Don't miss an insight. Subscribe to Techopedia for free.


Dekker’s Algorithm

What Does Dekker’s Algorithm Mean?

Dekker’s algorithm is the first known algorithm that solves the mutual exclusion problem in concurrent programming. It is credited to Th. J. Dekker, a Dutch mathematician who created the algorithm for another context. Dekker’s algorithm is used in process queuing, and allows two different threads to share the same single-use resource without conflict by using shared memory for communication.


Techopedia Explains Dekker’s Algorithm

Dekker’s algorithm will allow only a single process to use a resource if two processes are trying to use it at the same time. The highlight of the algorithm is how it solves this problem. It succeeds in preventing the conflict by enforcing mutual exclusion, meaning that only one process may use the resource at a time and will wait if another process is using it. This is achieved with the use of two "flags" and a "token". The flags indicate whether a process wants to enter the critical section (CS) or not; a value of 1 means TRUE that the process wants to enter the CS, while 0, or FALSE, means the opposite. The token, which can also have a value of 1 or 0, indicates priority when both processes have their flags set to TRUE.

This algorithm can successfully enforce mutual exclusion but will constantly test whether the critical section is available and therefore wastes significant processor time. It creates the problem known as lockstep synchronization, in which each thread may only execute in strict synchronization. It is also non-expandable as it only supports a maximum of two processes for mutual exclusion.


Related Terms