The local process END denotes the state in which a process successfully terminates. A process engages in no further actions after END. In this respect it has the same semantics as STOP. However, STOP denotes a state in which a process has halted prematurely, usually due to communication deadlock. In earlier chapters, to simplify presentation, we used STOP to indicate termination of a process. It would be more precise to replace these uses of STOP with END. With the introduction of a state describing successful termination, the need to use STOP explicitly in process description largely disappears. Figure 13.1 depicts an example of a sequential process together with its LTS, where E is used to denote END.

Figure 13.1. Sequential process BOMB.

If we define a process SKIP = END then P;SKIP ≡ P and SKIP;P ≡ P. A sequential composition in FSP always takes the form:

SP1;SP2;..SPn;LP

where SP1,.., SPn are sequential processes and LP is a local process. A sequential composition can appear anywhere in the definition of a primitive process that a local process reference can appear (for example, processes P123 and LOOP in Figure 13.2).

Figure 13.2. Sequential composition LOOP.

Sequential composition can be used in a recursive context as in Figure 13.3, where process R is defined as the sequential composition of sequential processes R(I) for values of I from 0 to 2 and the local process END when I=3.

Figure 13.3. Sequential composition and recursion.

Figure 13.4. Parallel composition of sequential processes.

Figure 13.4 gives an example of parallel composition of sequential processes. Note that a composite process that terminates can appear in the definition of a primitive process.

While a reachable STOP state is a safety violation resulting in the LTSA generating a counter example trace, a reachable END state is not a safety violation. However, a trace to a reachable END state will be generated during progress analysis since the END state violates all progress properties.

To verify that a program using this translation satisfies the required safety and progress properties, we must model the behavior of wait(), notify() and notifyAll(). We can then rigorously check the use of notify() versus notifyAll(). A model for the interaction of these methods is developed in the following. Firstly, we define a process ELEMENT to manage the BLOCKED state of each thread that accesses a monitor.

ELEMENT
         = (wait -> BLOCKED | unblockAll -> ELEMENT),
       BLOCKED
         = ({unblock,unblockAll} -> UNBLOCK),
       UNBLOCK
         = (endwait -> ELEMENT).

The wait action, representing a call to wait(), puts the process into the BLOCKED state. Then either an unblock action caused by a notify() or an unblockAll action caused by a notifyAll() causes the process to move to UNBLOCK and signal the return of the wait() method by the endwait action. We will deal with the way that the monitor lock is released and acquired by wait() later.

The CONTROL process manages how notify and notifyAll actions, representing the eponymous Java methods, cause unblock and unblockAll actions:

CONTROL = EMPTY,
       EMPTY   = (wait -> WAIT[1]

                 | {notifyAll,notify} -> EMPTY
                 ),
       WAIT[i:1..Nthread]
               = (when (i<Nthread)  wait -> WAIT[i+1]
                 |notifyAll -> unblockAll -> EMPTY

Since we can only check systems with a finite set of states, we must define a static set of identifiers Threads to represent the set of threads that can potentially access a monitor object. The cardinality of this set is defined by the constant Nthread. The CONTROL process maintains a count of the number of processes in the BLOCKED state. If there are no blocked processes then notify and notifyAll have no effect. If there are many blocked processes then a notify action unblocks any one of them. The set of threads waiting on a monitor and the effect of the wait(), notify() and notifyAll() methods are modeled by the composition:

const Nthread  = 3       //cardinality of Threads
set   Threads  = {a,b,c} //set of thread indentifiers
set   SyncOps  = {notify,notifyAll,wait}

||WAITSET
      = (Threads:ELEMENT || Threads::CONTROL)
        /{unblockAll/Threads.unblockAll}.

The composition defines an ELEMENT process for each thread identifier in the set Threads. The CONTROL process is shared by all the threads in this set. The relabeling ensures that when any thread calls notifyAll(), then all waiting threads are unblocked. The behavior of WAITSET is best illustrated using the animation facilities of LTSA.

Figure 13.5 shows a trace in which thread b calls wait, then thread a calls wait. A call by thread c to notify unblocks thread a. Note that while thread b was blocked before a, it is a that is unblocked first. In other words, the model does not assume that blocked threads are held in a FIFO queue, although many Java Virtual Machines implement thread blocking this way. The Java Language Specification specifies only that blocked threads are held in a set and consequently may be unblocked in any order by a sequence of notifications. An implementation that assumes FIFO blocking may not work correctly on a LIFO implementation. The WAITSET model permits all possible unblocking orders and consequently, when we use it in verification, it ensures that if an implementation model is correct, it is correct for all possible orders of blocking/unblocking actions.

Figure 13.5. WAITSET trace for notify.

Figure 13.6. WAITSET trace for notifyAll.

Figure 13.6 illustrates the behavior for notifyAll when threads a and b are blocked.

Variables are modeled in exactly the same way as presented in Chapter 4. However, for convenience, we add actions to model incrementing and decrementing integer variables. An integer variable is modeled as follows:

const Imax = 5  // a maximum value that variable can take
range Int  = 0..Imax
set   VarAlpha = {read[Int],write[Int],inc,dec}

VAR(Init=0)= VAR[Init],
VAR[v:Int] = (read[v]     ->VAR[v]       // v
             |inc         ->VAR[v+1]     // ++v
             |dec         ->VAR[v-1]     // --v
             |write[c:Int]->VAR[c]       // v = c
             ).

A boolean variable is modeled by:

const False = 0
const True  = 1
range Bool  = False..True
set   BoolAlpha = {read[Bool],write[Bool]}

BOOLVAR(Init=False) = BOOLVAR[Init],
BOOLVAR[b:Bool]     = (read[b]      ->BOOLVAR[b]  // b
                      |write[c:Bool]->BOOLVAR[c]  // b = c
                      ).

In Chapter 4, we noted that synchronized methods acquire the monitor lock before accessing the variables of a monitor object and release the lock on exit. We will use the same simple model of a lock used in Chapter 4, ignoring the detail that locks in Java support recursive locking:

set LockOps = {acquire,release}
LOCK = (acquire -> release ->LOCK).

We can now model the state of a monitor by the set of processes that represent its wait set, lock and variables. For example, the state for a monitor M that encapsulates a single boolean variable cond is modeled as follows:

||Mstate = (Threads::LOCK  || WAITSET
                  || Threads::(cond:BOOLVAR)
                  ).

The definition of the Java wait() operation in Chapter 5 requires that a waiting thread releases the synchronization lock. We model this as a sequential process that releases the lock when it blocks and acquires it again when it unblocks and finishes waiting.

WAIT = (wait ->release ->endwait ->acquire ->END).

In Java, the notification and waiting operations are only valid when the thread calling these operations holds the lock for the monitor object on which the operations are invoked. The following safety property checks that this is the case in the implementation models we construct:

property SAFEMON
   = ([t:Threads].acquire -> HELDBY[t]),
HELDBY[t:Threads]
   = ([t].{notify,notifyAll,wait} -> HELDBY[t]
     |[t].release -> SAFEMON
     ).

A synchronized method of the form:

synchronized void act()throws InterruptedException {
      while (!cond) wait();
      // modify monitor data
      notifyAll()
}

can now be modeled by the following FSP sequential process. As in Chapter 4, alphabet extension ensures that only intended interactions occur since it is usually the case that a process modeling a synchronized method will only use a subset of the data access actions (in this case only read is used on the boolean condition) and synchronization actions (in this case only notifyAll is used).

ACT   // act()
        = (acquire -> WHILE),     // monitor entry– acquire lock
      WHILE
        = (cond.read[b:Bool] ->   // while (!cond) wait();
          if !b then WAIT;WHILE else CONTINUE
          ),

      CONTINUE
        = (                       // modify monitor data
          notifyAll               // notifyAll()
          -> release              // monitor exit– release lock
          -> END
        ) + {SyncOps, LockOps, cond.BoolAlpha}.

Note that with the above constructions, while we can now model monitors in some detail, we are still ignoring the effect of InterruptException occurrence and handling. In the book, we have only used this mechanism to terminate all the threads that constitute the concurrent Java program. At the end of this chapter we discuss the problems that can arise if only a subset of threads is terminated in this way.

We can now translate the put() and get() methods of Program 13.1 into FSP into a reasonably straightforward way. Since we have abstracted from the details of storing items in the buffer, we replace the actions to place an item in the buffer with the action put and the actions to remove an item with the action get.

public void put(Object o)
   throws InterruptedException; //put object into buffer
public Object get()
   throws InterruptedException; //get object from buffer
}

class BufferImpl implements Buffer {
  protected Object[] buf;

protected int in = 0;
protected int out= 0;
protected int count= 0;
protected int size;

BufferImpl(int size) {
  this.size = size; buf = new Object[size];
}

public synchronized void put(Object o)
          throws InterruptedException {
  while(count==size) wait();
  buf[in] = o;
  ++count;
  in=(in+1) %size;
  notify();
}

public synchronized Object get()
          throws InterruptedException {
  while (count==0) wait();
  Object o =buf[out];
  buf[out]=null;
  --count;
  out=(out+1) %size;
  notify();
  return (o);
  }
}

/*  put method */
     PUT
       = (acquire -> WHILE),
     WHILE
       = (count.read[v:Int] ->   // while (count == size) wait();
          if v==Size then WAIT;WHILE else CONTINUE
         ),
     CONTINUE
       = (put                    // buf$,$[in] = o; in=(in+1) %size;
          -> count.inc           // ++count;
          -> notify -> release -> END
         ) + BufferAlpha.

/* get method */
     GET
       = (acquire -> WHILE),
     WHILE
       = (count.read[v:Int] ->   // while (count == 0 ) wait()
           if v==0 then WAIT;WHILE else CONTINUE
         ),
     CONTINUE
         = (get                // Object[o] = buf$,$[out]; buf$,$[out]=null;
          -> count.dec         // --count;
          -> notify -> release -> END
          ) + BufferAlpha.

To investigate the properties of the bounded buffer implementation, we model systems consisting of one or more producer threads and one or more consumer threads. The producer threads call put() and the consumer threads call get () as shown below.

PRODUCER = PUT;PRODUCER.
     CONSUMER = GET;CONSUMER.

We noted in section 13.2.1 that we must explicitly define the set of threads that will access the monitor being modeled. For the bounded buffer example, we have a set of producer threads, which put items into the buffer, and a set of consumer threads, which take items out of the buffer, identified as follows:

const Nprod = 2                  // #producers
const Ncons = 2                  // #consumers
set   Prod  = {prod[1..Nprod]}   // producer threads
set   Cons  = {cons[1..Ncons]}   // consumer threads

const Nthread  = Nprod + Ncons
set   Threads  = {Prod,Cons}

The producer and consumer processes are composed with the processes modeling the buffer monitor by:

||ProdCons = (Prod:PRODUCER || Cons:CONSUMER
                   || BUFFERMON).

To verify our implementation model of the bounded buffer, we need to show that it satisfies the same safety and progress properties as the design model. However, the bounded buffer design model was specified in Chapter 5, which preceded the discussion of how to specify properties. Consequently, we simply inspected the LTS graph for the model to see that it had the required synchronization behavior. The LTS of the implementation model is much too large to verify by inspection. How then do we proceed? The answer with respect to safety is to use the design model itself as a safety property and check that the implementation satisfies this property. In other words, we check that the implementation cannot produce any executions that are not specified by the design. Clearly, this is with respect to actions that are common to the implementation and design models – the put and get actions. The property below is the same BUFFER process shown in Figure 5.11, with the addition of a relabeling part that takes account of multiple producer and consumer processes.

property
      BUFFER = COUNT[0],
      COUNT[i:0..Size]
           = (when (i<Size) put->COUNT[i+1]
           |when (i>0)    get->COUNT[i-1]
           )/{Prod.put/put,Cons.get/get}.

The LTS for this property with two producer processes, two consumer processes and a buffer with two slots (Size = 2) is shown in Figure 13.7.

We are now in a position to perform a safety analysis of the bounded buffer implementation model using the composition:

||ProdConsSafety = (ProdCons || BUFFER).

With two producer processes (Nprod=2), two consumer processes (Ncons=2) and a buffer with two slots (Size=2), safety analysis by the LTSA reveals no property violations or deadlocks. In this situation, the implementation satisfies the design. However, safety analysis with two producer processes (Nprod=2), two consumer processes (Ncons=2) and a buffer with only one slot (Size=1) reveals the following deadlock:

Trace to DEADLOCK:
       cons.1.acquire
       cons.1.count.read.0

Figure 13.7. LTS for property BUFFER.

cons.1.wait          // consumer 1 blocked
       cons.1.release
       cons.2.acquire
       cons.2.count.read.0
       cons.2.wait          // consumer 2 blocked
       cons.2.release
       prod.1.acquire
       prod.1.count.read.0
       prod.1.put           // producer 1 inserts item
       prod.1.count.inc
       prod.1.notify        // producer 1 notifies item available
       prod.1.release
       prod.1.acquire
       prod.1.count.read.1
       cons.1.unblock       // consumer 1 unblocked by notify
       prod.1.wait          // producer 1 blocks trying to insert 2nd item
       prod.1.release
       prod.2.acquire
       prod.2.count.read.1
       prod.2.wait          // producer 2 blocks trying to insert item
       prod.2.release
       cons.1.endwait
       cons.1.acquire
       cons.1.count.read.1

cons.1.get           // consumer 1 gets item
       cons.1.count.dec
       cons.1.notify        // consumer 1 notifies space available
       cons.1.release
       cons.1.acquire
       cons.1.count.read.0
       cons.2.unblock       // consumer 2 unblocked by notify
       cons.1.wait
       cons.1.release
       cons.2.endwait
       cons.2.acquire
       cons.2.count.read.0
       cons.2.wait          // consumer 2 blocks since buffer is empty
       cons.2.release

The deadlock occurs because at the point that the consumer process calls notify to indicate that a space is available in the buffer, the wait set includes the second consumer process as well as both the producer processes. The consumer is unblocked and finds that the buffer is empty and goes back to waiting. At this point no further progress can be made and the system deadlocks since neither of the producer processes can run. This deadlock occurs if either the number of producer processes or the number of consumer processes is greater than the number of slots in the buffer. Clearly in this situation, the implementation given in the first printing of Chapter 5 was incorrect!

To correct the bounded buffer program of Chapter 5, to handle the situation of a greater number of producer or consumer threads than buffer slots, we need to replace the calls to notify() with calls to notifyAll(). This unblocks both consumer and the producer threads, allowing an insertion or removal to occur. Replacing the corresponding actions in the implementation model removes the deadlock and verifies that the Java program is now correct.

The lesson here is that it is always safer to use notifyAll() unless it can be rigorously shown that notify() works correctly. We should have followed our own advice in Chapter 5! The general rule is that notify() should only be used if at most one thread can benefit from the change of state being signaled and it can be guaranteed that the notification will go to a thread that is waiting for that particular state change. An implementation model is a good way of doing this.

The corrected model satisfies the following progress properties, which assert lack of starvation for put and get actions:

progress PUT[i:1..Nprod] = {prod[i].put}
progress GET[i:1..Ncons] = {cons[i].get}

The next step in verifying an implementation is to derive an FSP sequential process for each monitor method. These processes for acquireRead(), releaseRead(), acquireWrite() and releaseWrite() are listed below.

/*
     * acquireRead() method
     */
     ACQUIREREAD
       = (acquire -> WHILE),
     WHILE                   // while (writing || waitingW$>$0) wait();
       = (writing.read[v:Bool] -> waitingW.read[u:Int] ->

if (v || u>0) then WAIT;WHILE else CONTINUE
         ),
     CONTINUE
       = (acquireRead
          -> readers.inc           // ++readers;
          -> release -> END
          ) + ReadWriteAlpha.

     /*
     * releaseRead() method
     */
     RELEASEREAD
       = (acquire -> releaseRead
         -> readers.dec            // --readers;
         -> readers.read[v:Int] -> // if (readers==0) notify();
            if (v==0) then (notify -> CONTINUE) else CONTINUE
          ),
     CONTINUE
       = (release -> END) + ReadWriteAlpha.

     /*
     * acquireWrite() method
     */
     ACQUIREWRITE               // ++waitingW;
       = (acquire -> waitingW.inc -> WHILE),
     WHILE                      // while (readers$>$0 || writing) wait();
       = (writing.read[b:Bool] -> readers.read[v:Int]->
          if (v>0 || b) then WAIT;WHILE else CONTINUE
         ),
     CONTINUE
       = (acquireWrite
          -> waitingW.dec        // --waitingW;
          -> writing.write[True] // writing = true;
          -> release -> END
         )+ ReadWriteAlpha.

     /*
     * releaseWrite() method
     */
     RELEASEWRITE
        = (acquire -> releaseWrite
          -> writing.write[False] // writing = false;
          -> notifyAll            // notifyAll();
          -> release-> END
          ) + ReadWriteAlpha.

We have included the actions acquireRead, acquireWrite, releaseRead and releaseWrite in the model, which correspond to the actions in the design model of Chapter 7.

READER  = (acquireRead.call -> ACQUIREREAD;READING),
     READING = (releaseRead.call -> RELEASEREAD;READER).

     WRITER  = (acquireWrite.call -> ACQUIREWRITE;WRITING),
     WRITING = (releaseWrite.call -> RELEASEWRITE;WRITER).

To verify that the implementation model satisfies the desired safety properties, we use the safety property RW_SAFE originally specified in section 7.5.1 to check the correct behavior of the design model.

property SAFE_RW
   = (acquireRead -> READING[1]
     |acquireWrite->WRITING
     ),
READING[i:1..Nread]
   = (acquireRead -> READING[i+1]
     |when(i>1)  releaseRead -> READING[i-1]
     |when(i==1) releaseRead -> SAFE_RW
     ),
WRITING  = (releaseWrite -> SAFE_RW).

The system we perform safety analysis on consists of the reader and writer threads, the monitor state and the safety property as shown below:

||RWSYS = (Read:READER || Write:WRITER
               || RWPRIORMON
               || Threads::SAFE_RW
               ).

Safety analysis detects the following deadlock:

Trace to DEADLOCK:
           reader.1.acquireRead.call
           reader.1.acquire
           reader.1.writing.read.0
           reader.1.waitingW.read.0
           reader.1.acquireRead
           reader.1.readers.inc
           reader.1.release         // reader 1 acquires RW lock
           reader.1.releaseRead.call
           reader.2.acquireRead.call
           writer.1.acquireWrite.call
           writer.1.acquire
           writer.1.waitingW.inc
           writer.1.writing.read.0
           writer.1.readers.read.1
           writer.1.wait  // writer 1 blocked as reader has RW lock
           writer.1.release
           reader.2.acquire
           reader.2.writing.read.0
           reader.2.waitingW.read.1
           reader.2.wait  // reader 2 blocked as writer 1 waiting
           reader.2.release
           writer.2.acquireWrite.call
           writer.2.acquire
           writer.2.waitingW.inc
           writer.2.writing.read.0
           writer.2.readers.read.1
           writer.2.wait     // writer 2 blocked as reader has RW lock
           writer.2.release
           reader.1.acquire
           reader.1.releaseRead
           reader.1.readers.dec
           reader.1.readers.read.0
           reader.1.notify   // reader 1 releases RW lock & notifies
           writer.2.release
           reader.1.release
           reader.1.acquireRead.call
           reader.1.acquire
           reader.1.writing.read.0
           reader.1.waitingW.read.2
           reader.2.unblock  // reader 2 unblocked by notify
           reader.1.wait

reader.1.release
           reader.2.endwait
           reader.2.acquire
           reader.2.writing.read.0
           reader.2.waitingW.read.2
           reader.2.wait     // reader 2 blocks as writers waiting
           reader.2.release

The deadlock happens because the notify operation performed by Reader 1 when it releases the read–write lock unblocks another Reader rather than a Writer. This unblocked Reader subsequently blocks again since there are Writers waiting. The solution is again to use a notifyAll to awake all waiting threads and thus permit a Writer to run. Changing the notify action to notifyAll in the RELEASEREAD part of the model and rerunning the safety analysis confirms that the deadlock does not occur and that the implementation model satisfies the safety property.

Why did we not observe this deadlock in the actual implementation of Read-WritePriority when running the demonstration applet? The reason is quite subtle. In most Java Virtual Machines, the set of threads waiting on notification is implemented as a first-in-first-out (FIFO) queue. With this queuing discipline, the deadlock cannot occur as for the second Reader to block, a Writer must have previously blocked. This Writer will be unblocked by the notification when the first Reader releases the read–write lock and, consequently, the deadlock does not occur. However, although the implementation works for some JVMs, it is not guaranteed to work on all JVMs since, as noted earlier, the Java Language Specification specifies only that blocked threads are held in a set. Our implementation would exhibit the deadlock on a JVM that used a stack for the wait set. Consequently, the implementation is clearly erroneous and the notify() in the releaseRead() method should be replaced with notifyAll(). Again the lesson is that notify() should only be used with extreme care! However, it should be noted that the use of notify() in the ReadWriteSafe version of the read–write lock is correct since it is not possible in that implementation to have both Readers and Writers waiting simultaneously.

progress WRITE[i:1..Nwrite] = writer[i].acquireWrite
progress READ [i:1..Nwrite] = reader[i].acquireRead

||RWPROGTEST  = RWSYS > {Read.releaseRead.call,
                                 Write.releaseWrite.call}.