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

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

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:

• turn be a shared variable that alternates between 0 and 1.
• P0 and P1 be the two processes.

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:

1. • 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.

Drawbacks:

• Fails the progress condition.

• A process might have to wait unnecessarily even if the other process is not interested.

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:

Process P0:

Process P1:

Dekker’s Algorithm: Advantages

• Satisfies Mutual Exclusion

• Satisfies Progress

• Satisfies Bounded Waiting

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)