High-Level Thread Synchronization

Background and Motivation

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.

Concept

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.

Example

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.
        }
    }

Publications

[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.


Christian Heinlein, 22.09.09