Baklås (datavetenskap)

Exempel på hur ett baklås visuellt kan se ut.

Baklås eller dödläge (deadlock på engelska) ä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.[1]

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

  • 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ågra resurser - det är för krångligt att bygga ett nytt spår. Ett av tågen måste backa tills det blir dubbelspårigt 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.
  • En byggmästare vill låna en miljon kronor av banken för att bygga ett hus som han sedan ska sälja. Banken lånar bara ut en halv miljon kronor och huset börjar byggas. När pengarna tar 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. Banken kan lösa detta genom att låna ut ytterligare en halv miljon varpå byggmästaren bygger färdigt huset, säljer huset och återlämnar pengarna.
  • Fyra bilar möts i en 4vägs-korsning och alla 4 hävdar högerregeln dvs ingen kan köra och följaktligen kommer ingen någonstans.

I verkligheten är det vanligt förekommande att det uppstår en process som varken kan backas eller tilldelas resurser, vilket kan orsaka stora problem.

Undvika baklås

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, till exempel bör enkelspåriga järnvägar ha mötesplatser med dubbelspår med jämna mellanrum.

Se även

  • Dödläge (för termens mer allmänna betydelse)

Källor

  1. ^ ”dödläge”. Nationalencyklopedin. http://www.ne.se/d%C3%B6dl%C3%A4ge. Läst 24 september 2013.