Kritieke Secties

Historie

Een van de pioniers op het gebied van de gedistribueerde algoritmen was de Nederlander Edsger Dijkstra (1930-2002). Rond 1965 werkte Dijkstra aan een besturingssysteem genaamd THE.  Dit was een van de eerste besturingssystemen die multi-tasking ondersteunde: een methode waarbij meerdere taken,  ook wel processen genaamd, tegelijk worden uitgevoerd. Deze processen maken gebruik van dezelfde CPU en hetzelfde geheugen, maar het besturingssysteem creëert de illusie dat alle processen tegelijk worden uitgevoerd door razendsnel te switchen en de processen afwisselend steeds allemaal even rekentijd te geven op de CPU. Tegenwoordig wordt multi-tasking standaard ondersteund door vrijwel alle besturingssystemen, maar in die tijd was het een revolutie. Het THE systeem was niet gedistribueerd in de zin dat er meerdere computers waren (er was er maar een), maar er waren wel meerdere processen waarvan de activiteiten op elkaar afgestemd moesten worden, en die samen een doel moesten bereiken.  Enkele van de eerste gedistribueerde algoritmen zijn daarom geschreven voor het THE systeem.

Edsger Dijkstra

Race condities en kritieke secties

Een typische situatie waar Dijkstra mee te maken had was er een met twee processen, P1 en P2, die beiden een gedeelde variabele x met 1 verhogen:

P1: x = x+1 P2: x = x+1

Wanneer x aan het begin de waarde 0 heeft dan zou je verwachten dat na afloop, wanneer P1 en P2 klaar zijn, x de waarde 2 heeft gekregen. Dit is echter niet altijd het geval en dat komt omdat op het laagste niveau de instructie x = x+1 niet atomair is: de instructie x = x+1 wordt vertaald naar een serie machineinstructies waarbij  proces P1 eerst de waarde van de gedeelde variabele x copieert naar een lokale variabele l1, dan l1 met 1 ophoogt, en tot slot de waarde van l1  terugschrijft naar x.  Bij proces P2 gaat het net zo, alleen wordt dan gebruik gemaakt van een andere lokale variabele l2. Hierdoor is het mogelijk dat eerst P1 de waarde van x copieert naar l1, dat dan P2 de waarde van x copieert naar l2, waarna P1 de waarde van l1 met 1 ophoogt en terugschrijft naar x, waarna P2 de waarde van l2 met 1 ophoogt en terugschrijft naar x. Bij deze volgorde van de machineinstructies zal x na afloop van P1 en P2 de waarde 1 hebben.

Dit is een voorbeeld van een zogenaamde race conditie: een situatie waarin meerdere processen een gedeelde variabele lezen en schrijven, en het uiteindelijke resultaat afhangt van de relatieve snelheid van hun executies. Race condities zijn slecht: we willen niet dat het resultaat van berekening afhangt van toevallige omstandigheden. Race condities zijn de bron van talloze software bugs en vaak erg moeilijk om te vinden: typisch heb je te maken met software die vrijwel altijd goed werkt, maar af en toe opeens een fout antwoord geeft.

Om race condities te voorkomen stelde Dijkstra de notie van een kritieke sectie voor. Een programmeur kan stukken code markeren als kritieke sectie. We eisen vervolgens dat op ieder moment maximaal één proces in zijn kritieke sectie mag zijn. Op deze manier bereiken we wederzijdse uitsluiting of (in het Engels) mutual exclusion. Altijd wanneer er iets is waar slechts één proces tegelijk toegang toe mag hebben (een gedeelde variabele, een printer, netwerktoegang,..) dan kun je dat beschermen met een kritieke sectie. In het voorbeeld van de processen P1 en P2 zou de aangepaste code er alsvolgt uit kunnen zien:

P1: enter_critical_section() P2: enter_critical_section()
x = x+1 x = x+1
leave_critical_section() leave_critical_section()

Door kritieke secties te gebruiken hebben we de race conditie in dit programma verwijderd: onafhankelijk van de volgorde waarin P1 en P2 worden uitgevoerd zal na afloop de waarde van x altijd 2 hoger zijn dan aan het begin. De vraag is natuurlijk wel hoe we mutual exclusion kunnen realiseren: hoe ziet de code voor enter_critical_section() en leave_critical_section() er uit?  Het antwoord op deze vraag is een gedistribueerd algoritme waar alle processen aan mee doen en dat er voor zorgt dat op ieder moment maximaal één van de processen de kritieke sectie in kan.

Vier fundamentele problemen

Bij het realiseren van kritieke secties lopen we tegen vier fundamentele problemen aan, waar we altijd op bedacht moet zijn bij het ontwerpen van gedistribueerde algoritmen:

  1. Deadlock ("dodelijke omhelzing"): Een situatie waarin twee of meer processen niet verder kunnen omdat elk proces wacht totdat een van de anderen iets heeft gedaan. Een deadlock treedt bijvoorbeeld op wanneer iemand uit Italië in Nederland wil gaan wonen en werken: de gemeenteambtenaar wil de Italiaan pas inschrijven in de gemeente wanneer hij een Nederlandse bankrekening heeft, terwijl de bankmedewerker pas een bankrekening wil openen wanneer de Italiaan staat ingeschreven bij een Nederlandse gemeente.
  2. Livelock: Een situatie waarin twee of meer processen voortdurend instructies uitvoeren maar er geen vooruitgang wordt geboekt. Een livelock kan bijvoorbeeld optreden wanneer twee mensen elkaar tegenkomen in een nauwe gang en tegenoverelkaar staan: de een doet een stap naar rechts en de ander een stap naar links waardoor ze weer tegenover elkaar staan, dan doet de ene een stap naar links en de ander een stap naar rechts waardoor ze weer tegenover elkaar staan, enzovoorts.
  3. Starvation ("uithongering"): Een situatie waarin een proces nooit aan de beurt komt omdat het steeds weer op andere processen moet wachten. Starvation kan bijvoorbeeld optreden op een rotonde waar een eindeloze stroom fietsers er voor zorgt dat een automobilist moet wachten tot hij een ons weegt voordat hij de rotonde kan oversteken.
  4. Busy waiting: Een situatie waarin een proces tijdens het wachten voortdurend  (veel en onnodig) processortijd gebruikt. Denk aan je zusje die de hele tijd op de deur staat te bonzen en vraagt wanneer zij nu eindelijk de badkamer in mag.
In ons dagelijke leven hebben we voortdurend te maken met bovenstaande problemen maar eigenlijk slagen we er altijd wel in om ze op te lossen: de Italiaan staat ingeschreven in Nijmegen en heeft een rekening bij een lokale bank, de twee mensen hebben hun weg vervolgd, de automobilist nam uiteindelijk gewoon voorrang op de rotonde, en het zusje stopte na een kwartier met bonzen.  Bij computers ligt dit anders: deadlocks, livelocks en starvation vormen een belangrijke reden waarom computersoftware vaak blijft "hangen".

Software oplossingen voor mutual exclusion

Hieronder bespreken we een aantal "oplossingen" voor het mutual exclusion probleem en illustreren daarmee de problemen van deadlock, livelock, starvation en busy waiting.  Voor de eenvoud beperken we ons tot een situatie waarbij er slechts twee processen zijn die toegang willen tot een kritieke sectie.  Uiteindelijk gaat mutual exclusion over computerprogramma's die toegang willen tot gedeelde hulpbronnen zoals variabelen en printers, maar je kunt de oplossingen ook gebruiken om afspraken te maken met je zus over wie er wanneer de badkamer in mag!

Poging 1

De eerste "oplossing" maakt gebruik van een gedeelde globale variabele turn die de waarden 0 en 1 kan aannemen. (Denk aan een bordje bij de ingang van de badkamer waar met krijt een 0 of een 1 op staat.) Bij aanvang geven we turn de waarde 0. Het idee is dat variabele turn aangeeft wie er de beurt heeft.  Wanneer een proces de kritieke sectie in wil wacht het steeds net zo lang tot het de beurt heeft. Bij het verlaten van de kritieke sectie geeft een proces de beurt aan het andere proces.

Proces 0 Proces 1
... ...
while turn != 0 while turn != 1
  do { niets };   do { niets };
"kritieke sectie" ; "kritieke sectie";
turn = 1 turn = 0
... ...

Bovenstaande code garandeert mutual exclusion maar heeft serieuze nadelen. Allereerst is er natuurlijk sprake van busy waiting. Maar ernstiger is dat de processen om en om de kritieke sectie moeten binnengaan. Wanneer het ene proces elk uur de kritieke sectie in wil terwijl het andere proces dit slechts eens per dag doet, dan zal het eerste proces enorm vertraagd worden. In het meest extreme geval, wanneer een van de processen geen toegang meer vraagt tot de kritieke sectie en een ander proces wel, kan er starvation optreden.

Mutual exclusion

Poging 2

De tweede "oplossing" maakt gebruik van twee gedeelde Boolese variabelen flag[0] en flag[1], die in het begin allebei false zijn. De intuitie hierbij is dat ieder proces een vlag heeft, die aanvankelijk is gestreken. Wanneer een proces de kritieke sectie in wil wacht het eerst net zo lang totdat de vlag van het andere proces niet meer is opgehesen. Zodra dit het geval is hijst het proces zijn eigen vlag op en gaat de kritieke sectie in. Bij het verlaten van de kritieke sectie strijkt een proces zijn vlag..

Proces 0 Proces 1
... ...
while flag[1] while flag[0]
  do { niets };   do { niets };
flag[0] = true; flag[1] = true ;
"kritieke sectie"; "kritieke sectie";
flag[0] = false; flag[1] = false;
... ...

Deze "oplossing" is natuurlijk helemaal fout. Het probleem doet zich voor wanneer eerst Proces 0 de eerste regel uitvoert en gelijk daarna Proces 1. Beide processen zien dat de vlag van de andere
gestreken is, hijsen vervolgens hun eigen vlag en gaan vrolijk de kritieke sectie binnen. Er is dus niet voldaan aan mutual exclusion.

Poging 3

De derde "oplossing" maakt ook gebruik van twee vlaggen maar doet dit voorzichtiger: voordat een proces kijkt naar de vlag van de ander hijst het nu eerst de eigen vlag.

Proces 0 Proces 1
... ...
flag[0] = true; flag[1] = true;
while flag[1] while flag[0]
  do {niets };   do {niets };
"kritieke sectie"; "kritieke sectie";
flag[0] = false; flag[1] = false;
... ...

Maar ook deze "oplossing" is fout: wanneer eerst Proces 0 zijn vlag hijst en direct daarna hijst ook Proces 1 zijn vlag, dan komt geen van beide processen ooit nog de kritieke sectie in. De processen zijn "te beleefd" en er is sprake van een deadlock..

Poging 4

De vierde "oplossing" is een variant van de derde "oplossing" waarbij een proces de vlag weer strijkt op het moment dat er een deadlock dreigt:

Proces 0 Proces 1
... ...
flag[0] = true; flag[1] = true;
while flag[1] do while flag[0] do
   { flag[0] = false;    { flag[1] = false;
      "wacht even";      "wacht even"
      flag[0] = true; };      flag[1] = true; };
"kritieke sectie"; "kritieke sectie";
flag[0] = false; flag[1] = false;
... ...

We zitten nu dicht bij een oplossing, maar het kan nog steeds misgaan. Wanneer Proces 0 en Proces 1 om en om een regel code uitvoeren zullen ze tot in het oneindige vlaggen blijven hijsen en strijken maar zal nooit iemand de kritieke sectie binnenkomen: de code laat een livelock scenario toe.

Oplossing

De Nederlandse wiskundige Dekker bedacht in 1965 de eerste een correcte oplossing voor het mutual exclusion algoritme. Zijn oplossing maakt zowel gebruik van gedeelde variabelen flag[0] en flag[1] als van een variabele turn. Dekker gebruikte de variabele turn om een knoop door te hakken indien beide processen tegelijk de kritieke sectie in willen. De oplossing van Dekker was nogal complex, maar gebruikmakend van hetzelfde idee kwam Peterson in 1981 met de simpele en elegante oplossing die hieronder staat.


Proces 0 Proces 1
... ...
flag[0] = true; flag[1] = true;
turn = 1; turn = 0;
while (flag[1] && turn = 1)  while (flag[0] && turn = 0) 
   do { niets };   do { niets };
"kritieke sectie"; "kritieke sectie";
flag[0] = false; flag[1] = false;
... ...

Het enige bezwaar dat nog aan deze oplossing kleeft is dat er sprake is van busy waiting.

Uppaal

Hoe weten we eigenlijk zo zeker dat de oplossing van Peterson correct is?  Immers, alle andere "oplossingen" bleken ook fout te zijn. Hoe kunnen we uitsluiten dat dit ook niet het geval is bij Peterson's oplossing?  Hieronder presenteren we een Uppaal model  van Peterson's algoritme. Door dit model te analyseren met Uppaal kunnen we bewijzen dat er voldaan is aan de gewenste eigenschappen. Het model bestaat uit twee instanties van een template P: twee processen die in parallel draaien: eentje met pid ("process identifier") waarde 0 en eentje met pid waarde 1.

Uppaal model van Peterson's algoritme

De vertaling van pseudocode naar Uppaal is recht-toe-recht-aan. Om tot uitdrukking te brengen dat een proces meerdere keren de kritieke sectie in kan, keert de automaat na het verlaten van de kritieke sectie weer terug naar de startlocatie. De startlocatie beschrijft de toestand waarin het proces met andere zaken bezig is en niet de kritieke sectie in wil. Zodra een proces de kritieke sectie in wil springt het naar locatie try0. Een belangrijk aspect van Peterson's algoritme is dat de conditie flag[1-pid] && turn == 1-pid niet atomair is. Het kan bijvoorbeeld gebeuren dat proces P(0) eerst flag[1] evalueert, dat vervolgens proces P(1) een aantal stappen doet, en dat pas daarna het tweede deel van de conditie turn == 1 wordt geëvalueerd. In het model wordt de evaluatie van de conditie daarom ook beschreven met twee opeenvolgende transities: wanneer in locatie try2 variabele flag[1-pid] op false staat kan de conditie flag[1-pid] && turn == 1-pid niet tot true evalueren en mag het proces de kritieke sectie in. Indien daarentegen flag[1-pid] op true staat dan moet het tweede deel van de conditie ook nog bekeken worden. Dit gebeurt in locatie try3: als turn==pid mag het proces de kritieke sectie in, anders gaat het terug naar try2.

Met behulp van Uppaal kunnen we eenvoudig laten zien dat Peterson's algoritme voldoet aan mutual exclusion: voor alle bereikbare toestanden geldt dat P(0) en P(1) niet tegelijkertijd in de kritieke sectie kunnen zijn:


A[] ( not( P(0).cs and P(1).cs ))
Er is dus voldaan aan de mutual exclusion eis. Ook kunnen we  met Uppaal laten zien dat het algoritme geen deadlocks heeft: er is altijd een transitie mogelijk. In een van de opdrachten zullen we het model van Peterson's algoritme nog verder bestuderen.