I have written an application that demonstrates a volatile variable. When you run that application, it starts two threads. One thread runs in a loop and continually outputs the value of an integer variable (which it also increments). The other thread sleeps for five seconds and then writes a value to another variable, to "tell" the loop thread to terminate. That application's Terminate.java source code, which is included in this article's attached code.zip file, appears below.

public class Terminate
{
   public static void main (String [] args)
   {
      ThreadB tb = new ThreadB ();
      ThreadA ta = new ThreadA (tb);

      tb.start ();
      ta.start ();
   }
}

class ThreadA extends Thread
{
   private ThreadB tb;

   ThreadA (ThreadB tb)
   {
      this.tb = tb;
   }

   public void run ()
   {
      try
      {
          Thread.sleep (5000);
      }
      catch (InterruptedException e)
      {
      }

      tb.finished = true;
   }
}

class ThreadB extends Thread
{
   public volatile boolean finished = false;

   private int sum = 0;

   public void run ()
   {
      while (!finished)
      {
         System.out.println ("sum = " + sum++);
         Thread.yield ();
      }
   }
}

Notice that I've marked ThreadB's finished variable with the volatile keyword. This guarantees that each thread will always access the value of finished from main memory. For Java VMs that are capable of caching variable values in local memory, threads will be required to access the value of finished from main memory; no infinite loop will occur when this program is run on those Java VMs, because both threads work with the same main memory copy of finished.

Note: J2SE 5.0 introduces java.util.concurrent.atomic, a package of classes that extends the notion of volatile variables to include an atomic conditional update operation, which permits lock-free, thread-safe programming on single variables.

A Tour of J2SE 5.0's Synchronizers

J2SE 5.0 introduces four kinds of synchronizers, high-level tools that let your code achieve different kinds of synchronization: countdown latches, cyclic barriers, exchangers, and semaphores. These high-level synchronization tools are implemented by five classes in the java.util.concurrent package. This section identifies each class, as it briefly explores the first three synchronizers and extensively explores semaphores.

Countdown Latches

A countdown latch is a synchronizer that allows one or more threads to wait until some collection of operations being performed in other threads finishes. This synchronizer is implemented by the CountDownLatch class.

Cyclic Barriers

A cyclic barrier is a synchronizer that allows a collection of threads to wait for each other to reach a common barrier point. This synchronizer is implemented by the CyclicBarrier class and also makes use of the BrokenBarrierException class.

Exchangers

An exchanger is a synchronizer that allows a pair of threads to exchange objects at a synchronization point. This synchronizer is implemented by the Exchanger<V> class, where V is a placeholder for the type of objects that may be exchanged.

Semaphores

A semaphore, as implemented in J2SE 5.0's Semaphore class, is a synchronizer that uses a counter to limit the number of threads that can access limited resources. Ironically, this high-level synchronization tool is based on the same-named, low-level primitive that is often used to implement monitors. The discussion that follows first explores this low-level primitive, and then explores Semaphore.

In 1965, E. W. Dijkstra invented the semaphore concurrency construct. He used that construct to support mutual exclusion, the act of restricting shared resource access to one process at a time. Nowadays, we don't think about processes. Instead, we think about threads. That's why I refer to thread instead of process in the following paragraph.

Dijkstra's semaphore construct is a protected variable that initializes to a non-negative integer count, implements P (from the Dutch word "proberen," meaning "to test") and V (from the Dutch word "verhogen," meaning "to increment") operations, and has a wait queue. When a thread executes P on the semaphore, the count is tested to see if it is greater than 0. If that is the case, the semaphore decrements the count. But if the count is 0, the calling thread is made to wait in the queue. When a thread executes V on the semaphore, the semaphore determines if one or more threads are waiting in the queue. If so, the semaphore allows one of those threads to proceed. But if no threads are waiting, the count increments. Each one of the P and V operations is indivisible.

Semaphores classify as counting semaphores or binary semaphores. A semaphore is a counting semaphore if it can assume any non-negative integer value. The SDK documentation for J2SE 5.0's Semaphore class refers to that class as a counting semaphore. But if the semaphore can only assume 0 or 1, it is known as a binary semaphore. Binary semaphores are a special case of counting semaphores.

Semaphore uses the concept of permits to explain how it works. A thread must acquire a permit, guaranteeing that an item is available for use, before the thread can obtain the item from a pool of items. When a thread finishes using the item, it returns that item back to the pool and the permit back to the semaphore.

Use the public Semaphore(int permits, boolean fair) constructor to create a semaphore: permits specifies the number of available permits (hence resources that are available in a pool), and fair indicates whether or not the semaphore guarantees a first-in first-out (FIFO) granting of permits under contention (true, if this is the case). An example:

Semaphore sem = new Semaphore (1, false);

creates a binary semaphore that does not guarantee FIFO granting of permits under contention.

The public void acquire() method acquires a permit from the semaphore. The calling thread blocks until one is available or the thread is interrupted. An example:

sem.acquire ();

The public void release() method returns a permit to the semaphore. If any threads are waiting for a permit, one of those threads is selected and given the just-released permit. The thread is then re-enabled for thread scheduling. An example:

sem.release ();

To demonstrate Semaphore, I've created an application that makes use of the Pool class, shown in the SDK's Semaphore documentation. Check out that application's SemDemo.java source code, which locates in the article's code.zip file.

Conclusion

An exploration of Java's synchronization fundamentals is not complete without an examination of thread communication, volatile variables, and synchronizers. You've learned how Java uses its waiting and notification mechanism to support thread communication, have seen that volatile variables serve as a special-purpose alternative to synchronization, and have acquired insight into J2SE 5.0's high-level synchronizer tools.

I have some homework for you to accomplish:

• Five philosophers sit around a circular table. Each philosopher alternates between thinking and eating rice. In front of each philosopher is a bowl of rice that is constantly replenished by a dedicated waiter. Exactly five chopsticks are on the table, with one chopstick between each adjacent pair of philosophers. Each philosopher must pick up both chopsticks adjacent to his/her plate simultaneously before that philosopher can eat.

  Create a Java application that simulates this behavior. Avoid deadlock and the problem of indefinite postponement, where one of more philosophers soon starve because philosophers adjacent to the starving philosophers are always eating. Make sure that mutual exclusion is enforced, so that two adjacent philosophers do not use the same chopstick at the same time.

Next time, Java Tech explores SANE and TWAIN.

Resources

• Sample code for this article

Answers to Previous Homework

The previous Java Tech article presented you with some challenging homework on locks, synchronized methods, and synchronized statements. Let's revisit that homework and investigate solutions.

1. If a thread holds a lock, what happens when the thread needs to enter another critical section controlled by the same lock?

   The thread is allowed to enter the other critical section and execute its code without having to re-grab the same lock. Furthermore, the lock is not released when the thread leaves the inner critical section and returns to the outer critical section, because that lock must be held while the thread continues to execute within the outer critical section.

2. In the earlier example of a component's event registration and listener logic, I presented two synchronized methods and a synchronized statement. You might be tempted to remove the synchronized statement from notifyClients() and make the entire method synchronized. What is wrong with that idea?

   We run the risk of deadlock if we make the entire method synchronized. How is this possible? Assume two threads: an event-notification thread that invokes each registered listener's event-handling method, and a listener thread that registers that object's interest in receiving event notifications. Assume the event-handling method is synchronized, to protect itself from simultaneous invocation by multiple threads. Now consider this scenario: the event-notification thread has just entered its synchronized method and enters the loop to begin sending event notifications to registered listeners. At the same time, the listener thread is executing within code that synchronizes via the same lock as the listener's synchronized event-handling method. Each thread holds its own lock. Suppose the listener thread invokes a synchronized method in the event notification object to deregister its listener object. Because the deregistration method is synchronized using the same lock as the event-notification synchronized method, the listener thread must wait because the event-notification thread holds that lock. When the event-notification thread attempts to invoke the listener's event-handling method, it is forced to wait when it attempts to acquire the listener's lock, because the listener thread holds that lock. Neither thread can proceed because each thread holds the other thread's required lock, and deadlock occurs.

3. Construct an example that illustrates a lack of synchronization due to a pair of threads acquiring different locks. Use the keyword this and the synchronized statement in the example.

   Consult the NoSync.java source code in this article's attached code.zip file.

Jeff Friesen is a freelance software developer and educator specializing in Java technology. Check out his site at javajeff.mb.ca.