Section 14.6. Case Study: Cooperating Threads
14.6. Case Study: Cooperating ThreadsFor 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 has not 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.
Producer and consumer threads 14.6.1. Problem StatementTo 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 the take-a-number devices 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.
Simulating a waiting line 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 illustrate the various issues involved in trying to coordinate threads, we will develop more than one version of the program. Problem DecompositionThis simulation will use four classes of objects. Figure 14.17 provides a UML representation of the interactions among the objects. 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 itself a thread. 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:
Figure 14.17. The Bakery creates the Customer and Clerk threads and the TakeANumber gadget. Then Customers request and receive waiting numbers, and the Clerk requests and receives the number of the next customer to serve. |
public 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 class |
Passing a reference to a shared object
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 is 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.
Synchronized methods
Self-Study Exercise
| Exercise 14.9 | What is the analogue to mutual exclusion in the real-world bakery situation? |
14.6.3. 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 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. No other synchronized method can run in an object that is locked. Other threads must wait for the lock to be released before they can execute a synchronized method.
The monitor concept
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.
Mutually exclusive access to a shared object
Java Language Rule: 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 the object's synchronized methods. |
Effective Design: Synchronization
 | In order to restrict access of a method or set of methods to one object at a time (mutual exclusion), declare the methods synchronized. |
A cautionary note here is that a synchronized method blocks access to other synchronized methods, but not 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.
14.6.4. The Customer Class
A Customer thread should model the behavior of taking a number from the TakeANumber gadget. For the sake of the 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 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. As we noted earlier, each Customer also needs a reference to the TakeANumber object, which is passed as a constructor parameter (Fig. 14.20). This leads to the definition of Customer shown in Figure 14.21. 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.
Figure 14.20. The Customer tHRead.
Figure 14.21. Definition of the Customer class, Version 1.
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 class |
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, every 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.
Static (class) variables
Java Language Rule: Static (Class) Variables
| Static variables are associated with the class itself and not with its instances. |
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. |
14.6.5. The Clerk Class
The Clerk thread should simulate the behavior of serving the next customer in line, so it will repeatedly access TakeANumber.nextCustomer() and then serve that customer. For the sake of the simulation, we'll just print a message to indicate which customer is being served. Because there is only one clerk in this simulation, 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.
Figure 14.23. Definition of Clerk, Version 1.
public class Clerk extends Thread { private TakeANumber takeANumber; public Clerk(TakeANumber gadget) { takeANumber = gadget; } public void run() { while (true) { try { sleep( (int)(Math.random() * 50)); System.out.println("Clerk serving ticket" +takeANumber.nextCustomer()); } catch (InterruptedException e) { System.out.println("Exception " + e.getMessage() ); } } // while } // run() } // Clerk class |
14.6.6. 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 get them all started (Fig. 14.24). Note that the Customers and the Clerk are each passed a reference to the shared TakeANumber gadget.
Figure 14.24. Definition of the Bakery class.
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 class |
The main program
Problem: Nonexistent Customers
Now that we have designed and implemented the classes, let's run several experiments to test whether everything works as intended. Except for the synchronized nextNumber() method, we have made little attempt to ensure that the Customer and Clerk threads can work together cooperatively, without violating the real-world constraints that should be satisfied by the simulation. If we run the simulation as presently coded, it will generate five customers and the clerk will serve all of them. But we get something like the following output:
Starting clerk and customer threads Clerk serving ticket 1 Clerk serving ticket 2 Clerk serving ticket 3 Clerk serving ticket 4 Clerk serving ticket 5 Customer 10004 takes ticket 1 Customer 10002 takes ticket 2 Clerk serving ticket 6 Customer 10005 takes ticket 3 Clerk serving ticket 7 Clerk serving ticket 8 Clerk serving ticket 9 Clerk serving ticket 10 Customer 10001 takes ticket 4 Customer 10003 takes ticket 5
Testing and debugging
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 is actually a customer waiting?
Problem: the clerk thread doesn't wait for customer threads
The wrong way to address this issue would be to increase the amount of sleeping the Clerk does between serving customers. This would allow more customer threads to run, so it might seem 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. Thus we 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()
The clerk checks the line
And we add the following method to TakeANumber (Fig. 14.25):
public boolean customerWaiting() { return next > serving; }
Figure 14.25. The revised TakeANumber class.
In other words, the Clerk won't serve a customer unless there are customers waitingthat is, unless next is greater than serving. Given these changes, we get the following type of output when we run the simulation:
Starting clerk and customer threads Customer 10003 takes ticket 1 Clerk serving ticket 1 Customer 10005 takes ticket 2 Clerk serving ticket 2 Customer 10001 takes ticket 3 Clerk serving ticket 3 Customer 10004 takes ticket 4 Clerk serving ticket 4 Customer 10002 takes ticket 5 Clerk serving ticket 5
This example illustrates that when application design involves cooperating threads, the algorithm used must ensure the proper cooperation and coordination among the threads.
Effective Design: Thread Coordination
| When two or more threads must behave cooperatively, their interaction must be carefully coordinated by the algorithm. |
14.6.7. Problem: Critical Sections
It is easy to forget that thread behavior is asynchronous. You can't predict when a thread will be interrupted or may have to give up the CPU to another thread. In designing applications that involve cooperating threads, it's important for the design to incorporate features that guard against problems caused by asynchronicity. To illustrate this problem, consider the following statement from the Customer.run() method:
System.out.println("Customer " + id + " takes ticket " + takeANumber.nextNumber());
Thread interruptions are unpredictable
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 println() into two statements and putting a sleep() between them:
public void run() { try { int myturn = takeANumber.nextNumber(); sleep( (int)(Math.random() * 1000 ) ); System.out.println("Customer " + id + " takes ticket " + myturn); } catch (InterruptedException e) { System.out.println("Exception " + e.getMessage()); } } // run()
If this change is made in the simulation, you might get the following output:
Starting clerk and customer threads Clerk serving ticket 1 Clerk serving ticket 2 Clerk serving ticket 3 Customer 10004 takes ticket 4 Clerk serving ticket 4 Clerk serving ticket 5 Customer 10001 takes ticket 1 Customer 10002 takes ticket 2 Customer 10003 takes ticket 3 Customer 10005 takes ticket 5
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 so designed that once a thread begins reporting its state, it will be allowed to finish reporting before another thread can start reporting its own state. Accurate reporting of a thread's state is a critical element of the simulation's overall integrity.
Problem: an interrupt in a critical section
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 it is very unlikely 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 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 (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.
Figure 14.26. Definition of the TakeANumber class, Version 2. (This item is displayed on page 688 in the print version)
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 class |
Making a critical section uninterruptible
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:
public void run() { try { sleep((int)(Math.random() * 2000)); takeANumber.nextNumber(id); } catch (InterruptedException e) { System.out.println("Exception: "+ e.getMessage()); } } // run()
and from the run() method in Clerk:
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:
Starting clerk and customer threads Customer 10001 takes ticket 1 Clerk serving ticket 1 Customer 10003 takes ticket 2 Customer 10002 takes ticket 3 Clerk serving ticket 2 Customer 10005 takes ticket 4 Customer 10004 takes ticket 5 Clerk serving ticket 3 Clerk serving ticket 4 Clerk serving ticket 5
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."
Preventing undesirable interrupts
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 Programming Tip: Critical Sections
 | 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. |
Self-Study Exercise
| Exercise 14.10 | Given the changes we have 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.) |
14.6.8. Using wait/notify to Coordinate Threads
The examples in the preceding 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.
Busy waiting
As presently designed, the Clerk thread sits in a loop that repeatedly checks whether there is 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 (i.e., consumed) by the clerk.
Producer/consumer
This is only half the producer/consumer relationship because we haven't placed any constraint on the size of the waiting line. There is 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
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 the 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():
public synchronized int nextCustomer() { try { while (next <= serving) wait(); } catch(InterruptedException e) { System.out.println("Exception: " + e.getMessage()); } finally { ++serving; System.out.println(" Clerk serving ticket " + serving); return serving; } }
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 is why we use a while loop here. In effect, the Clerk will wait until there is 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.
A waiting thread gives up the CPU
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 will 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.
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.
Figure 14.27. In the final design of TakeANumber, its methods are synchronized.
Figure 14.28. The TakeANumber class, Version 3.
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 class |
Given this version of the program, the following kind of output will be generated:
Starting clerk and customer threads Customer 10004 takes ticket 1 Customer 10002 takes ticket 2 Clerk serving ticket 1 Clerk serving ticket 2 Customer 10005 takes ticket 3 Customer 10003 takes ticket 4 Clerk serving ticket 3 Customer 10001 takes ticket 5 Clerk serving ticket 4 Clerk serving ticket 5 Clerk waiting
Java Programming Tip: Busy Waiting
| Java's wait/notify mechanism can be used effectively to eliminate busy waiting from a multithreaded application. |
Effective Design: Producer/Consumer
| The producer/consumer model is a useful design for coordinating the wait/notify interaction. |
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:
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.
Wait/notify go into synchronized methods
Debugging Tip: Wait/Notify
 | It's easy to forget that the wait() and notify() methods can only be used within synchronized methods. |
EAN: 2147483647
Pages: 275