Chapter 4: Shared Objects and Mutual Exclusion

In the last chapter, we discussed the execution of multiple processes on one or more processors, modeling concurrent execution by interleaving and executing multiple concurrent threads in a Java program. We explained how process interaction is modeled using shared atomic actions, but not how real processes or threads interact. In this chapter, we turn to the issues involved in constructing concurrent programs in which threads interact to communicate and cooperate.

The simplest way for two or more threads in a Java program to interact is via an object whose methods can be invoked by the set of threads. This shared object’s state can of course be observed and modified by its methods. Consequently, two threads can communicate by one thread writing the state of the shared object and the other thread reading that state. Similarly, a set of threads may cooperate to update some information encapsulated in a shared object. Unfortunately, as we will explain, this simple scheme of interaction does not work.

4.1 Interference

We have seen that the execution of the instructions from a set of threads can be interleaved in an arbitrary fashion. This interleaving can result in incorrect updates to the state of a shared object. The phenomenon is known as interference. The problem of interference, and how to deal with it, is the main topic of this chapter.

4.1.1 Ornamental Garden Problem

To focus on the issues of thread interaction, we use an example known as the problem of the Ornamental Garden, due to Alan Burns and Geoff Davies (1993). The problem is stated as follows. A large ornamental garden is open to members of the public who can enter through either of two turnstiles as depicted in Figure 4.1. The management wants to determine how many people there are in the garden at any one time. They require a computer system to provide this information.

Figure 4.1: Ornamental Garden.

To simplify the problem further, we consider a garden that people are allowed to enter but never leave! The concurrent program to implement the population count required by the management of the ornamental garden consists of two concurrent threads and a shared counter object. Each thread controls a turnstile and increments the shared counter when a person passes through the turnstile. The class diagram for the program is depicted in Figure 4.2.

Figure 4.2: Ornamental Garden class diagram.

The Counter object and Turnstile threads are created by the go() method of the Garden applet shown below in which eastD, westD and counterD are objects of the same NumberCanvas class that we used in Chapter 2.

 private void go() {   counter = new Counter(counterD);   west = new Turnstile(westD,counter);   east = new Turnstile(eastD,counter);   west.start();   east.start(); }

The Turnstile thread shown in Program 4.1 simulates the periodic arrival of a visitor to the garden by sleeping for half a second and then invoking the increment() method of the counter. After the arrival of Garden.MAX visitors, the run() method exits and consequently, the thread terminates.

Program 4.1: Turnstile class.

 class Turnstile extends Thread {   NumberCanvas display;   Counter people;   Turnstile(NumberCanvas n,Counter c)     { display = n; people = c; }   public void run() {     try{       display.setvalue(0);       for (int i=1;i<=Garden.MAX;i++){         Thread.sleep(500); //0.5 second between arrivals         display.setvalue(i);         people.increment();       }     } catch (InterruptedException e) {}   } }

The remaining class Counter is more complex than is strictly necessary. The additional complexity is to ensure that the program demonstrates the effects of interference independently of any particular implementation of Java. To ensure that the program demonstrates the desired effect, Program 4.2 ensures that arbitrary interleaving occurs.

Program 4.2: Counter class.

 class Counter {   int value=0;   NumberCanvas display;   Counter(NumberCanvas n) {     display=n;     display.setvalue(value);   }   void increment() {     int temp = value;    //read value     Simulate.HWinterrupt();     value=temp+1;       //write value     display.setvalue(value);   } }

It does this by using the class Simulate which provides the method HWinterrupt(). The method, when called, sometimes causes a thread switch by calling Thread.yield() and sometimes omits the call leaving the current thread running. The idea is to simulate a hardware interrupt which can occur at arbitrary times between reading and writing to the shared Counter when performing an increment. Thus thread switches can occur at arbitrary times as discussed at the beginning of the last chapter. The Simulate class is defined by the following code:

 class Simulate {     public static void HWinterrupt() {         if (Math.random()< 0.5) Thread.yield();     } }

The problem with the Ornamental Garden program is illustrated by the screen shot of the running applet in Figure 4.3. When the Go button is pressed, the Garden.go() method is invoked to create a Counter object and the two Turnstile threads. Each thread then increments the counter exactly Garden.MAX times and then terminates. The value of the constant Garden.MAX has been set to 20, consequently, when both Turnstile threads terminate, the counter display should register that 40 people have entered the garden. In fact, as can be seen from Figure 4.3, the counter registers only 31. Where have the missing people gone? Why have nine increments to the counter been lost? To investigate why, we develop a model of the Ornamental Garden problem.

Figure 4.3: Garden display.

4.1.2 Ornamental Garden Model

In the remainder of the book, we generally model each object or set of objects as an FSP process. However, to find out why the Ornamental Garden program operates incorrectly, we must model it at the level of store accesses. Consequently, the model includes a VAR process that describes the read and write accesses to a store location. This store location is the value variable encapsulated by the people instance of the Counter class (Program 4.2). The complete model is described in Figure 4.4. The reader may be surprised that there is no explicit mention of an increment action. Instead, increment is modeled using read and write actions by the definition INCREMENT inside TURNSTILE. Each thread object, east and west, has its own copy of the read and write actions that make up the increment operation or procedure. This models what happens in the actual Java program since methods are re-entrant and thus the instructions which constitute a method may be interleaved on behalf of the threads executing the method concurrently. In other words, method activations are not atomic actions. The LTS for the TURNSTILE is given in Figure 4.5.

Figure 4.4: Ornamental Garden model.

Figure 4.5: LTS for TURNSTILE.

The alphabet of the process VAR has been declared explicitly as the set in Figure 4.4. We have not used set constants before. A set constant can be used wherever we previously declared sets of action labels explicitly. Sets are simply a way of abbreviating model descriptions. VarAlpha is declared as follows:

 set VarAlpha = {value.{read[T],write[T]} }

The alphabet for the TURNSTILE process is extended with this set using the alphabet extension construct +{...}. This is to ensure that there are no unintended free actions. For example, if a VAR write of a particular value is not shared with another process then it can occur autonomously. A TURNSTILE process never engages in the action value.write[0] since it always increments the value it reads. However, since this action is included in the alphabet extension of TURNSTILE, although it is not used in the process definition, it is prevented from occurring autonomously. The TURNSTILE process is slightly different from its Java implementation in that it does not run for a fixed number of arrivals but may end at any point. However, it cannot end in the middle of updating the shared variable value. The end action is only accepted as an alternative to an arrive action. Furthermore, TURNSTILE is defined as recursive so that analysis (discussed below) will not report spurious deadlocks as would be the case if we had used STOP after the action end. Note that the shared variable VAR is not only shared by the turnstiles east and west, but also by display which is used for checking purposes.

Having developed a model of the Ornamental Garden program, in some detail, what can we do with it? Well, we can animate the model using the LTSA tool to produce action traces for particular input scenarios. For example, the trace in Figure 4.6 illustrates the case where there is an east arrival and a west arrival and then end occurs.

Figure 4.6: An Animator trace for the Ornamental Garden.

The trace is correct in that after two arrivals the counter has a value of two. However, we might try many input scenarios before finding out what is wrong with the program. To automate the search for the error, we combine a TEST process with the existing model that signals when an erroneous action trace occurs. The process is defined below:

 TEST       = TEST[0], TEST[v:T]  =      (when (v<N){east.arrive,west.arrive}->TEST[v+1]      |end->CHECK[v]      ), CHECK[v:T] =     (display.value.read[u:T] ->        (when (u==v) right -> TEST[v]        |when (u!=v) wrong -> ERROR        )     )+{display.VarAlpha}.

The process counts the total number of east.arrive and west.arrive actions. When an end action occurs, and consequently the shared variable updates are complete, it checks that the value stored is the same as the total number of arrival events. If not, an error is declared by moving into the ERROR state. ERROR (like STOP) is a predefined FSP local process (or state). It is always numbered -1 in the equivalent LTS. Again, alphabet extension is used to ensure that no actions prefixed by display can occur autonomously.

The TEST process is combined with the existing model as follows:

 ||TESTGARDEN = (GARDEN || TEST).

We can now request the LTSA analysis tool to perform an exhaustive search to see if the ERROR state in TEST can be reached and if so to produce an example trace. The trace produced is:

 Trace to property violation in TEST:      go      east.arrive      east.value.read.0      west.arrive      west.value.read.0      east.value.write.1      west.value.write.1      end      display.value.read.1      wrong

This trace clearly indicates the problem with the original Java program. Increments are lost because the shared variable is not updated atomically. Thus both east and west turnstiles read the value 0 and write 1. If the east increment finished before the west increment started or vice versa, then the result would be two (as in the previous trace).

Destructive update, caused by the arbitrary interleaving of read and write actions, is termed interference.

In real concurrent programs, interference bugs are extremely difficult to locate. They occur infrequently, perhaps due to some specific combination of device interrupts and application I/O requests. They may not be found even after extensive testing. We had to include a simulated interrupt in the example program to demonstrate the error. Without the simulated interrupt, the program is still incorrect, although the erroneous behavior may not manifest itself on all systems.

The general solution to the problem of interference is to give methods that access a shared object mutually exclusive access to that object. This ensures that an update is not interrupted by concurrent updates. As we see in the following sections, methods with mutually exclusive access can be modeled as atomic actions.