Maekawa Algorithmus

Der Maekawa Algorithmus kommt in einem verteilten System zur Anwendung, um den Zugang zu einem kritischen Abschnitt zu regeln und dabei wechselseitigen Ausschluss zu garantieren. Die Grundidee dieses Algorithmuses ist es, nicht alle Prozesse zu fragen (wie z.B. 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 deadlocks führen (verletzt die Lifeness-Eigenschaft)).

Dabei benutzt man sog. Voting Sets, V_i. Jeder Prozess P_i hat ein Voting Set ($P_i \in V_i$) und liegt in mindestens 2 Voting Sets (aber in genau M). In einem Voting Set befinden sich $\left|V_i\right| = K \forall i$ und $\forall i \forall j [V_i \bigcap V_j \ne \empty ]$ (d.h. 2 verschiedene Voting-Sets haben mindestens ein gemeinsames Element).

Als Annäherung für das Optimum (möglichst kleines K) wird $K \approx \sqrt{N}$ benutzt. Man ordnet die Prozesse in einer $\sqrt{N}\times \sqrt{N}$ Matrix an und definiert ein Voting Set als alle Prozesse die in der gleichen Spalte und Zeile liegen wie P_i.

Bandbreite proportional zu $2K+K=3K\approx 3\sqrt{N}$ Nachrichten

Algorithmus

Jeder Prozess hat einen internen Status STATE mit den Werten RELEASED (Startwert), WANTED, HELD und eine boolesche Variable VOTED.

Hat ein Prozess den Wunsch, den kritischen Abschnitt zu betreten:

• setze STATE=WANTED
• Request-Nachricht an alle Prozesse im Voting Set
• warte bis K Antworten erhalten
• setze STATE=HELD

Beim Verlassen:

• setze STATE=RELEASED
• Release-Nachricht an alle Prozesse im Voting Set

Beim Empfang einer Request Nachricht:

• Wenn STATE=HELD oder VOTED=TRUE dann
  • Queue Request
• sonst
  • Antworte
  • setze VOTED=TRUE

Beim Empfang einer Release Nachricht:

• Ist Queue leer
  • setze VOTED=FALSE
• sonst
  • Sende Antwort an den ersten Prozess in der Queue (und entferne ihn davon)
  • setze VOTED=TRUE