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

March 17, 2025March 18, 2025 Lui Kreyszig 0 Comments

Available For 100% Free Book/Notes PDF Download (Click Here)

00:00

Contents [hide]

1 Dekker’s Algorithm – Process Synchronization (Two-Process Solution) (Algo-3)
2 Problem: Process Synchronization
3 Solution: Dekker’s Algorithm
4 Algorithm Steps:
5 Dekker’s Algorithm (Code Implementation in C++)
6 Key Properties of Dekker’s Algorithm
7 Limitations
8 Process Synchronization Two Process Solution) (Algo-3) l Decker’s Algorithm.
9 Process Synchronization

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:

Flags (want[2]) – Indicates if a process wants to enter the critical section.
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?

DIZNR INTERNATIONAL

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

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

Problem: Process Synchronization

Solution: Dekker’s Algorithm

Algorithm Steps:

1. Initialization:

2. Entry Section:

3. Critical Section (CS):

4. Exit Section:

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

Key Properties of Dekker’s Algorithm

Limitations