DEKKER AND PETTERSON SOLUTION USING SEMAPHORE COMPARISION

TABLE

Criteria Dekker’s Algorithm Peterson’s Algorithm

Definition First known software A simplified and efficient

solution to achieve mutual algorithm that achieves mutual
exclusion between two exclusion between two
processes. processes using flags.

Problem Solved Ensures only one process Solves mutual exclusion using
enters the critical section shared variables and ensures
at a time using busy- progress and bounded waiting.
waiting and turn variable.

No. of Designed for two Designed for two processes

Processes processes only. only.

Key Flags (interest), turn Flags (flag[2]) to indicate

Components variable, and alternation interest and turn variable to
Used logic. resolve conflict.

Mutual Guaranteed Guaranteed

Exclusion

Progress Ensures progress Ensures progress

Bounded Satisfied \Satisfied

Waiting

Working/Logic Process waits if the other Process sets flag, sets turn to
is interested, gives turn to other, waits until either other is
the other, and retries. not interested or it’s its turn.

Initialization Flag [0] = flag[1] = false, Same: flag [0] = flag [1] = false,
Required turn = 0 or 1 turn = 0 or 1

Hardware No special hardware No special hardware

Dependency instructions required. instructions required.

Fairness Fair but can lead to Simpler and more balanced

complex back-and-forth handing over of critical section.
handoffs.

Use of Busy Yes – like spinlock Yes – like spinlock

Waiting
Complexity More complex and hard to Simple and elegant for two
extend to n-processes processes

Extension to N Difficult – not scalable Not scalable – for only 2

Processes processes

Real-world Use Rarely used now; more Basis for understanding

historical importance modern synchronization

Advantage First software-based Simpler, more elegant; easier to

approach; no hardware understand and prove
needed correctness

Disadvantage Complex logic; not easy to Only for 2 processes; not

generalize; risk of livelock applicable to multiprocessor
shared memory in modern
systems

Variable Meaning

Flag [0] Boolean flag indicating Process 0 wants to enter the critical section.

Flag [1] Same as above for Process 1.

turn Indicates whose turn it is to enter the critical section in case both
want to enter.

Flag [0] = false;

Flag [1] = false;
turn = 0; // or 1 — doesn't matter as long as it's consistent.

Why these values?

 false = “I don’t want to enter the critical section” (initially, no process wants to
enter).

 turn = 0 or 1 = arbitrary start; tells whose turn it is if both want to enter — used to
resolve tie.
In Context

For Dekker’s Algorithm:

 Uses both flag [] and turn to handle contention.
 Ensures that turn is given to the other process when both want to enter,
avoiding deadlock.
For Peterson’s Algorithm:

 Uses flag [] to announce interest in critical section.

 Uses turn to yield priority to the other process temporarily, ensuring progress
and fairness.

Simple Analogy

Think of two kids (P0 and P1) who want to play a game:

 Each raises a hand (flag[i] = true) to say “I want to play”.

 If both raise hands, they ask whose turn it is.

 Whoever’s turn it is goes first; the other waits.

1. Dekker’s Algorithm (Process P0)

#include <stdio.h>
#include <stdbool.h>

// Shared variables
bool flag[2] = {false, false}; // flags for P0 and P1
int turn = 0; // can be 0 or 1

void process_P0() {
flag[0] = true; // P0 wants to enter

while (flag[1]) { // Check if P1 also wants to enter

if (turn == 1) {
flag[0] = false; // Yield to P1
while (turn == 1); // Busy wait
flag[0] = true; // Retry
}
}

// Critical Section
printf("Process P0 is in critical section\n");

// Exit Section
turn = 1; // Give turn to P1
flag[0] = false;
}
2. Peterson’s Algorithm (Process P0)
#include <stdio.h>
#include <stdbool.h>

// Shared variables
bool flag[2] = {false, false}; // flags for P0 and P1
int turn = 0;

void process_P0() {
flag[0] = true; // P0 wants to enter
turn = 1; // Give preference to P1

while (flag[1] && turn == 1); // Wait while P1 wants to enter and it’s their turn

// Critical Section
printf("Process P0 is in critical section\n");

// Exit Section
flag[0] = false;
}
SUMMARY TABLE

Feature Dekker’s Algorithm Peterson’s Algorithm

Flags Used Yes (flag[0], flag[1]) Yes (flag[0], flag[1])

Turn Yes Yes

Variable

Working Yield using flags + turn repeatedly Use turn to defer entry when
needed

Complexity Slightly more complex due to Simpler and elegant

retrying

1. Dekker’s Algorithm – Process P1

#include <stdio.h>
#include <stdbool.h>
// Shared variables
bool flag[2] = {false, false}; // flag[0] for P0, flag[1] for P1
int turn = 0; // 0 means P0's turn, 1 means P1's turn

void process_P1() {
flag[1] = true; // P1 wants to enter

while (flag[0]) { // Check if P0 also wants to enter

if (turn == 0) {
flag[1] = false; // Yield to P0
while (turn == 0); // Busy wait
flag[1] = true; // Retry to enter
}
}

// Critical Section
printf("Process P1 is in critical section\n");

// Exit Section
turn = 0; // Give turn to P0
flag[1] = false; // P1 no longer needs the critical section
}
2. Peterson’s Algorithm – Process P1
#include <stdio.h>
#include <stdbool.h>

// Shared variables
bool flag[2] = {false, false}; // flag[0] for P0, flag[1] for P1
int turn = 0; // 0 means P0's turn, 1 means P1's turn

void process_P1() {
flag[1] = true; // P1 wants to enter
turn = 0; // Give preference to P0

while (flag[0] && turn == 0); // Wait while P0 wants to enter and it’s their
turn

// Critical Section
printf("Process P1 is in critical section\n");
// Exit Section
flag[1] = false; // P1 done with the critical section
}

SUMMARY TABLE

Algorithm Process Sets flag[x] = Sets turn = Wait Condition

ID true y

Dekker P1 flag[1] = true Yields via while (flag[0]) { ... }

turn

Peterson P1 flag[1] = true turn = 0 while (flag[0] && turn ==

0);