Given a distributed system with four processes P1, P2, P3, and P4 where mutual e

Question

Given a distributed system with four processes P1, P2, P3, and P4 where mutual exclusion is enforced using Ricart-Agrawala's algorithm. Consider the scenario below and trace the steps of the algorithm in terms of different messagesuntil all three have been granted access right.

Both P1, P2 and P3 are requesting for critical section while P4 has no need at this time.

The timestamp of P1's request is 15, P2’s request is 36 and that of P3 is 65.

a. Does the critical section is accessed according to the increasing order of timestamps, namely ME3 under Ricart-Agrawala algorithm?

b. Does the same hold true in Maekawa’s algorithm? If not, how to adapt this algorithm to make Maekawa’s algorithm also meet ME3 by using logical /vector clock?

Explanation / Answer

a) As per Ricart-Agrawala algorithm the request are replied to on the basis of logical timestamp.

Upon reception of a request message, immediately send a timestamped reply message if and only if:

the receiving process is not currently interested in the critical section OR

the receiving process has a lower priority (usually this means having a later timestamp)

So in this case Critical Section entry will be in the order P1 then P2 and then P3

b) Maekawa’s algorithm : is not based on the timestamp rather is based on the reciept of permission from all the member of the quorum and priority.

So let there be three subsets S0 and S1 and S2

S0={P1,P4}

S1={P2,P4}

S2 ={P3,P4}

Now P1 sends a request a time 15 P4 has no other request at that time. It replies to P1 and P1 can enter Critical Section.

P1 after it's work sends release message to P4.

When P2 requests at a later time 36 if P4 has recieved the release message from P1 then it replies to P2.If not It will send enquire to P1 to see if it has all the permissions in place and since P1 only required permission from P4 it will put P2 's request to queue.

same happens to P3 .

Thus P1 P2 P3 in this fashion of execution exhibit ME3

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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