Baklås (datavetenskap)

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

Baklås (en:deadlock) är en situation inom till exempel logistik eller programmering där två (eller flera) processer är inblandade och där var och en av processerna väntar på att den andra processen ska återlämna en resurs vilken krävs för att den första processen ska kunna bli klar med sitt åtagande. 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 och därefter återlämna resurserna, 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 baklås. 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, pengarna är redan förbrukade. Baklås. 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 ett baklås stora problem.

Edsger Dijkstra formulerade en algoritm för detta, bankiralgoritmen (Banker's algorithm), som anger villkor för 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.

Personliga verktyg