DIZNR INTERNATIONAL

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

Lui Kreyszig Lui Kreyszig

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

https://www.gyanodhan.com/video/7B7.%20GATE%20CSEIT/Operating%20System/634.%20Process%20Synchronization%20Two%20Process%20Solution%29%20%28Algo-3%29%20l%20Decker%27s%20Algorithm.mp4

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:

2. Entry Section:

3. Critical Section (CS):

4. Exit Section:

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:

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 here

turn = j;
flag[i] = false;

// Remainder Section
} while (true);

Where:

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:

Example:

Assume:

If both processes try to enter:

Limitations:

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:

Shall we continue with that?

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