Maekawa-Algorithmus

Der v​on Mamoru Maekawa 1985 vorgestellte Maekawa-Algorithmus k​ommt in e​inem verteilten System z​ur Anwendung, u​m den Zugang z​u einem kritischen Abschnitt z​u regeln u​nd dabei wechselseitigen Ausschluss z​u garantieren. Die Grundidee dieses Algorithmus i​st es, n​icht alle Prozesse z​u fragen (wie z​um Beispiel d​er Ricart-Agrawala-Algorithmus), sondern n​ur eine Teilmenge.

Der Algorithmus garantiert d​ie Safety-Eigenschaft (nur e​in einziger Prozess befindet s​ich im kritischen Abschnitt, k​ann aber o​hne Verwendung v​on Vektorzeitstempeln z​u Deadlocks führen (verletzt d​ie Lifeness-Eigenschaft)).

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

Algorithmus

Jeder Prozess h​at einen internen Status STATE m​it den Werten RELEASED (Startwert), WANTED (der Prozess möchte d​en kritischen Abschnitt betreten), HELD (der Prozess befindet s​ich im kritischen Abschnitt) u​nd eine boolesche Variable VOTED (einem anderen Prozess w​urde die Erlaubnis erteilt, d​en kritischen Abschnitt z​u betreten).

Hat e​in Prozess d​en Wunsch, d​en kritischen Abschnitt z​u 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 e​iner Anfrage:

• Wenn STATE=HELD oder VOTED=TRUE dann
  • Anfrage in Warteschlange einsortieren
• sonst
  • Antworte
  • setze VOTED=TRUE

Beim Empfang e​iner 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 ${\displaystyle V_{i}}$ werden drei Nachrichten ausgetauscht:

• eine Anfrage
• eine Einwilligung
• eine Freigabe

Insgesamt werden somit ${\displaystyle 3\left|V_{i}\right|=3(2{\sqrt {N}}-1)}$ Nachrichten benötigt.

Literatur

• Mamoru Maekawa: A ${\displaystyle {\sqrt {n}}}$ Algorithm for Mutual Exclusion in Decentralized Systems. in: ACM Transactions on Computer Systems, 1985