DIZNR INTERNATIONAL

Critical Section Problem With Two Process Solution (Algo-1) Deckers solution, Strict Alteration.

Lui Kreyszig Lui Kreyszig

Critical Section Problem With Two Process Solution (Algo-1) Deckers solution, Strict Alteration.

https://www.gyanodhan.com/video/7B7.%20GATE%20CSEIT/Operating%20System/636.%20Critical%20Section%20Problem%20With%20Two%20Process%20Solution%20%28Algo-1%29%20%20%20Deckers%20solution%20%20Strict%20Alteration.mp4

The Critical Section Problem is a classic problem in operating systems and concurrent programming, where multiple processes need to access shared resources without causing data inconsistencies. One of the earliest solutions for two-process synchronization is Strict Alternation, also known as Dekker’s Algorithm (Algo-1).

Strict Alternation Solution (Algorithm-1)

Concept:
In the strict alternation method, processes take turns to enter their critical section by maintaining a shared variable turn.

Algorithm

Let:

  1. Process P0:

    while (turn != 0); // Wait until it's P0's turn
    // Critical Section
    turn = 1; // Give turn to P1

  2. Process P1:

    while (turn != 1); // Wait until it's P1's turn
    // Critical Section
    turn = 0; // Give turn to P0

Issues with Strict Alternation

Lack of Progress:

    • If one process does not need to enter its critical section, the other process is still forced to wait, leading to unnecessary delays.
  2. Busy Waiting:
    • The waiting process continuously checks the value of turn, leading to CPU wastage.
  3. Not Truly Concurrent:
    • A process can be blocked even when the critical section is available.

Improved Solution: Dekker’s Algorithm

To overcome the drawbacks of strict alternation, Dekker’s Algorithm introduces an additional mechanism using flags (flag[0] and flag[1]) to ensure mutual exclusion while allowing flexibility.

Would you like a detailed explanation of Dekker’s Algorithm or other alternative solutions like Peterson’s Algorithm?

The Critical Section Problem arises in concurrent programming when two or more processes need mutual exclusive access to a shared resource (like a variable or a file).

Here’s a breakdown of Algorithm 1: Strict Alternation and Dekker’s Algorithm, which are classic solutions for the two-process critical section problem.

Goal of a Critical Section Solution

A good algorithm must satisfy the following:

  1. Mutual Exclusion – Only one process in the critical section at a time.

  2. Progress – If no process is in the critical section, one of the waiting processes can enter.

  3. Bounded Waiting – No process waits forever to enter its critical section.

1. Strict Alternation (Algorithm 1)

This is the simplest solution but not efficient.

Idea:

A shared variable turn is used to strictly alternate between processes.

c

int turn = 0; // Shared variable

// Process P0
while (true) {
while (turn != 0); // Wait
// Critical Section
…
turn = 1; // Give turn to P1
// Remainder Section
}

// Process P1
while (true) {
while (turn != 1); // Wait
// Critical Section
…
turn = 0; // Give turn to P0
// Remainder Section
}

Drawbacks:

2. Dekker’s Algorithm

One of the earliest correct solutions for two processes using only shared memory and no special hardware.

Idea:

Each process expresses its desire to enter the critical section using a flag. If both want to enter, use the turn variable to decide who gets in.

Shared Variables:

c
boolean flag[2] = {false, false}; // flag[i] = true means Pi wants to enter
int turn = 0; // Whose turn is it?

Process P0:

c
while (true) {
flag[0] = true;
while (flag[1]) {
if (turn != 0) {
flag[0] = false;
while (turn != 0);
flag[0] = true;
}
}
// Critical Section
...
turn = 1;
flag[0] = false;
// Remainder Section
}

Process P1:

c
while (true) {
flag[1] = true;
while (flag[0]) {
if (turn != 1) {
flag[1] = false;
while (turn != 1);
flag[1] = true;
}
}
// Critical Section
...
turn = 0;
flag[1] = false;
// Remainder Section
}

Dekker’s Algorithm: Advantages

Summary

Feature Strict Alternation Dekker’s Algorithm
Mutual Exclusion Yes Yes
Progress No Yes
Bounded Waiting Yes Yes
Efficiency Inefficient (can block unnecessarily) Efficient in terms of fairness

Would you like a diagram, animation, or a code simulation to visualize these concepts better?

Critical Section Problem With Two Process Solution (Algo-1) Deckers solution, Strict Alteration.

IJRIM Volume 2, Issue 5 (May 2012) (ISSN 2231-4334)