Due: November 10

- Consider Algorithm 3 of Chapter 6 in the book (6.2.1.3). We want to extend the solution for n processes for n > 2. Implicit in the algorithm as given is that the other process (j) is always equal to (1-i). To generalize, let the statement turn:=j be replaced by turn:=(turn+1) mod n. Evaluate this new algorithm with respect to the set of properties of a "good" solution.

The modified algorithm has shared data of:

var

flag: array [0..n-1] of boolean;

turn: 0..n-1The code for process i is:

repeat

flag[i] := true;

turn := (turn + 1) mod n;

while (flag[j] and turn = j) do no-op;/* critical section */

flag[i] := false;

/* remainder section */

until false

Let us consider a system with 3 processes, P

_{0}, P_{1}, and P_{2}. Let turn be 0 initially. Now let P_{0}go through the entry code and then enter its critical section. We then have:flag[0] = true; flag[1] = false; flag[2] = false; turn = 1

If goes through its entry section to the while statement, then we have

flag[0] = true; flag[1] = true; flag[2] = false; turn = 2

Now, we can either fix j to be some process other than the current one (say 0), or we can try and "improve" the situation by having j range over all processes other than the current one (j = 0 or j = 2). In either case, we fall through the while condition and enter the critical section, violating mutual exclusion.

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

Suppose that the value of semaphore

S= 1 and processesP_{1}andP_{2}executewait(S) concurrently according to the following timeline:

T_{0}:P_{1}determines that value ofS= 1T_{1}:P_{2}determines that value ofS= 1T_{2}:P_{1}decrementsSby 1 and enters critical sectionT_{3}:P_{2}decrementsSby 1 and enters critical section

- (aka 6.12) Suppose that the
*signal*statement can appear as only the last statement in a monitor procedure. Suggest how the implementation described in Section 6.7 can be simplified.

Since the signal statement can only appear as the last statement in a monitor procedure, the signaling process can exit the monitor immediately after executing the signal statement. Thus, there is no need for the semaphore next and the integer variable next_count.

- Each external procedure F will be replaced by
wait(mutex)

body of F

signal(mutex)

- The operation x.wait can be implemented as
x-count := x-count + 1;

signal(mutex);

wait(x-sem);

x-count := x-count - 1;

- The operation x.signal can be implemented as
if x-count > 0

then begin

signal(x-sem);

exit monitor

end

else

signal(mutex)

- (aka 7.8) Consider a system consisting of four resources of the same type, being shared by three processes, each of which needs at most two resources. Prove that the system is deadlock free.

Proof by contradiction. Suppose the system is deadlocked. This implies that each process is holding (at least) one resource and is waiting for one more. (By the circular wait necessary condition.) Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources and therefore it will return its resources when done.

- Consider the following snapshot of a system:

Available

A

B

C

D2

1

0

0

Max

Allocation

A

B

C

D

A

B

C

D

P_{0}0

0

1

2

0

0

1

2

P_{1}2

7

5

0

2

0

0

0

P_{2}6

6

5

6

0

0

3

4

P_{3}4

3

5

6

2

3

5

5

P_{4}0

6

5

2

0

3

3

2

Answer the following questions using the banker's algorithm:

- What is the content of the matrix
Need?

Need

A

B

C

D

P_{0}0

0

0

0

P_{1}0

7

5

0

P_{2}6

6

2

2

P_{3}2

0

0

1

P_{4}0

3

2

0

- Is the system in a safe state? (If so, show a safe sequence; if not, be specific about the violating conditions.)
Yes. {

P_{0},P_{3},P_{4},P_{1},P_{2}}

- If a request from process P2 arrives for (0, 1, 0, 0), can the request be granted immediately? (Be sure and justify your answer.)

If the given request is granted, we have the following snapshot:

Allocation

A

B

C

D

P_{0}0

0

1

2

P_{1}2

0

0

0

P_{2}0

1

3

4

P_{3}2

3

5

5

P_{4}0

3

3

2

Need

A

B

C

D

P_{0}0

0

0

0

P_{1}0

7

5

0

P_{2}6

5

2

2

P_{3}2

0

0

1

P_{4}0

3

2

0

and

Available

A

B

C

D2

0

0

0

We can add to the safe sequence {

P_{0},P_{3},P_{4}}, resulting in

Available

A

B

C

D4

6

9

9

but at this point neither

P_{1}norP_{2}can be completed, so if we grantP_{2}'s request we end up with an unsafe state, so the request cannot be granted immediately.