Deriving Semaphore Solutions from "<await (B) S; >" (atomic action) Statements

from Andrews Chapter 4

• Specifying global invariant (for readers and writers problem)
• specifying bad conditions - conditions you don't want to occur

    BAD: (nr > 0 ^ nw > 0) or nw > 1

• specifying good conditions that must always hold

    RW: (nr == 0 or nw == 0) ^ nw <=1

• critical region for reader

    <nr = nr + 1; >
      read the database;
    <nr = nr -1;>

• critical region for writer

    < nw = nw + 1;>
      write the database;
    <nw = nw - 1;>

• Must guard the assignments to the shared variables to maintain predicate RW

int nr = 0, nw = 0;
## RW: (nr ==0 or nw ==0) ^ nw <=1

process Reader [i = 1 to m] {
  while (true) {
    ...
<await (nw == 0) nr = nr + 1; >
      read the database;
<nr = nr -1;>
  }
}

process Writer [j = 1 to m] {
  while (true) {
    ...
<await (nr == 0 and nw == 0) nw = nw +1; >
      write the database;
<nw = nw - 1; >
  }
}

• We need a semaphore "e" to provide mutually exclusive access to the shared variables
• We need a semaphore and a counter for each guard we implement
• For readers and writers we need:
• semaphore "r" to keep the delayed Reader processes and a counter "dr" to count the number of  delayed Reader processes
• semaphore  "w" to keep the delayed Writer processes and a counter "dw" to count the number of delayed Writer processes
• We need a common segment of code (SIGNAL) to exit each atomic statement

SIGNAL: if (nw == 0 and dr > 0) {
dr = dr - 1; V(r);  #awaken a reader or
               }
elseif (nr ==0 and nw ==0 and dw > 0) {
dw = dw - 1; V(w);  #awaken a writer, or
               }
               else
                 v(e);  # release the entry (mutex) lock

• Code for "passing the baton"
• When a process is executing within an atomic region, it holds a baton. When it finishes its work, it passes the "baton" (that is the right to enter an atomic region) to another process. If a process is waiting on a condition, it now has the "baton" and can execute its critical region. It then, in turn, passes the baton to another waiting process. This is accomplished through the SIGNAL code fragment.

int n = 0, nw = 0; ##RW: (nr==0 or nw == 0) and nw <=1
sem e = 1,        #controls entry to critical sections
     r = 0,           # use to delay readers
    w = 0;        #used to delay writers
int dr = 0,       #number of delayed readers
dw = 0;     #number of delayed writers

process Reader [i = 1 to M] {
  while(true) {
#<await nw == 0 nr = nr +1; >
    P(e);
    if (nw > 0) {dr =dr+1; V(e); P(r); }
    nr = nr+1;
    SIGNAL;
  read the database;
# <nr = nr-1;>
    P(e);
    nr = nr - 1;
    SIGNAL;
  }
}

process Writer [j = 1 to N] {
  while(true) {
# <await nr==0 and nw==0) nw = nw+1;>
   P(e);
    if (nr > 0 or nw >0) {dw = dw+1; V(e); P(w); }
nw = nw +1;
    SIGNAL;
    write the database;
# <nw = nw-1;>
    P(e);
nw = nw-1;
    SIGNAL;
  }
}

• Simplying Code
• By examination of the code, we can simplify the SIGNAL code fragment.
• For example, in the Reader, before the first use of SIGNAL, we know that nw = 0 and nr is positive (there are no running writers and there are some running readers)
• simplified SIGNAL: if (dr > 0) {dr = dr-1; V(r);} else V(e);
• In the Reader, before the second use of SIGNAL: (there are no running writers and no delayed readers)
• both nw and dr are zero
• In the Writer, before the first use of SIGNAL: (there are no running readers and there is a running writer)
• nw is positive and nr is zero
• In the Writer, before the second use of SIGNAL: (there are no running readers or writers)
• nr = 0 and nw = 0
• When writer finishes, if there is a delayed reader, start them up in cascading fashion.
• Writer always checks for readers first. This could be switched for a different prioritization of readers and writers

int nr = 0, nw = 0;   #RW: (nr==0 or nw==0) and nw<=1
sem e=1, r=0, w=0; #controlling entry to crit. sect. and holding delayed readers and writers
int dr =0, dw = 0;  #counting delayed readers and writers

process Reader [ i = 1 to M] {
  while(true) {
    # <await (nw ==0) nr = nr + 1; >
    P(e);
    if (nw > 0 {dr = dr + 1; V(e); P(r); }
    nr = nr +1;
    if (dr > 0) {dr = dr - 1; V(r); }
    else V(e);
    read the database;
    #<nr = nr -1;>
    P(e);
    nr = nr -1;
    if ( nr ==0 and dw > 0) { dw = dw -1; V(w)}
    else V(e);
  }
}

process Writer [j = 1 to N] {
  while(true) {
  # <await nr==0 and nw==0) nw = nw+1;>
   P(e);
    if (nr > 0 or nw >0) {dw = dw+1; V(e); P(w); }
nw = nw +1;
    V(e);
    write the database;
    # <nw = nw-1;>
    P(e);
nw = nw-1;
    if (dr > 0) { dr = dr - 1; V(r);}
elseif (dw > 0) { dw = dw - 1; V(w); }
    else V(e);
  }
}