Question

Assuming that there are 9 processes in a distributed system numbered p1, p2, ..., p9. Describe a situation where deadlock may occur when using Maekawa’s algorithm in this system.

Answer 1

Meakawas algorithm has 3 msgs reply,request and release msg

every site can send a request msg only from the subset sites

request subsets of every site is selected such that request subsets are disjoint , at least one element will be in common

one time one reply msg can be sent by a site

a site can send a reply msg only after getting release msg from a previous reply msg

to construct request sets we have 4 methods

m1: 2 request subsets are disjoint

m2: si belongs to Ri ie every site is under the request set

m3 : size of a request set is equal to k

M4:. Every site or process has k number of request set

Now to enter critical situation

All sites of request set wil get request msg

I will send reply msg to a request msg only when i have not sent any reply msg after a release msg

If not the request msg will be stored in a queue

Performance 3 rootN no of msgs ie root N no of msgs each for reply, request and response msg

The picture shows 9 processes in a distributive system

In all 5 distributions ie p4 to p1

P5 to p2

P6 to p3

P7to p9

P9 to p8 we come across deadlocks as. P4 sent reply msg to p1 and cannot send to any other process such as p2 and p2 will be deadlocked being waiting for reply msg from p1

Similarly p5 sends reply msg to p2 whereas p3 enters deadlock situation by waiting for rply msg from p5

P1 Waits for all 3 reply msgs from p1,p4 and p6

Thus enter deadlock by waiting for p6 reply msg which is already sent by p6 to p3

As according to meakawas algo one process can send only 1 reply msg at a time

P3 waits for reply msg from p5 and p5 has sent msg to p2 and so on.