Maekawa-Algorithmus

Der von Mamoru Maekawa 1985 vorgestellte 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 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 Deadlocks führen (verletzt die Lifeness-Eigenschaft)).

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

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

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 V_i werden drei Nachrichten ausgetauscht:

• eine Anfrage
• eine Einwilligung
• eine Freigabe

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

Literatur

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