Due: November 10
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, P0, P1, and P2. Let turn be 0 initially. Now let P0 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.
Suppose that the value of semaphore S = 1 and processes P1 and P2 execute wait(S) concurrently according to the following timeline:
- T0: P1 determines that value of S = 1
- T1: P2 determines that value of S = 1
- T2: P1 decrements S by 1 and enters critical section
- T3: P2 decrements S by 1 and enters critical section
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)
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.
Available A
B
C
D
2
1
0
0
Max
Allocation
A
B
C
D
A
B
C
D
P0
0
0
1
2
0
0
1
2
P1
2
7
5
0
2
0
0
0
P2
6
6
5
6
0
0
3
4
P3
4
3
5
6
2
3
5
5
P4
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
P0
0
0
0
0
P1
0
7
5
0
P2
6
6
2
2
P3
2
0
0
1
P4
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. {P0, P3, P4, P1, P2}
- 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
P0
0
0
1
2
P1
2
0
0
0
P2
0
1
3
4
P3
2
3
5
5
P4
0
3
3
2
Need
A
B
C
D
P0
0
0
0
0
P1
0
7
5
0
P2
6
5
2
2
P3
2
0
0
1
P4
0
3
2
0
and
Available A
B
C
D
2
0
0
0
We can add to the safe sequence {P0, P3, P4}, resulting in
Available A
B
C
D
4
6
9
9
but at this point neither P1 nor P2 can be completed, so if we grant P2's request we end up with an unsafe state, so the request cannot be granted immediately.