Process Synchronization Two Process Solution) (Algo-3) l Decker’s Algorithm.

Process Synchronization Two Process Solution) (Algo-3) l Decker’s Algorithm.

play-rounded-fill play-rounded-outline play-sharp-fill play-sharp-outline
pause-sharp-outline pause-sharp-fill pause-rounded-outline pause-rounded-fill
00:00

Dekker’s Algorithm – Process Synchronization (Two-Process Solution) (Algo-3)

Dekker’s Algorithm is one of the earliest known solutions to the critical section problem for two processes running in a shared memory environment. It ensures mutual exclusion, progress, and bounded waiting.



Problem: Process Synchronization

When multiple processes access shared resources, they need to be synchronized to avoid race conditions and ensure consistency.

Solution: Dekker’s Algorithm

Dekker’s Algorithm uses the following mechanisms:

  1. Flags (want[2]) – Indicates if a process wants to enter the critical section.
  2. Turn Variable – Specifies which process has priority.

Algorithm Steps:

1. Initialization:

  • want[0] = want[1] = false (Initially, both processes do not want to enter.)
  • turn = 0 (Process 0 gets priority initially.)

2. Entry Section:

  • A process sets its want[i] = true (indicating interest).
  • If the other process (j) also wants to enter:
    • The process waits if it is not its turn.
    • If it’s not its turn, it sets want[i] = false and retries later.

3. Critical Section (CS):

  • The process executes its critical section.

4. Exit Section:

  • The process sets want[i] = false.
  • Gives the turn to the other process (turn = j).

Dekker’s Algorithm (Code Implementation in C++)

#include <iostream>
#include <thread>
#include <atomic>
using namespace std;atomic<bool> want[2] = {false, false};
atomic<int> turn = 0;void process(int i) {
int j = 1 – i; // The other process
for (int k = 0; k < 5; k++) { // Simulating multiple iterations
want[i] = true;
while (want[j]) {
if (turn != i) {
want[i] = false;
while (turn != i); // Busy wait
want[i] = true;
}
}

// Critical Section
cout << “Process “ << i << ” is in the Critical Section.\n”;

// Exit Section
turn = j;
want[i] = false;
}
}

int main() {
thread t1(process, 0);
thread t2(process, 1);

t1.join();
t2.join();

return 0;
}

Key Properties of Dekker’s Algorithm

Mutual Exclusion – Only one process enters the critical section at a time.
Progress – If no process is in CS, one can enter without indefinite waiting.
Bounded Waiting – No process suffers indefinite postponement.

Limitations

 Works only for two processes.
 Uses busy waiting (inefficient CPU utilization).
 Not suitable for modern multi-core architectures.

Would you like an explanation of an alternative algorithm like Peterson’s Algorithm or Lamport’s Bakery Algorithm?

Process Synchronization Two Process Solution) (Algo-3) l Decker’s Algorithm.

Process Synchronization

🔐 Process Synchronization – Decker’s Algorithm (Two Process Solution, Algo-3)

Decker’s Algorithm is a classic software solution for process synchronization between two processes. It was one of the earliest attempts to solve the critical section problem without hardware support (i.e., no atomic test-and-set).


🧠 Why Use Decker’s Algorithm?

To ensure that two processes (say, P0 and P1) do not enter their critical sections at the same time, avoiding race conditions.

It satisfies the three requirements of synchronization:

  1. Mutual Exclusion

  2. Progress

  3. Bounded Waiting


⚙️ Basic Idea:

  • Each process indicates its intention to enter the critical section using a flag.

  • A shared variable turn decides which process gets the turn when both want to enter at the same time.


🔧 Variables Used:

c
boolean flag[2]; // flag[i] = true if process Pi wants to enter critical section
int turn; // whose turn it is (0 or 1)

🧾 Algorithm (for both processes P0 and P1):

🔁 Code for Process Pi (i = 0 or 1):

c
do {
flag[i] = true;
while (flag[j]) {
if (turn != i) {
flag[i] = false;
while (turn != i)
; // busy wait
flag[i] = true;
}
}
// Critical Section (CS)
// Perform shared data operations hereturn = j;
flag[i] = false;

// Remainder Section
} while (true);

Where:

  • i is the current process (0 or 1)

  • j = 1 - i is the other process


✅ How It Works:

  1. Each process sets flag[i] = true to indicate intent to enter.

  2. If the other process (j) also wants to enter (flag[j] == true), then check turn.

  3. If it’s not Pi’s turn, it backs off by setting flag[i] = false and waits.

  4. Once the turn becomes theirs again, it reasserts flag[i] = true and tries again.

  5. Upon exiting CS, the process:

    • Gives turn to the other: turn = j

    • Resets its flag: flag[i] = false


🔐 Ensures:

  • Mutual Exclusion: Only one process in CS at a time.

  • Progress: If no process is in CS, decision is based on turn.

  • Bounded Waiting: No process is left waiting forever.


📝 Example:

Assume:

  • flag[0] = flag[1] = false

  • turn = 0

If both processes try to enter:

  • Both set their flag to true

  • P1 finds turn != 1, backs off (flag[1] = false)

  • P0 enters CS

  • When done, P0 sets turn = 1, flag[0] = false

  • Now P1 can enter


⚠️ Limitations:

  • Only works for two processes

  • Not scalable for more than 2

  • Uses busy waiting (CPU cycles are wasted during wait)


🧠 Summary:

Feature Description
Process Support Only 2 processes
Main Control Variable flag[2] and turn
CS Safety Yes (ensures mutual exclusion)
Fairness Yes (bounded waiting, alternates turn)
Type Software-based

If you’d like, I can also share:

  • 📋 Annotated Code Example

  • 📊 Comparison with Peterson’s Algorithm

  • 🎓 MCQ Quiz for GATE Preparation

Shall we continue with that?

Process Synchronization Two Process Solution) (Algo-3) l Decker’s Algorithm.



Leave a Reply

Your email address will not be published. Required fields are marked *

error: