Java Synchronization Tutorial

Introduction to Threads

A thread is an object which runs concurrently with the other threads that exist at the same time. Here is one way to construct and run a thread:

    Thread t = new Thread (command);
    t.start();
    // ...

The command object passed to the Thread constructor is any object that implements the Runnable interface. This interface has just one method named run() which is the method that is called by the newly created thread when the thread's start() method is called.

Threads are similar to the operating system concept of a process except that processes run in separate address spaces, while all the threads of one process run in the same address space. This means that two threads could make use of the same object concurrently. This can lead to unpredictable results, so it is necessary to ensure that threads cooperate with each other on shared objects.

Thread synchronization is done by setting locks on objects. This is similar to database locking except that all Java locks are exclusive locks. Other modes, such as shared locks or intention locks, were not supported in Java 1.4. This changed in Java 1.5. Using these other lock types increases the level of concurrency possible in a Java program and reduces the likelihood that a deadlock will occur. However, in this tutorial only exclusive locks will be considered.

In Java, one does not usually explicitly set and release locks. These operations are done implicitly by calling a method declared to be synchronized or by executing a block that synchronizes on the object. (In Java 1.5 one can now explicitly set and release a lock, but the syntax is different.) When such a method or block starts, an exclusive lock is set on the object. When the method returns or the thread leaves the block, the lock is released. As in databases, a thread can hold the same lock more than once. This can happen if a synchronized method or block calls another synchronized method, or executes a synchronized block, using the same object. The Java run-time system increments a lock count, exactly as in a database lock manager, each time a synchronized method or block is started, and decrements it each time a synchronized method returns or the thread leaves the block.

Incidentally, a static method can also be synchronized. When this is done, the object that is locked is the object of type Class corresponding to this class. Each class has a unique corresponding instance of type Class. One can acquire the Class instance of an object by executing the getClass() method of any object.

Simple Synchronization Example

The following is an example of the use of synchronized methods.

import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * The Dumpster Class checks in objects but never releases them.
 */
public class Dumpster {
    private List contents = new ArrayList();

    /**
     * Check an object into the global dumpster
     * @param object The object to be placed in the global dumpster.
     */
    public synchronized void dump(Object object) {
	contents.add(object);
    }
    /**
     * Construct a string that represents the current dumpster contents.
     * @return The string representation of the global dumpster.
     */
    public synchronized String contains() {
	String s = "The dumpster currently contains the following:\n";
	for (Iterator i = contents.iterator(); i.hasNext(); ) {
	    s += i.next() + "\n";
	}
	return s;
    }
}

The Producer-Consumer Problem

If the Dumpster class is generalized to allow objects to be removed as well as inserted, then we have a solution to the classical concurrency problem known as the Producer-Consumer problem. We are indebted to a student, Michael Vigneau, who produced following graphic illustration of the Producer-Consumer problem.

If there is just one producer and one consumer, then it is not necessary to use locks. Simple load-store synchronization has much better performance. In principle, one can use load-store synchronization whenever the number of producers and consumers is bounded and known in advance. The solution using locking is appropriate only when the producers and consumers are not known in advance.

Unbounded Producer-Consumer

The SharedStack class given below is an example of a solution to the Producer-Consumer problem in which the capacity of the buffer is unbounded. In this case, only a consumer may ever have to wait, which occurs when the buffer is empty. If the buffer is bounded, then both producers and consumers may have to wait. Producers may have to wait for space to become available, while consumers may have to what until something is in the shared stack.

Whether bounded or unbounded, the Producer-Consumer problem cannot be solved with locks alone. The consumer must wait until something is in the buffer. While waiting it must sleep. This is accomplished with the wait() method. The producer must somehow convey to any waiting consumers that an item is now available. In other words, it has to wake up at least one consumer. This is accomplished with the notify() method. The wait() and notify() methods are in the Object class, so every object has them.

import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * A shared stack class.
 */
public class SharedStack {
    private List stack = new ArrayList();
    
    /**
     * Construct a new shared stack.
     */
    public SharedStack() {}
    
    /**
     * Push a new object onto a shared stack.
     * @param object The object to be pushed onto the stack.
     */
    public synchronized void produce(Object object) {
	stack.add(object);
	notify();
    }
    /**
     * Pop the top object off a stack or wait, if needed, until there is one.
     * @return The top object on the stack.
     */
    public synchronized Object consume() {
	while (stack.isEmpty()) {
	    try {
		wait();
	    } catch (InterruptedException e) {
	    }
	}
	int lastElement = stack.size() - 1;
	Object object = stack.get(lastElement);
	stack.remove(lastElement);
	return object;
    }
    /**
     * Construct a string that represents a shared stack.
     * @return The string representation of a shared stack.
     */
    public synchronized String contains() {
	String s = "The shared stack currently contains the following:\n";
	for (Iterator i = stack.iterator(); i.hasNext(); ) {
	    s += i.next() + "\n";
	}
	return s;
    }
}

Bounded Producer-Consumer

In the most general Producer-Consumer problem, the capacity of the buffer is bounded, so both producers and consumers may have to wait, and both must notify the others. In this case it is not enough, in general, to use the notify() method. The problem is that both producers and consumers may now be waiting for a notification. It is possible for a producer to notify another producer or for a consumer to notify another consumer. A particular case where this happens is given in the scenario below. Although this is very unlikely, it is still possible, so one should use notifyAll() instead of notify(). The notifyAll() method will notify all waiting threads rather than just one of them.

import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * A shared buffer class.
 */
public class SharedBuffer {
    private List buffer;
    private int capacity;

    /**
     * Construct a new shared buffer.
     * @param capacity The maximum capacity of the shared buffer.
     */
    public SharedBuffer(int capacity) {
	this.capacity = capacity;
	buffer = new ArrayList(capacity);
    }
    
    /**
     * Add a new object to a shared buffer or wait if no room is available.
     * @param object The object to be added to the buffer.
     */
    public synchronized void produce(Object object) {
	while (buffer.size() == capacity) {
	    try {
		wait();
		System.out.println("Buffer is full!");
	    } catch (InterruptedException e) {
	    }
	}
	buffer.add(object);
	notifyAll();
    }
    /**
     * Remove the first object waiting in the buffer or wait until there is one.
     * @return The first object in the buffer.
     */
    public synchronized Object consume() {
	while (buffer.isEmpty()) {
	    try {
		wait();
	    } catch (InterruptedException e) {
	    }
	}
	Object object = buffer.get(0);
	buffer.remove(0);
	notifyAll();
	return object;
    }
    /**
     * Construct a string that represents a shared buffer.
     * @return The string representation of a shared buffer.
     */
    public synchronized String contains() {
	String s = "The shared buffer currently contains the following:\n";
	for (Iterator i = buffer.iterator(); i.hasNext(); ) {
	    s += i.next() + "\n";
	}
	return s;
    }
}

Synchronization Scenario

Here is a simple scenario in which the notifyAll() method is necessary for correct synchronization of a shared bounded buffer. In this scenario there are 2 producers P₁ and P₂, and 2 consumers C₁ and C₂. Assume that the buffer capacity is 1, in other words, there is only one slot for a shared object in the shared list and that one is using notify() for notifications. The scenario proceeds as follows:

1. The buffer is initially empty with both consumers waiting. In other words, both consumers have called the wait() method.
2. Both producers concurrently attempt to place an object in the shared buffer. One of them, P₁, obtains the lock first and places its object in the shared buffer.
3. P₁ calls the notify() method. This causes one of the two consumers to be notified. Suppose that C₂ is the thread that is notified. The result of notification is that C₂ is removed from the wait set and placed in the lock queue.
4. P₁ releases the lock. This causes the thread at the head of the lock queue to be given ownership of the lock and to be changed from the blocked state to the ready state. The thread at the head of the queue is P₂.
5. Eventually P₂ will become the running thread. When it starts running it discovers that the buffer is full, so it calls the wait() method, releasing the lock, going into the blocked state and being added to the wait set.
6. At this point both a producer P₂ and a consumer C₁ are in the wait set.
7. Because P₂ has released the lock, C₂ obtains the lock and its state is changed from blocked to ready.
8. Eventually C₂ will become the running thread. When it does, it finds an object in the buffer. It removes (consumes) this object from the buffer and calls notify().
9. Because the wait set is not a queue, the notify signal can be given to either thread in the wait set. In this case it could be given to consumer C₁. In other words, a consumer could notify another consumer. The consumer C₁ is then removed from the wait set and placed in the lock queue.
10. The consumer C₂ then releases the lock. This causes C₁ to be become the owner of the lock, and its state is changed from blocked to ready.
11. Eventually C₁ becomes the running thread. When it does it discovers that the buffer is empty and it calls the wait() method, releasing the lock, going into the blocked state and being added to the wait set.
12. At this point both a producer P₂ and a consumer C₁ are in the wait set. Although the buffer is empty, the producer has not been notified about this. The situation could remain like this indefinitely.

The scenario above can easily be generalized to the case of a buffer with capacity N by using 2*N consumers and 2*N producers. One simply replaces each consumer in the scenario above with N consumers and each producer with N producers. With a little more effort it should be possible to introduce more complicated scenarios in which the number of producers and consumers could be reduced, but it is not clear how many producers and consumers are necessary for one to have a problem.

In any case, there is no problem if one uses notifyAll() rather than notify().