cjmchale@cs.tcd.ie (Ciaran McHale) (04/06/91)
Anyone who is working in the area of concurrency for object oriented
languages, whether the research concentrates on developing powerful
synchronisation mechanisms or the conflict between synchronisation and
inheritance, should find the following references of use.
(Try saying all that five time in quick sucession when you're drunk:-)
Sometime next week (when I'm not so brain dead) I'll post explaining
the conflict between synchronisation and inheritance.
@incollection{Path-Expressions-1,
author = "R. H. Campbell and A. N. Habermann",
title = "{The Specification Of Process Synchronisation
by Path Expressions}",
booktitle = "Lecture Notes in Computer Science, No. 16",
publisher = "Springer Verlag",
year = "1973",
pages = "89--102",
annote = "This is the original paper on path expressions.
The version of path expressions described here is
a bit primitive but the paper is still worth reading.",
keywords = "k-path-expressions, k-regular-path-expressions,
k-synchronisation"
}
@inbook{Path-Expressions-2,
author = "Maekawa and Oldehoeft and Oldehoeft",
title = "{Operating Systems---Advanced Concepts}",
chapter = "3.4.2",
type = "Section",
pages = "71--79",
publisher = "Benjamin/Cummings",
year = "1987",
annote = "This gives an overview of both Open and
Predicate Path Expressions",
keywords = "k-path-expressions, k-predicate-path-expressions,
k-open-path-expressions, k-synchronisation"
}
@article{Path-Expressions-5,
author = "Roy H. Campbell and Robert B. Kolstad",
title = "{An Overview of Path Pascal's Design and the
Path Pascal User Manual}",
journal = "ACM Sigplan Notices",
year = "1980",
volume = "15",
number = "9",
pages = "13--24",
month = sep,
annote = "Path Pascal uses Open Path Expressions.",
keywords = "k-path-expressions, k-open-path-expressions,
k-path-pascal"
}
@inproceedings{Path-Expressions-6,
author = "Sten Andler",
title = "{Predicate Path Expressions}",
booktitle = "Sixth Annual ACM Symposium on Principles of
Programming Languages",
year = "1979",
pages = "226--236",
address = "San Antonio, Texas",
annote = "This paper describes the usage of Predicate Path
Expressions, their formal semantics and an
efficient implementation.",
keywords = "k-path-expressions, k-predicate-path-expressions"
}
@inproceedings{Other-Powerful-Sync-1,
author = "Chris Tomlinson and Vineet Singh",
title = "{Inheritance and Synchronisation with
Enabled-Sets}",
booktitle = "{OOPSLA} '89 Proceedings",
year = "1989",
pages = "103--112",
month = oct,
annote = "Enabled-Sets offer an easy way to inherit
synchronisation constraints. Also see
\cite{Other-Powerful-Sync-2}.",
keywords = "k-enabled-sets, k-inheritance, k-synchronisation"
}
@inproceedings{Other-Powerful-Sync-2,
author = "Dennis G. Kafura and Keung Hae Lee",
title = "{Inheritance in Actor Based Concurrent
Object-Orientated Languages}",
booktitle = "{ECOOP} 89",
year = "1989",
editor = "Stephen Cook",
pages = "131--145",
publisher = "Cambridge University Press",
month = jul,
annote = "This paper also appears in {\em The Computer
Journal\/}, VOL. 32, No. 4, 1989, pages 297--303.
The mechanism presented, {\em behaviour abstraction\/},
is really Enabled-Sets\cite{Other-Powerful-Sync-1}
by a different name.",
keywords = "k-enabled-sets, k-inheritance, k-synchronisation"
}
@book{Other-Powerful-Sync-3,
author = "Fran\c{c}oise Andr\'{e} and Daniel Herman and
Jean-Pierre Verjus",
title = "{Synchronisation of Parallel Programs}",
publisher = "North Oxford Academic",
year = "1985",
series = "Studies in Computer Science",
note = "Original French language edition
(Synchronisation de Programmes Parall\`{e}les, Dunod)
\copyright BORDAS 1983",
annote = "A whole book on using boolean expressions as a
means of expressing synchronisation constraints. This
book seems to have provided a basis for the
{\em Activation Conditions\/} of the Guide
language\cite{Comandos-Sync-3}.",
keywords = "k-synchronisation, k-synchronisation-counters"
}
@inproceedings{Theory-of-Synch-1,
author = "Toby Bloom",
title = "{Evaluating Synchronisation Mechanisms}",
booktitle = "Seventh International ACM Symposium on Operating
System Principles",
year = "1979",
pages = "24--32",
annote = "This paper discusses six features which an ideal
synchronisation mechanism should process and
discusses how existing mechanisms compare to this
ideal.",
abstract = "In recent years, many high-level synchronisation
constructs have been proposed. each claims to satisfy
criteria such as expressive power, ease of use,
and modifiability. Because these terms are so
impercise, we have no good methods for evaluating how
well these mechanisms actually meet such requirements.
This paper presents a methodology for performing such
an evaluation. Synchronisation problems are
categorised according to some basic properties, and
this categorisation is used in formulating more
precise definitions of the criteria mentioned, and in
devising techniques for accessing how well those
criteria are met.",
keywords = "k-synchronisation"
}
@article{Other-Powerful-Sync-4,
author = "Gregory R. Andrews",
title = "{Synchronising Resources}",
journal = "ACM Transactions on Programming Languages and
Systems",
year = "1981",
volume = "3",
number = "4",
pages = "405--430",
month = oct,
keywords = "k-synchronisation"
}
@article{Other-Powerful-Sync-5,
author = "Denis Caromel",
title = "{Service, Asynchrony, and Wait-By-Necessity}",
journal = "Journal of Object Orientated Programming (JOOP)",
year = "1989",
pages = "12--22",
month = nov,
annote = "This paper discusses the addition to Eiffel of a
{\em process object\/} so that objects are split into
two basic categories---passive and active. A much
better paper describing this mechanism can be found in
\cite{Other-Powerful-Sync-24}.",
keywords = "k-eiffel, k-active-objects"
}
@article{Monitors-4,
author = "{C.A.R.} Hoare",
title = "{Monitors: An Operating System Structuring
Concept}",
journal = "Communications of the ACM",
year = "1974",
volume = "17",
number = "10",
pages = "549--557",
month = oct,
keywords = "k-monitors"
}
@misc{Comandos-Sync-3,
author = "D. Decouchant and S. Krakowiak and M. Meysembourg
and M. Riveill and X. Rousset de Pina",
title = "{A Synchronisation Mechanism for Typed Objects
in a Distributed System}",
howpublished = "Presented at the workshop on
``Object-Based Concurrent Programming'', OOPSLA '88,
San Diego",
year = "September 1988",
note = "Abstract in {\em ACM Sigplan Notices\/},
24(4):105--107, April 1989",
annote = "The Guide language uses {\em Activation Conditions\/},
which are boolean expressions on synchronisation
counters and instance variables, for expressing
synchronisation constraints.",
keywords = "k-synchronisation, k-guide, k-activation-conditions,
k-comandos"
}
@inproceedings{Misc-3,
author = "J. Eliot and B. Moss and Walter H. Kohler",
title = "{Concurrency Features for the Trellis/Owl
Language}",
booktitle = "{ECOOP} '87---European Conference on Object-Oriented
Programming",
year = "1987",
editor = "G. Goose and J. Hartmanis",
pages = "171--180",
publisher = "Springer-Verlag",
month = jun,
note = "This is Volume 276 of {\em Lecture Notes in Computer
Science\/}.",
keywords = "k-trellis, k-owl, k-concurrency, k-locks, k-queues"
}
@article{Misc-4,
author = "David L. Detlefs and Maurice P. Herlihy and
Jeannette M. Wing",
title = "{Inheritance of Synchronisation and Recovery
Properties in Avalon/C++}",
journal = "{IEEE} Computer",
year = "1988",
pages = "57--69",
month = dec,
keywords = "k-inheritance, k-synchronisation, k-transactions,
k-atomicity"
}
@inproceedings{Misc-5,
author = "Pierre America",
title = "{Inheritance and Subtyping in a Parallel
Object-Oriented Language}",
booktitle = "{ECOOP} '87---European Conference on Object-Oriented
Programming",
year = "1987",
editor = "G. Goos and J. Hartmanis",
pages = "234--242",
publisher = "Springer-Verlag",
month = jun,
note = "This is Volume 276 of {\em Lecture Notes in Computer
Science\/}.",
keywords = "k-inheritance"
}
@inproceedings{Other-Powerful-Sync-6,
author = "J. E. Grass and R. H. Campbell",
title = "{Mediators: A Synchronisation Mechanism}",
booktitle = "Proceedings of the Conference on Distributed
Computer Systems",
year = "1986",
month = sep,
pages = "468--477",
organization = "IEEE",
abstract = "This paper describes a construct called a
{\em mediator\/}. Mediators support synchronisation
and scheduling for systems programming within
distributed systems. Mediators are based on a resource
view of systems, and fit within a programming
methodology that emphesises resource modularity,
synchronisation modularity and encapsulated
concurrency. The paper examines other existing
synchronisation mechanisms in the light of modular
programming requirements. Subsequently, a sample
syntax and semantics for mediators is presented with
many examples.
\par
The mediator includes many interesting features.
These include: an adaptation of guarded commands;
{\em keys\/} that allow requests to be examined and
manipulated before they recieve service; parallel
guard execution; coupled and uncoupled modes of
service execution.
\par
Finally this paper discusses a few aspects of
implementation.",
annote = "The mediator concept is very powerful but it provides
it's power at the price of some complexity.",
keywords = "k-synchronisation, k-mediators"
}
@unpublished{Comandos-Sync-7,
author = "D. Decouchant and P. le Dot and M. Riveill",
title = "{A Synchronisation Mechanism for an Object Oriented
Distributed System}",
note = "Bull-IMAG, Z. I. de Mayencin - 2, rue Vignate,
38610 Gi\`eres - France",
month = feb,
year = "1990",
abstract = "This paper presents a mechanism for synchronising
shared objects in a distributed system based on
persistant, typed objets. Synchronisation constraints
are expressed as separate control clauses and are
factored for a class of objects. The interference of
this mechanism with inheritance and transactions is
examined and solutions are proposed. Examples of
synchronised objects are provided and a
semaphore-based implementation of this mechanism is
described.",
annote = "This is basically an updated version of
\cite{Comandos-Sync-3}",
keywords = "k-comandos, k-guide, k-activation-conditions,
k-synchronisation, k-inheritance, k-transactions"
}
@inproceedings{Other-Powerful-Sync-7,
author = "O. M. Nierstrasz",
title = "{Active Objects in Hybrid}",
booktitle = "{OOPSLA} '87 Proceedings",
editor = "Norman Meyrowitz",
organization = "ACM",
note = "Special issue of {\em ACM SIGPLAN Notices\/},
22(12):243--253",
abstract = "Most object-oriented languages are strong on
reusability or on strong-typing, but weak on
concurrency. In response to this gap, we are developing
{\em Hybrid\/}, an object-oriented language in which
objects are the active entities. Objects in Hybrid are
organised into {\em domains\/}, and concurrent
executions into {\em activities\/}. All object
communications are based on remote procedure-calls.
Unstructured {\em sends\/} and {\em accepts\/} are
forbidden. To this the mechanisms of
{\em delegation\/} and {\em delay queues\/} are added
to enable switching and triggering of activities.
Concurrent subactivities and atomic actions are
provided for compactness and simplicity. We show how
solutions to many important concurrent problems, such
as a pipelining, constraint management and
``administration'' can be compactly expressed using
these mechanisms.",
keywords = "k-hybrid, k-queues, k-delegation, k-atomicity,
k-active-objects"
}
@article{Other-Powerful-Sync-8,
author = "Anand Tripathi and Mehmet Aksit",
title = "{Communication, Scheduling, and Resource Management
in SINA}",
journal = "JOOP (Journal of Object Oriented Programming)",
year = "1988",
pages = "24--37",
month = nov,
keywords = "k-sina, k-concurrency, k-synchronisation"
}
@article{Other-Powerful-Sync-9,
author = "A. J. Gerber",
title = "{Process Synchronisaion by Counter Variables}",
journal = "ACM Operating Systems Review",
year = "1977",
volume = "11",
number = "4",
pages = "6--17",
month = oct,
abstract = "A new method for expressing synchronisation is
presented which derives from several concepts in
existing notational schemes. Synchronisation
conditions areexpressed in terms of (integer) counters
which are incorporated into the definitions of data
objects shared by several asynchronous processes.
It is shown that the method is at least as powerful as
PV-type synchronisation, and the solution to some
``classical'' problems are presented using the
notation.",
annote = "This is an early paper describing the use of
synchronisation counters and boolean guards. It is an
interesting read (even if only from a historical
viewpoint). Criticisms and defense of this paper
appear in
\cite{Other-Powerful-Sync-10,Other-Powerful-Sync-11}.",
keywords = "k-boolean-guards, k-synchronisation"
}
@misc{Other-Powerful-Sync-10,
author = "Sten Andler and Peter Feiler and A. Nico Habermann
and Walter Tichy",
title = "Letter to the editor",
howpublished = "ACM Operating Systems Review, 12(1):6--11",
month = jan,
year = "1978",
annote = "This letter criticises Gerber's paper
\cite{Other-Powerful-Sync-9}.",
keywords = "k-synchronisation, k-boolean-guards"
}
@misc{Other-Powerful-Sync-11,
author = "A. J. Gerber",
title = "Letter to the editor",
howpublished = "ACM Operating Systems Review, 12(3):5--10",
month = jul,
year = "1978",
annote = "This letter responds to the criticisms
\cite{Other-Powerful-Sync-10} of the author' previous
paper \cite{Other-Powerful-Sync-9}.",
keywords = "k-synchronisation, k-boolean-guards"
}
@book{Other-Powerful-Sync-12,
author = "Akinori Yonezawa and Mario Tokoro",
title = "Object-Oriented Concurrent Programming",
publisher = "MIT Press",
year = "1987",
series = "Computer Systems Series",
annote = "This book contains 10 papers in total. The systems
covered include Act~1, Actors, ABCL/1, Concurrent
Smalltalk, Orient84/K, POOL-T, the Formes System and
Omega.",
keywords = "k-synchronisation, k-concurrency, k-objects"
}
@phdthesis{Other-Powerful-Sync-13,
author = "Colin Atkinson",
title = "{An Object-Oriented Language for Software Reuse and
Distribution}",
school = "Department of Computing, Imperial College of Science,
Technology and Medicine, University of London",
address = "London SW7 2BZ",
year = "1990",
month = feb,
abstract = "\ldots
\par
This thesis describes a language, DRAGOON, which
provides a uniform a coherent vehicle for supporting
reuse, distribution and reconfiguration in
large-scale, embedded systems. The language is
primarily ``object-oriented'', providing the powerful
reuse mechanisms of inheritance, polymorphism and
dynamic binding, but is also highly ``Ada-oriented''
in that it incorporates many Ada features for
``programming-in-the-small'', and can be translated
into standard Ada for execution in a natural and
straightforward way.
\par
\ldots In concurrent systems, the synchronisation
conditions ruling the relative execution of methods
are superimposed on purely ``sequential'' classes by
the inheritance of special predefined ``behavioural
classes''\ldots",
annote = "This is a definitive work on DRAGOON. As can be
expected, this is much more complete and satisfying
than the articles on DRAGOON.",
keywords = "k-dragoon, k-synchronisation, k-denotic-logic
k-behavioural-classes"
}
@inproceedings{Other-Powerful-Sync-14,
author = "Andrea Di Maio and Cinzia Cardigno and Rami Bayan
and Catherine Destombes and Colin Atkinson",
title = "{DRAGOON: An Ada-based Object Oriented Language for
Concurrent, Real-Time, Distributed Systems}",
booktitle = "Ada-Europe International Conference",
year = "1989",
address = "Madrid",
month = jun,
abstract = "DRAGOON is a design and programming language that
enriches Ada with the typical features of an object
oriented paradigm and can be automatically translated
into Ada. This paper describes how it can be used to
design concurrent, distributable and dynamically
reconfigurable applications.",
keywords = "k-dragoon, k-synchronisation, k-denotic-logic
k-behavioural-classes"
}
@inproceedings{Other-Powerful-Sync-15,
author = "Stefano Genolini and Andrea Di Maio and Cinzia
Cardigno and Stephen Goldsack and Colin Atkinson",
title = "{Specifying Synchronisation Constraints in a Concurrent
Object-Oriented Language}",
booktitle = "Technology of O-O Languages and Systems (TOOLS '89)",
abstract = "This paper describes briefly how concurrency,
synchronisation and distribution are supported in the
object oriented language DRAGOON. In DRAGOON
separation of concerns for the functionality and the
synchronisation behaviour of an object is obtained by
using a form of inheritance. An abstract specification
of synchronisation properties is proposed that uses a
simple form of denotic logic.",
keywords = "k-dragoon, k-synchronisation, k-denotic-logic
k-behavioural-classes"
}
@misc{Other-Powerful-Sync-16,
author = "Colin Atkinson and Andrea Di Maio and Rami Bayan",
title = "{DRAGOON: An Object-Oriented Notation supporting the
reuse and Distribution of Ada Software}",
howpublished = "Position paper for Ada real-time issues workshop,
Pitlochry",
month = jun,
year = "1989",
abstract = "Among the more radical proposals for changes to the
Ada standard in Ada9X are those advocating the
introduction of ``object-oriented'' features
exemplified by languages such as Smalltalk and Eiffel.
DRAGOON is a language which supports all the
fundamental concepts of object-oriented programming
(classes, inheritance, polymorphism, dynamic binding)
in an Ada style, while retaining most of the features
of current Ada. It also employs enhanced forms of
multiple inheritance to support concurrency,
distribution and reconfiguration. Although not
designed specifically as a proposal for the Ada9X
project, therefore, DRAGOON may serve as a basis for
the development of Ada in an ``object-oriented''
direction. This paper provides a brief overview of the
language.",
keywords = "k-dragoon, k-synchronisation, k-denotic-logic
k-behavioural-classes"
}
@article{Misc-11,
author = "Maurice Herlihy",
title = "{A Methodology for Implementing Highly Concurrent Data
Structures}",
journal = "SIGPLAN Notices",
year = "1990",
volume = "25",
number = "3",
pages = "197--206",
month = mar,
note = "Special Issue: Second ACM SIGPLAN Synmposium on
Principles \& Practice of Parallel Programming
(PPOPP)",
abstract = "A {\em concurrent object\/} is a data structure shared
by concurrent processes. Conventional techniques for
implementing concurrent objects typically rely on
{\em critical sections\/}: ensuring that only one
process at a time can operate on the object.
Nevertheless, critical sections are poorly suited for
asynchronous systems: If one process is halted or
delayed in a critical section, other, non-faulty
processes will be unable to progress. By contrast, a
concurrent object implementation is
{\em non-blocking\/} is it always guarantees that some
process will complete an operation in a finite number
of steps, and it is wait-free if it guarantees that
{\em each\/} process will complete an operation in a
finite number of steps. This paper proposes a new
methodology for constructing non-blocking and wait-free
implementations of concurrent objects. The object's
representation and operations are written as stylised
sequential programs, with no explicit synchronisation.
Each sequential operation will is automatically
transformed into a non-blocking or wait-free operation
using novel synchronisation and memory management
algorithms. These algorithms are presented for a
multiple instruction/multiple data (MIMD) architecture
in which $n$ processes communicate by applying
{\em read}, {\em write}, and {\em compare\&swap\/}
operations to a shared memory.",
annote = "I can't seem to grasp all of this paper. However, what
I do understand is that this is important research.
Hopefully in a few years the ideas in this paper will
have matured a bit more and will be more accessable.",
keywords = "k-synchronisation"
}
@inproceedings{Monitors-12,
author = "Robert Seliger",
title = "{Extending C++ to Support Remote Procedure Call,
Concurrency, Exception Handling, and Garbage
Collection}",
booktitle = "USENIX C++ Conference Proceedings",
year = "1990",
pages = "241--261",
address = "San Francisco, California",
month = "9--11 April",
annote = "The concurrency mechanism used is a variation of
monitors. As such it is not very exciting but it has
been integrated quite well into the C++ language.
What is most surprising is that Monitors are still
being used 16 years after Hoare's paper on them.
Not too many other high level synchronisation
mechanisms can claim that (Path Expressions being the
only other example that springs to mind).",
keywords = "k-monitors, k-C++, k-exceptions, k-RPC,
k-garbage-collection"
}
@inproceedings{Other-Powerful-Sync-24,
author = "Denis Caromel",
title = "{Concurrency: An Object-Oriented Approach}",
booktitle = "TOOLS 2 (Technology of Object-Oriented Languages
and Systems)",
year = "1990",
editor = "Jean B\'ezivin and Bertrand Meyer
and Jean-Marc Nerson",
pages = "183--197",
publisher = "Angkor",
abstract = "Object-oriented programming seems well-suited for
concurrent programming; the design of a system as a
collection of concurent executable objects is
attractive. While many attempts have been made to
provide object-oriented languages with a model of
concurrency, few of them deal with reusability and
methodology.
\par
We propose a concurrent model that takes into account
such important concerns. We insist on concept
unifications: the underlying reasons that make
object-oriented programming adapted to concurrency. It
leads us to propose a concurrent object-oriented
design method.
\par
The first section presents the model which makes use
of object-oriented techniques such as inheritance and
polymorphism. The second puts it in concrete form
through a small example. Then, we develop a concurrent
object-oriented method which takes advantage of the
unification of concepts. The main ideas are to
postpone the process structuring and to use
flexibility for refinements. A real time example
exercises the method. We conclude with implementation
issues and perspectives.",
annote = "This paper does much more justice to Caromel's
synchronisation than his earlier paper
\cite{Other-Powerful-Sync-5}. The mechanism presented
in this paper is actually {\em quite\/} powerful
according to Bloom's evaluation mechanism
\cite{Theory-of-Synch-1}. To me it appears to be
rather like Mediators \cite{Other-Powerful-Sync-6} in
some regards (but more unified and easier to use).
This mechanism is for active objects with a single
thread of control which services requests (messages).
The synchronisation/scheduling policies are
implmeneted algorithmically rather than in a
declarative manner (Path Expressions,
synchronisation counters etc).",
keywords = "k-synchronisation, k-active-object"
}
Ciaran.
--
Ciaran McHale "There's a lot to be said for verbosity." ----
Department of Computer Science, Trinity College, Dublin 2, Ireland. \ /
Telephone: +353-1-772941 ext 1538 FAX: +353-1-772204 \/
Telex: 93782 TCD EI email: cjmchale@cs.tcd.ie