In: Computer Science
a. The buffer is declared to be an array of shared elements of type T. Another array defines the number of input elements available to each process. Each process keeps track of the index j of the buffer element it is referring to at the moment.
var buffer: array 0..max-1 of shared T;
available: shared array 0..n-1 of 0..max;
"Initialization"
var K: 1..n-1;
region available do begin
available(0) := max;
for every k do available (k) := 0;
end
"Process i"
var j: 0..max-1; succ: 0..n-1; begin
j := 0; succ := (i+1) mod n;
repeat
region available do
await available (i) > 0;
region buffer(j) do consume element;
region available do
begin
available (i) := available(i) - 1;
available (succ) := available (succ) + 1;
end
j := (j+1) mod max;
forever
end
In the above program, the construct region defines a critical region using some appropriate mutual-exclusion mechanism. The notation
region v do S
Means that at most one process at a time can enter the critical region associated with variable v to perform statement S
b. A deadlock is a situation in which:
P0 waits for Pn-1 AND
P1 waits for P0 AND
. . . . .
Pn-1 waits for Pn-2
Because
(available (0) = 0) AND
(available (1) = 0) AND
. . . . .
(available (n-1) = 0)
But if max > 0, this condition cannot hold because the critical regions satisfy the following invariant:
ut if max > 0, this condition cannot hold because the critical regions satisfy the following invariant: