Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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 @
Operating Systems

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.

do {
    //entry section
        critical section
    //exit section
        remainder section
} while (TRUE);

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

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

Frequently Asked Questions

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.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio. 

Previous article
Peterson’s Solution in OS
Next article
Bakery Algorithm in OS
Live masterclass