Consider a system with N blocks of storage, each of which holds one unit of info
ID: 3600445 • Letter: C
Question
Consider a system with N blocks of storage, each of which holds one unit of information (e.g. an integer,
character, or employee record). Initially, these blocks are empty and are linked onto a list called freelist.
Three processes communicate using shared memory in the following manner:
Shared Variables: freelist, list-1, list-2: block (where block is some data type to hold items)
PROCESS #1
var b: pointer to type block;
while (1)
{
b:= unlink(freelist);
produce_information_in_block(b);
link(b, list1);
}
PROCESS #2
var x,y: pointer to type block;
while (1)
{
x:=unlink(list-1);
y:=unlink(freelist);
use_block_x_to_produce info_in_y(x, y);
link(x, freelist);
link(y, list-2);
}
PROCESS #3
var c: pointer to type block;
while(1)
{
c:=unlink(list-2);
consume_information_in_block(c);
link(c, freelist);
}
Using the appropriate libraries, rewrite the pseudo-code as actual Unix/Linux processes, using semaphores to
implement the necessary mutual exclusion and synchronization. The solution must be deadlock-free and
concurrency should not be unnecessarily restricted. Further, you will have to implement a correct representation
of the three lists so that access to them is shared among the processes
Explanation / Answer
semaphore: mutex1, mutex2, mutex3: (1,1,1);
semaphore: freecnt, freemax, cnt1, cnt2: (n, n, 0,0);
{Process 1}
While (true) do
P (freemax) //lock freemax
P (freecnt) //lock freecnt
P (mutex1) //lock mutex
b = unlink (freelist) //unlinking the freelist
V (mutex1) // unlock mutex
Use b
P (mutex2) // lock mutex
link (b, list-1)
V (mutex2) //unlock mutex2
V (cnt1)
End (Process 1)
{Process 2}
While (true) do
P (cnt1)
P (mutex2)
x = unlink (list-1)
V (mutex2)
P (freecnt)
P (mutex1)
y = unlink (freelist)
V (mutex1)
V (freemax)
Use x & y
P (mutex1)
link (x, freelist)
V (mutex1)
V (freecnt)
P (mutex3)
link (y, list-2)
V (mutex3)
V (cnt2)
End (Process 2)
{Process 3}
While (true) do
P (cnt2)
P (mutex3)
c = unlink (list-2)
V (mutex3)
P (mutex1)
link (c, freelist)
V (mutex1)
V (freecnt)
End (Process 3)