Ricart-Agrawala mutual exclusion

Mutual exclusion and synchronization

Mutual exclusion makes sure that only one process at a time executes its critical section (CS), so shared resources are used consistently. In a distributed system there is no shared memory or common clock, so processes coordinate by messages. A logical ordering of the requests (Lamport timestamps) gives the order in which the CS is granted, which keeps the processes synchronised and prevents conflicts, deadlock and starvation.

Ricart-Agrawala algorithm (non-token based)

It is a permission-based algorithm that uses Lamport logical clocks. A process needs the permission (REPLY) of all other N−1 processes to enter the CS.

Each process Pi has a logical clock, a state (RELEASED, WANTED, HELD) and a queue of deferred requests.

1. To enter the CS: Pi sets state = WANTED, increments its clock, timestamps the request T = (Ci, i) and sends REQUEST(T) to all other processes.
2. On receiving REQUEST(Tj) from Pj, process Pi:
   • if state is HELD: defers the reply (adds to its queue);
   • if state is RELEASED: sends REPLY immediately;
   • if state is WANTED: compares timestamps; if the incoming request has the smaller timestamp (Tj < Ti), it sends REPLY, otherwise it defers.
3. Pi enters the CS after receiving REPLY from all N−1 processes (state = HELD).
4. On exit, Pi sets state = RELEASED and sends REPLY to all processes in its deferred queue.

Example

Three processes P1, P2, P3. P1 and P2 request at about the same time with timestamps (3,1) and (3,2); P3 is idle.

 P1 --REQ(3,1)--> P2, P3
 P2 --REQ(3,2)--> P1, P3
 P3: RELEASED, replies to both at once.
 P2 gets REQ(3,1): (3,1) < (3,2), so P2 replies to P1.
 P1 gets REQ(3,2): P1's own is smaller, so it defers.
 P1 has 2 replies, enters CS; on exit replies to P2.
 P2 then enters CS.

Ties go to the lower process id.

Performance: 2(N−1) messages per entry (N−1 requests + N−1 replies), synchronisation delay of one message time. Failure of any process blocks all, since all replies are needed.