Wederzijds uitsluitingsalgoritme van Peterson

Het wederzijds uitsluitingsalgoritme van Peterson is een algoritme dat ertoe dient een aantal componenten van een gedistribueerd programma dat een kritieke sectie bevat, zo te synchroniseren dat op ieder moment maar één component met de kritieke sectie bezig kan zijn.

Het probleem

Een gedistribueerd programma is een programma dat uit een aantal verschillende componenten bestaat die gelijktijdig kunnen worden uitgevoerd. Meestal bestaan er echter bepaalde bronnen die slechts door één component tegelijkertijd mogen worden aangesproken, bijvoorbeeld een stuk geheugen, een bestand of een randapparaat. Het deel van de component waarin zo'n bron wordt aangesproken wordt kritieke sectie genoemd en slechts één component mag zich tegelijkertijd in die kritieke sectie bevinden.

Om een voorbeeld in code te geven, stel dat het volgende programma een gedistribueerd programma is:

P: do                    ||           Q: do
     nks.p               ||                nks.q
     ;                   ||                ;
     ks.p                ||                ks.q
   od                    ||              od

Het probleem is nu ervoor te zorgen dat wanneer component P bezig is aan zijn kritieke sectie ks.p, component Q niet bezig kan zijn aan zijn kritieke sectie ks.q . Uiteraard is het wel toegestaan dat Q bezig is met de niet-kritieke sectie nks.q wanneer P bezig is met ks.p.

Het wederzijds uitsluitingsalgoritme van Peterson is een van de algoritmen die dit probleem oplossen. De bekendste variant van Peterson is de variant die twee componenten synchroniseert, maar het algoritme van Peterson kan worden uitgebreid tot n componenten, waarbij n ieder geheel getal kan zijn groter dan 1.

De veilige sluis

Peterson is in feite een variant op een ander algoritme, het 'veilige sluis-algoritme' (Engels: Safe Sluice algorithm).

Het idee achter de veilige sluis is een analogie met de sluizen die in dijken zitten waar weleens twee boten in tegengestelde richting doorheen willen varen. De kapitein van een van de boten P gebruikt een vlag om aan de kapitein van de andere boot Q te seinen dat hij gaat varen. Q gaat dan pas varen als de vlag van P niet is gehesen.

 PRECONDITIE:  vlag.p = false AND vlag.q = false
===================================================
P: do                    || Q: do
     nks.p;              ||     nks.q;
     vlag.p := true;     ||     vlag.q := true;
     if not(vlag.q) ->   ||     if not(vlag.p) ->
       skip fi;          ||       skip fi;
     ks.p;               ||     ks.q;
     vlag.p := false;    ||     vlag.q := false;
   od                    ||    od

Waarbij het if-statement gelezen moet worden als "als de conditie waar is, ga dan verder; zo niet, wacht dan tot hij waar wordt".

De veilige sluis zorgt er inderdaad voor dat maar een component op ieder moment bezig kan zijn aan zijn kritieke sectie. Kritieke sectie ks.p kan namelijk alleen worden uitgevoerd als vlag.q de waarde false heeft en andersom.

Met het algoritme van de veilige sluis kan het zich voordoen, dat beide componenten vast kunnen lopen in wat een deadlock wordt genoemd, ze kunnen eeuwig op elkaar gaan staan wachten. Bij een gedistribueerd programma is namelijk niet gegarandeerd dat de statements van componenten onderling in een bepaalde volgorde worden uitgevoerd, de volgorde binnen iedere component is natuurlijk wel gegarandeerd. Wanneer de twee componenten precies gelijk op het punt dat zij hun vlag op true willen zetten, dan kan het zo zijn dat beide vlaggen op true worden gezet, voordat beide componenten naar de vlag van de ander kijken:

Vanuit deze situatie kan geen van beide componenten verder en valt het hele het programma stil. Petersons algoritme is een uitbreiding die deze situatie voorkomt.

Van veilige sluis naar Peterson

Het probleem met de veilige sluis is dat de vlaggen allebei tegelijk de waarde true kunnen hebben. Het is dus nodig om het algoritme uit te breiden zodat de ene component het voor de andere gegarandeerd mogelijk maakt om verder te kunnen.

Als we even terugkeren naar de analogie van de sluis, kunnen we het probleem als volgt oplossen: we geven iedere kapitein een lampje en een knop. Kapitein P kan met zijn knopje het lampje van kapitein Q aanzetten en andersom, maar beide lampjes kunnen niet tegelijkertijd aan zijn. Na zijn vlag gehesen te hebben, duwt een kapitein op zijn knop. Degene die gaat, is degene wiens lampje brandt. De ander wacht totdat hij de enige is met een gehesen vlag.

Tegelijkertijd moeten we aantonen dat op punt A iets geldt waaruit we kunnen zien dat alleen P in zijn kritieke sectie zit:

do
  nks.p;
  x.p := true;
  if x.q = false OR H.p.q -> skip fi;
  {A.p}
  ks.p;
  x.p := false;
od

Wat we in feite moeten weten is $A.p\wedge A.q\Rightarrow false$. Omdat dat toch een sterke eis is, is het waarschijnlijk een goed idee om de ontwikkeling van het verdere programma te beginnen bij de logische uitspraak als keuze voor A die ons het meeste armslag geeft (de sterkste uitspraak die mogelijk is):

$A.p\equiv x.p\wedge (\neg x.q\vee H.p.q)$

Lokaal is deze uitspraak in orde (hij volgt direct uit het programma), maar de vraag is of we hem kunnen bewijzen als we de acties van het andere component in het vraagstuk betrekken.

In component q is het statement "x.q := true" het enige statement dat de bovenstaande uitspraak onwaar kan maken. We zullen dus dit statement zo uitbreiden dat hij de bovenstaande uitspraak gegarandeerd waar maakt.

We willen graag dat A.p en A.q niet tegelijkertijd waar kunnen zijn. Daartoe merken we op:

${\begin{matrix}&A.p\wedge A.q\\\equiv &\{{\mbox{keuze voor A}}\}\\&x.p\wedge (\neg x.q\vee H.p.q)\wedge x.q\wedge (\neg x.p\vee H.q.p)\\\equiv &\{{\mbox{predicaten calculus}}\}\\&x.p\wedge H.p.q\wedge x.q\wedge H.q.p\\\Rightarrow &\{{\mbox{over de x-en weten we niets}}\}\\&H.p.q\wedge H.q.p\\\Rightarrow &\{{\mbox{dat willen we graag}}\}\\&false\end{matrix}}$

We moeten dus iets bedenken voor H.p.q en H.q.p zodat $H.p.q\wedge H.q.p\Rightarrow false$. Een keuze die we hiervoor kunnen maken is de volgende: $H.p.q\equiv v=p\wedge H.q.p\equiv v=q$. Deze keus is mogelijk omdat met deze keus H.p.q en H.q.p nooit allebei waar kunnen zijn. Deze keuze en het feit dat we besloten hadden de toekenningen aan x.p en x.q uit te breiden, maken dat we aan het volgende programma komen:

do
  nks.p;
  x.p, v := true, p;
  if x.q = false OR v = q -> skip fi;
  ks.p;
  x.p := false;
od

Om nu weer aan een programma met one-point statements te komen, passen we dezelfde truc toe als in het voorgaande kader:

do
  nks.p;
  y.p := true
  v := p;
  if y.q = false OR v = q -> skip fi;
  ks.p;
  y.p := false;
od

Merk op dat dit programma heel nauw sluit en geen ruimte voor keuzevrijheid openlaat. We hadden er bijvoorbeeld niet voor kunnen kiezen om de toekenning aan v voor de toekenning aan y te doen, hadden we dat wel gedaan, dan was de exclusieve toegang voor alle compenten tot de kritische secties niet langer gegarandeerd. De volgende volgorde van uitvoering was dan namelijk mogelijk geweest nadat P en Q beide hun niet-kritieke secties uitgevoerd hadden:

${\begin{matrix}\{\neg y.p\wedge \neg y.q\}\\Q:v:=q\\\{\neg y.p\wedge \neg y.q\wedge v=q\}\\P:v:=p\\\{\neg y.p\wedge \neg y.q\wedge v=p\}\\P:y.p:=true\\\{y.p\wedge \neg y.q\wedge v=p\}\\P:if\neg y.q\vee v=q\rightarrow skipfi\\\{\neg y.q{\mbox{, dus P blokkeert niet}}\}\\\{y.p\wedge \neg y.q\wedge v=p\}\\Q:y.q:=true\\\{y.p\wedge y.q\wedge v=p\}\\P:if\neg y.p\vee v=p\rightarrow skipfi\\\{v=p{\mbox{, dus Q blokkeert niet}}\}\\\{y.p\wedge y.q\wedge v=p\}\\P:ks.p\|Q:ks.q\end{matrix}}$

Ook was het niet mogelijk geweest om de y's te laten vallen en compleet te vervangen door de v's. Hadden we dat wel gedaan, dan was de exclusieve toegang wel gegarandeerd - maar tegen de prijs van het volledig verlies van alle mogelijke parallellisme in het programma. Het programma was dan parallel geweest totdat het eerste component aan zijn kritieke sectie begonnen was. Daarna had ieder component moeten wachten tot de andere component klaar was met zijn kritieke sectie, zijn niet-kritieke sectie en tot hij de waarde van v omgezet had voordat het verder kon. Sterker nog, dat was het geval geweest voor twee componenten. Een implementatie van Peterson voor meerdere componenten zonder de y's had de exclusieve toegang ook niet meer gegarandeerd.

 PRECONDITIE:  vlag.p = false AND vlag.q = false
===================================================
P: do                    || Q: do
     nks.p;              ||     nks.q;
     vlag.p := true;     ||     vlag.q := true;
     lamp := p;          ||     lamp := q;
     if not(vlag.q)      ||     if not(vlag.p)
       OR                ||       OR
        lamp = q ->      ||        lamp = p ->
       skip fi;          ||       skip fi;
     ks.p;               ||     ks.q;
     vlag.p := false;    ||     vlag.q := false;
   od                    ||    od

De waarde van het algoritme van Peterson

Petersons algoritme is een van de zeer vele algoritmes om componenten te synchroniseren die gebruikmaken van one-point statements, dus waarvoor geen speciale voorzieningen in de uitvoerende computer nodig zijn. Peterson is hiervoor een van de meest elegante algoritmen.

Dat geldt ten minste voor de variant van Peterson met twee componenten. Petersons algoritme kan worden uitgebreid voor meer componenten, iedere component moet naar alle andere componenten controleren. Petersons algoritme voor n componenten werkt alleen maar voor precies N componenten en moet opnieuw geïmplementeerd worden voor iedere nieuwe waarde van n.

Externe bronnen

• On a method of multiprogramming W.H.J. Feijen en A.J.M. van Gasteren, Uitgeverij Springer uit de serie Monographs in computer science ISBN 0-387-98870-X