Introduction
Before we start with the discussion, make sure you have a detailed understanding of Interprocess communication and process synchronization.
Let us start with our topic:
In the above animation, Both the Robot wants to increase the given value by 1.
When the Blue robot accesses the given value and increments it, we do not face any ambiguity, but when both of them try to increment the value simultaneously, then there arises a problem, and the result does not come in our favor.
Both of them incremented the value, but since they did it at the same time, the value was incremented only once. This condition is known as the Race condition in which the resources are being shared concurrently to more than one process.
To solve this problem, we learn Dekker’s Algorithm.
In this article, we will learn about Dekker’s Algorithm, which will solve this problem and its different versions.
Also see, Multiprogramming vs Multitasking, Open Source Operating System
Dekker’s Algorithm
Several methods have been implemented to achieve mutual exclusion, bounded waiting, and progress, one of which is Dekker's Algorithm. To understand the algorithm, we must first comprehend the answer to the critical section problem.
 You can also try this code with Online C Compiler |
The logic for Dekker’s Algorithm is divided into 2 parts: the critical section and the remainder section. A critical section is a section considered as an entry point of the program or a process. And after the process gets completed, the remainder section handles the exit part of the program, like how the output of the program is handled.
The solution to the critical section problem must ensure the following three conditions:
- Mutual Exclusion
- Progress
- Bounded Waiting
Peterson's Solution is one of the solutions for ensuring that all factors are taken into account.
Dekker's Solution or Dekker’s Algorithm is another option. The first likely-correct solution to the critical section problem was Dekker's algorithm. It enables two threads to share a single-use resource without interfering with each other, and it relies solely on shared memory for communication. It was one of the earliest mutual exclusion algorithms to be created, and it avoids the tight alternation of a naive turn-taking algorithm.
Although Dekker's Solution has several versions, the final or fifth version is the most efficient and meets all of the above requirements.
Let us now look at the approach that Dekker’s algorithm implies:
Approach
If two processes try to access a resource simultaneously, Dekker's algorithm will allow only one of them to use it. It prevents conflict by imposing mutual exclusion, which means that only one process can access the resource and wait if another is doing so.
Version 1 of Dekker’s Algorithm
The idea is to use a shared or common thread no. between processes and stop the other process from entering its critical section if the common thread indicates the former one is already running.
Code:
Thread1(){
do {
/* entry section
wait until thread_no is 1 */
while (thread_no == 2)
continue;
/* critical section
exit section
give access to the other thread */
thread_no = 2;
// remainder section
} while (completed == false)
}
Thread2(){
do {
/* entry section
wait until thread_no is 2 */
while (thread_no == 1)
continue;
/* critical section
exit section
give access to the other thread */
thread_no = 1;
// remainder section
} while (completed == false)
}
main(){
int thread_no = 1;
startThreads();
}
Drawback
The problem of this first version of Dekker’s algorithm is the implementation of lockstep synchronization. It means that each thread is dependent on the execution of the others. Once one of the two processes has completed its execution, the second process will begin. It then grants access to the completed one and awaits its execution. The completed one, on the other hand, would never run, and so would never return access to the second process. As a result, the second process waits an indefinite amount of time.
Version 2 of Dekker’s Algorithm
Lockstep synchronization is removed in the second version of Dekker's algorithm. It is accomplished by using two flags to identify the current status of the item and updating them appropriately at the entrance and exit sections.
Code:
Thread_1()
{
do {
/* entry section
wait until thread_2 is in its critical section */
while (thread_2 == true)
continue;
// indicate thread_1 entering its critical section
thread_1 = true;
/* critical section
exit section
indicate thread_1 exiting its critical section*/
thread_1 = false;
// remainder section
} while (completed == false)
}
Thread_2()
{
do {
/*entry section
wait until thread_1 is in its critical section */
while (thread_1 == true)
continue;
// indicate thread_2 entering its critical section
thread_2 = true;
/* critical section
exit section
indicate thread_2 exiting its critical section */
thread_2 = false;
// remainder section
} while (completed == false)
}
Main()
{
/* flags to indicate if each thread is in
its critical section or not. */
bool thread_1 = false;
bool thread_2 = false;
startThreads();
}
Drawback
In this version, mutual exclusion is violated. If threads are preempted during flag update, both threads enter the critical section. When the preemption thread is restarted, the same thing happens in the beginning, when both flags are false.
Version 3 of Dekker’s Algorithm
It sets the flags before the entry section itself to re-ensure mutual exclusion.
Code:
Thread1()
{
do {
thread_1_wants_to_enter = true;
/* entry section
wait until thread_2 wants to enter
its critical section */
while (thread_2_wants_to_enter == true)
continue;
// critical section
/* exit section
indicate thread_1 has completed
its critical section */
thread_1_wants_to_enter = false;
// remainder section
} while (completed == false)
}
Thread2()
{
do {
thread_2_wants_to_enter = true;
/* entry section
wait until thread_1 wants to enter
its critical section */
while (thread_1_wants_to_enter == true)
continue;
// critical section
/* exit section
indicate thread_2 has completed
its critical section */
thread_2_wants_to_enter = false;
// remainder section
} while (completed == false)
}
Main()
{
/* flags to indicate if each thread is in
queue to enter its critical section */
bool thread_1_wants_to_enter = false;
bool thread_2_wants_to_enter = false;
startThreads();
}
Drawback
The problem of mutual exclusion was not solved in this version also. It also raises the chance of a deadlock, as both threads may get the flag at the same moment, causing them to wait indefinitely.
Version 4 of Dekker’s Algorithm
This version of Dekker's algorithm solves the problem of mutual exclusion and deadlock by setting the flag to false for a short period.
Code:
Thread1(){
do {
thread_1_wants_to_enter = true;
while (thread_2_wants_to_enter == true) {
/* gives access to other thread
wait for random amount of time */
thread_1_wants_to_enter = false;
thread_1_wants_to_enter = true;
}
/* entry section
wait until thread_2 wants to enter
its critical section
critical section
exit section
indicate thread_1 has completed
its critical section */
thread_1_wants_to_enter = false;
// remainder section
} while (completed == false)
}
Thread2(){
do {
thread_2_wants_to_enter = true;
while (thread_1_wants_to_enter == true) {
/* gives access to other thread
wait for random amount of time */
thread_2_wants_to_enter = false;
thread_2_wants_to_enter = true;
}
/* entry section
wait until thread_1 wants to enter
its critical section
critical section
exit section
indicate thread_2 has completed
its critical section */
thread_2_wants_to_enter = false;
// remainder section
} while (completed == false)
}
main(){
/* flags to indicate whether each thread is in
queue to enter its critical section */
bool thread_1_wants_to_enter = false;
bool thread_2_wants_to_enter = false;
startThreads();
}
Drawback
This version’s issue is an indefinite postponement. Because the amount of time spent on a random basis varies depending on the algorithm's situation, it is not acceptable in business-critical systems.
Version 5 of Dekker’s Algorithm
In this version, the entry to the critical section is determined by the favored thread notion. Resolving the issue over which thread should run first, ensures mutual exclusion and avoids deadlock, indefinite postponement, or lockstep synchronization. This version of Dekker's algorithm solves critical section problems in its entirety.
Thread1(){
do {
thread_1_wants_to_enter = true;
/* entry section
wait until thread_2 wants to enter
its critical section */
while (thread_2_wants_to_enter == true) {
// if 2nd thread is more favored
if (favoured_thread == 2) {
// gives access to other thread
thread_1_wants_to_enter = false;
// wait until this thread is favored
while (favoured_thread == 2);
thread_1_wants_to_enter = true;
}
}
/* critical section
favor the 2nd thread */
favoured_thread = 2;
/* exit section
indicate thread_1 has completed
its critical section */
thread_1_wants_to_enter = false;
// remainder section
} while (completed == false)
}
Thread2(){
do {
thread_2_wants_to_enter = true;
/* entry section
wait until thread_1 wants to enter
its critical section */
while (thread_1_wants_to_enter == true) {
// if 1st thread is more favored
if (favoured_thread == 1) {
// gives access to other thread
thread_2_wants_to_enter = false;
// wait until this thread is favored
while (favoured_thread == 1);
thread_2_wants_to_enter = true;
}
}
/* critical section
favour the 1st thread */
favoured_thread = 1;
/* exit section
indicate thread_2 has completed
its critical section */
thread_2_wants_to_enter = false;
// remainder section
} while (completed == false)
}
main(){
// to denote which thread will enter next
int favoured_thread = 1;
/* flags to indicate whether each thread is in
queue to enter its critical section */
bool thread_1_wants_to_enter = false;
bool thread_2_wants_to_enter = false;
startThreads();
}
This version guarantees a complete solution to the critical solution problem.
Also Read - Kadanes Algorithm
Must Read Evolution of Operating System
248+ registered 
