• Ricart and agarwala’s algorithm requires total ordering of all events in the system.
• When a process wants to enter a critical section, it sends a request message to all other processes.

The message contains the following information:

i.The process identifier of the process.

ii.The name of the critical section that process wants to enter.

iii.A unique timestamp generated by the process for the request message.

• On receiving a request message, a process either immediately sends back a reply message to the sender or defers sending a reply based on the following rules: i.If the receiver is not in the critical section nor is waiting for its turn to enter the critical section, it sends back an OK message to the sender.

ii.If the receiver process is itself currently in the critical section, it does not reply instead it queues the request message.

iii.If the receiver process wants to enter the critical and is waiting for its turn to enter the critical section, it compares the timestamp in the incoming message with the timestamp in its own request message that it has sent to other processes. The lowest one wins. If the incoming message is lower the receiver, the receiver sends back an OK message. If its own message has a lower timestamp, the receiver queues the incoming requests and sends nothing.

• After requests are sent for permission to enter a critical region, a process sits back and aits until all processes have permissions
• It enters the critical section as soon as it has received reply messages from all processes. After it finishes executing in the critical section, it sends OK message to all processes in its queue and deletes them from its queue.
• Example:

• In fig (a) there are four processes P1, P2, P3 and P4. While process P4 is in critical section, processes P1 and P2 want to enter the same critical section. To get permission from other processes, processes P1 and P2 send request messages with the timestamps 6 and 4 respectively to other processes.
• In fig (b).Since process P4 is in the critical section, it does not send a reply message to P1 and P2 and enters them in its queue. Process P3 is currently not interested in the critical section, so it sends OK messages to both P1 and P2. Process P2 defers sending a reply message to P1 and enters P1 in its queue because the timestamp (4) in its own request message is less than the timestamp (6) in P1’s request message but P1 replies to P2 as the timestamp (6) in its own request message is greater than the timestamp (4) in P2’s request message.

• In fig (c) when process P4 exits the critical section, it sends an OK message to all processes in its queue. Since process P2 has received OK message from all other processes, it enters the critical section. However, process P1 continues to wait since it has not yet received a reply message from the process P2.

• In fig (d), when process P2 exits the critical section, it sends an OK message to P1. Since process P1 has received a reply message from all other processes, it enters the critical section.
• Advantages: Mutual exclusion is guaranteed as a process can enter its critical section only after getting permission from all processes, freedom from starvation since entry to critical section is scheduled according to the timestamp.
• Disadvantages: Algorithm is suitable only for small group of processes, identity of all processes is needed making it complex.