Concurrent programming is still challenging and difficult. “Since concurrency techniques have become indispensable for programmers who create highly available services and reactive applications, temporal dimensions of correctness introduced by concurrency, i.e., safety and liveness, are central concerns in any concurrent design and its implementation” [Lea 98]. And without expert guidance and concurrent design-pattern description, they’re expected to occasionally fail. Thus providing significant examples and paradigms for teaching good and correct style is of prime importance.

Learning concurrency paradigms is necessary but it is not sufficient. The choice of the run-time semantics must be known since it may introduce subtle design and programming errors. It is the aim of this paper to exemplify the importance of process queuing and awaking policies (whether processes are named threads or tasks) resulting from possible choices of the monitor concept implementation.

The languages Java, C# and Ada implement the monitor concept [Hoare 1974]. Several possible monitor concurrency semantics have been used in the past and a classification is presented in [Buhr1995]. Every implementation provides mutual exclusion during the execution of a distinguished sequence (synchronized method in Java, lock in C#, protected object subprograms in Ada) using a lock for every object. The semantics differ in the chosen policies for blocking, signalling and awaking processes.

The Java policy uses explicit self-blocking and signalling instructions. It provides “wait()”,“notify()” and “notifyAll()” clauses with a unique waiting queue per encapsulated object (termed “synchronized”). A self-blocking thread joins the waiting queue and releases the object mutual exclusion lock. A notifying thread wakes up one or all waiting threads (which join the ready threads queue), but it does not release the lock immediately. It keeps it until it reaches the end of the synchronized “method” (or “block”) ; this is the “signal and continue” monitor discipline.

Hence the awaken threads must still wait and contend for the lock when it becomes available. However, as the lock is released, and not directly passed to an awaken thread (the lock availability is globally visible), another thread contending for the monitor may take precedence over awaken threads. More precisely, as the awaken threads share the ready queue with other threads, one of the latter may take precedence over the formers when contending for the processor; if this elected thread calls also a synchronized method (or enters a synchronized block) of the object, it will acquire the lock before the awaken threads and then access the object before them. This may contravene the problem specification and may require the use of defensive programming.

Java 1.5 allows using multiple named condition objects. This provides more programming flexibility, however the signalling policy remains the same.

The language C# has thread synchronization classes which expressiveness is close to Java 1.5 using for example Wait(), Pulse(), Monitor.Enter(), Monitor.Quit() and which queuing and signalling semantics is similar. Thus we shall refer to Java examples only.

Ada provides protected object types which has no low level clauses for blocking and awakening tasks. Condition synchronization relies on programmed guards (a boolean expression termed “barrier”). Access is provided by calling entries, functions and procedures, but only one of these can be executed at a time in mutual exclusion. The entries have barrier conditions, which must be true before the corresponding entry body can be executed. If the barrier condition is false, then the call is queued and the mutual exclusion is released. At the end of the execution of an entry or a procedure body of the protected object, all barriers which have queued tasks are re-evaluated and one waiting call which barrier condition is now true is executed. The mutual exclusion is released only when there is no more waiting task with a true barrier condition. Thus existing waiting calls with true barrier condition take precedence over new calls. This is the “eggshell model” for monitors. Evaluation of barriers, execution of protected operation sequences, and manipulation of entry queues are all done while the lock is held.

Download pdf Comparing Java, C# and Ada Monitors queuing policies