Vad är Avoidance (undvikande strategi)?

Avoidance (undvikande strategi) är en metod för att förhindra dödläge (Deadlock) genom att noggrant kontrollera resursallokering i systemet. Det innebär att systemet analyserar den aktuella resursstatusen och förutsäger framtida processförfrågningar för att endast tilldela resurser i ett säkert tillstånd (Safe State).

Table of Contents

Vad är dödläge (Deadlock)?

Dödläge uppstår när två eller flera processer väntar på resurser som är låsta av varandra, vilket leder till att ingen av dem kan fortsätta sin exekvering. Det betyder att processer fastnar i ett tillstånd där de aldrig får de resurser de behöver för att avslutas.

Villkor för dödläge (Coffmans villkor)

För att dödläge ska inträffa måste följande fyra villkor vara uppfyllda samtidigt:

Ömsesidig uteslutning (Mutual Exclusion): En resurs kan endast användas av en process åt gången.
Hålla och vänta (Hold and Wait): En process som redan har tilldelats resurser väntar på ytterligare resurser.
Ingen preemption (No Preemption): Resurser kan inte tvångsmässigt tas tillbaka från en process.
Cirkulär väntan (Circular Wait): En kedja av processer existerar där varje process väntar på en resurs som innehas av nästa process i kedjan.

Om dessa fyra villkor uppfylls samtidigt inträffar ett dödläge. Därför måste minst ett av dessa villkor brytas för att förhindra dödläge.

Metoder för att lösa dödläge

Det finns fyra huvudsakliga metoder för att hantera dödläge:

Förebyggande (Prevention): Eliminerar ett eller flera av Coffmans villkor för att förhindra dödläge.
Undvikande (Avoidance): Kontrollerar resursallokering och förhindrar att systemet går in i en osäker tillstånd.
Upptäckt (Detection): Identifierar när ett dödläge har inträffat och vidtar åtgärder för att lösa det.
Återställning (Recovery): Avbryter processer eller frigör resurser för att bryta dödläget.

Den mest använda metoden för undvikande av dödläge är bankirens algoritm (Banker’s Algorithm).

Bankirens algoritm

Bankirens algoritm, utvecklad av Edsger W. Dijkstra, är en metod där systemet bedömer om en viss resursallokering kan leda till dödläge innan den genomförs.

Grundläggande begrepp i algoritmen

För att algoritmen ska fungera krävs följande information:

Max (maximala resursbehov): Det maximala antalet resurser som en process kan behöva.
Allocation (allokerade resurser): Resurser som redan är tilldelade till en process.
Need (kvarvarande behov): De resurser som fortfarande behövs för att processen ska kunna slutföras (Need = Max – Allocation).
Available (tillgängliga resurser): De resurser som för närvarande inte är tilldelade och kan användas av processerna.

Hur algoritmen fungerar

Kontroll av säkert tillstånd: Systemet kontrollerar om tilldelning av resurser kommer att leda till ett tillstånd där alla processer kan slutföras.
Resursförfrågan och tilldelning:
- Om en process begär resurser kontrollerar systemet om det är säkert att bevilja förfrågan.
- Om det är säkert beviljas resurserna.
- Om det är osäkert förblir processen i väntetillstånd tills resurser är tillgängliga.
Frigörande av resurser: När en process avslutas returneras de resurser den använde till systemet.

Exempel på bankirens algoritm

Anta att vi har följande processer och resurser:

Process	Max (Maximalt behov)	Allocation (Tilldelat)	Need (Kvarvarande behov)
P1	(7, 5, 3)	(0, 1, 0)	(7, 4, 3)
P2	(3, 2, 2)	(2, 0, 0)	(1, 2, 2)
P3	(9, 0, 2)	(3, 0, 2)	(6, 0, 0)
P4	(2, 2, 2)	(2, 1, 1)	(0, 1, 1)
P5	(4, 3, 3)	(0, 0, 2)	(4, 3, 1)

Om de tillgängliga resurserna är (3, 3, 2) kontrollerar algoritmen om det är säkert att tilldela resurser till en process. Om en process kan få sina resurser och slutföras kommer dess resurser att återföras, vilket möjliggör att andra processer kan slutföras.

Fördelar och nackdelar med Avoidance

Fördelar

Förhindrar dödläge innan det inträffar.
Processer fastnar inte i en oändlig väntan.

Nackdelar

Kräver att varje process anger sitt maximala resursbehov i förväg.
Kan leda till prestandaförsämring eftersom förfrågningar måste kontrolleras innan de beviljas.
Mindre flexibel i dynamiska system där resursbehov förändras över tid.

Slutsats

Avoidance är en effektiv metod för att förhindra dödläge genom att systemet endast beviljar resursförfrågningar som håller det i ett säkert tillstånd. Bankirens algoritm är en av de mest använda teknikerna för detta ändamål.

Dock kräver denna metod att alla processers maximala resursbehov är kända i förväg, och att systemet kontinuerligt övervakar resursanvändningen. Alternativa strategier för att hantera dödläge inkluderar förebyggande, upptäckt och återställning, där valet av metod beror på systemets behov och krav.

Vad är Information Hiding (Informationsdöljning)?