Dödläge

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 juli 2019; kontroller kräver 16 redigeringar .

Deadlock (förkortat deadlock ) är en  situation i en multitasking-miljö eller DBMS där flera processer väntar på resurser upptagna av varandra, och ingen av dem kan fortsätta sin exekvering [1] .

Det enklaste exemplet på dödläge

Steg Process 1 Process 2
0 Vill fånga A och B, börjar med A Vill fånga A och B, börjar med B
ett Beslagtar resurs A Beslagtar resurs B
2 Väntar på att resurs B ska bli ledig Väntar på att resurs A ska bli ledig
3 Dödläge

Avlusning av dödlägen, såväl som andra synkroniseringsfel , kompliceras av det faktum att för att de ska inträffa krävs specifika villkor för samtidig exekvering av flera processer (i exemplet ovan, om process 1 hade lyckats fånga resurs B före process 2, då skulle felet inte ha uppstått).

Dynamiskt dödläge

Dynamiskt dödläge ( eng.  livelock ) betyder denna situation: systemet "fastnar inte" (som i ett vanligt dödläge), utan är engagerat i värdelöst arbete, dess tillstånd förändras ständigt - men ändå är det " loopat ", ger inget användbart arbete.

Ett verkligt exempel på en sådan situation: två människor möts ansikte mot ansikte. Var och en av dem försöker kliva åt sidan, men de skingras inte utan rör sig i samma riktning i flera sekunder.

Detektering av dödläge

Sökandet efter ömsesidig blockering utförs genom att konstruera och analysera den väntande grafen . I den väntande grafen markerar noder processer och objekt. Lås är markerade med kanter riktade från den nod som motsvarar det fångade objektet till den nod som motsvarar den process som har fångat det. Väntor är markerade med kanter riktade från noden som motsvarar vänteprocessen till noden som motsvarar det förväntade objektet.

Cykeln i väntediagrammet motsvarar ett dödläge . Det finns en speciell algoritm för att hitta cykler i en graf .

Det finns algoritmer för borttagning av dödläge . Samtidigt kan exekveringen av sökalgoritmer för borttagning av mutex leda till dynamiskt dödläge - ett mutex skapas, återställs, omformas, återställs igen och så vidare.

Dessutom implementeras dessa algoritmer av resurshanteraren, programmet som ansvarar för låsning och upplåsning. Om däremot en del av resurserna som används i låset tilldelas av någon annan är dödlägesdetektering inte möjlig. Till exempel upptäcker Oracle DBMS ett dödläge av förfrågningar till sina databaser, men om objekten i exemplet ovan är ett fält i databasen och till exempel en fil på hårddisken, kommer dödläget inte att upptäckas - DBMS bearbetar inte denna fil och för den är dödläget nr.

I praktiken bör elimineringen av dödlägen tas om hand i designstadiet av systemet - detta är det enda mer eller mindre pålitliga sättet att hantera dem. I det extrema fallet, när huvudkonceptet inte tillåter möjligheten att undvika dödlägen, bör du åtminstone bygga alla resursförfrågningar så att sådana lås tas bort smärtfritt.

Deadlock Prevention

Det klassiska sättet att hantera problemet är att utveckla en låshierarki: ett jämförelseförhållande upprättas mellan lås och en regel införs för att förbjuda fångst av ett "större" lås i ett tillstånd där ett "mindre" redan har fångats. . Således, om en process behöver flera lås, bör den alltid börja med det "största" låset - efter att ha släppt eventuella "mindre" lås som det innehåller, om några - och sedan i fallande ordning. Detta kan leda till onödiga åtgärder (om det "mindre" låset behövs och redan förvärvats, släpps det bara för att omedelbart skaffas igen), men det kommer garanterat att lösa problemet.

I vissa fall, särskilt i modulariserade system, komplicerar detta också arkitekturen. Så, till exempel, i ett gränssnitt mellan moduler måste du introducera anrop som inte gör något annat än att fånga och släppa några lås i modulen. Detta tillvägagångssätt används i Windows -filsystem i deras gränssnitt med undersystemen för cache och virtuellt minne.

Andra algoritmer:

Algoritmer och metoder för att förhindra dödläge
namn Coffmans  villkor Beskrivning
Bankers  algoritm ömsesidig uteslutning Bankers Algorithm är en resursallokerings-  och dödlägesbypass-algoritm utvecklad av  E. Dijkstra .
Rekursiv låsförebyggande algoritm ömsesidig uteslutning Förhindrar att en tråd får samma lås flera gånger.

Se även

Anteckningar

  1. ↑ Quittner 1980 , sid. 334-337.

Litteratur

Länkar

  Gå till Wikidata-objektet  Ordböcker och uppslagsverk