Solutions to Homework 3

Problem 1

Suppose that the operations on mutex are omitted from the solution to the readers/writers problem (Tanenbaum, p. 129, figure 2-34).

A. Show how a race condition can occur in which a reader and a writer are simultaneously accessing the database.

Answer: Suppose there are two readers P and Q and a writer W. Consider the following sequence of steps:

Initially db=1  rc=0

    P                  Q             W            Result
rc=rc+1                                              rc=1
                     rc=rc+1                         rc=2
if (rc==1) down(db)                                  noop
read_data_base()                   
                                   down(db)          db=0
                                write_data_base   
P and W are simultaneously reading the database.

B. Show how a race condition can occur in which all processes are forever blocked from accessing the database.

Answer: We need the fact that the high-level instructions "rc=rc+1" typically expands into three machine instructions something like

LOAD RA,rc      
ADD  RA,1      
STORE RA,rc   
and the fact that, when a process is suspended and resumed, registers are reset to their current values in the process.

Let P, Q, and R be readers. Consider the following sequence of steps:

Initially db=1  rc=0

    P                  Q                  R                  State
rc = rc+1                                                    rc=1
if (rc==1) down(db)                                          db=0
read_data_base()     
                    LOAD RA,rc                               RA in Q = 1
                                         LOAD  RA,rc         RA in R = 1
                    ADD RA, 1                                RA in Q = 2
                    STORE RA,rc                              rc=2
                                         ADD RA,1            RA in R = 2
                                         LOAD RA,rc          rc=2
                    if (rc==1) down(db)                      noop
                    read_data_base() 
                                         if (rc==1) down(db) noop
                                         read_data_base()
rc = rc-1                                                    rc=1
                    rc=rc-1                                  rc=0
                                         rc=rc-1             rc=-1
if (rc==0) up(db)                                            noop
                    if (rc==0) up(db)                        noop
                                         if (rc==0) up(db)   noop
use_read_data
                    use_read_data
                                         use_read_data
rc = rc+1                                                    rc=0
                    LOAD RA,rc                               RA in Q = 0
                                         LOAD  RA,rc         RA in R = 0
                    ADD RA, 1                                RA in Q = 1
                    STORE RA,rc                              rc=1
                                         ADD RA,1            RA in R = 1
                                         LOAD RA,rc          rc=1
if (rc==1) down(db)                                          block P
                    if (rc==1) down(db)                      block Q
                                         if (rc==1) down(db) block R
Now all the readers are blocked, and the semaphore db=0, so any writer that comes along will also block.

Problem 2

Consider the following sychronization problem: There are three processes, P, Q, and R. All three are executing a loop from 1 to N. You wish to enforce the condition that no process may enter the (I+1)st iteration until the other two processes have completed the Ith iteration. Show how this condition can be enforced using three semaphores.

Answer:

Semaphores sP, sQ, sR are initialized to 0

P                      Q                        R
for I := 1 to N     for I := 1 to N        for I := 1 to N
  [body of loop]      [body of loop]         [body of loop]
  up(sQ)              up(sP)                 up(sP)
  up(sR)              up(sR)                 up(sQ)
  down(sP)            down(sQ)               down(sR)
  down(sP)            down(sQ)               down(sR)
Thus, process P cannot complete its two calls to down(sP) until both Q and R have completed their calls to up(sP), and likewise for the other processes.