imported>Prüm: /* Literatur */

2021-05-09T16:11:20Z

Literatur

Neue Seite

Der von [[Mamoru Maekawa]] 1985 vorgestellte '''Maekawa-Algorithmus''' kommt in einem [[Verteiltes System|verteilten System]] zur Anwendung, um den Zugang zu einem [[Kritischer Abschnitt|kritischen Abschnitt]] zu regeln und dabei [[Mutex|wechselseitigen Ausschluss]] zu garantieren. Die Grundidee dieses Algorithmus ist es, nicht alle Prozesse zu fragen (wie zum Beispiel der [[Ricart-Agrawala-Algorithmus]]), sondern nur eine Teilmenge.

Der Algorithmus garantiert die Safety-Eigenschaft (nur ein einziger Prozess befindet sich im kritischen Abschnitt, kann aber ohne Verwendung von Vektorzeitstempeln zu [[Deadlock (Informatik)|Deadlocks]] führen (verletzt die Lifeness-Eigenschaft)).

Dabei benutzt man Voting Sets, <math>V_i</math>. Jeder Prozess <math>P_i</math> hat ein Voting Set (<math>P_i \in V_i</math>) und liegt in mindestens 2 Voting Sets. In jedem Voting Set befinden sich K Prozesse (<math>\forall i \left|V_i\right| = K</math>), und zwei verschiedene Voting Sets haben mindestens ein gemeinsames Element (<math>\forall i \forall j [V_i \bigcap V_j \ne \empty ]</math>)
Als Annäherung für das Optimum (möglichst kleines K) wird <math>K = 2\sqrt{N}-1</math> benutzt. Man ordnet die Prozesse in einer <math>\sqrt{N}\times \sqrt{N}</math> Matrix an und definiert das Voting Set <math>V_i</math> als alle Prozesse die in der gleichen Spalte oder Zeile liegen wie <math>P_i</math>.

== Algorithmus ==
Jeder Prozess hat einen internen Status STATE mit den Werten RELEASED (Startwert), WANTED (der Prozess möchte den kritischen Abschnitt betreten), HELD (der Prozess befindet sich im kritischen Abschnitt) und eine boolesche Variable VOTED (einem anderen Prozess wurde die Erlaubnis erteilt, den kritischen Abschnitt zu betreten).

'''Hat ein Prozess den Wunsch, den kritischen Abschnitt zu betreten:'''
* setze STATE=WANTED
* Anfrage (Request) an alle Prozesse im Voting Set
* warte bis K Antworten erhalten
* setze STATE=HELD und betrete den kritischen Abschnitt

'''Beim Verlassen:'''
* setze STATE=RELEASED
* Freigabe (Release) an alle Prozesse im Voting Set

'''Beim Empfang einer Anfrage:'''
* Wenn STATE=HELD oder VOTED=TRUE dann
** Anfrage in Warteschlange einsortieren
* sonst
** Antworte
** setze VOTED=TRUE

'''Beim Empfang einer Freigabe:'''
* Ist die Warteschlange leer
** setze VOTED=FALSE
* sonst
** Sende Antwort an den ersten Prozess in der Warteschlange (und entferne ihn daraus)
** setze VOTED=TRUE

== Nachrichtenkomplexität ==

Mit jedem Prozess in <math>V_i</math> werden drei Nachrichten ausgetauscht:

* eine Anfrage
* eine Einwilligung
* eine Freigabe

Insgesamt werden somit <math>3\left|V_i\right| = 3(2\sqrt{N}-1)</math> Nachrichten benötigt.

== Literatur ==

* Mamoru Maekawa: ''A <math>\sqrt{n}</math> Algorithm for Mutual Exclusion in Decentralized Systems''. in: [[Association for Computing Machinery|ACM]] Transactions on Computer Systems, 1985

[[Kategorie:Algorithmus]]
[[Kategorie:Verteiltes Rechnen]]

Maekawa-Algorithmus - Versionsgeschichte

imported>Prüm: /* Literatur */