Ricart and Agrawala's Algorithm for Mutual Exclusion
The Ricart-Agrawala Algorithm is a distributed system algorithm for achieving mutual exclusion without the need for release messages, developed by Glenn Ricart and Ashok Agrawala. The algorithm involves processes sending timestamped requests to enter a critical section, with careful handling of replies to ensure mutual exclusion.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Ricart and Agrawalas Algorithm Lowkya Pothineni
Abstract: The Ricart- Agrawala Algorithm is an algorithm for mutual exclusion on a distributed system. This algorithm is an extension and optimization of Lamport's Distributed Mutual Exclusion Algorithm, by removing the need for release messages. It was developed by Glenn Ricart andAshokAgrawala.
Algorithm: On initialization state:= RELEASED; To enter the section state:= WANTED; Multicast request to all processes; processing of incoming requests deferred here T:= request s timestamp; Wait until (number of replies received = (N 1)); state:= HELD; On receipt of a request <Ti, pi> at pj (i j) if (state= HELD or (state= WANTED and (T, pj) < (Ti, pi) )) then queue request from pi without replying; else reply immediately to pi; end if To exit the critical section state:= RELEASED; reply to any queued requests;
Steps how Algorithm works: Process requesting the Critical Section(CS): when a process wants to enter the CS, it sends a timestamped request to all other processes. When a process receives a request: if it is neither requesting nor executing the CS, it returns a reply (not timestamped). If it is requesting the CS, but the timestamp on the incoming request is smaller than the timestamp on its own request, it returns a reply which means the other process requested first. otherwise, it defers answering the request.
Process executing the CS: A process enters the CS when it has received a reply from all other processes in the system. Process releasing the CS: When a process leaves the CS, it: Sends a reply message to all the deferred requests. Process with next earliest request will now received its last reply message and enter the CS.
31 q3 not attempting to enter, p1 and p2 request entry simultaneously q3 replies immediately q2 receives request from q1, timestamp(q2) < timestamp(q1), therefore q2 does not reply q1 sees its timestamp to be larger than that of the request from q2, hence it replies immediately and q2 is granted access q2 will reply to q1 s request after exiting the critical section
Evaluation: Message complexity : 2(N 1) (N 1) reply (N 1) request Synchronization delay : 1 T ( just one round-trip time )
Execution: The results of the experiment for Ricart Agrawala Algorithm shows the implementation of the algorithm. The end result is still yet to be obtained However I am trying to obtain the relation between the number of processes and the messages trying to access the CS.
AdvantagesandDisadvantages: Advantages: Completely distributed and decentralized. Disadvantages: Every node is a single-point of failure. Slow and costly. For each request O(N) messages are needed.
Future Research: Ricart Agrawala can be extended to work on practical network applications. The correctness of the Ricart Agrawala Algorithm should not be affected when inserting new nodes into the network. In practical network insertion of new nodes . Whenever new nodes are added it should be able to update the sequence number, request received and the requests it is going to reply back or acknowledge. Ricart Agrawala can be extended to solve Dining Philosopher's Problem where there are several sites and several number of processes working in each site.
References: Maekawa, M.,Oldehoeft, A.,Oldehoeft, R.(1987). Operating Systems: Advanced Concept. Benjamin/Cummings Publishing Company, Inc. Mukesh Singhal "Advanced Concepts in Operating Systems . Google.co.in Wikipedia.org Referred most and obtained information from http://www.cs.kent.edu/~rkhadse/projects/aos/ricart_agrawala/Rah ul
