impasse - Deadlock

Niet te verwarren met Deathlok of Dreadlock .
Dit artikel gaat over het informatica-concept. Voor ander gebruik, zie Deadlock (het ondubbelzinnig maken) .

Image
Beide processen hebben resources nodig om de uitvoering voort te zetten. P1 heeft extra hulpbron R1 nodig en is in het bezit van hulpbron R2 , P2 heeft extra hulpbron R2 nodig en is in het bezit van R1 ; geen van beide processen kan doorgaan.
Image
Vier processen (blauwe lijnen) strijden om één middel (grijze cirkel), volgens een rechts-voor-links-beleid. Een deadlock treedt op wanneer alle processen de resource tegelijkertijd vergrendelen (zwarte lijnen). De impasse kan worden opgelost door de symmetrie te doorbreken.

Bij gelijktijdig computergebruik is een deadlock een toestand waarin elk lid van een groep wacht tot een ander lid, inclusief zichzelf, actie onderneemt, zoals het verzenden van een bericht of het vrijgeven van een slot . Deadlocks zijn een veelvoorkomend probleem in multiprocessing- systemen, parallel computing en gedistribueerde systemen , waar software- en hardwarevergrendelingen worden gebruikt om gedeelde bronnen te arbitreren en processynchronisatie te implementeren .

Een besturingssysteem , een deadlock wanneer een proces of thread voert een wachtende toestand omdat een aangevraagde systeembron wordt vastgehouden door een ander wachtende taak, die op zijn beurt wacht op een bron die door een andere wachtende taak. Als een proces zijn status niet voor onbepaalde tijd kan wijzigen omdat de door het proces gevraagde resources worden gebruikt door een ander wachtend proces, dan zou het systeem in een impasse zitten.

In een communicatiesysteem treden impasses voornamelijk op als gevolg van verloren of corrupte signalen in plaats van conflict over hulpbronnen.

Image
Twee processen die in tegengestelde volgorde strijden om twee bronnen.
  1. Er wordt één proces doorlopen.
  2. Het latere proces moet wachten.
  3. Een deadlock treedt op wanneer het eerste proces de eerste resource vergrendelt op hetzelfde moment dat het tweede proces de tweede resource vergrendelt.
  4. De impasse kan worden opgelost door het eerste proces te annuleren en opnieuw te starten.

Noodzakelijke voorwaarden

Er kan zich een impasse op een resource voordoen als en alleen als alle volgende omstandigheden tegelijkertijd in een systeem voorkomen:

  1. Wederzijdse uitsluiting : er moeten ten minste twee bronnen in een niet-deelbare modus worden bewaard. Anders zouden de processen niet worden verhinderd om de bron te gebruiken wanneer dat nodig is. Slechts één proces kan de resource op een bepaald moment gebruiken.
  2. Hold and wait of resource vasthouden: een proces houdt momenteel ten minste één resource vast en vraagt ​​om aanvullende resources die door andere processen worden vastgehouden.
  3. Geen voorkoop : een grondstof kan alleen vrijwillig worden vrijgegeven door het proces dat het bezit.
  4. Circulair wachten: elk proces moet wachten op een resource die wordt vastgehouden door een ander proces, dat op zijn beurt wacht tot het eerste proces de resource vrijgeeft. Over het algemeen is er een reeks wachtprocessen, P = { P 1 , P 2 , …, P N }, zodanig dat P 1 wacht op een hulpmiddel dat wordt vastgehouden door P 2 , P 2 wacht op een hulpmiddel dat wordt vastgehouden door P 3 etc. tot P N wacht op een bron bezit van P 1 .

Deze vier voorwaarden staan ​​bekend als de Coffman-voorwaarden uit hun eerste beschrijving in een artikel uit 1971 van Edward G. Coffman, Jr.

Hoewel deze voorwaarden voldoende zijn om een ​​impasse te veroorzaken op resourcesystemen met één instantie, duiden ze alleen op de mogelijkheid van een deadlock op systemen met meerdere instanties van resources.

Deadlock-afhandeling

De meeste huidige besturingssystemen kunnen deadlocks niet voorkomen. Wanneer een impasse optreedt, reageren verschillende besturingssystemen hierop op verschillende niet-standaard manieren. De meeste benaderingen werken door te voorkomen dat een van de vier Coffman-condities optreedt, vooral de vierde. De belangrijkste benaderingen zijn als volgt.

Impasse negeren

Bij deze benadering wordt aangenomen dat er nooit een deadlock zal optreden. Dit is ook een toepassing van het Ostrich-algoritme . Deze aanpak werd aanvankelijk gebruikt door MINIX en UNIX . Dit wordt gebruikt wanneer de tijdsintervallen tussen het optreden van deadlocks groot zijn en het gegevensverlies dat elke keer wordt opgelopen acceptabel is.

Het negeren van impasses kan veilig worden gedaan als formeel is bewezen dat impasses nooit voorkomen. Een voorbeeld is het RTIC-raamwerk.

Detectie

Onder de deadlock-detectie mogen deadlocks optreden. Vervolgens wordt de toestand van het systeem onderzocht om te detecteren dat er een impasse is opgetreden en vervolgens wordt deze gecorrigeerd. Er wordt een algoritme gebruikt dat de toewijzing van middelen en processtatussen volgt, het terugdraait en een of meer van de processen herstart om de gedetecteerde impasse te verwijderen. Het is gemakkelijk mogelijk om een ​​reeds opgetreden impasse te detecteren, aangezien de resources die elk proces heeft vergrendeld en/of momenteel zijn aangevraagd, bekend zijn bij de resourceplanner van het besturingssysteem.

Nadat een impasse is gedetecteerd, kan deze worden gecorrigeerd met een van de volgende methoden:

  1. Procesbeëindiging: een of meer processen die betrokken zijn bij de impasse kunnen worden afgebroken. Men zou ervoor kunnen kiezen om alle concurrerende processen die bij de impasse betrokken zijn af te breken. Dit zorgt ervoor dat een impasse met zekerheid en snelheid wordt opgelost. Maar de kosten zijn hoog omdat gedeeltelijke berekeningen verloren gaan. Of men kan ervoor kiezen om één proces tegelijk af te breken totdat de impasse is opgelost. Deze aanpak heeft een hoge overhead omdat na elke afbreking een algoritme moet bepalen of het systeem nog steeds in een impasse zit. Bij het kiezen van een kandidaat voor beëindiging moet rekening worden gehouden met verschillende factoren, zoals prioriteit en leeftijd van het proces.
  2. Voorrang van middelen : middelen die aan verschillende processen zijn toegewezen, kunnen achtereenvolgens worden gepreëmpteerd en aan andere processen worden toegewezen totdat de impasse is doorbroken.

preventie

Hoofd artikel: algoritmen voor het voorkomen van deadlocks
Image
(A) Twee processen die strijden om één bron, volgens een wie het eerst komt, het eerst maalt-beleid. (B) Deadlock treedt op wanneer beide processen de bron tegelijkertijd vergrendelen. (C) De impasse kan worden opgelost door de symmetrie van de sluizen te doorbreken. (D) De impasse kan worden voorkomen door de symmetrie van het vergrendelingsmechanisme te doorbreken.

Deadlock-preventie werkt door te voorkomen dat een van de vier Coffman-condities optreedt.

  • Het verwijderen van de voorwaarde voor wederzijdse uitsluiting betekent dat geen enkel proces exclusieve toegang heeft tot een bron. Dit blijkt onmogelijk voor bronnen die niet kunnen worden gespoold . Maar zelfs met in de wachtrij geplaatste bronnen kan de impasse nog steeds optreden. Algoritmen die wederzijdse uitsluiting vermijden, worden niet-blokkerende synchronisatie- algoritmen genoemd.
  • De voorwaarden voor vasthouden en wachten of het vasthouden van middelen kunnen worden verwijderd door processen te verplichten alle benodigde middelen aan te vragen voordat ze worden opgestart (of voordat ze aan een bepaalde reeks bewerkingen beginnen). Deze voorkennis is vaak moeilijk te bevredigen en is in ieder geval een inefficiënte besteding van middelen. Een andere manier is om van processen te eisen dat ze alleen bronnen aanvragen als ze er geen hebben; Ten eerste moeten ze al hun huidige resources vrijgeven voordat ze alle resources die ze nodig hebben helemaal opnieuw aanvragen. Ook dit is vaak onpraktisch. Het is zo omdat middelen kunnen worden toegewezen en gedurende lange perioden ongebruikt blijven. Ook kan het zijn dat een proces dat een populaire resource nodig heeft, voor onbepaalde tijd moet wachten, omdat een dergelijke resource altijd aan een proces kan worden toegewezen, wat resulteert in uithongering van resources . (Deze algoritmen, zoals het serialiseren van tokens , staan ​​bekend als de alles-of-niets-algoritmen .)
  • De voorwaarde van geen voorkoop kan ook moeilijk of onmogelijk te vermijden zijn, omdat een proces gedurende een bepaalde tijd over een bron moet kunnen beschikken, of het verwerkingsresultaat kan inconsistent zijn of er kan thrashing optreden. Het onvermogen om voorrang af te dwingen kan echter interfereren met een prioriteitsalgoritme . Voorkoop van een "uitgesloten" bron impliceert over het algemeen een terugdraaiing en moet worden vermeden omdat dit zeer kostbaar is in overhead. Algoritmen die voorkoop mogelijk maken, zijn onder meer lock-free en wait-free algoritmen en optimistische gelijktijdigheidscontrole . Als een proces enkele bronnen bevat en vraagt ​​om een ​​of meer andere bronnen die er niet onmiddellijk aan kunnen worden toegewezen, kan de voorwaarde worden verwijderd door alle momenteel vastgehouden bronnen van dat proces vrij te geven.
  • De laatste voorwaarde is de circulaire wachtvoorwaarde . Benaderingen die circulaire wachttijden vermijden, zijn onder meer het uitschakelen van onderbrekingen tijdens kritieke secties en het gebruik van een hiërarchie om een gedeeltelijke volgorde van resources te bepalen . Als er geen duidelijke hiërarchie bestaat, is zelfs het geheugenadres van bronnen gebruikt om de volgorde te bepalen en worden bronnen gevraagd in oplopende volgorde van de opsomming. Ook de oplossing van Dijkstra kan worden gebruikt.

Livelock

"Livelock" richt hier opnieuw. Voor de videogame, zie Livelock (videogame) .

Een livelock is vergelijkbaar met een deadlock, behalve dat de toestanden van de processen die betrokken zijn bij de livelock voortdurend veranderen ten opzichte van elkaar, geen vooruitgang.

De term werd bedacht door Edward A. Ashcroft in een paper uit 1975 in verband met een onderzoek naar boekingssystemen van luchtvaartmaatschappijen. Livelock is een speciaal geval van uithongering van hulpbronnen ; de algemene definitie stelt alleen dat een bepaald proces niet vordert.

Livelock is een risico bij sommige algoritmen die deadlock detecteren en herstellen . Als meer dan één proces actie onderneemt, kan het algoritme voor deadlockdetectie herhaaldelijk worden geactiveerd. Dit kan worden voorkomen door ervoor te zorgen dat slechts één proces (willekeurig of met prioriteit) actie onderneemt.

Gedistribueerde impasse

Gedistribueerde impasses kunnen optreden in gedistribueerde systemen wanneer gedistribueerde transacties of gelijktijdigheidscontrole worden gebruikt.

Gedistribueerde deadlocks kunnen worden gedetecteerd door ofwel een globale wait-for-grafiek te construeren op basis van lokale wait-for-grafieken bij een deadlock-detector of door een gedistribueerd algoritme zoals edge-chasing .

Fantoomdeadlocks zijn impasses die ten onrechte worden gedetecteerd in een gedistribueerd systeem als gevolg van interne systeemvertragingen, maar die niet echt bestaan.

Als een proces bijvoorbeeld een resource R1 vrijgeeft en een verzoek om R2 doet , en het eerste bericht is verloren of vertraagd, kan een coördinator (detector van deadlocks) ten onrechte een deadlock sluiten (als het verzoek om R2 terwijl het hebben van R1 een impasse).

Zie ook

Referenties

Verder lezen

Externe links