Java, Java, Java

For some applications it is necessary to synchronize and coordinate the behavior of threads to enable them to carry out a cooperative task. Many cooperative applications are based on the producer/consumer model. Ac- cording to this model, two threads cooperate at producing and consuming a particular resource or piece of data. The producer thread creates some message or result, and the consumer thread reads or uses the result. The consumer has to wait for a result to be produced, and the producer has to take care not to overwrite a result that hasn’t yet been consumed. Many types of coordination problems fit the producer/consumer model.

One example of an application for this model would be to control the display of data that is read by your browser. As information arrives from the Internet, it is written to a buffer by the producer thread. A sepa- rate consumer thread reads information from the buffer and displays it in your browser window. Obviously, the two threads must be carefully synchronized.

 

Problem Statement

To illustrate how to address the sorts of problems that can arise when you try to synchronize threads, let’s consider a simple application in which

several threads use a shared resource. You’re familiar with those take-Simulating a waiting line

a-number devices that are used in bakeries to manage a waiting line. Customers take a number when they arrive, and the clerk announces who’s next by looking at the device. As customers are called, the clerk increments the “next customer” counter by one.

There are some obvious potential coordination problems here. The de- vice must keep proper count and can’t skip customers. Nor can it give the same number to two different customers. Nor can it allow the clerk to serve nonexistent customers.

Our task is to build a multithreaded simulation that uses a model of a take-a-number device to coordinate the behavior of customers and a (sin- gle) clerk in a bakery waiting line. To help illustrate the various issues involved in trying to coordinate threads, we will develop more than one version of the program.

Problem Decomposition

This simulation will use four classes of objects.Figure 14.17 pro-What classes do we need?

vides a UML representation of the interactions among the objects. The

Figure 14.17: The Bakery creates the Customer and Clerk threads and the TakeANumber gadget. Then Customers request and re- ceive waiting numbers and the Clerk requests and receives the number of the next customer to serve.

 

 

 

 

 

 

 

 

 

 

 

 

TakeANumber object will serve as a model of a take-a-number device. This is the resource that will be shared by the threads, but it is not a thread itself. The Customer class, a subclass of Thread, will model the behavior of a customer who arrives on line and takes a number from the TakeANumber device. There will be several Customer threads created that then compete for a space in line. The Clerk thread, which simulates the behavior of the store clerk, should use the TakeANumber device to determine who the next customer is and should serve that customer. Fi- nally, there will be a main program that will have the task of creating and

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 14.18: The TakeANumber object keeps track of numbers and customers.

 

 

Passing a reference to a shared object

starting the various threads. Let’s call this the Bakery class, which gives us the following list of classes:

Bakery—creates the threads and starts the simulation. TakeANumber—represents the gadget that keeps track of the next cus- tomer to be served.

Clerk—uses the TakeANumber to determine the next customer and will serve the customer.

Customer—represents the customers who will use the TakeANumber

to take their place in line.

Design: The TakeANumber Class

The TakeANumber class must track two things: Which customer will be served next, and which waiting number the next customer will be given. This suggests that it should have at least two public methods: nextNumber(), which will be used by customers to get their waiting numbers, and nextCustomer(), which will be used by the clerk to de- termine who should be served (Fig. 14.18). Each of these methods will simply retrieve the values of the instance

variables, next and serving, which keep track of these two values.

As part of the object’s state, these variables should be private.

How should we make this TakeANumber object accessible to all of the other objects—that is, to all of the customers and to the clerk? The easiest way to do that is to have the main program pass a reference to the TakeANumber when it constructs the Customers and the Clerk. They can each store the reference as an instance variable. In this way, all the objects in the simulation can share a TakeANumber object as a common resource. Our design considerations lead to the definition of the TakeANumber class shown in Figure 14.19.

,,

 

 

 

 

 

 

 

 

 

 

 

J

Figure 14.19: Definition of the TakeANumber class, Version 1.

 

Note that the nextNumber() method is declared synchronized. As we will discuss in more detail, this ensures that only one customer at a time can take a number. Once a thread begins executing a synchronized method, no other thread can execute that method until the first thread

 

finishes. This is important because, otherwise, several Customers could Synchronized methods

call the nextNumber method at the same time. It’s important that the customer threads have access only one at a time, also called mutually ex- clusive access to the TakeANumber object. This form of mutual exclusion is important for the correctness of the simulation.

SELF-STUDY EXERCISE

EXERCISE 14.9 What is the analogue to mutual exclusion in the real- world bakery situation?

Java Monitors and Mutual Exclusion

An object that contains synchronized methods has a monitor associated

with it. A monitor is a widely used synchronization mechanism that en-The monitor concept

sures that only one thread at a time can execute a synchronized method. When a synchronized method is called, a lock is acquired on that object. For example, if one of the Customer threads calls nextNumber(), a lock will be placed on that TakeANumber object. While an object is locked, no other synchronized method can run in that object. Other threads must wait for the lock to be released before they can execute a synchronized method.

While one Customer is executing nextNumber(), all other Customers Mutually exclusive access to a shared

 

will be forced to wait until the first Customer is finished. When the synchronized method is exited, the lock on the object is released, al- lowing other Customer threads to access their synchronized meth- ods. In effect, a synchronized method can be used to guarantee mu- tually exclusive access to the TakeANumber object among the competing customers.

 

 

 

 

One cautionary note here is that although a synchronized method blocks access to other synchronized methods, it does not block access to nonsyn- chronized methods. This could cause problems. We will return to this issue in the next part of our case study when we discuss the testing of our program.

The Customer Class

A Customer thread should model the behavior of taking a number from the TakeANumber gadget. For the sake of this simulation, let’s suppose that after taking a number, the Customer object just prints it out. This will serve as a simple model of “waiting on line.” What about the Customer’s state? To help distinguish one customer

object

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 14.20:The Customer

thread.

 

from another, let’s give each customer a unique ID number starting at 10001, which will be set in the constructor method. Also, as we noted ear- lier, each Customer needs a reference to the TakeANumber object, which is passed as a constructor parameter (Fig. 14.20). This leads to the defini- tion of Customer shown in Figure 14.21. Note that before taking a num- ber the customer sleeps for a random interval of up to 1,000 milliseconds. This will introduce a bit of randomness into the simulation.

,,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J

Figure 14.21: Definition of the Customer class, Version 1.

 

 

 

 

Static (class) variables

Another important feature of this definition is the use of the static variable number to assign each customer a unique ID number. Remem- ber that a static variable belongs to the class itself, not to its instances. Therefore, each Customer that is created can share this variable. By incrementing it and assigning its new value as the Customer’s ID, we guarantee that each customer has a unique ID number.

 

 

 

 

 

The Clerk Class

The Clerk thread should simulate the behavior of serving the next customer in line, so the Clerk thread will repeatedly access TakeANumber.nextCustomer() and then serve that customer. For the sake of this simulation, we’ll just print a message to indicate which customer is being served. Because there’s only one clerk in this simu- lation, the only variable in its internal state will be a reference to the TakeANumber object (Fig. 14.22). In addition to the constructor, all we really need to define for this class is the run() method. This

leads to the definition of Clerk shown in Figure 14.23. In this case, the sleep() method is necessary to allow the Customer threads to run. The Clerk will sit in an infinite loop serving the next customer on each iteration.

 

 

Figure 14.22: The Clerk thread.

 

,,

 

 

 

 

 

 

 

 

 

 

 

 

 

J

Figure 14.23: Definition of Clerk, Version 1.

 

The Bakery Class

Finally, Bakery is the simplest class to design. It contains the main()

method, which gets the whole simulation started. As we said, its role will

be to create one Clerk thread and several Customer threads, and getThe main program

them all started (Fig. 14.24). Notice that the Customers and the Clerk

are each passed a reference to the shared TakeANumber gadget.

Problem: Nonexistent Customers

Now that we have designed and implemented the classes, let’s run sev- eral experiments to test that everything works as intended. Except for the synchronized nextNumber() method, we’ve made little attempt to make sure that the Customer and Clerk threads will work together cooperatively, without violating the real-world constraints that should be satisfied by the simulation. If we run the simulation as it is presently

 

,,

 

 

 

 

 

 

 

 

J

Figure 14.24: Definition of the Bakery class.

 

 

 

 

 

Testing and debugging

coded, it will generate five customers and the clerk will serve all of them. But we get something like the following output:

,,

 

 

 

 

Problem: The clerk thread doesn’t

J

Our current solution violates an important real-world constraint: You can’t serve customers before they enter the line! How can we ensure

 

wait for customer threadsthat the clerk doesn’t serve a customer unless there’s actually a customer

waiting?

The wrong way to address this issue would be to increase the amount of sleeping that the Clerk does between serving customers. Indeed, this would allow more customer threads to run, so it might appear to have the desired effect, but it doesn’t truly address the main problem: A clerk cannot serve a customer if no customer is waiting.

The correct way to solve this problem is to have the clerk check that there are customers waiting before taking the next customer. One way to model this would be to add a customerWaiting() method to our TakeANumber object. This method would return true whenever next is greater than serving. That will correspond to the real-world situation

The clerk checks the linein which the clerk can see customers waiting in line. We can make the

 

following modification to Clerk.run():

,,

 

 

 

 

 

 

 

 

J

And we add the following method to TakeANumber (Fig. 14.25):

,,

 

 

 

 

In other words, the Clerk won’t serve a customer unless there are cus- tomers waiting—that is, unless next is greater than serving. Given these changes, we get the following type of output when we run the simulation:

J

 

Figure14.25:Therevised

TakeANumber class.

 

 

 

 

 

 

 

 

 

 

 

 

\J

This example illustrates that when application design involves cooperat- ing threads, the algorithm used must ensure the proper cooperation and coordination among the threads.

 

Problem: Critical Sections

It is easy to forget that thread behavior is asynchronous. You can’t pre-

dict when a thread might be interrupted or might have to give up theThread interruptions are

unpredictable

 

CPU to another thread. In designing applications that involve cooperat- ing threads, it’s important that the design incorporates features to guard against problems caused by asynchronicity. To illustrate this problem, consider the following statement from the Customer.run() method:

,,

 

J

Even though this is a single Java statement, it breaks up into several Java bytecode statements. A Customer thread could certainly be interrupted between getting the next number back from TakeANumber and printing it out. We can simulate this by breaking the println() into two statements and putting a sleep() in their midst:

,,

 

 

 

 

 

 

 

J

If this change is made in the simulation, you might get the following output:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Problem: An interrupt in a critical

\J

Because the Customer threads are now interrupted in between taking a number and reporting their number, it looks as if they are being served in the wrong order. Actually, they are being served in the correct order. It’s their reporting of their numbers that is wrong!

The problem here is that the Customer.run() method is being in- terrupted in such a way that it invalidates the simulation’s output. A

 

sectionmethod that displays the simulation’s state should be designed so that once a thread begins reporting its state, that thread will be allowed to fin- ish reporting before another thread can start reporting its state. Accurate reporting of a thread’s state is a critical element of the simulation’s overall integrity.

 

A critical section is any section of a thread that should not be inter- rupted during its execution. In the bakery simulation, all of the statements that report the simulation’s progress are critical sections. Even though the chances are small that a thread will be interrupted in the midst of a println() statement, the faithful reporting of the simulation’s state should not be left to chance. Therefore, we must design an algorithm that prevents the interruption of critical sections.

 

Creating a Critical Section

The correct way to address this problem is to treat the reporting of the cus- tomer’s state as a critical section. As we saw earlier when we discussed the concept of a monitor, a synchronized method within a shared ob- ject ensures that once a thread starts the method, it will be allowed to

finish it before any other thread can start it. Therefore, one way out of Making a critical section

 

this dilemma is to redesign the nextNumber() and nextCustomer() methods in the TakeANumber class so that they report which customer receives a ticket and which customer is being served (Fig. 14.26). In this version all of the methods are synchronized, so all the actions of the TakeANumber object are treated as critical sections.

uninterruptible

 

 

,,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J

Figure 14.26: Definition of the TakeANumber class, Version 2.

 

 

Note that the reporting of both the next number and the next customer to be served are now handled by TakeANumber in Figure 14.26 . Because the methods that handle these actions are synchronized, they cannot be interrupted by any threads involved in the simulation. This guarantees that the simulation’s output will faithfully report the simulation’s state.

 

Given these changes to TakeANumber, we must remove the println() statements from the run() methods in Customer:

,,

 

 

 

 

 

J

and from the run() method in Clerk:

,,

 

 

 

 

 

 

 

 

J

Rather than printing their numbers, these methods now just call the ap- propriate methods in TakeANumber. Given these design changes, our simulation now produces the following correct output:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Preventing undesirable interrupts

\J

The lesson to be learned from this is that in designing multithreaded pro- grams, it is important to assume that if a thread can be interrupted at a certain point, it will be interrupted at that point. The fact that an interrupt

 

is unlikely to occur is no substitute for the use of a critical section. This is something like “Murphy’s Law of Thread Coordination.”

 

 

In a multithreaded application, the classes and methods should be de- signed so that undesirable interrupts will not affect the correctness of the algorithm.

 

 

 

SELF-STUDY EXERCISE

EXERCISE 14.10 Given the changes we’ve described, the bakery sim- ulation should now run correctly regardless of how slow or fast the Customer and Clerk threads run. Verify this by placing different-sized sleep intervals in their run() methods. (Note: You don’t want to put a sleep() in the synchronized methods because that would undermine the whole purpose of making them synchronized in the first place.)

Using wait/notify to Coordinate Threads

The examples in the previous sections were designed to illustrate the is- sue of thread asynchronicity and the principles of mutual exclusion and critical sections. Through the careful design of the algorithm and the ap- propriate 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 Busy waiting

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 repeat- edly checks whether there’s a customer to serve:

,,

 

 

 

 

 

 

 

 

 

 

 

 

Producer/consumer

J

A far better solution would be to force the Clerk thread to wait un- til 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 wait- ing 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():

 

,,

 

 

 

 

 

 

 

 

J

 

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 pointA waiting thread gives up the CPU

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:

,,

 

 

 

 

 

J

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.

J

 

 

 

 

Figure 14.27: In the final design of TakeANumber, its methods are synchronized.

 

,,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J

Figure 14.28: The TakeANumber class, Version 3.

 

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

,,

 

 

 

 

 

 

 

 

J

 

 

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 whenWait/notify go into synchronized

 

using the wait/notify mechanism:

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.