Introduction
This is an introduction to using the Java programming language in concurrent or ultithreaded applications. The context is the process synchronization material and related concurrent programming in operating systems courses as opposed to software ngineering. Topics covered are race conditions when threads share data, critical sections, mutual xclusion, semaphores, monitors, message passing, the rendezvous, remote procedure alls, distributed or network programming, and parallel processing. Solutions to the classical problems talked about in operating systems courses (the dining philosophers, the bounded buffer producers and consumers, and the database readers and writers) are shown in Java. Also shown is how to animate algorithms using the command set of the Xtango nimation
interpreter, animator. Some of the animation examples can be viewed as applets These example programs were developed and tested using Sun Microsystem's JDK version .0.2 and 1.1 for Solaris 2.x and Windows 95/NT (1996--97). They have been updated to emove all ``deprecated'' methods and constructors. The multimachine socket examples use the readObject() and writeObject() methods of the ObjectInputStream and bjectOutPutStream classes, which are part of the RMI (remote method invocation) add-on for JDK 1.0.2 and included with JDK 1.1.
All of the code examples described and hyperlinked here may be retrieved by anonymous ftp from site ftp.mcs.drexel.edu (144.118.40.9) in directory pub/shartley and file ookJavaExamples.tar.gz. This is a GNU gzip-compressed UNIX tar archive file. A zip archive version is also available there. You may also download them directly without using anonymous ftp: gzip tar archive and zip archive. Java is designed to be a platform-independent language, so all of these examples, including the animated ones, will run without change on Sun's Solaris 2.x UNIX for Sparc and Microsoft Windows 95/NT for Intel-based PCs.
In these compressed archives, there is a directory lib that contains three subdirectories: Utilities, Synchronization, and XtangoAnimation. The path to the lib directory needs to be put into your CLASSPATH environment variable so that your Java programs can import the classes in the subdirectories of lib. For example, suppose you unpack the archive so that lib is in directory /home/you/Java. Then on a UNIX system, put the line
setenv CLASSPATH /usr/local/JDK/lib/classes.zip:/home/you/Java/lib:.into your .cshrc or .login file. (Replace /usr/local/JDK/lib/classes.zip with wherever your system administrator has installed the Java system classes.)
On a Windows 95/NT system, put the line
SET CLASSPATH=C:\JAVA\JDK\LIB\CLASSES.ZIP;D:\LIB;.in your AUTOEXEC.BAT file (assuming you put lib into D: and the JDK into C:\JAVA).
To test your CLASSPATH setting, try these commands. java Utilities.GetOpt
java XtangoAnimation.XtangoAnimator
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 awake 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
Write a Java monitor for the baboons crossing a canyon (unisex bathroom) that is fair, that is, prevents starvation.
Printing W, X, Y, and Z
Cigarette Smokers
Write a Java monitor for the single sleeping barber. Then modify it for multiple sleeping barbers.
Baboons without Starvation
Multirider Bumper Cars
Santa, Reindeer, and Elves
Enhance the XtangoAnimator class so that there are commands for rotation, GIF image icons, grouping icons, lines with arrow heads, hiding, and unhiding
icons.
Find all remaining race conditions, if any, in the XtangoAnimator class
Message Passing
Sometimes the phrase ``send a message to an object'' is used to describe a thread in one object calling a method in another object. Here, that phrase is used to
describe a thread in one object sending a message to a thread in another object, where the message is itself an object.
This technique is used for thread communication and synchronization in a computing environment where the threads do not have shared memory (since the threads
reside in different virtual or physical machines). Hence the threads cannot share semaphores or monitors and cannot use shared variables to communicate.
Message passing can still be used, of course, in a shared memory platform.
Messages are sent through a port or channel with an operation like send(channel, message) and received from a port or channel with an operation like
receive(channel, message). Messages can be passed synchronously, meaning the sender blocks until the received does a receive and the receiver blocks until
the sender does a send. Since the sender and receiver are at specific known points in their code at a known specific instant of time, synchronous message passing
is also called a simple rendezvous with a one-way flow of information from the sender to the receiver.
In asynchronous message passing, the sender does not block. If there is not a receiver waiting to receive the message, the message is queued or buffered. The
receiver still blocks if there is no queued or buffered message when a receive is executed.
In conditional message passing, the message remains queued until some condition, specified by the receiver, becomes true. At that time, the message is passed to
the receiver, unblocking it.
A two-way flow of information, perhaps over the network, is called an extended rendezvous and can be implemented with a pair of sends and receives. Typically
a client thread uses this technique to communicate with a server thread and request a service to be performed on its behalf. A similar situation is a worker thread
contacting a master thread, asking for more work to do.
client or worker: send request; receive reply
server or master: receive request; perform service; send reply
Messages are objects and can be
passed by reference within the same Java Virtual Machine,
or serialized through a pipe within the same JVM,
or serialized through a socket between JVMs that are on the same physical machine or on different physical machines.
The base data types, int, double, etc., can be sent as messages in binary or raw data format through a pipe or socket using the DataInputStream and
DataOutputStream methods. They can also be sent as objects using the wrapper classes Integer, Double, etc.
Synchronization Package Classes
Here is a collection of Java message passing classes. All of the message passing channel classes implement the methods in the MessagePassing interface or the
ConditionalMessagePassing interface. This exception is thrown when an error occurs. This exception is used in implementing restricted rights channels
(below). All classes except the conditional ones extend this base class.
Synchronous Channel.
Asynchronous Channel. A Vector is used to queue sent but not yet received messages.
Asynchronous Conditional Channel. The receiver must pass an object that implements the Condition interface, that is the object must contain a
checkCondition() method that is used to determine which messages sent are eligible to be received.
Synchronous Conditional Channel.
Capacity Controlled Asynchronous Channel.
Receive-Only Rights Channel. Send-Only Rights Channel. These two filter classes can be wrapped around a message passing channel to permit only sending
or receiving on the channel. This is done by overriding the restricted method with one that throws NotImplementedMethodException.
Integers and Floating-Point Numbers as Messages in a Pipe or Socket Channel. The numbers are passed as binary or raw data types through a pipe within
the same JVM or a socket between different JVMs.
Serialized Objects as Messages in a Pipe or Socket Channel. The objects are serialized and deserialized using the writeObject() and readObject()
methods through a pipe within the same JVM or a socket between different JVMs.
