Consider a system with N blocks of storage, each of which holds one unit of info

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)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.