---
title: "Ricart-Agrawala mutual exclusion"
subject: "Distributed System"
chapter: 6
key: "semester_7/distributed_system:ricart-agrawala"
source: https://www.bctengineer.com/q/semester_7/distributed_system/ricart-agrawala
site: BCT Engineering
---

# Ricart-Agrawala mutual exclusion

Distributed System · Chapter 6: Coordination and Agreement

- Asked in: 2075 Asoj, 2+6 marks; Model question (asked 2 times)
- Video: [Ricart Agrawala Mutual Exclusion algorithm in Distributed Systems Synchronization](https://www.youtube.com/watch?v=EcoTlY0GXrA) — Simplified Computer Science Concepts-Prof. Rutuja
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/ricart-agrawala
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6

## Question

Explain the non-token based Ricart-Agrawala mutual exclusion algorithm along with an example. (How does mutual exclusion maintain synchronization in distributed system?)

## Short answer

Ricart-Agrawala uses Lamport timestamps. To enter CS, a process sends REQUEST to all others. Receivers reply immediately if idle or with larger timestamp, else defer. Process enters after all replies. Example: P1 (timestamp 3,1) and P2 (3,2) request; P1 wins, P2 defers, P1 replies after exit. Mutual exclusion is maintained by total ordering of requests.

## Answer

#### 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.
```text
 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. When can a process in Ricart-Agrawala enter the critical section?
   A. After receiving REPLY from all N-1 other processes
   B. After receiving REPLY from a majority of processes
   C. After sending REQUEST to all processes
   D. After the coordinator grants it
   Answer: A. It needs permission (REPLY) from every one of the other N-1 processes. (Key point: Entry condition)

2. Process Pi is in state WANTED and receives REQUEST from Pj. What does it do?
   A. Always replies immediately
   B. Replies immediately only if Pj's timestamp is smaller than its own; otherwise defers
   C. Always defers until it has left the CS
   D. Replies only if Pj has the larger timestamp
   Answer: B. Pi compares timestamps: the earlier (smaller) request wins, so Pi replies if Tj < Ti and defers otherwise. (Key point: Reply rule when WANTED)

3. What does a process do on leaving the critical section?
   A. Sends RELEASE to a coordinator
   B. Passes a token to its successor
   C. Sets state RELEASED and sends REPLY to all in its deferred queue
   D. Discards the deferred requests
   Answer: C. Deferred requests are answered on exit, allowing waiting processes to proceed. (Key point: Deferred replies)

4. How many messages does Ricart-Agrawala need per critical section entry?
   A. 3(N-1)
   B. 3
   C. N
   D. 2(N-1)
   Answer: D. N-1 REQUEST messages plus N-1 REPLY messages gives 2(N-1). (Key point: Message count)

## Related in Distributed System

- [Centralized vs Ricart-Agrawala algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acentral-vs-ra-compare) — Distributed System, chapter 6
- [Token ring mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atoken-ring-mutex) — Distributed System, chapter 6, asked 3×
- [Ricart-Agrawala performance issues](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Ara-performance-alternate) — Distributed System, chapter 6
- [Lamport algorithm for mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-mutex) — Distributed System, chapter 6
- [Mutex requirements; token vs non-token](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Amutex-requirements-compare) — Distributed System, chapter 6
- [Vector clock synchronization algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Avector-clock-algorithm) — Distributed System, chapter 5, asked 2×

## Related in other subjects

- [Mutual exclusion via sleep and wake](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Amutual-exclusion-sleep-wake) — Embedded System, chapter 6
- [Critical section; mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Acritical-section-mutual-exclusion-pc) — Operating System, chapter 3
- [Race condition; mutual exclusion requirements](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-mutual-exclusion-requirements) — Operating System, chapter 3
- [Semaphore for mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Asemaphore-enforce-mutual-exclusion) — Operating System, chapter 3