Dödlig låsning

Dödlig låsning (eng. deadlock)är en situation inom t ex logistik eller programmering där resurser allokerats på ett sådant sätt av olika processer att ingen av processerna kan slutföra sitt åtagande och återlämna resurser. Processerna väntar på varandra och ingen kan bli färdig, detta är programmeringens moment 22. Situationen kan lösas antingen genom att en av processerna tillförs mer resurser så att den kan bli klar, eller att någon av processerna backas så att dess resurser frigörs.

Exempel 1:Om två tåg kör från var sitt håll in på en enkelspårig järnväg (antag att de bromsar vid mötet, inte krockar) leder det till en dödlig låsning. Här finns ingen möjlighet att tilldela någon mer resurser, det blir för krångligt att bygga ett nytt spår. Ett av tågen måste backa tillbaka tills det blir dubbelspår igen så att tågen kan mötas. Därefter får tåget som backade tillgång till hela enkelspåret och kan köra vidare.

Exempel 2:En byggmästare vill låna en miljon av banken för att bygga ett hus som han sedan ska sälja. Banken lånar bara ut en halv miljon och huset börjar byggas. När pengarna är slut är huset halvfärdigt. Byggmästaren kan inte sälja sitt halvfärdiga hus och banken kan därför inte få tillbaka sina pengar. Det hjälper inte ens om han skulle riva det halvfärdiga huset. Dödlig låsning. Banken kan lösa detta genom att låna ut ytterligare en halv miljon, byggmästaren bygger färdigt, säljer huset och återlämnar pengarna.

I verkligheten förekommer dock många fall där en process varken kan backas eller tilldelas mer resurser. Då ger en dödlig låsning stora problem.

Edsger Dijkstra formulerade en algoritm för detta, bankiralgoritmen (bankers algorithm) som anger hur resurser får allokeras i ett system. För att den ska fungera i praktiken utan att göra systemet ineffektivt måste emellertid systemet vara konstruerat på ett sådant sätt att resurser kan allokeras och återlämnas i lämpliga mängder, t.ex. bör enkelspåriga järnvägar ha mötesplatser med dubbelspår med jämna mellanrum.

Se även:

• Ger du dig?

Redigera?

Artikeln skriven 2009-01-18 av Learning4sharing

Inga kategorier för denna artikel än...

Intresserad av fler artiklar?

Det romerska namnskicket
New York Dolls
Clarté
Tivedens nationalpark
Tre små gummor
Hopelandish
Alleanza Nazionale
Umberto Bossi
S 13