Signal and Exit Vs Signal and Continue

Monitors

Semaphores are like goto's and pointers: mistake prone, work okay but lack structure and ``discipline''.

For example, a disastrous typo:

V(S); criticalSection(); V(S)

This leads to deadlock:

P(S); criticalSection(); P(S)

Nested critical sections can lead to deadlock:

P1: P(Q); P(S); ... V(S); V(Q);

P2: P(S); P(Q); ... V(Q); V(S);

A monitor is an object with some built-in mutual exclusion and thread synchronization capabilities. They are an integral part of the programming language so the compiler can generate the correct code to implement the monitor. Only one thread can be active at a time in the monitor, where ``active'' means executing a method of the monitor. Monitors also have condition variables, on which a thread can wait if conditions are not right for it to continue executing in the monitor. Some other thread can then get in the monitor and perhaps change the state of the monitor. If conditions are now right, that thread can signal a waiting thread, moving the latter to the ready queue to get back into the monitor when it becomes free.

Monitors can use either signal-and-exit or signal-and-continue signaling discipline. In the former, a signaling thread must leave the monitor immediately, at which point it is guaranteed that the signaled thread is the next one in the monitor. In the latter, the signaled thread is not guaranteed to be the next one in the monitor. In fact, barging can take place: some thread that has called a monitor method and is blocked until the monitor is free can get into the monitor before a signaled thread.

Here are monitors for the three ``classical'' problems using the signal-and-exit signaling discipline and condition variables. They are written in a Java-like but not Java pseudocode. The synchronized attribute in a method definition means that only one thread at a time can be active in any synchronized method.

Bounded Buffer Pseudocode Monitor.

Philosopher starvation is prevented by introducing a new state: very hungry. A philosopher is put into this state if it is hungry, if one of its neighbors puts down its forks, and if it cannot eat because the other fork is in use. A new rule is added: a hungry philosopher cannot eat if it has a very hungry neighbor. These changes prevent a collaboration of two philosophers trying to starve the philosopher between them. Notice that signal-and-exit requires leaving and reentering the monitor to generate more than one signal.

Starvation-Free Dining Philosophers Pseudocode Monitor.

Writer starvation is prevented by requiring readers that come along to read the database to wait if there is a waiting writer even if other readers are currently reading the database. When the current readers finish, the waiting writer writes the database and then signals into the database a waiting reader. Each entering reader signals another waiting reader into the database.

Starvation-Free Readers and Writers Pseudocode Monitor.

Java Monitors

Java uses the synchronized keyword to indicate that only one thread at a time can be executing in this or any other synchronized method of the object representing the monitor. A thread can call wait() to block and leave the monitor until a notify() or notifyAll() places the thread back in the ready queue to resume execution inside the monitor when scheduled. A thread that has been sent a signal is not guaranteed to be the next thread executing inside the monitor compared to one that is blocked on a call to one of the monitor's synchronized methods. Also, it is not guaranteed that the thread that has been waiting the longest is the one woken up with a notify(); an arbitrary thead is chosen by the JVM. Finally, when a notifyAll() is called to move all waiting threads back into the ready queue, the first thread to get back into the monitor is not necessarily the one that has been waiting the longest.

Each Java monitor has a single nameless anonymous condition variable on which a thread can wait() or signal one waiting thread with notify() or signal all waiting threads with notifyAll(). This nameless condition variable corresponds to a lock on the object that must be obtained whenever a thread calls a synchronized method in the object. Only inside a synchronized method may wait(), notify(), and notifyAll() be called.

Methods that are static can also be synchronized. There is a lock associated with the class that must be obtained when a static synchronized method is called.

Usually all the publicly accessible methods, the service or access methods, are synchronized. But a Java monitor may be designed with some methods synchronized and some not. The non-synchronized methods may form the public access and call the synchronized methods, which are private.

An experiment was performed to determine if Java monitors are signal-and-exit or signal-and-continue. They use signal-and-continue. When a thread executes a notify(), Java does not necessarily move to the ready queue the thread that has been waiting the longest. Also, Java allows barging.

Java Monitors Use Signal-and-Continue.

Here are Java monitors for the three ``classical'' problems. Two important things to be aware of because of signal-and-continue, the lack of named condition variables, and barging. Most of the time it is necessary to use a while loop instead of an if when doing a wait().

while (condition) try {wait();} catch (InterruptedException e) {}        

It is possible that some other thread barged in and got the resource or whatever, requiring a recheck of the waiting condition. Most of the time it is necessary to use notifyAll() instead of notify() in order to awaken all waiting threads and let them recheck their waiting condition. It is not possible to direct a signal to the particular thread for whom the resource is now available or whatever.

The bounded buffer monitor can only be used by a single producer thread and a single consumer thread. The ``driver'' code is the same as that for the semaphore single-producer single-consumer bounded buffer. What could go wrong if more than one thread of each type used this monitor? How would you fix the monitor?

The Bounded Buffer Monitor.

The Producer and Consumer Driver.

Notice how inefficient the dining philosophers monitor is because a broadcast signal with notifyAll() must be sent whenever any philosopher puts down its forks due to Java's lack of named condition variables.

A Starvation-Free Dining Philosophers Monitor.

The Dining Philosophers Driver.

Since there are no named condition variables, another technique must be used to prevent starvation in the database readers and writers. The arrival times of readers forced to wait because of a waiting writer is maintained. When the waiting writer enters and then exits the database, all waiting readers that arrived before the time the writer just exiting finished writing are allowed to read the database.

A Starvation-Free Readers and Writers Monitor.

The Readers and Writers Driver.

As mentioned, Java does not have semaphores. Here is how they are implemented in the Synchronization package in the lib directory.

Base Semaphore Class.

An Exception.

Binary Semaphore Monitor.

Counting Semaphore Monitor.

A binary semaphore can be implemented in other ways than the above, for example. Compare and contrast the two implementations. Which do you prefer?

A lock acts like a binary semaphore except only the locking thread can unlock the lock.

Lock Example.

It is possible to use an object somewhat like a condition variable in a Java monitor. We can pull the code for the elements and spaces semaphores of the bounded buffer semaphore version into the bounded buffer implementation. The resulting bounded buffer can be used with multiple producer and multiple consumer threads.

Multiple Producer and Consumer Bounded Buffer.

The Producers and Consumers Driver.

A notification technique can be used to avoid waking up all the philosopher threads with a notifyAll(). An array of notification objects, convey, is used, one for each philosopher. If the forks are not available when the philosopher gets hungry, it waits inside its notification object for a notify().

Dining Philosophers Notification.

The Dining Philosophers Driver.

The following implements a starvation-free synchronization algorithm for the readers and writers with a notification object for each thread to wait inside until it can access the database.

Readers and Writers Notification.

The Readers and Writers Driver.

In contrast to named condition variables, it is not possible with this notification technique to wait in the middle of a monitor service method for a signal and then continue executing inside the monitor service method at that point after receiving the signal. The signaled thread has to reenter the monitor via a service method.

A skeleton class for implementing named condition variables (exercise for the reader):

Named Condition Variable.

Here is the code for the XtangoAnimator Class.

Laboratory Exercises

1. Write a Java monitor for the baboons crossing a canyon (unisex bathroom) that is fair, that is, prevents starvation.
2. Printing W, X, Y, and Z
3. Cigarette Smokers
4. Write a Java monitor for the single sleeping barber. Then modify it for multiple sleeping barbers.
5. Baboons without Starvation
6. Multirider Bumper Cars
7. Santa, Reindeer, and Elves
8. Enhance the XtangoAnimator class so that there are commands for rotation, GIF image icons, grouping icons, lines with arrow heads, hiding, and unhiding icons.
9. Find all remaining race conditions, if any, in the XtangoAnimator class.

---

Last modified 30 December 1997.

© 1997 Stephen J. Hartley

SJH

shartley@mcs.drexel.edu

cappsprours.blogspot.com

Source: https://lya.fciencias.unam.mx/jloa/monitors.html

Share this post