Safety properties are specified in FSP by property processes. Syntactically, these are simply FSP processes prefixed by the keyword property. They are composed with a target system to ensure that the specified property holds for that system. The example of Figure 7.2 specifies the property that it is polite to knock before entering a room.

Figure 7.2. property POLITE.

The LTS diagram of Figure 7.2 reveals that in translating a property process, the compiler automatically generates the transitions to the ERROR state. It is easily seen that an enter action before a knock action causes a transition to the ERROR state. In addition, knocking twice is a violation of the POLITE property. It should be noted that in every state of the property process of Figure 7.2, all the actions in its alphabet (enter, knock) are eligible choices. Those that are not part of the behavior allowed by the safety property are transitions to the ERROR state. This is true of all property processes.

The property to check the correct operation of the ACTUATOR of Figure 7.1 is simply:

property SAFE_ACTUATOR
     =(command->respond->SAFE_ACTUATOR).

Property processes may be composed with a system without affecting the correct behavior of that system. In other words, composing a property process with a set of processes does not affect their normal operation. However, if behavior can occur which violates the safety property, then a transition to the ERROR state results. To preserve this transparency of safety properties, property processes must be deterministic. That is they must not contain non-deterministic choices. Experience has shown that this is rarely a restriction in practice.

Thus, if P is composed with S, then traces of actions that are in the alphabet of S and the alphabet of P, must also be valid traces of P, otherwise ERROR is reachable. We can specify that an action or a set of actions should never happen by using alphabet extension. The example of Figure 7.3 asserts that disaster should never happen.

Figure 7.3. property CALM.

Listed below is a slightly modified version of the SEMADEMO model used in section 5.2.1 to show how semaphores are used to ensure mutual exclusion. The modification is to replace the single action critical with the actions enter and exit which model the entry and exit to the critical section in which mutually exclusive access to a shared resource is required.

LOOP =
         (mutex.down->enter->exit->mutex.up->LOOP).

     ||SEMADEMO = (p[1..3]:LOOP
                   ||{p[1..3]}::mutex:SEMAPHORE(1)).

To verify that this system does in fact ensure mutual exclusion, we can specify a mutual exclusion property and compose it with the system as follows:

property MUTEX =
      (p[i:1..3].enter->p[i].exit->MUTEX).

||CHECK = (SEMADEMO || MUTEX).

The safety property MUTEX specifies that when a process enters the critical section (p[i].enter), the same process must exit the critical section (p[i].exit)before another process can enter. The property is not violated in the system as it stands; however, if we change the value with which the semaphore is initialized from one to two (i.e. SEMAPHORE(2)) then safety analysis using LTSA produces the following trace:

Trace to property violation in MUTEX:
          p.1.mutex.down
          p.1.enter
          p.2.mutex.down
          p.2.enter

The trace is clearly a violation of mutual exclusion since two processes have entered the critical section.

In modeling the single-lane bridge, we use the following constant and range definitions:

const N = 3    // number of each type of car
range T = 0..N // type of car count
range ID= 1..N // car identities

The essence of the problem is access to the bridge, so the only events of interest in which a car participates are entering the bridge and leaving the bridge. Consequently, a car is modeled by a process that repeatedly enters and leaves the bridge:

CAR = (enter->exit->CAR).

To model the fact that cars cannot pass each other on the bridge, we require the following processes which constrain the order of the enter and exit actions respectively:

NOPASS1  = C[1], //preserves entry order
     C[i:ID]  = ([i].enter->C[i%N+1]).

     NOPASS2  = C[1], //preserves exit order
     C[i:ID]  = ([i].exit->C[i%N+1]).

     ||CONVOY = ([ID]:CAR||NOPASS1||NOPASS2).

The CONVOY process models a set of cars traveling in the same direction that enter the bridge one after the other and leave the bridge one after the other. However, it does not stop one car exiting the bridge before the next car enters. The behavior of all cars is captured by the following composition:

||CARS = (red:CONVOY || blue:CONVOY).

The remaining entity that must be modeled is the bridge itself. This must constrain CARS so that although one or more cars moving in the same direction may be on the bridge concurrently, cars moving in different directions may not. To enforce this, the bridge maintains a count of blue cars on the bridge and of red cars on the bridge. Red cars are only allowed to enter when the blue count is zero and vice versa. The BRIDGE process is listed below:

BRIDGE = BRIDGE[0][0], // initially empty
     BRIDGE[nr:T][nb:T] =   //nr is the red count, nb the blue
           (when (nb==0)
              red[ID].enter -> BRIDGE[nr+1][nb]
           |red[ID].exit    -> BRIDGE[nr-1][nb]
           |when (nr==0)
              blue[ID].enter-> BRIDGE[nr][nb+1]
           |blue[ID].exit   -> BRIDGE[nr][nb-1]
           ).

Note that the exit actions of the bridge permit the car counts, nr and nb, to be decremented even though their value is 0. As described in Chapter 5, the FSP compiler in the LTSA tool will automatically map these undefined states to the ERROR state, indicating this by issuing warnings:

Warning - BRIDGE.-1.0 defined to be ERROR
     Warning - BRIDGE.0.-1 defined to be ERROR
     ...

In fact, when BRIDGE is composed with CARS, their behavior prevents cars which have not entered from exiting and the ERROR state is unreachable.

Before describing the overall system composition, we need to specify a safety property to compose with the system that verifies that cars do not collide on the bridge. The required property is listed below. It specifies that while red cars are on the bridge only red cars can enter and while blue cars are on the bridge only blue cars can enter. When the bridge is empty, either a red car or a blue car may enter. The index i is used to count the red (or blue) cars currently on the bridge.

property ONEWAY =(red[ID].enter   -> RED[1]
                 |blue[ID].enter -> BLUE[1]
                 ),
RED[i:ID] = (red[ID].enter -> RED[i+1]
            |when(i==1)red[ID].exit -> ONEWAY
            |when(i>1) red[ID].exit -> RED[i-1]
            ),

BLUE[i:ID]= (blue[ID].enter -> BLUE[i+1]
                 |when(i==1)blue[ID].exit -> ONEWAY
                 |when(i>1) blue[ID].exit -> BLUE[i-1]
                 ).

The entire system can now be modeled by the composite process specified in Figure 7.5.

Figure 7.5. SingleLaneBridge model.

Safety analysis using LTSA verifies that the ONEWAY safety property is not violated.

However, without the constraints provided by the BRIDGE, the composition (CARS||ONEWAY) yields the following safety violation:

Trace to property violation in ONEWAY:
          red.1.enter
          blue.1.enter

In the single-lane bridge problem, it is reasonably clear which are the active entities and which are the passive entities. Cars are implemented as Java threads and the bridge as a monitor. This leaves the model entities NOPASS1 and NOPASS2 concerned with constraining overtaking. These have no explicit representation in the implementation. The overtaking constraint is dealt with in the BridgeCanvas class which displays car movement. Figure 7.6 depicts the class diagram for the program.

Figure 7.6. Single-lane bridge class diagram.

An instance of the BridgeCanvas class is created by the SingleLaneBridge applet. A reference to it is passed to each newly created RedCar and Blue-Car object. The methods provided by the BridgeCanvas class are listed in Program 7.1.

class BridgeCanvas extends Canvas {

  public void init(int ncars) {...}   //set number of cars

  //move red car with the identity i a step
  //returns true for the period from just before,
  // until just after car on bridge
  public boolean moveRed(int i)
         throws InterruptedException{...}

  //move blue car with the identity i a step
  //returns true for the period from just before,
  //until just after car on bridge
  public boolean moveBlue(int i)
         throws InterruptedException{...}

  public synchronized void freeze(){...} //freeze display
  public synchronized void thaw(){...}  //unfreeze display
}

class RedCar implements Runnable {

  BridgeCanvas display; Bridge control; int id;

  RedCar(Bridge b, BridgeCanvas d, int id) {
    display = d; this.id = id; control = b;
  }

  public void run() {
    try {
      while(true) {
          while (!display.moveRed(id));         // not on bridge
          control.redEnter();            // request access to bridge
          while (display.moveRed(id));       // move over bridge
          control.redExit();             // release access to bridge
      }
    } catch (InterruptedException e) {}
  }
}

  class BlueCar implements Runnable {

    BridgeCanvas display; Bridge control; int id;

    BlueCar(Bridge b, BridgeCanvas d, int id) {
      display = d; this.id = id; control = b;
    }

    public void run() {
      try {
        while (true) {
          while (!display.moveBlue(id));        // not on bridge
          control.blueEnter();           // request access to bridge
          while (display.moveBlue(id));       // move over bridge
          control.blueExit();            // release access to bridge
        }
      } catch (InterruptedException e) {}
    }
  }

The code for the two classes representing cars is listed in Program 7.2. Each car moves until it is about to enter the bridge. It then requests access to the bridge by invoking control.redEnter() if it is a red car and control.blueEnter() if it is blue. When a car has crossed the bridge, it invokes the appropriate Exit method.

class Bridge {
  synchronized void redEnter()
   throws InterruptedException {}
  synchronized void redExit()  {}
  synchronized void blueEnter()
   throws InterruptedException {}
  synchronized void blueExit() {}
}

The entry and exit bridge access methods are provided by an instance of the class Bridge or a class derived from Bridge. Class Bridge provides a null implementation as listed in Program 7.3. This enables us to view the results of an unsafe bridge implementation.

The SingleLaneBridge applet class creates one, two or three of each of the red and blue cars depending on which button is clicked. In addition, the check boxes select an implementation of the bridge monitor. Figure 7.7 depicts the consequences of using the null implementation of Program 7.3.

Figure 7.7. Single-lane bridge display using Bridge class.

Clicking the Safe check box creates a system that avoids the collisions of Figure 7.7. It uses the class SafeBridge which is a direct translation of the BRIDGE process from the model. Each of the guarded actions from the model becomes a conditionally synchronized method. Since this has been modeled and shown to preserve the ONEWAY safety property, we can be reasonably confident in the safety of the SafeBridge implementation. The code for the class is listed in Program 7.4.

class SafeBridge extends Bridge {

  private int nred  = 0; //number of red cars on bridge
  private int nblue = 0; //number of blue cars on bridge

  //Monitor Invariant:   nred≥0 and nblue≥0 and
  //           not(nred>0 and nblue>0)

  synchronized void redEnter()
       throws InterruptedException {
     while (nblue>0) wait();
     ++nred;
   }

  synchronized void redExit(){
      --nred; if (nred==0)notifyAll();
   }

  synchronized void blueEnter()
       throws InterruptedException {
     while (nred>0) wait();
     ++nblue;
   }

  synchronized void blueExit(){
     --nblue; if (nblue==0)notifyAll();
   }
 }

The implementation of SafeBridge uses conditional notification. We only wake up waiting threads when the number of cars on the bridge – either red or blue – is decremented to zero. This avoids unnecessary thread switches since otherwise, blue cars would be woken up every time a red car leaves the bridge and vice versa. It is only the last car of a particular color to leave the bridge that should wake up waiting car threads.

SafeBridge ensures that cars do not collide on the bridge; however, it does not ensure that cars eventually get the opportunity to cross the bridge. With three cars of each color, if a red car crosses the bridge first there is always a red car on the bridge and consequently, blue cars never get to cross. This situation is called starvation: a form of liveness property discussed in the next section.

To illustrate the notion of progress, we use a simple example, that of tossing a coin. The model is depicted in Figure 7.8.

Figure 7.8. COIN model.

If the coin were tossed an infinite number of times, we would expect that heads would be chosen infinitely often and that tails would be chosen infinitely often. In fact, this depends on the scheduling policy used to decide on which transition from the set of eligible transitions should be executed. If the policy is not fair then we could always choose the toss transition leading to heads. We assume that the scheduling policy for choice is fair as defined in the following:

If the transition (or transitions) of an action occurs infinitely often in a system, we can say that it is always the case at any stage of the execution that the action will eventually occur. With the assumption of fair choice then the coin-tossing system should eventually choose heads and eventually choose tails. We can assert this with progress properties specified in FSP. A progress property is defined by:

In other words, a progress property asserts that at any stage of execution one of the actions in the progress set will eventually occur. The liveness requirement for coin tossing can now be expressed as:

progress HEADS = {heads}
progress TAILS = {tails}

The COIN system we have defined so far satisfies these properties. We now examine a system that does not. Suppose that the agent which tosses the coin first picks one of two coins: a normal coin with a head and a tail as defined in Figure 7.8 and a trick coin which has a head on both sides. The outcome of tossing the trick coin must always be heads. This system is modeled in Figure 7.9.

Progress analysis of the TWOCOIN system against the progress properties HEADS and TAILS produces the following output:

Progress violation: TAILS
     Path to terminal set of states:

Figure 7.9. TWOCOIN model.

pick
     Actions in terminal set:
     {toss, heads}

This confirms the expected result: if the agent picks the trick coin then the action tails will never occur. This is of course a violation of the TAILS progress property, which asserts that in an infinite execution, tails must occur infinitely often. The reader should note that the system of Figure 7.9 does not violate the progress property:

progress HEADSorTAILS = {heads,tails}

Property HEADSorTAILS is not violated since only one of the actions in the progress set need be executed infinitely often to satisfy the property.

Progress analysis involves first performing a search for terminal sets of states.

In graph theory, this is known as a strongly connected component, which has no path to any nodes outside the set of nodes in the component. For example, the labeled transition system of Figure 7.9 has two terminal sets of states, {1, 2}, which are the states relating to the trick coin, and {3, 4, 5}, which are the states relating to the normal coin.

An execution of a system represented by a finite set of states can only be infinite if some of the states are visited infinitely often. The states that are visited infinitely often in an execution must form a terminal set. Given fair choice, each terminal set of states represents an execution in which each transition in the set is executed infinitely often. Since there is no transition out of a terminal set, any action that is not used in all terminal sets cannot occur infinitely often in all executions of the system. Checking that a progress property holds is now simply checking that in each terminal set, at least one of the actions in the progress set occurs as a transition. Conversely, a progress property is violated if analysis finds a terminal set of states in which none of the progress set actions appear. For the TAILS property, this terminal set is the set of states {1, 2} in which the action tails does not occur. The output gives the shortest execution path to the root of the terminal set and lists the actions that do appear in the set.

If no progress properties are specified, LTSA performs progress analysis using a default property. This property asserts that for every action in the alphabet of the target system, given fair choice, that action will be executed infinitely often. This is equivalent to specifying a separate progress property for every action. For the TWOCOIN system, this default analysis produces the following output:

Progress violation for actions:
     {pick}
     Path to terminal set of states:
          pick
     Actions in terminal set:
     {toss, heads, tails}

     Progress violation for actions:
     {pick, tails}
     Path to terminal set of states:
          pick
     Actions in terminal set:
     {toss, heads}

The analysis produces two progress violations since the action pick is not executed infinitely often in either terminal set. The value of this default property is that if it is not violated, then no specified progress properties can be violated. In other words, if the default property holds, then every other progress property, specified in terms of subsets of the action alphabet of a target system, must also hold. This is true since the default property asserts that every action is executed infinitely often. All systems in which the states occur inside a single terminal set satisfy the default progress property.

If default progress analysis is applied to the single-lane bridge model then no violations are detected. However, we know from the implementation that it is possible for progress violations to occur. Either the blue cars or the red cars may wait forever to cross the bridge. Why do we not detect these progress problems?

The answer lies in the fair choice assumption underlying the progress test. This means that every possible execution of the system will eventually happen including those in which cars do not starve. To detect progress problems we must superimpose some scheduling policy for actions, which models the situation in which the bridge is heavily used, i.e. we need to impose adverse conditions which "stress-test" the system. We use action priority expressions to describe these scheduling policies. Action priority is specified in FSP with respect to process compositions.

Low Priority Operator ("≫")

Note

||C = (P||Q)≫{a1,...,an} specifies a composition in which the actions a1,...,an have lower priority than any other action in the alphabet of P||Q including the silent action tau. In any choice in this system which has one or more transitions not labeled by a1,...,an, the transitions labeled by a1,...,an are discarded.

Action priority operators simplify the composite processes by discarding particular transitions. Figure 7.10 illustrates the effect for a simple example. When work is specified to be a high priority action in the composition HIGH, the sleep transition disappears since it is lower priority and consequently in a choice between sleep and work, work will always be chosen. When work is specified to be a low priority action in the composition LOW, the work transition disappears since it is lower priority and consequently in a choice between sleep and work, sleep will always be chosen.

Figure 7.10. Action priority.

A bridge which decides dynamically at any given point whether to admit blue cars or red cars needs to have more information about the state of cars than is currently available in the model. In particular, the bridge needs to know whether cars are waiting to cross. To this end, the model for a car is modified so that it requests access to the bridge before attempting to enter. The revised model for a car is:

CAR = (request->enter->exit->CAR).

The bridge model can now count the number of cars waiting at each end. The count is incremented when a car requests access and decremented when the car enters the bridge. Our first attempt at a revised BRIDGE process uses this count of waiting cars as follows. Red cars are only allowed to enter the bridge if there are no blue cars on the bridge and there are no blue cars waiting. Blue cars are only allowed to enter the bridge if there are no red cars on the bridge and no red cars waiting to enter the bridge. The revised BRIDGE process is as follows:

/* nr - number of red cars on the bridge
        nb - number of blue cars on the bridge
        wr - number of red cars waiting to enter
        wb - number of blue cars waiting to enter
     */
     BRIDGE = BRIDGE[0][0][0][0],
     BRIDGE[nr:T][nb:T][wr:T][wb:T] =
       (red[ID].request  -> BRIDGE[nr][nb][wr+1][wb]
       |when (nb==0 && wb==0)
         red[ID].enter   -> BRIDGE[nr+1][nb][wr-1][wb]
       |red[ID].exit     -> BRIDGE[nr-1][nb][wr][wb]
       |blue[ID].request -> BRIDGE[nr][nb][wr][wb+1]
       |when (nr==0 && wr==0)
         blue[ID].enter  -> BRIDGE[nr][nb+1][wr][wb-1]
       |blue[ID].exit    -> BRIDGE[nr][nb-1][wr][wb]
       ).

The problem with this model is that when we check the safety properties of the new SingleLaneBridge system, a deadlock is reported:

Trace to DEADLOCK:
           red.1.request
           red.2.request
           red.3.request
           blue.1.request
           blue.2.request
           blue.3.request

The trace is the scenario in which there are cars waiting at both ends, and consequently, the bridge does not allow either red or blue cars to enter. To solve this problem, we must introduce some asymmetry into the problem (as was done for the Dining Philosophers in Chapter 6). This takes the form of a boolean variable (bt) which indicates whether it is the turn of blue cars or red cars to enter the bridge. Initially, bt is set to true indicating it is blue's turn. As soon as a blue car exits the bridge, bt is set to false. When a red car exits, bt is set to true again. The BRIDGE process becomes:

const True = 1
const False = 0
range B = False..True
/* nr - number of red cars on the bridge
   nb - number of blue cars on the bridge
   wr - number of red cars waiting to enter
   wb - number of blue cars waiting to enter
   bt - true indicates blue turn,
        false indicates red turn
*/
BRIDGE = BRIDGE[0][0][0][0][True],
BRIDGE[nr:T][nb:T][wr:T][wb:T][bt:B] =
 (red[ID].request ->BRIDGE[nr][nb][wr+1][wb][bt]
 |when (nb==0 && (wb==0||!bt))
   red[ID].enter  ->BRIDGE[nr+1][nb][wr-1][wb][bt]
 |red[ID].exit    ->BRIDGE[nr-1][nb][wr][wb][True]
 |blue[ID].request->BRIDGE[nr][nb][wr][wb+1][bt]
 |when (nr==0 && (wr==0||bt))
   blue[ID].enter ->BRIDGE[nr][nb+1][wr][wb-1][bt]
 |blue[ID].exit   ->BRIDGE[nr][nb-1][wr][wb][False]
).

The condition under which the bridge permits a red car to enter is that there are no blue cars on the bridge and either there are no blue cars waiting or it is not blue's turn: nb==0 &&(wb==0 || !bt). The condition for a blue car to enter is that there are no red cars on the bridge and either there are no red cars waiting or it is blue's turn: nr==0 &&(wr==0 || bt).

This corrected model no longer deadlocks. Further, a progress analysis reports that BLUECROSS and REDCROSS properties are not violated.

The revision to the program involves a new version of the bridge monitor which implements precisely the BRIDGE process from the model developed in the last section. In fact, we do not need to introduce a new monitor method to implement the request action made by cars. The existing enter methods can be modified to increment a wait count before testing whether or not the caller can access the bridge. As before, the tests are simply the negation of the guards in the model BRIDGE process. The new implementation is listed in Program 7.5.

In the demonstration applet, this implementation of the monitor is used when the Fair check box is clicked.

class FairBridge extends Bridge {
  private int nred = 0; //count of red cars on the bridge
  private int nblue = 0; //count of blue cars on the bridge
  private int waitblue = 0;  //count of waiting blue cars
  private int waitred = 0;   //count of waiting red cars
  private boolean blueturn = true;

  synchronized void redEnter()
      throws InterruptedException {
    ++waitred;
    while (nblue>0||(waitblue>0 && blueturn)) wait();
    --waitred;
    ++nred;
  }

  synchronized void redExit(){
    --nred;
    blueturn = true;
    if (nred==0)notifyAll();
  }

  synchronized void blueEnter(){
      throws InterruptedException {
    ++waitblue;
    while (nred>0||(waitred>0 && !blueturn)) wait();
    --waitblue;
    ++nblue;
  }

  synchronized void blueExit(){
    --nblue;
    blueturn = false;
    if (nblue==0) notifyAll();
  }
}

In modeling the problem, the first step is to decide on the actions of interest. These are acquiring and releasing read access to the shared database and acquiring and releasing write access. The actions are declared below as the set Actions:

set Actions = {acquireRead,releaseRead,
               acquireWrite,releaseWrite}

As for the Ornamental Garden model in section 4.1.2, we use a set constant simply as a way of abbreviating the model description. The processes that model Readers and Writers are:

READER =
       (acquireRead->examine->releaseRead->READER)
       +Actions
        {examine}.

     WRITER =
       (acquireWrite->modify->releaseWrite->WRITER)
       +Actions
        {modify}.

A READER process must acquire read access before examining the database and a WRITER must acquire write access before modifying the database. The alphabets of both processes have been defined to be the full set of access actions by the alphabet extension +Actions. This ensures that while a READER only engages in the acquireRead and releaseRead actions, the acquireWrite and releaseWrite actions cannot occur freely for any prefixed instance of the process. Similarly, for WRITER processes, the acquireRead and releaseRead actions cannot occur freely. The examine and modify actions are hidden since they are irrelevant to the problem of synchronizing access to the shared database.

Access to the shared database is controlled by a read/write lock. The lock accepts acquireRead actions when it has not been acquired for write access by acquireWrite. It permits only a single write access when it has not been acquired for read access. The lock is modeled by the RW_LOCK process:

const False = 0   const True = 1
range Bool  = False..True
const Nread = 2           // Maximum readers
const Nwrite= 2           // Maximum writers

RW_LOCK = RW[0][False],
RW[readers:0..Nread][writing:Bool] =
      (when (!writing)
         acquireRead ->RW[readers+1][writing]
      |releaseRead   ->RW[readers-1][writing]
      |when (readers==0 && !writing)
         acquireWrite->RW[readers][True]
      |releaseWrite  ->RW[readers][False]
      ).

The RW_LOCK process maintains a count of the number of concurrent read accesses (readers) and a boolean (writing) which is set to true when the lock is acquired for write access. The action to acquire read access is only accepted when writing is false and the action to acquire write access is only accepted when readers==0 and writing is false.

Safety Property

To check that the lock behaves as desired, we define a safety property, RW_SAFE, as follows:

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 property asserts that initially either an acquireRead action or a acquireWrite action can be accepted. In other words when the lock is free, it can be acquired for either read or write access. When acquired for read access (READING), further acquireRead actions are permitted but no acquireWrite actions. The lock does not become free until all the releaseRead actions which correspond to the acquireRead actions have happened. When the lock has been acquired for write access (WRITING), only the releaseWrite action should occur. To check that the lock implementation RW_LOCK satisfies the property, the lock is composed with the property as follows:

||READWRITELOCK = (RW_LOCK || SAFE_RW).

The resulting LTS is depicted in Figure 7.13.

Figure 7.13. READWRITELOCK LTS.

The transitions to the ERROR state in Figure 7.13 occur if a Reader or Writer is badly behaved. For example, if a Reader performs a releaseRead without previously having performed an acquireRead then a safety violation will occur. A violation will also occur if more than two acquireRead requests are made.

The composition of READER and WRITER processes with the read/write lock is described in Figure 7.14. Analysis of this system reveals no deadlocks or safety violations. The addition of well-behaved READER and WRITER processes ensures that the error transitions of Figure 7.13 cannot occur.

Figure 7.14. READERS_WRITERS model.

Progress Property

The progress properties that are important in the Readers–Writers system are that both Readers and Writers should eventually acquire access to the shared database. We can express the required progress properties as follows:

progress WRITE = {writer[1..Nwrite].acquireWrite}
progress READ  = {reader[1..Nread].acquireRead}

The WRITE property asserts that it should always be the case that at least one of the WRITER processes can perform an acquireWrite action. Since WRITER s are completely symmetric, we can reasonably expect that if one can acquireWrite then so can the others. READ specifies the same property for READER processes and acquireRead. A progress check reports no violations of these properties in the system specified by READERS_WRITERS. Because of the fair choice assumption, progress problems only occur in complete system models that are erroneous. To find how the system performs when loaded or "stressed", we must specify adverse scheduling conditions using action priority. This is exactly the procedure we adopted to find the progress problems in the single-lane bridge model. Indeed, the adverse conditions are similar to those used in the bridge problem. To model a heavily loaded system, we give lower priority to release actions in the same waywegavelowerpriorityto exit actions in the bridge problem. (Alternatively, we could give higher priority to the acquire actions.) The system model used for progress analysis is described by:

||RW_PROGRESS = READERS_WRITERS
                     ≫{reader[1..Nread].releaseRead,
                        writer[1..Nread].releaseWrite}.

Analysis of this system leads to the violation:

Progress violation: WRITE
     Path to terminal set of states:
          reader.1.acquireRead
     Actions in terminal set:
     {reader.1.acquireRead, reader.1.releaseRead,
      reader.2.acquireRead, reader.2.releaseRead}

The violation describes the scenario in which Writers cannot access the shared database because a Reader always has read access. In other words, the number of Readers never drops to zero and consequently, the read/write lock denies access to Writers. The terminal set of states that describes this behavior can clearly be seen in Figure 7.15. It contains the states numbered 3, 4 and 5. Before exploring solutions to this progress problem, we translate the existing model into an implementation in the next section.

Figure 7.15. RW PROGRESS LTS.

In the interests of brevity, we describe only the monitor that synchronizes the accesses of Readers and Writers to a shared database. This synchronization is the essence of the problem. In the same way that we defined the set of actions of interest in the Readers–Writers model, we define an interface that identifies the monitor methods that must be implemented. In the sections that follow, we develop a number of alternative implementations of this interface. The interface is listed in Program 7.6.

interface ReadWrite {
     public void acquireRead()
         throws InterruptedException;
     public void releaseRead();
     public void acquireWrite()
        throws InterruptedException;
     public void releaseWrite();
}

Each method in the ReadWrite interface corresponds directly to the action of the same name in the model. Our first implementation of ReadWrite, which corresponds exactly to the RW_LOCK process from the model, is listed in Program 7.7.

The guarded actions from the model become synchronized methods containing waits. However, in the implementation, we must decide on notification to awake threads blocked in waits. The simple solution, as discussed in Chapter 5, is to include a call to notifyAll() in every monitor method that modifies the state of the monitor. However, this can lead to unnecessary thread switches. In the ReadWriteSafe monitor, notification is required only when the last Reader has relinquished access and when a Writer releases. When the last Reader calls releaseRead() (i.e. readers==0), notify() rather than notifyAll() can be used since only Writers can be waiting and it is only necessary to unblock a single Writer. When a Writer is finished it calls releaseWrite() which then calls notifyAll(). This is because it may be necessary to unblock either one or more Readers or a Writer.

class ReadWriteSafe implements ReadWrite {
  private int readers =0;
  private boolean writing = false;

  public synchronized void acquireRead()
             throws InterruptedException {
    while (writing) wait();
    ++readers;
  }

  public synchronized void releaseRead() {
    --readers;
    if(readers==0) notify();
  }

public synchronized void acquireWrite()
            throws InterruptedException {
  while (readers>0 || writing) wait();
  writing = true;
}

  public synchronized void releaseWrite() {
    writing = false;
    notifyAll();
  }
}

The implementation suffers from the progress problem detected in the model. If the number of Readers accessing the shared database never drops to zero, then Writers can never gain access. This behavior can be seen in the demonstration applet when the two Reader threads are started such that there is always one holding the lock. The applet display is depicted in Figure 7.16.

Figure 7.16. Readers–Writers applet display.

To address the progress problem discovered with our first model and implementation of the Readers–Writers problem, we adopt an approach in which Readers are denied access if there are Writers waiting to acquire access. This should give Writers priority in acquiring the lock and avoid the situation in which they wait forever for access. To detect that a Writer is waiting for access, we must add another action to its repertoire. A Writer must request access before attempting to acquire it. This is exactly the same solution we adopted in the single-lane bridge solution to detect whether cars were waiting. The additional action is requestWrite and the revised WRITER process is shown below:

set Actions = {acquireRead,releaseRead,
       acquireWrite,releaseWrite,requestWrite}

WRITER =
  (requestWrite->acquireWrite->modify
               ->releaseWrite->WRITER
  )+Actions{modify}.

The READER process remains unchanged. RW_LOCK is modified to maintain a count of waiting Writers (waitingW). The count is incremented when a Writer requests access and decremented when it actually acquires access. Readers are only allowed to acquire the lock when the number of waiting Writers is zero. The revised lock process is listed below:

RW_LOCK = RW[0][False][0],
     RW[readers:0..Nread]
       [writing:Bool]
       [waitingW:0..Nwrite] =
       (when (!writing && waitingW==0)
          acquireRead -> RW[readers+1][writing][waitingW]
       |releaseRead   -> RW[readers-1][writing][waitingW]
       |when (readers==0 && !writing)
          acquireWrite-> RW[readers][True][waitingW-1]
       |releaseWrite  -> RW[readers][False][waitingW]
       |requestWrite  -> RW[readers][writing][waitingW+1]
       ).

This definition of RW_LOCK still satisfies the RW_SAFE property. Note that we have not had to change the definition of the safety property. The request action (requestWrite) is not relevant to the safe operation of the lock and so does not appear in the alphabet of the safety property. Safety is determined only by the correct sequencing of acquire and release actions.

A progress analysis of RW_PROGRESS now produces the output:

Progress violation: READ
     Path to terminal set of states:
          writer.1.requestWrite
          writer.2.requestWrite
     Actions in terminal set:
     {writer.1.requestWrite, writer.1.acquireWrite,
      writer.1.releaseWrite, writer.2.requestWrite,
      writer.2.acquireWrite, writer.2.releaseWrite}

We no longer have a violation of the WRITE property, demonstrating that in this Writers priority system, Writers can always access the shared database. However, we now have a READ progress violation. This occurs since, if there is always a Writer waiting to acquire the lock, then Readers will never gain access. However, in the practical application of read/write locks, the Writers priority solution is often satisfactory since there are usually many more read accesses to a database than write accesses. In addition, it may be important that Readers get the most up-to-date information. The implementation of a Writers priority lock is listed in Program 7.8. It follows directly from the revised definition of RW_LOCK.

A version of the read/write lock that satisfies both the READ and WRITE properties involves the addition of a boolean which indicates whether it is the Readers' turn or the Writers' turn. Readers only defer to waiting Writers when it is not their turn to acquire the lock. This turn variable plays exactly the same role in the Readers–Writers problem as the turn variable in the single-lane bridge. The final version of the read/write lock model is listed below. The implementation is left as an exercise.

RW_LOCK = RW[0][False][0][False],
    RW[readers:0..Nread]
      [writing:Bool]
      [waitingW:0..Nwrite]
      [readersturn:Bool] =
    (when (!writing && (waitingW==0||readersturn))
          acquireRead ->RW[readers+1][writing][waitingW][readersturn]
      |releaseRead    ->RW[readers-1][writing][waitingW][False]
      |when (readers==0 && !writing)
         acquireWrite  ->RW[readers][True][waitingW-1][readersturn]
      |releaseWrite    ->RW[readers][False][waitingW][True]
      |requestWrite    ->RW[readers][writing][waitingW+1][readersturn]
    ).

class ReadWritePriority implements ReadWrite{
  private int readers =0;
  private boolean writing = false;
  private int waitingW = 0; // no of waiting Writers.

  public synchronized void acquireRead()
            throws InterruptedException {
    while (writing || waitingW>0) wait();
    ++readers;
  }

  public synchronized void releaseRead() {
     --readers;
     if (readers==0) notifyAll();
  }

  public synchronized void acquireWrite()
             throws InterruptedException {
    ++waitingW;
    while (readers>0 || writing) wait();
    --waitingW;
    writing = true;
  }

  public synchronized void releaseWrite() {
    writing = false;
    notifyAll();
  }
}