Solution to Homework #3

**6.2** Prove that, in the bakery algorithm (Section 6.2.2), the
following property holds: If Pi is in its critical section and Pk (k 6
= i) has already chosen its number[k] 6 =0,then(number[i],i) < (number[k],k).

**Answer:**

Suppose that Pi is in its critical section, and Pk(k!=i) has already
chosen its number[k], there are two cases:

1. Pk has already chosen its number when Pi does the last test before
entering its critical section.

In this case, if (number([i], i) < (number[k],k) does not hold,
since they can not be equal, so (number[i],i) > (number[k],k). Suppose
this is true, then Pi can not get into the cirtical section before Pk does,
and Pi will looping at the last while statement until the condition does
not hold, which is modified by Pk when it exits from its critical section.Note
that if Pk get a new number again, it must be larger than that of Pi's.

2. Pk did not chose its number when Pi does the last test before entering
its critical section.

In this case, since Pk has chosen its number when Pi is in its critical
section, Pk must chose its number later than Pi. According to the algorithm,
Pk can only get a bigger number than Pi, so (number[i],i) < number([k],k)
holds.

**6.3 **The first known correct software solution to the critical-section
problem for two processes was developed by Dekker. The two processes, P0
and P1, share the following variables: var flag: array [0..1] of boolean;
(* initially false *) turn: 0..1;

repeatFigure 6.24 The structure of process Pi in Dekker's algorithm.flag[i]:=true;

while flag[j]

do if turn = j

then begin

flag[i]:=false;

while turn = j do no-op;

flag[i]:=true;

end;critical section

turn := j;

flag[i]:=false;remainder section

until false;

The structure of process Pi (i = 0 or 1), with Pj (j = 1 or 0) being
the other process, is shown in Figure 6.24.

Prove that the algorithm satisfies all three requirements for the critical-section
problem.

**Answer: **To prove property (a) we note that each Pi enters its
critical section only if flag[j] = false. Since only Pi can update flag[j],
and since Pi inspects flag[j] only while flag[i]=true, the result follows.

a. To prove property (b), we first note that the value of the variable turn is changed only at the end of the critical section. Suppose that only process Pi wants to enter the critical section. In this case, it will find flag[j]=false and immediately enter the critical section, independent of the current value of turn. Suppose that both processes want to enter the critical section, and the value of turn = 0. Two cases are now possible. If Pi finds flag[0] = false then it will enter the critical section. If Pi finds flag[0] = true then we claim that P0 will enter the critical section before P1. Moreover, it will do so within a finite amount of time.

b. To demonstrate this fact, first consider process P0. Since turn = 0, it will only be waiting for flag[1] to be set to false; more precisely, it will not be executing in the begin block associated with the if statement. Furthermore, it will not change the value of flag[0]. Meanwhile, process P1 will find flag[0] = true and turn = 0. It will set flag[1] = false and wait until turn = 1. At this point, P0 will enter its critical section. A symmetric argument can be made if turn =1. 6.4 The first known correct software solution to the critical-section problem for n processes with a lower bound on waiting of n

**6.6** Show that, if the wait and signal operations are not executed
atomically, then mutual exclusion may be violated.

**Answer: **Suppose the value of semaphore S = 1 and processes P1
and P2 execute wait(S) concurrently.

a. T0: P1 determines that value of S =1

b. T1: P2 determines that value of S =1

c. T2: P1 decrements S by 1 and enters critical section

d. T3: P3 decrements S by 1 and enters critical section

**6.8 **The Cigarette-Smokers Problem. Consider a system with three
smoker processes and one agent process. Each smoker continuously rolls
a cigarette and then smokes it. But to roll and smoke a cigarette, the
smoker needs three ingredients: tobacco, paper, and matches. One of the
smoker processes has paper, another has tobacco, and the third has matches.
The agent has an infinite supply of all three materials. The agent places
two of the ingredients on the table. The smoker who has the remaining ingredient
then makes and smokes a cigarette, signaling the agent on completion. The
agent then puts out another two of the three ingredients, and the cycle
repeats. Write a program to synchronize the agent and the smokers.

**Answer: **The shared data structures are

var a: array [0...2] of
semaphore { initially = 0 }

/* which controls which smoker can continue */

agent: semaphore { initially =
1 }

/* Each time agent distribute two resources, and one smoker can continue
*/

The agent process code is as follows:

repeat

Set i to a value between 0 and 2.

wait(agent);

signal(a[i]);

until false;

Each smoker process waits for the signal which informs the smoker
to continue.

repeat

wait(a[i]);

"smoke"

signal(agent);

until false;

**6.13 **Consider a system consisting of processes P1, P2, ..., Pn,
each of which has a unique priority number. Write a monitor that allocates
three identical line printers to these processes, using the priority numbers
for deciding the order of allocation.

**Answer: **The monitor code is

type resource = monitor

var P: array[0..2] of boolean;

X: condition;

procedure acquire (id: integer, printer-id: integer);

begin

if P[0] and P[1] and P[2] then X.wait(id)

if not P[0] then printer-id := 0;

else if not P[1] then printer-id := 1;

else printer-id := 2;

P[printer-id]:=true;

endprocedure release (printer-id: integer)

begin

P[printer-id]:=false;

X.signal;

endbegin

P[0] := P[1] := P[2] := false;

end