Threads and Concurrent Programming

Problem: 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:

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

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 section 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.

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() uninterruptible 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.

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:

and from the run() method in Clerk:

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.”

In a multithreaded application, the classes and methods should be designed 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 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.)