Ricart–Agrawala algorithm: Difference between revisions

Revision as of 06:56, 20 September 2018

Latest revision as of 19:26, 15 November 2024

(17 intermediate revisions by 13 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>ack</math>release messages.<ref>{{cite journal|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|urls2cid=https://dl.acm.org/citation.cfm?id=3585371779615|ref=origpaper|doi-access=free}}</ref>. It was developed by computer scientists [[Glenn Ricart]] and [[Ashok Agrawala]].

==Algorithm==

Line 19 ⟶ 20:

* 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> on 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.

Line 35 ⟶ 36:

==See also==

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

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

* [[Maekawa's Algorithmalgorithm]]

* [[Suzuki-KasamiSuzuki–Kasami algorithm]]

* [[Raymond's Algorithmalgorithm]]

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

*[[Naimi-Trehel's Algorithm]]

==References==

{{RefListReflist}}

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

{{DEFAULTSORT:Ricart-Agrawala Algorithm}}