Comparing Java, C# and Ada Monitors queuing policies : a case study and its Ada refinement Claude Kaiser, Jean-François Pradat-Peyre, Sami Évangelista, Pierre Rousseau CEDRIC - CNAM Paris 292, rue St Martin, 75003 Paris {kaiser, peyre, evangeli, rousseau}[at]cnam[dot]fr http://quasar.cnam.fr Abstract. Learning concurrency paradigms is necessary but it is not sufficient since the choice of run-time semantics may introduce subtle programming errors. It is the aim of this paper to exemplify the importance of process queuing and awaking policies resulting from possible choices of the monitor concept implementation. The first part of the paper compares the behaviour of concurrent processes sharing a unique waiting queue for condition synchronization when implemented in Java or in Ada. A particular solution of the dining philosophers paradigm will be used to show how the difference in the monitor semantics may lead or not to deadlock. This comparison provides insight for deriving a correct Java implementation. The second part of the paper shows how the implementation can be refined when using Ada entry families and requeue with requeue once restriction. The result is elegant, safe and fair, and deterministic. This paper ends with quantitative comparisons of concurrency complexity and of concurrency effectiveness. We conclude that Java and C# multithreading need defensive concurrent programming while Ada allows more latitude for developing correct concurrent programs. 1. Introduction 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 Ada Letters August 2006 Volume XXVI, Number 2 [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. The “requeue” statement enables a request to be processed in two or more steps, each associated with an entry call. The effect is to return the current caller back to an entry queue. The caller is neither aware of the number of steps nor of the requeuing of its call. This sequence of steps corresponds to a sequential automaton. According to the eggshell model, any entry call of such a sequence which guard has become true has precedence over a new call contending for the protected object. Ada Letters August 2006 Volume XXVI, Number 2 If we summarize the differences in the awaking policies: Java and C# make no choice and leave all ready processes able to compete for the lock, while Ada gives precedence to the processes waiting in entry queues. The first part of this paper compares the behaviour of concurrent processes sharing a unique waiting queue for condition synchronization when implemented in Java or in Ada. A particular solution of the dining philosophers paradigm will be used to show how the difference in the monitor semantics, i.e. in the awaking policies, may lead or not to deadlock. This comparison provides insight for deriving a correct Java implementation. The second part of the paper shows how the implementation can be refined when using Ada entry families and requeue with requeue once restriction. The result is elegant, safe and fair, and deterministic. This paper ends with quantitative comparisons of concurrency complexity and of concurrency effectiveness. We conclude that Java and C# multithreading need defensive concurrent programming while Ada allows more freedom for developing correct concurrent programs. 2. A new solution for the dining philosophers paradigm The dining philosophers, originally posed by Dijkstra [Dijkstra 7I], is a well-known paradigm for concurrent resource allocation. Five philosophers spend their life alternately thinking and eating. To dine, each philosopher sits around a circular table at a fixed place. In front of each philosopher is a plate of food, and between each pair of philosophers is a chopstick. In order to eat, a philosopher needs two chopsticks, and they agree that each will use only the chopsticks immediately to the left and to the right of his place. The problem is to write a program simulating the philosopher’s behaviours and to devise a protocol that avoids two unfortunate conclusions. In the first one, all philosophers are hungry but none is able to acquire both chopsticks since each holds one chopstick and refuses to give it up. This is deadlock, a safety concern. In the second one, a hungry philosopher will always lack one of the two chopsticks which are alternately used by its neighbours. This is starvation, a liveness consideration. This paradigm has two well-known approaches for obtaining a solution. In the first one, the chopsticks are allocated one by one, and a reliable solution is obtained by adding one of the usual constraints for deadlock prevention: the chopsticks are allocated in fixed (e.g., increasing) order; a chopstick allocation is denied as soon as the requested allocation would lead to an unsafe state (seated dinner, with only 4 chairs). Ada implementation of this approach can be found in [Burns 1995, Barkaoui 1997]. In the second one, the chopsticks are allocated globally only, which is a safe solution; when a fair solution is necessary, it is obtained by adding reservation constraints, care being taken that these constraints do not reintroduce deadlock. Ada implementation are given in [Brosgol 1996, Kaiser 1997] Let us consider now another approach, which does not seem to have been much experimented except in [Kaiser 1997]. The chopsticks are allocated as many as available and the allocation is completed as soon as the missing chopsticks are released. Let us observe the behaviour of this solution when implemented in Java and in Ada and from these experiments, let us determine the conditions of its correctness. Ada Letters August 2006 Volume XXVI, Number 2 3. Comparing Java and Ada monitor semantics with this new solution This section presents several implementations which, influenced by the Java style, use all a unique waiting queue, implicitly and compulsory in Java, explicitly and restrictively in Ada: • A Java class with synchronized methods which are dependant of the Java monitor semantics, • A transcription of this Java class into an Ada protected object associated with embedding procedures used to skirt the Ada eggshell semantics, in order to force it to behave as a Java monitor, • An Ada regular implementation of a protected object using fully the Ada eggshell semantics. 3.1. Java implementation The Java implementation style is influenced by the choice of a monitor semantics with a unique implicit waiting queue. It leads to the following Chop class with get_LR and release methods. public final class Chop { private int N ; private boolean available [ ] ; Chop (int N) { this.N = N ; this.available = new boolean[N] ; for (int i =0 ; i < N ; i++) { available[i] = true ; // non allocated stick } } public synchronized void get_LR (int me) { int score = 0 ; // pseudo program counter used for transcripting the Java code in Ada while ( !available [me]) { try { wait() ; } catch (InterruptedException e) {} } available [me] = false ; score = 1; // left stick allocated // don’t release mutual exclusion lock and immediately requests second stick while ( !available [(me + 1)% N]) { try { wait() ; } catch (InterruptedException e) {} } available [(me + 1)% N] = false ; score = 2; // both sticks allocated } public synchronized void release (int me) { available [me] = true ; available [(me + 1)% N] = true ; notifyAll() ; } } Ada Letters August 2006 Volume XXVI, Number 2 3.2. Ada transcription of the Java monitor policy The transcription has to cope with two main differences between Java and Ada: the localisation of the blocking statements into the code and the awaking policy. 1. In Java, wait() is a method of the Object Class and one or several wait() calls may appear in the code; thus a signalled thread exiting from the wait() method returns inside the code at the instruction immediately following the wait() call. In Ada, a task calling an entry waits if the barrier of this entry is false and there is no waiting possibility inside the entry code. Thus a signalled task must always start at the beginning of the entry code. In the transcription into Ada, the Java get_LR() method code which contains two calls to wait() is sliced in three sequences of code delimited by these calls and referenced using a pseudo program counter, named score, and the Ada entry, Get_LR(), uses a case statement for selecting the code alternative to execute when the calling task is signalled. 2. This Java implementation style is simulated by an Ada program mimicking the Java monitor behaviour. The Java method is represented by the procedure Get_LR() calling the Sticks.Get_LR() entry as long as the allocation is not completed. Sticks.Get_LR() entry barrier is always True. An entry Sticks.Wait() provides the unique waiting queue for condition synchronization. Once notified, all tasks queued at Sticks.Wait() leave the protected object, none are requeued, and the Get_LR() procedure calls again Sticks.Get_LR(), competing anew for the monitor lock. This is repeated until the calling task gets all its sticks allocated. generic Type Id is mod < >; -- instanciated as mod N package Chop is procedure Get_LR(C : Id); procedure Release(C : Id); end Chop; package body Chop is type SticState is array(Id) of Boolean; type Cardinal is new Integer range 0..2; protected Sticks is entry Get_LR(C : Id; Score : in out Cardinal); -- Score is the number of already allocated sticks procedure Release(C : in Id); private entry Wait(C : Id; Score : in out Cardinal); Available: SticState := (others => True); NotifyAll : Boolean := False; -- Java signal simulation end Sticks; Ada Letters August 2006 Volume XXVI, Number 2 protected body Sticks is entry Get_LR(C : Id; Score : in out Cardinal) when True is begin case Score is when 0 => if Available(C) then Available(C) := False; Score:= 1; -- Left stick allocated if Available(C + 1) then Available(C + 1) := False; Score := 2; -- Right stick also allocated on the spot end if; end if; when 1 => if Available(C + 1) then Available(C + 1) := False; Score := 2; -- Right stick now also allocated; end if; when 2 => null; end case; if Score /= 2 then NotifyAll := False; requeue Wait; -- Java wait simulation end if; end Get_LR; entry Wait(C : Id; Score : in out Cardinal) when NotifyAll is begin -- when NotifyAll is True, the eggshell model gives precedence to all queued tasks null; -- all queued tasks quit the monitor end Wait; procedure Release(C : Id) is begin Available(C) := True; Available(C + 1) := True; NotifyAll := (Wait'Count > 0); -- Java NotyfyAll simulation end Release; end Sticks; procedure Get_LR(C : Id) is Score : Cardinal := 0; begin -- the following participate simulating the Java signalling semantics while Score /= 2 loop -- possibly overtaken by another philosopher while in the system ready queue Sticks.Get_LR(C, Score); end loop; end Get_LR; procedure Release(C : Id) is begin Sticks.Release(C); end Release; end Chop; These two preceding programs (the Java one as well as the Ada one transcribing it) usually run correctly and this may give false confidence. However these programs are not safe. They occasionally fail and deadlock, but this is a situation which is rare, difficult to reproduce and therefore to explain and debug. Ada Letters August 2006 Volume XXVI, Number 2 3.3. Ada regular implementation In order to get insight, the same program is implemented letting the Ada monitor behave normally, i.e. respecting the eggshell semantic. Once notified, a waiting task does not leave the protected object and is requeued to Get_LR(). It has precedence over new requestors. If several tasks are queued at the wait() entry, all of them must be requeued prior letting one of them execute the Get_LR() entry call. package body Chop is type SticState is array(Id) of Boolean; type Cardinal is new Integer range 0..2; type SticScore is array(Id) of Cardinal; protected Sticks is entry Get_LR(C : Id); procedure Release(C : in Id); private entry Wait(C : Id); Available : SticState := (others => True); -- Stick availability Score : SticScore := (others => 0); -- allocation state StillToNotify : Integer := 0; NotifyAll : Boolean := False; -- Java signal simulation end Sticks; protected body Sticks is entry Get_LR(C : Id) when not NotifyAll is -- after each execution of Release -- the Wait entry queue must be fully emptied before serving Get_LR anew begin case Score(C) is when 0 => if Available(C) then Available(C) := False; Score(C):= 1; -- Left stick allocated if Available(C + 1) then Available(C + 1) := False; Score(C):= 2; -- Right stick also allocated on the spot end if; end if; when 1 => if Available(C + 1) then Available(C + 1) := False; Score(C) := 2; -- Right stick now allocated; end if; when 2 => null; end case; if Score(C) /= 2 then requeue Wait; -- Java wait simulation end if; end Get_LR; entry Wait(C : Id) when NotifyAll is begin StillToNotify := StillToNotify - 1; NotifyAll:= StillToNotify > 0; -- when False, opens the Get_LR barrier requeue Get_LR; -- all signalled tasks remain inside the monitor end Wait; Ada Letters August 2006 Volume XXVI, Number 2 procedure Release(C : Id) is begin Available(C) := True; Available(C + 1) := True; Score(C) := 0; -- awakes all blocked tasks as with Java's NotifyAll StillToNotify := Wait’Count; NotifyAll := StillToNotify > 0; end Release; end Sticks; procedure Get_LR(C : Id) is begin Sticks.Get_LR(C); end Get_LR; procedure Release(C : Id) is begin Sticks.Release(C); end Release; end Chop; This implementation is reliable, fair and never deadlocks when running. Quasar, our tool for concurrent Ada analysis [Evangelista 2003], has validated its correctness and has given also a sequence of actions that leads the Java program to a deadlock. Let us consider the following running sequence. Philosophers request the sticks in the following sequential order: 4, 3, 2, 1, 0. Philosopher 4 takes two sticks and eats while Philosophers 3, 2 and 1, one after the other, take their left stick and wait for their right stick that they find already allocated. Philosopher 0 finds that its left stick has been allocated, so it waits for it. As soon as Philosopher 4 has released its two sticks, it becomes hungry anew and calls Get_LR immediately. Suppose that Philosopher 0, which has been signalled of its stick availability, has taken its left stick in the meanwhile and now waits for its right one. The correctness depends on the choice of the next process that will access the monitor. If it is Philosopher 3, it will take its right stick and eat. If it is Philosopher 4, it will take its left stick and find its right stick already allocated. It will be blocked, as already are the four other Philosophers, and this is a deadlock. The Java policy allows Philosopher 4 to compete for acquiring the access lock of the object chop, and if it succeeds occasionally to take precedence over Philosopher 3, this will cause a deadlock. Ada gives always precedence to the existing waiting calls, that is Philosopher 3 has always precedence over Philosopher 4 and there is never a deadlock. This shows that the correctness relies sometimes on the concurrency semantic of the run-time system. It shows also why deadlock is not systematic in the Java implementation, and why this non-deterministic behaviour makes its correctness difficult to detect by tests. Deadlock is prevented if a philosopher already owning its left stick books immediately its right stick, forbidding its right neighbour to get precedence for acquiring it anew as a left stick. This leads to Java and C# defensive implementations that are reliable but not fair (see Annex 1). Ada Letters August 2006 Volume XXVI, Number 2 4. An Ada deterministic deadlock free and fair implementation All the preceding implementations use a unique waiting queue and this implies a semi-active awaking solution. Semi-active means that any waiting process must be signalled even if its blocking condition has not changed and if it is doomed to wait anew. Programming several condition synchronization queues allows refining the implementation of our new solution of the dining philosophers paradigm in a more attractive solution. In Ada, the use of entry families and requeue statement provides then an efficient and correct (i.e., no deadlock, no starvation) implementation with at most one task waiting at an entry, with requeuing just once (no semi- active wait while scanning entry queues) and with a simple Boolean variable as entry barrier. Moreover this solution is very elegant and deserves being presented as a tribute to Don Knuth who wrote in the preface of its Art of Computer Programming “The process of preparing programs can be an aesthetic experience much like composing poetry or music”[Knuth 1969]. package body Chop is type SticState is array(Id) of Boolean; protected Sticks is entry Get_LR(Id); -- entry family procedure Release(C : in Id); private entry Get_R(Id); -- entry family Available : SticState := (others => True); -- Stick availability end Sticks; protected body Sticks is entry Get_LR(for C in Id) when Available (C) is begin Available (C) := False; requeue Get_R(C + 1) ; end Get_LR; -- Left stick is allocated entry Get_R(for C in Id) when Available (C) is begin Available (C) := False; end Get_R; -- stick C is allocated as a right stick procedure Release(C : Id) is begin Available(C) := True; Available(C + 1) := True; end Release; end Sticks; procedure Get_LR(C : Id) is begin Sticks.Get_LR(C); end Get_LR; procedure Release(C : Id) is begin Sticks.Release(C); end Release; end Chop; This style of programming is inherited from the private semaphore [Dijkstra 1968] and the original monitor [Hoare 1974] proposals where a waiting process is awaken only when it has been granted all the resources it requested. The waiting queues contain at most one task and thus the queuing policy has no influence. Since there is always one and only one requeue operation executed, there is no task recycling among entry queues. All these features contribute reducing non-determinacy (see section 6.1 and Annex 2). This leads us to suggest an extension of the Ravenscar profile [Burns 2004], allowing protected objects with entry families and requeue statements conjugated with the restriction of at most one task per entry and one requeue execution per task. Ada Letters August 2006 Volume XXVI, Number 2 This implementation is safe and fair. If necessary, priorities may be given to tasks. Entries Get_R may have priority over Get_LR. This may also be stated in the program, as below. entry Get_LR(for C in Id) when Available (C) and Get_R(C)’Count = 0 is begin Available (C) := False; -- Left stick allocated requeue Get_R(C + 1) ; end Get_LR; Another interest of an implementation that has got rid of the queuing policy influence is that it is easy to trace the allocation process and to undo it when a client is aborted. Suppose that the Ada “requeue with abort” clause is added. When a task waiting at Get_LR() is aborted, it has no stick reserved yet for it and the abortion has no effect on the resource availability, while aborting a task waiting at Get_R() causes a stick leakage and ruins the problem stability. A policy for propagating abortion signals to abortion handlers, much alike the one used for exceptions, would be welcome in some future Ada language revision. It would allow releasing the already allocated stick, as programmed below. entry Get_LR(for C in Id) when Available (C) is begin Available (C) := False; -- Left stick allocated requeue Get_R(C + 1) with abort; end Get_LR; entry Get_R(for C in Id) when Available (C) is begin Available (C) := False; -- stick allocated as a right stick when aborted => Available (C – 1) := True ; -- abortion handler, not possible in Ada to-day end Get_R; 5. Chops Global allocation Chops Global allocation allows the largest number of jointly eating philosophers and therefore is a useful benchmark when comparing implementations. In this solution, the chopsticks are allocated globally. The use of entry families provides again a simple Ada implementation. The corresponding part of the protected object body is then: entry Get_LR(for C in Id) when Available (C) and Available(C + 1) is begin Available (C) := False; -- Left stick allocated Available (C + 1) := False; -- Right stick allocated end Get_LR; -- no requeue needed However, this solution allows starvation when a postponed philosopher has always one of its neighbours eating. In Java, starvation may additionally occur when a releasing philosopher calls immediately Get_LR and gets anew the monitor lock before a signalled philosopher. 6. Instrumentation 6.1. Concurrency complexity Our verification tool Quasar [Evangelista 2003] translates automatically a concurrent Ada program into a formal model. The size of the generated model can be used as a concurrency Ada Letters August 2006 Volume XXVI, Number 2
Description: