Java Synchronization

By Mario Marchand, Université Laval, adapted from the textbook "Applied Operating System Concepts" by Silberschatz, Galvin, and Gagne, Wiley, 2000.

First recall that a thread in Java can be in any one of the four possible states: New, Runnable, Blocked, and Dead.  A thread is in the New state when a thread object is created but not started. Calling the start() method allocates memory for the new thread in the JVM and calls the run() method of the thread object: this moves the thread from the New state to the Runnable state. A thread in the Runnable state is eligible to be run by the JVM (the JVM does not distinguish between a thread that is eligible to be run and a thread that is currently running). A thread becomes Blocked if it performs a blocking statement such as doing an I/O or invoke certain methods such as sleep() or suspend(). Calling the resume() method moves the thread from the Blocked to the Runnable state. A thread moves to the Dead state when its run() method terminates or when the stop() method is called. It is not possible to determine the exact state of a thread. But the isAlive() method returns a boolean value that determines whether or not a thread is in the Dead state. These concepts are reviewed in these ppt slides.

Now let us discuss the tools that are available in Java to perform thread synchronization.

Synchronized methods

Each object in Java has associated with it a single lock. When a ordinary method of an object is invoked by a thread, the lock is ignored. Consequently, an arbitrary number of threads can be active in the same method of an object at any time (either in the Runnable state or in the Blocked state). If, however, a method is qualified by the keyword synchronized, then only one thread can be in that method at any time; i.e. a synchronized method is mutually exclusive. More specifically, when a synchronized method of an object is invoked by a thread, the thread is permitted to run this method only if the thread owns the lock of the object. If, at the time of invocation, no other thread owns the lock of the object, then the lock of the object will be granted to the calling thread and the thread will enter the synchronized method. If, at the time of invocation, another thread owns the lock, then the calling thread will be put in the Blocked state and put in a queue of threads, called the entry queue of the object, that are waiting for the lock in order to enter into one of the synchronized methods of the object. An object can have more then one synchronized method and, in that case, all these synchronized methods are mutually exclusive between themselves: at any time, only one thread can be in one of the synchronized methods of an object. When a thread leaves a synchronized method, the lock is given to an arbitrary thread of the entry queue (this decision of which thread to choose is made by the JVM according to some fair policy) and the chosen thread is put into the Runnable state. Hence, each object in Java that has one or more synchronized methods defines a monitor (but, so far, without condition variables).

wait(), notify(), and notifyAll()

These other synchronization tools are additional methods that are available to any object in Java.

When a thread running in a synchronized method of an object is calling the wait() method of the same object, that thread releases the lock of the object, it also enters in the Blocked state, and is put in a special waiting queue, called the waiting queue of the object. Hence, each object has two distinct queues associated with it: a waiting queue and an entry queue. Note also that wait() forces the thread to release its lock. This means that it must own the lock of an object before calling the wait() method of that (same) object. Hence the thread must be in one of the object's synchronized methods before calling wait().

A thread in the waiting queue of an object can run again only when some other thread calls the notify() (or the notifyAll) method of the same object. More specifically, when a thread calls the notify() method of an object, the JVM picks an arbitrary thread in the waiting queue of the object and puts it in the entry queue of the same object (hence, that thread is still Blocked).  If instead a thread calls the notifyAll() method of an object, then all threads of the object's waiting queue are put in the entry queue. If no threads are waiting in the waiting queue, then notify() and notifyAll() have no effect. Before calling the notify() or notifyAll() method of an object, a thread must own the lock of the object (hence it must be in one of the object's synchronized methods).

Semaphores

There are no built-in semaphores in Java. It is however very easy to construct semaphores from the basic Java synchronization tools. Here, for example, is a Java class that implements a counting semaphore with identical functionality to the counting semaphore we have seen in class.

class Semaphore
{
        private int count;

        public Semaphore(int count)
        {
                this.count = count;
        }

        synchronized public void Wait()
        {
                count--;
                if (count<0) {
                        // then place this thread in waiting queue
                        try{wait();}
                                catch (Exception e) {
                                        System.out.println("Wait has been interrupted!");
                                }
                }
        }
 

        synchronized public void Signal()
        {
                count++;
                        // remove a thread in waiting queue
                        // and place it in entry queue
                        notify();
                        //has no effect if there are no threads in waiting queue
        }

}//Semaphore

Note that both methods are synchronized methods. Hence both Wait() and Signal() are mutually exclusive. Note also that Wait() calls wait() to block the calling thread and place it in the waiting queue of the semaphore object. Since wait() throws an exception, we need to use the try{} catch(){} exception handler. Hence wait() is always going to block the thread, unless some unusual event occurred (like the interruption of your program). The notify() method, however, does not throw any exception. Since notify() has no effect when no threads are in the waiting queue, it is not necessary to restrict the call to notify() to the case when count<=0, i.e. it is not necessary to replace notify() by if(cout<=0){ notify();}.

Once we have semaphores, we can use them to perform all of our synchronization tasks. This is the approach taken in the following Java program of the Producer/Consumer problem: ProdConSem.java. Note that all console input operations are done by CI.java and the file Semaphore.java contains the Semaphore class.
 

Trying to construct a monitor with condition variables

Each object in Java that has one or more synchronized methods defines a monitor. Furthermore, since each object has at most one waiting queue (built up by wait() and emptied by notify()), a java monitor has at most one condition variable. How can we then construct a monitor in Java that has more than one condition variable?

We might first try to create instances of following Condition class to represent condition variables.

class Condition {

        Condition() { }

        synchronized public void Cwait() {
                try {
                        wait();
                } catch (InterruptedException e) {
                        System.out.println("Cwait() interrupted");
                }
        }

        synchronized public void Csignal() {
                notify();
        }

}

Hence, different Condition objects would represent different condition variables.

Refer to the solution of the producer/consumer problem using a single monitor with two condition variables (notempty, and notfull) that we have seen in class. The bounded buffer would be a member of a BufferMonitor object that would contain two synchronized methods: take() and append(). We would also have two instances of Condition: notempty and notfull that would also be member of BufferMonitor. Hence this means that the first statement of take() would be:

        synchronized public void take(int id) {
                if (count==0) {
                        notempty.Cwait(); //wait until not empty
                }
                //...

and the first statement of append() would be:

        synchronized public void append(int id) {
                if (count==BuffSize) {
                        notfull.Cwait(); //wait until not full
                }
                //...
A call to Cwait() would always block the thread and put it in the waiting queue of the Condition object. But since that thread would also own the lock of the BufferMonitor object (since it did not release it), no other thread would be able to enter the BufferMonitor. Hence, no other thread would be able to call Csignal() since these calls are in the BufferMonitor's synchronized methods. Consequently, we would then have a deadlock! Hence, the program IncorrectProdConMon.java which implements such a solution has a deadlock.

To construct a monitor with more than one waiting queue (i.e. with more than one waiting condition) from a Java monitor, a thread should be able to release the lock of an object without exiting one of it's synchronization method and without calling the wait() method of the object. But Java does not provide any tools to accomplish this. Hence, the only way to construct such monitors is then to insure the mutual exclusion property of the monitor methods without defining these methods as synchronized! This could be accomplished, for instance, by using a semaphore to ensure mutual exclusion of each monitor methods. The program ProdConMon.java implements this solution.


Last update: January 21, 2002