Gedistribueerd programmeren

Gedistribueerd programmeren (ook wel parallel programmeren) is een techniek van programmeren en programma-ontwerp, waarbij een computerprogramma bestaat uit meerdere deelprogramma's die al dan niet gelijktijdig uitgevoerd kunnen worden. Multiprocessor-machines zijn in staat om betere prestaties te behalen door dit soort programmering.

Werking

Bij gedistribueerd programmeren wordt een enkele taak opgesplitst in meerdere subtaken die relatief onafhankelijk berekend en achteraf weer samengevoegd kunnen worden tot een enkel resultaat. Dit kan binnen een enkele computer zijn, of verspreid over meerdere systemen. In het tweede geval is de term distributed computing van toepassing. Gedistribueerd programmeren is het meest effectief bij taken die gemakkelijk in stukken opgedeeld kunnen worden zoals (sommige) puur wiskundige problemen.

Distributed computing (gedistribueerd rekenen) kan gedefinieerd worden als een methode waar gewerkt wordt door verschillende computers, gelinkt middels een communicatienetwerk.

Pioniers in het gebied van gedistribueerd programmeren zijn onder anderen Edsger Dijkstra en Tony Hoare.

Vergelijking met sequentieel programmeren

Een vaak voorkomende beschrijving van de werking van een computer is die waarin een programma een recept is: een lijst van instructies die een voor één, van begin tot eind door de computer uitgevoerd worden (zie ook Von Neumann-cyclus). Dit model van programma's uitvoeren door een computer staat bekend als sequentiële uitvoering van een programma.

Een gedistribueerd systeem is een computerprogramma dat bestaat uit een aantal sequentiële programma's die gelijktijdig kunnen worden uitgevoerd. Dat wil zeggen, ieder deelprogramma wordt op dezelfde manier uitgevoerd als een sequentieel programma, maar ten opzichte van elkaar kunnen de instructies van de subprogramma's gelijktijdig uitgevoerd worden.

Voorbeeld van een gedistribueerd programma:

|[             ||   |[             ||  |[
  x := x + 1   ||      y := y + 1  ||    z := z + 1
]|             ||   ]|             ||  ]|

Gedistribueerd programmeren kent vele varianten van precieze uitvoering; de deelprogramma's kunnen op verschillende processoren uitgevoerd worden of afwisselend op één processor. Er kan gebruikgemaakt worden van meerdere computers in een netwerk of een enkele computer met vele processoren. Iedere variant kent zijn voor- en nadelen.

Synchronisatie en atomiciteit

Interleaving

De techniek van het gedistribueerd programmeren geeft een software-ontwikkelaar extra flexibiliteit in zijn ontwerp, omdat hij de mogelijkheid heeft om een groot programma te verdelen over losse blokken die samenwerken en mogelijk zelfs van de rekenkracht van meerdere processoren tegelijkertijd gebruikmaken. Deze extra flexibiliteit heeft echter wel zijn prijs in termen van extra complexiteit in het ontwerp van de deelprogramma's van een gedistribueerd programma.

In een sequentieel programma is het zo dat ieder statement in het programma uitgevoerd wordt in de volgorde waarin de statements in het programma opgeschreven staan. De opvolging van statements en het effect van die statements op het geheugen van de computer ligt duidelijk vast. Bij een gedistribueerd programma is het echter zo dat meerdere programma's tegelijkertijd draaien en dat de precieze volgorde waarin de statements van de verschillende deelprogramma's worden uitgevoerd ook niet vast ligt. Beschouw het volgende programma:

   Gedeeld:
       var x : integer;
  |
       x := 0;

  Deelprogramma's:
|[                      ||     |[
    do true ->          ||          do true ->
      x := x + 1        ||            x := x - 1
    od                  ||          od
]|                      ||     ]|

De statements van de deelprogramma's kunnen onderling in willekeurige volgorde uitgevoerd worden. Ook is er niets bekend over de snelheid waarmee ieder deelprogramma draait. Het volgende is een mogelijke opeenvolging van statements bij uitvoering van het programma:

   x := x - 1
   x := x + 1
   x := x + 1
   x := x + 1
   x := x + 1
   x := x + 1
   x := x + 1
   x := x - 1
   x := x - 1
   x := x + 1
   x := x + 1
   { x heeft nu de waarde 5 }
   .....

Maar het volgende kan even goed:

   x := x + 1
   x := x - 1
   x := x + 1
   x := x - 1
   x := x + 1
   x := x - 1
   x := x + 1
   x := x - 1
   { x heeft nu de waarde 0 }
   .....

Bovendien zou het kunnen dat een computer de verhoging van x intern als volgt uitvoert:

   y := x;
   z := y + 1;
   x := z

en de verlaging op een soortgelijke manier, waarmee de precieze volgorde van onderlinge statements en hun effecten op het geheugen een nog veel groter aantal variaties kent.

Dit fenomeen (dat de verschillende statements in een programma in verschillende volgorden kunnen worden uitgevoerd) heet interleaving. En een bepaalde volgorde uit alle mogelijkheden wordt ook een (specifieke) interleaving genoemd.

Atomiciteit

Zoals eerder opgemerkt is het bij het gedistribueerd programmeren altijd de vraag hoe statements nu precies uitgevoerd worden en welke statements onderbroken kunnen worden en zo onverwachte uitwerkingen kunnen hebben. Het is daarom bij het gedistribueerd programmeren altijd zaak te weten welke statements ondeelbaar zijn (dat wil zeggen niet onderbroken kunnen worden en dus altijd de verwachte uitwerking hebben). Een dergelijk, ondeelbaar statement wordt een atomair statement genoemd.

Een bijzonder soort van atomair statement is het one-point statement: dit is een statement waarin maximaal één gedeelde variable maximaal één keer voorkomt (dus ook: wordt uitgelezen, of aan wordt toegekend, maar niet beide). Een dergelijk statement is altijd atomair, omdat in een dergelijk statement gebruik wordt gemaakt van het feit dat een computer niet tegelijkertijd kan lezen van en schrijven naar één positie in het geheugen van de computer. Als er dan ook niet van meer dan één gedeelde positie in het geheugen gebruik wordt gemaakt, is het statement per definitie atomair. Bij het algoritme-ontwerp op academisch niveau wordt dan ook vaak gestreefd naar algoritmes op basis van one-point statements - de werking daarvan hangt namelijk niet af van bijzondere maatregelen in een programmeertaal om te voorkomen dat dingen verkeerd gaan.

Synchronisatie

Toch lost het one-point statement niet alle problemen op. Het is soms nodig dat deelprogramma's in een gedistribueerd programma op hoger niveau met elkaar rekening houden dan alleen op het niveau van toegang tot een positie in het geheugen. Te denken valt aan toegang tot randapparatuur, of ervoor zorgen dat een deelprogramma niet te ver op alle andere voor gaat lopen. Het is dan nodig de uitvoering van deelprogramma's te synchroniseren.

Synchronisatie komt er altijd op neer dat een deelprogramma tijdelijk stilgezet wordt totdat aan een bepaalde voorwaarde voldaan is. Hiervoor bestaan vele synchronisatie-mechanismen; voorbeelden hiervan zijn seinpalen (in de literatuur vaak semaforen genoemd), monitors, blokkerende kanalen of busy waiting.

Dit stilzetten is echter ook niet probleemloos: bij onnauwkeurig ontwerp van een gedistribueerd programma dreigt het gevaar van deadlock (alle deelprogramma's komen stil te staan en blijven eeuwig op elkaar wachten), livelock (deelprogramma's blijven, in reactie op andere deelprogramma's, steeds nutteloze handelingen herhalen) of individual starvation (het systeem als geheel loopt door, maar een of meerdere deelprogramma's worden zo snel uitgevoerd dat de rest niet meer aan bod komt). Dat laatste gevaar dreigt ook als in een gedistribueerde programma's met 'prioriteiten' wordt gewerkt (waarbij een deelprogramma meer recht heeft op processortijd dan andere deelprogramma's).

Zie ook wederzijds uitsluitingsalgoritme van Peterson

De voor- en nadelen van gedistribueerde programma's

Over het algemeen is het ontwerp van een gedistribueerd programma aanzienlijk ingewikkelder dan dat van een sequentieel programma. Daarbij geldt ook nog dat een gedistribueerd programma niet méér problemen kan oplossen dan een sequentieel programma (zie ook Turingmachine). Toch geniet het gedistribueerd programmeren veel en aanhoudend ook meer en meer aandacht.

Een reden daarvoor is voornamelijk dat een gedistribueerd programma weliswaar niet krachtiger kan zijn dan een sequentieel programma, maar wel sneller. Gedistribueerde programma's worden dan ook vaak ingezet om de rekenkracht van vele computers te bundelen in de oplossing van één probleem (zie ook distributed computing, SETI, grid computing).

Enkele nadelen

• Het tegelijkertijd plaatsvinden van bewerkingen op of met gedeelde resources (zoals variabelen), levert het probleem op dat men moet kunnen inzien dat «elke mogelijke» executie van een gedistribueerd programma (dus alle interleavings van de verschillende deelprogramma's), correct zijn. Dat wil zeggen, voldoen aan de specificaties van het systeem. Worden daar fouten mee gemaakt, dan kan het absurde resultaten tot gevolg hebben.
• Men moet soms bij de uitvoering van gedistribueerde processen rekening houden met het eventuele crashen van bepaalde delen van het systeem. Bij systemen die slechts uit één proces bestaan is het vaak meteen duidelijk, maar hoe is een systeem goed werkend te houden als het uit vele naast elkaar lopende processen bestaat. Kortom de foutbestendigheid is een complexer probleem.

Enkele voordelen

• Door concurrency (het Engelse woord voor gelijktijdigheid) in systemen wordt het mogelijk verschillende dingen naast elkaar te doen. Denk daarbij aan uw besturingssysteem dat vele programma's (lees: processen) naast elkaar kan draaien. Maar ook in de moderne apparatuur is het nodig dat er tegelijkertijd naar verschillende randapparatuur wordt geluisterd (muizen en keyboards), terwijl het vorige commando nog bezig is uitgevoerd te worden.
• Er is meestal minder programmeerwerk vereist. Immers, als er geen volgorde is, hoeft dit ook niet gecodeerd te worden.
• Men geeft een hoop uit handen aan compilers en het besturingssysteem, waardoor op een hoger niveau de efficiëntie kan worden verbeterd.
• Het systeem is flexibeler; er kunnen makkelijker componenten aan worden toegevoegd of worden aangepast op het moment dat er geen vaste volgorde is in executies. (Anders moet er namelijk een plaats gevonden worden voor de functie in de gehele sequentie).

Varianten en technieken van gedistribueerd programmeren

Over de jaren zijn er veel varianten en technieken van gedistribueerd programmeren ontwikkeld. Zowel op het gebied van hardware-architecture als van software-implementaties zijn zeer vele varianten op het thema ontstaan.

Variaties in de hardware

Als het gaat over gedistribueerd programmeren en het uitvoeren van gedistribueerde programma's, gaat het over het algemeen om twee dingen: processoren (die instructies uitvoeren) en geheugen (waarin data opgeslagen worden).

Processoren

Bij het uitvoeren van gedistribueerde programma's is het mogelijk gebruik te maken van één enkele processor, dan wel van meerdere. In het geval van meerdere is ieder aantal mogelijk tussen 2 en het aantal deelprogramma's dat uitgevoerd moet worden (meer processoren dan dat kan ook, maar is niet nuttig) -- in dit geval spreekt men vaak van parallel programmeren, omdat deelprogramma's dan zeker parallel aan elkaar uitgevoerd worden. In het geval er meer deelprogramma's zijn dan processoren, is het nodig dat een onderliggend systeem (zie besturingssysteem) ervoor zorgt dat ieder deelprogramma regelmatig toegang verkrijgt tot een processor (zie task switching, load balancing, besturingssysteem).

In het geval van meerdere processoren zijn er ook weer variaties mogelijk—te denken valt aan meerdere processoren verbonden met een bus, maar ook processoren verbonden via een netwerk zijn mogelijk. In dit laatste geval is het mogelijk dat er een speciaal ingericht netwerk met een specifieke vorm wordt gebruikt, of een generiek netwerk. In het eerste geval kan met de vorm van het netwerk rekening worden gehouden bij het ontwerp van het parallelle programma om zo optimale rekensnelheden te bereiken; bekende vormen van netwerken zijn het lineaire netwerk (processoren in een rij geschakeld), het cykel-netwerk (een uitbreiding van het lineaire netwerk waarbij er een cirkel gevormd wordt) en de taurus (een vierkant van processoren, waarbij iedere processor verbonden is met buren links, rechts boven en onder). In het tweede geval gaat het vaak over netwerken waarvan de samenstelling niet specifiek voor één taak bedoeld is, zoals een LAN, WAN of het internet (zie Distributed computing en grid computing).

Geheugens

Ook in het gebruik van geheugen is variatie mogelijk. Met name gaat het over de vraag of alle deelprogramma's in het gedistribueerde programma geheugen delen of dat ieder deelprogramma (of processor) een eigen geheugen heeft. Dit heeft voornamelijk weerslag op het gebruik van synchronisatie-mechanismen: seinpalen zijn bijvoorbeeld handiger bij gedeeld geheugen, blokkerende kanalen zijn makkelijker bij individueel geheugen.

Uiteraard zijn variaties in processoren en geheugens ook te combineren: vier processoren voor één geheugen bijvoorbeeld en meerdere van dergelijke blokken. Zie ook SIMD, MIMD.

Variaties in de software

Ook in de software-uitvoering van het gedistribueerde programma is veel variatie ontstaan, zowel op het hogere niveau van programma-architectuur als op het lagere niveau van het organiseren van deelprogramma's.

Architecturen

Over het algemeen zijn er drie architecturen binnen gedistribueerde programma's:

• Het programma is een groot programma dat intern gebruikmaakt van meerdere deelprogramma's - dit zijn tegenwoordig de meeste, bekende desktopprogramma's als tekstverwerkers en spreadsheets: programma's met een duidelijke hoofdtaak op een enkele computer, maar die gebruikmaken van deelprogramma's om bijvoorbeeld een responsievere interface te bewerkstelligen.
• Het systeem bestaat uit opzichzelfstaande deelprogramma's - deze architectuur is meer geëigend om van meerdere processoren gebruik te maken dan de vorige; het is niet noodzakelijk dat alle deelprogramma's gelijk zijn aan elkaar en alleen andere data bewerken, maar het komt wel vaak voor. Bij deze categorie valt te denken aan peer-to-peerprogramma's, programma's als SETI@Home en andere grid-computingimplementaties.
• Client-serverarchitectuur - een architectuur waarbij sommige programma's aan andere programma's vragen om werk voor ze te doen. Deze architectuur is de basis van het huidige internet met bijvoorbeeld het web, waarbij browsers pagina's opvragen van andere computers. In tegenstelling tot de vorige architectuur is er hier duidelijk een hiërarchie van "baas" en "werknemer".

Processen en threads

Ook op lager niveau is variatie ontstaan in de precieze implementatie van gedistribueerde programma's. Bekende termen hier zijn processen en threads (zie ook multitasking).

Het gebruik van processen staat bekend als multiprocessing (waarin ieder deelprogramma door het besturingssysteem als een volwaardig programma wordt gezien met eigen blok geheugen en andere middelen). Bij het gebruik van multiprocessing is het mogelijk ieder deelprogramma te voorzien van alle flexibiliteit die een volwaardig programma ook heeft. Dit is echter wel een zware belasting voor een systeem.

Het gebruik van threads heet multithreading. Een thread is een soort van "deelproces" dat draait op de middelen en een stuk van het geheugen van een normaal proces—waarbij het mogelijk is meerdere threads aan één proces te verbinden. Dit levert een aanzienlijk lagere belasting van het systeem op, maar een thread is wel minder flexibel qua toegang tot het systeem dan een volwaardig proces. Het komt echter vaak genoeg voor dat een parallel programma geen zware systeemtoegang nodig heeft en dus probleemloos met threads uit de voeten kan in plaats van processen.

Zie ook

• Filosofenprobleem

Externe links

• The Transputer Archive—Informatie over transputers, een bekende soort computer die geoptimaliseerd is voor parallelle programma's (gearchiveerd)
• The Occam Archive—Informatie over de Occam taal, die speciaal bedoeld is voor het bouwen van parallelle programma's (gearchiveerd)
• Oracle — De officiële website van Oracle, makers van de Java taal waarin multithreading ingebouwd is

Bronnen

• ISO/IEC standard 9945-1:1996 : De POSIX Threads standaard, een standaard multithreading bibliotheek.
• ISO/IEC 9945-1:2002 en ISO/IEC 9945-2:2002 : De POSIX standaard, waarin onder andere een multiprocessing bibliotheek gedefinieerd is.