Concurrent Object-Oriented Programming:
The MP-EIFFEL Approach
Miguel Oliveira e Silva, DET–IEETA, University of Aveiro, Portugal
|
 |
TOOLS USA
2003
PROCEEDINGS
PDF Version |
Abstract
This article evaluates several possible approaches for integrating concurrency
into object-oriented programming languages, presenting afterwards, a new language
namedMP-Eiffel. MP-Eiffel was
designed attempting to include all the essential properties of both concurrent
and object-oriented programming with simplicity and safety.
A special care was taken to achieve the orthogonality of all the language mechanisms,
allowing their joint use without unsafe side-effects (such as inheritance anomalies).
1 INTRODUCTION
In this article a new concurrent object-oriented programming
language is presented.
This language – named MP-Eiffel
(Multi-Processor Eiffel) – is
developed as an
extension to the sequential object-oriented language Eiffel. This choice
is not
accidental. Eiffel’s powerful, safe, and simple object-oriented
semantics proved to
be an excellent framework to introduce concurrency mechanisms.
The choices
made for the language concurrent mechanisms, and their semantics,
resulted from an attempt to provide a safe and simple integration of
the essential
properties of both worlds: concurrent and sequential object-oriented
programming.
In section 2 the essential characteristics, requirements, problems,
and elementary
solutions of concurrent programming are briefly reviewed. Object-oriented
sequential
programming is then briefly introduced, giving emphasis to its fundamental
and
useful properties.
Since this work is about creating programming language
mechanisms, some important
language design rules are enumerated and succinctly justified. Those
rules
will be used to justify the choices made in MP-Eiffel.
Several
existing possibilities for integrating concurrency in an object-oriented
language are presented and evaluated in section 4. A special care is
taken to study
the conditions under which unsafe interference may arise from the joint
use of some
mechanisms, such as the well known problem of “inheritance anomalies”.
It is shown
that such problems can be prevented without compromising neither of
the essential
properties of both worlds.
Other important concurrency safety problems
such as deadlocks, and other synchronization
requirements such as scheduling are briefly approached.
Finally, the MP-Eiffel language
is presented. MP-Eiffel aims
to be a safe concurrent language, where unsynchronized accesses
to shared resources are statically prevented (unlike, for example,
Java).
Concurrent activities are performed by abstract processors (a
term reused from
Meyer’s approach to concurrency: SCOOP), which may access shared
objects, and
also communicate directly with each other through a mechanism named “trigger”.
Concurrent
access to objects use a readers-writer semantics, in which side-effect
free accesses may occur simultaneously (the only acceptable form of
intra-object
concurrency), but at most only one writer is allowed to proceed.
The
type system is used to safely control the access to shared objects,
with the
introduction of two type modifiers: shared and remote.
SCOOP semantics
of reusing the separate part of preconditions for conditional
synchronization is also used in MP-Eiffel.
The exception handling mechanism
is adapted for a concurrent environment in
which a synchronous communication mechanism (either when accessing
a shared object,
or when sending a synchronous message to another processor) retains
Eiffel’s
normal semantics. For asynchronous communication between processors
the message
communication status is verifiable by special direct inter-processor
communication
functions (synchronous).
MP-Eiffel takes the view of removing
from programs all time dependent requirements
(scheduling, exclusion, etc.) which do not affect their logical semantics,
delegating them either to the language semantics (exclusion, deadlocks)
or to a
separate description program (scheduling, real-time requirements).
This way the
programs are safer and easier to understand.
2 CONCURRENT PROGRAMMING
In this section we will make a synthesis of
the most important characteristics of a
concurrent programming system (programming language and libraries).
A special
care will be taken to generalize as much as possible the concepts involved,
and to
identify the most serious problems raised by this type of programming.
Abstract concurrent programming
Since we are interested in the essential properties
of concurrency, we don’t want to
bind our concurrent processing entities to specific “lower level” realizations
such as
threads, processes, object request brokers, MPI, PVM, or any other.
Instead, we
will use an abstract notion of “processor” adapted from
Meyer [Mey97, page 964]:
A processor is an autonomous thread of control
capable of supporting
the sequential execution of instructions.
Nothing is assumed on
how this virtual processor will be implemented at runtime.
We won’t even exclude the possibility that a processor may start
by being a thread
in one machine and end as a process in another through a remote procedure
call
mechanism.
In general, concurrency does not require simultaneous (parallel)
processor execution.
A concurrent program can be thought as the concurrent execution of
sequential“
programs”, one for each processor (of course, they may depend
highly on
each other).
From a concurrent programming system we expect the ability
to – safely – specify
and control two things:
- concurrent execution of processors;
- inter-processor synchronization and communication.
Concurrent
execution of processors
Concurrent systems need mechanisms to start,
support, and terminate the execution
of processors, either as part of the programming language constructs
or provided
in a library. In particular they need to assign processors to specific
processing devices
(threads, processes, computers in a distributed system, or any other).
This
assignment will be called heterogeneous if the concurrent system
allows the assignment
of different processing devices for processors, otherwise it will
be classified as
homogeneous processor mapping.
Heterogeneous processor mapping is a
desirable property since it enforces the
decoupling between a concurrent program and specific processing devices.
However,
specific types of concurrent programming, such as real-time and embedded
systems
may pose strong restrictions to valid (feasible) processor mappings.
Inter-processor
synchronization and communication
To ensure a correct inter-processor
interaction it is necessary to enforce proper timing
constraints between them. Such synchronization requirements may arise
from the
necessity to guarantee safety properties [Lam83], the verification
of some condition,
the need to impose a specific processor scheduling strategy [RF77],
or several of
these possibilities at the same time.
Safety
A safety problem exists when a program may have an unpredictable
(erroneous)
behavior due to incorrect inter-processor synchronization.
This type
of errors is the most serious correctness problem raised by concurrent
programming. They are dependent on low level timing conditions which
might be
hard to reproduce and detect.
Race conditions are the simplest of this
type of problems. They exist whenever
several processors simultaneously attempt to modify a shared resource
without a
correct exclusion synchronization (which may prevent any of them
to do what they
expect, leaving the resource in an inconsistent unsafe state). This
problem is solved
by protecting the access to the mutable shared resource within a
critical section,
using for example, semaphores [Dij68].
One advantage of a concurrent
programming language when compared with a
library approach for concurrency (such as POSIX threads in C [But97]),
is that it
gives the possibility of prevention of this type of errors using
the language semantics,
as will be shown in the next section.
Other safety problems created
by synchronization mechanisms may also exist,
such as deadlocks, and the more general problem of ensuring liveness
[Lam83].
For correctness and robustness reasons, our goal should be
to ensure that no
such errors would ever occur in a concurrent program.
Conditional synchronization
Frequently the access to a critical region
of a shared resource depends not only on
exclusion needs, but also on the verification of some resource related
condition. For
example, a printing processor is required to conditionally wait for
the non-emptiness
of its shared job queue.
There are several mechanisms well adapted to
this problem such as conditional
critical regions and monitors [Hoa74].
Scheduling
Scheduling is the strategy for choosing the processor to
be executed when processor
contention occurs (which may depend on limited processing devices
resources, or
resulting from an attempt to access a shared resource).
In general,
scheduling depends on three factors [RF77]: the decision mode, the
priority function, and an arbitration rule. The decision mode characterizes
the time
instances in which processor scheduling is computed, the priority
function is the
processor ordering algorithm, and the arbitration rule is the strategy
used to choose
between equal priority processors.
The scheduling choice may affect
the safety of concurrent programs, since it may
prevent some deadlock problems, or – such as when an extremely
unfair algorithm
is used – it may pose other liveness problems such as starvation
to some processor.
Deadlocks
Deadlocks are situations in which processors wait
forever for each others allocated
resources. In order for a deadlock to occur, four necessary conditions
must be verified
[CES71]:
- mutual exclusion (exclusive access to a resource);
- hold and wait
(waiting for resources while holding at least one);
- no preemption;
- circular wait.
The absence of any of these conditions is sufficient
to prevent deadlocks.
Three possible approaches can be applied to handle
this problem [CES71]:
- Prevention;
- Avoidance;
- Detection.
Deadlock prevention ensures the absence of deadlocks
by statically assuring that
at least one of the four conditions does not apply. For example,
if a processor is only
allowed to hold a unique resource (preemption allowed), or if processors
must acquire
all resources at the same time (hold and wait denied), or if an ordered
allocation
of resources is imposed (circular waiting impossible), then deadlocks
cannot occur.
However, some care must be taken in the usage of prevention techniques
since they
tend to be too costly to the overall performance of the concurrent
system.
Another safe possibility is to use deadlock avoidance techniques.
If information
about current and future resource allocation is available, then that
knowledge can
be used to avoid circular waits (see, for example, the Banker’s
algorithm [Dij68,
Hab69]).
The third possibility is to have deadlock detection algorithms
and recovery strategies
(which may use exception handling techniques).
Only the first two approaches
are guaranteed to be safe – since
they do not affect
the normal execution of a processor – so those are the ones a
safe language should
consider. Unlike the mutual exclusion problem – which
is a local problem with a local
solution – this problem arises due to a global (system wide)
interference between
processors. This characteristic makes it a much more difficult problem
to tackle.
Communication
By far the most important request for synchronization
is the necessity for interprocessor
communication. A communication mechanism is said to be synchronous
in relation to a processor if that processor may be required to wait
(block), otherwise
it is called asynchronous.
There are two basic models for inter-processor
communication:
- message passing (direct);
- shared memory1 (indirect).
In message passing, processors communicate
directly using some sort of a (real
or virtual) point-to-point connection. This form of communication
is well adapted
for loosely connected processors (as in a distributed system),
and for client-server
topologies. The sender processor in this communication abstraction
can either be
synchronous or asynchronous.
Shared memory is an indirect inter-processor
mechanism, in which processors
communicate by using a shared writable and readable entity. It
is well adapted
for processors who need to frequently share mutable information.
Shared memory
requires a synchronous communication.
As noted in [LN78] either model
can be converted into the other, so one could
argue that in principle a concurrent language only needs one of
them. However,
they represent different processor communication abstractions and
have different
requirements to the underlying execution system, so it is also
defensible to have
them both.
3 DESIGN OF OBJECT-ORIENTED LANGUAGES
Meyer [Mey97, page 147] defines
object-oriented software construction as:
(...) the building of software
systems as structured collections of possibly partial abstract data
type implementations.
An Abstract Data Type (ADT) [LZ74, Mey97] is,
by definition, a type that is
completely defined by the external operations it provides, and
its semantics (axioms
and preconditions). In object-oriented programming ADTs are implemented
with
classes [Mey97], and their run-time instances are called objects.
Making
the software’s topmost structure depend only on ADTs and
their relations,
simplifies the development of complex systems, due to its modularity
and
understandability [Mey97, page 39].
An object-oriented programming language is characterized by some
fundamental
properties:
- Objects are first-class entities, aware of their behavior
(defined by its class),
to whom some operations may be requested, and which are themselves
usable
as arguments on operation requests;
- There is an explicit and uniform communication mechanism
between objects
(message passing in SmallTalk terminology, or feature calling in
Eiffel, C++
or Java);
- The ability to transparently use objects on behalf of any
type applicable to its
class (inclusion polymorphism).
- The ability for a class to
inherit from others, reusing or redefining their features.
Additionally some languages also provide other important
mechanisms:
- Information hiding [Par72b, Par72a], through explicit private
and public class
interfaces2;
- The ability to specify the ADT semantics (invariants and
preconditions) in
the class, promoting Design by Contract [Mey97, chapter 11];
- Multiple inheritance;
- Parametric polymorphism [CW85][Mey97, chapter 10];
- Exception handling;
- Class attribute protection [Mey97, page 206] (an attribute
can only be changed
by routines of its class).
Some authors [Car88, CHC90] argue for the
necessity to separate the notion of
inclusion polymorphism (subtyping), from the ability to
reuse features using inheritance
(subclassing). In the remaining of this article, following
the language design
rules of simplicity and uniqueness presented ahead, we
will follow Meyer’s [Mey97]
approach in which the same language mechanism – inheritance – provides
both possibilities
(at the same time if needed). Although simpler, this choice
poses an extra
burden on the language type system to guarantee the detection
of all type errors
during program compilation.
Hereafter we shall use the expression “object
entity”,
to designate the programming
language constructs which handles object references or
values (in Eiffel they
are class attributes, routines local variables or their
formal arguments [Mey97, page
213]).
The challenge is how to integrate concurrent and object-oriented
systems without
compromising none of their essential properties.
Language design guidelines
To ease the process of construction of high
quality programs (especially in what
concerns correctness), it is not enough for a programming
language to have all or
most of desired mechanisms; the way they are put together
and their usability are
also essential.
On language design Hoare [Hoa73] notes that programming
languages should
help the programmer in the most difficult aspects of programming:
program design,
documentation and debugging.
The first fundamental rule presented by
Hoare for good language design is simplicity,
which can be stated as follows.
Rule 1 (Simplicity) A programming language
should be simple to understand and
use.
Of course a programming language is a tool to express solutions
of problems, so
although simplicity is essential on the implementation
of its fundamental properties
and mechanisms it is not a reason to ignore them. Otherwise
an elusively simpler
structure in the programming language may cause a much
higher complexity in the
programs. This leads to another essential rule: completeness.
Rule 2
(Completeness) A programming language should implement
the mechanisms, and have the properties considered essential to its
methodology
of problem
solving.
The second essential rule presented by Hoare regards safety3
on language constructs
usage.
Rule 3 (Safety) Programming language mechanisms
should be prevented from producing
meaningless results.
This rule justifies, for example, the use of a
static type system – which
prevents
the occurrence of type errors at run time – and it will also
be essential for evaluating
the proposed concurrent mechanisms.
Other less essential rules should
be taken into consideration when designing
programming languages. That is the case of efficiency,
which promotes the language
use in resource demanding applications.
Rule 4 (Efficiency)
The programming
language should not compromise the automatic generation of programs
which make
an efficient use of system
resources (CPU,
memory, etc.).
Meyer [Mey92, appendix B], presents two other rules.
Rule 5 (Uniqueness)
The language design
should provide one good way to express every operation of interest;
it should avoid providing
two.
Rule 6 (Consistency)
The language design should
never depart from a small number
of powerful ideas, taking them to their full realization.
Other guidelines
can be formulated which go along with these rules.
Rule 7 (Abstraction)
Programming language constructs
should be completely defined using only their external abstract behavior,
regardless of implementation.
This rule promotes simplicity. The external
abstract behavior of programming
language constructs should be made simple, regardless of
their possible implementations.
Simple mechanisms are sometimes hard to implement correctly.
For example,
the ability to covariantly redefine feature signatures
in Eiffel (which is a simple
and useful behavior), is difficult to implement in order
to ensure a safe system
[Coo89][Mey97, page 621].
Rule 8 (Orthogonality)
Programming language
constructs should be made as orthogonal
as possible, in order to make them work correctly regardless
of being used
together with others.
The observance of this rule simplifies the language
semantics, and is a guarantee
that no undesirable side-effect will occur when its mechanisms
are jointly used. It is
important to note that orthogonality applies to the constructs
essential semantics,
not to their eventual implementations. The implementation
of a language mechanism
may depend heavily on the context in which it is used.
For example, the
uniform inter-object communication mechanism (feature call
or message passing using
Eiffel or SmallTalk terminology) can be reused in a concurrent
system for
either of the two types of processor communication: shared
memory or message
passing.
4 THE ROAD TO OBJECT-ORIENTED CONCURRENCY
In this section we shall
evaluate some object-oriented approaches for concurrency, in
order to justify the choices adopted in our approach presented
in the next section.
Processors and objects
There are several possibilities for integrating
processors with objects. Some approaches
promote processors to classes (//Eiffel [Car93], POOL [Ame87]),
in which
there is a special main feature with the processor’s
body and synchronization code.
This possibility raises many problems. It assumes that
processors are valid
ADTs, which is in general difficult to accept (it would
be an ADT with a unique
operation). If that concept is applied to the special concurrent
case of a sequential
program (uni-processor), then we would be at odds with
the basic object-oriented
design definition of constructing software systems as organized
collections of ADTs
implementations. A better possibility is presented by
the actors model [Agh86, AK99], in which
instead of promoting processors to classes, classes are
augmented with a processor,
capable of processing and responding to a call to any of
the class’s
features. This
model is well adapted to the distributed modular message
based nature of objectoriented
programming, but has the drawback of making processors
and classes hardwired
entities.
Meyer’s proposal for concurrency with Eiffel [Mey97,
page 951] – SCOOP4– goes
much further by allowing a processor to handle multiple communicable
objects
(of different types if necessary). In SCOOP the concurrent
nature (separateness) of
an object may not be a property of its class, but simply
a property of the object’s
entities which use it. This makes objects and processors
more independent entities,
simplifying the reuse of normal sequential classes in a
concurrent system.
However, these two approaches – Actors
and SCOOP – restrict
our concurrency
model to explicit message passing communication between
processors (no object is
ever executed by more than one processor), which although
being adaptable to any
concurrency need, may not be the more appropriate and efficient
option. Frequently
our concurrency needs demand direct resource sharing between
processors in which
the participation of a third processor is not the simplest
and more appropriate
programming approach (using a real life analogy: why restrict
ourselves to use a
unique “chauffeur” to handle a shared car,
when anyone can drive).
A fourth option is to make objects
and processors completely orthogonal entities,
in which an object may be executed by different processors,
and the processor creation
depends on the use of some specific mechanism. This is
the approach taken in
several widely used concurrent systems such as Java threads
and ADA’s
protected
types. This possibility, however, if not done correctly
creates more safety problems,
resulting from concurrent access synchronization. Those
problems will be studied
below. Intra-object concurrency
Intra-object concurrency is the possibility
of more than one processor operating
simultaneously inside an object. Is this type of concurrency
acceptable? If so, in
what conditions?
Since the fundamental theory behind object-oriented
programming is taking
classes as ADTs implementations, the answer to the first
question is immediate:
It can only be allowed if it does not compromise the class’s
ADT implementation.
In sequential programming an object
is only usable during its stable times
[Mey97, page 364]: after its creation, before or after
terminating the execution of
any of its features (times at which the class invariant
must hold). When an object
feature is being executed, the class invariant may not
hold, in which case it could
invalidate a feature call from another processor. Also,
a conditional wait for the invariant, and eventually the feature
precondition,
is not a sufficient condition to allow this type of concurrency,
since it may create
race conditions (the worst kind of concurrent errors),
and it does not take into
consideration the possibility of an incomplete invariant
implementation (which is a
common situation). A simpler sufficient (but not necessary)
condition is to consider
classes as monitors5, thus ensuring mutual exclusion on
the execution of any of its
features. This is the approach followed, for example, by
Actors, SCOOP and ADA’s
protected types.
Java completely ignores this problem, unacceptably
leaving that responsibility
to the programmer. For this reason Java is an unsafe language
for concurrent
programming [Han99].
One interesting exception to this mutual exclusion
rule is to allow intra-object
concurrency for simultaneous side-effect-free queries
to objects. For this reason, a
readers-writer model [CHP71] for object concurrent
access is a more general preferable
option (one writer excludes all other processors, but
multiple readers can simultaneously
access the object).
The enforcement of class attribute protection by
the language (as happens with
Eiffel), is also a desirable property since it prevents
the occurrence of a dangerous
unsafe intra-object form of concurrency resulting
from a change to an object state
outside the control of its class.
Synchronizing processors
As seen in the previous section, it is necessary
to impose appropriate timing constraints
when processors compete for a shared resource (object,
CPU). Such need
may arise from safety reasons (mutual exclusion, liveness),
conditional synchronization, or scheduling policies.
The integration of synchronization with
object-oriented mechanisms has been
one of the most difficult challenges, and has concentrated
much of the investigation
in this area.
The fundamental reason for this is simple to understand.
One of the key abstractions
that justifies much of the success of high-level sequential
programming
languages is the ability to ignore, during program development,
timing constraints
attached to the language constructs. A program expresses
the causality between instructions,
and ensures the verification of some logical, time independent,
conditions
before and after their execution [Flo67]. Concurrency may
break this simple view of
languages and programs. Object-oriented concurrency increases
this problem due to
the possible interference of some of its fundamental mechanisms
such as inheritance.
The coexistence of concurrency with
inheritance has been widely studied [Ame87,
KL89, MY93]. The problems it raises were named “inheritance anomalies” by
Matsuoka
(et al.) [MY93].
Inheritance anomalies
An inheritance anomaly occurs when the synchronization
scheme loses its initial goal
(mutual exclusion, conditional access or scheduling) in
a descendant class, forcing its
explicit redefinition. In the presence of these problems,
the use of inheritance may
became unsafe, which is unacceptable for a concurrent object-oriented
language.
Rule 9 (Inheritance Invariance)
A sufficient
condition which prevents inheritance
anomalies is the guarantee that the synchronization expected
in any object
entity in the program applies to all possible (conforming)
objects it may be attached
to.
If the language synchronization code (portion of the program
which specifies synchronization
behavior) is explicitly part of the program (explicit synchronization),
then the observance of this rule will most likely require
the unsafe cooperation of
the programmer. On the other hand, if implicit synchronization
is used together
with the type system in a static typed language, then there
is the possibility for a
static safety assurance. In order to reach that goal it
is necessary to guarantee that
the interaction with objects usable by more than one processor
is done through a
proper concurrency type modifier, and that the subtyping
relation (conformance)
imposes its observance.
Meyer’s SCOOP approach uses this strategy
by augmenting the type system with
the modifier SEPARATE to denote entities that have references
to objects belonging
to other processors, and by statically ensuring the absence
of “traitors”:
separate
objects attached to a non-separate object entity [Mey97,
page 973].
Synchronization programming
The preceding discussion suggests
the existence of two apparently irreconcilable situations:
Implicit synchronization disallows the possibility for
imposing some specific
synchronization need in the program, but on the other hand,
when concurrency was
presented in section 2 one of the requirements was to allow
precisely that: the ability
to specify (safe) synchronization schemes (such as a scheduling
policy).
Implicit synchronization is coherent with the already
mentioned idea that timing
dependent constraints should be kept apart from language
constructs in order
to simplify their semantics and to allow its reuse on different
(or even mutable) execution
systems. Following this reasoning, including non-essential
synchronization
requirements in the program would be a form of overspecification.
A
possible solution to this problem, following the orthogonality rule,
is to have an
external language (or configuration system) in which non-essential
synchronization
requirements may be expressed. The compiling and execution
systems would have to
validate such timing requirements (which may include real-time
constraints), build
and support the execution of programs in which the verification
of those constraints
is ensured (violations to them must be detectable and propagated
to the program
using an appropriate exception mechanism).
A similar approach is taken
in [RA95] for real-time specifications.
This approach also provides
a solution for implementing heterogeneous processor
mapping. In his SCOOP approach, Meyer uses for this purpose
a Concurrency
Control File [Mey97, page 971]. Conditional synchronization
Although many synchronization constraints
may, and most likely should, be separated
from the program’s logic, there are two important
exceptions: exclusion (since
it is a minimum requirement for a safe concurrent language);
and conditional synchronization.
Conditional synchronization depends highly on the program’s
state,
which makes it difficult to separate it into an external
safe specification.
How can then conditional synchronization
be integrated in a concurrent language,
without creating safety problems, and without interfering
with the other language
mechanisms? In object-oriented languages, objects interact
by calling each others public features
(routines or attributes), and – as already noted – a
safe concurrent interaction
between objects must occur in the object’s stable
times. This restriction strongly
suggests that conditional synchronization tests be located
in the object’s
class interface
(this also seems to be the simplest solution).
The next problem is to
decide in which part of the class’s interface
it should be
located. One possible scheme is to have a centralized conditional
synchronization
control (such as behavior abstractions [KL89]) separated
from the normal class interface.
This option seems to be an acceptable choice for synchronization
conditions
that apply to the call of any public feature of the class,
but it is highly questionable
when they apply only to a subset of those features (or
simply one of them).
Also, this option is highly sensitive to partitioning of
acceptable states inheritance
anomalies [MY93]. A partial solution for this type of inheritance
anomaly is to use
method (routine) guards, in which conditional synchronization
tests are attached
to the routines requiring their observance. A complete
solution requires that the
guards also apply to eventual routine redefinitions in
descendant classes.
Curiously (but not by chance) these
requisites seem quite similar to those applicable
to one of the semantic specification of routines: preconditions.
This observation
raises the question of how should assertions behave under
a concurrent interaction?
Assertions are correctness conditions, which must be verified
in the places where
they are declared. However, if an assertion (or part of
it) depends on more than
one processor (concurrent condition), its value may be,
from time to time, false due
to the (unpredictable) activity of another processor. This
is a safety problem: one
needs to lock the objects on which the assertion depends
before the test is made, but
then the assertion may sometimes fail due to unpredictable
timing relations between
competing processors, making it useless for correctness
assurance (they became part
of the problem, not the solution).
Again one is surprised with the similarity
of such reasoning with the one which
has led to the proposal of conditional critical regions
and monitors [Hoa74]. Meyer,
while studying this problem, called it the concurrent precondition
paradox [Mey97,
page 994].
Of course, one possible “solution” is to disallow
the existence of assertions which
depend on more than one processor. However, this would
be a very poor solution,
since it restricts tremendously the applicability of Design
by Contract.
Another alternative is to remove the concurrent
conditions from the assertions,
and use them as conditional synchronization tests before
assertion verification. This
approach, though a safe one, implies the introduction of
a new language construct
and the duplication of the assertions semantics (it goes
against the rules of simplicity,
uniqueness and orthogonality), and, more importantly, it
restricts the reuse of
sequential classes under a concurrent environment (since
they would lack conditional
synchronization tests).
A much simpler solution is to make the assertion
conditions that depend on
more than one processor, conditional synchronization tests.
This is Meyer’s elegant
solution to this problem [Mey97, page 996].
One last important observation
on this topic. From all the assertions that are
applicable to object’s state times – invariants,
preconditions and postconditions–
this scheme only makes sense for preconditions. Invariants
cannot be conditional
synchronization tests, because they must always hold in
the object’s
stable times
regardless of its executing processors. Postconditions,
on the other hand, apply
when the routine’s work is already done, so there is nothing
to wait for.
Deadlocks and other liveness problems
One last group of difficult synchronization
problems remains to be studied in the
context of its integration in an object-oriented language:
deadlocks, livelocks, and
other liveness problems. As mentioned previously, they
should be approached as
safety problems, and, as such, a safe concurrent language
should be able to ensure
its absence, either by prevention or avoidance techniques.
Not all of
the four necessary conditions for deadlock resolution can safely be
used for deadlock resolution under an object-oriented system.
That is the case
of “mutual exclusion” (if synchronous processor interaction
is required) and “no
preemption”. Breaking either of these conditions
would result in objects interacting
while in unstable times. Therefore, the only two conditions
that can be used to
prevent or avoid deadlocks are the “hold and wait” and “circular
wait” conditions.
Since deadlocks are a system problem
(not the responsibility of any individual
processor), their resolution requires system wide techniques.
That is not a unique
case in object-oriented languages: a similar situation
occurs, for example, in the use
of covariant feature signature redefinition in the presence
of subtyping.
Again, a static typed language (with concurrent
properties) with an implicit
synchronization scheme seems to be a promising approach
to the problem, due to
the fact that it may statically gather information about
probable resource allocation
needs. A smart compiling system may use a mixture of prevention
and avoidance
techniques (depending on the resource allocation patterns)
to ensure a safe program.
Also, these liveness problems
will most likely be simplified if resource (object)
allocation is concentrated and restricted to fewer places
in the program.
At this time this is still an open problem
requiring deeper analysis and experimentation.
Processors communication
Object-oriented programming uses a uniform
inter-object communication language
mechanism, so its reuse for processor communication arises
naturally (simplicity,
uniqueness, consistency, orthogonality and abstraction).
If this adaptation is quite
consensual, the same does not happen with the choice for
the appropriate model:
message passing or shared memory. At first sight, since
objects communicate with
each other through messages, the choice would seem obvious:
message passing
model. However, although both are message passing forms
of communication, they
apply to different things: objects and processors.
The message passing
inter-processor model of communication would be the correct
(and only) option if objects were at most handled by a
unique processor (as
happens with Actor languages and SCOOP). However, if
that is not the case, then
that choice is not so clear. The question here is not
whether objects communicate
through message passing (which they always do), but which
processor has the
responsibility to fulfill the request executing the appropriate
feature. If a concurrent
program is seen as the aggregation of communicating sequential
programs (one
for each processor) using shared resources, then the
simplest solution will be the
shared memory model. As will be seen, from this choice
results also a simpler and
more efficient integration of the exception handling
mechanism with concurrency.
Nevertheless, as mentioned previously, the usefulness
of a direct inter-processor communication
mechanism, as exists in Actors or SCOOP, is obvious.
It is useful, for
example, to implement client-server program architectures,
or for loosely connected
distributed systems.
This is a situation where language design rules
conflict with each other, and a
choice must be made. Considering the uniqueness rule (rule
5) and the fact that
either model can be converted into the other [LN78], the
use of only one of them
seems the correct approach. However, they represent two
different ways of expressing
concurrent programming, and so, without them, a language
would be less complete.
To convert one in the other, the resulting program loses
simplicity (rule 2).
If a specific direct inter-processor
(message passing) mechanism is to be devised,
then a way must be found to identify processors (otherwise
this form of communication
would be senseless) and it is also necessary to study
how this mechanism can
be integrated within classes, since processors can only
execute inside objects. Here
we are confronted with an apparent paradoxical situation:
in an approach which regards
inter-object and inter-processor direct communication
as different things, how
can the latter be implemented within classes? After all,
classes are object types, not
processor types.
To solve this apparent paradox it is necessary to find
answers to the processor
identification problem. One possible approach would be
to define a centralized processor
registration, identification and communication mechanism,
where processors
could be named, and through which they could exchange messages.
This possibility,
however, has serious drawbacks:
- messages would most likely be restricted to data, to which
an appropriate behavior could only be defined by the receiver processor
(with no assurance
that the data values are meaningful to it);
- it would be a mechanism outside the object-oriented program
entities: classes;
- a communicating processor would have to rely on a third
party entity for
choosing the correct destination processor;
- it is a centralized scheme, which does not scale well to
distributed systems,
and may raise communication bottleneck problems;
- it is a rather complex solution.
All these problems – some
of which might have some benefits in other programming
environments – are not appropriate to object-oriented
systems. In these
systems, communication involves behavior (requested by
the sender, and with the
guarantee that it is meaningful to the receiver processor);
classes should be the only
topmost program structure; and software development should
be decentralized.
On the other hand, if there was a simple
way to bind processor identification
to objects, then messages between processors could be requests
for the execution of
features on any of the receiver processor objects, which
does not have the drawbacks
of the presented centralized possibility. In fact, a simple
solution to this problem
already exists: SCOOP’s approach is (almost) perfect
for an object-oriented direct
inter-processor communication mechanism. There, a processor
is identified by the
nonseparate objects it creates and it is responsible for
handling any message (feature
call) sent to them. To handle all messages without losses,
it is necessary to attach
a message queue to processors. Therefore, a message is
handled when its turn has
arrived and the processor is not doing anything else.
In this approach,
if a procedure message is sent, then the communication will be
naturally asynchronous (to the sender). On the other hand,
a function (or an attribute)
message will be synchronous (as will be seen, delaying
the point of synchronization
until the result is needed – as SCOOP proposes – might
not be appropriate
for a meaningful exception handling mechanism).
However, using this
SCOOP approach for processor direct communication – in
languages that separates both forms of communication (inter-object
and interprocessor) – disregards the
fact that, normally, classes are not built thinking about
inter-processor direct communication. So, it is questionable
that the interfaces (acceptable
messages) to both worlds should be the same. Therefore,
it makes sense to
augment classes with an inter-processor export mechanism,
in which the names of
the communicable inter-processor features are listed.
Grabbing multiple
objects
Frequently in concurrent programming it is necessary to
ensure an exclusive access
(or better yet: a readers-writer lock access mode) to other
objects besides the current
object for the execution of a code block. A possible approach
to get this functionality
is to add a new critical region instruction such as [Han72]:
However, this option has the problem of moving object locking
requests away
from the current object stable times (which may pose extra
difficulties for ensuring
safety in deadlocks and other complex liveness problems).
A simpler approach is
the one proposed in SCOOP, in which objects are held within
the routine’s
body,
and the criteria for choosing the objects to grab is simply
the ones attached to
the routine’s concurrent formal arguments (separate
in SCOOP). Also, with this
approach – unlike the dedicated critical region instruction – it
is easy to apply the
Inheritance Invariance rule, making it immune to inheritance
anomalies.
Another interesting positive side-effect of this
choice is that – since
it concentrates
and restricts the places where locks are allowed – it
will most likely simplify the
resolution of deadlocks and other liveness problems. The
example presented in the
end of this article clearly illustrates this situation.
Concurrent exception
handling
One last integration problem will be addressed: how to
handle exceptions under a
concurrent system.
Meyer [Mey97, page 412] defines exceptions as run-time
events that may cause a
routine to fail. A failure may arise from hardware related
problems (lack of memory,
or arithmetic operations faults), or, in general, resulting
from a contract failure. In a
disciplined exception handling mechanism (as exists in
Eiffel), a routine can either
fail – reporting failure to its caller – or
retry to fulfill the contract (failing again if
unable to do that). Under a concurrent system new sources
of failures may arise.
Processors may fail, either by an unsolved exception, or,
in a distributed system,
due to a communication failure.
In a sequential language, the exception
mechanism exploits the causal relation
between the exception source (a program block) and its
handler (declared within the
scope of the exception). For example, in C++ the block
is defined by TRY statements
and exceptions handled in CATCH instructions.
In Eiffel every routine is a possible
exception block, and exceptions are handled by RESCUE clauses,
or propagated to
the caller. This causality property is essential for a
correct failure localization and
its appropriate handling.
A similar scheme can be applied in a concurrent
environment if this casual proximity
relation persists. That is the case of a synchronous processor
interaction (either
with shared memory processor communication, or synchronous
message passing), if
no lazy evaluation (wait by necessity [Car89]) scheme is
allowed (unlike SCOOP
[Mey97, page 987]). With wait by necessity schemes, the
required proximity relation
between the caller and the callee may not hold, disallowing
a correct exception
handling.
When the callee object may involve more than one processor,
two new problems
arise: how can that object be used in a failure recovery
(retry) attempt, and what
will happen if, meanwhile, another processor attempts to
use it?
One possibility for solving both problems would
be to maintain the lock (exclusive
access) to the failed routine’s object until either
there was a successful recovery
(from where everything would go on as if nothing had happen),
or a processor failure
occurred (which in a mechanism like Eiffel’s, occurs
when the exception is propagated
until the processor’s creation routine is reached,
and also fails). On processor
failure, there could be an exception raised to any processor
attempting to use that
object. However, this is not a completely satisfactory
solution, because the failure
might have been the responsibility of the caller (not the
callee), due, for example, to
a precondition failure. Such event should not affect either
the called routine’s object,
or other processors that might use it. A much better solution
is to use this scheme
only if the called routine’s object is not in a stable
state (in which case it is not
usable anyway). Otherwise, the exception will only affect
the caller, and a recovery
attempt would be simply a new call request requiring appropriate
synchronization.
In a shared memory communication model this scheme is particularly
simple and
efficient since it does not require the collaboration of
another processor. We will call
this solution a disciplined synchronous exception handling.
Under asynchronous
communication there is a different situation. In this case–
by definition – no causal relation can be established between
the failure and the
message sender, which inhibits the possibility of using
the proposed synchronous
mechanism. Several approaches can be devised to handle
this situation. If, in this
form of communication, it is assumed that an eventual communication
failure is not
the responsibility of the sender, then a possible approach
is simply not providing an
asynchronous exception handling mechanism. However, this
simpler choice (rule 1)
is not complete (rule 2) because it would result on a higher
complexity in programs
requiring the confirmation of a successful communication.
Another possibility is to
use the asynchronous communication mechanism in the reverse
direction generating–
on communication failure – a special error notification message
(that special feature
would have to be predefined, and also redefinable, in any
class). In that case
the sender (caller) could detect and handle asynchronous
communication failures.
However, in languages with both forms of processor communication
(as proposed
in this article), this approach interferes with the shared
memory communication
mechanism (rule 8), because it would require that both
communicating processors
were somehow dedicated to asynchronous communication.
Considering all
this problems, the best solution is, most likely, to provide special
inter-processor direct communication functions (synchronous),
which – if
the caller
desires – can be used to query the message communication
status (processed, failed,
etc.). Those special functions would have to be provided
by the language library
and be available in any class.
5 MP-EIFFEL APPROACH TO CONCURRENCY
MP-Eiffel is a concurrent object-oriented
programming language based on the
concepts and solutions presented in the previous sections.
It is characterized by the
following properties:
- exclusion safety (aiming, in the future, to become safe
in other synchronization aspects);
- heterogeneous processor mapping;
- readers-writer concurrent access semantics to objects;
- shared-memory synchronous processor communication;
- message passing synchronous and asynchronous processor
communication;
- absence of inheritance anomalies (inheritance safety);
- disciplined concurrent exception handling;
- external concurrency control language, to specify processor
mapping, scheduling
policy, and other timing constraints6.
The
decision to use Eiffel as the base language for implementing concurrency
mechanisms was based on Eiffel’s simplicity, safety,
coherent integration of its
language mechanisms, its static type system
and the support for Design by Contract.
It was also decided that MP-Eiffel should
(as much as possible) contain Eiffel,
to allow the reuse of its classes.
Shared and remote objects
In MP-Eiffel the normal object communication
scheme follows the processor shared
memory model, so objects might be executed by several processors.
To ensure a safe
usage of objects the Eiffel’s type system was augmented
with two new concurrent
type modifiers: SHARED and REMOTE.
Object entities, depending on its concurrent
type modifier, can hold references to objects with three
possible concurrent scopes:
normal, shared, or remote.
If an entity is neither shared or remote,
then it is named normal. Normal entities
can only contain expanded objects, or references to normal
objects. Normal objects
are created by applying the creation instruction to normal
entities, and are said to
belong to the creating processor.
A shared entity can only contain shared
objects. An object is shared, if it was
created by the creation instruction on a shared entity,
or if it is a normal valued
feature (attribute or function) reference of a shared object.
Shared objects can be
freely used by several processors. If a routine of a shared
object has side-effects
to the object’s state (“impure”), then its use requires
mutual exclusion (“writer”
access mode), otherwise a “readers” access
mode applies.
Remote entities can contain references to
normal objects belonging to other
processors. Those objects are said to be remote to the
current processor. Only
side-effect-free (“pure”) valued features can be called
on remote objects (the use of
commands is forbidden). The use of remote objects follows
a “readers” access
mode.
The concurrency access of a type – normal, shared,
or remote – will
be called its
concurrent scope.
“Traitors”
To ensure the safety in the MP-Eiffel’s
type system, it is necessary to guarantee the
absence of “traitors”: objects attached to
entities with different concurrent scopes.
Aiming for that
goal, two type rules are imposed:
Concurrent scope propagation rule:
the type of normal reference valued features
and routine formal arguments maintains the concurrent scope
of current
object;
Normal objects passing rule: routines of non-normal
objects can only receive
references to normal objects if, and only if, the corresponding
routine formal
argument is declared as remote.
Concurrent preconditions
Preconditions in MP-Eiffel behave as
presented in the previous section. Its normal
concurrent scope part is checked first (unless the causality
of the logical expression,
makes that impossible by the use of the logical operators
OR ELSE or AND
THEN);
then, its non-normal part (if any, and if it involves the
use of objects) is used as a
conditional synchronization test. However, no synchronization
is required for testing
the “Voidness” of non-normal references.
This behavior requires
that the non-normal part of preconditions cannot be disable
by the compiling system (the normal part behaves as in
Eiffel).
Triggering: a direct inter-processor communication
mechanism
Based on the reasons presented in the previous section,
MP-Eiffel also possesses
a direct inter-processor communication mechanism. This
mechanism is called “trigger”.
A processor is
able to receive trigger messages, if it owns objects with
the desirable
messages listed in their trigger accept clauses. The trigger
accept clause is
attached to classes, and has a similar structure as creation
clauses, using instead a
new keyword: TRIGGER.
For example a deferred
class with the ability to receive external time events on
behalf of its creation processor, could be defined as follows:
Triggers are inherited by descendant classes (renaming
works smoothly with this
mechanism since both use feature names).
Trigger messages can be send
by any processor, and its structure is almost identical
to a normal feature call with the difference that the call
is preceded by the
keyword TRIGGER (the same keyword is used
in the trigger accept clause and in
the trigger send instruction, because the word has both
meanings). For example to
trigger a tic in a processor owning a TIMER RECEIVER object:
If the trigger message is a procedure (as happens
in the above example), then the
communication will be completely asynchronous, otherwise
it will be synchronous
(the message sender processor will wait in the point of
the trigger, until the result
arises).
MP-Eiffel ensures that no trigger message
will ever be lost. To implement this
behavior, a receiving queue is attached to any processor
that may receive trigger
messages. Also, by default, all messages are ordered in “time” (using
a scheme such
as [Lam78]) so the normal (default) behavior of the queue
is to serve oldest messages
first.
Locking the access to multiple objects
To lock (with readers-writer
semantics) multiple objects MP-Eiffel uses
a similar
approach as SCOOP: all non-normal actual arguments are
locked within the
routine’s body execution.
Processors lifecycle
Processors are created by applying the creation
instruction to remote entities. They
may have an agenda to fulfill (their creation feature),
and may also have to process
triggers. Their lifecycle goes from creation through a
succession of “active” and“
idle” states until their termination when they cease to be necessary.
The “idle” states
only exist if the processor owns objects with trigger accept
clauses. A processor without trigger accept clauses will
terminate as soon as its
creation procedure ends.
The program will end when all non-terminated
processors have empty trigger
queues. Exception handling
MP-Eiffel implements the disciplined
synchronous exception handling described in
the section 4 for both forms of synchronous communication:
inter-object communication
involving several processors and the triggering of valued
features.
For the MP-Eiffel’s
asynchronous form of communication – the
triggering of
procedures – the scheme proposed in the section 4
is implemented. The status of the
asynchronous communication attempt, is verifiable by special
direct inter-processor
communication functions (synchronous) provided by the MP-Eiffel’s
library.
Final remarks
This language adds three new keywords to Eiffel: SHARED,
REMOTE, and TRIGGER;
and the class structure is augmented with a trigger accept
clause (trigger export
mechanism).
All mechanisms were designed taking in consideration all
of the language design
rules presented in the previous sections (9 rules). In
particular they are quite simple
to understand and use, complete, and orthogonal to each
other (the example
presented below is a good example of these characteristics).
Nevertheless,
the precise definition of the external concurrency control language,
and the compiling and run-time supporting system necessary
to ensure the nonexistence
of deadlocks and other liveness situations, is yet to be
carefully thought and
implemented.
Example: The Dining Philosophers problem
No article on concurrent
programming languages is “complete” without
presenting
the classic dining philosophers problem proposed by Dijkstra
[Dij72, Dij77]. In
this problem, several philosophers (five) do their living
either thinking or eating
spaghetti. However, in order for a philosopher to be able
to eat spaghetti he needs
two forks (the ones in his left and right sides), but the
number of forks is restricted
to exactly the same number of philosophers (so it is necessary
to share forks, and is
also necessary to avoid deadlock or starvation situations).
One possible solution in MP-Eiffel is presented below.
6 CONCLUSION
In this article a new concurrent object-oriented programming
language – MP-Eiffel– was
introduced, taking special care to present the reasoning
behind the choices
made throughout all its mechanisms and their semantics.
A prototype
compiler is being developed which will allow its practical validation
and experimentation. In the future, the concurrency control
language will be
implemented, taking into consideration the absence of
deadlocks and other liveness
synchronization problems.
Footnotes
1 The term “shared memory” is
system usable by all processors.
2 Eiffel goes beyond this limited
distinction allowing a much more tunable export control.
3 Hoare uses the term “security” for
this purpose.
4 Simple Concurrent Object-Oriented
Programming.
5 A curious situation since
the importance of Simula’s class concept was recognized by
Hoare
[Hoa74] and Hansen [Han93] when proposing monitors.
6 Not presented in this article.
REFERENCES
[Agh86] Gul A. Agha. Actors: A Model of Concurrent Computation
in Distributed
Systems. MIT Press, Cambridge, Massachusetts, 1986.
[AK99] Gul A.
Agha and Wooyoung Kim. "Actors: A unifying model for parallel
and distributed computing". Journal of Systems Architecture,
45(15),
September 1999.
[Ame87] Pierre America. "Pool-t: A parallel object-oriented
language". In Akinori
Yonezawa and M. Tokoro, editors, Object-Oriented Concurrent
Programming,
pages 199–220. MIT Press, 1987.
[But97] David R. Butenhof. Programming
with POSIX Threads. Addison-Wesley,
1997.
[Car88] L. Cardelli. "Structural subtyping and the notion
of power type". In Proceedings
of the 15th ACM SIGPLAN-SIGACT symposium on Principles
of programming languages, pages 70–79. ACM Press, 1988.
[Car89]
Denis Caromel. Service, "Asynchrony, and Wait-by-Necessity". Journal
of
Object-Oriented Programming, 2(4):12–18, 1989.
[Car93] Denis
Caromel. "Toward a method of object-oriented concurrent programming".
Communications of the ACM, 36(9):90–102, 1993.
[CES71] E. G.
Coffman, M. Elphick, and A. Shoshani. "System deadlocks". ACM
Computing Surveys (CSUR), 3(2):67–78, 1971.
[CHC90] William
R. Cook, Walter Hill, and Peter S. Canning. "Inheritance is not
subtyping". In Proceedings of the 17th ACM SIGPLAN-SIGACT
symposium
on Principles of programming languages, pages 125–135.
ACM Press, 1990.
[CHP71] P. J. Courtois, F. Heymans, and D. L. Parnas. "Concurrent
control with“ readers” and “writers”". Communications
of the ACM, 14(10):667–668,
1971.
[Coo89] William R. Cook. "A proposal for making Eiffel type-safe".
The Computer
Journal, 32(4):305–311, 1989. Originally in
Proc. European Conf.
on Object-Oriented Programming (ECOOP).
[CW85] Luca Cardelli and Peter
Wegner. "On understanding types, data abstraction,
and polymorphism". ACM Computing Surveys (CSUR), 17(4):471–523,
1985.
[Dij68] Edsger W. Dijkstra. Cooperating Sequential Processes.
Programming Languages.
Academic Press, New York, 1968.
[Dij72] Edsger W. Dijkstra. "Hierarchical
ordering of sequential processes". In Operating
Systems Techniques, pages 72–93. Academic Press,
1972. EWD310.
[Dij77] Edsger W. Dijkstra. Two starvation-free
solutions of a general exclusion
problem. circulated privately known as EWD625, 1977.
[Flo67] R. W.
Floyd. "Assigning meanings to programs". In J. T. Schwartz, editor,
Mathematical Aspects of Computer Science, Proceedings of Symposia in
Applied Mathematics, pages 19–32, Providence,
1967. American Mathematical
Society.
[Hab69] A. N. Habermann. "Prevention of system deadlocks".
Communications of
the ACM, 12(7):373–377, 1969.
[Han72] Per Brinch Hansen. "Structured
multiprogramming". Communications of
the ACM, 15(7):574–578, 1972.
[Han93] Per Brinch Hansen. "Monitors
and concurrent pascal: a personal history".
In The second ACM SIGPLAN conference on History of programming
languages, pages 1–35. ACM Press, 1993.
[Han99] Per Brinch Hansen.
"Java’s insecure parallelism". ACM
SIGPLAN Notices,
34(4):38–45, 1999.
[Hoa73] C. A. R. Hoare. "Hints on programming
language design". Technical Report
STAN-CS-73-403, Stanford Artificial Intelligence Laboratory,
Computer
Science Department, Stanford University, 1973.
[Hoa74] C. A. R. Hoare.
"Monitors: an operating system structuring concept". Communications
of the ACM, 17(10):549–557, 1974.
[KL89] Dennis G. Kafura and
Keung Hae Lee. "Inheritance in actor based concurrent
object-oriented languages". In Proceedings of the Third
European
Conference on Object-Oriented Programming, July 1989.
[Lam78] Leslie
Lamport. "Time, clocks, and the ordering of events in a distributed
system". Communications of the ACM, 21(7):558–565,
1978.
[Lam83]
Leslie Lamport. "Specifying concurrent program modules". ACM
Transactions on Programming Languages and Systems (TOPLAS), 5(2):190–222,
1983.
[LN78] Hugh C. Lauer and Roger M. Needham. "On the duality
of operating
system structures". In Proceedings of the Second International
Symposium
on Operating Systems, October 1978. reprinted in Operating
Systems
Review, Vol. 13, No. 2, April 1979, pp. 3-19.
[LZ74] Barbara Liskov
and Stephen Zilles. "Programming with abstract data types".
In Proceedings of the ACM SIGPLAN symposium on Very high
level languages,
pages 50–59, 1974.
[Mey92] Bertrand Meyer. Eiffel: The Language.
Prentice Hall, Englewood Cliffs,
N.J., March 1992. 2nd printing.
[Mey97] Bertrand Meyer. Object-Oriented
Software Construction. Prentice Hall,
2nd edition, 1997.
[MY93] Satoshi Matsuoka and Akinori Yonezawa. "Analysis
of inheritance anomaly
in object-oriented concurrent programming languages". In
G. Agha,
P. Wegner, and A. Yonezawa, editors, Research Directions
in Concurrent
Object-Oriented Programming, pages 107–150. MIT Press,
1993.
[Par72a] D. L. Parnas. "On the criteria to be used
in decomposing systems into
modules". Communications of the ACM, 15(12):1053–1058,
1972.
[Par72b] D. L. Parnas. "A technique for software module
specification with examples".
Communications of the ACM, 15(5):330–336, 1972.
[RA95] Shangping
Ren and Gul A. Agha. "Rtsynchronizer: language support for
real-time specifications in distributed systems". In Proceedings
of the ACM
SIGPLAN 1995 workshop on Languages, compilers, & tools
for real-time
systems, pages 50–59. ACM Press, 1995.
[RF77] Manfred Ruschitzka
and R. S. Fabry. "A unifying approach to scheduling".
Communications of the ACM, 20(7):469–477, 1977.
About the author
|
 |
Miguel Oliveira e Silva is a PhD student
and teaching assistant
in the Electronics and Telecommunications Department of the University
of Aveiro, Portugal. He is also part of the IEETA’s research
group in the same University. He can be reached at mos@det.ua.pt.
See also http://www.ieeta.pt/˜mos. |
Cite this article as follows: Miguel Oliveira e Silva: "Concurrent
Object-Oriented Programming:
The MP-Eiffel Approach", in Journal of Object Technology,
vol. 3, no. 4, April 04, Special issue: TOOLS USA 2003, pp. 97-124.
http://www.jot.fm/issues/issues_2004_04/article6
|
