Ricart-Agrawala-Algorithmus

Der Ricart-Agrawala-Algorithmus kommt in einem verteilten System zur Anwendung um den Zugang zu einem kritischen Abschnitt zu regeln und dabei wechselseitigen Ausschluss zu garantieren. Dabei basiert der Algorithmus auf dem Nachrichtenaustausch und der Wahl von Nummern durch die Knoten eines Computernetzwerkes. Er wurde von Glen Ricart und Ashok K. Agrawala im Jahr 1981 veröffentlicht.

Wenn ein Rechner in einem Netzwerk einen kritischen Abschnitt betreten möchte, muss dieser an alle anderen Rechner im Netzwerk eine Anfrage-Nachricht mit einer selbst gewählten Nummer senden. Alle Knoten vergleichen dann ihre gewählte Nummer mit den empfangenen. Der Rechner mit der kleinsten gewählten Nummer darf den kritischen Abschnitt betreten. Ist ein Rechner im Besitz einer höheren Nummer, so muss er den Rechnern mit kleinerer gewählter Nummer den Vortritt lassen und sendet eine entsprechende Antwort. Andernfalls unterbleibt die Antwort und der Rechner mit der größeren Nummer wird zu einer Liste hinzugefügt mit dem Zweck später benachrichtigt zu werden. Wenn ein Rechner Antwort-Nachrichten von allen anderen Rechnern eines Netzwerkes erhalten hat, kann dieser wie gewünscht den kritischen Bereich betreten.

Algorithmus

Der Algorithmus, der auf jedem Rechner des Netzwerkes abläuft, unterteilt sich in zwei parallel ausgeführte Prozesse. Der eine Hauptprozess ist für die Anfrage zur Erteilung der Erlaubnis, den kritischen Abschnitt betreten zu dürfen, verantwortlich und betritt daraufhin letztlich den Abschnitt. Ein zweiter Prozess empfängt die Antwort-Nachrichten der anderen Rechner.

Im Hauptprozess wird zunächst eine Nummer gewählt. Diese wird an alle anderen Rechner in einer Anfrage-Nachricht übermittelt und danach auf das Eintreffen der Antwort-Nachrichten gewartet. Sind alle Antwort-Nachrichten eingetroffen, wird der kritische Abschnitt betreten.

Doch auch die anderen Rechner des Netzwerkes haben möglicherweise das Interesse, den kritischen Abschnitt zu betreten und senden ebenfalls eine Anfrage-Nachricht mit ihrer Nummer. Parallel wird von jedem Rechner ein zweiter Prozess ausgeführt. Dieser empfängt ständig die Anfrage-Nachrichten der jeweils anderen Rechner und vergleicht die Nummern. Ist bei einem Vergleich die eigene gewählte Nummer größer als die des anderen Rechners, wird diesem Rechner sofort eine Antwort-Nachricht gesendet, so dass er den kritischen Abschnitt betreten kann. Ist die eigene Zahl hingegen die kleinere, wird der Rechner in einer „Verzögerungs-Liste“ vermerkt.

Sofern ein Rechner den kritischen Abschnitt betreten konnte, sendet dieser nach dem Verlassen des Abschnittes innerhalb des Hauptprozesses Antwort-Nachrichten an alle Prozesse, die in der „Verzögerungs-Liste“ vermerkt sind.

Nachrichtenkomplexität

In einem Netzwerk mit $n$ Knoten fallen für jeden Knoten, der den kritischen Abschnitt betreten will $2*(n-1)$ Nachrichten an: Es werden $(n-1)$ Anfragenachrichten versendet und ebenfalls $(n-1)$ Antwortnachrichten empfangen. Folglich entstehen $n*(2*(n-1))$ Nachrichten, wenn jeder der $n$ Knoten den kritischen Abschnitt betreten will. Für den schlimmsten Fall, dass alle Prozesse den kritischen Abschnitt betreten wollen, kann die Nachrichtenkomplexität des Algorithmus also mit Hilfe der Landau-Symbole als ${\mathcal {O}}(n^{2})$ ausgedrückt werden. Durch den quadratischen Nachrichtenaufwand ist der Algorithmus in größeren Netzwerken ineffizient.

Beispiel

Angenommen, es existieren die drei Rechner A, B und C. Jeder wählt zufällig eine Nummer:

A: 3
B: 7
C: 9

Nach der Wahl senden sich alle gegenseitig die Nummern in Nachrichten zu. Zum Beispiel sendet A 3 an B und C. Die anderen verfahren entsprechend. Da A die kleinste Nummer gewählt hat, fügt dieser die anderen beiden zu seiner „Verzögerungs-Liste“. Gleichzeitig erhält er von B und C Antwort-Nachrichten und kann den kritischen Abschnitt betreten. B erhält eine Antwort-Nachricht von C, da B's Wert kleiner als der von C ist. Außerdem fügt B den Rechner C zu seiner „Verzögerungs-Liste“. Da B jedoch eine größere Zahl gewählt hat als A, sendet er an A eine Antwort-Nachricht. Wenn A den kritischen Abschnitt verlassen hat, sendet A an alle Rechner in seiner „Verzögerungs-Liste“ die Antwort-Nachricht. Der Rechner C mit der größten Nummer kann nur die Antwort-Nachrichten an A und B schicken und muss dann warten, bis er die Antwort-Nachrichten von A und B erhalten hat, nachdem diese jeweils den kritischen Abschnitt verlassen haben.

Literatur

G. Ricart, A. K. Agrawala: An Optimal Algorithm for Mutual Exclusion in Computer Networks. Communications of the ACM, Januar 1981, Ausgabe 24, Nummer 1, S. 9–17
Mordechai Ben-Ari: Principles of Concurrent and Distributed Programming. 2. Auflage. 2006. S. 216 ff., ISBN 0-321-31283-X