## 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
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
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
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
if (rc==1) down(db)                      noop
if (rc==1) down(db) noop
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
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
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.

```Semaphores sP, sQ, sR are initialized to 0