Dekker-Algorithmus: Unterschied zwischen den Versionen
Singh (Diskussion | Beiträge) |
Singh (Diskussion | Beiträge) |
||
Zeile 27: | Zeile 27: | ||
==Funktionsweise== | ==Funktionsweise== | ||
− | Dieser Algorithmus arbeitet wie der Peterson-Algorithmus mit drei Variablen. Mit Ausnahme das die <code>turn</code> Variable als Schlüssel fungiert. Die beiden Flaggen werden mit dem boolischen Wert <code>false</code> deklariert. Die <code>turn</code> Variable wird auf <code>0</code> gesetzt. Beide Prozesse setzen Ihre Flaggen auf true und treten somit in die while-Schleife ein, weil die Bedingung erfüllt ist. Aber bei der if-Verzweigung ist die Bedingung im Prozess 1 nicht mehr erfüllt. Prozess 2 setzt <code>flag2</code> auf <code>false</code>. Jetzt versucht Prozess 1 | + | Dieser Algorithmus arbeitet wie der Peterson-Algorithmus mit drei Variablen. Mit Ausnahme das die <code>turn</code> Variable als Schlüssel fungiert. Die beiden Flaggen werden mit dem boolischen Wert <code>false</code> deklariert. Die <code>turn</code> Variable wird auf <code>0</code> gesetzt. Beide Prozesse setzen Ihre Flaggen auf true und treten somit in die while-Schleife ein, weil die Bedingung erfüllt ist. Aber bei der if-Verzweigung ist die Bedingung im Prozess 1 nicht mehr erfüllt. Prozess 2 setzt <code>flag2</code> auf <code>false</code>. Jetzt versucht Prozess 1 einen erneuten Eintritt in die while-Schleife. Aber dies schlägt fehl, weil die Bedingung für den Schleifeneintritt nicht mehr erfüllt ist und somit wandert Prozess 1 in die kritische Section. Wenn Prozess 1 die kritische Section verlässt setzt er <code>turn</code> auf <code>1</code> und <code>flag1</code> auf <code>false</code>. Man kann also sagen wenn <code>turn</code> auf <code>0</code> gesetzt ist wandert Prozess 1 in die kritische Section und wenn <code>turn</code> auf <code>1</code> gesetzt ist wandert Prozess 2 in die kritische Section. |
[[Kategorie:Algorithmen]] | [[Kategorie:Algorithmen]] |
Aktuelle Version vom 21. Januar 2008, 17:45 Uhr
Der Dekker-Algorithmus (benannt nach Theodorus Dekker) ist ein Algorithmus, genau wie der Peterson-Algorithmus, der das Problem mit dem Eintritt von Prozessen in der kritischen Section löst. Dieser Algorithmus gewährleistet, das nur ein Prozess in der kritischen Section sich befindet.
Pseudo C-Code des Algorithmus
// globale Variablendeklaration boolean flag1 = false; boolean flag2 = false; int turn = 0; // Prozess 1 // Prozess 2 p0: flag1 = true; p1: flag2 = true; '''while''' (flag2) { '''while''' (flag1) { '''if''' (turn != 0) { '''if''' (turn != 1) { flag1 = false; flag2 = false; '''while''' (turn != 0) { '''while''' (turn != 1) { } } flag2 = true; flag2 = true; } } } } // kritischer Abschnitt // kritischer Abschnitt turn = 1; turn = 0; flag1 = false; flag2 = false;
Funktionsweise
Dieser Algorithmus arbeitet wie der Peterson-Algorithmus mit drei Variablen. Mit Ausnahme das die turn
Variable als Schlüssel fungiert. Die beiden Flaggen werden mit dem boolischen Wert false
deklariert. Die turn
Variable wird auf 0
gesetzt. Beide Prozesse setzen Ihre Flaggen auf true und treten somit in die while-Schleife ein, weil die Bedingung erfüllt ist. Aber bei der if-Verzweigung ist die Bedingung im Prozess 1 nicht mehr erfüllt. Prozess 2 setzt flag2
auf false
. Jetzt versucht Prozess 1 einen erneuten Eintritt in die while-Schleife. Aber dies schlägt fehl, weil die Bedingung für den Schleifeneintritt nicht mehr erfüllt ist und somit wandert Prozess 1 in die kritische Section. Wenn Prozess 1 die kritische Section verlässt setzt er turn
auf 1
und flag1
auf false
. Man kann also sagen wenn turn
auf 0
gesetzt ist wandert Prozess 1 in die kritische Section und wenn turn
auf 1
gesetzt ist wandert Prozess 2 in die kritische Section.