Dödläge

Hur aktiva och passiva dödlägen (livelock och deadlock) uppstår och problemet kan lösas

Litteratur

Lea: Concurrent programming in Java, avsnitt 2.2.5-2.2.6

Hur uppstår ett passivt dödläge?

Ett passivt dödläge innebär att två eller fler trådar allihop har låst något objekt (eller någon annan resurs som till exempel skrivare, bildskärm, minnesutrymme) och väntar på något annat objekt som någon annan av trådarna har låst. Inträffar detta kommer ingen av trådarna någonsin mer att få exekvera eftersom alla väntar på något lås som aldrig blir ledigt därför att den som skulle låsa upp det också ligger och väntar. Detta illustreras av bilden på sid 87.

Ett passivt dödläge uppstår om följande fyra villkor är uppfyllda (de brukar kallas Coffmans villkor):

  1. Exklusivt ägande

    2. Endast en tråd i taget har tillträde till en viss resurs. Om en resurs ägs av en tråd och någon annan tråd vill ha den måste den vänta. Javas synchronized fungerar på detta sätt.
  2. Allokerat och begärt

    3. Det måste finnas en tråd som äger en resurs och väntar på andra resurser som ägs av andra trådar.
  3. Oavbruten allokering

    4. En resurs, tex en synkroniserad metod, kan bara lämnas frivilligt. I Java uppfylls detta villkor genom att javamotorn aldrig tvingar en tråd att lämna ett synkroniserat block och låsa upp det objektets lås.
  4. Cirkulär kedja av väntande processer

    5. Det måste finnas ett antal trådar, kalla dem t0, t1, ..., tn, där t0 väntar på t1, t1 väntar på t2, ..., tn-1 väntar på tn och tn väntar på t0.
Villkoren är inte oberoende av varandra. Nummer fyra kan inte uppfyllas om inte nummer två är uppfyllt.

Hur hanteras problem med passiva dödlägen?

Vi vill naturligtvis inte att ett passivt dödläge ska uppstå. Några vanliga metoder att hantera problemet är dessa:

Förebygga

Om inte samtliga Coffmans villkor är uppfyllda blir det inget passivt dödläge. Vi kan därför redan när programmet konstrueras försäkra oss om att det aldrig uppstår något genom att se till att minst ett av villkoren aldrig uppfylls.

Avsnitt 2.2.6 beskriver en metod att bryta mot villkor nummer fyra. Den går ut på att numrera alla objekt och låta alla trådar begära låsen i nummerordning. En tråd som har tagit lås nummer ett kommer därmed aldrig att behöva vänta på någon annan tråd eftersom ingen annan kan "köra om den" och låsa låset till ett objekt med högre nummer. Med andra ord kommer kommer den delan av villkor fyra som innebär att tn väntar på t0 aldrig att inträffa.

En  möjlighet att bryta mot villkor nummer två är att låta trådarna begära alla resurser de behöver (till exempel låsa alla lås) på en gång. Om en tråd inte får allihopa måste den lämna tillbaks de den redan fått. Detta är lite klurigt att implementera i Java eftersom det inte går att kolla om ett lås är ledigt när en tråd går in i ett synkroniserat block.

Upptäcka

Det finns flera metoder att upptäcka om ett dödläge uppstår. En är att systemet har en lista över vilka processer/trådar som väntar på vilka. Denna lista analyseras vid lämpliga tillfällen (till exempel när ready queue är tom) och om en cirkulär väntan (villkor nummer fyra) finns avslutas en av trådarna. Sådana här algoritmer tar en hel del tid att exekvera så det är förmodligen bara i stora system med relativ hög risk för passiva dödlägen som det är relevent att använda dem.

Ignorera

Enkelt och smärtfritt så länge det fungerar. Denna metod används av många operativsystem och även av javamotorn.

Aktiva dödlägen

Ett aktivt dödläge innebär att en eller fler trådar exekverar utan att göra någon nytta. Ett sådant kan uppstå till exempel i nedanstående kod:
boolean failure = true;
while (failure) {
    try {
        methodThatCanThrowException();
        failure = false;
    }
    catch ( Exception e ) {}
}
Tanken är att metoden metodThatCanThrowException() ska anropas tills anropet lyckas. Men om anropet aldrig lyckas blir vi kvar i loopen för evigt, ett aktivt dödläge har uppstått.

Det finns tyvärr inga kända metoder varken för att förhindra att aktiva dödlägen uppstår eller för att upptäcka att de har uppstått.