Dekkers Algorithmus

Definition - Was bedeutet Dekkers Algorithmus?

Der Dekker-Algorithmus ist der erste bekannte Algorithmus, der das Problem des gegenseitigen Ausschlusses bei der gleichzeitigen Programmierung löst. Es wird Th gutgeschrieben. J. Dekker, ein niederländischer Mathematiker, der den Algorithmus für einen anderen Kontext erstellt hat. Der Dekker-Algorithmus wird in der Prozesswarteschlange verwendet und ermöglicht es zwei verschiedenen Threads, dieselbe Einwegressource ohne Konflikte gemeinsam zu nutzen, indem gemeinsam genutzter Speicher für die Kommunikation verwendet wird.

Technische.me erklärt Dekkers Algorithmus

Mit dem Dekker-Algorithmus kann nur ein einziger Prozess eine Ressource verwenden, wenn zwei Prozesse gleichzeitig versuchen, sie zu verwenden. Das Highlight des Algorithmus ist, wie er dieses Problem löst. Es gelingt, den Konflikt durch Erzwingen des gegenseitigen Ausschlusses zu verhindern. Dies bedeutet, dass jeweils nur ein Prozess die Ressource verwenden darf und wartet, wenn ein anderer Prozess sie verwendet. Dies wird durch die Verwendung von zwei "Flags" und einem "Token" erreicht. Die Flags geben an, ob ein Prozess den kritischen Abschnitt (CS) betreten möchte oder nicht. Ein Wert von 1 bedeutet WAHR, dass der Prozess die CS eingeben möchte, während 0 oder FALSCH das Gegenteil bedeutet. Das Token, das auch den Wert 1 oder 0 haben kann, gibt die Priorität an, wenn für beide Prozesse die Flags auf TRUE gesetzt sind.

Dieser Algorithmus kann den gegenseitigen Ausschluss erfolgreich erzwingen, prüft jedoch ständig, ob der kritische Abschnitt verfügbar ist, und verschwendet daher erhebliche Prozessorzeit. Es entsteht das als Lockstep-Synchronisation bekannte Problem, bei dem jeder Thread möglicherweise nur in strikter Synchronisation ausgeführt wird. Es ist auch nicht erweiterbar, da es nur maximal zwei Prozesse zum gegenseitigen Ausschluss unterstützt.