Dekkers algoritm

Dekkers algoritm är den första kända korrekta lösningen på problemet med ömsesidig uteslutning vid samtidig programmering där processer endast kommunicerar via delat minne. Lösningen tillskrivs den holländska matematikern Th. J. Dekker av Edsger W. Dijkstra i en opublicerad artikel om sekventiella processbeskrivningar och hans manuskript om samverkande sekventiella processer. Det tillåter två trådar att dela en engångsresurs utan konflikt, och endast använda delat minne för kommunikation.

Den undviker strikt växling av en naiv turtagningsalgoritm och var en av de första algoritmerna för ömsesidig uteslutning som uppfanns.

Översikt

Om två processer försöker komma in i en kritisk sektion samtidigt kommer algoritmen att tillåta endast en process, baserat på vems tur det är. Om en process redan är i det kritiska avsnittet kommer den andra processen att vänta på att den första processen avslutas. Detta görs genom att använda två flaggor, wants_to_enter[0] och wants_to_enter[1] , som indikerar en avsikt att gå in i den kritiska delen av process 0 respektive 1, och en variabel tur som indikerar vem som har prioritet mellan de två processerna.

Dekkers algoritm

Dekkers algoritm kan uttryckas i pseudokod enligt följande. 

variabler vill_att_skriva: array av 2 booleaner tur: heltal vill_att_skriva in[0] ← falskt vill_skriva in[1] ← falsk tur ← 0 // eller 1
 
p0: vill_att_skriva[0] ← sant medan vill_att_inträda[1] { if tur ≠ 0 { vill_att_skriva in[0] ← falskt medan sväng ≠ 0 { // upptagen vänta } vill_att_skriva[0] ← sant } } // kritisk sektion ... sväng ← 1 vill_gå in[0] ← falskt // resterande avsnitt
 
p1: vill_att_skriva[1] ← sant medan vill_att_inträda[0] { if tur ≠ 1 { vill_att_skriva in[1] ← falskt medan tur ≠ 1 { // upptagen vänta } vill_att_skriva[1] ← sant } } // kritisk sektion ... sväng ← 0 vill_gå in[1] ← falskt // resterande avsnitt

Processer indikerar en avsikt att gå in i den kritiska sektionen som testas av den yttre while-slingan. Om den andra processen inte har flaggat avsikt, kan den kritiska sektionen gå in på ett säkert sätt oberoende av den aktuella svängen. Ömsesidig uteslutning kommer fortfarande att garanteras eftersom ingen av processerna kan bli kritiska innan deras flagga ställs in (vilket innebär att minst en process kommer in i while-slingan). Detta garanterar också framsteg eftersom det inte kommer att vänta på en process som har dragit tillbaka avsikten att bli kritisk. Alternativt, om den andra processens variabel ställdes in, skrivs while-slingan in och turnvariabeln kommer att fastställa vem som tillåts bli kritisk. Processer utan prioritet kommer att dra tillbaka sin avsikt att gå in i den kritiska delen tills de prioriteras igen (den inre while-slingan). Processer med prioritet kommer att bryta från while-slingan och gå in i sin kritiska sektion.

Dekkers algoritm garanterar ömsesidig uteslutning , frihet från dödläge och frihet från svält . Låt oss se varför den sista fastigheten håller. Anta att p0 har fastnat i while wants_to_enter[1] -slingan för alltid. Det finns frihet från dödläge, så så småningom kommer p1 att fortsätta till sin kritiska sektion och sätta tur = 0 (och värdet på tur kommer att förbli oförändrat så länge som p0 inte går framåt). Så småningom kommer p0 att bryta ut ur den inre medan sväng ≠ 0 slinga (om den någonsin satt fast på den). Efter det kommer den att ställa in wants_to_enter[0] till sant och sätta sig i väntan på att wants_to_enter[1] ska bli falsk (eftersom turn = 0 kommer den aldrig att utföra åtgärderna i while-loopen). Nästa gång p1 försöker komma in i sin kritiska sektion, kommer den att tvingas utföra åtgärderna i sin while wants_to_enter[0] -loop. Speciellt kommer den så småningom att ställa in wants_to_enter[1] på false och fastna i while-svängen ≠ 1 slinga (eftersom svängen förblir 0). Nästa gång kontrollen övergår till p0 kommer den att lämna while wants_to_enter[1] -slingan och gå in i dess kritiska sektion.

Om algoritmen modifierades genom att utföra åtgärderna i slingan while wants_to_enter[1] utan att kontrollera om turn = 0 , så finns det en möjlighet att svälta. Därför är alla steg i algoritmen nödvändiga.

Anteckningar

En fördel med denna algoritm är att den inte kräver speciella test-and-set (atomic read/modify/write) instruktioner och är därför mycket portabel mellan språk och maskinarkitekturer. En nackdel är att den är begränsad till två processer och använder upptagen väntan istället för processavstängning. (Användningen av upptagen väntan tyder på att processer bör spendera ett minimum av tid inne i den kritiska delen.)

Moderna operativsystem tillhandahåller primitiver för ömsesidig uteslutning som är mer generella och flexibla än Dekkers algoritm. Men i avsaknad av faktiska konflikter mellan de två processerna, är in- och utträde från kritisk sektion extremt effektiv när Dekkers algoritm används.

Många moderna CPU: er exekverar sina instruktioner på ett ur funktion; även minnesåtkomster kan ordnas om (se minnesordning ) . Denna algoritm fungerar inte på SMP- maskiner utrustade med dessa CPU:er utan användning av minnesbarriärer .

Dessutom kan många optimerande kompilatorer utföra transformationer som gör att denna algoritm misslyckas oavsett plattform. På många språk är det lagligt för en kompilator att upptäcka att flaggvariablerna wants_to_enter[0] och wants_to_enter[1] aldrig nås i slingan. Den kan sedan ta bort skrivningarna till dessa variabler från slingan, med hjälp av en process som kallas loop-invariant kodrörelse . Det skulle också vara möjligt för många kompilatorer att upptäcka att turvariabeln aldrig modifieras av den inre slingan och utföra en liknande transformation, vilket resulterar i en potentiell oändlig slinga . Om någon av dessa transformationer utförs kommer algoritmen att misslyckas, oavsett arkitektur.

För att lindra detta problem bör flyktiga variabler markeras som modifierbara utanför omfånget för det aktuella exekverande sammanhanget. Till exempel i C# eller Java skulle man annotera dessa variabler som "flyktiga". Observera dock att C/C++ "volatile"-attributet endast garanterar att kompilatorn genererar kod med rätt ordning; den inkluderar inte de nödvändiga minnesbarriärerna för att garantera att koden körs i ordning . C++11 atomvariabler kan användas för att garantera lämpliga ordningskrav — som standard är operationer på atomvariabler sekventiellt konsekventa så om variablerna wants_to_enter och turn är atomära kommer en naiv implementering "bara att fungera". Alternativt kan beställning garanteras genom explicit användning av separata stängsel, med last- och butiksverksamhet med en avslappnad beställning.

Se även

Hämtad från " https://en.wikipedia.org/w/index.php?title=Dekker%27s_algorithm&oldid=1123217173 "