Moderne Besturingssystemen. dr. Patrick De Causmaecker

Moderne Besturingssystemen dr. Patrick De Causmaecker

Inhoudsopgave 1 Klassieke concepten 1.1 Wat en waarom . . . . . . . . . . . . . . . . 1.2 Toepassingen . . . . . . . . . . . . . . . . . 1.2.1 Fabrieksautomatisatie . . . . . . . . 1.2.2 Andere toepassingen . . . . . . . . . 1.2.3 Bureelautomatisering . . . . . . . . . 1.2.4 Classificatie, taxonomie . . . . . . . . 1.3 Taxonomie . . . . . . . . . . . . . . . . . . . 1.3.1 Multi-processor op een bus (A) . . . 1.3.2 Multi-processor op een netwerk (B) . 1.3.3 Multi-computers op een bus (C) . . . 1.3.4 Multi-computers in een netwerk (D) . 1.4 Software Concepten . . . . . . . . . . . . . . 1.4.1 Network File System . . . . . . . . . 1.4.2 Een echt gedistribueerd systeem? . . 1.5 Communicatie in gedistribueerde systemen . 1.5.1 Overzicht . . . . . . . . . . . . . . . 1.5.2 Het gelaagde model . . . . . . . . . . 1.5.3 Client/Server . . . . . . . . . . . . . 1.5.4 Remote procedure call (RPC) . . . . 1.6 Synchronisatie in gedistribueerde systemen . 1.6.1 Klokken . . . . . . . . . . . . . . . . 1.6.2 Fysieke klokken . . . . . . . . . . . . 1.6.3 Wederzijdse uitsluiting . . . . . . . . 1.6.4 Verkiezingsalgoritmen . . . . . . . . 1.6.5 Atomaire transacties . . . . . . . . . 1.6.6 Gedistribueerde deadlocks . . . . . .

i

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 2 2 4 4 4 7 7 8 9 10 11 11 15 16 16 16 16 23 31 31 34 36 39 40 47

Hoofdstuk 1 Klassieke concepten 1.1

Wat en waarom

Van 1945 tot 1985 heersten centrale systemen. Deze varieerden in grootte van mini-computer tot mainframe. Van 1985 af groeide de concurrentie van de microcomputer. Deze leverde goedkope rekenkracht en voldoende comfort om aan de wensen van een modale gebruiker te voldoen. Het delen van (dure) infrastructuur zoals printers en schijf-eenheden leidde vanaf 1985 tot het ontwikkelen van het local area network (LAN). Dit delen van middelen veroorzaakt conflicten tussen gebruikers en processen waarvan de oplossing duidelijk op het niveau van het besturingssysteem moet gesitueerd worden. Vanaf dit ogenblik spreken we van een gedistribueerd systeem. Deze ontwikkeling is verder te begrijpen op economische gronden. Tot 1980 gold voor de prijs van computer-kracht de wet van Grosch: rekenkracht ' (prijs)2

(1.1)

Dit betekende dat men zijn mogelijkheden kon verviervoudigen door het dubbele uit te geven. Een verhoging van de capaciteit van een centrale computer loonde dus dermate dat men de overhead van een permanent bemand rekencentrum met zeer gespecialiseerde medewerkers kon compenseren door de verhoogde dienstverlening en effici¨entie aan de kant van de gebruikers. Bij de opkomst van goedkope microcomputer-technologie veranderde deze wetmatigheid. De mogelijkheden van deze goedkope chips konden niet zo gemakkelijk uitgebreid worden. Het gevolg was dat men enkel kwantitatief kon uitbreiden en de wet evolueerde naar een lineair verband: rekenkracht ' prijs

(1.2)

Met andere woorden, 1000 20 Mips-chips leverden een rekenkracht van 20000 Mips. Dit is een theoretische bovengrens, in werkelijkheid is communicatie noodzakelijk tussen de processoren wat de werkelijke rekenkracht nog verlaagt. Het werd dus economisch voordelig om veel kleine toestellen te kopen met een standaard uitrusting die volledig ter beschikking van ´e´en gebruiker konden staan en die in een netwerk verbonden waren om het delen van kritische infrastructuur mogelijk te maken. Anderzijds werd het conceptueel mogelijk om ingewikkelde berekeningen te verdelen over verschillende parallelle processoren of computers om de verwerking door parallelle processen te versnellen. Dit model, dat men overgenomen had uit de productie, bleek evenwel veel gecompliceerder dan men aanvankelijk had gedacht. Parallel processen is nog steeds een moeilijk gegeven waarvoor meestal ervaren en gespecialiseerde programmeurs noodzakelijk zijn. De automatisering van deze activiteit (het parallel uitvoeren van programma’s die geschreven zijn voor een seri¨ele processor) is een onderzoeksgebied. 1

1.2

Toepassingen

Om de eisen die aan een gedistribueerd besturingssysteem gesteld worden, beter te begrijpen is het goed naar een mogelijke toepassing te kijken.

1.2.1

Fabrieksautomatisatie

Probleemstelling Bij het automatiseren van de productie wordt op elk niveau intelligentie ingebouwd. Een sensor beslist of een bepaalde waarde acceptabel is of niet. De waarde die de sensor meet kan verbonden zijn met andere waarden voor dezelfde machine. er zal dus al gauw een centraal punt binnen de machine ontstaan waar meetwaarden met mekaar vergeleken worden. Dit centraal controle-orgaan moet de machine doen functioneren en volgt dus een programma dat stuur-signalen uitzendt. Het zal be¨ınvloed worden door de meetwaarden, om de machine te laten doen waarvoor ze ontworpen is. De machines vervullen taken in een een productieproces. Welke taken dit zijn, waar en wanneer die moeten uitgevoerd werd. Welke taken dit zijn, waar en wanneer ze moeten uitgevoerd worden, wordt niet op het niveau van de machines bepaald. Er is een intelligentie die de taken plant en daarbij bepaalde variabelen optimaliseert (kost, doorvoer-tijd, halen van deadlines,. . . ). Deze intelligentie beheert een bepaald machinepark, maar wordt op haar beurt gestuurd door de binnenkomende bestellingen en de economische processen die het bedrijf laten renderen. Welke activiteiten, hoe belangrijk zijn wordt dan wee op het niveau van het bedrijfsbeleid beslist. We zien dat er dus verschillende beslissing-niveau’s zijn, en dat de verdeling of versnippering van de intelligentie toeneemt naarmate men meer gedetailleerd gaat kijken. Een centrale oplossing Men kan het grootste deel van deze beslissingen ondersteunen op een centraal niveau. Eens de metingen gedigitaliseerd zijn kunnen ze door een digitale computer worden verwerkt. De beslissingen worden dan vertaald in digitale stuur-signalen die slechts in de laatste stap naar de individuele machines gebracht worden. In “Stad onder de sterren” beschrijft Arthur C. Clarke een dergelijke situatie waar, een beetje karikaturaal, een centrale computer elk atoom in een ruimtestad controleert. Hierdoor ontstaat een wereld waarin slijtage niet meer bestaat. Afgezien van het het feit dat dit theoretisch onmogelijk is, heeft een dergelijke oplossing een aantal vervelende eigenschappen. 1. De stad hangt voor zijn voortbestaan af van de centrale computer. Als deze uitvalt valt het hele systeem stil. Er is geen zacht verval, het is alles of niets. (Arthur C. Clarke loste dit op door de computer ook zichzelf te laten controleren!) 2. Bij een uitbreiding moet men het model in de centrale computer aanpassen. Bij problemen met een machine moet het centraal model dynamisch aangepast worden. 3. De centrale eenheid is zwaar belast. De benadering heeft ook voordelen. 1. Alle informatie is op ´e´en punt aanwezig. Inconsistenties kunnen tot een minimum herleid worden. 2. Er is een duidelijk beeld van de investeringen. 3. Er is een duidelijk beeld van de operationele kosten. 2

Een hi¨ erarchische oplossing Men kan de knopen in de hi¨erarchische structuur intelligent maken. Het beslissingsmodel wordt dan afgebeeld op de hardware en de software. Beide volgen de boomstructuur. Er zijn enige nadelen aan deze oplossing. 1. De informatie wordt versnipperd. 2. De investerings- en operationele kosten zijn minder transparant. 3. Inconsistenties kunnen ontstaan doordat het beeld van het systeem gedeeltelijk moet overgenomen worden door de verschillende componenten. Het is niet te vermijden dat hierbij bepaalde informatie dubbel opgeslagen wordt. Maar er zijn ook voordelen. 1. Flexibiliteit: het is mogelijk om wijzigingen te beperken tot het niveau waarboven ze niet meer gemerkt worden. 2. Robuustheid: het falen van ´e´en component hoeft niet de werking van het ganse systeem in het gedrang te brengen. 3. Schaalbaarheid: uitbreiding kan relatief gemakkelijk, enkel de bovenliggende knopen moeten aangepast worden. Hoewel dit hi¨erarchische model ontegensprekelijk voordelen heeft, is er toch nog steeds een centrale component aanwezig. Het uitvallen van een computer aan de top van een (sub)boom kan de werking van een hele sector of van het ganse systeem in het gedrang brengen. Bovendien vereist een wijziging nog steeds aanpassingen op verschillende niveau’s. Men heeft dan ook nagedacht over alternatieven. E´en mogelijkheid is de heterarchische benadering. Een heterarchisch model In dit model is er geen centrale supervisie. Een productie-eenheid bestaat uit een aantal cellen die, met een bekende capaciteit, bepaalde taken aankunnen. Binnen een cel functioneren autonome componenten. Zij werken samen op basis van een onderhandelingsmodel. Dit is vaak op de economische wetmatigheid van vraag en aanbod gebaseerd. Een opdracht die een cel binnenkomt wordt toegekend aan de verschillende componenten in een volgorde die bepaald is door een kostenmodel. Er zijn enige nadelen en problemen. 1. Voorspelbaarheid: aangezien de gedetailleerde werking van het systeem bepaald wordt via een onderhandelingsmodel is het moeilijk om gedetailleerde voorspellingen te doen. 2. Het kostenmodel is moeilijk te defini¨eren, en pogingen leiden vaak tot ad hoc oplossingen waarvan men de werking niet goed begrijpt. De voordelen volgen uit de gronden voor de definitie: 1. Flexibiliteit: een nieuwe component kan zichzelf realiseren in de competitie voor opdrachten. Hij hoeft dus niet meer expliciet ge¨ınstalleerd te worden. 2. Beperking van de informatiestroom tussen de componenten. De autonomie maakt het volledig inlichten van alle componenten overbodig. 3

3. Robuustheid: een defecte component kan de werking van het systeem niet in het gedrang brengen. 4. Zelf-organisatie via het onderhandelingsmodel.

1.2.2

Andere toepassingen

Andere voorbeelden van toepassingen zijn wagens, kernreactoren, vliegtuigen, diensten-organisaties, . . . Herhaal de analyse voor een u bekend voorbeeld.

1.2.3

Bureelautomatisering

In de bureelautomatisering is de distributie doorgedrongen via het gebruik van losse PC’s. Deze vervingen aanvankelijk enkel de schrijfmachine. Vandaag worden PC’s in netwerken verbonden om 1. Toestellen te delen (printer, scanner, archief). 2. Communicatie tussen mensen te verbeteren (mail, intranet) 3. De flexibiliteit te verhogen. Ook hier wordt er nagedacht over manieren om de beschikbare middelen beter te benutten. We denken bijvoorbeeld aan systemen die complexe bewerkingen op gegevens kunnen uitvoeren in de dode tijd van de aanwezige computers. Er zijn aan dit proces enige gevaren verbonden. 1. De gebruiker wordt geconfronteerd met een grote complexiteit. Het kan niet de bedoeling zijn dat de gebruiker de details van het netwerk kent. Hij moet integendeel een beeld voor zich krijgen dat coherent is. De computer op zijn bureel dient zich te gedragen als een gesprekspartner met een grondige kennis van wat er zich in het systeem afspeelt. Dit noemen we de “single system image”. Het is alsof alle intelligentie lokaal aanwezig is. 2. Fouten in het netwerk mogen de activiteiten van de medewerkers niet al te zeer be¨ınvloeden. Bij een lokale onderbreking moeten de meeste aangesloten werkstations nog verder kunnen functioneren. 3. De veiligheid en privacy moet op alle niveaus gewaarborgd zijn. Confidentialiteit en versleutelde communicatie dienen transparant verzekerd te zijn. 4. Authentisering moet ondersteund worden zodat de herkomst van een belangrijk bericht kan achterhaald worden.

1.2.4

Classificatie, taxonomie

In 1972(!) definieerde Flynn de volgende categorie¨en voor parallelle systemen. • SISD : Single Instruction Single Data • SIMD : Single Instruction Multiple Data • MISD : Multiple Instruction Single Data 4

• MIMD : Multiple Instruction Multiple Data De ‘Instruction’ en ‘Data’ staan respectievelijk voor stromen van bevelen (het ‘programma’) en stromen van gegevens. • SISD is het model voor de klassieke computer (Mauchly, Eckert en Von Neumann, Von Neumann 1945) met ´e´en verwerkingseenheid waarin geen parallellisme is gerealiseerd. VE1

VE2

VEn

G1

G2

Gn

CG

CE

Figuur 1.1: SIMD met centraal geheugen

• SIMD ontstaat wanneer dezelfde bewerkingen op verschillende gegevens worden uitgevoerd. Een voorbeeld is de lus f or(i = 0; i < 100; i = i + 1)A[i] = B[i] + C[i];

(1.3)

die in de tijd van ´e´en optelling kan worden uitgevoerd indien er meer dan 100 optellers beschikbaar zijn. Ook als het aantal optellers kleiner is dan 100 kan deze lus bij parallelle verwerking sterk versneld uitgevoerd worden. Conceptueel heeft deze architectuur de vorm in figuur 1.1 Bij het uitvoeren van een programma zal de controle-eenheid de gegevens naar de individuele geheugens moeten brengen, en de verwerkingseenheden de juiste instructies moeten geven om tenslotte de resultaten uit de individuele geheugens terug te brengen naar het centrale geheugen. Het is duidelijk dat dit transporteren van data een bottleneck dreigt te worden. Men noemt deze oplossing SIMD met gedistribueerd geheugen. Een alternatief schema is te zien in figuur 1.2. Het centrale geheugen is hier weggelaten, en de verwerkingseenheden hebben toegang tot alle geheugenmodules in het systeem. Hierdoor wordt de controle-eenheid ontlast van het centrale geheugenbeheer. Voordeel is de hogere snelheid, nadeel is de mindere flexibiliteit van het ontwerp. Indien een iteratie dient uitgevoerd te worden, waarbij dezelfde bewerking verschillende keren op de gegevens wordt uitgevoerd, kan men meerder hardware-implementaties van deze bewerking voorzien, wat toelaat de gegevens in een pijplijn te verwerken. Dit principe wordt ge¨ıllustreerd in de figuur 1.3. Als toepassingen van deze vorm van parallelle dataverwerking vernoemen we – Transformations van de pixels in een beeld 5

VE1

VE2

G1

VEn

G2

Gn

CE

Figuur 1.2: SIMD zonder centraal geheugen

Data

IT. Stap

IT. Stap

IT. Stap

IT. Stap

IT. Stap

Uitgang na n stappen

Figuur 1.3: Parallelle iteratie in een pijplijn

– Berekeningen op eindig elementen modellen – RISC processoren functioneren naar buiten toe als SISD machines, maar zijn inwendig voorzien van parallelle circuits. Het parallel maken van het programma gebeurt tijdens de uitvoering. Men komt tot prestaties van meer dan ´e´en instructie per klok-cyclus. (http://www.arstechnica.com/cpu/). • MISD kan gebruikt worden bij zoek-problemen waar grote verzamelingen gegevens op ´e´en criterium worden gecontroleerd. • MIMD is het meest algemene geval. Een pijplijn voor de optelling van re¨ele getallen kan beschouwd worden als een MIMD systeem. Industri¨ele voorbeelden zijn te vinden bij HP, SUN, SGI, IBM, Compaq. CISCO routers, SSL processors, MPEG decoders zijn processoren met een specifiek doel en gebruiken een parallelle architectuur om de verwerking te versnellen. Tenslotte worden er speciale, toepassingsgebonden processoren ontworpen voor het human genome project, simulatie van deeltjesversnellers, simulatie van stroomdynamica, enzovoort.

6

1.3

Taxonomie

Men maakt traditioneel een onderscheid tussen multi-processor systemen en multi-computer systemen. Het verschil ligt in de mate van koppeling. Multi-processor systemen hebben meestal een gedeeld geheugen, terwijl multi-computersystemen meer onafhankelijk zijn en hoogstens voor het hoog-volume permanent geheugen en archivering gedeelde middelen gebruiken. Verder maakt men een onderscheid volgens de structuur van het communicatie-medium. Sterke koppeling gebeurt via een geschakeld netwerk terwijl minder sterk gekoppelde systemen over een bus communiceren.

Multiprocessor

Multicomputer

Bus

A

C

Geschakeld

B

D

Figuur 1.4: Taxonomie van een gedistribueerd systeem

1.3.1

Multi-processor op een bus (A)

Gedeeld Geheugen VE 1

VE 2

VE 3

Figuur 1.5: Multi-processoren op een bus De performantie wordt bepaald door de snelheid van de processoren, de snelheid van het geheugen en de snelheid van de bus, maar ook door de aard van de applicaties. Als het aantal processoren te groot wordt zal, afhankelijk van het gevraagde bus-verkeer, de bus vroeg of laat een bottleneck worden. Het verkeer over de bus kan beperkt worden door elke processor te voorzien van een cache geheugen. Hierin wordt het deel van het geheugen gekopieerd dat momenteel door de processor gebruikt wordt. Als meerdere processoren met hetzelfde deel van het geheugen bezig zijn, ontstaat er een consistentieprobleem. De inhoud van de cache-geheugens gaat verschillen van de inhoud van het geheugen. Dit kan vermeden worden door de combinatie van twee strategie¨en: 7

• Write-through: een leesoperatie kan steeds in de cache gebeuren, maar bij een schrijfoperatie wordt het centrale geheugen onmiddellijk aangepast. • Snooping: elke processor beluistert continu de bus en maakt delen van de cache ongeldig als ernaar geschreven wordt. Bij een volgende leesoperatie zal dit deel vanuit het geheugen opgehaald worden.

1.3.2

Multi-processor op een netwerk (B)

Als men in een systeem met n processoren en n geheugens elke processor verbindt met elk geheugen zijn er n(n − 1)/2 verbindingen nodig. Deze lijnen zullen dus snel meer oppervlakte gaan innemen dan de processoren en geheugens samen. Om dit te verzachten bouwt men geschakelde netwerken. We bekijken de zogenaamde crossbar-switch en het omega-netwerk. De crossbar-switch

G

G

G

VE

VE

VE Figuur 1.6: Een crossbar switch met n = 3

Elke processor is verbonden met n schakelaars en elk geheugen is verbonden met dezelfde n schakelaars. Door de juiste schakelaar te bedienen kunnen er verschillende processoren simultaan toegang krijgen tot verschillende geheugens (zie figuur 1.6). Het aantal verbindingslijnen is 2n en het aantal schakelaars is n2 . Een pad van een processor naar een geheugen vereist het zetten van ´e´en schakelaar. De kostprijs van het netwerk is bepaald door het aantal schakelaars en deze neemt kwadratisch toe met de grootte van het multi-processor systeem. 8

Het omega-netwerk We beschouwen schakelaars met twee ingangen en twee uitgangen (zie figuur 1.7). Elke schakelaar heeft twee standen waarbij telkens twee koppels (ingang, uitgang) met mekaar verbonden zijn. Elke

VE

G

VE

G

VE

G

VE

G

Figuur 1.7: Een omega-netwerk n = 4 schakelaar neemt in wezen ´e´en binaire beslissing. Om toe te laten dat ´e´en processor alle geheugens kan bereiken moeten er voldoende beslissingspunten zijn. Dit betekent: aantalschakelstappen ≥ log2 (n)

(1.4)

Dit geeft aanleiding tot evenveel kolommen van schakelaars in de figuur. Elke kolom verbindt juist n ingangen met evenveel uitgangen, zodat er telkens juist n/2 schakelaars aanwezig zijn. Het aantal schakelaars in een omega-netwerk is dus n log2 (n) (1.5) 2 Dit maakt het goedkoper dan een crossbar-switch. Bij elke verbinding tussen een processor en een geheugen moeten log2 (n) schakelaars gezet worden. Het is dus trager dan de crossbar.

1.3.3

Multi-computers op een bus (C)

Zoals vandaag blijkt is het bouwen van een multi-computer zeer eenvoudig. Elke computer zijn eigen geheugen en randapparatuur. De communicatie tussen de computers gebeurt over een netwerk, dat 9

meestal een bus-topologie heeft. De communicatie tussen de computers is in het concept veel minder intens dan de communicatie in een multi-processor. Vandaar dat een relatief traag netwerk meestal kan volstaan. Hoewel caching in principe niet nodig is zullen we zien dat dit bij het delen van schijfgeheugen wel gebruikt wordt. een mooie oplossing voor het probleem van de inconsistentie bestaat in dit geval niet. Snooping is immers niet mogelijk. Het grootste deel van deze cursus zal over deze architectuur handelen.

1.3.4

Multi-computers in een netwerk (D)

Netwerken van multi-computers kunnen verschillende topologie¨en gebruiken. Een raster kan gerealiseerd worden op een eenvoudige print (zie figuur 1.8). Elke computer die zich niet aan een rand

Figuur 1.8: Een raster met torus topologie bevindt kan rechtstreeks communiceren met 4 naburen. Om de andere computers te bereiken dient hij beroep te doen op computers langs een pad. Door verbindingen te maken van rand tot rand ontstaat een torus. Hierin heeft elke computer exact vier naburen, en dit maakt het ontwerpen van programmatuur eenvoudiger. Een kubus wordt bekomen door 8 computers zo te schakelen dat elke computer drie naburen heeft Een kubus in vier dimensies heeft zestien hoekpunten waarin elk hoekpunt vier naburen heeft. Men kan dit gemakkelijk inzien door de co¨ordinaten van de kubus in een assenstelsel te bekijken. In drie dimensies richten we het co¨ordinatenstelsel zo in dat de oorsprong in het centrum van de kubus ligt, en dat de zijvlakken overeenkomen met de respectievelijke co¨ordinaten 1 en -1 (Zie figuur 1.9). De hoekpunten hebben dan de co¨ordinaten (1,1,1), (-1,1,1), (1,-1,1), (-1,-1,1), (1,1,1), (-1,1,-1), (1,-1,-1), (-1,-1,-1). Twee hoekpunten zijn onmiddellijk met mekaar verbonden indien 10

(−1,−1,1) (1,−1,1)

(−1,1,1) (1,1,1)

(−1,1,−1) (1,−1,−1)

(1,1,−1)

Figuur 1.9: Een kubus in drie dimensies

de co¨ordinraten slechts op ´e´en positie van mekaar verschillen. Er is bijvoorbeeld een rechtstreekse verbinding tussen (1,1,1) en (1,1,-1), maar niet tussen (1,1,1) en (1,-1,-1). Om vanuit ´e´en hoekpunt een ander te bereiken dient men ´e´en voor ´e´en de co¨ordinaten aanpassen, en dit kan dus maximaal op 3 posities nodig zijn. Men veralgemeent dit gemakkelijk tot 4 dimensies. De hoekpunten zijn dan (1,1,1,1), (-1,1,1,1), (1,-1,1,1), (-1,-1,1,1), (1,1,-1,1), (-1,1,-1,1), (1,-1,-1,1), (-1,-1,-1,1) (1,1,1,-1), (-1,1,1,-1), (1,-1,1,-1), (-1,-1,1,-1), (1,1,-1,-1), (-1,1,-1,-1), (1,-1,-1,-1), (-1,-1,-1,-1). Het langste pad tussen twee hoekpunten is heeft dan lengte 4. In n dimensies zijn er 2n hoekpunten. Elk hoekpunt is met n naburen onmiddellijk verbonden. Het langste pad tussen twee hoekpunten heeft lengte n. Als men dus k computers volgens deze topologie met mekaar wil verbinden heeft men een kubus in n = log2 (k) nodig. Per computer moet men n = log2 (k) verbindingen voorzien. In totaal zijn er (k/2) log2 (k) verbindingen nodig. Het langste pad heeft lengte n = log2 (k).

1.4

Software Concepten

Operating systems en software concepten zijn vaak minder goed gedefinieerd dan de hardware waarop ze uitgevoerd worden. Een onderscheid dat zeker gemaakt wordt is dit tussen zwakke en sterke koppelingen. Het systeem met een aantal personal computers met elk een eigen verwerking en geheugen, verbonden via een LAN, met een aantal randapparaten zoals printers, database servers, plotters, enz. is zwak gekoppeld. De componenten hebben een hoge mate van autonomie, de configuratie is zeer flexibel en robuust. Een multiprocessor die in real-time een ruimteschip bestuurt zal het andere uiterste vormen. In deze applicatie spelen fracties van een seconde een belangrijke rol en de componenten zullen perfect samenwerken en op basis van heel strikte contracten taken uitvoeren. We beschouwen nu een voorbeeld van een zwak gekoppelde software configuratie: NFS.

1.4.1

Network File System

NFS is een vroeg voorbeeld van een netwerk operating system. Het concentreert zich op het beschikbaar maken van bestanden over een netwerk. We zullen via dit voorbeeld kennis maken met de vereisten als betrouwbaarheid, authenticatie, performantie, correctheid, flexibiliteit, schaalbaarheid en transparantie zoals die aan een gedistribueerd systeem worden opgelegd. NFS is tevens ´e´en van de eerste voorbeelden waarin het client/server principe gerealiseerd werd. Zonder een netwerk operating system is het toch mogelijk om resources te delen. Zo bijvoorbeeld kent UNIX het bevel rlogin dat toelaat om op een andere machine in het netwerk in te loggen. 11

File Server Client

Client

Aanvraag Antwoord

Figuur 1.10: Een typische werkplek met client-machines en een NFS server

Hierbij verandert de eigen lokale computer effectief in een terminal en kan men processen starten op het andere (remote) UNIX systeem. Een ander bevel is rcp. Het laat toe om bestanden te copi¨eren over het netwerk. Met rcpM achine1 : Bestand1M achine2 : Bestand2

(1.6)

wordt het bestand “Bestand1” op computer “Machine1” gekopieerd naar bestand “Bestand1” op computer “Machine2”. Telnet sessies, ftp, ssh, ... zijn andere voorbeelden. Een nadeel bij al deze oplossingen is het gebrek aan transparantie. De gebruiker moet weten welke computers op het netwerk aangesloten zijn. Soms gaat dat via een naam, maar soms moeten fysieke adressen gekend zijn. Dit is een belasting van de gebruiker die in grotere systemen niet meer werkbaar is. Alleen al het vervangen van een computer of het verplaatsen van bestandensystemen zal problemen opleveren. Men heeft dit vrij vroeg opgemerkt en NFS is een eerste poging om hieraan tegemoet te komen. Het principe is dat machines die bestanden ter beschikking moeten stellen, ingesteld worden als fileservers. Deze nemen aanvragen van gebruikersprogramma’s die op ander machines lopen in ontvangst en laten deze clients toe om bestanden te lezen om om erin te schrijven (figuur 1.10). de bestanden op de file server zijn georganiseerd in een hi¨erarchische structuur, een boomstructuur met een ‘root’ directory en verschillende subdirectories. De clienten importeren een subboom van deze structuur en plaatsen deze in hun eigen boomstructuur. Ze zijn daarbij vrij in het kiezen van de plaats. Eens dit gebeurd is (men spreekt van “mounten”) is de subboom van de file server toegankelijk via de boom van de client. De gebruikersprogramma’s zullen het verschil niet meer merken. De losse koppeling komt hier naar voor in de vrije keuze van de plaats waar een subboom in de eigen hi¨erarchie gemounted wordt. Er is geen enkele garantie noch reden waarom verschillende clienten dezelfde boomstructuur zouden gebruiken. NFS werd oorspronkelijk door SUN Microsystems bedacht en ge¨ımplementeerd voor gebruik op UNIX werkstations. Het is ondersteund in alle UNIX en LINUX implementaties en het is ook vanuit Windows bruikbaar. NFS architectuur Het onderscheid tussen client en server is niet machine-gebonden. wanneer een computer ingesteld wordt als een server betekent dit dat een proces gestart wordt dat aanvragen kan ontvangen en

12

server

client

gemounted

geexporteerd

Figuur 1.11: Het werkingsprincipe van de NFS mount.

beantwoorden. Een client is dan een proces dat aanvragen lanceert. Deze aanvragen kunnen dus zowel van dezelfde als van andere computers afkomstig zijn. De l;ijst van directories die een server ter beschikking stelt wordt bijgehouden in een bestande /etc/exports. Hierin worden tevens een aantal regels voor het gebruik aangegeven. Clienten gebruiken ge-exporteerde directories door ze te mounten. Hierbij zal de gemounte directory deel gaan uitmaken van de eigen hi¨erarchie (zie figuur 1.11). Op deze manier kunnen ook schijfloze clienten ingesteld worden om een schijfruimte op een ander station te gebruiken. Clienten met een eigen schijf kunnen hun bestandensysteem uitbreiden. Twee clienten die dezelfde directory mounten kunnen de gemeenschappelijke bestanden gebruiken. Hiervoor zijn verder geen maatregelen nodig. NFS is conceptueel dus zeer eenvoudig. NFS protocollen De interface tussen clients en servers is essentieel en moet goed gedefinieerd worden. Indien men een client-toepassing schrijft dient deze op alle implementaties te werken. Een protocol is een verzameling aanvragen die door clients naar servers worden gestuurd, samen met de antwoorden die de servers hierop terug kunnen sturen. Buiten de protocollen dient bij de client geen kennis over de structuur van de server vereist te zijn. De client beschouwt de server als een black box. • MOUNT Dit is het eerste protocol waarbij de client toegang krijgt tot een specifieke directory. De client stuurt een pad naar de server en vraagt vergunning om de betreffende directory in zijn eigen hi¨erarchie te mounten. De server controleert of de padnaam correct is, en of de opgegeven directory ge¨exporteerd is. In dit geval levert hij een filehandle af die de client zal gebruiken bij alle verdere toegangen. Clients kunnen zo ingesteld worden dat ze bij de opstart een reeks mounts uitvoeren. Op die manier krijgen de gebruikers steeds dezelfde machine functies aangeboden. Om onnodige vertragingen bij het opstarten te vermijden maakt men gebruik van een “automount” functie die de directories slechts mount als de eerste aanvraag gelanceerd wordt. Dit schept mogelijkheden voor spiegelen waarbij de server die het eerst reageert gekozen wordt (dit is een primitieve vorm het balanceren van de belasting). We moeten ons uiteraard wel realiseren dat het dupliceren van bestanden door NFS niet ondersteund wordt. De consistentie tussen gespiegelde servers zal dus op applicatieniveau moeten gegarandeerd worden. 13

• Een verzameling NFS protocollen regelt de toegang tot directories en files. Er bestaat geen OPEN en teen CLOSE aanvraag. NFS servers houden dus geen lijst bij van welke clienten met welke bestanden aan het werken zijn. De reden hiervoor is schaalbaarheid en betrouwbaarheid. Het bijhouden van lijsten over clienten is een belasting die stijgen met het aantal clienten. Dit is dus niet schaal-invariant. Het bijhouden van open bestanden zou verder inhouden dat de client op de server moet vertrouwen voor deze bestandsinformatie. Bij het uitvallen en terug opstarten van de server kan dit tot problemen leiden. • LOOKUP Om een bestand te lezen moet de client een LOOKUP aanvragen. Hierbij wordt een bestandsnaam opgezocht in de directory-structuur van de server. Het resultaat is een filehandle die bij daaropvolgende READ of WRITE aanvragen gebruikt wordt. De bij deze laatste aanvragen doorgezonden informatie bevat een offset en een grootte van het te lezen deel van het bestand. De server hoeft dus ook hier niks bij te houden tussen twee oproepen en wordt dan ook toestandsloos genoemd. (Een systeem met een toestand is bijvoorbeeld RFS in UNIX SV). Door deze toestandsloze manier van werken ontstaan wel een aantal problemen. Hier vermelden we het op slot zetten van een bestand dat in UNIX mogelijk is maar dat niet zonder meer door de server kan ge¨ımplementeerd worden. Authenticering gebeurt via het NIS (Network Information System) waarin publieke sleutels worden bijgehouden. Elke client heeft zijn eigen private sleutel waardoor zijn identiteit kan gecontroleerd worden door de server. Om de bedrijfszekerheid te verhogen werkt NIS met een master/slave principe. Hierin worden de tabellen gedupliceerd. Na een wijziging zijn er tijdelijk fouten mogelijk. NIS werd vroeger “yellow pages” genoemd en “yp” komt nog steeds voor in de naamgeving van de bevelen die NIS bedienen (ypwhich, ypset,...) NFS implementatie De implementatie van NFS is geen deel van het NFS systeem. Toch is het interessant om te zien hoe het in het UNIX bestandensysteem is ingepast. De client benadert bestanden via de systeemaanroepen (system calls). Transparantie vereist dat programma’s geen onderscheid merken tussen remote bestanden en lokale bestanden. Dit wordt gerealiseerd door een extra laag, het virtuele file systeem (VFS). Een lokaal bestand zal volgens de normale UNIX strategie bediend worfden, een remote bestand via NFS (zie figuur 1.12). In het VFS wordt een tabel bijgehouden met per open bestand ´e´en element. Dit is vergelijkbaar met de i-nodes. In VFS spreken we evenwel van de v-node. Hierin is aangeduid of het om een lokaal of om een remote bestand gaat. Voor een lokaal bestand bevat de v-node een i-node. Voor een remote bestand is er een r-node. Een r-node verwijst naar een element van de tabellen in de NFS client waar zich de filehandle bevindt. Bij het openen van een bestand zal de NFS client de padnaam opzoeken bij de server en de filehandle opslaan in een nieuwe r-node. De VFS zal deze opslaan in zijn v-node. Hierop ontvangt de aanroeper een file descriptor voor de remote file. De tabellen in VFS verbinden de file descriptor met de gepast v-node Bij een READ zal niet alleen het gevraagde blok getransfereerd worden, maar meestal meer. Normaal wordt een blok van 8192 bytes groot overgebracht volgens een read ahead principe. Eenzelfde procedure wordt gebruikt bij een WRITE. Deze resulteert pas in een transfer als het blok van 8192 volledig gebruikt is. Zoals UNIX normaal voor lokale bestanden caches gebruikt, doet ook NFS dit. Clienten hebben caches voor file attributen (cfr. i-node cache in UNIX) en voor bestandsinhoud. Dit vermindert uiteraard het netwerkverkeer. 14

Systeem aanroepen

Virtueel File Systeem

Lokaal

Virtueel File Systeem

NFS

Remote

Remote

Server Bericht

Bericht

Bericht

Figuur 1.12: NFS implementatie in een UNIX systeem

We hebben reeds bij de bespreking van een multi-processor systeem opgemerkt dat caches inconsistent kunnen worden. Snooping vormde toen een oplossing. Dit is hier niet van toepassing. NFS gebruikt een verzachtende benadering als pragmatische oplossing. De geldigheid van cache-blokken wordt beperkt tot 3 seconden voor bestanden en 30 seconden voor directories. Indien een file-blok uit cache wordt gelezen wordt er een signaal naar de server gestuurd om na te gaan of het bestand gewijzigd is. Tenslotte worden alle gewijzigde blokken om de 30 seconden naar de server gestuurd. Dit verbreekt de UNIX semantiek die verzekert dat een blok gewijzigd is zodra het geschreven is.

1.4.2

Een echt gedistribueerd systeem?

NFS is zwak gekoppelde software op zwak gekoppelde hardware. Het beperkt zich tot het organiseren van het delen van de bestanden. De gebruikers zullen dus duidelijk zien dat er meerdere computers zijn. In een echt gedistribueerd systeem zou de gebruiker zich niet bewust hoeven te zijn van de vele computers. Zijn opdrachten zouden ergens in het netwerk uitgevoerd worden en hij zou een “single system image” hebben. Samenvattend stellen we dat een gedistribueerd systeem moet voldoen aan • Transparantie. • Flexibiliteit. • Robuustheid. • Beveiliging. • Schaalbaarheid.

15

1.5 1.5.1

Communicatie in gedistribueerde systemen Overzicht

In deze paragraaf zullen we de effecten van distributie op de communicatie tussen de processen onderzoeken. Theoretisch is het belangrijkste onderscheid met een centrale computer dat de communicatie niet meer volledig betrouwbaar is, en bovendien afhankelijk van de belasting in het netwerk. Het centrale geheugen waar op we vroeger konden steunen is niet meer aanwezig. Hierdoor zijn concepten als semaforen en monitoren moeilijker te implementeren. Synchronisatie van processen zal dus problematischer zijn in gedistribueerde systemen. De communicatie in heterogene, geografische verspreide verzamelingen computersystemen is gebaseerd op het OSI referentiekader. We herhalen kort de struktuur van dit model. De eerste architectuur voor gedistribueerde software werd gerealiseerd in het Client/Server model. We bespreken deze architectuur vanuit de hardware en het operating system, zowel als vanuit de software ontwikkeling. Op dit model is een methode voor uitvoering van procedures op afstand gebaseerd, Remote Procedure Call. Deze vormt het basismodel voor alle verdere ontwikkelingen op dit gebied tot op de dag van vandaag. Tenslotte gaan we in op het begrip groepscommunicatie.

1.5.2

Het gelaagde model

Het OSI model vormt de basis voor de classificatie van communicatie-componenten. Hoewel het niet steeds helemaal gevolgd werd, en enige belangrijke netwerk-architecturen er sterk van afwijken, heeft het het voordeel een algemene, vroeg gedefinieerde norm te zijn (zie figuur 1.13). Bij het doorgeven van boodschappen tussen twee ”peer¨entiteiten in eenzelfde laag wordt de boodschap voorzien van een header (´en een trailer in het geval van de data-link laag) doorgegeven via de interface naar een entiteit in de onderliggende laag. Als de fysieke laag bereikt is wordt de boodschap effectief doorgestuurd. Aan de ontvangende kant wordt een omgekeerde bewerking uitgevoerd. Deze overhead is te verantwoorden omdat het netwerk zeer veel trager is dan de processor. Bewerkingen op de zendende en op de ontvangende machine zijn dus niet bepalend voor de communicatie tijd. De complexiteit in de netwerklagen (fysiek, data-link, netwerk en transport)heeft vooral te maken met het behandelen van de geografische spreiding en de heterogeniteit van de netwerkinfrastructuur en van de communicerende computers in een wide area network (WAN). In een local area network (LAN) is taak van deze lagen eerder beperkt. Tegelijk liggen de verhoudingen van de snelheden anders. De tijd nodig voor communicatie is kleiner, en meer van dezelfde orde van grootte als de tijd voor de verwerking op de computers.

1.5.3

Client/Server

Het OSI model biedt een oplossing voor het doorzenden van boodschappen tussen applicaties. Het zegt evenwel niks over de structuur van een gedistribueerd systeem. Het Client/Server model is een poging om een dergelijke structuur te bouwen. Het is de bedoeling een gedistribueerd besturingssysteem te bieden waarin processen samenwerken door effici¨ente communicatie. Het is op het niveau van deze processen dat het Client/Server model een eerste classificatie definieert.

16

proces B

proces A

applicatie−protocol applicatie

applicatie

presentatie−protocol presentatie

presentatie

sessie−protocol sessie

sessie

transport−protocol transport

transport

netwerk−protocol netwerk

netwerk

datalink−protocol datalink

datalink

fysiek protocol fysiek

fysiek

Figuur 1.13: Het OSI model Twee soorten communicerende processen Servers zijn processen die op aanvraag bepaalde taken uitvoeren. Clienten zijn processen die diensten van Servers aanvragen. Er is een vraag/antwoord protocol dat de communicatie tussen clienten en servers regelt. We beschrijven in eerste instantie een ideaal, “zuiver”, client/server systeem. We gaan ook in op implementatie-problemen, en bediscussieren een paar fundamentele keuzes bij het ontwerp van een dergelijk systeem. Op deze manier hopen we tegelijkertijd de problematiek van communicerende processen in het algemeen duidelijk te maken. De communicatie wordt verzorgd door kleine kernels die op alle machines draaien en die zich enkel met de (netwerk) verbindingen en het afhandelen van de verzending van de boodschappen hoeven bezig te houden (zie figuur 1.14). Alle andere diensten van het besturingssysteem, waaronder het beheer van de schijfruimte, worden door processen in het gebruikersgeheugen gerealiseerd. Om geen onnodige overhead te veroorzaken worden, in het geval van identieke machines, enkel lagen 1,2 en 5 gebruikt (zie figuur 1.15) De procedure met vraag en antwoord vereist geen verbinding. De client moet enkel weten hoe de server te bereiken, en omgekeerd. In principe hoeft de kernel slects twee systeemaanroepen aan te bieden: 17

?? C

S !! Kernel

Kernel

Figuur 1.14: Client en server communiceren via een eenvoudige kernel

Vraag/Antwoord

Data Fysisch Figuur 1.15: Enkel lagen 1,2 en 5

18

de send en de receive. In het onderstaande voorbeeld wordt van deze twee diensten gebruik gemaakt in een demonstratieprogramma dat een bestand doorzoekt. Een voorbeeld We bespreken twee programma’s, in C-taal. E´en implementeert een server, het andere een client. De server is een file server, en accepteert vragen READ en WRITE. De client laat de gebruiker toe om een string te specifi¨eren en geeft een getal terug dat aangeeft op welke positie in het bestand de string het eerst aangetroffen wordt. Het resultaat is negatief indien de string niet in het bestand voorkomt. Om de co¨odinatie tussen de twee functies te verzeker, is een gemeenschappelijke header geschreven die de nodige constanten vastlegt. #define MAXNAAM 255 // de maximale lengte van een bestandsnaam #define BUFFERGT 1024 // de maximale hoeveelheid data per READ #define FILESERVER 243 // het netwerkadres van de file server #define READ #define WRITE #define #define #define #define

1 2

// de lees-opdracht // de schrijf-opdracht

OK 0 // foutkodes EOPERATOR -1 // slechte operator EPARAMTER -2 // slechte parameter EIO -3 // slechte io

// Het bericht is gedefinieerd als een struct struct bericht { long long long long long char char };

bron; // de afzender opcode; // de gevraagde of uitgevoerde operatie aantal; // het aantal te lezen of gelezen bytes offset; // waar moet gelezen worden resultaat; // het resultaat van de operatie naam[MAXNAAM]; // de naam van het bestand, identificatie server data[BUFFERGT]; // plaats voor de gelezend data

Het resultaatveld bevat informatie over de operatie. Indien deze geslaagd is geeft ze aan hoeveel bytes er gelezen werden, en is dan positief. Een negatief resultaatveld duidt op een fout. Bij het versturen van een verzoek bevat het veld “opcode” de aard van de gewenste dienst. De code voor de server ziet er als volgt uit. #include void main(void) { struct bericht b1, b2; int resultaat; while (true) { 19

receive(FILESERVER, &b1); switch (b1.opcode) { case READ : resultaat = readFile(&b1,&b2); case WRITE : resultaat = readFile(&b1,&b2); default : resultaat = E_OPERATOR; } b2.resultaat = resultaat; send(b1.bron,&b2); } } De server wacht dus op een boodschap (een aanvraag) van een client in de “receive”. Hij is hier effectief geblokkeerd tot een dergelijke aanvraag binnenkomt. Afhankelijk van de in bericht b1 gespecifieerde operator, voert hij een READ of een WRITE uit, en plaatst de resultaten in bericht b2. Hij zendt het resultaat terug naar de afzender. En wacht op de volgende opdracht. De code van de client zou er als volgt kunnen uitzien. We veronderstellen dat alles in de functie “zoek” moet gebeuren. Deze kan vanuit een hoofdprogramma opgeroepen worden als zoek("\dataFolder\dataBestand","stortbad")

(1.7)

om het woord “stortbad” op te zoeken in het bestand \dataFolder\dataBestand #include long zoek(char file[],char zoekString[]) { struct bericht b1; long positie; long gevonden; long client = 110; positie = 0; b1.resultaat = 0; do { positie += b1.resultaat; b1.opcode = READ; b1.offset = positie; b1.aantal = BUFFERGT; strcpy(b1.naam, file); send(FILESERVER, &b1); receive(client, &b1); if (b1.resultaat > 0) gevonden = zoekData(b1.buffer,b1.resultaat,zoekString); } while (b1.resultaat > 0 && gevonden < 0); if (gevonden >= 0) return positie+gevonden; else return -1; }

20

(1.8)

De client initialiseert de boodschap. Ze word via “send” verzonden naar “FILESERVER”. Hierna blokkeert de client tot een antwoord binnenkomt in “receive”. De functie “zoekData” wordt opgeroepen om in “b1.resultaat” bytes te gaan zoeken naar de “zoekString”. De lus eindigt onmiddellijk als de string gevonden wordt. Merk op dat er geen enkele status bijgehouden wordt op de server. Deze hoeft enkel de vragen te behandelen. Adressen In het voorbeeld worden getallen gebruikt als adressen. Het is de bedoeling dat deze uniek zijn in de pool van processen. Het voorbeeld gaat eigenlijk uit van een centrale toekenning. De kernels worden zo ingesteld dat ze weten waar een bepaald procesnummer kan gevonden worden. Een alternatief is het gebruiken van adressen van de vorm “machine.proces” waarin de computer waarop de server draait moet opgegeven worden. Deze methode wordt gebruikt in bepaalde UNIX implementaties. Het centrale en ´e´enmalige toekennen van unieke procesnummers is nadeling voor de flexibiliteit. Iets beter zou bijvoorbeeld zijn dat de servers centraal toegekend worden, en zich allemaal in eenzelfde ruimte bevinden (bijvoorbeeld tussen 0 en 1000). De clientprocessen kunnen dan vrijgelaten worden om een nummer te kiezen tussen 1.000 en 1.000.000.000. Als zij een randomgenerator gebruiken is de kans op botsingen klein. We spreken van een “ijle” adresruimte. Als we dit ook voor de serverprocessen toelaten kunnen zij op twee manieren tewerk gaan. 1. Zij moeten hun adres rondzenden via een “broadcast” zodat alle potenti¨ele clienten het nummer, eventueel via hun kernel, kunnen opzoeken. 2. Alle processen hebben een identificatie (een naam). Bij een eerste aanvraag lanceert de kernel van de client een broadcast om de server te localiseren. De server die zijn identificatie herkent antwoordt met zijn procesnummer. Een laatste, krachtiger, methode is het gebruik van een “nameserver” die geraadpleegd wordt om namen van servers te vertalen in procesnummers. Deze nameservers kan men dan via ´e´en van de vorige methodes localiseren. Blokkeren of niet blokkeren Bij het ontwerp van de interface naar de diensten van de kernel neemt men beslissingen die zowel voor het ontwerp als voor het gebruik gevolgen hebben. Een belangrijke vraag is of men de aanroepen naar “send” en “receive” blokkerend of niet-blokkerend definieert. Merk op dat we het hier hebben over de aanroepen naar de kernel, en niet over de functies van deze twee procedures. Een blokkerende “send” laat het proces wachten tot de boodschap verzonden is, en niet tot het antwoord terugkomt. De functie “receive” wordt normaal als blokkerend beschouwd. Het is de bedoeling dat het oproepende proces wacht tot een boodschap binnenkomt. Indien dit niet-blokkerend is, dan moet men een mechanisme voorzien worden dat toelaat het proces in te lichten over de aankomst van een boodschap. Dit maakt de taak voor de programmeur moeilijker. Indien men in parallel, het proces aan andere zaken wil laten werken kan men best gebruik maken van threads. Dit zien we later. Een blokkerende “send” wacht dus tot de boodschap volledig verzonden is alvorens het oproepende proces verder te laten werken. Dit heeft het voordeel dat de kernel de gegevensstructuur met de boodschap kan gebruiken, en zich geen zorgen hoeft te maken dat het proces deze ondertussen overschrijft. Een nadeel is dat het proces een dode tijd kent bij het verzenden van een boodschap. Een niet-blokkerende “send” vereist dus bijzondere maatregelen voor de afhandeling van de operatie. Indien de kernel de gegevensstructuur met de boodschap ter plaatse leest terwijl ze doorgestuurd 21

client

client

send

start

return

trap

end

t

client vervolgt, voorzichtig

client

send

start

trap client

return

end

t

client vervolgt, onverstoord

kopieer naar buffer en send

start

trap

return

end

t

Figuur 1.16: Blokkerende of niet-blokkerende “send”

wordt, mag het proces deze data niet wijzigen alvorens de verzending volledig is afgewerkt. Dit betekent dat het op de hoogte moet worden gebracht op het ogenblik dat het zover is. Het moet bovendien wacht-condities kunnen inbouwen indien toegang tot de gegevensstructuur toch vereist is. Voor de programmeur zal de beste oplossing erin bestaan het verzenden in een thread te laten gebeuren, die vanuit een eigen geheugengebied verzendt, en die wacht tot de data verzonden zijn. Dit komt eigenlijk overeen met de handelswijze in het geval van een blokkerende send. De kernel kan een niet-blokkerende “send” ook implementeren door een kopie van de gegevensstructuur te maken. Hij gebruikt dan inwendig een buffer van waaruit de bytes verzonden worden. Dit maakt de kernel ingewikkelder aangezien hij nu deze buffers moet beheren. Bovendien worden de gegevens extra gekopieerd. Indien er slechts ´e´en buffer gebruikt wordt, kan geen enkel proces een “send”’starten terwijl een verzending bezig is. Dit kan opgelost worden via meerdere buffers die als een mailbox beheerd worden. Merk op dat hierdoor nog steeds slechts pieken tot een bepaalde hoogte kunnen worden opgevangen. De mailbox heeft immers ook een eindige capaciteit. (zie figuur 1.16)

22

vraag client

antwoord

vraag client

client

antwoord

ok vraag

ok vraag

ok antwoord

ok antwoord

client

Figuur 1.17: Betrouwbare communicatie door bevestiging van ontvangst

Bufferen of niet bufferen Aan de “receive”-kant moet nog een onderscheid gemaakt worden. Als er geen buffer ingebouwd wordt, moet de ontvangende kernel het bericht onmiddellijk in het geheugen van het ontvangende proces plaatsen. De hiertoe gecre¨eerde buffer wordt een kritische sectie, zodat het ontvangende proces dient geblokkeerd te worden. Indien de receive blokkerend werkt, hoeven geen extra maatregelen genomen te worden. Een extra probleem ontstaat natuurlijk wel indien het ontvangende proces de een nieuwe boodschap ontvangt alvorens het de vorige heeft ontvangen. Dit kan gebeuren indien de server-belasting hoog is en de uit te voeren taak omvangrijk. De kernel kan dus best zelf bufferen, eventueel via een mailbox, wat opnieuw toelaat pieken tot een bepaalde hoogte op te vangen. Betrouwbaar of niet betrouwbaar Een laatste ingrijpende beslissing die bij het ontwerp wordt gemaakt is wat er gebeurt in het geval van een communicatiefout. Wanneer de client zijn “send” heeft uitgevoerd en hij verder kan werken zijn er drie mogelijkheden (zie figuur 1.17): 1. Hij weet niet wat er met zijn boodschap gebeurt. Deze kan verloren gaan. Het systeem zal enkel de kans op verlies proberen te beperken. Dit is de eenvoudigste benadering. De correcte werking van het protocol tussen client en server wordt aan de toepassing overgelaten. 2. De kernel van de ontvangende machine zendt een bevestiging. De kernel van de client heft de blokkering slechts op nadat deze bevestiging is aangekomen. De client verkrijgt dus zekerheid over de aankomst van zijn boodschap. In ruil levert hij rekenkracht in (dode tijd). Om blokkering bij uitval van de ontvanger of bij een communicatiefout te voorkomen voorziet men een time-out toestand. Dit gebeurt twee maal: de client zendt een vraag naar de server. De server antwoordt. 3. In het client/server protocol wordt elke vraag beantwoord (of men eist dit). De client blijft geblokkeerd tot het antwoord terug komt. De server krijgt bevestiging van de client over de aankomst van zijn boodschap. Hier wordt enige overhead ge¨elimineerd. Tegelijkertijd wordt de functionaliteit van het communicatieprotocol gewijzigd: de client blokkeert tijdens de afhandeling van de boodschap door de server. Dit kan problematisch als er onvoldoende zekerheid is over de afhandeling van de boodschap in een eindige tijd. Wat gebeurt er als de server crasht of tijdelijk overbelast is? Opnieuw dient een time-out voorzien te worden.

1.5.4

Remote procedure call (RPC)

Het client/server protocol steunt op het uitwisselen van berichten tussen applicaties. In de jaren 80 van vorige eeuw merkten Birrell en Nelson op dat dit in strijd was met de functie-oproep interface 23

Lokale Variabelen van Een boodschap

Lokale Variabelen van Een boodschap

Lokale Variabelen van Een boodschap

naar

naar

naar

s1 s2 n

voor

256

tijdens

na

Figuur 1.18: De evolutie van de stapel tijdens de oproep van strncpy

die men in courante programmeertalen gebruikt om modules met mekaar te verbinden. Zij stelden een methode voor om toe te laten dat applicaties functies op een ander toestel zouden oproepen. Dit werd de functie-oproep op afstand of remote procedure call. Deze methode biedt een alternatieve benadering voor het client/server model. Ze is vandaag nog in gebruik. Ernaast staan variaties op hetzelfde thema zoals we ook boodschap-gebaseerde variaties van client/server terugvinden. Hoe werkt RPC? RPC biedt de mogelijkheid functies op te roepen die zich op een ander toestel bevinden. Voor de transparantie bedachten Birrell en Nelson een techniek die goed lijkt op een gewone functie-oproep. Laten we eerst een voorbeeld van een gewone oproep bekijken. In de c-bibliotheek vinden we de functie strncpy. Deze is gedefinieerd als volgt. char ∗ strncpy(char ∗ s1, constchar ∗ s2, size tn);

(1.9)

Deze functie kopieert een string (s2) met een maximale lengte (n) naar een andere string (s1) . Als resultaat geeft de functie een pointer naar de gekopieerde string terug (s1). Door het gebruik van const in het prototype belooft de functie strncpy om de string s2 niet te wijzigen. Een oproep van deze functie kan er dan als volgt uitzien. ... char naar[256]; char van = "Een boodschap\n"; strncpy(naar,van,256); ... Bij de oproep zal voor de doorgegeven variabelen zowel als voor de lokale variabelen binnen strncpy plaats gereserveerd worden op een stapel (zie figuur 1.18). De twee string-variabelen worden doorgegeven via een pointer. Dit noemen we call by reference . De geheeltallige variabele n wordt doorgegeven als een getal. Deze waarde wordt gekopieerd naar de lokale variabele. We spreken van call by value Stcnpy werkt door ter plaatse te kopieren, in het geheugengebied van de oproepende functie. De manier waarop parameters doorgegeven worden is van groot belang bij RPC. Er bestaat 24

variabele

37

variabele

37

Lokaal

37

variabele

132

132

voor

tijdens

na

Figuur 1.19: De evolutie van de stapel tijdens een oproep met copy/restore

nog een derde manier, namelijk call by copy/restore . Hierbij wordt de waarde tweemaal gekopieerd, eemnaal bij de oproep, naar het gebied van de opgeroepen functie, en eenmaal bij het be¨eindigen terug naar het gebied van de oproepende functie (zie figuur 1.19). De programmeertaal C gebruikt dit mechanisme niet. De manier waarop een variabele doorgegeven wordt hangt af van het type van de variabele. In C++ kan men aangeven (via &) of een variabele via zijn waarde of als een referentie moet doorgegeven worden. Dit is ook het geval in Pascal. In ADA gebruikt men de woorden in, out, en inoutom de functionaliteit aan te geven. In-parameters worden by valuedoorgegeven. Out-parameters worden bij het terugkeren gekopieerd. Inout-parameters dienen beide doelen: het doorgeven van een waarde bij de oproep en het ontvangen van een resultaat. Deze laatste worden afhankelijk van de Ada-compiler behandeld door een call by reference of een copy/restore . Stel nu dat we de functie strncpy op een andere computer willen laten uitvoeren. Het is duidelijk dat de call by reference de meeste problemen zal veroorzaken. De opgeroepen functie moet dan immers toegang hebben tot het geheugengebied van de oproepende functie. Dit geheugengebied bevindt zich op een andere machine. Elke dergelijke toegang zou communicatie in het netwerk veroorzaken. De functie zou zeer zorgvuldig moeten ontworpen worden om het communicatiekanaal minimaal te belasten. Daarentegen stelt call by value geen onoverkomelijke problemen. Bij de oproep wordt de waarde doorgestuurd, en ze hoeft niet terug te komen. Copy/restore is ook zeer goed gedefinieerd. Bij de oproep geven we de waarde door, en bij het be¨eindigen wordt de gewijzigde waarde terug gestuurd. Bij het ontwerpen van RPC was het de bedoeling om het gebruik transparant te maken. De oproep van een remote procedure zou op dezelfde manier moeten kunnen gebeuren als de oproep van een lokale functie. Bovendien zou de techniek onafhankelijk moeten zijn van de programmeertaal. Om dit te verwezenlijken wordt de volgende methode gebruikt. Een remote procedure zoals strncpy wordt via de functie-bibliotheek aangeboden als een gewone functie. Vanuit de programmeertaal kan de programmeur de functie oproepen zoals hij andere functies aanroept. Hij hoeft in principe zelfs niet te weten dat het om een remote functie gaat. In de bibliotheek bevindt zich niet de normale kode voor de functie, maar een doorgeefluik naar de functie aan de andere kant. We noemen dit de client stub . De client stub aanvaardt de parameters in de oproep en verpakt ze voor verzending. De kernel stuurt het pakket door naar de server waar zich de ander kant van het luik bevindt, de server stub . In deze server stub worden de parameters uitgepakt en aan de eigenlijke kode aangeboden. Eens de functie be¨eindigd is heeft het omgekeerde proces plaats (zie figuur 1.20). 25

aanroep

pak par’s uit

pak par’s in

aanroep server

client terug

pak res. in

pak res. uit

kernel

terug

kernel

Figuur 1.20: In en uitpakken van parameters in de stubs van RPC

Het doorgeven van de parameters Het in en uitpakken van de parameters is het centrale deel van dit werkingsprincipe. We noemen het parameter marshalling . Traditionele programmeertalen laten de compiler vaak vrij in de keuze van de representatie van datatypes. Zo is de int in C een type waarvoor de compiler de best passende grootte mag kiezen. Meestal wordt een datatype gekozen dat door de processor ondersteund wordt. Hetzelfde kan gezegd worden over de karakter-tabel. De meeste computers gebruiken ASCII, andere gebruiken EBCDIC als kode voor het voorstellen lettertekens. UNICODE is een meer recent alternatief. Bij het voorstellen van gehele getallen zijn twee conventies gangbaar, de zogenaamde little endian en big endian voorstellingswijzen. De compilers gebruiken de conventie die bij het systeem past. Als men via RPC van ´e´en systeem naar een ander parameters uitwisselt, dan moet daar rekening mee gehouden worden. Het is duidelijk dat men een conventie dient af te spreken, een intermediaire canoniekevorm dient te gebruiken, of gespecialiseerde stubs dient te schrijven die goed begrip aan beide zijden van het luik verzekeren. Een ander probleem vormen de pointers. Pointers zijn een min of meer type-veilige vorm van geheugenreferentie. Ze verwijzen typisch in het eigen centrale geheugen en laten toe om manipulaties van dit geheugen te programmeren. Indien pointers gebruikt worden bij RPC oproepen kan de remote functie verplicht worden tot een aantal geheugentoegangen over het netwerk. De complexiteit die hierbij ontstaat is moeilijk te overzien. Een oplossing kan erin bestaan het geheugenblok waarin zich de datastructuur bevindt, door te zenden, bij de oproep of bij de eerste toegang. In een andere methode wordt een gekodeerder versie van de datastructuur doorgestuurd. Hierbij moet aan de zendende kant ingepakt en aan de ontvangende kant uitgepakt worden. We zullen dit uitgebreider behandelen als we op objecten gebaseerde methodes bespreken. Dynamische binding Hoe vindt de client zijn server? De oplossingen vari¨eren van eens voor altijd systemen tot dynamische flexibele oplossingen. E´en manier is te veronderstellen dat de programmeur alles beslist. Dit betekent dat deze vastlegt waar de servers voor de verschillende functies zich bevinden. Bij een herconfiguratie, bijvoorbeeld omwille van performantie, moeten alle programma’s onderzocht en aangepast worden. Iets beter als dit in configuratiebestanden gebeurt. Elke client heeft zijn eigen configuratiebestand 26

waarin aangegeven wordt waar welke servers lopen. Dit heeft het voordeel dat bij een herconfiguratie alleen de bestanden van de clients moeten aangepast worden. Tijdens het uitvoeren heeft een programma evenwel geen enkele manier om een nieuwe functie te zoeken, of om een alternatieve koppeling te maken indien een server overbelast is of niet meer reageert. Dynamische binding veronderstelt geen configuratiebestand. Er wordt uitgegaan van een formele specificatie van de serverfuncties. Voor een server met als functies read, write, create en delete zou de specificatie er als volgt kunnen uitzien. specification of fileserver, version 2.3; long read(in char nm[MAXNM], out char buf[BUFFERG], in long nbytes, in long positie); long write(in char nm[MAXNM], out char buf[BUFFERG], in long nbytes, in long positie); int create(in char[MAXNM], in int mode); int delete(in char[MAXNM]); end; De kernwoorden in en out geven aan dat het om input of output parameters gaat. Ze worden als waarde doorgegeven in de gepaste richting. Verder bestaat het woord inout voor het aangeven van een copy/restore parameter. Het voordeel van het aangeven van de richting waarin een parameter moet gekopieerd worden is belangrijk voor de stub’s. Op basis van deze informatie kan de communicatie beperkt worden tot het noodzakelijke. Deze specificatie dient in de eerste plaats als input voor het genereren van de stub’s aan clienten serverkant. Wanneer een programmeur van een client-programma nu bijvoorbeeld de functie read aanroept, zal bij het linken de door de stub aangeboden de zogenaamde proxy versie van de functie gebruikt worden. Een proxy is in dit geval ´e´en zijde van het doorgeefluik. Het is in een functie die, via de kernel, de opdracht doorspeelt naar de machine waarop de functie in werkelijkheid loopt. In de tweede plaats dient de formele specificatie om de communicatie tussen client en server tot stand te brengen. Bij het opstarten van de server-functie exporteert de server zijn specificatie via een programma dat een binder wordt genoemd. Dit proces noemen we het registreren van de server. Het omgekeerde proces bestaat ook, hierbij maakt de server zijn registratie ongedaan. Na de registratie beschikt de binder over een unieke identifier (volgens ´e´en van bovenstaande methodes), en een handle die hem in staat stelt de server te vinden. Eventueel is er ook beveiligings- of afschermingsinformatie aanwezig. Als een client een server wil vinden, bijvoorbeeld als het programma bij een read is aangekomen, zal clientstub merken dat er nog geen verbinding gemaakt is. Hij zendt een boodschap naar de binder met de vraag om die bepaalde versie van die bepaalde server te importeren. De binder kiest ´e´en van de beschikbare servers die deze functie met dit versienummer hebben ge¨exporteerd. Als er een geschikte server gevonden wordt geeft de binder de handle en de unieke identifier door aan de clientstub. Hierna zal de stub de handle en de unieke identifier gebruiken om de server met de gepaste parameters te contacteren en de functie uitgevoerd te krijgen. De soepelheid van deze manier van dynamische binding is een duidelijk pluspunt. Aan de negatieve kant noteren we het extra werk voor het importeren en exporteren van de interfaces. Dit effect kan aanzienlijk zijn aangezien vele functies slechts af en toe zullen opgeroepen worden. De binder kan een bottleneck worden bij grote systemen. Een andere tekortkoming is de semantiek. De specificatie van de interfaces is slechts ´e´en facet. De betekenis van de functies is een ander. Het systeem gaat

27

uit van een ondubbelzinnige naamgeving. Het is niet duidelijk dat dit in een heterogeen systeem kan gegarandeerd worden. RPC wanneer fouten optreden In zowel gecentraliseerde als gedistribueerde systemen kunnen fouten optreden. Gedistribueerde systemen hebben een parallel karakter. Dit betekent dat de foutafhandeling verschillend zal zijn. We bekijken 5 fouten die enkel kunnen optreden in een gedistribueerd systeem. • Een niet te vinden server Als de binder de server niet vindt zal hij bij de client een foutmelding genereren. De oorzaak van de fout kan bij een client liggen, die nog een oude versie wil gebruiken, of bij de servers die zich toevallig allemaal hebben afgemeld. De beste manier om de client op de hoogte te brengen is het exception mechanisme. Bij het optreden van een fout wordt een boodschap gegenereerd die op de ´e´en of ander manier door het programma opgevangen wordt. De overhead die hierdoor veroorzaakt wordt verschilt per programmeertaal, maar kan in sommige gevallen oplopen tot 90 % van de programmeer-inspanning. De bijkomende complexiteit veroorzaakt door distributie dient dus in rekening te worden gebracht bij het inschatten van ontwikkelingsprojecten. Hedendaagse raamwerken bieden voor de meest optredende fouten een standaard afhandeling, waardoor de druk op de programmeurs kan verminderen. • Verloren aanvragen Het afhandelen van een verloren aanvraagbericht kan gebeuren door de kernel een timer te laten bijhouden die niet mag aflopen voordat er een antwoord of bevestiging komt. Indien de timer toch afloopt zendt de kernel opnieuw. Als het eerdere bericht inderdaad verloren is gegaan, weet de server van niets en handelt de opdracht op de gewone manier af. Indien de pogingen van de kernel blijven mislukken zal hij terugvallen op het geval van de niet te vinden server . • Verloren antwoorden Ook hier zouden we een timer kunnen gebruiken. Het probleem is echter dat de kernel niet kan weten of het antwoord verloren is gegaan, dan wel de aanvraag. Indien de aanvraag verloren ging, is de voorgaande handelswijze correct. Indien het antwoord verloren ging, heeft de server eventueel acties ondernomen die niet opnieuw mogen gebeuren. Acties die een willekeurig aantal keer mogen uitgevoerd worden noemen we idempotent. Niet alle acties zijn idempotent. Het overschrijven van geld van een bankrekening, bijvoorbeeld, kan best geen willekeurig aantal keer uitgevoerd worden. Om dit te vermijden kan men elke aanvraag van een nummer voorzien. Als een server een boodschap krijgt met een nummer dat lager is dan het nummer van de laatst uitgevoerde opdracht, kan hij besluiten dat het om een herhaalde vraag gaat, en dat deze niet opnieuw dient uitgevoerd te worden. Een alternatieve benadering is het gebruik van een versheidsbit. Als deze bit aanstaat, dan gaat het om de eerste transmissie van een aanvraag. Als de bit niet aanstaat moet de server bij niet idempotente opdrachten controleren of het om een herhaling gaat. • Uitgevallen server Het uitvallen van een server illustreert het best de complexiteit veroorzaakt door distributie. Men kan de server-activiteit opsplitsen in drie phases: ontvangst, uitvoering, antwoord. Als de server uitvalt voor ontvangst van een boodschap gaat het om een niet te vinden server. Als de 28

crash zich voordoet na ontvangst, maar voor de uitvoering is er nog niets gebeurd, en moet de opdracht nog uitgevoerd worden. Als de crash optreedt na uitvoering, maar voor het verzenden van het antwoord, is de opdracht uitgevoerd, maar zal de client er nooit van horen. In dit geval mag de opdracht niet nog eens uitgevoerd worden. Dit veronderstelt telkens dat de uitvoering als ´e´en atomair geheel kan behandeld worden. Het probleem is wat de server moet doen als hij terug opstart. Er bestaan drie benaderingen: 1. In de at-least-once semantiek wordt de opdracht minstens ´e´en maal uitgevoerd. De client kan hiervan uitgaan, maar moet er rekening mee houden dat een opdracht meerdere malen uitgevoerd kan worden. 2. In de at-most-once semantiek heeft de client geen garantie dat de opdracht ´e´enmaal zal uitgevoerd worden, maar het is wel zeker dat er nooit een herhaalde uitvoering zal zijn. 3. Het eenvoudigste is helemaal niks te garanderen, en het aan de implementatie van de serverkernel over te laten hoe er gehandeld wordt bij het terug opstarten na een crash. Deze politiek laat de client in het ongewisse, maar vermindert wel de vereisten voor de server. Het is gemakkelijk in te zien dat een exactly-once semantiek niet te realiseren valt. De mogelijkheid van het gedeeltelijk uitvallen van een computersysteem is inherent verbonden met distributie. • Uitgevallen client Het uitvallen van een client veroorzaakt onvoorziene problemen aan de serverkant. Er ontstaan immers processen die lopen in opdracht van een client die niet meer bestaat. We noemen deze wezen. Deze processen gebruiken resources, blokkeren databank-records, cre¨eren andere processen waarvan de resultaten nooit opgevraagd zullen worden. Bij het verzenden van het antwoord komen ze in een slapende toestand waarbij ze, afhankelijk van de strategie, een zekere tijd blijven wachten tot de client ontvangst van het antwoord bevestigt. Bovendien kan een client die terug opstart, en een nieuwe RPC lanceert, in verwarring komen door ontvangst van het antwoord van een wees. Er vestaan 4 mogelijke oplossingen, maar geen van deze is werkelijk bevredigend. 1. Men kan een logboek bijhouden van elke RPC. Bij het terug opstarten worden eerst en vooral alle wezen gedood. Deze methode noemt men uitroeiing. Het logboek vormt het grootste nadeel aangezien het een bijkomende overhead veroorzaakt voor de implementatie van RPC. Verder is het onduidelijk dat alle wezen kunnen worden gedood, indien het netwerk door falende infrastructuur, niet meer samenhangend is. 2. Men kan het begrip tijdperk invoeren. Een opstartende client zend een boodschap rond die het begin van een nieuw tijdperk aankondigt. Alle lopende RPC processen worden be¨eindigd bij het begin van een dergelijk nieuw tijdperk. Als er toch processen blijven lopen, omdat het netwerk niet samenhangend meer is, worden ze gedetecteerd bij het binnenkomen van het antwoord, en genegeerd. Deze methode noemt men re¨ıncarnatie. 3. Men kan het be¨eindigen van processen beperken tot deze waarvoor geen eigenaar meer kan worden gelokaliseerd. Dit noemt men zachte re¨ıncarnatie. 4. Tenslotte kan men met tijdsquanta werken. De RPC moet na het verstrijken van een tijd T een nieuw quantum vragen. Als hij dit niet krijgt stopt hij. Na een crash wacht 29

een kernel een tijd langer dan T alvorens terug op te starten. Op dat ogenblik zijn alle wezen uitgestorven. Men noemt dit expiratie. Het aanvragen van een nieuw quantum veroorzaakt overhead, en de wachttijd voor het opstarten veroorzaakt dode tijd. Het probleem is het vinden van een goed quantum T . Dit probleem is eigenlijk niet goed te behandelen. Het stoppen van processen is steeds problematisch. Er kunnen bijvoorbeeld databanksloten toegekend zijn aan een proces. Deze moeten worden opgezocht om te verkomen dat andere processen lange wachttijden oplopen. Problemen RPC is bij de meeste constructeurs beschikbaar en blijkt een praktische oplossing voor een gedistribueerd systeem te vormen. Er zijn evenwel een antal problemen. • Globale variabelen Het klassieke voorbeeld is errno , een UNIX variabele die de laatst opgetreden fout bevat. Functies noteren bij een fout, hierin wat er misging, en de oproepende omgeving kan errno lezen en gepast reageren. Het is duidelijk dat dit bij een parallelle remote uitvoering geen zin heeft. Het probleem is dat historisch, de ontwerpers UNIX niet met RPC rekening hielden, maar dat ondertussen wel veel UNIX systemen RPC ondersteunen. • Variabelen Sommige programmeertalen, zoals C-taal, gebruiken onvolledige specificaties voor de types van de variabelen. De grootte van een tabel wordt in een C-functie prototype meestal niet gespecifieerd. Bij het schrijven van een interface voor een RPC server moet dit nochthans wel gebeuren. Zoniet kan de client stub niet weten welke gegevens doorgegeven moeten worden. Hetzelfde kan gezegd worden van pointer-gebaseerde datastructuren. • De gebruikersinterface De UNIX/LINUX scripting talen gebruiken pijplijnen en redirectiesymbolen om programma’s met mekaar te verbinden. Het fundamentele idee is dat de output van ´e´en proces als input van een ander kan dienen. Een proces hoeft meestal niet te weten of de invoer uit een bestand komt, of door een ander proces geproduceerd wordt. Synchronisatie gebeurt in de pijplijn die door de scripting omgeving gecreeerd wordt. Dit principe kan niet veralgemeend worden naar gedistribueerde processen. Beschouw bijvoorbeeld een file-server waarop drie processen een lees-schrijf-operatie willen uitvoeren door p1 < f1 | p2 | p3 > f2 De processen p1, p2 en p3 lopen alle op verschillende machines. De file-server kan beschouwd worden als een vierde machine. Wie is in deze rij afhankelijk van wie, of, wie is client van welke server? Een eerste benadering is te beginnen bij p1. Proces p1 is client van de file-server om het bestand f1 te lezen. Proces p2 is dan client van p1 om zijn output te krijgen. Proces p3 is client van p2. En tenslotte moet de file-server client zijn van p3. Dit is in tegenspraak met de definitie van de server. Deze kan niet fungeren als client. Een tweede benadering begint bij p3. Proces p3 is client van de file-server om zijn output in het bestand f2 te schrijven. Proces p2 is client van p3 om zijn output op te vangen. Proces p1 is client van p1. En de file-server moet opnieuw als client optreden voor p1, het bestand f1 moet als het ware de pijplijn op gang brengen. Deze benadering past dus ook niet in het client/server model. 30

Het oude model van de scripting talen die in UNIX ontwikkeld werden en die veelvuldig gebruikt worden in allerlei toepassingen, is dus niet compatibel met de client/server benadering. RPC is op dit model gebaseerd en heeft dus deze beperkingen in zich. Voor een specifieke toepassing is het meestal mogelijk ad-hoc oplossingen te bedenken. Zo kunnen de pipes als tijdelijke bestanden ge¨ımplementeerd worden. Dit veroorzaakt overhead waardoor gebruikers het gebruik van de scripting taal in vraag moeten stellen.

1.6

Synchronisatie in gedistribueerde systemen

Communicatie is een basis voor het samenwerken van processen. Om tot een geco¨ordineerde groep processen is synchronisatie een tweede voorwaarde. Inbegrepen is het gebruik van kritieke secties en het toewijzen van resources. In gecentraliseerde systemen met ´e´en gemeenschappelijk geheugen wederzijdse uitsluiting gerealiseerd worden via datastructuren in het geheugen. Semaforen en monitoren zijn modellen die goed werken in een gemeenschappelijk geheugen. Het probleem is ingewikkelder als hiervan niet mag uitgegaan worden. Een tweede probleem is gelijktijdigheid. In een centraal systeem is er een gemeenschappelijke klok aanwezig die toelaat om uit te maken in welke volgorde de gebeurtenissen zich voordoen. We zullen zien dat een dergelijke gemeenschappelijke klok niet bestaat in een gedistribueerd systeem. Voor we deze punten in detail bespreken vatten we de kenmerken van een gedistribueerd systeem samen. 1. De relevante informatie is verspreid (g´e´en gemeenschappelijk geheugen). 2. Processen baseren hun beslissingen enkel op informatie die lokaal beschikbaar is. 3. Er moet worden voorkomen dat het hele systeem uitvalt als ´e´en component uitvalt. 4. Er bestaat geen gemeenschappelijke klok of een precieze globale tijd. De eerste drie eigenschappen herkennen we. Ze drukken uit dat er geen centrale componenten aanvaard kunnen worden. Dit heeft onder andere te maken met vereisten als schaalbaarheid en robuustheid. De vierde eigenschap is het gevolg van een theoretische discussie. Ze drukt uit dat een absolute tijd een centraal concept is.

1.6.1

Klokken

Veel mechanismen die in een centraal systeem werden ontwikkeld gaan uit van een exacte tijdsregeling. In eens systeem met ´e´en centrale verwerkingseenheid is er ook een centrale klok. Deze wordt door de kernel van het besturingssysteem bediend en kan op elk ogenblik de exacte tijd geven. Een voorbeeld van een programma dat deze tijd gebruikt is make.Het beschikt over een structuurbeschrijving van een toepassing in termen van afhankelijkheidsrelaties tussen bestanden. Indien een bestand A afhangt van een bestand B, en de datum van laatste wijziging voor B is later dan deze voor A, dan besluit make dat A opnieuw moet gegenereerd worden. Make kan gebruik maken van een absolute tijd. Indien deze evenwel niet betrouwbaar is kan het volgende scenario zich voordoen: • Bestand A wordt in twee verschillende takken van de make boom vermeld. • Bestand A wordt in ´e´en tak gegenereerd met datumstempel 2124. • Tegelijkertijd wordt bestand B in de andere tak gewijzigd door een preprocessor en krijgt datumstempel 2123 van laatste wijziging. 31

• Aangezien B een vroegere datumstempel heeft dan A wordt A niet opnieuw gegenereerd, hoewel A van B afhankelijk is. Dit kan zich voordoen als de twee takken op verschillende machines worden uitgevoerd. De klokken op de twee machines zijn niet volledig gesynchroniseerd. We merken hier op dat dit mislukt omdat de volgorde van de gebeurtenissen niet correct is weergegeven in de datumstempels. Het volgende scenario loopt wel goed af: • Bestand A wordt in ´e´en tak gegenereed met datumstempel 2124. • Tegelijkertijd wordt bestand B in de andere tak gewijzigd door de preprocessor en krijgt datumstempel 3221. • Aangezien B een latere datumstempel heeft dan A wordt A opnieuw gegenereerd. Hoewel de klokken in de twee takkend dus niet juist lopen, ontstaat er hier geen probleem omdat de volgorde van de gebeurtenissen correct is weergegeven in de datumstempels (A is van vroegere datum dan B). Dit inspireerde Leslie Lamport tot het defini¨eren van logische klokken. Logische klokken De timer van een computer draagt de naam klok, maar dient eigenlijk niet om de tijd bij te houden. De voornaamste functie van deze schakeling is het bepalen van het tempo waaraan de instructies worden uitgevoerd. De systeemklokken die zich in de kernels van de besturingssystemen bevinden gebruiken deze timers om een benaderde tijd bij te houden. Hardwarematig bestaat een dergelijke timer uit een kristal en twee registers: het bewaarregister en het telregister. Het kristal trilt onder spanning met een exacte frequentie. De duur van een oscillatie is konstant met een vrij grote nauwkeurigheid. Na elke oscillatie wordt het telregister met 1 verminderd tot het nul wordt. Op dat ogenblik wordt een interrupt gegenereerd en wordt het telregister op de waarde in het bewaarregister gezet. En dan begint de cyclus opnieuw. De interrupt noemen we een kloktik. De kleine fout op de oscillatietijd zorgt ervoor dat geen twee klokken exact gelijk lopen. Deze fout is cummulatief. Ze genereert een zogenaamde tijdongelijkheid tussen de verschillende computers in een netwerk. Deze tijdongelijkheid kan problemen genereren voor het correct functioneren van programma’s als make.Indien ge¨eist wordt dat de tijdongelijkheid binnen bepaalde grenzen blijft spreken we van fysieke klokken.Synchronisatie van fysieke klokken wordt in een volgende paragraaf besproken. Voor veel toepassingen is de absolute tijd niet belangrijk. Meestal maken ze wel gebruik van een kennis van de volgorde van de gebeurtenissen. Dit is alleen dan van belang als er sprake is van interactie. Voor twee, niet interagerende processen is het niet nodig dat de volgorde waarin de gebeurtenissen zich voordoen bekend of gevolgd is. Klokken die toelaten om de volgorde van gerelateerde gebeurtenissen te bepalen noemen we logische klokken.We bespreken hier de algoritme van Lamport voor de synchronisatie van logische klokken. Gegeven zijn twee gebeurtenissen a en b. We zeggen dat a voor b komt, genoteerd a → b, indien 1. De gebeurtenissen a en b zich in hetzelfde proces voordoen en a in de tijd voor b optreedt. 2. a de gebeurtenis is waarbij een proces een bericht verstuurt en b de gebeurtenis waarbij een proces ditzelfde bericht ontvang. 32

3. er een keten gebeurtenissen e1 , e2 . . . en bestaat zodat a → e1 → e2 → . . . → en → b. Dit is een transitieve relatie. De orde die erdoor gedefinieerd wordt is niet volledig. Indien twee gebeurtenissen x en y niet binnen hetzelfde proces gebeuren, en de processen waartoe ze behoren geen berichten uitzenden, dan geldt noch x → y noch y → x. We zeggen dat x en y concurrente gebeurtenissen zijn. Het blijkt mogelijk te zijn om een tijdwaarde te defini¨eren die consistent is met bovenstaande definitie. We zoeken hiervoor een numerieke functie C die werkt op gebeurtenissen zodanig dat als voor twee gebeurtenissen a en b geldt dat a → b ⇒ C(a) < C(b)

(1.10)

Het algoritme van Lamport laat toe om deze functie in een gedistribueerd systeem te berekenen. Hij is er dus in geslaagd een gedistribueerde logische klok te defini¨eren die op elk punt in het gedistribueerde systeem kan gebruikt worden om de volgorde van gebeurtenissen te bepalen. Neem de drie processen 0

0

0

0

5

0

6

10

5

6

10

10

12

20

10

12

20

15

18

30

15

18

30

20

24

40

20

24

40

25

30

50

25

30

50

30

36

60

30

36

60 70

0

35

42

70

35

42

40

48

80

40

48

80

45

54

90

45

54

90

50

60

100

50

60

100

55

66

110

55

66

110

60

72

120

60

101

120

65

78

130

65

107

130

70

84

140

70

113

140

75

90

150

108

119

150

Figuur 1.21: De definitie van de Lamport klok in figuur 1.21. De klokken in de processen vertonen een systematisch verschil. Bij het zenden van een proces met een tragere klok naar een proces met een snellere klok is er geen probleem. Het ogenblik van aankomst is later dan het ogenblik van verzending. Het zendende proces voegt zijn tijdsstempel toe aan de boodschap. Het ontvangende proces controleert of zijn tijd later is dan de tijdsstempel in de boodschap. Bij het zenden in de omgekeerde richting ontstaat er wel een probleem. Het ontvangende proces stelt vast dat de tijdsstempel van verzending een later tijdsstip aangeeft dan het ogenblik van ontvangst. Op dit ogenblik voldoet zijn tijdsfunctie niet meer aan voorwaarde 1.10. Gezien deze tijdsfunctie enkel een logische betekenis heeft, en de ontvangst voorlopig de laatste gebeurtenis binnen het proces voorstelt, kan het zijn tijdsfunctie aanpassen. De aanpassing kan bovendien zodanig uitgevoerd worden dat tussen twee opeenvolgende gebeurtenissen minstens ´e´en kloktik tijdsverschil zit (zie figuur 1.21). Met deze methode hebben we een tijdsfunctie die aan het axioma 1.10 voldoet. Het 33

is nu nog mogelijk dat twee gebeurtenissen exact dezelfde tijd hebben (construeer zelf een voorbeeld). Om ook dit te voorkomen kunnen we bijvoorbeeld het procesidentificatienummer als fractioneel deel bij de tijdsfunctie optellen. Alle gebeurtenissen a binnen proces 1234 hebben dan een tijd van de vorm C(a) = x.1234 en verschillen dus van alle gebeurtenissen binnen een ander proces op voorwaarde dat de proces identificatie uniek is. We hebben nu een totale ordening van de gebeurtenissen in het systeem die de causale ordening van met mekaar verbonden gebeurtenissen (dit zijn gebeurtenissen binnen hetzelfde proces of zend- en ontvangstgebeurtenissen van eenzelfde bericht) bewaart. Veel toepassingen hebben precies een dergelijke ordening nodig. (Oefening: Wat is de betekenis van de ordening voor gebeurtenissen die niet met mekaar verbonden zijn?)

1.6.2

Fysieke klokken

Er zijn situaties waar de klok van Lamport niet voldoet. Deze treden op in toepassingen waar de werkelijke tijd van belang is. Real − time toepassingen dragen dit begrip in hun naam. In deze toepassingen zijn de onderdelen gebonden aan minimale responstijden. We kunnen dan geen logische klok gebruiken aangezien de responstijden verbonden zijn met noodsituaties of specifieke vereisten van processen en toestellen die chemische of fysische wetmatigheden volgen. We hebben in dergelijke situaties nood aan klokken die gesynchroniseerd zijn binnen wel bekende marges. Er zijn tegenwoordig veel bronnen van werkelijke tijd beschikbaar. In specifieke toepassing moeten algoritmen ervoor zorgen dat de kloktijden binnen aanvaardbare marges synchroon zijn. Algoritmen voor kloksynchronisatie Kloksynchronisatie is in een gedistribueerd systeem nodig omdat klokken niet exact gelijk lopen. Als we door de functie C(t) de kloktijd voorstellen, dan zou in een ideaal systeem C(t) = t op alle ogenblikken t in het tijdsinterval waarbinnen de toepassing gebruikt wordt. In dit geval hebben we dus dC = 1 op alle ogenblikken t. Dit ideale geval doet zich in de praktijk helaas niet voor. In dt constant is. Dit komt overeen met een systeem een eerste benadering kunnen we wel zeggen dat dC dt waarin de klok aan een constant ritme tikt dat hoger ligt dan het ritme van de erkende klokken. In deze veronderstelling bestaat er een constante afwijking ρ zodat 1 − rho <

dC < 1 + ρ. dt

(1.11)

Dit is uiteraard in de praktijk nog steeds niet het geval. Wat men wel kent is een maximale waarde voor ρ. Dit leidt tot figuur 1.22. In figuur 1.22 is te zien dat na een tijd ∆t de maximale afwijking tussen twee klokken opgelopen is tot 2ρ∆t. Indien het maximale verschil tussen twee klokken in δ het systeem delta bedraagt, moet er een synchronisatie plaatsvinden om de ∆t = 2ρ seconden. We bespreken volgende algoritmen ter illustratie. 1. De algoritme van Cristian In dit algoritme wordt een centrale tijdserver verondersteld. Als een proces vaststelt dat het volgende synchronisatie-ogenblik gekomen is vraagt het de tijdserver om de tijd. Het antwoord van de tijdserver bevat de tijd op het ogenblik van verzending. De client moet een correctie toepassen voor de vertraging in het netwerk. De situatie is in figuur 1.23 weergegeven. 0) de beste schatting Als er geen informatie is over de responstijd I van de tijdserver, dan is (T1 −T 2 voor de correctie die bij de tijdsstempel in het antwoord moet gevoegd worden om de juiste tijd bij ontvangst te bekomen. Als men weet wat de waarde van I is kan een nauwkeuriger

34

C(t)

2rDt 1+r 1 1−r

1

Dt

t

Figuur 1.22: De maximale afwijking tussen twee klokken neemt lineair toe met de tijd

schatting bekomen worden als (T1 −T2 0 −I) . Hierbij is verondersteld dat de transporttijd voor vraag en antwoord gelijk zijn. Onregelmatigheden in het netwerkverkeer of in de netwerkconfiguratie kunnen deze tijden be¨ınvloeden. Om de precisie te vergroten kan men meerdere metingen doen. Anomaal grote tijdsverschillen worden waarschijnlijk veroorzaakt door uitzonderlijke situaties in het netwerk. Deze hebben een grotere kans op asymetrie, en worden weggelaten bij het berekenen van de gemiddelde tijd. Het is zelfs niet onredelijk om het bericht dat het snelst terugkomt als beste schatting te aanvaarden. Merk tenslotte op dat het gebruik van T1 − T0 geen grote fouten zal introduceren aangezien het verschil tussen de twee de tijd meet over een voldoende klein interval. 2. De algoritme van Berkeley De tijdserver in het algoritme van Cristian is passief. Deze methode kan worden gebruikt waar er een gepriviligeerde tijdserver is. Dit zal meestal samenvallen in een nood binnen de toepassing aan een exacte meting van de tijd. Indien een dergelijke server niet aanwezig is, kan de volgende methode gebruikt worden. Ze werd ontwikkeld binnen Berkeley UNIX. In dit besturingsysteem is het de voornaamste zorg de klokken binnen bepaalde grenzen gelijk te laten lopen. Dit gaat als volgt. Een gespecialiseerd proces (de tijddemon in de typische UNIX naamgeving) vraagt elke machine periodiek wat de tijd daar is. Op grond van de antwoorden berekent de demon een gemiddelde tijd. De andere machines krijgen dan de opdracht hun klok aan te passen. Ze zullen dit geleidelijk doen: een klok die achterloopt zal gedurende een zekere tijd sneller gaan lopen tot de achterstand ingehaald is, een klok die voorloopt gaat een zekere tijd trager tikken tot voorsprong is.

35

T0 Aanvraag

I

Tijd bij verzending T1 Figuur 1.23: De schatting voor de correctie op tijd in de boodschap is

(T1 −T0 −I) 2

3. Middelende algoritmen Voorgaande methodes gebruiken een centrale server. Een gedistribueerde methode werkt bijvoorbeld als volgt. De tijd wordt verdeeld in resynchronisatie-intervallen. Er wordt een intervallengte R afgesproken. Als, volgens de lokale klok, een interval verstreken is, zendt het proces een broadcast boodschap met zijn eigen tijd. Vervolgens gaat het een vastgestelde tijd S wachten op broadcasts met tijden van andere stations. Op basis van de ontvangen tijden wordt een nieuwe, gemiddelde, tijd berekent voor het lokale station.

1.6.3

Wederzijdse uitsluiting

Wederzijdse uitsluiting heeft te maken met de afscherming van kritieke secties. Dit zijn deze delen van programma’s die resources delen. Meestal mag slechts ´e´en proces tegelijk de kritieke sectie geassocieerd aan een bepaalde resource binnengaan. In systemen met ´e´en verwerkings eenheid en gedeeld geheugen wordt wederzijdse uitsluiting geregeld door de implementatie van semaforen of equivalente constructies. Deze zijn dan gebaseerd op de behandeling van interrupts binnen de processor, of op specifieke instructies die met het geheugen kunnen werken. Beide hulpmiddelen vallen weg zodra er meerdere verwerkingseenheden actief zijn of als er geen gedeeld geheugen meer is. We hebben dus nood aan alternatieve constructies. In de volgende paragrafen bestuderen we een paar mogelijkheden. Een gecentraliseerd algoritme We gaan uit van het bestaan van een centrale server voor wederzijdse uitsluiting. Dit proces noemen we de co¨ordinator. Per kritieke sectie dient een co¨ordinator aangeduid te worden, die eventueel wel meerder kritieke secties kan co¨ordineren (zie figuur 1.24. Een proces A dat een kritieke sectie binnen wil vraagt de co¨ordinator om toestemming. Deze controleert of er een proces in de gevraagde sectie is. Als het niet zo is zendt de co¨ordinator een “OK”en kan A binnen gaan. Indien er een proces in de sectie is, dan voegt hij proces A achteraan toe aan zijn lijst van processen die de sectie binnen willen. Als een proces de kritieke sectie verlaat, brengt het de co¨ordinator daarvan op de hoogte. Deze zendt dan een “OK” naar proces X vooraan in de lijst en verwijdert X. Deze methode voldoet aan de voorwaarden van wederzijdse uitsluiting: 36

A

C

B IN?

A

C

B

OK

IN?

M

Wachtrij Toegang tot een vrije sectie

C

B UIT

C

M

A

OK M

Wachtrij De sectie is niet vrij, geen antwoord

Wachtrij De sectie komt vrij, toegang toegestaan

Figuur 1.24: Een centrale oplossing voor wederzijdse uitsluiting

• Er kan slects ´e´en proces tegelijk in de kritieke sectie zijn. Dit is eenvoudig in te zien daar de co¨ordinator wacht tot er een signaal komt dat de sectie vrij is. • Processen worden niet tegengehouden door andere processen die zich in een niet-kritieke sectie bevinden. • De wachtrij is zo eerlijk als een Engelse “queue”, geen enkel proces zal voor onbepaalde tijd moeten wachten. Ze is evenwel veel fragieler dan de oplossing met semaforen die we in een centraal systeem ter beschikking hebben. • De centrale rol van de co¨ordinator betekent dat het hele systeem afhangt van de stabiliteit van dit proces. Als de co¨ordinator uitvalt krijgt geen enkel proces nog toelating om de kritieke sectie te betreden. Een proces dat een aanvraag lanceert kan zelfs niet uitmaken of de co¨ordinator nog werkt. De normale strategie is immers te wachten tot er een “OK” komt. • Een centrale co¨ordinator kan overbelast worden. Indien men de controle van kritieke secties concentreert op ´e´en extra stabiele machine, dan kan deze machine in een groot systeem een bottleneck worden. Tegen het uitvallen van een centrale component kan men verkiezingsalgoritmen aanwenden (zie paragraaf 1.6.4). Om de vragende processen op de hoogte te brengen van het al dan niet functioneren van de co¨ordinator kan men een bevestiging terugsturen, ook indien er geen toestemming tot binnengaan gegeven wordt. De overbelasting van de centrale component betekent een risico voor de schaalbaarheid. Laat ons een gedistribueerde versie bekijken. Een gedecentraliseerde algoritme In deze algoritme uit 1981 wordt verondersteld dat de gebeurtenissen ondubbelzinnig geordend zijn. De Lamport klok van paragraaf 1.6.1 zorgt voor een dergelijke strikte ordening. Wanneer een proces een kritieke sectie wil binnen gaan, zendt het een bericht met zijn procesnummer, zijn kloktijd, en de naam van de kritieke sectie. Het zendt dit proces aan alle andere processen. Het ontvangt van 37

alle ontvangende processen een bevestiging. De actie van een ontvangend proces hangt nadien af van zijn eigen toestand: 1. Als de ontvanger zich in een niet kritieke sectie van zijn programma bevindt, zendt hij “OK” terug. 2. Als de ontvanger in de kritieke sectie is geeft hij geen antwoord. Hij plaatst de aanvraag in een wachtrij. 3. Als de ontvanger de kritieke sectie wil binnengaan en reeds een verzoek heeft rondgestuurd, vergelijkt hij de tijd in het bericht met de tijd in zijn eigen verzoek. Als deze tijd lager is, dan zindt hij een “OK” terug. Als hij zelf een lagere tijd had (hij verzond zijn verzoek dus “vroeger”) dan plaatst hij de binnenkomende aanvraag in een wachtrij en zendt niets. De zender van een verzoek wacht tot alle gevraagde processen hun toestemming hebben verleend. Pas dan mag het de kritieke sectie binnengaan. Bij het verlaten van deze sectie zendt het een “OK” aan alle processen in zijn wachtrij en maakt die leeg. Dit algoritme voldoet aan de voorwaarden voor wederzijdse uitsluiting: • Een proces dat in een niet kritiek deel van zijn programma aan het werk is zendt onmiddellijk “OK”, wat equivalent is met “ik meng me niet in deze discussie”. • Als er een proces in de kritieke sectie is, zendt het geen “OK”, en de kandidaat krijgt een “OK” te weinig. Hij zal dus zijn sectie niet binnengaan, en er kunnen dus nooit twee processen tegelijk in de kritieke sectie komen. • Een proces A dat van een ander proces geen “OK” krijgt komt in de wachtrij van dit proces. Op voorwaarde dat al deze processen ooit hun kritieke sectie be¨eindigen zal proces A ooit van alle processen een “OK” krijgen, en het zal niet gedoemd zijn tot eeuwig wachten. Merk op dat deze processen in de wachtrij moeten gekomen zijn v´oo´r ze de boodschap van A ontvangen en bevestigen. Indien ze later aankomen, hebben ze op dat ogenblik een latere tijd en zullen A moeten laten voorgaan door het een “OK” te zenden. Bij betrouwbare communicatie is het aantal dergelijke processen eindig. Ze zijn bovendien exact geordend, ´e´en van hen staat vooraan in de rij en wacht enkel op toestemming van het proces in de kritieke sectie. De volgende wacht op twee toestemmingen enz. Deze processen komen dus in een eindige tijd door de kritieke sectie, en A mag dus zeker ooit binnen. Hoewel deze algoritme voldoet aan de voorwaarden vertoont het dezelfde nadelen als de centrale oplossing. Een proces wacht op toestemming van alle processen. Dit betekent dat alle processen actief moeten blijven. Het uitvallen van ´e´en proces blokkeert het hele systeem. De verplichting tot bevestiging is opnieuw een oplossing: een proces dat niet bevestigt kan als dood worden beschouwd. Alle processen houden nu wachtrijen bij en zijn potenti¨ele bottlenecks. Er zijn een aantal verbeteringen mogelijk, die we hier niet bespreken. Hoewel deze nadelen de algoritme niet aantrekkelijk maken, toont het aan dat het mogelijk is een gedistribueerde algoritme te construeren waarvan de werking ondubbelzinnig kan worden aangetoond. Een token ring algoritme Een andere, gedistribueerde oplossing bestaat in het softwarematig construeren van een zogenaamde token ring.De processen worden geordend. Als er n processen zijn, dan krijgt elk proces een nummer 38

in [0, n − 1]. Elk proces k heeft twee naburen, namelijk (k − 1)modulon en (k + 1)modulon. Een proces kan slechts de kritieke sectie binnen als het het zogenaamde “token” heeft. Dit is een object dat wordt doorgegeven van nabuur tot nabuur. Een proces dat het token ontvangt gaat ofwel de kritieke sectie binnen of het geeft het token door. Een proces dat de kritieke sectie verlaat geeft de token door. Het proces voldoet duidelijk aan alle voorwaarden van wederzijdse uitsluiting. (verifieer!) Praktisch kunnen moeten een aantal problemen opgelost worden. Als de token verloren gaat moet het opnieuw worden gegenereerd. Detectie van een verloren token is niet gemakkelijk. Processen zouden bijvoorbeeld de tijd kunnen meten dat het token nodig heeft om rond te gaan. Als deze tijd abnormaal lang wordt zouden ze kunnen beslissen om een nieuw token te genereren. Alleen kan deze abnormaal lange tijd ook veroorzaakt worden door abnormaal intensief verkeer in de kritieke sectie. Bevestiging van ontvangst is een methode om een dood proces te detecteren. De ring moet dan opnieuw geconfigureerd worden, of het proces dat de detectie doet moet zijn nieuwe nabuur zoeken. Dit betekent dat de configuratie van de software ring door alle processen moet gekend zijn. Deze problemen zijn analoog aan de problemen die in netwerken optreden, en de daar geldende oplossingen kunnen hier ook gebruikt worden. Zo kan een nieuw proces er bijvoorbeeld voor zorgen dat de ring defect geraakt en een hernieuwing van de ring eisen. Besluit Onderstaande tabel laat toe de karakteristieken van de drie algoritmen te vergelijken. Het aantal berichten per toegang tot de kritieke sectie geeft een maat voor de overhead. Voor het gecentraliseerde systeem zendt men een vraag, ontvangt men een bevestiging en een “OK”. Het decentrale systeem vereist een vraag en een “OK” per proces dat in aanmerking komt. De token ring vereist ´e´en bericht per toegang indien elk proces het token telkens gebruikt om binnen te gaan, en ∞ berichten per toegang indien er geen toegangen zijn. De tijd tot het binnengaan is gemeten in berichttijden. Deze is bepalend voor de wachttijd indien het netwerk traag is ten opzichte van de verwerkingseenheden (zie tabel 1.1). Deze algoritmen zijn alle zeer gevoelig aan storingen door het uitvallen van processen. Algoritme Centraal Decentraal Token ring

Berichten per toegang Tijd tot binnengaan 3 2 2(n − 1) 2(n − 1) 1 tot ∞ 0 tot n − 1

Problemen uitval van de co¨ordinator uitval van een proces tokenverlies, procesuitval

Tabel 1.1: Vergelijking van de drie algoritmen Om dit op te vangen moeten er vaak uitgebreide voorzorgsmaatregelen getroffen worden. Het is merkwaardig dat een gedistribueerd systeem minder robuust blijkt te zijn dan een gecentraliseerd systeem. Als men ervan kan uitgaan dat de processen niet uitvallen zijn de drie methodes bruikbaar.

1.6.4

Verkiezingsalgoritmen

Vaak heeft een gedistribueerd systeem nood aan een co¨ordinerend proces. Dit vervult een centrale rol in de werkorganisatie voor de processen. De nadelen verbonden aan een centrale component komen hier dan ook tot uiting. Aan ´e´en van die nadelen proberen verkiezingsalgoritmen iets te doen: de gevoeligheid voor het uitvallen van de co¨ordinator. Indien de co¨ordinator verdwijnt kan

39

een verkiezingsalgoritme toelaten dat de processen een nieuwe co¨ordinator kiezen. We bekijken een paar dergelijke algoritmen. Het recht van de sterkste De Engelse naam voor dit algoritme is “bully-algorithm”, omdat het een proces laat winnen op basis van een verder niet terzake doende eigenschap. Het algoritme wordt gestart als een proces merkt dat een co¨ordinator niet meer op aanvragen reageert. Een proces A gaat dan als volgt tewerk: 1. A zendt een bericht “VERKIEZING” naar alle processen met een hoger nummer. 2. Als niemand op dit bericht reageert, wint A de verkiezing. 3. Als ´e´en van de hogere processen antwoord geeft neemt dit de verdere verkiezing op zich. Bij het ontvangen van een bericht “VERKIEZING” wordt een antwoord “OK” teruggezonden. De ontvanger houdt dan een verkiezing, tenzij hij er al ´e´en lopen heeft. Een proces dat geen antwoord meer ontvangt veronderstelt dat het het grootste procesnummer heeft van de nog lopende processen en wint de verkiezingen. Het zendt de boodschap “COORDINATOR” met zijn procesnummer naar alle processen. Als later een proces met een hoger nummer opgestart wordt merkt het dit bij zijn zoektocht naar de coordinator. Het neemt dan deze job over door zelf een bericht “COORDINATOR” te sturen. Een ring De processen worden in een logische ring geplaatst. Elk proces heeft ´e´en opvolger en ´e´en voorganger. Wanneer een proces vaststelt dat de co¨ordinator niet meer functioneert, zendt het een bericht “VERKIEZING” naar zijn opvolger. Als de opvolger niet meer loopt, wordt het naar de opvolger van de opvolger gestuurd; de processen kennen weer alle het volledige netwerk. Het bericht heeft tot doel om een lijst van lopende processen op te bouwen. De lijst reist mee. Aanvankelijk bevat ze enkel het procesnummer van de initiatiefnemer. Bij ontvangst van het bericht voegt een proces zijn nummer aan de lijst toe en zendt het door naar zijn opvolger. Als de initiatiefnemer uiteindelijk het bericht ontvangt stelt hij vast dat hij reeds in de lijst staat. Hij veranderd de inhoud van de boodschap in “COORDINATOR”, wat betekent dat het proces met het hoogste nummer in de lijst aangeduid wordt. Deze boodschap gaat nog eens helemaal rond tot iedereen weet wie de nieuwe co¨ordinator is. De figuur 1.25 laat zien wat er gebeurt als twee processen tegelijkertijd merken dat de co¨ordinator deficient is. Beide starten een verkiezingsalgoritme, maar beide komen tot dezelfde conclusie. Oefening Laat zien dat het bully-algorithme eveneens werkt als meerdere processen tegelijkertijd een verkiezing starten.

1.6.5

Atomaire transacties

Zoals vroeger gezien zijn semaforen van een te laag niveau voor een goede programmeeromgeving. De programmeur moet zich om teveel details van de parallelle omgeving bekommeren. Dit geldt ook voor de methodes die we in deze paragraaf besproken. We hebben abstracte benaderingen nodig die 40

1

5

2

2

0 3

6

2 9 9

5

3

6

4

8 6

5 5

Figuur 1.25: Een ringalgoritme voor de verkiezing aan het werk, 2 en 5 hebben de uitval vastgesteld

het gedistribueerd werken voor de programmeur onzichtbaar maakt. Met betrekking tot wederzijdse uitsluiting bespreken we hier het concept van een atomaire transactie. Inleiding Conceptueel is een atomaire transactie een geheel van handelingen die volledig of helemaal niet uitgevoerd worden. Als twee bedrijven een aandelentransactie bespreken en uitvoeren, dan kunnen de besprekingen lange tijd in beslag nemen, en op elk ogenblik afgebroken worden. Indien de besprekingen afspringen is het alsof er niks is gebeurd. Daarenteden, als op een bepaald ogenblik besloten wordt de overeenkomst uit te voeren, is er geen weg meer terug. Dit is een bruikbaar concept in een gedistribueerd systeem. Als een proces een aantal gegevens wil wijzigen terwijl het een bepaald deel van zijn programma uitvoert, dan kan het zijn dat tegelijkertijd een ander proces dezelfde gegevens gebruikt. Het is de bedoeling van een transactie dat de operaties op de gegevens teruggeschroefd kunnen worden op het ogenblik dat er een conflict aan het licht komt. In de vroege dagen van de administratieve gegevensverwerking was het niet mogelijk om databanken on-line bij te werken. In de plaats werd in de loop van de dag een bestand van wijzigingen aangelegd. Dit bestand werd ’s avonds verwerkt. Deze verwerking bestond erin dat op basis van de oude gegevensbank en een wijzigingsbestand een nieuwe bank werd gemaakt. Op elk ogenblik bestonden de oude gegevens en de wijzigingen. Indien er een technisch probleem optrad kon men terugspoelen en opnieuw beginnen. Dit model wordt vandaag nog gebruikt bij zeer foutgevoelige systemen met potentieel groot dataverkeer, bijvoorbeel online banking systemen.

41

Model Het model dat we hier beschrijven laat toe dat programmeurs een sequentieel beeld voor ogen houden, en geen rekening houden met alles wat gedistribueerd werken met gedeelde resources met zich mee brengt. Dit zijn zowel de conflicten tussen processen over gemeenschappelijke resources als foutsituaties in de communicatie. • Stabiel geheugen De methodes die we bespreken gaan uit van het bestaan van stabiel geheugen. Dit is niet vluchtig geheugen waarvan de betrouwbaarheid veel hoger is dan de betrouwbaarheid van de courante gegevensdragers. In de praktijk kunnen hiervoor bijvoorbeeld RAID systemen gebruikt worden. • Operaties voor transacties De programmeur krijgt de volgende operaties aangeboden: 1. BEGIN TRANSACTION : De hierna volgende opdrachten maken deel uit van ´e´en transactie. 2. END TRANSACTION : Be¨eindig de transactie en probeer overeenstemming te bereiken. 3. ABORT TRANSACTION : Breek de transactie en herstel de oude waarden 4. READ : Lees data 5. WRITE : Schrijf data Naast READ en WRITE kunnen natuurlijk nog andere instructies ge¨ımplementeerd worden. Bijvoorbeeld het zenden en ontvangen van post of het ondervragen van een databank. Tabel 1.2 bevat voorbeeld, in pseudo-code, van een transactie. BEGIN TRANSACTION reserveer Gent-Keulen reserveer Keulen-M¨ unchen reserveer M¨ unchen-Salzburg END TRANSACTION

BEGIN TRANSACTION reserveer Gent-Keulen reserveer Keulen-M¨ unchen Keulen-M¨ unchen vol ⇒ ABORT TRANSACTION END TRANSACTION

Tabel 1.2: Een voorbeeld van twee conflicterende transacties. Deze algoritmen zijn alle zeer gevoelig aan storingen door het uitvallen van processen. • Eigenschappen van transacties Vanuit het standpunt van de programmeur hebben transacties volgende eigenschappen: 1. Serialiteit : concurrente transacties be¨ınvloeden mekaar niet. 2. Ondeelbaarheid : Voor de buitenwereld vindt de transactie als ondeelbare eenheid plaats. 3. Permanentie : Wanneer een transactie wordt bevestigd (de commit ) zijn de veranderingen permanent.

42

BEGIN TRANSACTION x=0 x=x+1 END TRANSACTION

BEGIN TRANSACTION x=0 x=x+2 END TRANSACTION

BEGIN TRANSACTION x=0 x=x+3

Tabel 1.3: Drie transacties, mogelijke uitkomsten bij seri¨ele uitvoering zijn x = 1, x = 2, x = 3. volgorde 1 volgorde 2 volgorde 3

x = 0; x = 0; x = 0;

x = x + 1; x=0 x=0

x=0 x = x + 1; x = x + 1;

x = x + 2; x = x + 2; x = 0;

x = 0; x = 0; x = x + 2;

x = x + 3; x = x + 3; x = x + 3;

legaal legaal illegaal

Tabel 1.4: Drie mogelijke volgordes, slechts twee zijn compatibel met een seri¨ele uitvoering.

De serialiteit bezorgt de programmeur het comfort waarover we in de inleiding spraken. Hij hoeft zich geen zorgen te maken over onderbrekingen, terugkomen na een onderbreking e.d. Om het implementatieprobleem beter te begrijpen bekijken we een klein voorbeeld dat illustreert wat serialiteit betekent. Beschouw de drie transacties in tabel 1.3. In de tweede tabel (1.4) worden drie scenario’s voorgesteld. De uitkomst is twee keer mogelijk, dit is het gevolg van een mogelijke volgorde van de atomaire transacties, en ´e´en keer niet mogelijk. De ondeelbaarheid van de transacties betekent dat geen enkel proces de resources in een tussenstadium kunnen zien. Als een transactie erin bestaat dat er 256 bytes bijgeschreven worden aan het eind van een bestand dat aanvankelijk 1 K bytes bevatte, dan zullen parallelle processen bij het lezen van dit bestand ofwel ontdekken dat het 1 Kbyte groot is, of 1,25 Kbyte. Een waarde tussenin is niet mogelijk. De permanentie van een transactie betekent dat de operatie niet omkeerbaar is na een commit . De commit is de laatste stap van een transactie waarna het proces dus zeker is van het realiseren van het welslagen van zijn operatie. • Geneste transacties Transacties kunnen subtransacties bevatten. Dit gebeurt als tijdens het uivoeren van een transactie een proces een verdere transactie nodig heeft. Deze geneste transacties noemen we kind-transacties. Deze kinderen kunnen zelf ook weer kind-transacties genereren. In dit geval wordt de betekenis van een commit problematischer. Als een kind-transactie slaagt betekent dit enkel dat de ouder-transactie verder kan gaan. Het kan nog steeds gebeuren dat deze ouder-transactie uiteindelijk niet lukt. In dat geval moet de semantiek van de oudertransactie gevolgd worden. Dit betekent dan onder andere dat de acties van het kind ook teniet moeten worden gedaan. Een commit op het niveau van een kind-transactie is dus steeds voorwaardelijk. Conceptueel kan men dit het best begrijpen door de resources waarop een transactie werkt, en hun toestand, als een eigen universum van de transactie te zien. Als ze afgebroken wordt hebben de acties van de transactie op de resources geen gevolg voor het grotere universum waarin ze werd opgestart. Dit geld ook voor de acties van de kind-processen die wel goed eindigen. Deze mogen geen invloed hebben op het grotere universum als de ouder-transactie afbreekt. 43

1

1

2

2

3

3

2

1

vóór

3

1

1b private ruimte

1

2

2

3

3

4b

4

2

3

2

3

1b

4b

1

4

tijdens

na

Figuur 1.26: De evolutie van de private ruimte tijdens een transactie.

Implementatie Om de ondeelbaarheid te realiseren kunnen processen in transacties geen gewone toegang tot de resources krijgen. De transacties zouden bovendien niet meer serieel zijn. We bespreken twee methodes van implementatie. • Private ruimte Bij de eerste methode wordt een private werkruimte gecre¨eerd. Elk proces heeft een eigen ruimte waarin zich de objecten bevinden die het manipuleert. Er zijn conceptueel evenveel kopies van een object als er transacties actief zijn die ermee werken. Bij het be¨eindigen van de transactie wordt gecontroleerd of er conflicten zijn opgetreden of niet (zie later). Als dit resulteert in een abort , wordt de private werkruimte gewoon verwijderd. Als er een commit komt, worden de bestanden in de private ruimte de nieuwe versies van de werkelijke bestanden (of de bestanden in de private ruimte van de ouder indien het om een kind-transactie gaat). Dit concept kan letterlijk ge¨ımplementeerd worden. Het kopi¨eren van alle bestanden induceert dan meestal een niet-aanvaardbare overhead. Er zijn een tweetal optimalisaties mogelijk die meestal ook gehanteerd worden. Een eerste optimalisatie bestaat erin de bestanden waaruit alleen gelezen wordt niet naar de private ruimte te kopi¨eren. Er hoeft enkel een pointer naar het werkelijke bestand of het bestand in de ruimte van de ouder te worden aangemaakt. De commit van deze transactie zal afhangen van een eventuele wijziging van dit bestand tijdens de transactie. Een tweede verbetering betreft de bestanden waar wel in geschreven wordt. We veronderstellen dat de bestandsopslag ge¨ındexeerd is. Het is niet nodig deze blokken te kopi¨eren die niet gewijzigd worden. Het is voldoende de index te dupliceren - bij een hi¨erarchische index zelfs slechts een gedeeltelijk - en een kopie te maken van elk blok dat gewijzigd wordt. De kopie¨en noemen we schaduwblokken. Zie figuur 1.26. • Intentielijsten 44

De tweede methode lijkt op het gebruik van aanpassingsbestanden in de oudere informatiesystemen. De bestanden worden werkelijk gewijzigd, maar enkel nadat de intentie tot wijziging is genoteerd in stabiel geheugen. Deze intentie bevat de identificatie van de transactie, van het bestand en het blok dat gewijzigd wordt, en verder de oude en de nieuwe waarde van het blok. Als de transactie uiteindelijk commit zal een commit record naar de intentielijst geschreven worden. Als de transactie wordt afgebroken wordt de intentielijst gebruikt om terug te keren naar de oorspronkelijke toestand. (rollback). Als bijkomend voordeel bevat de lijst een beveiliging tegen een crash. De toestand van juist voor de crash kan worden hersteld, of alle transacties kunnen teruggerold worden naar de toestand voor ze startten. • Tweefasen commit Een kritieke fase bij de implementatie van transacties is de commit.Hierbij kunnen meerdere processen op meerdere computers betrokken zijn. Het tweefasen commit protocol dat we hier bespreken maakt gebruik van stabiel geheugen om dit te realiseren. E´en van de processen is de co¨ordinator, meestal het proces dat de transacties startte. Bij het begin van een commit schrijft dit proces een record “voorbereiden”in de lijst op stabiel geheugen. Vervolgens zendt het een boodschap naar alle andere processen om zich voor te bereiden op een commit . Een proces schrijft bij ontvangst een record “klaar” in stabiel geheugen en zendt een bericht “klaar” terug. Als niet alle processen reageren, schrijft de co¨ordinator “abort” in stabiel geheugen, zendt deze boodschap aan alle processen en voert zelf een abort uit. Als alle processen gereageerd hebben met “klaar” schrijft de co¨ordinator dit in stabiel geheugen. Vanaf nu is de commit voltrokken, onafhankelijk van wat nog gebeurt. De co¨ordinator zendt alle betrokken processen een boodschap “commit”. Een proces dat een dergelijke boodschap ontvangt, schrijft “commit” in zijn eigen lijst, voert die commit uit, en zendt een bericht “voltooid” terug naar de co¨ordinator. Door het gebruik van stabiel geheugen is dit een zeer veilige algoritme. • Oefening Wat gebeurt er als de co¨ordinator ergens in dit proces uitvalt en later weer opstart? Wat gebeurt er als een ondergeschikt proces ergens uitvalt en later weer opstart? Gelijktijdigheid Bij de bespreking van de implementatie lieten we in het midden hoe eventuele conflicten geregeld werden. Dit is het onderwerp van de gelijktijdigheidsregeling. • Sloten De oudste oplossing is het gebruik van sloten. Een transactie vraagt exclusieve toegang tot een resource. Slechts nadat deze door het systeem is toegestaan worden de operaties uitgevoerd. We onderscheiden – Leessloten die vermijden dat een schrijfrecht wordt toegekend aan een ander proces. Er kunnen een willekeurig aantal leessloten simultaan toegekend worden. – Schrijfsloten die vermijden dat een ander proces toegang (lees- of schrijf-) krijgt. Er kan simultaan slechts ´e´en schrijfslot toegekend worden. 45

De eenheid die op slot kan gezet worden noemen we de korrel.De korrel kan een volledig bestand, een record in een databank, een veld of een byte zijn. De korrelgrootte heeft invloed op de werking van het systeem. Een grotere korrel belemmert het parallellisme. Er zullen immers meer conflicten optreden. Een kleinere korrel veroorzaakt meer overhead. Er moeten immers meer sloten aangemaakt worden en de hoeveelheid informatie per slot is groter. Om deadlocks en conflicten tussen processen zoveel mogelijk te vermijden worden sloten niet op willekeurige ogenblikken tijdens de transactie aangemaakt of vrijgegeven. In de plaats deelt men een transactie op in een groeifase en een krimpfase. Tijdens de groei worden enkel sloten aangemaakt. Tijdens de krimp worden ze ´e´en voor ´e´en vrijgegeven. Het proces kan op verschillende manieren gebruik maken van deze twee fasen om de werking te vergemakkelijken. 1. Als er geen schrijfoperaties gebeuren tijdens de groeifase kan er gemakkelijk teruggekeerd worden naar de begintoestand als een bepaald slot niet kan verkregen worden. 2. Als alle transacties twee fasen gebruiken zijn alle volgordes die ontstaan door parallellisme consistent met seri¨ele uitvoering. 3. Als de krimpfase pas begint wanneer de transactie klaar is, dus na commit of abort , dan leest een transactie altijd een waarde die geschreven is door een gecommitted proces. Bij het gebruik van sloten kunnen deadlocks optreden. De standaard technieken kunnen worden toegepast. Detectie is hier effici¨enter omdat een transactie gemakkelijker kan vernietigd worden. Het hele concept is zo gemaakt dat het al dan niet slagen van een transactie een proces weinig of niet be¨ınvloed. • Optimistisch Sloten zijn een zeer voorzichtige benadering van het probleem. Als het aantal te verwachten botsingen tussen transacties klein is, vormen ze een relatief grote overhead. Dit aantal zal klein zijn als de korrel klein is, en als de transacties geen omvangrijke operaties bevatten. De optimistische benadering bestaat erin alle operaties zonder meer te laten doorgaan. Een eventueel probleem wordt dan opgelost als het zich voordoet. Daartoe wordt bijgehouden welke files gelezen en geschreven worden. Bij de commit wordt bij alle andere transacties gekeken of ´e´en van de files van de transactie veranderd is sinds de transactie werd gestart. Zoja, dan eindigt de transactie met een abort. Deze methode sluit deadlocks uit, en parallellisme is maximaal omdat g´e´en proces ooit op een ander hoeft te wachte. Bij druk verkeer eindigen veel transacties met abort . In dit geval is deze benadering geen goede keuze. • Tijdstempels Een tijdstempel is een unieke tijd die aan een transactie is gekoppeld. Conceptueel is het het ogenblik waarop de (ondeelbare) actie plaatsvindt. Het probleem voor de implementatie is dat in de transactie in werkelijkheid niet op ´e´en specifiek ogenblik gebeurt, maar een zeker tijd in beslag neemt. De implementatie van transacties met behulp van tijdstempels moet ervoor zorgen dat serialiteit, ondeelbaarheid en permanentie gewaarborgd zijn. Aan elke transactie wordt een tijd gekoppeld. Lamport klokken kunnen ervoor zorgen dat de tijden causaal en uniek zijn. Elke toegang tot een resource (bijvoorbeeld een schrijf- of een leesoperatie) gebeurt conceptueel op dit ogenblik. Deze toegang kan voorlopig zijn, op voorwaarde dat de transactie eindigt met een commit of ze kan definitief zijn als de transactie 46

reeds gecommitted heeft. Als een transactie probeert om een resource te gebruiken, moet ze op de laatste toegangstijden letten. Als deze laatste toegangstijd later is dan het tijdsstempel van de transactie moet voorzichtigheid in acht genomen worden. Ook als de laatste toegangstijd vroeger is, maar nog voorlopig kan het zijn dat de transactie moet wachten. Laten we dit illustreren met een voorbeeld. We veronderstellen dat er drie processen zijn, α, β en γ, met Tα < T β < T γ (1.12) Verder veronderstellen we dat α reeds afgelopen is, terwijl β nog loopt en γ eventueel nog loopt, maar ook reeds kan gestopt zijn. We veronderstellen dat de resources hier records zijn. Proces α heeft gelezen en geschreven in alle records die β en γ gebruiken. V´oo´r β en γ starten hebben alle records dus het tijdstempel van α. We bekijken een aantal situaties. 1. β probeert te schrijven, en het tijdstempel is nog Tα . Zolang β nog niet commit wordt het voorlopig schrijfstempel Tβ . Er is geen probleem. 2. β probeert te schrijven of te lezen nadat γ geschreven en gecommitted heeft. Het tijdstempel voor wijziging is nu Tγ . Proces β moet afbreken. 3. β probeert te schrijven of te lezen nadat γ gelezen en gecommitted heeft. Het lezen is geen probleem, maar schrijven kan niet toegelaten worden omdat γ dan met een conceptueel verouderd bestand zou gewerkt hebben. 4. β probeert te lezen, nadat γ een voorlopige schrijf- of leesoperatie gedaan heeft. Een leesoperatie zou geen problemen opleveren, maar als γ voorlopig geschreven heeft moet β wachten en hopen dat γ afbreekt. • Oefening 1. Bedenk zelf een paar bijkomende gevallen en leg uit wat er moet gebeuren. 2. Zijn deadlocks mogelijk bij deze methode?

1.6.6

Gedistribueerde deadlocks

Ook in een gedistribueerd systeem kunnen deadlocks optreden. De betrokken processen kunnen zich nu op verschillende machines bevinden. We hebben vroeger gezien dat er vier manieren waren om met deadlocks om te gaan. 1. Struisvogelpolitiek, we doen alsof het probleem niet bestaat en hopen dat een externe ingreep eventuele problemen kan oplossen. 2. Detectie, we laten toe dat deadlocks optreden maar zorgen ervoor dat we het te weten komen. Ingeval van deadlock moet er een proces verwijderd worden. 3. Onmogelijk maken, we zorgen ervoor dat deadlocks niet optreden door structurele maatregelen te nemen. 4. Vermijden, we letten er bij het toekennen van resources op dat deadlock niet kan optreden.

47

Struisvogelpolitiek wordt vaak toegepast, zeker bij heterogene systemen met veel soorten toepassingen. Specifieke toepassingen die bestaan uit samenwerkende processen kunnen wel een actieve politiek voeren. Detectie is vaak de meest bruikbare actieve politiek. We bespreken hierna een paar algoritmen. Deadlocks kunnen onmogelijk gemaakt worden, maar dit is moeilijker dan op een centraal systeem. Vermijden wordt niet gebruikt omdat de algoritmen per proces een lijst van benodigde resources veronderstellen. Detectie van een gedistribueerde deadlock Voorkomen en vermijden zijn moeilijk in gedistribueerde systemen. Detectie blijkt een meer handelbare mogelijkheid. Bovendien zijn transacties minder gevoelig voor afbreken waardoor het oplossen van een deadlock na detectie eenvoudiger is. • Een gecentraliseerde oplossing Deze bestaat erin dat een co¨ordinator de allocatieboom bijhoudt en detectie algoritmen uitvoert op deze boom. Dit kan enkel indien alle processen alle (pogingen tot) allocatie van een resource melden aan de co¨ordinator. Een alternatief is een periodieke update van de co¨ordinator door de deelnemende processen. Coördinator

Coördinator

A

S

C

R

B

T

Machine 1

A

S

C

R

B

T

Machine 2

A

S

S

C

Wil R

Wil

Houd B

T

Vrij

Figuur 1.27: Een overkill situatie bij een centrale co¨ordinator: B vraagt T aan nadat het R heeft vrijgegeven, maar de boodschappen komen in omgekeerde volgorde bij de co¨ordinator. Figuur 1.27 laat zien wat kan gebeuren als de communicatie in het netwerk onvoorspelbaar is. Doordat de boodschap van vrijgeven van een resource later bij de co¨ordinator aankomt dan de boodschap van aanvraag, veronderstelt de co¨ordinator ten onrechte dat er een deadlock opgetreden is. Hij gaat over tot het oplossen van dit probleem door een proces te verwijderen. 48

Deze overkill is een verlies aan resources en capaciteit, maar hoeft niet dramatisch te zijn. Een mogelijke oplossing is het gebruik van een Lamport tijd. Een boodschap krijgt dan een tijdstempel mee. Bij ontvangst kan een bericht en detectie van een vermoedelijke deadlock door de co¨ordinator, gaat deze rondvragen of er nog hangende berichten met een vroeger tijdstempel zijn. Als alle berichten zijn binnen gekomen kan de diagnose met vertrouwen gesteld worden. • Gedistribueerde detectie Er zijn heel wat algoritmen gepubliceerd. We bespreken de Chandy-Misra-Haas algoritme van 1983. Hierbij is het toegelaten om meerdere resources tegelijk aan te vragen. We zullen nu een gewijzigde versie van het resource-allocatie-graaf gebruiken waarbij de resources niet meer voorgesteld worden. De pijlen in figuur 1.28 stellen derhalve wachtsituaties voor, waarbij een proces kan wachten op een actie van een ander proces, eventueel op een andere machine. Het is onmiddellijk duidelijk dat er een deadlock opgetreden is. Deze wordt als volgt gevonden. (0,2,3) =3 =0

=1 (0,0,1)

(0,1,2)

(0,3,5)

=5

=2

(0,5,7)

(0,2,4)

=7

(0,4,6) =4

=6

(0,7,0)

Figuur 1.28: Gedistribueerde detectie Wanneer proces 0 zijn aanvraag naar de resource van proces 1 lanceert, stelt het vast dat het moet wachten. Het zendt een boodschap naar 1 met zijn nummer (0), het proces dat het bericht zendt (0) en het proces waarnaar het bericht wordt gezonden. Dit is bericht (0, 0, 1). Bij ontvangst van dit bericht, vervangt proces 1 de identificatie van de afzender door zijn eigen nummer (1) en verzendt het bericht naar alle processen waarop het wacht. Dit is bericht (0, 1, 2). Zoals in figuur 1.28 te zien is bereikt het bericht uiteindelijk proces 0, met als initiator eveneens 0. Dit proces heeft dus de deadlock gedtecteerd, en kan aan een oplossing beginnen. E´en oplossing is onmiddellijk af te breken. Dit is effici¨ent, maar leidt tot overkill indien twee processen tegelijkertijd de deadlock ontdekken. Een andere oplossing is mogelijk indien, tijdens het rondgeven van het bericht, elk proces zichzelf toevoegt aan de lijst van betrokken processen. De afzender kan dan zien welk proces het hoogste procesnummer heeft en dit proces vragen af te breken. Het hoogste procesnummer is vaak laatst toegekend, en op deze manier wordt dus het jongste proces verwijderd. Onmogelijk maken van gedistribueerde deadlock Transacties laten toe om gestructureerde maatregelen te nemen die deadlocks voorkomen. We veronderstellen hierbij opnieuw dat de processen strict geordend zijn: elk proces draagt zijn eigen unieke tijdstempel. Deze tijdstempel geeft aan hoe lang het proces reeds actief is, en dit wordt bij deze

49

methode gebruikt als een maat voor het resource-verbruik. De conventie die we invoeren zorgt ervoor dat er enkel wachtcondities kunnen optreden in een bepaalde volgorde van tijdstempels, hetzij dalend, hetzij stijgend. Dit voorkomt cycly in het allocatiegraaf. Er zijn twee methodes. 1. wait-die: Een proces dat een resource wil die in bezit is van een jonger proces mag wachten, een proces dat een resource wil die in het bezit is van een ouder proces moet zichzelf vernietigen. Het is duidelijk dat enkel wachtcondities kunnen bestaan waarbij een ouder proces op een jonger wacht. Hierdoor gaan minder oudere processen verloren dan jongere. 2. wound-wait: Een proces dat een resource van een ouder proces nodig heeft wacht. Een proces dat een resource van een jonger proces ambieert kan het jongere proces vernietigen. Beide methodes maken gebruik van transacties om het be¨eindigen van een proces zonder schade te laten gebeuren. De methode wait-die (1) heeft het nadeel dat een jonger proces nadat het zichzelf vernietigd heeft, onmiddellijk opnieuw zal starten. Dit geeft aanleiding tot een reeks van mislukte pogingen tot het oudere proces klaar is. Bij wound-wait (2) verdwijnt een jonger proces even van het toneel. Als het onmiddellijk terug opstart, zal het moeten wachten op het oudere proces dat nu bezig is.

50