Question

A pipeline algorithm is implemented so that a stream of data elements of type T produced by a process P0 passes through a sequence of processes P1, P2, ., Pn - 1, which operates on the elements in that order.
a. Define a generalized message buffer that contains all the partially consumed data elements and write an algorithm for process Pi (0 ≤ i ≤ n - 1), of the form
repeat
receive from predecessor;
consume element;
send to successor:
forever
Assume P0 receives input elements sent by Pn - 1. The algorithm should enable the processes to operate directly on messages stored in the buffer so that copying is unnecessary.
b. Show that the processes cannot be deadlocked with respect to the common buffer.

Answer 1

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:

 

 

But if max > 0, this condition cannot hold because the critical regions satisfy the following invariant: