Thread synchronization in Java
using synchronized methods or statements
is simple and straightforward
as long as mutual exclusion of threads
is sufficient for an application.
Things become less straightforward
when wait and notify (or notifyAll)
have to be employed to realize more flexible synchronization schemes.
In that context,
things become even more complicated by the fact
that monitors and condition variables
– which have been related, but separate entities
in the original monitor concept –
have been merged into a single unit,
namely an object.
In practice that means
that every Java object used as a monitor
possesses only a single, implicit condition variable
which is the object itself.
Therefore,
monitor-based solutions of synchronization problems
using two or more different condition variables
– for example, a rather straightforward solution
of the well-known bounded buffer problem
employing two condition variables notempty and notfull –
are difficult to convert to functionally equivalent
and comparably comprehensive Java programs.
Guaranteeing (and proving) the correctness of such code
is further complicated by the fact
that notify (or notifyAll)
does neither suspend the executing thread
(either immediately or at the time it leaves the monitor,
i. e., the synchronized method or statement it is currently executing)
nor immediately resumes the notified thread.
(In other words,
notify does not put the notified thread in the running,
but only in the runnable state.)
That means that the notifying thread
(or even any other currently running thread)
might execute the monitor code several times again
before the notified thread is actually able to continue.
This behaviour,
which is in contrast to the signal semantics
of the original monitor concept,
usually improves performance as it demands fewer thread switches,
but on the other hand increases the typically already high enough possibility
of undesired race conditions even further.
Path expressions have been proposed a long time ago to describe synchronization conditions on a more abstract level in order to avoid the problems described above. More recently, interaction expressions have been developed as a significant extension and generalization of path expressions, providing operators for sequential and parallel composition, sequential and parallel iteration, disjunction and conjunction, as well as parameterized expressions and quantifiers.
To synchronize the threads of a Java program with interaction expressions,
the methods that shall be synchronized
must be marked with a new keyword sync.
Afterwards,
they can be used in interaction expressions
describing permissible execution sequences of these methods.
Whenever a sync method is called,
it is checked whether its execution is currently permitted
by all interaction expressions containing this method.
If this is true,
the method is executed,
while otherwise the corresponding thread is blocked
until another sync method terminates
in which case the check is repeated.
To simplify the construction of complex interaction expressions and to predefine frequently occurring expressions or expression patterns, parameterized interaction macros are provided.
Even though this concept has been developed in the context of Java, in particular because it provides threads as an integral part of the language environment, it is easily portable to other languages, e. g., C and C++, if threads and synchronization primitives such as semaphores or mutexes are provided by an appropriate library.
The well-known readers and writers problem
– any number of readers might be executed in parallel,
while a writer needs exclusive access to an object –
can be solved as follows
using interaction expressions in Java.
Methods that shall be synchronized by interaction expressions
are declared with a new keyword sync,
while interaction expressions are introduced by the new keyword expr.
The expression used below describes that
either any number of concurrent read methods
(parallel iteration operator #)
or a single write method
(disjunction operator |)
might be executed repeatedly (sequential iteration operator *).
class ReadWrite {
...... // Data fields.
// Interaction expression to synchronize read and write.
expr * ( # read() | write() );
public sync void read () {
...... // Actual read operation.
}
public sync void write () {
...... // Actual write operation.
}
}
[1] C. Heinlein: Workflow- und Prozeßsynchronisation mit Interaktionsausdrücken und -graphen. Konzeption und Realisierung eines Formalismus zur Spezifikation und Implementierung von Synchronisationsbedingungen. Dissertation, Fakultät für Informatik, Universität Ulm, 2000.
(PostScript, PDF)
Describes interaction expressions in all details,
including formal and operational semantics,
complexity results,
application to workflow synchronization,
graphical representation,
etc.
(Unfortunately in German only.)
[2] C. Heinlein:
"Workflow and Process Synchronization with Interaction Expressions and Graphs."
In: Proc. 17th Int. Conf. on Data Engineering (ICDE) (Heidelberg, Germany, April 2001). IEEE Computer Society, 2001, 243–252.
(PostScript, PDF)
A compact summary of the previous Ph. D. thesis in English.
[3] C. Heinlein:
"Advanced Thread Synchronization in Java Using Interaction Expressions."
In: M. Aksit, M. Mezini, R. Unland (eds.): Objects, Components, Architectures, Services, and Applications for a Networked World (Int. Conf. NetObjectDays, NODe 2002; Erfurt, Germany, October 2002; Revised Papers). Lecture Notes in Computer Science 2591, © Springer-Verlag, Berlin, 2003, 345–365.
Describes the integration of interaction expressions
into the Java programming language
by means of a simple precompiler
and gives various examples of their use.