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. According 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 separate consumer thread reads information from the buffer and displays it in your browser window. Obviously, the two threads must be carefully synchronized.
Subsection14.6.1Problem 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-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 device 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 (single) 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.
Subsection14.6.2Problem Decomposition
This simulation will use four classes of objects. Figure 14.6.1 provides a UML representation of the interactions among the objects.
Figure14.6.1.The Bakery creates the Customer and Clerk threads and the TakeANumber gadget. Then Customer s request and receive waiting numbers and the Clerk requests and receives the number of the next customer to serve.
The 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. Finally, there will be a main program that will have the task of creating and 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 customer 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.
Subsection14.6.3Design: The TakeANumberClass
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 determine who should be served (Figure 14.6.2). 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.
Figure14.6.2.The TakeANumber class.
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 Listing 14.6.3.
class TakeANumber {
private int next = 0; // Next place in line
private int serving = 0; // Next customer to serve
public synchronized int nextNumber() {
next = next + 1;
return next;
} // nextNumber()
public int nextCustomer() {
++serving;
return serving;
} // nextCustomer()
} // TakeANumber
Listing14.6.3.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 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 exclusive access to the TakeANumber object. This form of mutual exclusion is important for the correctness of the simulation.
ExercisesSelf-Study Exercise
1.Mutual exclusion.
What is the analogue to mutual exclusion in the real-world bakery situation?
Bakery customers are polite by nature.
Really? Even when they run out of donuts?
The take-a-number machine allows only one person at a time to take a ticket.
Right,
The baker makes sure customers stand in a single file.
Good luck with that.
All of the above working together.
Nah.
Subsection14.6.4Java 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 ensures 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 will be forced to wait until the first Customer is finished. When the synchronized method is exited, the lock on the object is released, allowing other Customer threads to access their synchronized methods. In effect, a synchronized method can be used to guarantee mutually exclusive access to the TakeANumber object among the competing customers.
Principle14.6.4.synchronized.
Once a thread begins to execute a synchronized method in an object, the object is locked so that no other thread can gain access to that object’s synchronized methods.
In order to restrict access of a method or set of methods to one object at a time (mutual exclusion), declare the methods synchronized.
One cautionary note here is that although a synchronized method blocks access to other synchronized methods, it does not block access to nonsynchronized 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.
Subsection14.6.5The CustomerClass
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?
Figure14.6.6.The Customer class.
To help distinguish one customer 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 earlier, each Customer needs a reference to the TakeANumber object, which is passed as a constructor parameter (Figure 14.6.6). This leads to the definition of Customer shown in Listing 14.6.7. Note that before taking a number the customer sleeps for a random interval of up to 1,000 milliseconds. This will introduce a bit of randomness into the simulation.
public class Customer extends Thread {
private static int number = 10000; // Initial ID number
private int id;
private TakeANumber takeANumber;
public Customer( TakeANumber gadget ) {
id = ++number;
takeANumber = gadget;
}
public void run() {
try {
sleep( (int)(Math.random() * 1000 ) );
System.out.println("Customer " + id +
" takes ticket " + takeANumber.nextNumber());
} catch (InterruptedException e) {
System.out.println("Exception " + e.getMessage());
}
} // run()
} // Customer
Listing14.6.7.Definition of the Customer class, Version 1.
Another important feature of this definition is the use of the static variable number to assign each customer a unique ID number. Remember 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.
Principle14.6.8.Static (Class) Variables.
Static variables are associated with the class itself and not with its instances.
Principle14.6.9.EFFECTIVE DESIGN: Unique IDs.
Static variables are often used to assign a unique ID number or a unique initial value to each instance of a class.
Subsection14.6.6The ClerkClass
Figure14.6.10.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 simulation, the only variable in its internal state will be a reference to the TakeANumber object (Figure 14.6.10). 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 Listing 14.6.11. 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.
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 get them all started (Listing 14.6.12). Notice that the Customers and the Clerk are each passed a reference to the shared TakeANumber gadget.
public class Bakery {
public static void main(String args[]) {
System.out.println("Starting clerk and customer threads");
TakeANumber numberGadget = new TakeANumber();
Clerk clerk = new Clerk(numberGadget);
clerk.start();
for (int k = 0; k < 5; k++) {
Customer customer = new Customer(numberGadget);
customer.start();
}
} // main()
} // Bakery
Listing14.6.12.Definition of the Bakery class.
Subsection14.6.8Problem: Nonexistent Customers
Now that we have designed and implemented the classes, let’s run several experiments to test that everything works as intended. Except for the synchronizednextNumber() 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 coded, it will generate five customers and the clerk will serve all of them. But we get something like the following output:
Our current solution violates an important real-world constraint: You can’t serve customers before they enter the line! How can we ensure that 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 in which the clerk can see customers waiting in line. We can make the following modification to Clerk.run():
public void run() {
while (true) {
try {
sleep((int)(Math.random() * 50));
if (takeANumber.customerWaiting())
System.out.println("Clerk serving ticket "
+ takeANumber.nextCustomer());
} catch (InterruptedException e) {
System.out.println("Exception " + e.getMessage());
}
} // while
} // run()
And we add the following method to TakeANumber(Figure 14.6.13):
public boolean customerWaiting() {
return next > serving;
}
Figure14.6.13.The revised TakeANumber class.
In other words, the Clerk won’t serve a customer unless there are customers waiting—that is, unless next is greater than serving. Given these changes, we get the following type of output when we run the simulation:
This example illustrates that when application design involves cooperating threads, the algorithm used must ensure the proper cooperation and coordination among the threads.
When two or more threads must behave cooperatively, their interaction must be carefully coordinated by the algorithm.
Subsection14.6.9Problem: Critical Sections
It is easy to forget that thread behavior is asynchronous. You can’t predict when a thread might be interrupted or might have to give up the CPU to another thread. In designing applications that involve cooperating 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:
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:
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 interrupted in such a way that it invalidates the simulation’s output. A method that displays the simulation’s state should be designed so that once a thread begins reporting its state, that thread will be allowed to finish 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 interrupted 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.
Subsection14.6.10Creating a Critical Section
The correct way to address this problem is to treat the reporting of the customer’s state as a critical section. As we saw earlier when we discussed the concept of a monitor, a synchronized method within a shared object 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 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 (Listing 14.6.15). In this version all of the methods are synchronized, so all the actions of the TakeANumber object are treated as critical sections.
public class TakeANumber {
private int next = 0; // Next place in line
private int serving = 0; // Next customer to serve
public synchronized int nextNumber(int custId) {
next = next + 1;
System.out.println( "Customer " + custId + " takes ticket " + next );
return next;
} // nextNumber()
public synchronized int nextCustomer() {
++serving;
System.out.println(" Clerk serving ticket " + serving );
return serving;
} // nextCustomer()
public synchronized boolean customerWaiting() {
return next > serving;
} // customerWaiting()
} // TakeANumber
Listing14.6.15.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.6.15. 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:
public void run() {
while (true) {
try {
sleep( (int)(Math.random() * 1000));
if (takeANumber.customerWaiting())
takeANumber.nextCustomer();
} catch (InterruptedException e) {
System.out.println("Exception: "+e.getMessage());
}
} // while
} // run()
Rather than printing their numbers, these methods now just call the appropriate methods in TakeANumber. Given these design changes, our simulation now produces the following correct output:
The lesson to be learned from this is that in designing multithreaded programs, 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.”
Principle14.6.16.EFFECTIVE DESIGN: The Thread Coordination Principle.
Use critical sections to coordinate the behavior of cooperating threads. By designating certain methods as synchronized, you can ensure their mutually exclusive access. Once a thread starts a synchronized method, no other thread will be able to execute the method until the first thread is finished.
In a multithreaded application, the classes and methods should be designed so that undesirable interrupts will not affect the correctness of the algorithm.
Java’s monitor mechanism will ensure that while one thread is executing a synchronized method, no other thread can gain access to it. Even if the first thread is interrupted, when it resumes execution again it will be allowed to finish the synchronized method before other threads can access synchronized methods in that object.
ExercisesSelf-Study Exercise
1.Critical Sections.
Given the changes we’ve described, the bakery simulation 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.)
Subsection14.6.11The Busy-Waiting Problem
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 Customer s and Clerk in this bakery simulation.
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:
public void run() {
while (true) {
try {
sleep( (int)(Math.random() * 1000));
if (takeANumber.customerWaiting())
takeANumber.nextCustomer();
} catch (InterruptedException e) {
System.out.println("Exception: " + e.getMessage());
}
} // while
} // run()
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.
Subsection14.6.12The wait/notify Mechanism
So, let’s use Java’s wait/notify mechanism to eliminate busy waiting from our simulation. As noted in Figure 14.4.1, 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:
public synchronized int nextNumber( int custId) {
next = next + 1;
System.out.println("Customer " + custId + " takes ticket " + next);
notify();
return next;
}
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
public void run() {
while (true) {
try {
sleep((int)(Math.random() * 1000));
takeANumber.nextCustomer();
} catch (InterruptedException e) {
System.out.println("Exception: "+ e.getMessage());
}
} // while
} // run()
The Clerk thread may be forced to wait when it calls the nextCustomer method.
Figure14.6.18.The revised TakeANumber class.
Because we no longer need the customerWaiting() method, we end up with the new definition of TakeANumber shown in Figure 14.6.18 and Listing 14.6.19.
public class TakeANumber {
private int next = 0;
private int serving = 0;
public synchronized int nextNumber(int custId) {
next = next + 1;
System.out.println( "Customer " + custId + " takes ticket " + next);
notify();
return next;
} // nextNumber()
public synchronized int nextCustomer() {
try {
while (next <= serving) {
System.out.println(" Clerk waiting ");
wait();
}
} catch(InterruptedException e) {
System.out.println("Exception " + e.getMessage());
} finally {
++serving;
System.out.println(" Clerk serving ticket " + serving);
return serving;
}
} // nextCustomer()
} // TakeANumber
Listing14.6.19.The TakeANumber class, Version 3.
Given this version of the program, the following kind of output will be generated:
The producer/consumer model is a useful design for coordinating the wait/notify interaction.
ExercisesSelf-Study Exercise
1.Busy Waiting.
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.
Subsection14.6.13The wait/notifyMechanism
There are a number of important restrictions that must be observed when 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.
Principle14.6.22.DEBUGGING TIP: Wait/Notify.
It’s easy to forget that the wait() and notify() methods can only be used within synchronized methods.
