Table of contents

1 Multiprogrammeren ten opzichte van sequentieel programmeren 1.1 Synchronisatie en atomiciteit 1.1.1 Interleaving 1.1.2 Atomiciteit 1.1.3 Synchronisatie 2 Nut van multiprogrammeren 3 Varianten en technieken van multiprogrammeren 3.2 Variaties in de hardware 3.2.4 Processoren 3.2.5 Geheugens 3.3 Variaties in de software 3.3.6 Architecturen 3.3.7 Processen en threads 4 Externe links 5 Andere bronnen

Multiprogrammeren ten opzichte van 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 één 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 multiprogramma is een computerprogramma dat bestaat uit een aantal sequentiële programma's die gelijktijdig kunnen worden uitgevoerd. Dat wil zeggen, ieder deelprogramma van een multiprogramma 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 multiprogramma:
 |[ |||[ ||  |[ 
 x := x + 1||y := y + 1  || z := z + 1 
]| ||]| ||  ]| 

Multiprogrammeren kent vele varianten van precieze uitvoering; de deelprogramma's van een multiprogramma kunnen op verschillende processoren uitgevoerd worden of afwisselend op één processor. Er kan gebruik gemaakt 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 multiprogrammeren 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 gebruik maken. Deze extra flexibiliteit heeft echter wel zijn prijs in termen van extra complexiteit in het ontwerp van de deelprogramma's van een multiprogramma.

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 multiprogramma 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 ligt ook niet vast. Beschouw het volgende multiprogramma:

 
  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 multiprogramma:

 
  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 evengoed:

 
  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 ook nog eens 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 multiprogramma 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 multiprogrammeren 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 multiprogrammeren altijd zaak te weten welke statements ondeelbaar zijn (d.w.z. niet onderbroken kunnen worden en dus altijd de verwachtte 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 multiprogramma 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 delprogramma 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, monitors, blokkerende kanalen of busy waiting.

Dit stilzetten is echter ook niet probleemloos: bij onnauwkeurig ontwerp van een multiprogramma 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 multiprogramma met prioriteiten wordt gewerkt (waarbij een deelprogramma meer recht heeft op processortijd dan andere deelprogramma's).

Nut van multiprogrammeren

Over het algemeen is het ontwerp van een multiprogramma aanzienlijk ingewikkelder dan dat van een sequentieel programma. Daarbij geldt ook nog dat een multiprogramma niet meer problemen op kan lossen dan een sequentieel programma (zie ook complexiteitstheorie). Toch geniet het multiprogrammeren veel en aanhoudend ook meer en meer aandacht.

De reden daarvoor is voornamelijk dat een multiprogramma weliswaar niet krachtiger kan zijn dan een sequentieel programma, maar wel sneller. Multiprogramma'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).

Varianten en technieken van multiprogrammeren

Over de jaren zijn er veel varianten en technieken van multiprogrammeren 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 multiprogrammeren en het uitvoeren van multiprogramma's, gaat het over het algemeen om twee dingen: processoren (die instructies uitvoeren) en geheugen (waarin data opgeslagen worden).

Processoren

Bij het uitvoeren van multiprogramma'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 programmere, 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 databus, 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 multiprogramma 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 multiprogramma 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 multiprogramma's:

1. Het programma is een groot programma dat intern gebruik maakt van meerdere deelprogramma's -- dit zijn tegenwoordig de meeste, bekende desktop programma's als tekstverwerkers en spreadsheets: programma's met een duidelijke hoofdtaak op een enkele computer, maar die gebruik maken van deelprogramma's om bijvoorbeeld een responsievere interface te bewerkstelligen.
2. Het systeem bestaat uit op zichzelf staande 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-peer programma's, programma's als SETI@Home en andere grid computing implementaties.
3. Client-server architectuur -- 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 WWW, waarbij browsers pagina's opvragen va andere computers. In tegenstelling tot de vorige architectuur is er hier duidelijk een hiërarchie van "baas" en "werknemer".

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

Het gebruik van processen staat bekend als multiprocessing (waarin ieder deelprogramma door het Operating system 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 op 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.

Externe links

• The Transputer Archive -- Informatie over transputers, een bekende soort computer die geoptimaliseerd is voor parallelle programma's
• The Occam Archive -- Informatie over de Occam taal, die speciaal bedoeld is voor het bouwen van parallelle programma's
• [1] -- De officiële website van Javasoft/Sun Microsystems, makers van de Java taal waarin multithreading ingebouwd is