Concurrent computing

Schrik niet van de titel van deze blog! Ik leg in deze blog uit wat verstaan wordt onder concurrent computing: welk problemen ermee opgelost worden? Welke nieuwe problemen erdoor ontstaan (en hoe die op te lossen zijn)? Maar waarom het toch een belangrijk onderwerp is wat veel gebruikt wordt.

Wat is concurrent computing?

In het Nederlands wordt de term ‘gedistribueerd programmeren’ gebruikt. Ik houd het in deze blog bij Concurrent computing omdat ik vind dat het de lading beter dekt. Concurrent computing is het opsplitsen van een grote taak in meerdere kleinere taken die (relatief) onafhankelijk uitgevoerd kunnen worden. Deze kleinere taken kunnen tegelijkertijd (concurrent) worden uitgevoerd. Wanneer de kleinere taken afgehandeld zijn, worden ze samengevoegd tot een enkel resultaat.

Aangezien dit vrij abstract is hierbij een voorbeeld: het bakken van een ei.
Dit bevat een aantal taken:

  • pak eieren
  • pak koekenpan
  • pak boter
  • pak zout en peper
  • zet koekenpan op gasfornuis
  • zet gasfornuis aan
  • doe boter in de koekenpan
  • wacht tot boter heet genoeg is
  • breek eieren en doe ze in de koekenpan
  • bak de eieren
  • wacht tot eieren gebakken zijn
  • voeg zout en peper toe
  • doe gasfornuis uit
  • haal koekenpan van gasfornuis
  • schep gebakken eieren uit pan

Zoals je ziet zijn er best veel taken te identificeren bij het “bakken van een ei”. Sommige taken zijn helemaal onafhankelijk van de andere taken. Maar andere taken moeten “wachten” tot een bepaalde taak is afgelopen. Bijvoorbeeld “zet koekenpan op gasfornuis” kan pas starten als “pak koekenpan” is afgehandeld. Ook zijn er taken waarin de volgorde waarin ze onderling afgehandeld worden niet zo van belang is, zoals “pak eieren”, “pak koekenpan”, “pak boter” en “pan zout en peper”. Het maakt niet veel uit of je de eieren, boter, zout en peper of koekenpan eerst pakt. Het maakt ook niet veel uit of je eerst het gasfornuis aan doet, daarna de boter in de pan en dan de pan op het gasforunuis zet, of in een andere volgorde of allemaal tegelijkertijd.

Laten we kijken of we de taken kunnen groeperen en de verbanden kunnen aanbrengen:

Schematische weergave van het bakken van eieren

Welke problemen lost het op?

Als één persoon het ei gaat bakken, dan zal het niet per se sneller of beter gaan. Maar als je meerdere personen hebt die elk een of meer taken kunnen uitvoeren, dan kan het wel efficienter. Als het het niet gaat om eieren bakken voor 1 persoon, maar eieren bakken voor 100 personen, dan wordt die efficiëntie nog belangrijker.

Een computer kan ook meer dan 1 taak tegelijkertijd uitvoeren. Eigenlijk doet een computer dat de hele tijd, maar zijn die taken meestal aparte programma’s. Bijvoorbeeld je hebt nu een web browser open en wellicht een Word document. Voor beide is de computer taken aan het uitvoeren.

Als een computerprogramma wordt uitgevoerd, dan kan je dit zien als een reeks van taken die gedaan moeten worden. Sommige taken duren relatief lang. Zo is het schrijven of lezen van data van een schijf of van het internet, een taak die qua doorlooptijd ergens tussen “meteen klaar” en “dit duurt echt veel te lang” ligt. Dit soort taken wil je eigenlijk laten uitvoeren zonder dat het de rest van het computerprogramma blokkeert. Oftewel het computerprogramma zou niet moeten hoeven wachten totdat de taak afgerond is. Het computerprogramma kan dan verder met andere taken, terwijl de langdurende taak loopt. En als die langdurende taak dan klaar is, wil je verder met de volgende gerelateerde taak.

Een voorbeeld waar je dit kan zien (maar wat je dus eigenlijk niet merkt), is als je aan het tekstverwerken bent. De tekstverwerker zal om de zoveel tijd het gewijzigde bestand automatisch bewaren, zodat mocht er iets misgaan je niet alles overnieuw hoeft te typen. Dit bewaren duurt afhankelijk van de grootte van het bestand zeer kort tot wel enkele seconden, en dit gebeurt terwijl je zit te typen. Het zou dan heel irritant zijn als de letters die je typt niet meer op het scherm verschijnen, omdat de tekstverwerker het bestand net aan het bewaren is. Omdat het bewaren en het tonen van de letters die je typt twee aparte taken zijn die gelijktijdig kunnen gebeuren, merk je hier niks van.

Een ander voorbeeld is een website. Je kan je voorstellen dat meerdere mensen tegelijktijd een pagina van die website willen bekijken. De server waar de website “op staat”, krijgt dan tegelijkertijd verschillende vragen. Zo’n vraag duurt even om af te handelen, voordat het antwoord (de pagina) teruggegeven kan worden. Er draaien dan ook meerdere taken op die server die allemaal zo’n vraag kunnen beantwoorden en deze taken kunnen dat “gelijktijdig” afhandelen.

Je zou dit kunnen vergelijken met een garderobe in de schouwburg; je geeft je jas af, de medewerker hangt het op en geeft een ontvangstbewijs terug. Als er maar 1 medewerker zou zijn en meerdere bezoekers, dan zouden veel mensen lang moeten wachten. Maar met meerdere medewerkers neemt de wachttijd af. Elke medewerker doet dezelfde taak, omdat er veel vraag is naar die taak.

Even terug naar ons voorbeeld. In geval van het eieren-bak-voorbeeld zouden de taken verdeeld kunnen worden als er meer dan een persoon zou meewerken:

Schematische weergave van het bakken van eieren verdeelt over 3 personen

Zoals je ziet zijn er in dit voorbeeld 3 personen die de taken uitvoeren. Sommige taken kunnen prima tegelijkertijd uitgevoerd worden, zoals het pakken van eieren, koekenpan, boter en zout en peper. Aangezien er 3 personen zijn maar dat stukje 4 taken heeft, zal persoon C of eerst de eieren pakken of eerst de zout en peper. Als er nog een 4e persoon was geweest, kon ook dat tegelijk. Ook zie je dat personen soms even moeten wachten totdat een taak is afgerond (die soms door een andere persoon wordt uitgevoerd), voordat ze verder kunnen met hun volgende taak.

Hoe werkt dat dan?

Een computer kan meerdere taken tegelijkertijd uitvoeren, bijvoorbeeld omdat de computer meerdere processoren heeft en/of de processor meerdere “cores” heeft. Dit heet parallel computing. Maar meerdere processoren of “cores” is niet per se een voorwaarde om concurrent computing te ondersteunen. Een computer doet sowieso meerdere taken “tegelijkertijd”, vaak meer taken dan het aantal processoren of cores. Dit werkt zo: de tijd dat 1 taak op de processor mag draaien, is beperkt, vaak tot niet langer dan 10 tot 100 millisecondes. Als de taak binnen die tijd niet is afgerond, dan wordt de taak gepauzeerd en mag een andere taak op de processor. Dit wordt ook wel time slicing genoemd en wordt gebruikt ongeacht het aantal processoren.

In het plaatje hiernaast zie je hoe het werkt. Twee taken worden “tegelijkertijd” afgehandeld. Tegelijkertijd staat tussen aanhalingstekens, omdat steeds eerst de ene daarna de andere wordt gedaan.

Bij 2 processoren kan het er zo uitzien.

Merk op dat de taken niet per definitie aan 1 processor gebonden zijn en dat er nog steeds gebruik gemaakt wordt van time slicing.

Zoals je ziet is de totale tijd die nodig is om taak A en taak B af te ronden kleiner als er 2 processoren gebruikt worden, namelijk 3 time slices bij 2 processoren en 5 time slices bij gebruik van 1 processor.

Welke nieuwe problemen ontstaan?

Concurrent computing kan ervoor zorgen dat taken efficienter uitgevoerd worden en dat het voor de gebruiker lijkt of de computer niet door een bepaalde taak geblokkeerd wordt.

Als taken tegelijkertijd worden uitgevoerd is het wel belangrijk dat iets ervoor zorgt dat de verschillende taken even veel tijd krijgen, dat ze gestart en gepauzeerd worden op het juiste moment en in de juiste volgorde, dat de taken soms onderling moeten kunnen communiceren en dat als ze dezelfde data gebruiken, dat dat geen problemen oplevert. Dit samen wordt concurrency control genoemd.

Een veel gebruikt voorbeeld om te illustreren welke problemen zich kunnen voordoen bij concurrent computing is die van het opnemen van een bankrekening. Je kan je voorstellen dat dit de volgende stappen heeft:

1) controleer of er genoeg op de rekening staat om x bedrag op te nemen

2a) zo ja, haal x bedrag van de rekening

2b) zo nee, laat weten dat het niet kan.

Als op exact hetzelfde moment 2 keer een bedrag van dezelfde rekening wordt gehaald, en er time slicing wordt gebruikt, kan het zijn dat het volgende gebeurt:

Bovenstaande wordt een race condition genoemd.

Om een race condition op te lossen, kan gebruik worden gemaakt van een blokkade; in het voorbeeld hierboven zorg je ervoor dat er maar 1 taak tegelijk iets met de bankrekening kan doen, andere taken moeten even wachten. Dit wordt ook wel een lock genoemd.

Maar hierdoor kan weer een deadlock ontstaan; een vergelijkbaar voorbeeld als hierboven zou zijn geld overschrijven van rekening A naar rekening B. Als twee taken dat willen doen en de eerste zet een lock op rekening A en wil daarna een lock zetten op rekening B, maar de tweede is net iets eerder en heeft al een lock op rekening B gezet en wil een lock op rekening A, dan zijn beide taken op elkaar aan het wachten.

Een ander probleem kan hier weer uit ontstaan: resource starvation. Dit is als een taak iets (een resource) nodig heeft om te beginnen, maar deze resource nooit beschikbaar komt (bijvoorbeeld omdat een andere taak de resource steeds gelockt heeft).

Een voorbeeld van resource starvation is het Filosofenprobleem.

Bovenstaande problemen zijn allemaal op te lossen, maar de programmeur moet zich hiervan wel bewust zijn. Sommige programmeertalen hebben hulpmiddelen zodat bovenstaande problemen zoveel mogelijk voorkomen worden.

Hoe werkt concurrent computing in programmeertalen?

De meeste programmeertalen bieden (op verschillende niveaus) ondersteuning voor concurrent computing.  Bij sommige programmeertalen wordt concurrent computing op een vrij laag niveau ondersteund, wat betekent dat de programmeur veel zelf moet doen. Gelukkig zijn er ook programmeertalen en frameworks die concurrent computing ondersteunen op een hoger niveau, waardoor veel van bovenstaande problemen al opgelost zijn of simpel zijn te voorkomen.

Om het niet onnodig ingewikkeld te maken (en deze blog ook niet te lang), focus ik alleen op een bepaalde manier (op een hoger niveau) van het gebruik van concurrent computing die je in veel talen (onder verschillende namen) terug ziet komen:

Beloftes

Als je aan het programmeren bent, werk je veel met waardes. Bijvoorbeeld een getal, de naam van het bestand wat je op dat moment aan het inlezen bent of de inhoud van datzelfde bestand. Sommige waardes kosten relatief veel tijd om te achterhalen, zoals bijvoorbeeld de inhoud van een bestand, omdat het bestand ingelezen moet worden vanaf schijf of het internet. Het zou dus handig zijn als je dat tegelijkertijd met andere taken kan uitvoeren, zodat het programma er niet op hoeft te wachten. Je doet eigenlijk een belofte dat de waarde achterhaald is op het moment dat je er echt iets mee wilt doen, en in de tussentijd kan je in je programma net doen of je de waarde al hebt.

Een belofte wordt in programmeertalen Promise, Future (een toekomstige waarde), delay (uitstel) of deferred (uitgesteld) genoemd, maar aangezien meestal Promise of Future gebruikt wordt, houd ik het bij “belofte”. Overigens is er een verschil tussen promises en futures die per programmeertaal anders uitgelegd wordt.

Een belofte (Promise / Future) kan dus gebruikt worden alsof het de waarde is die het belooft te zijn. De belofte kan op een gegeven moment vervuld worden (Promise fulfilled of future resolved). Ook kan het zijn dat de belofte gebroken wordt (promise rejected). Als een belofte vervuld wordt, kan het programma iets met de beloofde waarde doen. Maar wanneer een belofte gebroken wordt, kan het programma daar op een andere manier op reageren. Als je bijvoorbeeld in je programma een tekst wil ophalen van een website en een andere tekst van een heel andere website, dan kan je dat zien als twee beloftes voor toekomstige waardes. Deze beloftes kunnen tegelijkertijd vervuld worden, of als het internet “stuk” is, dan worden de beloftes gebroken. Als je een belofte net gedaan hebt, dan is die nog niet vervuld maar ook nog niet gebroken; de belofte staat nog uit (promise pending).

Wat heb je hier nu aan hoor ik je denken? Als we teruggaan naar het eieren-bak-voorbeeld dan zou je de taak “pak eieren” als een belofte kunnen zien dat je op een zeker moment in de toekomst eieren hebt. Als je die belofte kan vervullen, dan kan je doorgaan naar de volgende taak (“breek eieren en doe ze in de koekenpan”), tenzij je de eieren laat vallen, want dan breek je de belofte (en de eieren).

Ons voorbeeld zou er in pseudocode als volgt uit kunnen zien:

eieren = pakEieren()		// de belofte om eieren te pakken
koekenpan = pakKoekenpan()	// de belofte om een koekenpan te pakken
boter = pakBoter()		// de belofte om boter te pakken
zoutEnPeper = pakZoutEnPeper()	// de belofte om zout en peper te pakken
gasfornuis = zetGasFornuisAan()	// de belofte om gasfornuis aan te zetten


BeloftesSamen( [ koekenpan, boter ] )	// als de beloftes beide
 .vervuld( koekenpanMetBoter => { 	// vervult zijn
   BeloftesSamen( [			// doe nieuwe beloftes:
     zetOpGasFornuis(gasfornuis, koekenpan)
     doeBoterInKoekenpan(koekenpan, boter)
     gasfornuis
   ] )
 } )
 .vervuld( heteKoekenpan => {		// als bovenstaande 3 beloftes 
					// vervuld zijn, doe een nieuwe
					// belofte:
   wachtTotBoterHeetGenoegIs(koekenpanMetBoter)
 } )
 .vervuld( koekenpanMetEieren => {	// als bovenstaande belofte 
					// vervuld is, doe nieuwe belofte
   breekEierenInKoekenpan(eieren, heteKoekenpan)
 } )
 .vervuld( bakkendeEieren => {
   BeloftesSamen( [
     bakEieren(koekenpanMetEieren)
     naEnigeTijd {			// terwijl de eieren aan het 
					// bakken zijn, voeg zout en 
					// peper toe na enige tijd
       voegZoetEnPeperToe (koekenpanMetEieren, zoutEnPeper);
     }
   ] )
 } )
 .vervuld( gebakkenEieren => {		// als bovenstaande twee beloftes
					// vervuld zijn:
    wachtTotEierenGebakkenZijn(bakkendeEieren)
 } )
 .vervuld( eierenKlaar => {		// als de bovenstaande belofte 
					// vervuld is,
    BeloftesSamen( [			// doe 3 nieuwe beloftes:
      schepEierenUitPan(gebakkenEieren)
      haalKoekenpanVanFornuis()
      doeGasFornuisUit()
    ] )
  } )
  .vervuld( {		// als bovenstaande beloftes vervuld zijn, dan
    eetEieren()		// zijn de eieren klaar om opgegeten te worden
  } )
  .gebroken( {		// als een van bovenstaande beloftes gebroken 
			// wordt, doe dan dit:
    geefRedenWaaromErGeenEierenZijn()
  } )	

Zoals je ziet kunnen beloftes geschakeld worden in een rij van beloftes (promise chaining), waarbij als een belofte vervuld is een nieuwe belofte gemaakt kan worden. Ook kunnen beloftes samen een nieuwe belofte vormen. Deze nieuwe belofte zal alleen dan vervuld zijn, als alle beloftes waar die uit gestaat, ook vervuld zijn. De volgorde waarin deze beloftes vervuld worden, is dan niet van belang. Ook kunnen ze tegelijkertijd afgehandeld worden.

Ik hoop dat ik de beloftes die ik aan het begin van deze blog deed, heb kunnen vervullen en dat duidelijk is wat concurrent computing is.

Geef een reactie

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *

Deze site gebruikt Akismet om spam te verminderen. Bekijk hoe je reactie-gegevens worden verwerkt.