Gelijktijdigheid: Wederzijdse uitsluiting

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

Het centrale thema van besturingssysteemontwerp zijn allemaal betrokken met het beheer van processen en threads:

  • Multiprogrammering: Het beheer van meerdere processen binnen een Uniprocessorsysteem.

  • Multiprocessing: Het beheer van meerdere processen binnen een Multiprocessor.

  • Gedistribueerde verwerking: Het beheer van meerdere processen die worden uitgevoerd over meerdere, gedistribueerde computersystemen. De recente toename van clusters is een uitstekend voorbeeld van dit type systeem.

  • Gelijktijdigheid is fundamenteel voor al deze gebieden en voor het besturingssysteemontwerp. Gelijktijdigheid bevat een massa ontwerpkwesties, zoals communicatie tussen processen, delen en of wedijveren voor bronnen (zoals geheugen, bestanden en I/O toegang), synchronisatie van de activiteiten tussen processen en toewijzing van processortijd aan processen. We zullen zien dat deze kwesties niet alleen in Multiprocessing en gedistribueerde verwerkingsomgevingen voorkomen maar zelfs in single-processor Multiprogrammering systemen.

    Gelijktijdigheid treedt op in drie verschillende contexten:

  • Meerdere applicaties: Multiprogrammering was bedacht om toe te laten dat processortijd dynamisch gedeeld kon worden tussen een aantal actieve applicaties.
  • Gestructureerde applicaties: Als een aanvulling op de principes van modulair ontwerp en gestructureerde programmering, kunnen sommige applicaties eigenlijk geprogrammeerd worden als een set van gelijktijdige processen.
  • Besturingssysteem structuur: Dezelfde structurele voordelen gelden voor systeemprogramma's en we hebben gezien dat besturingssystemen zelf vaak geïmplementeerd zijn als een set van processen en threads.

    Doordat dit onderwerp zo belangrijk is zullen vier hoofdstukken en een appendix aan gelijktijdig-gerelateerde kwesties besteed worden.  Hoofdstukken 5 en 6 zullen gaan over gelijktijdigheid in Multiprogrammering en Multiprocessing systemen. Hoofdstukken 16 en 18 onderzoeken gelijktijdigheid in verband met gedistribueerde verwerking.

     

    5.1. Principes van gelijktijdigheid

    In een single-processor Multiprogrammering systeem worden processen in tijd tussengevoegd (interleaved) om te laten lijken dat uitvoering simultaan gebeurd (zie figuur 2.12a). Zelfs ondanks dat er geen parallelle verwerking heeft plaatsgevonden en ondanks het feit dat er een bepaalde hoeveel overhead is tussen het schakelen van de processen, voorziet tussengevoegde (interleaved) uitvoering voor belangrijke voordelen in efficiënte verwerking en programmastructuur. In een meervoudig processorsysteem is het zelfs mogelijk om niet alleen de processen tussen te voegen, maar zelfs om elkaar te overlappen (figuur 2.12b).

    Op het eerste zicht lijkt het dat tussenvoeging (interleaving) en overlapping een fundamenteel andere uitvoermodus en verschillende problemen weergeeft. In feite kunnen beide technieken bekeken worden als voorbeelden van gelijktijdige verwerking en beide hebben te maken met dezelfde problemen. In het geval van een Uniprocessor stammen de problemen af van een basiskarakteristiek van Multiprogrammeringsystemen: De relatieve uitvoersnelheid van processen kan niet worden voorspeld. Het hangt af van de activiteiten van andere processen, de manier waarop het besturingssysteem de onderbrekingen afhandelt en het planningsbeleid van het besturingssysteem. De volgende moeilijkheden doen zich voor:

    1. Het delen van globale bronnen zit vol met risico's. Bijvoorbeeld, als twee processen tegelijk gebruikmaken van dezelfde globale variabele en beide voeren een lees- en schrijfopdracht uit op die variabele, dan is de volgorde waarin de verschillende lees- en schrijfopdrachten gebeuren van groot belang. Een voorbeeld van dit probleem wordt in de volgende onderafdeling getoond.
    2. Het is moeilijk voor een besturingssysteem om de toewijzing van bronnen optimaal te beheren. Bijvoorbeeld, proces A kan het voor een specifiek I/O kanaal gebruik aanvragen van, en de besturing daarvan worden toegestaan en dan opgeschort worden voordat het gebruik gaat maken van dat kanaal. Het kan voor het besturingssysteem onwenselijk zijn om eenvoudigweg dat kanaal te vergrendelen en te voorkomen dat het door andere processen wordt gebruikt; dit zal inderdaad tot een deadlock-conditie leiden, zoals beschreven in hoofdstuk 6.
    3. Het zal zeel moeilijk worden een programmafout te lokaliseren, omdat de resultaten niet deterministisch en reproduceerbaar zijn.

    Alle voorgaande moeilijkheden treden ook op in een Multiprocessor systeem, omdat ook hier de relatieve uitvoersnelheid niet te voorspellen is. Een Multiprocessor systeem moet ook nog omgaan met problemen die komen van de simultane uitvoering van processen. In principe zijn deze dezelfde als die van een Uniprocessorsysteem.

    5.1.1. Een eenvoudig voorbeeld

    Beschouw de volgende procedure:

    void echo()
    {
    chin = getchar();
    chout = chin;
    putchar(chout);
    }

    Deze procedure laat de elementaire elementen zien van een programma dat een karakter echo procedure voorziet; input wordt verkregen van een toetsenbord, een aanslag per keer. Iedere ingevoerde karakter wordt opgeslagen in de variabele chin. Dan wordt het overgedragen aan de variabele chout en naar het beeldscherm gestuurd. Eender welk programma kan deze procedure herhaaldelijk oproepen om gebruikersinvoer te aanvaarden en te tonen op het gebruikersscherm.

    Nu ga ervan uit dat er een Single-processor Multiprogrammeringssysteem hebben dat een enkele gebruiker ondersteund. De gebruiker kan van de ene applicatie naar de andere applicatie springen en iedere applicatie gebruikt voor invoer hetzelfde toetsenbord en voor uitvoer hetzelfde scherm. Omdat iedere applicatie de echo procedure nodig heeft is het logisch dat dit een gedeelde procedure is en dat dit wordt geladen in het gedeelte van het geheugen dat gedeeld wordt door alle applicaties. Dus wordt er maar een enkele kopie van de echo procedure gebruikt.

    Het delen van het hoofdgeheugen tussen de processen is handig om efficiënte en interactie tussen processen mogelijk te maken. Alhoewel zulke deling kan leiden tot problemen. Beschouw de volgende sequentie:

    1. Proces P1 roept de echo procedure aan en wordt onmiddellijk onderbroken nadat getchar zijn waarde teruggeeft en opslaat in chin. Op dit moment is de meest recent ingevoerd karakter x opgeslagen in variabele chin.
    2. Proces P2 wordt geactiveerd en roept de echo procedure aan, welke de conclusie, de invoer en de uitvoer van een enkel karakter, y, op het scherm uitvoert.
    3. Proces P1 wordt voortgezet. Tegen deze tijd is de waarde x overschreven in chin en daardoor verloren gegaan. In de plaats daarvan bevat y de waarde van chin, welk verplaatst wordt naar chout en getoond wordt.

    Het eerste karakter is dus verloren gegaan en het tweede karakter is tweemaal getoond. De bron van dit probleem is de globaal gedeelde variabele chin. Meerdere processen hebben toegang tot deze variabele. Als één proces de variabele aanpast en dan onderbroken wordt, kan een ander proces deze variabele aanpassen, voordat het eerste proces deze variabele heeft kunnen gebruiken. Veronderstel dat we enkel één proces op een moment toelaten in die procedure. Dan zal de voorafgaande sequentie als volgt verlopen:

    1. Proces P1 roept de echo procedure aan en wordt onmiddellijk onderbroken na de conclusie van de invoerfunctie. Op dit moment, is de meest recent ingevoerde karakter x opgeslagen in variabele chin.
    2. Proces P2 wordt geactiveerd en roept de echo procedure aan. Omdat P1 nog steeds in de echo procedure zit, alhoewel het momenteel opgeschort is, is P2 geblokkeerd om de procedure aan te roepen. Daarom wordt P2 opgeschort, wachtend op de beschikbaarheid van de echo procedure.
    3. Op een later moment, wordt proces P1 voortgezet en zal het de uitvoer van de echo voltooien. Het juiste karakter x zal worden getoond.
    4. Als P1 de echo verlaat, zal dit de blokkering van P2 opheffen. Zodra P2 wordt voortgezet zal de echo procedure succesvol kunnen worden aangeroepen.

    Dit probleem was beschreven met de aanname dat er een Single-processor en een Multi-programmeringsbesturingssysteem was. Dit voorbeeld laat zien dat het probleem van gelijktijdigheid zelfs voorkomt met een enkele processor. In een Multiprocessor systeem ontstaan dezelfde problemen van beschermde gedeelde bronnen en zal dezelfde oplossing werken. Eerst, laten we ervan uitgaan dat er geen mechanisme is om de globaal gedeelde variabelen te controleren:

    1. Proces P1 en P2 zijn beide, ieder op een andere processor, in uitvoering. Beide processen roepen de echo procedure aan.

    2. De volgende gebeurtenissen treden op; gebeurtenissen op dezelfde lijn treden parallel op:

    Proces P1

    Chin = getchar();

    Chout = chin;

    Proces P2


    Chin = getchar();

    Putchar(chout);

    Het resultaat is dat de karakterinvoer naar P1 verloren is gegaan voordat het getoond is en de karakterinvoer naar P2 wordt door zowel P1 als P2 getoond. Laten we opnieuw de mogelijkheid toevoegen om de methode af te dwingen dat enkel een proces per keer in de echo kan zitten. Dan zal de volgende sequentie optreden:

    1. Processen P1 en P2 zijn beide in uitvoering, ieder op een aparte processor. P1 roept de echo procedure aan.

    2. Terwijl P1 in de echo procedure zit, roept P2 de echo aan. Omdat P1 nog steeds in de echo procedure zit (of P1 opgeschort of uitvoerend is), is P2 geblokkeerd om de procedure binnen te gaan. Daarom wordt P2 opgeschort, wachtend op de beschikbaarheid van echo procedure.

    3. Op een later moment voltooid P1 de uitvoering van de echo, verlaat de procedure en gaat verder met zijn uitvoering. Onmiddellijk nadat P1 de echo heeft verlaten, wordt P2 voortgezet en zal het beginnen met de uitvoer van de echo.

    De reden waarom we een probleem hebben is in het geval van een Uni-processorsysteem, dat een interrupt de uitvoering op eender welke plaatst in het proces kan onderbreken. In het geval van een Multiprocessor systeem hebben we hetzelfde probleem en zelfs kan er nog een probleem zijn omdat er twee processen gelijktijdig in uitvoering zijn en beide dezelfde globale variabele proberen te benaderen. De oplossing voor beide types is echter hetzelfde: beheer de toegang tot de gedeelde bron.

    5.1.2. Race conditie

    Een race conditie treedt op wanneer meerdere processen of threads data items lezen en schrijven, zodat het uiteindelijke resultaat afhangt van de rangschikking van de uitvoering van instructies in de diverse processen. Laat ons twee eenvoudige voorbeelden nemen.

    Bij het eerste voorbeeld gaan we uit van twee processen, P1 en P2, die de globale variabele a delen. Op een gegeven moment van uitvoering herziet P1 variabele a naar de waarde 1 en op een gegeven moment van uitvoering herziet P2 variabele a naar de waarde 2. Dit betekent dat de twee taken in een wedloop zitten om de variabele a te beschrijven. In dit voorbeeld bepaald de "verliezer' van de race (het proces dat als laatste de herziening uitvoert) de uiteindelijke waarde van a.

    In ons tweede voorbeeld gaan we uit van twee processen, P3 en P4, die de globale variabelen b en c delen, met de oorspronkelijke waardes b = 1 en c = 2. Op een gegeven moment van uitvoering voert P3 de toewijzing uit b = b + c, en op een gegeven moment van uitvoering, voert P4 de toewijzing uit c = b + c. Let op dat de twee processen verschillende variabelen herziet. De uiteindelijke waarden van de twee variabelen hangen af van de rangschikking waarin de twee processen de twee toewijzingen uitvoert. Als P3 de toewijzing als eerste uitvoert, dan zal de uiteindelijke waarden b = 3 en c =5 zijn. Als P4 de toewijzing als eerste uitvoert dan zullen de uiteindelijke waarden b = 4 en c = 3 zijn.

    5.1.3. Besturingssysteem belangen

    1. Welke ontwerp- en beheerproblemen treden op door het bestaan van gelijktijdigheid? We kunnen de volgende belangen opsommen:
    2. Het besturingssysteem moet in staat zijn op de hoogte te blijven van de diverse processen. Dit wordt gedaan door middel van proces controleblokken en is beschreven in hoofdstuk 4.
    3. Het besturingssysteem moet bronnen toewijzen en de toewijzing ongedaan maken voor ieder actief proces. Op momenten willen meerdere processen dezelfde bron benaderen. Deze bronnen zijn:
      1. Processortijd: Dit is de planningsfunctie.
      2. Geheugen: De meeste besturingssystemen gebruiken een virtueel geheugenschema.
      3. Bestanden: Wordt behandeld in hoofdstuk 12.
      4. I/O apparaten: Wordt behandeld in hoofdstuk 11.
    4. Het besturingssysteem moet de data en de fysieke bronnen van ieder proces beschermen tegen ongewenste beïnvloeding van andere processen. Dit gaat gepaard met technieken dat betrekking heeft met geheugen, bestanden en I/O apparaten.
    5. Het functioneren van een proces en de uitvoer dat het produceert moet onafhankelijk zijn van de snelheid waarmee dit wordt uitgevoerd en relatief tot de snelheid van andere gelijktijdige processen. Dit is het onderwerp van dit hoofdstuk.

    Om te begrijpen hoe de kwestie van snelheidsonafhankelijkheid kan worden geregeld, moeten we kijken hoe de verschillende processen onderling kunnen reageren.

    5.1.4. Proceswisselwerking

    De manieren waarop processen op elkaar inwerken kunnen we klasseren in de mate waarop ze van elkaars bestaan afweten. Tabel 5.2 somt drie mogelijke niveaus van elkaars bewustzijn en de consequenties van elk:

  • Processen zijn zich niet bewust van elkaar:
  • Processen zijn zich indirect bewust van elkaar:
  • Processen zijn zich direct bewust van elkaar:
  • De condities zullen niet altijd overduidelijk zijn zoals gesuggereerd in tabel 5.2. Verschillende processen kunnen beide aspecten van competitie en samenwerking vertonen. Desalniettemin, is het productief om de drie items van de voorafgaande lijst apart te onderzoeken en te bepalen wat de implicaties zijn voor het besturingssysteem.

    5.1.4.1. Concurrentie tussen processen voor bronnen

    Concurrent processen komen met elkaar in conflict als ze met elkaar wedijveren voor het gebruik van dezelfde bron. In zijn zuivere vorm, kunnen we de situatie als volgt beschreven. Twee of meer processen moeten gedurende hun uitvoering toegang krijgen tot een bron. Geen proces is zich bewust van het bestaan van andere processen, en elk zal niet worden aangetast door de uitvoering van andere processen. Hieruit volgt dat elk proces de toestand van ieder bron moet verlaten die het onaangetast gebruikt. Voorbeelden van bronnen zijn: I/O apparaten, geheugen, processortijd, en de klok.
    Er is geen uitwisseling van informatie tussen de concurrerende processen. Echter, kan de uitvoering van een proces het gedrag van concurrerende processen beïnvloeden. Vooral wanneer twee processen toegang wensen tot één bron, dan zal die bron door het besturingssysteem aan één proces toegewezen worden, en de ander zal moeten wachten. Derhalve, zal het proces dat de toegang geweigerd werd, worden vertraagd. In een extreem geval, kunnen de geblokkeerde proces nooit toegang krijgen tot de bronnen en dus ook nooit succesvol beëindigen.

    In het geval van concurrerende processen moeten er drie controleproblemen getrotseerd worden. Ten eerste is er de noodzaak van wederzijdse uitsluiting. Veronderstel dat twee of meer processen toegang tot één niet-deelbare bron vereisen, zoals een printer. Gedurende de duur van de uitvoering, zal ieder proces opdrachten naar het I/O apparaat sturen, statusinformatie ontvangen, gegevens verzenden en/of gegevens ontvangen. Wij verwijzen naar dergelijke hulpbron als een kritieke bron, en het gedeelte van het programma dat het gebruikt als een kritieke sectie van het programma. Het is belangrijk dat slechts één programma per keer te toegestaan ​​in zijn kritieke sectie. We kunnen niet eenvoudigweg op het besturingssysteem steunen om deze beperking te begrijpen en af te dwingen, omdat de gedetailleerde vereisten niet voor de hand liggen. In
    het geval van de printer, bijvoorbeeld, willen we dat elk individuele proces de controle heeft over de printer, terwijl het een volledig bestand afdrukt. Anders zullen lijnen van concurrerende processen worden tussengevoegd.

    De handhaving van de wederzijdse uitsluiting creëert twee extra controleproblemen. Een daarvan is dat van een deadlock. Beschouw bijvoorbeeld twee processen, P1 en P2, en twee bronnen, R1 en R2. Veronderstel dat elk proces toegang moet hebben tot beide bronnen om zijn functie te kunnen uitvoeren. Dan is het mogelijk om de volgende situatie te hebben: het besturingssysteem wijst R1 aan P2 toe en R2 aan P1 toe. Elk proces wacht op een van de twee bronnen. Geen van beide zal de bron vrijgeven dat het reeds bezit totdat het een andere bron heeft verworven en de functie die beide bronnen nodig had heeft uitgevoerd.  De twee processen zijn deadlocked.

    Een laatste controleprobleem is uitsterving. Stel dat drie processen (P1, P2, P3) ieder periodieke toegang vereisen tot bron R. Beschouw de situatie waarin P1 in het bezit is van de bron, en zowel P2 en P3 vertraagd zijn, wachtend op die bron. Wanneer P1 zijn kritieke sectie verlaat, zullen ofwel P2 of P3 toegestaan moeten worden R te benaderen. Veronderstel dat het besturingssysteem toegang tot P3 verleent en P1 opnieuw toegang vereist voordat P3 zijn kritieke sectie voltooit. Als het besturingssysteem toegang verleent tot P1 nadat P3 is voltooid, en vervolgens afwisselend toegang verleent tot P1 en P3, dan kan P2 onbeperkt de toegang tot die bron worden ontzegd, hoewel er geen deadlock situatie is.
    Controle van de concurrentie gaat onvermijdelijk gepaard met het besturingssysteem, omdat het besturingssysteem de bronnen toewijst. Bovendien, de processen zelf moeten op een of andere manier de vereiste voor wederzijdse uitsluiting kunnen uitdrukken, zoals het vergrendelen van een bron vóór het gebruik. Elke oplossing zal gepaard gaan met een of andere vorm van ondersteuning door het besturingssysteem, zoals de voorziening van de vergrendelingsfaciliteit. Figuur 5.1 toont het wederzijdse uitsluitingsmechanisme in abstracte termen. Er zijn n processen om gelijktijdig uitgevoerd te worden. Iedere proces bevat (1) een kritieke sectie die werkt op bepaalde bronnen Ra en (2) aanvullende code voorafgaand aan en de kritieke sectie volgend die niet gepaard gaat met de toegang tot Ra. Omdat alle processen dezelfde bron Ra benaderen is het gewenst dat slechts één proces tegelijk in zijn kritieke sectie kan zitten. Om wederzijdse uitsluiting af te dwingen, zijn er twee functies voorzien: entercritical en exitcritical. Elke functie neemt als argument de naam van de bron die het onderwerp is van concurrentie. Ieder proces dat probeert zijn kritieke sectie binnen te gaan terwijl een ander proces voor dezelfde bron is in zijn kritieke zit, wordt gedwongen te wachten.
    Er blijft over om de specifieke mechanismen te onderzoeken voor de functies van entercritical en exitcritical te verschaffen . Voor het moment, stellen we deze kwestie uit terwijl we kijken naar de andere gevallen van proces interactie.

    5.1.4.2. Samenwerking tussen bronnen door delen

    Het geval van samenwerking door het delen omvat processen die samenwerken met andere processen zonder zich expliciet bewust te zijn van hen. Bijvoorbeeld, meerdere processen kunnen toegang tot de gedeelde variabelen of tot gedeelde bestanden of databanken. Processen mogen de gedeelde data gebruiken en bij te werken zonder naar andere processen te verwijzen, maar weet dat andere processen toegang tot dezelfde data kunnen hebben. Derhalve moeten de processen samenwerken om er zeker van te zijn dat de data die ze delen goed beheerd worden. De controlemechanismen moeten de integriteit van de gedeelde data waarborgen.

    Omdat data op de bronnen wordt gehouden (apparaten, geheugen), zijn de controleproblemen van wederzijdse uitsluiting, deadlock en uithongering weer aanwezig. Het enig verschil is dat de data-items op twee verschillende modi benaderd kan worden, lezen en schrijven, en enkel schrijf operaties moeten wederzijds exclusief zijn.

    Echter, buiten deze problemen, is er een nieuwe vereiste: Die van data coherentie. Als een eenvoudig voorbeeld, Beschouw een boekhoudkundige toepassing waarin verschillende gegevenselementen bijgewerkt kunnen worden. Stel dat twee gegevensitems a en onderhouden moeten worden in de relatie a = b. Dat wil zeggen, een programma dat een waarde bijwerkt moet ook de andere bijwerken om de relatie te behouden. Beschouw de volgende twee processen:

    P1:
    a = a + 1;
    b = b + 1;

    P2:
    b = 2 * b;
    a = 2 * a;

    Als de toestand oorspronkelijk consistent was, dan zal elk proces afzonderlijk de gedeelde data in een consistente toestand verlaten. Beschouw nu de volgende gelijktijdige uitvoeringssequentie, waarbij de twee processen wederzijdse uitsluiting op elk individueel gegevensitem (a en b) handhaven: 

    a = a + 1;
    b = 2 * b;
    b = b + 1;
    a = 2 * a;

    Op het einde van deze uitvoeringssequentie, geldt de voorwaarde a = b niet langer meer. Bijvoorbeeld, als we beginnen met a = b = 1, aan het einde van deze uitvoeringssequentie hebben we a = 4 en b = 3. Het probleem kan vermeden worden door de gehele sequentie in ieder proces te declareren om een kritieke sectie te zijn. We zien dus dat het begrip kritieke sectie belangrijk is bij de samenwerking en door het delen. Dezelfde abstracte functies van entercritical en exitcritical zoals eerder besproken (figuur 5.1) kan hier gebruikt worden. In dit geval kan het argument voor de functie een variabele zijn, een bestand of elk ander gedeeld object zijn. Bovendien, als kritieke secties gebruikt worden om de integriteit van gegevens te voorzien, hoeft er geen specifieke bron of variabele te zijn die kan worden aangemerkt als een argument. In dat geval is, kunnen we denken aan een argument als zijnde een identificatie dat gedeeld is tussen de gelijktijdige processen om de kritieke secties te identificeren die wederzijds exclusief moeten zijn.

    5.1.4.3. Samenwerking tussen processen door communicatie

    In de eerste twee gevallen die we hebben besproken, heeft ieder proces zijn eigen geïsoleerde omgeving dat de andere processen niet bevat. De interacties tussen processen zijn indirect. In beide gevallen is er een deling. In het geval van concurrentie, zijn er deelbare bronnen zonder zich bewust te moeten zijn van andere processen. In het tweede geval delen ze waarden, en hoewel ieder proces niet uitdrukkelijk bewust is van andere processen, is het zich bewust van de noodzaak om de data-integriteit te handhaven. Wanneer processen door communicatie samenwerken, nemen de verschillende processen deel aan een gemeenschappelijke inspanning die alle processen koppelen. De communicatie biedt een manier om de verschillende activiteiten te synchroniseren, of te coördineren.

    Meestal kan de communicatie worden gekenmerkt als een of andere bestaande vorm van berichten. Primitieven voor het verzenden en ontvangen van berichten kunnen verstrekt worden als onderdeel van de programmeertaal of door de kernel van het besturingssysteem.

    Omdat er niets wordt gedeeld tussen processen in het doorgeven van berichten, is wederzijdse uitsluiting geen controle vereiste voor deze vorm van samenwerking. Echter zijn de problemen van deadlock en uithongering nog steeds aanwezig. Als voorbeeld van deadlock, kunnen twee processen geblokkeerd worden, doordat ze elk moeten wachten op een communicatie van de ander. Als voorbeeld van starvation, beschouwen we drie processen P1, P2 en P3, die het volgende gedrag vertonen. P1 probeert herhaaldelijk te communiceren met ofwel P2 of P3, en P2 en P3 proberen beide te communiceren met P1. Een volgorde zou kunnen ontstaan waarin P1 en P2 herhaaldelijk informatie uitwisselen, terwijl P3 geblokkeerd is, wachtend op een communicatie van P1. Er is geen deadlock, omdat P1 actief blijft, maar P3 wordt uitgehongerd.

    5.1.5. Vereisten voor wederzijdse uitsluiting

    Iedere voorziening of mogelijkheid om wederzijdse uitsluiting te voorzien zou aan de volgende voorwaarden moeten voldoen:

    1. Wederzijdse uitsluiting moet worden afgedwongen: Tussen alle processen dat kritieke secties bevatten voor dezelfde bron of gedeeld object, is enkel één proces per keer is toegestaan in zijn kritieke sectie.
    2. Een proces dat stil staat in zijn niet-kritieke sectie moet dat op een dergelijke manier doen zonder dat er interferentie is met andere processen.
    3. Het mag voor een proces niet mogelijk zijn om toegang te krijgen tot een kritische sectie om onbeperkt uitgesteld te zijn: geen deadlock of starvation.
    4. Als er geen proces in zijn kritieke sectie zit, moet eender welk proces dat een ingang tot zijn kritieke sectie aanvraagt toegestaan worden om zonder vertraging binnen te gaan.
    5. Geen aannames worden gemaakt over relatieve processorsnelheden of het aantal processoren.
    6. Een proces blijft enkel voor een begrensde tijd in zijn kritieke sectie.

    Er zijn een aantal manier waarmee aan de vereisten voor wederzijdse uitsluiting kan worden voldaan. Een manier is om de verantwoordelijkheid bij die processen te laten die gelijktijdig vertraging wensen te worden. Processen, of het nu systeem programma's of applicatieprogramma’s zijn, zouden vereist moeten zijn om met elkaar samen te werken om wederzijdse uitsluiting af te dwingen. Dit zonder ondersteuning van de programmeertaal of besturingssysteem. We kunnen hiernaar refereren als zijnde de software benadering. Alhoewel deze aanpak vatbaar is voor hoge verwerkingsoverhead en fouten, is het handig om een dergelijke aanpak te onderzoeken om beter inzicht te krijgen in de complexiteit van gelijktijdige verwerking. Een tweede aanpak heeft betrekking met het gebruik van speciale machine instructies. Deze hebben als voordeel dat de overhead verminderd, maar desalniettemin zullen we laten zien dat deze manier niet de voorkeur geniet; deze wordt behandeld in sectie 5.2. De derde manier is om enig niveau van ondersteuning binnen het besturingssysteem of een programmeertaal te bieden. Drie van de meest belangrijke manieren van aanpak zullen onderzocht worden in secties 5.3 tot 5.5.

    5.2. Wederzijdse uitsluiting: hardware ondersteuning

    In deze sectie zullen we naar verschillende interessante hardware benaderingen kijken van wederzijdse uitsluiting.

    5.2.1. Uitschakelen van interrupts

    In een Uniprocessorsysteem kunnen gelijktijdige processen geen overlappende uitvoering hebben; ze kunnen enkel tussengevoegd worden. Verder zal een proces verder gaan met uitvoeren totdat het een besturingssysteem service aanroept of totdat het onderbroken wordt. Om wederzijdse uitsluiting te garanderen is het voldoende om te voorkomen dat een proces onderbroken kan worden. Deze mogelijkheid kan door het besturingssysteem voorzien worden door middel van eenvoudige richtlijnen die door het besturingssysteem zijn bepaald voor het in- en uitschakelen van onderbrekingen (interrupts). Dan kan een proces op de volgende manier wederzijdse uitsluiting afdwingen (vergelijk figuur 5.1):

    While (true) {
    /* disable interrupts */;
    /* critical section */;
    /* enable interrupts */;
    /* remainder */;
    }

    Omdat de kritieke sectie niet onderbroken kan worden is wederzijdse uitsluiting gegarandeerd. De efficiëntie van uitvoering kan merkbaar achteruitgaan, omdat de processor beperkt is in de mogelijkheid om processen tussen te voegen (interleaving). Een ander probleem is dat deze manier niet werkt in een Multiprocessor omgeving. Als de computer meer dan een processor bevat dan is het mogelijk (en kenmerkend) dat er meer dan een proces tegelijk in uitvoering is. In dit geval zal het uitschakelen van interrupts de wederzijdse uitsluiting niet kunnen garanderen.

    5.2.2. Speciale machine instructies

    In een Multiprocessor configuratie kunnen verschillende processoren toegang hebben tot een algemeen hoofdgeheugen. In dit geval is er gaan master/slave relatie; sterker nog, de processoren gedragen zich onafhankelijk in een peer relatie. Er is geen interrupt mechanisme tussen de processoren waarop wederzijdse uitsluiting gebaseerd kan worden.

    Op hardware niveau, zoals vermeld was, toegang tot een geheugenlocatie sluit iedere andere toegang uit tot die locatie. Met dit als basis hebben processor ontwerpers verschillende machine instructies voorgesteld die twee acties atomair2 kunnen uitvoeren zoals lezen en schrijven of lezen en testen van een enkele geheugenlocatie binnen één fetch instructiecyclus. Tijdens het uitvoeren van de instructie, is voor iedere instructie de toegang geblokkeerd welke refereert naar die geheugenlocatie.

    2 De term atomair betekend dat de instructie behandeld wordt als een enkele stap die niet onderbroken kan worden.

    1.2.2.1. Vergelijk&Verwissel instructie

    De vergelijk&verwissel instructie, ook wel een vergelijk en uitwisselingsinstructie genoemd, kan als volgt worden omschreven:0

    int compare_and_swap (int *word, int testval, int newval)
    {
    int oldval;
    oldval = *word
    if (oldval == testval) *word = newval;
    return oldval;
    }

    De versie van de instructie controleert een geheugenlocatie (*wordt) tegen een testwaarde (testval). Als de huidige geheugenlocatiewaarde testval is, dan zal het vervangen worden met newval; anders blijft het ongewijzigd. De oude geheugenwaarde wordt altijd teruggegeven; de geheugenlocatie wordt bijgewerkt als de teruggegeven waarde dezelfde is als de test waarde. Deze atomaire instructie heeft daarom twee delen: Een vergelijking wordt gemaakt tussen een geheugenwaarde en een testwaarde; als beide waarden dezelfde zijn, zal een verwisseling plaatsvinden. De volledige vergelijk&verwissel functie wordt atomair uitgevoerd - dat wil zeggen dat het niet vatbaar is voor onderbreking.

    Een andere versie van deze functie retourneert een Booleaanse waarde: waar als de verwisseling heeft plaatsgevonden; onwaar anderzijds.  Een of andere versie van deze instructie is op bijna alle processorfamilies beschikbaar (x86, Ia64, sparc, IBM z series, etc.), en de meeste besturingssystemen gebruiken deze instructie om de gelijktijdigheid te ondersteunen.

    Figuur 5.2a toont een wederzijds uitsluitingsprotocol dat gebaseerd is op het gebruik van deze instructie. Een gedeelde variabele bolt is geinitialiseerd op 0. Het enige proces dat de kritieke sectie mag binnengaan is diegene die bolt is gelijk aan 0 vindt. Alle andere processen die proberen de kritieke sectie binnen te gaan naar de busy waiting mode. De term busy waiting of spin waiting refereert naar een techniek waarin een proces niets kan doen totdat de toestemming krijgt om de kritische sectie binnen te gaan, maar verder gaat met uitvoeren van een instructie of set van instructies die de desbetreffende variabele testen om toegang te verschaffen. Als een proces de kritieke sectie verlaat zet het waarde van bolt opnieuw op 0; op dit punt kan enkel alleen een van de wachtende processen toegang krijgen tot zijn kritieke sectie. De keuze van proces hangt af van welk proces voorvalt om de volgende compare&execute instructie uit te voeren.

    5.2.2.2. Uitwisseling instructie

    De uitwisselingsinstructie kan als volgt worden gedefinieerd:

    void exchange (int *register, int *memory)
    {
    int temp;
    temp = *memory
    *memory = *register
    *register = temp
    }

    De instructie wisselt de inhoud van een register met dat van een geheugenlocatie. Zowel de Intel IA-32 architectuur als de IA-64 architectuur (Itanium) bevatten een XCHG-instructie.

    Figuur 5.2b laat en wederzijdse uitsluitingsprotocol zien die gebaseerd is op een uitwisselingsinstructie. Een gedeelde variabele bolt is geïnitialiseerd op 0. Ieder proces gebruikt een lokale variabele key die geïnitialiseerd is op 0. Het sluit alle processen uit van de kritieke sectie door de waarde van bolt op 0 te zetten. Als een proces zijn kritieke sectie verlaat, zal het de waarde van bolt terugzetten op 0, zodat een ander proces toegestaan wordt zijn kritieke sectie binnen te gaan.

    1.2.2.3. Eigenschappen van de machine-instructie benadering

    Het gebruik van een speciale machine instructie om wederzijdse uitsluiting af te dwingen haat een aantal voordelen:

  • Het is toepasbaar oneindig veel processen op zowel een enkele processor of meerdere processoren die geheugen delen.
  • Het is eenvoudig en daarom makkelijk te controleren.
  • Het kan gebruikt worden om meerdere kritieke secties te ondersteunen; iedere kritieke sectie kan gedefinieerd worden door zijn eigen variabele.
  • Er zijn enkele nadelen:

    Busy waiting wordt gebruikt: Terwijl een proces op toegang tot een kritieke sectie aan het wachten is zal het verder gaan met het gebruiken van processortijd.

    Uitsterving is mogelijk: Als een proces een kritieke sectie verlaat en meer dan één proces aan het wachten is, dan is de selectie van een wachtend proces arbitrair. Een proces kan dus voor onbepaalde tijd toegang geweigerd worden.

    Deadlock is mogelijk: Beschouw het volgende scenario op een Single-processorsysteem. Proces P1 voert de speciale instructie uit (bv. compare&swap, exchange) en gaat zijn kritieke sectie binnen. P1 wordt dan onderbroken om dan P2 aan de processor te geven, welk een hogere prioriteit heeft. Als P2 dezelfde bron als P1 probeert te benaderen zal het de toegang ontzegd worden op basis van het wederzijds uitsluitingsprotocol. Dus zal het in de busy waiting lus terechtkomen. Hoe dan ook, P1 zal nooit uitgezonden worden omdat het een lagere prioriteit heeft dan een andere klaarstaand proces P2.

    Door zowel de minpunten van software als hardware oplossingen moet we verder zoeken naar andere mechanismen.

    5.3. Semaforen

    We gaan nu verder met besturingssysteem en programmeertaalmechanismen die worden gebruikt om gelijktijdigheid te voorzien. Tabel 5.3 somt de mechanismen op in algemeen gebruik. In deze sectie beginnen we met semaforen. De volgende twee secties gaan over het monitoren en het doorgeven van berichten. De andere mechanismen in tabel 5.3 worden samen met specifieke besturingssysteem voorbeelden in hoofdstukken 6 en 13 behandeld.

    De eerste belangrijke vooruitgang om te gaan met de problemen van gelijktijdige processen kwam in 1965 met Dijstra's verhandeling. Dijkstra was betrokken met het ontwerp van een besturingssysteem als een collectie van sequentieel samenwerkende processen en met de ontwikkeling van efficiënte en betrouwbare mechanismen om samenwerking te ondersteunen. Deze mechanismen kunnen kant en klaar door de gebruikersprocessen worden gebruikt als de processor en het besturingssysteem deze mechanismen beschikbaar stellen.

    Het fundamenteel principe is: Twee of meer processen kunnen samenwerken door middel van eenvoudige signalen, zodat een proces geforceerd kan worden om op een specifieke plaats te stoppen totdat een bepaald signaal ontvangen wordt. Eender welk complexe vereiste voor coördinatie kan worden voldaan door het gebruik van bijbehorende signalen. Voor de signalering worden speciale variabelen gebruikt, semaforen genaamd. Om een signaal via semafoor s te verzenden, voert een proces het primitieve semSignal(s) uit. Om een signaal via semafoor s te ontvangen, voert een proces het primitieve semWait(s) uit; als het bijbehorend signaal nog niet is verzonden, zal het proces onderbroken worden totdat verzending plaatsvindt.

    Om het gewenst effect te kunnen bereiken, kunnen we de semafoor als een variabele zien die een integer waarde bevat waarop enkel drie operaties zijn gedefinieerd:

  • Een semafoor kan worden geïnitialiseerd tot een niet-negatieve integer waarde.
  • De semWait operatie verminderd de semafoor waarde. Als de waarde negatief wordt dan zal het proces dat semWait uitvoert geblokkeerd worden. Anders zal het proces verder gaan met uitvoeren.
  • De semSignal operatie vermeerderd de semafoorwaarde. Als de resulterende waarde kleiner of gelijk is aan nul, dan zal een proces die geblokkeerd is door een semWait operatie, gedeblokkeerd worden.
  • Buiten deze drie operaties is er geen manier om semaforen te onderzoeken of te manipuleren.

    We zullen deze operaties als volgt uitleggen. Om te beginnen, heeft de semafoor een nul-waarde of een positieve waarde. Als de waarde positief is, is de waarde gelijk aan het aantal processen dat een wacht kan uitvaardigen en onmiddellijk verder kan gaan met uitvoeren. Als de waarde nul is, zowel door initialisatie of omdat het aantal processen gelijk is aan de initiële semafoor waarde die een wacht hebben uitgevaardigd. Iedere volgende wacht brengt de semafoor waarde verder in het negatieve. De negatieve waarde komt overeen met het aantal processen die aan het wachten zijn om gedeblokkeerd te worden. Ieder signaal deblokkeert een van de wachtende processen als de semafoor waarde negatief is.

    [DOWN08] wijst op drie interessante gevolgen van de semafoor definitie:

  • In het algemeen is er geen manier om te weten voordat een proces een semafoor verminderd of wel of niet zal blokkeren.
  • Nadat een proces een semafoor vermeerderd, en een ander proces geactiveerd wordt, voeren beide processen gelijktijdig uit. Er is geen manier om te weten welk proces, als beide, onmiddellijk op een Uniprocessor verder gaan.
  • Als je een semafoor signaleert, moet je niet noodzakelijk weten of een ander proces aan het wachten is, zodat het aantal niet-geblokkeerde processen nul of één kan zijn.
  • Figuur 5.3 wijst op een meer formele definitie van de primitieven van semaforen. De semWait en semSignal primitieven zijn geacht atomair te zijn. Een meer beperkte versie, gekend als de binaire semafoor, is gedefinieerd in figuur 5.4.

    Een binaire semafoor kan enkel de waarden 0 en 1 aannemen en kan gedefinieerd worden door de volgende drie operaties:

    1. Een binaire semafoor kan geïnitialiseerd worden naar 0 of 1.
    2. De semWaitB operatie controleert de semafoor waarde. Als de waarde 0 is, dan is het proces dat semWaitB uitvoert geblokkeerd. Als de waarde één is, dan wordt de waarde veranderd naar nul en zal het proces verder gaan met uitvoeren.
    3. De semWaitB operatie controleert om te zien of processen op dit semafoor geblokkeerd zijn (semafoor waarde gelijk aan 0). Indien dit zo is dan zal een proces dat geblokkeerd is door een semWaitB operatie gedeblokkeerd worden. Als er geen processen geblokkeerd zijn, dan zal de waarde van de semafoor op één gezet worden.

    In principe zou het gemakkelijker moeten zijn om de binaire semafoor te implementeren en het kan aangetoond worden dat het dezelfde expressieve kracht heeft als de algemene semafoor (zie probleem 5.16).

    Om de verschillen tussen de twee typen semaforen te tonen wordt de niet-binaire semafoor vaak gerefereerd als ofwel een tellende semafoor ofwel een algemene semafoor.

    Een concept gerelateerd tot de binaire semafoor is de mutex. Een hoofdzakelijk verschil tussen de twee is dat het proces dat de mutex vergrendeld (zet de waarde op 0), diegene moet zijn om deze te ontgrendelen (zet de waarde op 1). In tegenstelling is het mogelijk voor een proces om de binaire semafoor te vergrendelen en voor een andere om deze te ontgrendelen.

    Voor zowel tellende semaforen als binaire semaforen wordt er een wachtrij gebruikt om processen op wacht te zetten wachtend op de semafoor. De vraag komt op in welke volgorde de processen uit de wachtrij verwijderd moeten worden. De meest eerlijke aanpak is first-in-first-out (FIFO): Het proces dat het langst geblokkeerd is wordt als eerste vrijgegeven van de wachtrij; een semafoor die op deze definitie gebaseerd wordt een sterke semafoor genoemd.

    Een semafoor dat de volgorde niet specifieert waarin de processen worden verwijderd wordt een zwakke semafoor genoemd. Figuur 5.5 is een voorbeeld van de werking van een sterke semafoor. De processen A, B en C hangen of van proces D. Initieel (1), A is uitvoerende; B, C en D staan klaar; en de semafoorteller staat op 1, dat aangeeft dat een van D's resultaten beschikbaar is. Als A een semWait instructie uitgeeft op semafoor s, dan zal de semafoor verminderen naar 0 en A kan verder gaan met uitvoeren; vervolgens zal het zich vervoegen met de wachtrij. Dan zal B gaan uitvoeren (2), eventueel geeft het een semWait instructie uit en is het geblokkeerd, wat toestaat dat D om uitgevoerd te kunnen worden (3). Als D een nieuw resultaat voltooid, geeft he teen semWait signaal uit, wat B toelaat naar de klaarstaande wachtrij (4) te gaan. D voegt zich terug bij de klaarstaande wachtrij en C begint met het uitvoeren (5) maar is geblokkeerd als het een semWait instructie uitgeeft. Gelijkaardig, A en B voeren uit en zijn geblokkeerd op de semafoor, wat toelaat D verder te gaan met uitvoering (6). Als D een resultaat heeft, geeft het een semSignal uit, welke C naar de klaarstaande wachtrij verplaatst. Latere cyclussen van D zullen A en B loslaten van de Blocked toestand.

    Voor het wederzijds uitsluitingsalgoritme behandeld in de volgende subsectie en geïllustreerd in figuur 5.6, garanderen sterke semaforen het uitblijven van uitsterving waar zwakke semaforen dit niet hebben. We zullen aannemen dat sterke semaforen gemakkelijker zijn, omdat deze vorm typisch wordt gebruikt in besturingssystemen.

    5.3.1. Wederzijdse uitsluiting

    Figuur 5.6 laat een duidelijke oplossing zien het wederzijds uitsluitingsprobleem dat gebruikmaakt van een semafoor s (vergelijk figuur 5.1). Beschouw n processen, geïdentificeerd in de array P(i), waarvan ze allemaal dezelfde bron willen benaderen. Ieder proces heeft een kritieke sectie die gebruikt wordt om de bron te benaderen. In ieder proces wordt een semWait(s) net voor de kritieke sectie uitgevoerd. Als de waarde van s negatief wordt, dan wordt het proces geblokkeerd. Als de waarde 1 is, dan zal het worden verminderd tot 0 en zal het proces onmiddellijk zijn kritieke sectie binnengaan, omdat s niet langer positief is, geen ander proces zal mogelijk zijn de kritieke sectie binnen te gaan.

    De semafoor is geïnitialiseerd op 1. Het eerste proces dat een semWait uitvoert zal onmiddellijk de kritieke sectie binnen kunnen gaan, door de waarde van s op 0 te zetten. Ieder ander proces die de kritieke sectie probeert binnen te gaan zal het bezet vinden en zal worden geblokkeerd, door de waarde van s op -1 te zetten. Eender welk proces de toegang probeert te zoeken zal ervoor zorgen dat de s verder zal verminderen. Als een proces dat oorspronkelijk zijn kritieke sectie verlaat, s zal worden vermeerderd en een van de geblokkeerde processen (als er één is) zal van de tot die semafoor behorende wachtrij van geblokkeerde processen worden verwijderd en in de Ready toestand worden gezet. Zodra het vervolgens door het besturingssysteem wordt gepland mag het zijn kritieke sectie binnengaan.

    Figuur 5.7 laat een mogelijke sequentie zien voor drie processen die gebruik maken van wederzijdse uitsluitingsdiscipline van figuur 5.6. In dit voorbeeld benaderen drie processen (A, B, C) een gedeelde bron die beveiligd zijn door semafoor lock. Proces A voert een semWait(lock) uit; omdat de semafoor een waarde van 1 heeft op het moment van de semWait operatie. Het kan onmiddellijk zijn kritieke sectie binnengaan en de semafoor neemt de waarde 0 aan. Terwijl A is zijn kritieke sectie zit, voeren zowel B als C een semWait operatie uit en zijn geblokkeerd in afwachting van de beschikbaarheid van de semafoor. Als A zijn kritieke sectie verlaat en een semSignaal(lock) uitvoert, kan B, welk het eerste proces in de wachtrij was, nu zijn kritieke sectie binnengaan.

    Het programma van figuur 5.6 kan met de vereiste even goed omgaan als er meer dan één proces toegelaten zijn in zijn kritieke sectie. Aan deze vereiste kan eenvoudigweg voldaan worden door de semafoor te initialiseren met de gespecifieerde waarde. Op ieder moment kan de waarde van s.count als volgt geïnterpreteerd worden:

  • s.count 0: s.count is het aantal processen dat zonder vertraging semWait(s) kan uitvoeren (als er in de tussentijd geen semSignal(s) is uitgevoerd). Zulke situaties laten semaforen toe om synchronisatie als ook wederzijdse uitsluiting te ondersteunen.
  • s.count < 0 de magnitude van s.count is het aantal processen dat onderbroken is in s.queue.
  • 5.3.2. Het producent/consument probleem

    We gaan nu een van de meest algemene problemen onderzoeken dat men tegenkomt in gelijktijdige verwerking: het producent/consument probleem. De algemene bewering is: Er zijn een of meer producenten die een of ander type van data (records, karakters) genereren en deze in een buffer plaatsen. Er is een enkele consument die deze zaken een voor een uit de buffer neemt. Het systeem moet beperkt worden om een overlapping van de buffer operaties te voorkomen. Dat wil zeggen, alleen één agent (producent of consument) mag de buffer op een bepaald benaderen. Het probleem is om er zeker van te zijn dat de producent geen data aan de buffer probeert toe te voegen als deze vol is en dat de consument geen data probeert te verwijderen van een lege buffer. We zullen kijken naar een aantal oplossingen voor dit probleem om de kracht en valkuilen van semaforen aan te tonen.

    Om te beginnen laat ons aannemen dat de buffer onbeperkt is een lineaire array van elementen bevat. In abstracte termen, kunnen we de producent en consument problemen als volgt definiëren:

    producer:

    while (true) {
       /* produce item v */;
       b[in] = v;
       in++;
    }

     

    consumer:

    while (true) {
       while (in <= out)
          /* do nothing */;
       w = b[out];
       out++;
       /* consume item w */;
    }

    Figuur 5.8 illustreert de structuur van buffer b. De producent kan items genereren en deze op zijn eigen ritme opslaan in de buffer. Iedere keer wordt een index (in) in de buffer vermeerderd. De consument gaat in een gelijkaardige manier verder maar moet er zeker van zijn dat het niet van een lege buffer leest. Daarom moet de consument voordat het verder gaat er zeker van zijn dat het verder is gegaan (in> out).

    Laat ons proberen dit systeem te implementeren met het gebruik van binaire semaforen. Figuur 5.9 is een eerste poging. In plaats van om te gaan met de indices in en out, kunnen we eenvoudigweg het aantal items in de buffer bijhouden door gebruik te maken van de integer variabele n (= in - out). De semafoor s wordt gebruikt om wederzijdse uitsluiting af te dwingen; de semafoor delay wordt gebruikt om de consument tot semWait te dwingen als de buffer leeg is.

    .

    Deze oplossing lijkt nogal rechttoe rechtaan. De producent is vrij om op ieder moment toevoegingen te doen aan de buffer. Voor het toevoegen voert het een semWaitB(s) uit en semSignalB(s) nadien om te voorkomen dat de consument of een of andere producent de buffer gedurende de operatie benaderd. Terwijl het in de kritieke sectie zit, vermeerderd de producent de waarde van n. Als n = 1, dan was de buffer juist leeg op het moment van deze toevoeging, zodat de producent een semSignalB(delay) uitvoert om de consument een melding te geven van dit feit. De consument begint met wachten op het eerste item dat geproduceerd moet worden, gebruikmakend van semWaitB(delay). Dan neemt het een item en verminderd het n in zijn kritieke sectie. Als de producent in staat is om voor de consument te blijven (een algemene situatie), dan zal de consument zelden geblokkeerd zijn door de semafoor delay, omdat n normaal positief is. Daardoor zullen zowel producent en consument vlot kunnen uitvoeren.

    Er is echter een onvolkomenheid in dit programma. Als de consument de buffer heeft uitgeput, dan moet het de semafoor delay opnieuw instellen, zodat het geforceerd wordt te moeten wachten totdat de producent meer items in de buffer heeft geplaatst. Dit is het doel van dit statement: if n == 0 semWaitB(delay). Beschouw het afgetekend scenario in tabel 5.4. Op lijn 14 faalt de consument op de semWaitB operatie uit te voeren. De consument heeft inderdaad de buffer uitgeput en n op 0 (regel 8) gezet, maar de producent heeft n verhoogd voordat de consument dit kan testen op regel 14. Het resultaat is een semSignalB dat niet overeenkomt met een voorgaande semWaitB. De waarde van -1 voor n in regel 20 betekend dat de consument een item van de buffer heeft geconsumeerd dat niet bestond. Het zal niet eenvoudig lukken om het voorwaardelijke statement naar de binnenkant van de kritieke sectie van de consument te verplaatsen, omdat dit tot een deadlock kan leiden (bv. na regel 8 van tabel 5.4).

    Een oplossing voor dit probleem is om een aanvullende variabele te introduceren, dat voor later gebruik, in de kritieke sectie van de consument gezet kan worden. Dit wordt getoond in figuur 5.10. Een zorgvuldige tracering van de logica zou je moeten overtuigen dat een deadlock niet langer meer kan voorkomen.

    Een enigszins schonere kan verkregen worden als algemene semaforen (ook tellende semaforen genaamd) worden gebruikt, zoals te zien is in figuur 5.11. De variabele n is nu een semafoor. Zijn waarde is gelijk aan het aantal items in de buffer. Veronderstel nu dat in het overbrengen van dit programma een fout wordt gemaakt en de operaties semSignal(s) en semSignal(n) met elkaar worden verwisseld. Dit zou vereisen dat de semSignal(n) operatie zonder onderbreking van de consument of andere producent uitgevoerd moet worden in de kritieke sectie van de producent. Zou dit het programma beïnvloeden? Nee, omdat in elk geval de consument sowieso moet wachten op beide semaforen voordat het verder kan gaan.

    Veronderstel nu dat de semWait(n) en semWait(s) operaties per ongeluk van volgorde zijn verwisseld. Dit zorgt voor een ernstige en fatale onvolkomenheid. Als de consument ooit zijn kritieke sectie binnengaat op het moment dat de buffer leeg is (n.count = 0), dan kan geen enkele producent iets aan de buffer toevoegen is zit systeem in een deadlock situatie. Dit een goed voorbeeld van de subtiliteit van semaforen en de moeilijkheid om correctie ontwerpen te maken.

    Laat ons uiteindelijk een nieuw en realistische beperking aan het producent/consument probleem toevoegen: namelijk, dat de buffer eindig is. De buffer wordt behandeld als een circulaire opslag (figuur 5.12), en aanwijzer waarden moeten modulo van de grootte van de buffer worden uitgedrukt. De volgende relaties gelden dan:

    De producent en consument functies kunnen als volgt uitgedrukt worden (variabele in en out worden geïnitialiseerd op 0 en n is de grootte van de buffer):

    producer:

    while (true) {
       /* produce item v */;
       while ((in + 1) % n == out)
          /* do nothing */;  
       b[in] = v;
       in = (in + 1) % n;
    }

    Consumer:

    while (true) {
       while (in == out)
          /* do nothing */;
       w = b[out];
       out = (out + 1) % n;
       /* consume item w */;
    }

    Figuur 5.13 laat een oplossing zien door het gebruik van algemene semaforen. De semafoor e is toegevoegd om het aantal lege plaatsen bij te houden.

    5.3.3. Implementatie van semaforen

    Zoals eerder was vermeld is het imperatief dat de semWait en semSignal operaties als atomaire primitieven kunnen worden geïmplementeerd. Een onmiskenbare manier is om ze in de hardware of firmware te implementeren. Bij gebreke hiervan worden er een aantal schema's voorgesteld. De essentie van het probleem is dat van wederzijdse uitsluiting: Alleen een proces tegelijk mag een semafoor manipuleren met ofwel een semWait of een semSignal operatie.

    Een ander alternatief is het gebruik van hardware ondersteunde schema's voor wederzijdse uitsluiting. Bijvoorbeeld, figuur 5.14a laat het gebruik van een compare&swap instructie zien. In deze implementatie is de semafoor opnieuw de structuur, zoals in figuur 5.3, maar nu bevat het een nieuwe integer component, s.flag. Weliswaar gaat dit gepaard met een of andere vorm van een busy wachten. Echter zijn de semWait en semSignal operaties relatief kort, zodat de hoeveelheid busy wachten minimaal is.

    Voor een Single-processorsysteem is het mogelijk om onderbrekingen te onderdrukken voor de duur van de semWait of semSignal operatie, zoals gesuggereerd in figuur 5.14b. Ook hier wil de relatief korte duur van deze operaties zeggen dat deze aanpak redelijk is.

    5.4. Monitors

    Semaforen bieden een primitieve maar toch krachtig en flexibel hulpmiddel om wederzijdse uitsluiting af te dwingen en om processen te coördineren. Echter zoals figuur 5.9 suggereert, kan het moeilijk zijn om een correct programma te maken met gebruik van semaforen. De moeilijkheid is dat semWait en semSignal operaties verspreid over het programma kunnen liggen en het niet gemakkelijk is om de algemene effecten van deze effecten te zien op de semaforen waarop ze betrekking hebben.

    De monitor is een constructie van een programmeertaal dat een gelijkwaardige constructie als dat van semaforen voorziet, en dat makkelijker te beheersen is. De monitor constructie is in een aantal programmeertalen verwerkt, zoals Concurrent Pascal, Pascal-Plus, Modula-2, Modula-3 en Java. Het is ook geïmplementeerd als een programmabibliotheek. Dit laat programmeurs toe op een object een monitor vergrendeling te zetten. In het algemeen iets zoals een gelinkte-lijst, je zou alle gelinkte-lijsten willen vergrendelen met één slot, of één slot voor iedere lijst te hebben, of om voor ieder element van iedere lijst een slot te hebben.

    5.4.1. Monitor met signaal

    Een monitor is een software module dat bestaat uit, een of meer procedures, een initialisatie sequentie en lokale data. De belangrijkste karakteristieken van een monitor zijn de volgende:

    1.       De lokale data variabelen zijn enkel toegankelijk door de procedures van de monitor en niet door eender welke externe procedure.

    2.       Een proces gaat de monitor binnen door een van zijn procedures aan te roepen.

    3.       Enkel een proces per keer kan in de monitor uitgevoerd worden; elk ander proces dat de monitor zal oproepen worden geblokkeerd, wachtend totdat de monitor beschikbaar is.

    De eerste twee karakteristieken zijn herkenbaar van objecten uit object-georiënteerde software. Inderdaad, een object-georiënteerd besturingssysteem of programmeertaal kan gemakkelijk een monitor als een object met speciale karakteristieken implementeren.

    Door de discipline af te dwingen van een proces per keer, is de monitor in staat een faciliteit van wederzijdse uitsluiting te voorzien. De data variabelen in de monitor kunnen enkel door een proces per keer benaderd worden. Een gedeelde datastructuur kan daarom beveiligd worden door het te plaatsen in een monitor. Als de data in een monitor een bron voorstelt, dan voorziet de monitor van een faciliteit van wederzijdse uitsluiting om die bron te benaderen.

    Voordat dit bruikbaar is voor gelijktijdige verwerking, moet de monitor synchronisatie hulpmiddelen bevatten. Veronderstel bijvoorbeeld dat een proces een monitor aanroept, en terwijl het in de monitor is, het geblokkeerd moet worden tot aan een of andere conditie wordt voldaan. Een faciliteit is nodig door welk het proces niet alleen geblokkeerd, maar ook de monitor loslaat, zodat een ander proces het binnen mag gaan. Nadien, als voldaan is aan de voorwaarde en de monitor opnieuw beschikbaar is, moet het proces voortgezet worden en toegestaan worden de monitor opnieuw binnen te gaan op het punt van onderbreking.

    Een monitor ondersteund synchronisatie door het gebruik van de conditie variabelen die zijn in de monitor zijn ingesloten en enkel toegankelijk zijn binnen de monitor. Conditie variabelen zijn een speciale data type in monitors, welke bestuurd worden door twee functies:

  • cwait(c): schort de uitvoering op van het oproepend proces op conditie c. De monitor is nu beschikbaar voor gebruik door een ander proces.
  • csignal(c): zet uitvoering verder van een of ander proces die geblokkeerd is na een cwait op dezelfde conditie. Als er meerdere gelijkaardige processen zijn, moet je er een uit kiezen; als er geen gelijkaardig proces is moet je nietsdoen.
  • Merk op dat monitor wait en signal operaties verschillend zijn van die voor de semafoor. Als een proces in een monitor signaleert en er geen wachtende taak is op de conditie variabele, dan is het signaal verloren.

    Figuur 5.15 illustreert de structuur van een monitor. Alhoewel een proces een monitor kan binnengaan door het aanroepen van een van zijn procedures, kunnen we denken dat als de monitor een enkel bewaakt ingangspunt heeft, zodat enkel een proces per keer in de monitor kan zitten. Andere processen die proberen de monitor binnen te gaan de wachtrij binnen van wachtende processen wachtend op de beschikbaarheid van de monitor. Eens een proces in de monitor zit, kan het zichzelf tijdelijk blokkeren op conditie x door een cwait(x) uit te geven; dan wordt het geplaatst in de wachtrij van processen die wachten om de monitor opnieuw binnen te gaan zodra de conditie veranderd., en verder gaat met uitvoering op het punt in het programma dat volgt op de cwait(x) oproep.

    Als een proces in de monitor dat in uitvoering is een verandering in de conditie variabele x detecteert, geeft het een signal(x) uit, welk de corresponderende conditie wachtrij alarmeert dat de conditie is veranderd.

    Als voorbeeld van het gebruik van een monitor, laat ons teruggaan naar het bounded-buffer producer/consumer probleem. Figuur 5.16 laat een oplossing zien door gebruikmaking van een monitor. De monitor module, bounded buffer, controleer de buffer die gebruikt wordt om de karakters op te slaan en op te halen. De monitor bevatten twee conditie variabelen (gedeclareerd met de constructie cond): notfull is true als er plaats is om op zijn minst een karakter toe te voegen aan de buffer, en notempty is true als er op zijn minst een karakter in de buffer zit.

    Een producent kan karakters aan de buffer toevoegen door middel van de procedure append die zich in de monitor bevindt; de producent heeft geen directe toegang tot de buffer. De conditie notfull wordt eerst door de procedure gecontroleerd om te bepalen of genoeg plaats is in de buffer. Indien er niet genoeg plaats is, dan wordt het proces dat de monitor uitvoert op die conditie geblokkeerd. Een ander proces (producent of consument) kan nu de monitor binnen gaan. Als de buffer nadien niet langer meer vol zit, mag het geblokkeerd proces van de wachtrij verwijderd worden, gereactiveerd worden en verder uitgevoerd worden. Na het plaatsen van karakter in de buffer signaleert het proces de notempty conditie. Een vergelijkbare beschrijving kan gemaakt worden voor de consument functie.

    Dit voorbeeld toont de scheiding aan van de verantwoordelijkheid met monitors in vergelijking tot die van semaforen. In het geval van monitors, dwingt de monitor constructie wederzijdse uitsluiting af: Het is niet mogelijk voor zowel een producent als een consument om gelijktijdig de buffer te benaderen. Echter moet de programmeur de geschikte cwait en csignal primitieven in de monitor plaatsen om te voorkomen dat processen items in een volle buffer proberen op te slaan of dat ze items proberen verwijderen uit een lege buffer. In het geval van semaforen, zijn zowel wederzijdse uitsluiting als synchronisatie de verantwoordelijkheid van de programmeur.

    Let op dat in figuur 5.16 een proces de monitor onmiddellijk verlaat nadat het de csignal functie heeft uitgevoerd. Als het csignal niet gebeurd op het eind van de procedure, dan, in Hoare's voorstel, geeft het proces een signaal is geblokkeerd uit om de monitor beschikbaar te maken en in de wachtrij te plaatsen tot de monitor vrij is. Een mogelijkheid op dit punt zou zijn om het geblokkeerd proces in ingangswachtrij te plaatsen, zodat het zou wedijveren voor toegang met andere processen die niet de monitor zijn binnengekomen. Echter omdat een proces geblokkeerd op een csignal functie heeft het al deels zijn taak in de monitor uitgevoerd. Het is logisch om dit proces voorrang te verlenen boven nieuw binnenkomende processen door een nieuwe dringende wachtrij op te zetten (figuur 5.15). Een taal dat monitors gebruikt, Concurrent Pascal, vereist dat csignal alleen als laatste operatie verschijnt die uitgevoerd moet worden door een monitor procedure.

    Als er geen processen aan het wachten zijn op conditie x, dan heeft de executie van csignal(x) geen effect.

    Zoals met semaforen is het mogelijk om fouten te maken in de synchronisatie functie van monitors. Bijvoorbeeld, als ofwel de csignal functies in de boundedbuffer weggelaten zijn, dan zullen de processen die de bijbehorende conditie wachtrij willen binnengaan permanent opgehangen. Het voordeel van monitors boven dat van semaforen is dat alle synchronisatie functies aan de monitor toebehoren. Daardoor is het makkelijker om te controleren dat de synchronisatie correct is verlopen en om fouten te detecteren. Verder, eens als een monitor correct is geprogrammeerd, dan is de toegang tot de beveiligde bron correct vanuit alle processen. In tegenstelling tot semaforen is brontoegang alleen correct voor de processen dat de bron benaderen correct geprogrammeerd zijn.

    5.4.2. Alternatief model van monitoren met kennisgeving en uitzending

    Hoare's definitie van monitors vereist dat er op zijn minst een proces in de conditie wachtrij zit; een proces uit die wachtrij kan onmiddellijk worden uitgevoerd als een ander proces een csignal voor die conditie uitgeeft. Het proces dat het csignal uitgeeft ofwel de monitor onmiddellijk verlaten of geblokkeerd worden op de monitor.

    Er zijn twee keerzijden met deze methode:

    1. Als het proces dat de csignal uitgeeft niet gedaan is met de monitor, dan zullen twee additionele proceswisselingen vereist zijn: een om dit proces te blokkeren en een ander om het weer verder te zetten als de monitor weer beschikbaar komt.
    2. Procesplanning dat geassocieerd is met een signaal moet perfect betrouwbaar zijn. Als een csignal uitgegeven wordt, dan moet een proces van de corresponderen conditiewachtrij onmiddellijk geactiveerd worden en de planner moet er zeker van zijn dat geen enkel ander proces de monitor binnengaat voor activatie. Anders kan de conditie waaronder het proces was geactiveerd veranderen. Bijvoorbeeld in figuur 5.16, als een csignal(notempty) is uitgegeven, moet een proces van de notempty wachtrij worden geactiveerd voordat een nieuwe consument de monitor binnengaat. Een ander voorbeeld: een producent proces mag een karakter aan een lege buffer toevoegen en dan falen voor de signalering: ieder proces in de notempty wachtrij zou permanent blijven vastzitten.

    In de Hoare monitor bevat ieder signaal een niveau 1 conditie alsook het impliciete bericht, "I have freed enough bytes for your particular allocate call to work now.:. Impliciet bevat het signaal bevat dus het niveau 2 conditie. Als de programmeur nadien de definitie van het niveau 2 conditie aanpast, is het nodig om alle signalerende processen te herprogrammeren. Als de programmeur de aannames veranderd gemaakt door elk specifiek wachtend proces (bv. wachtend op een licht verschillend niveau 2 invariant), kan het nodig zijn alle signalerende processen te herprogrammeren. Dit is niet modulair en zorgt waarschijnlijk voor synchronisatie fouten (bv. wakker worden door vergissing) als de code wordt veranderd. De programmeur moet onthouden dat hij alle procedures in de monitor moet veranderen, een uitzending verzekert het niveau 1 conditie en bevat een hint dat niveau 2 kan bevatten; ieder proces zou het niveau 2 conditie zelf moeten controleren. Als een verandering wordt gemaakt in het niveau 2 conditie in ofwel een wachter of een signaleerder, dan is er geen mogelijkheid van verkeerd wakker worden, omdat iedere procedure zijn eigen niveau 2 conditie controleert. Daarom kan binnen iedere procedure het niveau 2 conditie verscholen worden. Met de Hoare monitor, het niveau 2 conditie moet meegegeven worden van de wachter in de code van ieder signalerend proces, welk de data abstractie en modulaire interprocedurale principes schendt.

    5.5. Uitwisselen van berichten

    Als processen op elkaar inwerken moeten aan twee fundamentele vereisten worden voldaan: synchronisatie en communicatie. Het is nodig om processen te synchroniseren om wederzijdse uitsluiting af te dwingen: het kan nodig zijn dat samenwerkende processen met elkaar informatie uitwisselen. Een aanpak van beide functies is het doorgeven van berichten. Het doorgeven van berichten heeft het voordeel dat het zich leent om geïmplementeerd te worden in gedistribueerde systemen, als zowel gedeeld-geheugen Multiprocessor en Uni-processorsystemen.

    Bericht uitwisselingssystemen zijn er in verschillende soorten. In deze sectie behandelen we een algemene introductie dat over de eigenschappen gaat die typisch in zulke systemen worden gevonden. De eigenlijke functie van het uitwisselen van berichten wordt gewoonlijk voorzien in de vorm van een primitieven paar:

    send (destination, message)

    receive (source, message)

    Dit is een minimum benodigde set van operaties benodigd voor processen die zich bezighouden met het doorgeven van berichten. Een proces stuurt informatie in de vorm van een bericht naar een ander proces die aangewezen is door een bestemming. Een proces ontvangt informatie door de receive primitieve uit te voeren, dat de bron en het bericht aangeeft.

    Een aantal ontwerpkwesties met betrekking tot berichtuitwisselingssystemen worden opgesomd in tabel 5.5, en onderzocht in het resterende van deze sectie.

    5.5.1. Synchronisatie

    De communicatie van een bericht tussen twee processen houdt een of ander niveau van synchronisatie tussen beiden in: De ontvanger kan geen bericht ontvangen totdat het door een ander proces is verstuurd. Bovendien moeten we opgeven wat met een proces gebeurd nadat het een send of receive primitieve uitgeeft.

    Beschouw de send primitieve als eerst. Als een send primitieve in een proces wordt uitgevoerd dan zijn er twee mogelijkheden: Of het zendend proces is geblokkeerd totdat het bericht is ontvangen, of niet. Gelijkaardig als een proces een receive primitieve uitgeeft zijn er twee mogelijkheden:

    1. Als voordien een bericht was verstuurd, het bericht is ontvangen en uitvoering gaat verder.
    2. Als er geen wachtend proces is, dan zal ofwel (a) het proces geblokkeerd zijn totdat een bericht aankomt, of (b) het proces zal verder gaan met uitvoeren en de poging om te ontvangen opgeven.

    Dus zowel de zender als ontvanger blokkerend of niet-blokkerend zijn. Drie gangbare systemen zijn gebruikelijk, alhoewel een specifiek systeem normaal gesproken er maar een of twee heeft geïmplementeerd:

    Blokkerende zender, blokkerende ontvanger: Zowel zender als ontvanger zijn geblokkeerd, totdat het bericht is afgeleverd; dit wordt soms een rendez-vous genoemd. Deze combinatie laat tussen processen een strakke synchronisatie toe.

    Niet-blokkerende zender, blokkerende ontvanger: Alhoewel de zender verder mag gaan, is de ontvanger geblokkeerd, totdat het gevraagde bericht aankomt. Dit is waarschijnlijk de meest gangbare combinatie. Het laat toe dat een proces zo snel als mogelijk een of meer berichten naar een variëteit van kan zenden kan zenden. Een proces dat een bericht moet ontvangen voordat het bruikbaar werk kan doen moet worden geblokkeerd totdat een dergelijk bericht aankomt. Een voorbeeld is een serverproces (=ontvanger) die een dienst of bron aanlevert aan een ander proces.

    Niet-blokkerende zender, niet-blokkerende ontvanger: Het is niet vereist dat een van beide partijen moet wachten.

    De niet-blokkerende send is natuurlijker voor vele gelijktijdige programmeertaken. Bijvoorbeeld, als het wordt gebruikt om een uitvoer bewerking aan te vragen, zoals afdrukken, laat dat het aanvragend proces toe om de aanvraag uit te geven in de vorm van een bericht en dan gaat dan verder. Een mogelijk gevaar van de niet-blokkerende send is dat een fout tot een situatie kan leiden waarin een proces herhaaldelijk berichten aanmaakt. Omdat er geen blokkering is om het proces te beheersen, kunnen deze berichten de systeembronnen verbruiken, zoals processortijd een buffer-ruimte, tot de beschadiging van andere processen en het besturingssysteem. Ook zal de niet-blokkerende send een behoorlijke last op de programmeur zetten om te bepalen of een bericht is ontvangen: processen moeten gebruik maken van antwoordberichten om de ontvangst van een bericht te bevestigen.

    Voor de receive primitieve lijkt de blokkerende versie voor vele gelijktijdige taken natuurlijker. In het algemeen kan een proces dat een bericht aanvraagt pas verder gaan als het de verwachte informatie heeft ontvangen. Echter, als een bericht verloren is gegaan, wat kan gebeuren in gedistribueerde systemen, of als een proces faalt voordat het kan anticiperen op een bericht, kan een proces onbeperkt geblokkeerd raken. Dit probleem kan opgelost worden door het gebruik van de niet-blokkerende receive. Het gevaar van deze aanpak is dat een bericht verzonden is nadat een proces de overeenkomstige receive heeft uitgevoerd, het bericht gaat dus verloren. Andere mogelijkheden zijn om processen toe te laten te testen of een bericht wachtende is voordat het een receive uitgeeft en een proces toe te laten meer dan een bron in de receive primitieve op te geven.  Deze laatste manier is handig als een proces aan het wachten is op berichten van meer dan een bron en verder kan gaan als een van deze berichten zijn ontvangen.

    5.5.2. Adressering

    Het is duidelijk dat er een manier nodig is om in de send primitieve op te geven welk proces het bericht moet ontvangen. De meeste implementaties laten toe een ontvangend proces om de bron van een bericht aan te geven die ontvangen moet worden.

    De verschillende schema's om processen in send en receive primitieven te specifiëren vallen in twee categorieën: directe adressering en indirecte adressering. Met directe adressering, bevat de send primitieve een specifieke identificatie van het doelproces. De receive primitieve kan op twee manieren worden afgehandeld. Een manier is om te vereisen dat het proces een zendend proces uitdrukkelijk aanwijst. Het proces moet van tevoren weten van welk proces een bericht wordt verwacht. Dit is dikwijls effectief voor gelijktijdige samenwerkende processen. In andere gevallen is het onmogelijk om bronprocessen hierop te laten anticiperen. Een voorbeeld is een printer-server proces, welk van ieder proces een aanvraag voor een afdruk zal accepteren. Voor zulke applicaties is impliciete adressering effectiever. In dit geval bevat de bron parameter van de receive primitieve dat geretourneerd wordt als de ontvangende operatie is uitgevoerd.

    Een andere algemene manier is indirecte adressering. In dit geval, worden berichten niet direct van zender naar ontvanger gezonden, maar naar een gedeelde datastructuur gezonden dat bestaat uit wachtrijen die tijdelijk de berichten kan bewaren. In het algemeen wordt er naar zulke wachtrijen als zijnde mailboxen. Dus om twee processen te laten communiceren, moet een proces een bericht sturen naar de juiste mailbox en het ander proces moet dit bericht ophalen uit de mailbox.

    De kracht van het gebruik van indirecte adressering is dat door de loskoppeling van zender en ontvanger, het toelaat voor grotere flexibiliteit is het gebruik van berichten. De relatie tussen zenders en ontvangers kunnen een-op-een, veel-op-één, één-op-veel, veel-op-veel zijn (figuur 5.18). Een één-op-éen relatie laat toe dat er twee processen een privécommunicatie link opgezet kan worden. Een veel-op-één relatie is handig voor cliënt/server interactie; een proces voorziet een service naar een aantal andere processen. In dit geval wordt naar een mailbox verwezen als een port. Een één-op-veel relatie laat een zender en meerdere ontvangers toe; het is handig voor applicaties waar een bericht of informatie uitgezonden moet worden naar een reeks processen. Een veel-op-veel relatie laat toe meerdere server processen toe om aan meerdere cliënten van gelijktijdige service te voorzien.

    De associatie tussen processen en mailboxen kan zowel statisch als dynamisch zijn. Poorten worden vaak statisch met een specifiek proces geassocieerd, dat wil zeggen, de poort wordt gecreëerd en permanent tot dat proces toegewezen. Gelijkaardig wordt ook een een-op-een relatie typisch statisch en permanent gedefinieerd. Als er meerdere zenders zijn kan de verbinding tussen zender naar een mailbox dynamisch gebeuren. Primitieven zoals connect en disconnect kunnen voor dit doel worden gebruikt.

    Een gerelateerde kwestie heeft te maken heeft met het eigendomsrecht van een mailbox. In het geval van een poort is dit normaal gesproken eigendom van en gecreëerd door het ontvangend proces. Wanneer een proces wordt vernietigd, wordt de poort ook vernietigd. Voor de algemene mailbox situatie, kan het besturingssysteem een create-mailbox service voorzien. Zulke mailboxen kunnen worden bekeken door zoals het eigendom is van het creërend proces, in welk geval ze samen met het proces beëindigen, of als geëigend door het besturingssysteem, in welk geval een expliciet commando nodig is om de mailbox te vernietigen.

    5.5.3. Bericht formaat

    Het formaat van het bericht hangt af van de objectieven van de berichtenfaciliteit en of de faciliteit loopt op een enkele computer of een gedistribueerd systeem. Voor sommige besturingssystemen geven ontwerpers de voorkeur aan korte, vaste-lengte berichten om verwerking en opslag overhead tot een minimum te beperken. Als een grote hoeveelheid data moet passeren, kan de data in een bestand worden gezet en het bericht zal dan verwijzen naar dat bestand. Een flexibelere methode is om berichten van flexibele lengte toe te laten.

    Figuur 5.19 laat een typisch berichtformaat zien voor besturingssystemen die variabele-lengte berichten ondersteunen. Het bericht is opgedeeld in twee delen: een header, welk de informatie van het bericht bevat en een body, welk de inhoud van het bericht bevat. De header kan de volgende informatie bevatten: een identificatie van de bron en beoogde bestemming van het bericht, een lengte veld en een type veld om zich te kunnen onderscheiden tussen verschillende soorten berichten. Er kan ook nog extra controle informatie zijn, zoals een pointer veld, zodat een gelinkte lijst van berichten kan worden aangemaakt; een sequentie nummer, om het aantal en volgorde van de doorgegeven berichten tussen bron en bestemming bij te houden; en een prioriteitsveld.

    5.5.4. Wachtrij discipline

    De eenvoudigste wachtrij discipline is first-in-first-out, maar dit kan niet voldoende zijn als er berichten zijn die belangrijker zijn dan andere. Een alternatief is om op basis van een berichttype of bestemming door de zender een bericht prioriteit toe te laten. Een ander alternatief is om de ontvanger toe te laten de berichtenwachtrij te inspecteren en te selecteren welk bericht het vervolgens wil ontvangen.

    5.5.5. Wederzijdse uitsluiting

    Figuur 5.20 laat een manier zien hoe het doorgeven van berichten kan worden gebruikt om wederzijdse uitsluiting af te dwingen (vergelijk figuren 5.1, 5.2 en 5.6). We nemen het gebruik aan van de blokkerende receive primitieve en de niet-blokkerende send primitieve. Een set van gelijktijdige processen delen een mailbox, box, welk door alle processen gebruikt kan worden om te zenden en te ontvangen. De mailbox wordt geïnitialiseerd om een enkel bericht zonder inhoud te bevatten. Een proces dat zijn kritieke sectie wenst binnen te gaan probeert eerst een bericht te ontvangen. Als de mailbox leeg is, dan wordt het proces geblokkeerd. Eens het proces het bericht heeft verkregen, voert het zijn kritieke sectie uit en plaatst het bericht terug in de mailbox. Het bericht functioneert dus als een token dat tussen de processen wordt doorgegeven.

    De voorgaande oplossing neemt aan dat als meer dan een proces de ontvangst operatie gelijktijdig uitvoert, dan:

  • Als er een bericht is, wordt het bezorgd een enkel een proces en de andere worden geblokkeerd, of
  • Als de wachtrij van berichten leeg is, zijn alle processen geblokkeerd, als er een bericht beschikbaar is, is er enkel een geblokkeerd proces geactiveerd en wordt het bericht gegeven.
  • Deze aannames zijn voor bijna alle berichtuitwisselingssystemen waar.

    Als voorbeeld op het gebruik van een berichtuitwisseling, is figuur 5.21 een oplossing op het bounded-buffer producent/consument probleem. Door het gebruiken van de kracht van de basis wederzijdse uitsluiting berichtuitwisseling, kan het probleem met een algoritmische structuur, vergelijkbaar met dat van figuur 5.13, worden opgelost. In de plaats daarvan heeft het programma van figuur 5.21 het voordeel van de mogelijk om berichten uit te wisselen om gebruikt te worden om data door te geven bovenop dat van signalen. Twee mailboxen worden gebruikt. Als de producent data genereert, wordt het naar de mailbox mayconsume gestuurd. Zo lang er op zijn minst een bericht in die mailbox zit, kan de consument verbruiken. Daarom doet mayconsume dienst als een buffer; de data in de buffer is als een wachtrij van berichten georganiseerd. De 'grootte' van de buffer wordt bepaald daar de globale variabele capacity. Initieel is de mailbox mayproduce gevuld met een aantal lege berichten dat gelijk is aan de capaciteit van de buffer.

    Het aantal berichten in mayproduce verminderen met iedere productie en groeien met iedere consumptie.

    Deze aanpak is erg flexibel. Er kunnen meerdere producenten en consumenten zijn, zolang als ze allemaal toegang hebben tot beide mailboxen. Het systeem mag zelfs gedistribueerd worden, met alle producent processen en de mayproduce mailbox op een site en alle consument processen en de mayconsume mailbox op een andere.

    5.6. Lezen/schrijven probleem

    Om te gaan met het ontwerp van synchronisatie en gelijktijdige mechanismen is het handig om mogelijke te zijn het probleem te relateren aan de hand van gekende problemen en om mogelijk te zijn om eender welke oplossing te testen in termen van zijn mogelijkheid om deze gekende problemen op te lossen. In de literatuur, hebben verschillende problemen de belangrijkheid en frequente verschijning aangenomen, beide omdat ze voorbeelden zijn van algemene ontwerp problemen en voor hun educatieve waarde. Een van zulke problemen is dat van het producent/consument probleem, welke reeds onderzocht is. In deze sectie kijken we naar een ander klassiek probleem: het lezers/schrijvers probleem.

    Het lezers/schrijvers probleem wordt als volgt gedefinieerd: Er is een datagebied dat gedeeld wordt tussen een aantal processen. Het datagebied kan een bestand, een geheugenblok of zelfs een bank van processorregisters zijn. Er zijn een aantal processen dat alleen het datagebied lezen (readers) en een aantal dat enkel naar het datagebied schrijven (writers). De condities waaraan voldaan moet worden zijn als volgt:

    1. Aantal lezers dat tegelijk een bestand mogen lezen is volkomen vrij.
    2. Een schrijver tegelijkertijd mag naar een bestand schrijven.
    3. Tijdens het schrijven mag lezer het bestand lezen.

    Dus lezers zijn processen die niet vereist zijn om elkaar uit te sluiten en schrijvers zijn processen die benodigd zijn om alle andere processen, readers en gelijkaardige schrijvers uit te sluiten.

    Voordat we verder gaan laten we dit probleem van twee andere onderscheiden: het algemeen wederzijds uitsluitingsprobleem en de producent/consument probleem. In het lezers/schrijvers probleem schrijven lezers niet naar het datagebied, noch zullen schrijvers het datagebied lezen terwijl het aan het schrijven is. Een algemener geval in deze zaak is om een de processen het datagebied toe te staan deze te lezen of te beschrijven. In dat geval kunnen we eender welk deel van een proces als kritieke sectie bepalen die dat datagebied benaderd en de algemene oplossing tot wederzijdse uitsluiting opleggen. De reden om betrokken te zijn met een meer beperkt geval is dat er voor dit geval meerdere efficiënte oplossingen mogelijk zijn en dat voor dit probleem de minst efficiënte oplossingen onaccepteerbaar traag zijn. Veronderstel bijvoorbeeld dat het gedeeld gebied een bibliotheek catalogus is. Gewone gebruikers van de bibliotheek lezen de catalogus om een boek te vinden. Een of meerdere bibliothecarissen hebben de mogelijkheid om de catalogus bij te werken. In de algemene oplossing, zou ieder toegang tot de catalogus als een kritieke sectie worden behandeld en gebruikers zouden worden geforceerd om de catalogus met een tegelijk te lezen. Dit zou duidelijk niet te tolereren vertragingen met zich meebrengen. Op hetzelfde moment is het belangrijk om te voorkomen dat schrijvers met elkaar interfereren en het is ook nodig dat er wordt gelezen op het moment dat er wordt geschreven om de toegang tot inconsequente informatie te voorkomen.

    Kan het producent/consument probleem eenvoudig beschouwd worden als een speciaal geval van het lezers/schrijvers probleem met een enkele schrijver de producent) en een enkele lezer (de consument)? Het antwoord is nee. De producent is niet gewoon een schrijver. Het moet wachtrij pointers lezen om te bepalen waar hij het volgend item schrijft en het moet bepalen of de buffer vol is. Gelijkaardig, de consument is niet gewoon een lezer, omdat het de wachtrij pointers moet aanpassen om te laten zien dat het een unit van de buffer heeft verwijderd.

    We gaan nu twee oplossingen voor dit probleem bestuderen.

    5.6.1. Lezers hebben voorrang

    Figuur 5.22 is een oplossing dat gebruik maakt van semaforen dat een instantie laat zien van een lezer en een schrijver; de oplossing veranderd niet voor meerdere lezers en schrijvers. Het schrijvers proces is eenvoudig. De semafoor wsem wordt gebruikt om wederzijdse uitsluiting af te dwingen. Zolang als een schrijver het gedeeld datagebied benaderd mogen geen andere schrijvers en geen schrijvers het benaderen. Het lezers proces maakt ook gebruik van wsem om wederzijdse uitsluiting af te dwingen. Echter om meerdere lezers toe te laten, vereisen we dat als er geen andere lezers aan het lezen zijn. De eerste lezer dat probeert te lezen zou moeten wachten op wsem. Als er reeds op zijn minst een lezer aan het lezen is, is het voor volgende lezers niet nodig te wachten om binnen te gaan. De globale variabele readcount wordt gebruikt om het aantal lezers bij te houden en de semafoor x wordt gebruikt om zeker te zijn dat readcount netjes wordt bijgewerkt.

    5.6.2. Schrijvers hebben voorrang

    In de voorgaande oplossing hebben lezers prioriteit. Eens een enkele lezer begonnen is met het benaderen van het datagebied, is het mogelijk dat lezers de controle van het datagebied terugkrijgen zolang er op zijn minst één lezer in de handeling van het lezen zit. Daarom zijn schrijvers onderwerp van uitsterving.

    Figuur 5.23 laat een oplossing zien dat garandeert dat er geen nieuwe lezers zijn toegestaan om het datagebied te benaderen eens er op zijn minst een schrijver verklaard heeft om te willen schrijven. Voor lezers zijn de volgende semaforen en variabelen aan de reeds gedefinieerde toegevoegd:

  • Een semafoor rsem dat alle lezers hindert terwijl er op zijn minst een schrijver toegang wenst tot het datagebied.
  • Een variabele writecount dat de instelling van rsem controleert.
  • Een semafoor y dat het bijwerken van writecount controleert.
  • Voor lezers is er een extra semafoor benodigd. Het mag niet toegestaan zijn een lange wachtrij te bouwen op rsem; anders zullen schrijvers niet in staat zijn naar de wachtrij te springen. Daarom is maar een lezer toegestaan een plaats te nemen in de wachtrij van rsem, met extra lezers die plaats willen nemen in de wachtrij van z, onmiddellijk voor het wachten op rsem. Tabel 5.6 somt de mogelijkheden op.

    Een alternatieve oplossing, welke prioriteit aan schrijvers geeft en welk geïmplementeerd is met gebruikmaking van berichtuitwisseling, wordt getoond in figuur 5.24. In dit geval is er een controller proces dat toegang heeft tot het gedeeld datagebied. Andere processen welke toegang willen hebben tot het datagebied zenden een verzoek bericht naar de controller, krijgen toestemming het datagebied met een "OK" antwoord bericht en geeft de voltooiing van de toegang aan met een "finished" bericht. De controller is uitgerust met drie mailboxen, een voor elk type bericht dat het kan ontvangen.

    De controller proces service schrijft verzoek berichten voor de lezers verzoek berichten om schrijvers prioriteit te geven. Daarnaast moet wederzijdse uitsluiting afgedwongen worden. Om dit te doen wordt de variabele count gebruikt, welk wordt geïnitialiseerd op een groter aantal dan het maximumaantal mogelijke lezers. In dit voorbeeld gebruiken we een waarde van 100. De actie van de controller kan als volgt samengevat worden:

  • Als count > 0, dan is er geen schrijver aan het wachten en dan kunnen er of kunnen er geen lezers actief zijn. Behandel eerst alle "finished" berichten om de actieve lezers te wissen. Behandel dan de service aanvragen en dan de lees aanvragen.
  • Als count = 0, dan is het enige openstaande aanvraag een schrijf aanvraag. Laat de schrijver toe om verder te gaan en wacht op een "finished" bericht.
  • Als count < 0, dan heeft een schrijver een aanvraag gedaan en is gemaakt om te wachten om alle actieve lezers te wissen. Daarom moeten alleen "finished" berichten worden behandeld.
  • Herhalingsvragen

    1. Noem vier punten waarbij het begrip gelijktijdigheid van belang is bij het ontwerpen.

      Communicatie tussen processen, het delen van en het wedijveren om bronnen, de synchronisatie van meerdere procesactiviteiten, en het toedelen van de processortijd aan de processen.
       
    2. In welke drie situaties is gelijktijdigheid belangrijk?

      Meerdere toepassingen, gestructureerde toepassingen, structuur van het besturingssysteem.
       
    3. Wat is de basisvereiste bij het uitvoeren van gelijktijdige processen?

      De mogelijkheid om wederzijdse uitsluiting af te dwingen.
       
    4. Noem drie vormen van onderlinge bewustzijn tussen processen en beschrijf iedere vorm in het kort.

      Processen die zich niet bewust zijn van elkaar:
      Dit zijn onafhankelijke processen die niet zijn bedoeld om samen te werken.
      Processen die zich indirect bewust zijn van elkaar: Dit zijn processen die elkaar niet noodzakelijkerwijs van naam hoeven te kennen, maar die toegang tot hetzelfde object delen, bijvoorbeeld tot een I/O buffer.
      Processen die zich direct bewust zijn van elkaar: Dit zijn processen die met elkaar kunnen communiceren op basis van een procesidentificatienummer en die ontworpen zijn om gezamenlijk aan een bepaalde activiteit te werken.
       
    5. Wat is het verschil tussen concurrerende en samenwerkende processen?

      Concurrerende processen moeten tegelijkertijd toegang tot dezelfde bron hebben, zoals een schijf, bestand of printer.
      Samenwerkende processen delen de toegang een gemeenschappelijk object, zoals een geheugenbuffer of zijn in staat zijn om met elkaar te communiceren en samen te werken bij de uitvoering van een toepassing of activiteit.

       
    6. Noem de drie besturingsproblemen die samenhangen met concurrerende processen en beschrijf deze in het kort.

      Wederzijdse uitsluiting: Wedijverende processen kunnen alleen een bron benaderen die beide op ieder op zijn beurt willen benaderen; mechanismen voor wederzijdse uitsluiting moeten dit één-op-een-keer-beleid af te dwingen.
      Deadlock: Als wedijverende processen exclusieve toegang tot meer dan één bron moeten krijgen dan kan een deadlock optreden als elke van de processen de controle kreeg over één bron en aan het wachten is op de andere bron.
      Verhongering: één van een reeks van concurrerende processen kunnen voor onbepaalde tijd toegang tot een benodigde bron nodig worden geweigerd omdat andere leden van de set die bron monopoliseren.

       
    7. Geef de vereisten voor wederzijdse uitsluiting.
       
      1. Wederzijdse uitsluiting moet dwingend worden opgelegd: slechts één proces van alle processen met kritieke secties voor dezelfde bron of hetzelfde gedeelde object wordt tegelijkertijd in de kritieke sectie toegelaten.
      2. Een proces dat stopt in zijn niet-kritieke sectie, moet dat doen zonder andere processen te verstoren.
      3. Een proces dat toegang wenst tot zijn kritieke sectie, mag niet oneindig worden vertraagd: deadlocks en uithongering mogen niet voorkomen.
      4. Bevindt geen enkel proces zich in zijn kritieke sectie, dan moet elk proces dat verzoekt om toegang tot zijn kritieke sectie, zonder vertraging toegang krijgen.
      5. Er worden geen veronderstellingen gebruikt over de relatieve snelheden van processen of het aantal processen.
      6. Een proces bevindt zich slechts een beperkte tijd in zijn kritieke sectie.
         
    8. Welke bewerkingen zijn mogelijk op een semafoor?
       
      1. Een semafoor kan worden geïnitialiseerd op een niet-negatieve waarde.
      2. De bewerking wait operatie verlaagt de semafoorwaarde. Wordt de waarde negatief, dan wordt het proces dat de opdracht wait uitvoert, geblokkeerd.
      3. De bewerking signal verhoogt de semafoorwaarde. Is de waarde niet positief, dan wordt een proces dat is geblokkeerd door een bewerking wait gedeblokkeerd.
         
    9. Wat is het verschil tussen een binaire en een algemene semafoor?

      Een binaire semafoor kan slechts de waarden 0 en 1 aannemen.
      Een algemene
      semafoor kan elk geheel getal aannemen.
       
    10. Wat is het verschil tussen een sterke en een zwakke semafoor?

      Een sterke semafoor vereist dat processen die worden geblokkeerd op die semafoor worden gedeblokkeerd gebruikmakend van een first-in-first-out beleid.
      Een zwakke
      semafoor bepaalt niet de volgorde waarin geblokkeerde processen gedeblokkeerd moeten worden.

       
    11. Wat is een monitor?

      Een monitor is een programmeertaal constructie voorziet in  abstracte data types en wederzijds exclusieve toegang tot een reeks procedures.
       
    12. Wat is het verschil tussen blokkerende en niet-blokkerende berichten?

      Er zijn twee aspecten, het verzenden en ontvangen van primitieven.
      1. Wanneer een
      send primitieve wordt uitgevoerd in een proces, zijn er twee mogelijkheden: ofwel wordt het verzendende proces geblokkeerd totdat het bericht is ontvangen of niet.
      2. Wanneer een proces een primitieve receive ontvangt zijn er twee mogelijkheden: is eerder al een bericht ontvangen, dan wordt het bericht ontvangen en wordt de uitvoering voortgezet. Is er geen wachtend bericht, dan
      (
      a) wordt het proces geblokkeerd totdat het bericht aankomt, of
      (
      b) wordt het proces voortgezet en staakt het zijn poging een bericht te ontvangen.
       
    13. Welke voorwaarden zijn in het algemeen verbonden aan het lezer/schrijverprobleem?

      1. Elk aantal lezers kunnen gelijktijdig het bestand te lezen.
      2. Slechts een schrijver per keer kan naar het bestand schrijven.
      3. Als een schrijver naar het bestand schrijft, kan geen lezer dit lezen.

    Probleemvraagstukken

    1. Processen en threads zijn een krachtig structureerhulpmiddel voor het implementeren van programma’s die als sequentiële programma’s veel complexer zouden zijn. Een oudere constructie waarvan het bestuderen leerzaam is, is de coroutine. Het doel van deze opgave is coroutines te introduceren en te vergelijken met processen. Ga uit van het volgende, eenvoudige probleem uit [CONW63]:
      Lees kaarten met kolommen van 80 symbolen en druk ze af in regels van 125 symbolen met de volgende verschillen: achter elk kaartbeeld wordt een extra spatie ingevoegd en elk paar aangrenzende asterisken (**) op een kaart wordt vervangen door het symbool .
      1. Ontwikkel een oplossing van dit probleem als een gewoon sequentieel programma. U zult ontdekken dat het programma lastig te schrijven is. De interacties van de verschillende onderdelen van het programma zijn ongelijk door de conversie van de lengte van 80 naar 125; bovendien is de lengte van het kaartbeeld, na de conversie, afhankelijk van het aantal malen dat er dubbele asterisken voorkomen. Een mogelijkheid om de duidelijkheid te verhogen en de kans op programmafouten te verkleinen, is de toepassing te schrijven als drie aparte procedures. De eerste procedure leest kaartbeelden in, vult elk beeld aan met een spatie en schrijft een stroom tekens naar een tijdelijk bestand. Nadat alle kaarten zijn gelezen, leest de tweede procedure het tijdelijke bestand, vervangt de asterisken en schrijft een tweede tijdelijk bestand. De derde procedure leest de stroom tekens uit het tweede tijdelijke bestand en drukt regels met 125 tekens af.
         
      2. Door de overhead van de 1/0 en de tijdelijke bestanden is de sequentiële oplossing onaantrekkelijk. Conway stelde een nieuw type programmastructuur voor, de coroutine, die het mogelijk maakt de toepassing te schrijven als drie programma’s die zijn verbonden door buffers van één teken (figuur 5-25). Bij een traditionele procedure bestaat er een master/slave-relatie tussen de aanroepende en aangeroepen procedure. De aanroepende procedure kan een aanroep uitvoeren vanuit elk punt in de procedure; de aangeroepen procedure wordt begonnen op zijn ingangspunt en keert terug naar de aanroepende procedure op het punt van aanroep. De coroutine kent een meer symmetrische relatie. Bij elke aanroep wordt de uitvoering voortgezet vanaf het laatste actieve punt in de aangeroepen procedure. Aangezien een aanroepende procedure niet ‘hoger’ is dan de aangeroepen procedure, wordt geen return uitgevoerd. In plaats daarvan kan elke coroutine de besturing overdragen aan elke andere coroutine met een hervattingsopdracht. Wordt een coroutine voor het eerst aangeroepen, dan wordt deze ‘hervat’ vanaf het ingangspunt. Daarna wordt de coroutine opnieuw geactiveerd op het punt van haar eigen, laatste hervattingopdracht. Merk hierbij op dat maar één coroutine in een programma tegelijk kan worden uitgevoerd en dat de overgangspunten expliciet zijn gedefinieerd in de code, waardoor hier geen sprake is van gelijktijdige verwerking. Leg de werking van het programma in figuur 5-25 uit.
         
      3. Het programma gaat niet in op de conditie voor de beëindiging. Veronderstel dat de routine READCARD de waarde true als resultaat geeft zodra de routine een beeld van 80 symbolen in inbuf heeft geplaatst; in alle andere gevallen geeft de routine false als resultaat. Wijzig het programma om deze mogelijkheid op te nemen. Merk op dat de laatst afgedrukte regel hierdoor minder dan 125 tekens kan bevatten.
         
      4. Formuleer de oplossing opnieuw met behulp van drie processen die semaforen gebruiken.


         
    2. Ga uit van een programma met gelijktijdigheid en twee processen, p en q, zoals wordt getoond in de volgende code. A, B, C, D en E zijn willekeurige, atomaire (ondeelbare) opdrachten. Veronderstel dat het hoofdprogramma (dat niet wordt getoond) een parbegin van de twee processen uitvoert.

       
      void p()
      {
          A;
          B;
          C;
      }
      void q()
      {
          D;
          E;
      }

      Toon alle mogelijke verwevingen in de uitvoering van de voorgaande twee processen. (Laat het uitvoeringsspoor zien in termen van atomaire statements.)
       

    3. Bestudeer het volgende programma:

       
      const int n = 50;
      int tally;
      void total()
      {
          int count;
          for (count = 1; count<= n; count++)
          {
              tally++;
          }
      }
      void main()
      {
          tally = 0;
          parbegin (total (), total () );
      write (tally);
      }
       
      1. Bepaal de juiste ondergrens en bovengrens van de uiteindelijke waarde van de gedeelde variabele tally die door dit gelijktijdige programma wordt uitgevoerd. Veronderstel dat processen kunnen worden uitgevoerd met elke relatieve snelheid en dat een waarde alleen kan worden verhoogd nadat deze door een afzonderlijke machine-instructie in een register is geladen.
         
      2. Stel dat een willekeurig aantal van deze processen parallel mogen worden uitgevoerd onder de veronderstellingen van vraag a. Welke gevolgen heeft deze wijziging voor het bereik van de uiteindelijke waarden van tally?
         
    4. Is actief wachten altijd minder efficiënt (als het gaat om het gebruik van processortijd) dan een passief wachten? Licht het antwoord toe.
       
    5. Bestudeer het volgende programma:
       
      boolean blocked [2];
      int turn;
      void P (int id)
      {
          while (true)
              {
              blocked[id] = true;
              while (turn != id)
              {
                  while (blocked[1-id])
                  /* do nothing */;
                  turn = id;
              }
              /* critical section */
              blocked[id] = false;
              /* remainder */
          }
      }
      void main()
      {
          blocked[0] = false;
          blocked[1] = false;
          turn = 0;
          parbegin (P(0), P(1));
      }

      Deze softwareoplossing van het probleem van wederzijdse uitsluiting werd voorgesteld in [HYMA66I. Zoek een tegenvoorbeeld dat bewijst dat deze oplossing onjuist is. Het is overigens aardig op te merken dat zelfs de redactie van Communications of the ACM hierbij om de tuin werd geleid.
       

    6. Een andere benadering van wederzijdse uitsluiting is de bakkerijalgoritme van Lam- port [LAMP74j, die zo wordt genoemd omdat hij is gebaseerd op de praktijk in bakkerijen en andere winkels waar elke klant bij aankomst een nummertje krijgt, zodat hij wordt bediend wanneer hij aan de beurt is. De algoritme luidt als volgt:

       
      boolean choosing[n];
      int number[n];
      while (true)
      {
          choosing[i] = true;
          number[i] = 1 + getmax(number[], n);
          choosing[i] = false;
          for (int j = 0; j < n; j++)
          {
              while (choosing[j])
              { };
              while ((number[j] != 0) && (number[j], j) < (number[i], i))
              { };
          }
          /* critical section */;
          number [i] = 0;
          /* remainder */;
      }

      De arrays choosing en number worden respectievelijk geinitialiseerd met false en 0. Element i van elke array kan worden gelezen en geschreven door proces i, maar uitsluitend worden gelezen door andere processen. De notatie (a,b) < (c,d) wordt gedefinieerd als



      a. Beschrijf de algoritme in woorden.

      b. Toon aan dat de algoritme deadlocks vermijdt.

      c. Toon aan dat de algoritme wederzijdse uitsluiting afdwingt.
       

    7. Wordt, zoals in figuur 5-2, een speciale machine-instructie gebruikt voor wederzijdse uitsluiting, dan is het niet mogelijk te bepalen hoe lang een proces moet wachten voordat het toegang krijgt tot zijn kritieke sectie. Ontwerp een algoritme die de instructie testset gebruikt maar die garandeert dat elk proces dat wacht op toegang tot zijn kritieke sectie, de kritieke sectie kan uitvoeren binnen n - 1 beurten, waarbij n het aantal processen is dat toegang kan eisen tot de kritieke sectie en een ‘beurt’ een gebeurtenis is die bestaat uit een proces dat de kritieke sectie verlaat en een ander proces dat toegang krijgt.
       
    8. Bestudeer de volgende definitie van semaforen:
       
      void semWait(s)
      {
          if (s.count > 0)
          {
              s.count--;
          }
          else
          {
              place this process in s.queue;
              block;
          }
      }
      void semSignal (s)
      {
          if (there is at least one process blocked on semaphore s)
          {
              remove a process P from s.queue;
              place process P on ready list;
          }
          else
              s.count++;
      }

      Vergelijk deze verzameling definities met die in figuur 5-3. Let op het volgende verschil: bij de voorgaande definitie kan een semafoor nooit een negatieve waarde krijgen. Is er een verschil in de gevolgen van de twee verzamelingen definities wanneer die worden gebruikt in programma’s? Met andere woorden: kunt u de ene verzameling vervangen door de andere zonder de betekenis van het programma te veranderen?
       

    9. Het moet mogelijk zijn algemene semaforen te implementeren met binaire semaforen. We kunnen de bewerkingen semWaitB en semSignalB gebruiken en twee binaire semaforen, delay en mutex Beschouw het volgende:

       
      void semWait(semaphore s)
      {
          semWaitB(mutex);
          s--;
          if (s < 0)
          {
              semSignalB(mutex);
              semWaitB(delay);
          }
          else
              SemsignalB(mutex);
      }
      void semSignal(semaphore s);
      {
          semWaitB(mutex);
          s++;
          if (s <= 0)
              semSignalB(delay);
          semSignalB(mutex);
      }

      In eerste instantie wordt s ingesteld op de gewenste semafoorwaarde. Elke bewerking semWait verlaagt s en elke bewerking semSignal verhoogt s. De binaire semafoor mutex, die wordt geïnitialiseerd op 1, zorgt voor wederzijdse uitsluiting bij het bijwerken van s. De binaire semafoor delay, die wordt geïnitialiseerd op 0, wordt gebruikt om processen uit te stellen.
      Het voorgaande programma bevat een fout. Beschrijf de fout en stel een verandering voor die de fout verhelpt. Aanwijzing: Veronderstel dat twee processen semwait(s) aanroepen waarbij s de beginwaarde 0 heeft. Nadat het eerste proces net semSignalB(mutex) heeft uitgevoerd, maar nog niet semWaitB(delay) ,vordert de tweede aanroep van semWait(s) tot hetzelfde punt. U hoeft hiervoor slechts één regel van het programma verplaatsen.
       

    10. In 1978 sprak Dijkstra het vermoeden uit dat voor het probleem van wederzijdse uitsluiting zonder uithongering geen oplossing bestond in de situatie met een onbekend. maar eindig aantal processen, gebruik makend van een eindig aantal zwakke semaforen. In 1979 weerlegde J.M. Morris deze veronderstelling door het publiceren van een algoritme die drie zwakke semaforen gebruikt. De werking van de algoritme kan als volgt worden beschreven: als één of meer processen staan te wachten in een semWait(S) -bewerking en een ander proces voert semSignal(S) uit, wordt de waarde van S niet veranderd en een van de wachtende processen wordt gedeblokkeerd, onafhankelijk van semWait (S). Naast de drie semaforen gebruikt de algoritme twee variabelen (niet-negatieve gehele getallen) als tellers van het aantal processen in bepaalde secties van de algoritme. Daarbij krijgen de semaforen A en B een beginwaarde van 1 en krijgen de semafoor M en de tellers NA en NM een begin- waarde 0. De semafoor B voor de wederzijdse uitsluiting beschermt de toegang tot de gedeelde variabele NA. Een proces dat probeert zijn kritieke sectie binnen te gaan, moet twee drempels nemen in de vorm van de semaforen A en M. De tellers NA en NM bevatten respectievelijk het aantal processen dat klaar staat om de drempel A te nemen en het aantal processen dat drempel A al heeft genomen maar nog niet drempel M. In het tweede gedeelte van de beschrijving gaan de NM processen die geblokkeerd staan bij M, één voor één hun kritieke sectie binnen. Hierbij wordt opnieuw een cascadetechniek gebruikt die lijkt op de aanpak in het eerste gedeelte. Ontwikkel een algoritme die overeenkomt met deze beschrijving.
       
    11. Het volgende probleem werd eens gebruikt in een examen:
      Jurassic Park bestaat uit een dinosaurusmuseum en een park voor safariritjes. Er zijn m passagiers en n karretjes voor één passagier. Passagiers lopen eerst een tijdje rond in het museum en gaan vervolgens in een rij staan voor een ritje in een safarikarretje. Is er een karretje beschikbaar, dan stapt er één passagier in en rijdt het karretje gedurende een willekeurige tijd rond in het park. Zijn alle n karretjes bezet met rondrijdende passagiers, dan moet een passagier die een ritje wil maken, wachten; is een karretje vrij maar zijn er geen wachtende passagiers, dan wacht het karretje. Gebruik semaforen om de m passagiersprocessen en de n karretjesprocessen te synchroniseren.
      Het volgende ontwerp werd gevonden op een kladblaadje op de vloer van de examenzaal. Beoordeel de juistheid van de code. Negeer de syntaxis en ontbrekende declaraties van variabelen. Eerder is al vermeld dat P en V overeenkomen met semWait en semSignal.
       
      resource Jurassic_Park()
          sem car_avail := 0, car_taken := 0, car_filled := 0, passenger_released := 0
          process passenger(i := 1 to num_passengers)
              do true -> nap(int(random(1000*wander_time)))
                  P(car_avail); V(car_taken); P(car_filled)
                  P(passenger_released)
              od
          end passenger
          process car(j := 1 to num_cars)
              do true -> V(car_avail); P(car_taken); V(car_filled)
                  nap(int(random(1000*ride_time)))
                  V(passenger_released)
              od
          end car
      end Jurassic_Park

       

    12. In het commentaar bij figuur 5.9 en tabel 5.3 werd opgemerkt dat “Dit kan niet zomaar worden opgelost door de voorwaardelijke opdracht te verplaatsen naar de kritieke sectie van de consument, omdat dit kan leiden tot een deadlock”. Toon dit aan met een tabel, vergelijkbaar met tabel 5.3.
       
    13. Bestudeer de oplossing van het producent/consumentprobleem met een eindige buffer die is gedefinieerd in figuur 5.10. Ga uit van het (veel voorkomende) geval waarin de producent en de consument met ongeveer dezelfde snelheid functioneren. Het scenario kan als volgt luiden:
      Producer: append; semSignal; produce; ...; append; semsignal; produce; ...; Consumer: consume: ...; take: semwait; consume; ...; take; semWait; ...
      De producent kan altijd een nieuw element toevoegen en een signaal verzenden tijdens de consumptie van het vorige element door de consument. De producent voegt altijd een element toe aan een lege buffer en de consument haalt altijd het enige element uit de buffer. Hoewel de consument nooit wordt geblokkeerd op de semafoor. wordt een groot aantal aanroepen van het semafoormechanisme gebruikt, wat leidt tot een aanzienlijke overhead.
      Maak een nieuw programma dat onder deze omstandigheden efficiënter is. Aanwijzingen: sta toe dat n een waarde van -1 heeft, wat niet alleen betekent dat de buffer leeg is maar ook dat de consument dit heeft opgemerkt en geblokkeerd wordt totdat de producent nieuwe gegevens aanlevert. De oplossing vereist geen gebruik van de lokale variabele m uit figuur 5.10.
       
    14. Bestudeer figuur 5-13. Verandert de betekenis van het programma als de volgende onderdelen worden verwisseld?
      1. semWait(e); semWait(s)
      2. semSignal(s); semSignal(n)
      3. semWait(n); sexaWait(s)
      4. semSignal(s); semSignal(e)
         
    15. In de bespreking van het producent/consumentprobleem met een eindige buffer bood onze definitie ruimte aan ten hoogste n - 1 ingangen in de buffer.
      1. Waarom is dit?
         
      2. Wijzig de algoritme om deze tekortkoming te verhelpen.
         
    16. Deze opgave illustreert het gebruik van semaforen voor het coördineren van drie soorten processen.4 De Kerstman slaapt in zijn werkplaats op de Noordpool en kan alleen worden gewekt als (1) zijn rendieren alle negen zijn teruggekeerd van hun vakantie in de Zuid-Pacific of (2) een van zijn dwergen problemen heeft bij het maken van speelgoed. Om de Kerstman wat rust te gunnen, kunnen de dwergen hem alleen wekken als drie dwergen een probleem hebben; andere dwergen die een bezoek willen brengen aan de Kerstman, moeten wachten totdat deze drie zijn teruggekeerd. Ontwaakt de Kerstman en ziet hij dat er drie dwergen voor de deur van zijn werkplaats staan te wachten én dat het laatste rendier is teruggekeerd uit de tropen. dan beslist de Kerstman dat de dwergen maar moeten wachten tot na Kerstmis, omdat het belangrijker is zijn slee in orde te maken. (Hierbij wordt verondersteld dat de rendieren de tropen liever niet verlaten en daarom tot het laatst mogelijke ogenblik wachten met terugkeren naar de Noordpool.) Het laatste rendier dat terugkeert, moet de Kerstman halen, terwijl de andere rendieren wachten in een warme hut voordat ze voor de slee worden gespannen. Los dit probleem op met semaforen.
       
    17. Toon aan dat het uitwisselen van berichten en semaforen een vergelijkbare functionaliteit hebben door:
      1. Het uitwisselen van berichten te implementeren met semaforen. Aanwijzing: gebruik een gedeeld buffergebied voor de opslag van de postvakken, die elk bestaan uit een array met posities voor berichten.
         
      2. Een semafoor te implementeren met het uitwisselen van berichten. Aanwijzing: gebruik een afzonderlijk proces voor de synchronisatie.