Wederzijds uitsluitingsalgoritme van Peterson
Van Wikipedia
Het wederzijds uitsluitingsalgoritme van Peterson is een algoritme dat ertoe dient een aantal componenten van een multiprogramma die allen een kritieke sectie bevatten zo te synchroniseren dat op ieder moment maar één component aan zijn kritieke sectie bezig kan zijn.
Inhoud |
[bewerk] Het probleem
Een multiprogramma is een programma dat bestaat uit meerdere componenten die wellicht gelijktijdig uitgevoerd worden. In een dergelijk programma komt het vaak voor dat componenten beschikken over een kritieke sectie, een stuk van het component dat dusdanig in elkaar zit dat de berekening uitgevoerd door het multiprogramma als geheel alleen maar goed kan gaan als maximaal één component op ieder moment bezig is aan zijn kritieke sectie.
Om een voorbeeld in code te geven, stel dat het volgende programma een multiprogramma is:
P: do true -> || Q: do true ->
nks.p || nks.q
; || ;
ks.p || ks.q
od || od
Het probleem is nu ervoor te zorgen dat als component P bezig is aan zijn kritieke sectie ks.p, dat component Q niet bezig kan zijn aan zijn kritieke sectie ks.q . Uiteraard is het wel toegestaan dat Q bezig is met niet-kritieke sectie nks.q als P bezig is met ks.p.
Het wederzijds uitsluitingsalgoritme van Peterson is een van de vele algoritmen die dit probleem oplossen. De bekendste variant van Peterson is de variant die twee componenten synchroniseert, maar Peterson kan uitgebreid worden tot N componenten, waarbij N ieder geheel getal kan zijn groter dan 1.
[bewerk] De veilige sluis
Peterson is in feite een variant op een ander algoritme, het veilige sluis-algoritme (Engels: Safe Sluice algorithm).
Het veilige sluis-algoritme begint met een vlag om aan te geven dat een component verder wil (hier aangegeven voor een enkele component - de andere component is precies hetzelfde, maar met p en q verwisseld)
do true -> nks.p; v.p := true; ks.p; v.p := false; od Om dit goed te laten gaan, mag de vlag van de component alleen de waarde true krijgen als de vlag van de andere component de waarde false heeft: do true -> nks.p; if v.q = false -> v.p := true fi; ks.p; v.p := false; od Dit is in feite de oplossing al, alleen gebruikt het niet exclusief one-point statements. Om deze reden introduceren we een vlag waarvan de waarde door de vlag van de component geïmpliceerd wordt:
PRECONDITIE : x.p = false, v.p = false
do true ->
nks.p;
x.p := true;
if x.q = false
{dus zeker ook v.q = false} ->
v.p := true fi;
ks.p;
x.p, v.p := false, false;
od
Nu kunnen we v laten vallen en helemaal vertrouwen op x. do true -> nks.p; x.p := true; if x.q = false -> skip fi; ks.p; x.p := false; od |
Het idee achter de veilige sluis is een analogie met de sluizen die in dijken zitten waar wel eens 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 P niet aan het seinen is. Dit algoritme (waarvan de correctheid bewijsbaar is door afleiding - zie kader) ziet er als volgt uit:
PRECONDITIE: vlag.p = false AND vlag.q = false
===================================================
P: do true -> || Q: do true ->
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. Ks.p kan namelijk alleen worden uitgevoerd als vlag.q de waarde false heeft en andersom - het programma zorgt ervoor dat de situatie 
(allebei de vlaggen de waarde false) niet voor kan komen.
De veilige sluis heeft echter wel een groot gebrek, namelijk dat beide componenten compleet vast kunnen lopen in wat een deadlock genoemd wordt - ze kunnen eeuwig op elkaar gaan staan wachten. Bij een multiprogramma is namelijk niet gegarandeerd dat de statements van componenten onderling in een bepaalde volgorde uitgevoerd worden (de volgorde binnen een component is natuurlijk wel gegarandeerd). Als beide componenten aangeland zijn op het punt dat zij hun vlag op true willen zetten, dan kan het zo zijn dat beide vlaggen op true gezet worden voordat een component naar de vlag van de ander kan kijken:
: : vlag.p := true vlag.q := true if not(vlag.q) WAIT if not(vlag.p) WAIT
Vanuit deze situatie kan geen van beide componenten verder en valt heel het programma stil. Petersons algoritme is een uitbreiding die deze situatie voorkomt.
[bewerk] 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.
Om van de deadlock van de veilige sluis af te komen, zullen we de conditie van de synchronisatie moeten verzwakken. Tegelijkertijd moeten we aantonen dat op punt A iets geldt waaruit we kunnen zien dat alleen P in zijn kritieke sectie zit:
do true ->
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 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:
We moeten dus iets bedenken voor H.p.q en H.q.p zodat do true -> 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 true -> 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 over 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:
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. |
. 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):
. Een keuze die we hiervoor kunnen maken is de volgende: 
. 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:
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. Deze oplossing (ook weer bewijsbaar - zie kader) maakt gebruik van een tussen de componenten gedeelde variabele en ziet er als volgt uit:
PRECONDITIE: vlag.p = false AND vlag.q = false
===================================================
P: do true -> || Q: do true ->
nks.p; || nks.q;
vlag.p := true; || vlag.q := true;
lamp := p; || lamp := q;
if not(vlag.q) || if not(vlag.p)
OF || OF
lamp = q -> || lamp = p ->
skip fi; || skip fi;
ks.p; || ks.q;
vlag.p := false; || vlag.q := false;
od || od
[bewerk] De waarde van Peterson
Petersons algoritme is een van de zeer vele algoritmes om componenten te synchronizeren die gebruikmaken van one-point statements (en dus geen speciale voorzieningen in de uitvoerende computer behoeven). Peterson is wel een van de meeste elegante algoritmes die er bestaan - zowel qua implementatie als qua bewijs.
Tenminste, dat geldt voor de variant van Peterson voor twee componenten. Petersons algoritme kan uitgebreid worden voor meerdere componenten, maar wordt daarbij al gauw een woud van code. Het bewijs wordt niet veel lastiger en valt door middel van inductie te geven. De implementatie is echter zeer inefficiënt en bovendien schaalt hij niet goed: Petersons algoritme voor N componenten werkt alleen maar voor precies N componenten en moet opnieuw geïmplementeerd worden voor iedere waarde van N.
[bewerk] 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 038798870X
