Wróć do bloga
Encyklopedia30 listopada 2020

Dekker's algorithm

Dekker's algorithm

Dekker's algorithm – pierwsze znane poprawne rozwiązanie problemu wzajemnego wykluczania w programowaniu współbieżnym bez konfliktów, wykorzystując do komunikacji tylko pamięć współdzieloną.

W sytuacji kiedy dwa procesy będą próbowały wejść do sekcji krytycznej w tym samym czasie, algorytm dopuści tylko jeden proces, w zależności od tego, czyja jest kolej. Jeśli jeden proces znajduje się już w sekcji krytycznej, drugi proces będzie zajęty, czekając na to aż pierwszy proces opuści sekcje krytyczną.

Rozwiązanie to zostało przypisane holenderskiemu matematykowi Th. J. Dekker’owi.

Istnieje 5 wersji algorytmu Dekker’a, wersja 5 będąca finalną uznawana jest za tą, która w najlepszy sposób rozwiązuje problem wzajemnego wykluczania i jest najbardziej wydajna spośród wszystkich wersji.