Ricart–Agrawala algorithm: Difference between revisions

Revision as of 11:06, 16 September 2012

Latest revision as of 19:26, 15 November 2024

(41 intermediate revisions by 27 users not shown)

Line 1:

{{Short description|Algorithm for mutual exclusion on a distributed system}}

{{Unreferencedmore citations needed|date=December 2009}}

The '''Ricart-AgrawalaRicart–Agrawala Algorithmalgorithm''' 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 <math>release messages.</mathref>{{cite messagesjournal|last1=Ricart|first1=Glenn|last2=Agrawala|first2=Ashok K.|title=An optimal algorithm for mutual exclusion in computer networks|journal=Communications of the ACM|date=1 January 1981|volume=24|issue=1|pages=9–17|doi=10.1145/358527.358537|s2cid=1779615|ref=origpaper|doi-access=free}}</ref> It was developed by computer scientists [[Glenn Ricart]] and [[Ashok Agrawala]].

==Algorithm==

=== Terminology ===

* A ''site'' is any computing device which is runningruns the Ricart-Agrawala Algorithm

* The ''requesting site'' is the site which is requesting entryto intoenter the critical section.

* The ''receiving site'' is every other site which is receiving thea request from the requesting site.

===Algorithm===

''' Requesting Site: '''

* Sends a message to all sites. This message includes the site's name, and the current timestamp of the system according to its [[logical clock]] (''which is assumed to be synchronized with the other sites'')

''' Receiving Site: '''

* Upon reception of a request message, immediately sendsending a timestamped ''reply'' message if and only if:

:* the receiving process is not currently interested in the critical section OR

:* the receiving process has a lower priority (''usually this means having a later timestamp)

* Otherwise, the receiving process will defer the reply message. This means that a reply will be sent only after the receiving process has finished using the critical section itself.

''' Critical Section: '''

* Requesting site enters its critical section only after receiving all reply messages.

* Upon exiting the critical section, the site sends all deferred reply messages.

===Performance===

* NumberMax number of network messages;: <math>2*(N-1)</math>

* Synchronization Delays: One message propagation delay

===Common Optimizationsoptimizations===

Once site <math>P_i</math> has received a <math>reply</math> message from site <math>P_j</math>, site <math>P_i</math> may enter the critical section multiple times without receiving permission from <math>P_j</math> untilon subsequent attempts up to the moment when <math>P_i</math> has sent a <math>reply</math> message to <math>P_j</math>. This is called Roucairol-Carvalho optimization or Roucairol-Carvalho algorithm.

This optimization is called Roucairol & Carvalho Optimization.

===Problems===

Line 36:

==See also==

* [[Lamport's bakery algorithm|Lamport's Bakery Algorithm]]

* [[Lamport's Distributeddistributed Mutualmutual Exclusionexclusion Algorithmalgorithm]]

* [[Maekawa's Algorithmalgorithm]]

* [[Suzuki-Kasami'sSuzuki–Kasami Algorithmalgorithm]]

* [[Raymond's Algorithmalgorithm]]

* [[Naimi–Trehel algorithm|Naimi–Trehel's algorithm]]

*[[Naimi-Trehel's Algorithm]]

==References==

{{Reflist}}

*Maekawa, M., Oldehoeft, A., Oldehoeft, R.(1987). Operating Systems: Advanced Concept.Benjamin/Cummings Publishing Company, Inc.

{{DEFAULTSORT:Ricart-Agrawala Algorithm}}

[[Category:Distributed algorithms]]

[[de:Ricart-Agrawala-Algorithmus]]

[[fr:Algorithme de Ricart et Agrawala]]