1.
Introduction
2.
Dekkerâ€™s Algorithm
2.1.
Approach
2.2.
Version 1 of Dekkerâ€™s Algorithm
2.3.
Version 2 of Dekkerâ€™s Algorithm
2.4.
Version 3 of Dekkerâ€™s Algorithm
2.5.
Version 4 of Dekkerâ€™s Algorithm
2.6.
Version 5 of Dekkerâ€™s Algorithm
3.
3.1.
What is mutual exclusion?
3.2.
What are the Disadvantages of Dekkerâ€™s Algorithm?
3.3.
Why does Dekker's algorithm's first version fail?
3.4.
What is a deadlock in OS?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Dekker's Algoirthm

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction

Before we start with the discussion, make sure you have a detailed understanding of Interprocess communication and process synchronization

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.

## 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.

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 */
continue;
/* critical section
exit section
// remainder section
} while (completed == false)
}
do {
/* entry section
wait until thread_no is 2 */
continue;
/* critical section
exit section
// remainder section
} while (completed == false)
}
main(){
}``````

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 */
continue;
// indicate thread_1 entering its critical section
/* critical section
exit section
indicate thread_1 exiting its critical section*/
// remainder section
} while (completed == false)
}

{

do {
/*entry section
wait until thread_1 is in its critical section */
continue;
// indicate thread_2 entering its critical section
/* critical section
exit section
indicate thread_2 exiting its critical section */
// remainder section
} while (completed == false)
}

Main()
{
/* flags to indicate if each thread is in
its critical section or not. */

}``````

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 {

/* entry section
wait until thread_2 wants to enter
its critical section */
continue;

// critical section

/* exit section
its critical section */

// remainder section

} while (completed == false)
}

{
do {

/* entry section
wait until thread_1 wants to enter
its critical section */
continue;
// critical section
/* exit section
its critical section */
// remainder section

} while (completed == false)
}
Main()
{
/* flags to indicate if each thread is in
queue to enter its critical section */

}
``````

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 {
wait for random amount of time */
}
/* entry section
wait until thread_2 wants to enter
its critical section
critical section
exit section
its critical section */
// remainder section
} while (completed == false)
}
do {
wait for random amount of time */
}
/* entry section
wait until thread_1 wants to enter
its critical section
critical section
exit section
its critical section */
// remainder section
} while (completed == false)
}
main(){
/* flags to indicate whether each thread is in
queue to enter its critical section */
}``````

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 {
/* entry section
wait until thread_2 wants to enter
its critical section */
// if 2nd thread is more favored
// wait until this thread is favored
}
}
/* critical section
/* exit section
its critical section */
// remainder section
} while (completed == false)
}
do {
/* entry section
wait until thread_1 wants to enter
its critical section */
// if 1st thread is more favored
// wait until this thread is favored
}
}
/* critical section
/* exit section
its critical section */
// remainder section
} while (completed == false)
}
main(){
// to denote which thread will enter next
/* flags to indicate whether each thread is in
queue to enter its critical section */
}``````

This version guarantees a complete solution to the critical solution problem.

Must Read Evolution of Operating System

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### What is mutual exclusion?

A mutual exclusion (mutex) is a program object that prevents multiple processes from accessing a shared resource at the same time.

### What are the Disadvantages of Dekkerâ€™s Algorithm?

One disadvantage is that it can only handle two processes at a time and uses busy waiting instead of process suspension.

### Why does Dekker's algorithm's first version fail?

The implementation of lockstep synchronization is the problem with this first version of Dekker's algorithm. It means that each thread depends on the execution of the others.

### What is a deadlock in OS?

A deadlock occurs when two computer programs that share the same resource effectively prevent each other from accessing the resource, causing both programs to stop working.

## Conclusion

This article discusses, Dekkerâ€™s Algorithm and its different versions and the code of each version.