Suppose processes P1, P2 and P3 share the critical section. P1 sends a request to enter the critical section at logical time 1. P2 sends a request to enter the critical section at logical time 2. P3 sends a request to enter the critical section at logical time 3. Apply Ricart and Agrawala’s algorithm to demonstrate how mutual exclusion is achieved.

Question

What will be an ideal response?

Answer 1

We demonstrate how this algorithm works in five steps.
a. When P1 sends a request to P2 and P3, P2 and P3 reply to P1, because neither of
them is in the critical section.Hence P1 is ready to enter the critical section.
b. Suppose P2 sends a request to P1 and P3 before P1 enters the critical section.When
P1 receives P2’s request, P1 compares the time stamp of P2 against its own and adds
P2 to P1’s request queue.When P3 receives P2’s request, P3 replies to P2.Then P1
enters the critical section.
c. Suppose P3 sends a request to P1 and P2 after P1 enters the critical section.When P1
receives P3’s request, P1 adds P3 to P1’s request queue and does not reply, because
P1 is already in the critical section.When P2 receives P3’s request, P2 compares the
time stamp of P3 against its own and adds P3 to the request queue.
d. When P1 exits the critical section, it replies to P2 and P3. Now P2 has replies from
both P1 and P3.Note that P2 obtained P3’s reply in step b.Then P2 enters the critical
section.
e. When P2 exits the critical section, it replies to P3. Now P3 has replies from both P1
and P2.Then P3 enters the critical section.