Threads and Concurrent Programming

The examples in the previous sections were designed to illustrate the issue of thread asynchronicity and the principles of mutual exclusion and critical sections. Through the careful design of the algorithm and the appropriate use of the synchronized qualifier, we have managed to design a program that correctly coordinates the behavior of the Customers and Clerk in this bakery simulation.

The Busy-Waiting Problem

One problem with our current design of the Bakery algorithm is that it uses busy waiting on the part of the Clerk thread. Busy waiting occurs when a thread, while waiting for some condition to change, executes a loop instead of giving up the CPU. Because busy waiting is wasteful of CPU time, we should modify the algorithm.

As it is presently designed, the Clerk thread sits in a loop that repeatedly checks whether there’s a customer to serve:

A far better solution would be to force the Clerk thread to wait until a customer arrives without using the CPU. Under such a design, the Clerk thread can be notified and enabled to run as soon as a Customer becomes available. Note that this description views the customer/clerk relationship as one-half of the producer/consumer relationship. When a customer takes a number, it produces a customer in line that must be served (that is, consumed) by the clerk.

This is only half the producer/consumer relationship because we haven’t placed any constraint on the size of the waiting line. There’s no real limit to how many customers can be produced. If we did limit the line size, customers might be forced to wait before taking a number if, say, the tickets ran out, or the bakery filled up. In that case, customers would have to wait until the line resource became available and we would have a full-fledged producer/consumer relationship.

The wait/notify Mechanism

So, let’s use Java’s wait/notify mechanism to eliminate busy waiting from our simulation. As noted in Figure 14.6, the wait() method puts a thread into a waiting state, and notify() takes a thread out of waiting and places it back in the ready queue. To use these methods in this program we need to modify the nextNumber() and nextCustomer() methods. If there is no customer in line when the Clerk calls the nextCustomer() method, the Clerk should be made to wait():

Note that the Clerk still checks whether there are customers waiting. If there are none, the Clerk calls the wait() method. This removes the Clerk from the CPU until some other thread notifies it, at which point it will be ready to run again. When it runs again, it should check that there is in fact a customer waiting before proceeding. That’s why we use a while loop here. In effect, the Clerk will wait until there’s a customer to serve. This is not busy waiting because the Clerk thread loses the CPU and must be notified each time a customer becomes available.

When and how will the Clerk be notified? Clearly, the Clerk should be notified as soon as a customer takes a number. Therefore, we put a notify() in the nextNumber() method, which is the method called by each Customer as it gets in line:

Thus, as soon as a Customer thread executes the nextNumber() method, the Clerk will be notified and allowed to proceed.

What happens if more than one Customer has executed a wait()? In that case, the JVM will maintain a queue of waiting Customer threads. Then, each time a notify() is executed, the JVM will take the first Customer out of the queue and allow it to proceed.

If we use this model of thread coordination, we no longer need to test customerWaiting() in the Clerk.run() method. It is to be tested in the TakeANumber.nextCustomer(). Thus, the Clerk.run() can be simplified to

The Clerk thread may be forced to wait when it calls the nextCustomer method.

Because we no longer need the customerWaiting() method, we end up with the new definition of TakeANumber shown in Figures 14.27 and 14.28. 

Given this version of the program, the following kind of output will be generated:

SELF-STUDY EXERCISE

EXERCISE 14.11 An interesting experiment to try is to make the Clerk a little slower by making it sleep for up to 2,000 milliseconds. Take a guess at what would happen if you ran this experiment. Then run the experiment and observe the results.

The wait/notify Mechanism 

There are a number of important restrictions that must be observed when using the wait/notify mechanism: methods:

• Both wait() and notify() are methods of the Object class, not the Thread class. This enables them to lock objects, which is the essential feature of Java’s monitor mechanism. 
• A wait() method can be used within a synchronized method. The method doesn’t have to be part of a Thread. 
• You can only use wait() and notify() within synchronized methods. If you use them in other methods, you will cause an IllegalMonitorStateException with the message “current thread not owner.” 
• When a wait()—or a sleep()—is used within a synchronized method, the lock on that object is released so that other methods can access the object’s synchronized methods.