Gelijktijdigheid: deadlock en utisterving

Start Omhoog Computersystemen Besturingssystemen Processen Threads Gelijktijdigheid: Wederzijdse uitsluiting Gelijktijdigheid: deadlock en utisterving Geheugenbeheer Virtueel geheugen Uniprocessor planning Multiprocessor en real-time planning Bestandsbeheer I/O beheer en schijfplanning Bash Powershell Begrippen

6.1. Principes van een deadlock

Een dodelijke omarming of impasse (deadlock) kan worden gedefinieerd als een permanente blokkering van een aantal processen die concurreren om systeembronnen (voorzieningen, resources) of die met elkaar communiceren. Een verzameling processen verkeert in een impasse wanneer elk proces in de verzameling bezig is te wachten op een gebeurtenis (meestal het vrijkomen van een bepaalde bron) die alleen geïnitieerd kan worden door een ander proces in de verzameling. De impasse is permanent, omdat geen van de gebeurtenissen ooit geïnitieerd zal worden. In tegenstelling tot andere problemen bij het beheer van concurrerende processen, is er over het algemeen geen efficiënte oplossing. Bij alle deadlocksituaties spelen tegenstrijdige behoeften aan bronnen, waarbij twee of meer processen betrokken zijn. Een algemeen voorbeeld is de deadlock in het verkeer. Figuur 6-1a toont een situatie waarin vier auto's ongeveer tegelijk aankomen bij een kruising van vier wegen. De vier kwadranten van de kruising zijn de bronnen die beheerd moeten worden. Willen de vier auto's allemaal rechtdoor rijden over de kruising, dan luiden de vereiste bronnen om precies te zijn als volgt:

  • Auto 1, reist naar het noorden, heeft kwadranten a en b nodig.
  • Auto 2 heeft kwadranten b en c nodig.
  • Auto 3 heeft kwadranten c en d nodig.
  • Auto 4 heeft kwadranten d en a nodig.
  • Een typische wegcode is dat een auto op een kruispunt moet stoppen om het voertuig dat van rechts komt voorrang te verlenen. Deze regel werkt als er slechts twee of drie auto's op de kruising bevinden. Bijvoorbeeld, als alleen de noordelijke en westelijke auto's het kruispunt naderen, zal de noordelijke auto moeten wachten en de westelijke auto door laten gaan. Als alle vier de auto op hetzelfde moment aankomen, en iedere auto zich aan de regel houdt, zal iedere auto zich onthouden om het kruispunt op te rijden. Dit veroorzaakt dit een potentiële deadlock. De impasse is enkel potentieel, niet actueel, omdat de nodige middelen beschikbaar zijn om een van de auto's voor te laten gaan. Als één auto uiteindelijk kiest om verder te gaan, kan het dat doen.

    Indien alle vier wagens de regels negeren en op hetzelfde moment (voorzichtig) het kruispunt oprijden, dan neemt elke wagen beslag op een bron (één kwadrant), maar kan niet doorgaan omdat op de vereiste tweede bron al beslag is gelegd door een andere auto. Dit is een echte deadlock.

    Laten we nu eens kijken naar een voorstelling van een deadlock met betrekking tot processen en computer bronnen. Figuur 6.2 (gebaseerd op een in [BACO03]), die wij aanduiden als een gezamenlijk vooruitgangsdiagram, illustreert de voortgang van de twee processen die strijden om twee bronnen. Ieder proces heeft voor een bepaalde tijd het exclusieve gebruik nodig van beide bronnen. Twee processen, P en Q, hebben de volgende algemene vorm:

    Proces P

    Proces Q

    •••

    •••

    Get A

    Get B

    •••

    •••

    Get B

    Get A

    •••

    •••

    Release A

    Release B

    •••

    •••

    Release B

    Release A

    •••

    •••

    In figuur 6.2, representeert de x-as de voortgang van de uitvoering van P en de y-as de voortgang in de uitvoering van Q. Het gezamenlijke verloop van beide processen wordt daarom voorgesteld door een pad voortgaat vanaf de oorsprong in noordoostelijke richting. Voor een systeem met één processor, kan er slechts één proces tegelijk uitgevoerd worden, en het pad bestaat uit afwisselende horizontale en verticale segmenten met een horizontaal segment die een periode waarin P wordt uitgevoerd en Q wacht vertegenwoordigt en een verticaal segment die een periode waarin Q wordt uitgevoerd en P  wacht vertegenwoordigt. De afbeelding geeft gebieden aan waarin zowel P en Q resource A (schuine omhoogstaande lijnen) vereisen; zowel P en Q vereisen bron B (neerwaartse schuine lijnen); en zowel P en Q vereisen beide middelen. Omdat we aannemen dat elk proces exclusieve controle over elke bron vereist, dit zijn allemaal verboden gebieden; dat wil zeggen dat het onmogelijk is voor ieder pad de gezamenlijke uitvoeringsvoortgang van P en Q om deze gebieden binnen te gaan voor te stellen.

    De figuur toont zes verschillende uitvoering paden. Deze kunnen als volgt samengevat worden:

  • Q bezet B en daarna A en geeft vervolgens B en A vrij. Wanneer P de uitvoering hervat, zal het kunnen beide bronnen kunnen te bezetten.
  • Q bezet B en daarna A. P voert en blokkeert op een verzoek om A. Q geeft B en A vrij. Wanneer P de uitvoering hervat, zal het beide bronnen kunnen bezetten.
  • Q bezet B en vervolgens bezet P A. Een deadlock is onvermijdelijk, omdat de uitvoering van Q wordt geblokkeerd op A en de uitvoering van P wordt geblokkeerd op B.
  • P bezet A en vervolgens bezet Q B. Een deadlock is onvermijdelijk, omdat de uitvoering van Q wordt geblokkeerd op A en de uitvoering van p wordt geblokkeerd op B.
  • P bezet A en daarna B. Q wordt uitgevoerd en wordt geblokkeerd op een verzoek om B. P geeft A en B vrij. Wordt de uitvoering van Q hervat, dan kan Q beide voorzieningen bezetten.
  • P bezet A en daarna B en geeft vervolgens A en B vrij. Wordt de uitvoering van Q hervat, dan kan Q beide voorzieningen bezetten.
  • Het grijze gebied in figuur 6.2, dat we een fataal gebied zouden kunnen noemen, heeft betrekking op het commentaar op de paden 3 en 4. Als dit fatale gebied op een pad van de uitvoering ligt, is deadlock onontkoombaar. Merk op dat het bestaan van een fataal gebied afhankelijk is van de logica van de twee processen. Deadlock is echter alleen onontkoombaar als de samengestelde voortgang van de twee processen een pad creëert dat over het fatale gebied voert.

    Of een deadlock optreedt, is afhankelijk van de dynamiek van de uitvoering en van de kenmerken van de toepassing. Veronderstel bijvoorbeeld dat P niet beide voorzieningen tegelijk nodig heeft, maar de volgende vorm heeft:

    Proces P

    Proces Q

    •••

    •••

    Get A

    Get B

    •••

    •••

    Release A

    Get A

    •••

    •••

    Get B

    Release B

    •••

    •••

    Release B

    Release A

    •••

    •••

    Deze situatie is weergegeven in figuur 6.3. Bestudeer deze figuur en overtuig jezelf ervan dat nooit een deadlock zal ontstaan, ongeacht de timing van de processen ten opzichte van elkaar.

    Een samengesteld voortgangsdiagram kan dus worden gebruikt om de uitvoeringsgeschiedenis van twee processen die bronnen delen, te herleiden. In gevallen waarbij meer dan twee processen strijden om dezelfde bron, zal het diagram evenveel dimensies hebben als er processen zijn. De basisprincipes met betrekking tot fatale gebieden en deadlock blijven echter gelijk.

     

    6.1.1. Herbruikbare bronnen

    We kunnen twee algemene categorieën hulpbronnen (resources) onderscheiden: herbruikbare en verbruikbare. Een herbruikbare hulpbron (reusable resource) is een voorziening die veilig kan worden gebruikt door één proces tegelijk en die door dat gebruik niet opraakt. Processen krijgen gebruikseenheden van een bron die ze later vrijgeven voor hergebruik door andere processen. Voorbeelden van herbruikbare bronnen zijn processors, 1/0-kanalen, hoofdgeheugen en secundair geheugen, apparaten en gegevensstructuren, zoals bestanden, databases en semaforen.

    Een voorbeeld van een deadlock bij herbruikbare hulpbronnen zijn twee processen die wedijveren om de exclusieve toegang tot een bestand D Op schijf en een tapestation T. De programma's voeren de bewerkingen uit zoals weergegeven in figuur 6.4. Een deadlock treedt op wanneer elk proces een bron bezet heeft en verzoekt om de andere bron. Een deadlock treedt bijvoorbeeld op als het systeem met multiprogrammering de uitvoering van de processen als volgt verweeft:

    p0 p1 q0 q1 p2 q2

    Dit lijkt misschien eerder een programmeerfout dan een probleem voor de ontwerper van het besturingssysteem. We hebben echter gezien waarom het ontwerpen van programma's met gelijktijdigheid een probleem is. Zulke deadlocks treden nu eenmaal op en de oorzaak ligt vaak verborgen in complexe programmalogica, wat detectie lastig maakt. Eén benadering voor het opvangen van zo'n deadlock is om in het systeemontwerp beperkingen te stellen voor de volgorde waarin bronnen worden aangevraagd.

    Een ander voorbeeld van een deadlock bij een herbruikbare voorziening hangt samen met aanvragen voor hoofdgeheugen. Veronderstel dat de ruimte die kan worden toegewezen, 200 kilobytes (KB) is en de volgende reeks van aanvragen optreedt:

    P1 P2
    ••• •••
    Request 80 Kbytes; Request 70 Kbytes;
    ••• •••
    Request 60 Kbytes; Request 80 Kbytes;

    De deadlock treedt op wanneer beide processen hun tweede verzoek uitvoeren. Is de hoeveelheid geheugen waarom zal worden verzocht niet vooraf bekend. dan is dit type deadlock moeilijk af te handelen met beperkingen in het systeemontwerp. Dit specifieke probleem kan uiteindelijk het best worden opgelost door het probleem onmogelijk te maken met behulp van virtueel geheugen, dat wordt besproken in hoofdstuk 8.

    6.1.2. Verbruikbare bronnen

    Een verbruikbare hulpbron (consumable resource) is een voorziening die kan worden gemaakt (geproduceerd) en vernietigd (geconsumeerd). Meestal is het aantal verbruikbare bronnen van een bepaald soort onbeperkt. Een producerend proces dat niet geblokkeerd is, kan elk gewenst aantal verbruikbare bronnen maken. Wordt de bron gebruikt door een proces, dan houdt zij op te bestaan. Voorbeelden van verbruikbare voorzieningen zijn interrupts, signalen, berichten en informatie in I/O-buffers.

    Een voorbeeld van een deadlock bij verbruikbare bronnen is het volgende paar processen, waarbij ieder proces een bericht van een ander proces probeert te ontvangen en dan een bericht naar een ander proces stuurt:

    P1 P2
    ••• •••
    Receive (P2); Receive (P1);
    ••• •••
    Send (P2, M1); Send (P1, M2);

    De deadlock treedt op als het ontvangen blokkerend is: dit wil zeggen dat het ontvangende proces geblokkeerd is totdat het bericht is ontvangen. Wederom veroorzaakt een ontwerpfout de deadlock. Zulke fouten kunnen heel subtiel en lastig te detecteren zijn. Bovendien kunnen zeldzame combinaties van gebeurtenissen een deadlock veroorzaken; een programma kan lange tijd worden gebruikt, misschien zelfs jaren, voordat het probleem zich openbaart.

    Er is geen effectieve aanpak die alle soorten deadlocks kan afhandelen. Tabel 6.1 bevat de hoofdelementen van de belangrijkste manieren die zijn ontwikkeld: het voorkomen, vermijden en detecteren van deadlock. We behandelen deze drie achtereenvolgens nadat we de brontoewijzingsschema's hebben toegelicht, maar we geven eerst een toelichting op de condities voor deadlock.

    6.1.3. Brontoewijzingsschema's

    Een handig hulpmiddel bij het voorstellen van de toewijzing van bronnen aan processen is het brontoewijzingsschema, dat geïntroduceerd werd door Holt [HOLT72]. Het brontoewijzingsschema is een gerichte graaf die een toestand van het systeem van bronnen en processen weergeeft. waarbij elk proces en elke bron wordt voorgesteld door een node. Een pijl van een proces naar een bron stelt een bron voor die voor een proces benodigd is, maar nog niet is toegewezen (figuur 6.5a). In een bronnode geeft elke punt een instantie van die bron aan. Voorbeelden van brontypes met verschillende instanties zijn I/O-apparaten die door een bronbeheermodule in het besturingssysteem worden toegekend. Een lijn die in een grafiek van een verbruikbare bron naar een proces gaat geeft aan dat het proces een producent van die bron is.

    Figuur 6.5c geeft een voorbeeld van een deadlock. Er is slechts één eenheid elk van de bronnen Ra en Rb. Proces P1 bevat Rb en verzoekt Ra, terwijl P2 Ra bevat, maar Rb verzoekt. Figuur 6.5d heeft dezelfde topologie als figuur 6.5c, maar er is geen deadlock, omdat meerdere eenheden van elke bron beschikbaar zijn.

    De brontoewijzingsschema's van figuur 6.6 komen overeen met de deadlock situaties uit figuur 6.1b. Merk op dat we in dit geval is geen eenvoudige situatie hebben waarin twee processen elk een bron andere bezitten die de ander nodig heeft. Integendeel, in dit geval is er een cirkelvormige keten van processen en bronnen die resulteren in een deadlock.

    6.1.4. Condities voor een deadlock

    Om een deadlock mogelijk te maken moet er aan drie voorwaarden van het beleid worden voldaan:

    1. Wederzijdse uitsluiting. Slechts één proces kan een bron tegelijk gebruiken. Geen proces kan toegang krijgen tot een bron eenheid die is toegewezen aan een ander proces.
    2. Vasthouden en wachten. Een proces kan kan de bronnen vasthouden in afwachting van de toewijzing van andere bronnen.
    3. Geen preëmptieve onderbreking. Geen bron kan met geweld uit een proces worden verwijderd dat het vasthoudt.

    In veel opzichten zijn deze condities gewenst. Bijvoorbeeld, wederzijdse uitsluiting is nodig om de consistentie van resultaten en de integriteit van een database te garanderen. Evenzo moet preëmptieve onderbreking niet willekeurig worden uitgevoerd. Wanneer bijvoorbeeld gegevensbronnen erin betrokken, moet preemptieve onderbreking worden ondersteund door een rollback herstelmechanisme, dat een proces en de bronnen naar een eerdere ​​geschikte toestand herstelt, van waaruit het proces uiteindelijk haar acties kan herhalen.

    De eerste drie voorwaarden noodzakelijk maar niet voldoende voor een deadlock te laten bestaan. Voor de deadlock daadwerkelijk te laten plaatsvinden, is nog een vierde voorwaarde vereist:

    1. Cirkelvormig wachten. Een gesloten keten van processen bestaat, zodat elk proces minstens één bron bevat dat benodigd is door het volgende proces in de keten (bijvoorbeeld figuur 6.5c en Figuur 6.6).

    De vierde conditie is, in feite, een mogelijk gevolg van de eerste drie. Dat is, aangezien er aan de eerste drie voorwaarden is voldaan, een opeenvolging van gebeurtenissen kan plaatsvinden die leiden tot een onoplosbare situatie van cirkelvormig wachten. Het onoplosbaar cirkelvormige wachten is inderdaad de definitie van deadlock. Het cirkelvormig wachten zoals vermeld in voorwaarde 4 is onoplosbaar omdat het aan de eerste drie voorwaarden te voldoet. Dus de vier voorwaarden tezamen vormen voldoende en noodzakelijke voorwaarden voor een deadlock.

    Om deze uiteenzetting te verduidelijken, is het nuttig om terug te keren naar het concept van het gezamenlijke voortgangsdiagram, zoals getoond in figuur 6.2.

    Herinner dat we een fataal gebied gedefinieerd hebben als een, dat wanneer de processen naar dat gebied zijn geëvolueerd, deze processen in impasse impasse zullen belanden. Een fatale gebied bestaat alleen als aan alle van de eerste drie boveenstaande voorwaarden wordt voldaan. Indien er aan één of meer van deze voorwaarden niet wordt voldaan, is er geen fatale gebied en kan er geen deadlock optreden. Dit zijn dus de noodzakelijke voorwaarden voor de deadlock. Om een deadlock te laten voorkomen, moet er niet alleen een fataal gebied zijn, maar ook een sequentie van bronaanvragen die hebben geleid tot het fataal gebied. Als een cirkelvormige wachttijd optreedt, dan is in feite het fatale gebied betreden. Dus, alle vier de bovenstaande voorwaarden volstaan voor een deadlock. Om samen te vatten:

    Mogelijkheid van een deadlock Bestaan van een deadlock
    1. Wederzijdse uitsluiting 1. Wederzijdse uitsluiting
    2. Geen preëmptieve onderbreking 2. Geen preëmptieve onderbreking
    3. Vasthouden en wachten 3. Vasthouden en wachten
      4. Cirkelvormig wachten

    Er bestaan drie algemene benaderingen voor het omgaan met een deadlock. Ten eerste kan men een deadlock voorkomen door het aannemen van een beleid dat een van de voorwaarden elimineert (voorwaarden 1 tot 4). Ten tweede kan men deadlock vermijden door de juiste dynamische keuzes te maken op basis van de huidige toestand van de brontoewijzing. Ten derde kan men proberen de aanwezigheid van een deadlock te detecteren (die voorwaarden 1 tot 4 bevat) en actie te ondernemen om te herstellen. We bespreken elk van deze benaderingen op hun beurt.

    6.2. Voorkomen van een deadlock

    Bij de aanpak om deadlock te voorkomen (deadlock prevention) wordt, eenvoudig gezegd, een systeem zo opgezet dat de mogelijkheid van een deadlock eenvoudigweg wordt uitgesloten. We kunnen methoden voor het voorkomen van deadlock onderbrengen in twee groepen. Een indirecte methode voor het voorkomen van deadlock is het voorkomen dat een van de drie genoemde, noodzakelijke condities (conditie 1 tot en met 3) optreedt. Een directe methode voor het voorkomen van deadlock is het voorkomen dat het cirkelvormig wachten (conditie 4) optreed We gaan nu in op technieken die samenhangen met elk van deze vier condities.

    6.2.1. Wederzijdse uitsluiting

    In het algemeen kan de eerste van de vier genoemde condities, 'wederzijdse uitsluiting', niet onmogelijk worden gemaakt. Vereist de toegang tot een bron wederzijdse uitsluiting, dan moet het besturingssysteem wederzijdse uitsluiting ondersteunen. Bij sommige bronnen, bijvoorbeeld bestanden, kunnen meervoudige toegangen zijn  toegestaan voor lezen maar slechts één exclusieve toegang voor schrijven. Ook in dat geval kan een deadlock optreden, als meer dan één proces toestemming voor schrijven nodig heeft.

    6.2.2. Vasthouden en wachten

    De conditie 'vasthouden en wachten' kan worden voorkomen door te eisen da een proces in één keer alle vereiste systeembronnen aanvraagt en het proces te blokkeren totdat aan alle aanvragen tegelijk kan worden voldaan. Deze aanpak is in twee opzichten inefficiënt. In de eerste plaats kan een proces lange tijd geblokkeerd

    raken in afwachting van alle gevraagde voorzieningen terwijl het misschien ook zou kunnen worden voortgezet met slechts enkele ervan. In de tweede plaats kunnen aan een proces toegewezen bronnen gedurende een lange periode ongebruik blijven terwijl ze ontoegankelijk zijn voor andere processen.

    Er is ook een praktisch probleem, dat ontstaat bij het gebruik van modulair programmeren of een structuur met multithreading voor een toepassing: elke toepassing moet op de hoogte zijn van alle bronnen waarom gevraagd kan worden op alle niveaus of in alle modules om een gecombineerde aanvraag te kunnen indienen.

    6.2.3. Geen preëmptieve onderbreking

    De conditie 'geen preëmptieve onderbreking' kan op verschillende manieren worden voorkomen. Houdt een proces bepaalde bronnen bezet maar wordt een volgend verzoek geweigerd, dan kan worden geëist dat het proces alle bronnen vrijgeeft en, indien nodig, later nog eens verzoekt om de bronnen tezamen met de ontbrekende bron. Ook kan het besturingssysteem een proces preëmptief onderbreken en eisen dal dit zijn bronnen vrijgeeft indien dit proces een voorziening vraagt die op dit moment bezet is door een ander proces. Deze laatste aanpak voorkomt een deadlock alleen indien twee processen niet dezelfde prioriteit hebben.

    Onderbreken is alleen zinvol als het wordt toegepast op bronnen waarvan de toestand gemakkelijk kan worden opgeslagen en later kan worden hersteld, zoals bijvoorbeeld het geval is bij een processor

    6.2.4. Circulair wachten

    De conditie 'cirkelvormig wachten' kan worden voorkomen door een lineaire rangorde van soorten voorzieningen te definiëren: zijn bronnen van soort R toegewezen aan een proces, dan mag het proces vervolgens uitsluitend bronnen aanvragen van het soort dat in rangorde volgt op R.

    We kunnen laten zien hoe deze aanpak werkt door een Index te verbinden aan elke soort bron. Bron Ri gaat dan vooraf aan Ri bij de rangorde i < j. Veronderstel nu dat er een deadlock bestaat tussen twee processen, A en B, omdat A Ri heeft bezet en heeft verzocht om Rj en B Rj heeft bezet en heeft verzocht om Ri. Deze toestand is onmogelijk, omdat dit impliceert dat i < j en j < i.

    Het voorkomen van het 'cirkelvormig wachten' kan evenals het voorkomen van 'vasthouden en wachten' inefficiënt zijn, omdat het processen vertraagt en onnodig de toegang tot voorzieningen weigert.

    6.3. Vermijden van een deadlock

    Een aanpak bij het oplossen van het probleem met deadlock, die subtiel anders is dan het voorkomen van deadlock, is het vermijden van deadlock.2 Bij het voorkomen van deadlock leggen we beperkingen op aan bronaanvragen om minstens één van de vier condities voor deadlock te voorkomen. Dit wordt indirect gedaan, door een van de drie noodzakelijke condities te voorkomen (wederzijdse uitsluiting, vasthouden en wachten, geen preëmptieve onderbreking), of direct, door cirkelvormig wachten te verhinderen. Dit leidt tot inefficiënt gebruik van systeembronnen en inefficiënte uitvoering van processen. Bij het vermijden van deadlock (deadlock avoidance) daarentegen zijn de drie noodzakelijke condities toegestaan, maar worden weloverwogen keuzen gemaakt om te zorgen dat het punt van een deadlock nooit wordt bereikt. Het vermijden laat daardoor meer ruimte open voor gelijktijdigheid dan het voorkomen. Bij het vermijden van deadlock wordt dynamisch besloten of het huidige verzoek om het toewijzen van een voorziening zou kunnen leiden tot een deadlock als aan de vraag wordt voldaan. Het vermijden van deadlock vereist daarom kennis van de toekomstige aanvragen van processen om bronnen.

    In deze paragraaf beschrijven we twee benaderingen voor het vermijden van deadlock:

    Start een proces niet als de bronaanvragen ervan kunnen leiden tot een deadlock.

    Geef geen gehoor aan een volgende aanvraag van een proces om een systeembron als de toewijzing daarvan zou kunnen leiden tot een deadlock.

    Voordelen:

  • Geen voortijdige beëindiging van processen
  • Geen rollbacks
  • Minder beperkingen dan bij voorkomen van deadlock
  • Beperkingen:

    Aantal bronnen nodig voor elk proces moet op voorhand gekend zijn

  • Processen zijn onafhankelijk
  • Volgorde van uitvoeren staat los van synchronisatie
  • Vast nummer van bronnen om te alloceren
  • Een proces mag niet stoppen terwijl het een bron vasthoudt
  • 2 Het begrip vermijden is enigszins verwarrend: we kunnen de hier besproken benaderingen in feite ook beschouwen als voorbeelden van het voorkomen van deadlock; ze voorkomen uiteindelijk het optreden van een deadlock.

    6.4. Detecteren van een deadlock

    Manieren om deadlock te voorkomen, zijn zeer conservatief: ze lossen het probleem van deadlock op door de toegang tot voorzieningen te beperken en processen restricties op te leggen. Een aanpak voor het detecteren van deadlock (deadlock detection), het andere uiterste, beperkt de toegang tot voorzieningen en de acties van

    processen niet. Bij het detecteren van deadlock wordt, waar mogelijk, altijd voldaan aan alle aanvragen van processen voor systeembronnen. Periodiek voert het besturingssysteem een algoritme uit waarmee het de conditie 'cirkelvormig wachten' kan vaststellen, de vierde conditie die eerder werd beschreven en werd geïllustreerd in figuur 6.6.

    6.4.1. Algoritme voor het detecteren van een deadlock

    Een controle op een deadlock kan worden uitgevoerd bij elk verzoek om een voorziening of, minder frequent, op basis van de kans dat een deadlock optreedt. Het uitvoeren van een controle bij elk verzoek Om een systeembron heeft twee voordelen: het leidt tot een vroege detectie en de algoritme is relatief eenvoudig, omdat deze is gebaseerd op incrementele veranderingen in de toestand van het systeem. Daar staat tegenover dat zulke veelvuldige controles veel processortijd verbruiken.

    Een veel gebruikte algoritme voor het detecteren van deadlock is de algoritme die wordt beschreven in [COFF71]. Hierin worden de matrix Allocation de vector Available gebruikt die in de vorige paragraaf zijn beschreven. Daarna een matrix met aanvragen Q gedefinieerd, waarbij Qij de hoeveelheid voorzieningen van type j voorstelt waarom proces i heeft verzocht. De algoritme markeert processen waarvoor geen deadlock bestaat. In eerste instantie is geen enkel proces geparkeerd. Vervolgens worden de volgende stappen uitgevoerd:

    1. Markeer elk proces dat in de matrix Allocation een rij met uitsluitend nullen heeft.
    2. Initialiseren een tijdelijke vector W en stel die gelijk aan de vector Available
    3. Zoek een index i waarvoor geldt dat proces i op dit moment niet gemarkeerd is en rij i van Q kleiner is dan of gelijk is aan W. Dat wil zeggen: Qik Wk,  voor 1 k m.  Wordt zo'n rij niet gevonden, beëindig dan de algoritme.
    4. Wordt zo'n rij wel gevonden, markeer dan proces i en voeg de bijbehorende rij van de matrix Allocation toe aan W. Dat wil zeggen: Wk = Wk + Aik, 1 k m. Keer terug naar Stap 3.

    Een deadlock bestaat uitsluitend als er aan het einde van de algoritme ongemarkeerde processen zijn. Elk ongemarkeerde proces bevindt zich in een deadlock. Deze algoritme gebruikt een methode waarbij een proces wordt gezocht waarvoor aan alle verzoeken om voorzieningen kan worden voldaan vanuit de beschikbare voorzieningen en waarbij wordt verondersteld dat vervolgens al die voorzieningen worden toegewezen, het proces volledig wordt uitgevoerd en de voorzieningen weer worden vrijgegeven. De algoritme zoekt vervolgens een volgend uit te voeren proces. Merk op dat de algoritme niet garandeert dat een deadlock wordt voorkomen; dat zal afhankelijk zijn van de volgorde waarin aan de verzoeken wordt voldaan. De algoritme stelt uitsluitend vast of op dit moment een deadlock bestaat.

    We kunnen figuur 6.10 gebruiken om de algoritme voor het detecteren van deadlock te illustreren. De algoritme wordt als volgt uitgevoerd:

    1. Markeer P4, omdat er geen voorzieningen zijn toegewezen aan P4.
    2. Stel W gelijk aan W = (0 0 0 0 1).
    3. Het verzoek van P3 is kleiner dan of gelijk aan W, dus markeer P3 en Stel W gelijk aan W = W + (0 0 0 1 0) = (0 0 0 1 1).
    4. Geen ander ongemarkeerd proces heeft een rij in Q die kleiner is dan of gelijk is aan W. Beëindig daarom de algoritme.

    6.4.2. Herstel

    Is een deadlock eenmaal gedetecteerd. dan is een aanpak voor herstel (recovery) nodig. De volgende methoden zijn mogelijk. waarvan de eerste de minst geavanceerde en de laatste de meest geavanceerde:

    1. Breek alle processen met een deadlock af. Dit is, geloof het of niet, een van de meest gebruikte en misschien wel de meest gebruikte methode in besturingssystemen.
    2. Draai elk proces met een deadlock terug tot een of ander eerder gedefinieerd controlepunt en herstart alle processen. Dit vereist dat mechanismen voor het terugdraaien (rollback) en herstarten (restart) zijn ingebouwd in het systeem. Bij deze aanpak bestaat het risico dat de deadlock opnieuw zal Optreden. Aangezien gelijktijdige verwerking echter niet een van tevoren bepaalde uitkomst heeft. zal dat meestal niet gebeuren.
    3. Beëindig na elkaar de processen met een deadlock totdat de deadlock niet meer bestaat. De volgorde waarin de te beëindigen processen worden geselecteerd. moet worden gebaseerd op een criterium dat uitgaat van minimale kosten. Na elke beëindiging moet de algoritme voor het detecteren opnieuw worden uitgevoerd om te controleren of de deadlock nog bestaat.
    4. Neem de toegewezen bronnen preëmptief na elkaar af van de processen totdat de deadlock niet meer bestaat. Net zoals bij 3 moet een op kosten gebaseerde selectie worden uitgevoerd en moet de algoritme voor het detecteren opnieuw worden uitgevoerd na elke preëmptieve onderbreking. Een proces waarvan de toewijzing van een bron preëmptief wordt afgenomen, moet worden teruggedraaid tot een punt voorafgaand aan de toewijzing van de bron.

    Voor 3 en 4 kunnen de selectiecriteria worden ontleend aan de volgende opsomming. Kies het proces dat:

  • tot nu toe de minste processortijd heeft verbruikt;
  • tot nu toe de minste uitvoer heeft geproduceerd;
  • de langste resterende duur heeft;
  • tot nu toe de kleinste hoeveelheid toegewezen systeembronnen heeft;
  • de laagste prioriteit heeft.
  • Sommige van deze grootheden zijn gemakkelijker te meten dan andere. Vooral een schatting van de resterende duur is verdacht. Bovendien is er, afgezien van de prioriteit, geen maatstaf voor de 'kosten' voor de gebruiker, die kunnen verschillen van de kosten voor het systeem.

    6.5. Geïntegreerde aanpak van een deadlock

    Zoals tabel 6.1 toont, hebben alle manieren voor de aanpak van deadlock sterke en zwakke punten. In plaats van te proberen een voorziening voor het besturingssysteem te ontwerpen die slechts één van deze manieren toepast, kan het efficiënter zijn in verschillende situaties verschillende benaderingen te gebruiken. [SILB98] oppert de volgende aanpak:

  • Groepeer systeembronnen in een aantal verschillende klassen bronnen.
  • Gebruik de eerder gedefinieerde strategie voor het vermijden van cirkelvormig wachten om deadlock tussen klassen van bronnen te voorkomen.
  • Gebruik binnen één klasse bronnen de algoritme die het best bij de klasse past.
  • Een voorbeeld van deze techniek zijn de volgende klassen van bronnen:

  • Swap-ruimte: blokken geheugen op een secundaire Opslag die worden gebruikt voor het swappen van processen.
  • Procesbronnen: apparaten die kunnen worden toegewezen, bijvoorbeeld magneetbandstations of bestanden.
  • Hoofdgeheugen: pagina's of segmenten die aan processen kunnen worden toegewezen.
  • Interne bronnen: bijvoorbeeld I/O-kanalen.
  • De volgorde in dit overzicht is de volgorde waarin bronnen worden toegewezen. Deze volgorde is aanvaardbaar als we uitgaan van de volgorde van de stappen die een proces tijdens zijn levensduur kan volgen. Binnen elke klasse kan de volgçnde aanpak worden gevolgd:

  • Swap-ruimte: voorkom deadlock door te eisen dat alle vereiste systeembronnen die kunnen worden gebruikt, in één keer worden toegewezen. Dit komt overeen met de aanpak van 'vasthouden en wachten'. Deze manier is redelijk als de maximaal vereiste opslagruimten bekend zijn, wat vaak het geval is. Het vermijden van deadlock is een andere mogelijkheid.
  • Procesbronnen: vermijden van deadlock is bij deze categorie meestal effectief, omdat het redelijk lijkt dat processen vooraf aangeven welke voorzieningen in deze klasse ze nodig kunnen hebben. Het voorkomen van deadlock door een rangorde aan te brengen in de bronnen van deze klasse is ook mogelijk.
  • Hoofdgeheugen: het voorkomen van deadlock door processen preëmptief te onderbreken is vaak de meest geschikte manier bij het hoofdgeheugen. Wordt een proces preëmptief onderbroken, dan wordt het eenvoudig naar het secundaire geheugen geswapt, wat ruimte vrijmaakt voor het oplossen van de deadlock.
  • Interne bronnen: het voorkomen van deadlock door een rangorde in de bronnen aan te brengen, kan worden gebruikt.
  • 6.6. Probleem van de dinerende filosofen

    We zullen nu het probleem van de dinerende filosofen bekijken, dat geïntroduceerd werd door Dijkstra [DIJK71]. Vijf filosofen wonen samen in een huis, waarin de tafel voor hen gedekt is. Het leven van elke filosoof bestond hoofdzakelijk uit nadenken en eten. Na vele jaren nadenken hadden de filosofen afgesproken dat alleen spaghetti werkelijk kon bijdragen aan hun krachtsinspanningen.

    De tafelschikking van de filosofen was eenvoudig (figuur 6.11): ze aten aan een ronde tafel met daarop een schaal spaghetti, vijf borden, één voor elke filosoof, en vijf vorken. Een filosoof die wat wilde eten, ging aan de tafel zitten op de aan hem toegewezen plaats en at spaghetti met de twee vorken naast zijn bord. Het probleem luidt als volgt: ontwerp een ritueel (algoritme) waarmee alle filosofen kunnen eten. De algoritme moet voldoen aan wederzijdse uitsluiting, zodat twee filosofen niet tegelijk dezelfde vork kunnen gebruiken, en moet deadlock en uithongering (in dit geval zowel letterlijk als figuurlijk) vermijden.

    Dit probleem is op zichzelf niet erg belangrijk of zelfs maar relevant. Het illustreert echter wel enkele elementaire problemen bij deadlock en uithongering. Bovendien tonen de pogingen om oplossingen te ontwikkelen veel van de moeilijkheden van gelijktijdige verwerking (zie bijvoorbeeld [GlNG901]. Bovendien kan het probleem van de dinerende filosofen dienen als een representatief voorbeeld van problemen die samenhangen met het coördineren van gedeelde bronnen bij het optreden als een applicatie gelijktijdige uitvoeringsthreads bevat. Derhalve is dit probleem is een standaard test voor het evalueren benaderingen

    Met betrekking tot synchronisatie.

     

    6.6.1. Oplossing gebruikmakend van semaforen

    Figuur 6.12 suggereert een oplossing met het gebruik van semaforen. Iedere filosoof neemt eerst de vork aan de linkerkant en dan de vork aan de rechterkant. Nadat de filosoof klaar is met eten, worden de twee vorken teruggeplaatst op de tafel. Helaas leidt deze oplossing, tot een deadlock: Als alle filosofen op hetzelfde moment honger hebben, gaan ze allemaal zitten, en zullen ze allemaal de vork aan hun linkerhand nemen, en ze zullen allemaal naar de andere vork willen grijpen, die niet daar is. In deze onwaardige positie, zullen alle filosofen verhongeren.

    Om het risico van de impasse te doorbreken, konden we vijf extra vorken kopen (een meer propere oplossing!) of om de filosofen spaghetti te leren eten met slechts één vork. Als een andere benadering, kunnen we het toevoegen van een bediende overwegen die laat maar vier filosofen tegelijk in de eetkamer toestaat. Met ten hoogste vier zetelende filosofen, heeft ten minste één filosoof toegang tot twee vorken. Figuur 6.13 toont opnieuw een dergelijke oplossing met het gebruik van semaforen. Deze oplossing vrij is van deadlock en uithongering.

    6.6.2. Oplossing gebruikmakend van monitors

    Figuur 6.14 toont een oplossing voor het probleem van dinerende filosofen met behulp van een monitor. Een vector van vijf conditie variabelen wordt gedefinieerd, een conditie variabele per vork. Deze conditie variabelen worden gebruikt om een filosoof toe te staan te wachten op de beschikbaarheid van een vork. Daarnaast is er een Booleaanse vector die de beschikbaarheidsstatus van elke vork registreert (waar betekent dat de vork beschikbaar is). De monitor bestaat uit twee procedures. De get_forks procedure wordt door een filosoof gebruikt om zijn of haar linker of rechter vork te grijpen. Als een van beide vorken niet beschikbaar is, wordt het filosoofproces op de wachtrij van de bijbehorende conditie variabele gezet. Dit maakt het mogelijk dat een ander filosoof proces de monitor kan binnengaan. De release-forks procedure wordt gebruikt om de twee vorken beschikbaar te maken. Merk op dat de structuur van deze oplossing vergelijkbaar is met die van de semafoor oplossing dat voorgesteld wordt in figuur 6.12. In beide gevallen grijpt een filosoof eerst de linker vork en vervolgens de rechter vork. In tegenstelling tot de seinpaal oplossing, deze monitor oplossing heeft geen last van een deadlock, omdat slechts één proces tegelijk in de monitor kan zitten. Zo wordt het eerste filosoof proces dat de monitor binnen gaat gewaarborgd dat het de rechtervork kan grijpen nadat hij de linkervork heeft gegrepen, voordat de volgende filosoof aan de rechterkant de kans heeft om de linker vork te grijpen, welk de rechtervork is van deze filosoof.

     

    6.7. Mechanismen voor gelijktijdigheid in Unix

    UNIX biedt verschillende mechanismen voor communicatie en synchronisatie tussen processen. We gaan hier in op de belangrijkste:

  • Pijpen
  • Berichten
  • Gedeeld geheugen
  • Semaforen
  • Signalen
  • Pijpen, berichten en gedeeld geheugen zijn een middel voor gegevensuitwisseling tussen processen. Semaforen en signalen worden gebruikt voor het initiëren van acties van andere processen.

    6.7.1. Pijpen

    Een van de belangrijkste bijdragen van UNIX aan de ontwikkeling van besturingssystemen is de pijp (pipe). De pijp is gebaseerd op het concept van coroutines [RITC84], een pijp is een cirkelvormige buffer waarmee twee processen kunnen communiceren volgens het producent/consumentmodel. Het is daarmee een FIFO-wachtrij (first-in-first-out), die wordt geschreven door het ene proces en die wordt gelezen door het andere proces.

    Bij het maken van een pijp krijgt deze een vaste grootte in bytes. Probeert een proces te schrijven naar een pijp, dan wordt het schrijfverzoek onmiddellijk uitgevoerd als er voldoende ruimte is Is er onvoldoende ruimte, dan wordt het proces geblokkeerd. Op overeenkomstige wijze wordt een lezend proces geblokkeerd als het probeert meer bytes te lezen dan zich op dat moment in de pijp bevinden; anders wordt het leesverzoek onmiddellijk uitgevoerd. Het besturingssysteem past wederzijdse uitsluiting toe. Dat wil zeggen: slechts één proces tegelijk heeft toegang tot de pijp

    Er zijn twee soorten pijpen: benoemde pijp (named pipe) en naamloze pijp (unnamed pipe). Alleen gerelateerde processen kunnen een naamloze pijp delen terwijl processen zonder relatie alleen een benoemde pijp kunnen delen.

    6.7.2. Berichten

    Een bericht is een blok tekst dat vergezeld gaat van een type. UNIX biedt de systeemaanroepen msgend en msgrcv om processen te laten deelnemen aan het doorgeven van berichten. Aan elk proces is een wachtrij verbonden, die werkt als een postvak.

    De afzender van een bericht specificeert het type bij elk bericht dat wordt verzonden en dit type kan door de ontvanger worden gebruikt als een selectiecriterium. De ontvanger kan berichten ontvangen in de volgorde first in, first out of op basis van het type. Een proces wordt opgeschort wanneer het probeert een bericht

    te verzenden naar een volle wachtrij. Een proces wordt ook opgeschort wanneer het probeert te lezen uit een lege wachtrij. Probeert een proces een bericht van een bepaald type te lezen en mislukt dit, dan wordt het proces niet onderbroken.

    6.7.3. Gedeeld geheugen

    Gedeeld geheugen is de snelste vorm van communicatie tussen processen die UNIX biedt. Het is een blok virtueel geheugen dat door verschillende processen gedeeld wordt. Processen lezen en schrijven in gedeeld geheugen met de hulp van dezelfde machine-instructies die ze gebruiken om te lezen en schrijven in andere delen van hun virtuele geheugenruimte. Processen kunnen alleen-lezen 0f alleen-schrijven zijn, wat per proces wordt bepaald. Voorzieningen met betrekking tot wederzijdse uitsluiting zijn geen onderdeel van de voorzieningen Voor gedeeld geheugen, maar moeten geleverd worden door de processen die het gedeeld geheugen gebruiken.

    6.7.4. Semaforen

    De systeemaanroepen voor semaforen in UNIX System V zijn een generalisatie van de primitieven semWait en semSignal die werden gedefinieerd in hoofdstuk 5: verschillende bewerkingen kunnen tegelijkertijd worden uitgevoerd en bij de bewerkingen voor het verhogen en verlagen kunnen waarden groter dan 1 worden gebruikt. De kernel voert alle gevraagde bewerkingen uit op atomair niveau: geen enkel ander proces krijgt toegang tot de semafoor totdat alle bewerkingen zijn voltooid.

    Een semafoor bestaat uit de volgende elementen:

  • De huidige waarde van de semafoor;
  • Het procesidentificatienummer van het laatste proces dat de semafoor heeft gebruikt;
  • Het aantal processen dat wacht totdat de waarde van de semafoor groter is dan de huidige waarde;
  • Het aantal processen dat wacht totdat de waarde van de semafoor gelijk is aan nul.
  • Bij de semaforen horen wachtrijen met processen die op die semafoor zijn geblokkeerd.
  • Semaforen worden eigenlijk gecreëerd binnen een verzameling, waarbij een semafoorverzameling bestaat uit een of meer semaforen. De systeemaanroep semctl geeft de mogelijkheid om alle semafoorwaarden in de verzameling op één moment een waarde te geven. Daarnaast bestaat er een systeemaanroep sem_op, die als argument een lijst van semafoorbewerkingen accepteert, die elk zijn gedefinieerd in een van de semaforen in de verzameling. Wordt deze aanroep uitgevoerd, dan voert de kernel de aangegeven bewerkingen één voor één uit. Voor iedere bewerking specificeert de waarde sem_op de feitelijke functie. Hierbij bestaan de volgende mogelijkheden:

  • Is sem_op positief, dan verhoogt de kernel de waarde van de semafoor en wekt de kernel alle processen die wachten Op het verhogen van de semafoor.
  • Is sem_op 0, dan controleert de kernel de waarde van de semafoor. Is deze 0, dan gaat de kernel verder met de andere bewerkingen in de lijst. Is deze niet 0, dan verhoogt de kernel het aantal processen dat wacht totdat deze semafoor 0 is en schort de kernel het proces op tot de gebeurtenis die de waarde van de semafoor gelijk maakt aan 0.
  • Is sem_op negatief en is de absolute waarde van sem_op kleiner dan of gelijk aan de waarde van de semafoor, dan telt de kernel sem_op (een negatief getal) op bij de waarde van de semafoor. Is het resultaat 0, dan wekt de kernel alle processen die wachten totdat de waarde van de semafoor gelijk is aan 0.
  • Is sem_op negatief en is de absolute waarde van sem_op groter dan de waarde van de semafoor, dan schort de kernel het proces op tot de gebeurtenis die de waarde van de semafoor verhoogt.
  • Deze generalisatie van de semafoor biedt een aanzienlijke flexibiliteit voor het uitvoeren van de synchronisatie en de coördinatie van processen.

    6.7.5. Signalen

    Een signaal is een softwaremechanisme dat een proces informeert over het optreden van asynchrone gebeurtenissen. Een signaal lijkt op een hardware-interrupt, maar kent geen prioriteiten. Dat wil zeggen: alle signalen worden gelijkwaardig behandeld. Signalen die tegelijk optreden, worden één voor één aan een proces gepresenteerd, zonder specifieke volgorde.

    Processen kunnen signalen naar elkaar verzenden en de kernel kan intern signalen verzenden. Een signaal wordt bezorgd door een veld bij te werken in de procestabel voor het proces waarnaar het signaal wordt verzonden. Aangezien elk signaal wordt opgeslagen als één bit, kunnen signalen van een bepaald type niet

    worden opgeslagen in een wachtrij. Een signaal wordt verwerkt vlak nadat een proces ontwaakt voor de uitvoering of zodra een proces zich voorbereidt op een terugkeer uit een systeemaanroep. Een proces kan reageren op een signaal door een bepaalde standaardactie uit te voeren (bijvoorbeeld beëindigen), door een functie voor signaalafhandeling uit te voeren of door het signaal te negeren.

    Tabel 6.2 noemt de signalen die zijn gedefinieerd voor UNIX SVR4.

    Herhalingsvragen

    1. Geef voorbeelden van herbruikbare en verbruikbare bronnen.

      Voorbeelden van herbruikbare bronnen zijn processors, I/O-kanalen, hoofdgeheugen en secundair geheugen, apparaten en gegevensstructuren zoals bestanden, databases en semaforen.
      Voorbeelden van verbruikbare bronnen zijn interrupts, signalen, berichten en informatie in I/O buffers.
       
    2. Aan welke drie condities moet zijn voldaan om deadlock mogelijk te maken?

      Wederzijdse uitsluiting: Slechts één proces tegelijk mag een bron gebruiken.
      Vast te houden en
      te wachten:
      Een proces mag toegewezen bronnen vasthouden terwijl het wacht op de toewijzing aan anderen.
      Geen preëmptie:
      Een bron kan niet zomaar worden afgenomen van een proces dat deze vasthoudt.

       
    3. Wat zijn de vier condities die deadlock veroorzaken?

      De bovengenoemde drie voorwaarden, plus:
      Cirkelvormig wachten:
      Er bestaat een gesloten keten van processen waarin dat elk proces ten minste een bron vasthoudt die het volgende proces in de keten nodig heeft (voorbeeld figuur 6.5c en figuur 6.6).

       
    4. Hoe kan de conditie 'vasthouden en wachten' worden voorkomen?

      De conditie 'vasthouden en wachten' kan worden voorkomen door te eisen dat een proces in één keer al zijn vereiste systeembronnen aanvraagt en het proces te deblokkeren totdat aan alle aanvragen tegelijk kan worden voldaan.
       
    5. Geef twee manieren om de conditie 'geen preemptieve onderbreking' te voorkomen?

      Houdt een proces bepaalde bronnen bezet maar wordt een volgend verzoek geweigerd, dan kan worden geëist dat het proces alle bronnen vrijgeeft en, indien nodig, later ook nog eens verzoekt om de bronnen tezamen met ontbrekende bron. Ook kan het besturingssysteem een proces preëmptief onderbreken en eisen dat dit zijn bronnen vrijgeeft indien dit proces een voorziening vraagt die op dit moment bezet is door een ander proces.
       
    6. Hoe kan de conditie 'cirkelvormig wachten' worden voorkomen?

      De conditie 'cirkelvormig wachten' kan worden voorkomen door een lineaire rangorde van soorten voorzieningen te definiëren: zijn bronnen van soort R toegewezen aan een proces, dan mag het proces vervolgens uitsluitend bronnen aanvragen van het soort dat in rangorde volgt op R.
       
    7. Wat is het verschil tussen vermijden, detecteren en voorkomen van deadlock?

      Voorkomen van deadlock: Beperkingen opleggen aan bronaanvragen om minstens één van de vier condities van deadlock te voorkomen. Dit wordt indirect gedaan door een van de drie noodzakelijke condities te voorkomen (wederzijdse uitsluiting, vasthouden en wachten, geen preëmptieve onderbreking), of direct, door cirkelvormig wachten te verhinderen.
      Vermijden van deadlock:
      De drie noodzakelijke condities zijn toegestaan, maar er worden weloverwogen keuzen gemaakt om te zorgen dat het punt van een deadlock nooit wordt bereikt.
      Detecteren van deadlock: Waar mogelijk altijd voldoen aan alle aanvragen van processen voor systeembronnen. Periodiek een algoritme uitvoeren waarmee de conditie 'cirkelvormig wachten' kan worden vastgesteld.

    Probleemvraagstukken

    1. Laat zien dat de vier condities voor deadlock van toepassing zijn op figuur 6.1a.
       
    2. Beschrijf in woorden elk van de getoonde paden in figuur 6-3, vergelijkbaar met  de beschrijving van de paden in figuur 6.2 in paragraaf 6.1.
       
    3. Bij de situatie volgens figuur 6-3 werd beweerd dat daar geen deadlock kon optreden.  Ga deze bewering na.
       
    4. Ga uit van de volgende momentopname van een systeem. Er is op dit moment een wachtrij met openstaande verzoeken waaraan niet is voldaan.
      1. Bereken hoeveel elk proces nog kan aanvragen en noteer dit in de kol men  onder 'Nog nodig'.
         
      2. Bevindt het systeem zich op dit moment in een veilige of een onveilige toestand? Waarom?
         
      3. Is er op dit moment sprake van een deadlock? Waarom wel of waarom niet.
         
      4. Bij welke processen bestaat eventueel een deadlock of zou een deadlock kunnnen optreden?
         
      5. Als een aanvraag van m komt voor (0, 1, 0, 0), kan dan onmiddellijk veilig aan da verzoek worden voldaan? En in welke toestand (deadlock. veilig, onveilig) zou het inwilligen van dat volledige verzoek het systeem plaatsen? Voor welke processen zou het onmiddellijk voldoen aan dit volledige verzoek eventueel een deadlock veroorzaken?
         
    5. Pas de algoritme voor het detecteren van deadlock uit paragraaf 6.4 toe op volgende gegevens en toon de resultaten.
       
    6. 6.6 Een spoelsysteem (figuur 6-16) bestaat uit een invoerproces 1, een gebruikersproces P en een uitvoerproces 0, die zijn verbonden door twee buffers. De processen wisselen informatie uit in blokken van gelijke grootte. Deze blokken worden opgeslagen in een buffer op een schijf. Tussen de invoerbuffer en de uitvoerbuffer zit een zwevende begrenzing die afhangt van de snelheid van de processen. De communicatieprimitieven die worden gebruikt, garanderen dat wordt voldaan aan de volgende beperking van de bron:

          i + o < max

      waarbij
          max = maximum aantal blokken op schijf
          i = aantal invoerblokken op schijf
          o = aantal uitvoerblokken op schijf

      Het volgende is bekend over de processen:
      1. 1. Zolang de omgeving gegevens aanlevert, zal proces 1 deze vroeg of laat opslaan als invoer op schijf (mits er schijfruimte vrijkomt).
      2. Zolang invoer beschikbaar is op de schijf zal proces P die vroeg of laat verbruiken en een eindige hoeveelheid gegevens uitvoeren naar schijf voor elk ingevoerd blok (mits er schijfruimte vrijkomt).
      3. Zolang uitvoer beschikbaar is op de schijf, zal proces 0 deze vroeg of laat verbruiken.

      Toon aan dat in dit systeem een deadlock kan ontstaan.
       

    7. Formuleer een aanvullende beperking voor de voorziening die de deadlock uit opgave 6.5 voorkomt maar die toch toelaat dat de begrenzing tussen de invoerbuffer en de uitvoerbuffer kan worden aangepast aan de huidige behoeften van de processen.
       
    8. In het multiprogrammeringsysteem THE [DIJK68] is een drum (een voorloper van de schijf voor secundaire opslag) verdeeld in invoerbuffers, verwerkingsgebieden en uitvoerbuffers, met zwevende begrenzingen die afhankelijk zijn van de snelheid van de betrokken processen. De huidige toestand van de drum kan worden beschreven met de volgende parameters:
          max = maximum aantal pagina’s op de drum;
          i = aantal invoerpagina’s op de drum;
          p = aantal verwerkingspagina’s op de drum;
          o = aantal uitvoerpagina’s op de drum;
          reso = minimum aantal pagina’s dat is gereserveerd voor de uitvoer;
          resp = minimum aantal pagina’s dat is gereserveerd voor de verwerking.
      Formuleer de noodzakelijke bronbeperkingen die garanderen dat de capaciteit van de drum niet wordt overschreden en dat een minimum aantal pagina’s permanent is gereserveerd voor uitvoer en verwerking.
       
    9. In het multiprogrammeringsysteem THE kan een pagina de volgende overgangen tussen toestanden maken:
      1. leeg invoerbuffer (productie invoer)
      2. invoerbuffer verwerkingsgebied (consumptie invoer)
      3. verwerkingsgebied uitvoerbuffer (productie uitvoer)
      4. uitvoerbuffer leeg (consumptie uitvoer)
      5. leeg verwerkingsgebied (procedureaanroep)
      6. verwerkingsgebied leeg (procedureterugkeer)
      1. Beschrijf het effect van deze overgangen in termen van de grootheden i, o en p.
         
      2. Kan een van de overgangen leiden tot een deadlock als de veronderstellingen over de invoerprocessen, de gebruikersprocessen en de uitvoerprocessen uit opgave 6.5 waar zijn?
         
    10. Ga uit van een systeem met in totaal 150 eenheden geheugen, die als volgt zijn toegewezen aan drie processen:

       
      Proces Maximum Vasthouden
      1 70 45
      2 60 40
      3 60 15

      Pas de bankiersalgoritme toe om te controleren of veilig kan worden voldaan aan elk van de volgende aanvragen. Is dat mogelijk, geef dan de reeks van beëindigingen aan die gegarandeerd mogelijk is. Is dat niet mogelijk, toon dan de afname in de resulterende toewijzingstabel.

      1. Er komt een vierde proces binnen met een maximale geheugenbehoefte van 60 eenheden en een eerste behoefte van 25 eenheden.
         
      2. Er komt een vijfde proces binnen met een maximale geheugenbehoefte van 60 eenheden en een eerste behoefte van 35 eenheden.
         
    11. Beoordeel de bruikbaarheid van het bankiersalgoritme in een besturingssysteem.
       
    12. Een algoritme voor een pijplijn wordt zo geïmplementeerd dat een door proces P0
      geproduceerde stroom gegevenselementen van type T een reeks processen P1, P2, Pn-1 doorloopt, die in deze volgorde bewerkingen uitvoeren op de elementen.
      1. Definieer een gegeneraliseerde berichtenbuffer die alle gedeeltelijk geconsumeerde gegevenselementen bevat en schrijf een algoritme voor proces Pi (0 i n -1) met de vorm
        repeat
        ontvangen van voorganger;
        element consumeren;
        verzenden naar opvolger;
        forever
        Veronderstel dat P0 lege elementen ontvangt die zijn verzonden door Pn-1. De algoritme moet de processen rechtstreeks laten werken met de in de buffer opgeslagen berichten, zodat kopiëren niet nodig is.
         
      2. Bewijs dat voor het proces geen deadlock kan ontstaan vanwege de gemeenschappelijke buffer.
         
      1. Drie processen delen vier eenheden van een bron die uitsluitend één voor één kunnen worden gereserveerd en vrijgegeven. Elk proces heeft maximaal twee eenheden nodig. Bewijs dat een deadlock niet kan optreden.
         
      2. N processen delen M eenheden van een bron die uitsluitend één voor één kunnen worden gereserveerd en vrijgegeven. De maximale behoefte van elk proces is nooit groter dan M en het totaal van alle maximale behoeften is kleiner dan M + N. Bewijs dat geen deadlock kan optreden.
         
    13. Veronderstel dat een systeem bestaat uit vier processen en één systeembron. De huidige status van de claim en toewijzingsmatrices is
      C= A=
      Wat is het minimale benodigde aantal eenheden van de bron dat voor deze toestand beschikbaar moet zijn om deze veilig te laten zijn?
    14. Ga uit van de volgende mogelijkheden voor het afhandelen van deadlock: (1) de bankiersalgoritme, (2) het detecteren van deadlock en het verwijderen van een thread, waardoor alle voorzieningen vrijkomen, (3) het van tevoren reserveren van alle voorzieningen, (4) het herstarten van een thread en het vrijgeven van alle voorzieningen als de thread moet wachten, (5) het aanbrengen van een rangorde in bronnen en (6) het detecteren van deadlock en een rollback van de threadacties.
      1. Een criterium dat kan worden gebruikt om de verschillende benaderingen van deadlock te evalueren, is het volgende: welke benadering maakt de grootste gelijktijdigheid mogelijk? Met andere woorden: bij welke benadering kunnen de meeste threads worden uitgevoerd zonder te wachten als er geen deadlock is? Maak een rangorde van 1 tot en met 6 van de genoemde mogelijkheden voor het afhandelen van deadlock, waarbij 1 de grootste gelijktijdigheid heeft. Licht uw rangorde toe.
         
      2. Een ander criterium is efficiëntie: welke benadering vereist de minste processoroverhead? Maak een rangorde van 1 tot en met 6 van de genoemde benaderingen, waarbij 1 het meest efficiënt is, en ga er daarbij vanuit dat een deadlock een zeldzame gebeurtenis is. Licht uw rangorde toe. Verandert uw rangorde als deadlocks vaak optreden?
         
    15. Geef commentaar op de volgende oplossing van het probleem van de dinerende filosofen. Een hongerige filosoof pakt eerst de vork links van hem. Is de vork rechts van hem ook beschikbaar, dan pakt hij die vork en begint hij te eten. Is de rechter vork niet beschikbaar, dan legt hij de linker vork neer en herhaalt hij de cyclus.
       
    16. Stel, er zijn twee typen filosofen. Het ene type, een ‘linkshandige’, pakt altijd eerst de vork links van hem en het andere type, een ‘rechtshandige’, pakt altijd eerst de vork rechts van hem. Het gedrag van een linkshandige is gedefinieerd in figuur 6.11. Het gedrag van een rechtshandige luidt als volgt:
       
      begin
          repeat
              think;
              wait ( fork[ (i + 1) mod 5]);
              wait ( fork[i] );
              eat;
              signal (fork[i] );
              signal ( fork[ (i + 1) mod 5]);
          forever

      end;

      Bewijs het volgende;
      a. Elke tafelschikking van linkshandigen en rechtshandigen met minimaal één links- handige en één rechtshandige vermijdt een deadlock.

      b. Elke tafelschikking van linkshandigen en rechtshandigen met minimaal één links- handige en één rechtshandige voorkomt uithongering.
       

    17. In figuur 6.17 is een andere oplossing voor het probleem van de dinerende filosofen met behulp van monitoren weergegeven. Vergelijk deze oplossing met die in figuur 6.14 en beschrijf je conclusies.
       
    18. In tabel 6.3 is het bij sommige atomaire bewerkingen in Linux niet nodig dat een variabele tweemaal wordt benaderd, zoals bij de bewerking atomicread (atomic_t *v). Een eenvoudige leesbewerking is in elke architectuur uiteraard atomair. Waarom is deze bewerking dan toch toegevoegd aan de verzameling atomaire bewerkingen?
       
    19. Bekijk het volgende codefragment in een Linux-systeem.
      read_lock(&mr_rwlock);
      write_lock(&mr_rwlock);
      Waarin mr_rwlock is een lees-schrijfgrendel is. Wat is het effect van deze code?
       
    20. De twee variabelen a en b hebben startwaarden van respectievelijk 1 en 2. De volgende code is voor een Linux-systeem:
       
      Thread 1 Thread 2
      a = 3;  
      mb();  
      b = 4; c = b;
        d = a;

      Welke mogelijke fouten worden vermeden door het gebruik van geheugenbarrières?