Dekker’s and Peterson’s algorithms are classical software solutions to the two-process critical-section problem. Both use shared variables to decide which process may enter the critical section when P0 and P1 compete at the same time. Dekker’s solution uses two interest flags plus a turn variable and temporarily withdraws a process when both want to enter. Peterson’s solution is simpler: each process raises its flag, gives the other process priority through the turn variable, and waits only when the other process is interested and has priority. Under the classical textbook assumptions of atomic reads/writes and proper memory visibility, both are designed to satisfy mutual exclusion, progress and bounded waiting for two processes.
Why Was the Critical-Section Problem Difficult?
Two processes may want to enter the same critical section at nearly the same time. A simple idea such as “check a variable and then enter” can fail because the check and update may happen in an unsafe order.
Dekker and Peterson combine “interest” and “priority” so two processes can coordinate without using a hardware lock instruction.
Revise Critical Section & Mutual Exclusion in OS if mutual exclusion, progress and bounded waiting are not clear yet.
What Do flag[] and turn Actually Mean?
What Must a Correct Two-Process Solution Guarantee?
These are exactly the three conditions introduced in the critical-section chapter.
What Is Dekker’s Solution?
Dekker’s solution uses two interest flags and a turn variable. If both processes want the critical section, the process whose turn is not favored temporarily withdraws its interest, waits for its turn, and then tries again.
That temporary withdrawal is the special idea that makes Dekker different from a simple two-flag solution.
Dekker’s Algorithm for P0 and P1
Process P0
while (true) {
flag[0] = true;
while (flag[1]) {
if (turn == 1) {
flag[0] = false;
while (turn == 1) {
; // wait
}
flag[0] = true;
}
}
// critical section
turn = 1;
flag[0] = false;
// remainder section
}
Process P1
while (true) {
flag[1] = true;
while (flag[0]) {
if (turn == 0) {
flag[1] = false;
while (turn == 0) {
; // wait
}
flag[1] = true;
}
}
// critical section
turn = 0;
flag[1] = false;
// remainder section
}
Read the code as a conversation. “I want to enter” is the flag. “If both want to enter, whose turn is it?” is the turn variable. The process that loses the tie backs off, then tries again later.
Dekker’s Solution: Both Processes Request at the Same Time
Assume both flags become true and turn = 0.
This tie-breaking and backing-off behavior prevents the “both flags true forever” deadlock of the naive two-flag approach.
How Does Dekker Satisfy the Three Requirements?
| Requirement | How Dekker Handles It |
|---|---|
| Mutual Exclusion | If both processes are interested, turn decides which process backs off, so they do not both enter. |
| Progress | If only one process is interested, the other flag is false and the interested process can enter. |
| Bounded Waiting | After leaving, a process gives turn to the other process, preventing unlimited repeated entry by one side when both compete. |
What Is Peterson’s Solution?
Peterson’s solution is a simpler two-process mutual-exclusion algorithm that uses two interest flags and one turn variable. A process first says “I want to enter,” then gives the other process priority if both request together.
For process Pi, let j be the other process.
Peterson’s Algorithm for P0 and P1
Process P0
while (true) {
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1) {
; // wait
}
// critical section
flag[0] = false;
// remainder section
}
Process P1
while (true) {
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0) {
; // wait
}
// critical section
flag[1] = false;
// remainder section
}
Peterson’s algorithm is shorter because it does not need Dekker’s “lower my flag, wait for turn, raise my flag again” pattern.
Peterson’s Solution: Both Processes Request Together
Suppose P0 and P1 both set their flags to true.
When Does Peterson Allow a Process to Enter?
| Other Process Interested? | turn Favors Other? | What Happens? |
|---|---|---|
| No | Does not matter | Enter immediately |
| Yes | No | Enter |
| Yes | Yes | Wait |
How Does Peterson Satisfy Mutual Exclusion, Progress & Bounded Waiting?
| Requirement | Reason |
|---|---|
| Mutual Exclusion | If both flags are true, turn can favor only one side at a time, so one process waits. |
| Progress | If the other process is not interested, its flag is false and the interested process does not wait. |
| Bounded Waiting | A requesting process gives the other side priority through turn, preventing one process from repeatedly overtaking forever under the classical assumptions. |
Dekker’s vs Peterson’s Solution
Dekker’s Solution
Uses flags and turn, but includes a back-off step where a process temporarily clears its flag when it loses the tie.
Peterson’s Solution
Uses flags and turn in a shorter form. A process raises its flag and directly gives the other process priority through turn.
| Point | Dekker | Peterson |
|---|---|---|
| Processes supported | Two | Two |
| Shared variables | Two flags + turn | Two flags + turn |
| Main special idea | Back off by lowering flag when losing turn | Give other process priority through turn |
| Code complexity | More complex | Simpler |
| Busy waiting | Yes | Yes |
| Hardware atomic lock required? | No, under textbook assumptions | No, under textbook assumptions |
| Main teaching value | Shows careful software tie-breaking | Elegant classical software solution |
See Which Process Enters in Peterson’s Algorithm
Select a simple contention case. The visual explains the decision using flags and turn.
Only P0 Wants to Enter
Decision
Limitations of Dekker’s and Peterson’s Algorithms
So Peterson’s algorithm is excellent for learning the idea, but it should not be treated as a drop-in replacement for modern synchronization libraries.
Why Do Textbooks Mention Atomic Reads and Writes?
Both algorithms depend on processes seeing shared values such as flag and turn in the intended order.
The classical proof assumes reads and writes of these shared variables behave atomically and with memory-order behavior suitable for the algorithm.
On modern hardware, ordinary variables can be affected by compiler optimizations, caches and memory reordering. Practical implementations therefore need proper atomic or memory-ordering primitives.
Why Is Dekker Better Than Strict Alternation?
Strict Alternation
P0 and P1 must take turns even if one process does not want to enter. This can violate progress.
Dekker
A process can enter when the other process is not interested. turn is mainly used to settle actual competition.
Why Is Peterson Better Than “Just Use Two Flags”?
Imagine this naive rule:
If P0 and P1 both set their flags to true at the same time, each sees the other flag as true and both wait forever.
Peterson adds turn to break this tie. When both are interested, turn decides which waiting condition stays true and which process can proceed.
Dekker/Peterson vs Semaphore
| Point | Dekker/Peterson | Semaphore |
|---|---|---|
| Type | Classical software algorithms | Synchronization primitive |
| Basic version | Two processes | Can coordinate many processes/threads |
| Main shared data | Flags and turn | Semaphore state plus waiting mechanism |
| Waiting | Busy waiting | Can use blocking or spinning depending implementation |
| Typical modern use | Mainly educational/theoretical | Common synchronization concept and implementation tool |
For semaphore basics, revise Semaphores in OS: Wait, Signal, Test-and-Set & Synchronization.
Common Student Mistakes
How to Write Dekker’s & Peterson’s Solutions in an Exam
Short definition
State that each is a two-process software solution to the critical-section problem using shared variables.
One algorithm
Write variables, pseudocode, one simultaneous-request example and explain mutual exclusion.
Comparison answer
Explain failed simple approaches, Dekker, Peterson, mutual exclusion/progress/bounded waiting, busy waiting and a comparison table.
Fast memory trick
Dekker backs off · Peterson gives the other side turnPractice Questions With Answers
1. What problem do Dekker’s and Peterson’s algorithms solve?
They solve the two-process critical-section problem using shared software variables under classical textbook assumptions.
2. What does flag[i] mean?
flag[i] = true means process Pi is interested in entering the critical section.
3. What is the purpose of the turn variable?
turn breaks a tie when both processes want to enter the critical section.
4. What is special about Dekker’s solution?
When both processes compete, the process that loses the turn temporarily lowers its interest flag, waits, and then tries again.
5. What is Peterson’s waiting condition for Pi?
Pi waits while flag[j] is true and turn equals j, where j is the other process.
6. Why are two flags alone not enough?
If both processes set their flags to true at the same time and each waits for the other flag to become false, both can wait forever.
7. Do Dekker and Peterson use busy waiting?
Yes. Waiting processes repeatedly check shared conditions.
8. How many processes does basic Peterson’s solution support?
The basic textbook Peterson solution supports two processes.
9. Which is simpler, Dekker or Peterson?
Peterson’s solution is generally simpler and shorter to understand and write.
10. Are these algorithms commonly used directly in modern application code?
Usually no. They are mainly studied to understand software mutual exclusion; real programs normally use synchronization primitives provided by the language, runtime or operating system.
One-Minute Revision
Frequently Asked Questions
What is Dekker’s algorithm in OS?
Dekker’s algorithm is a classical two-process software mutual-exclusion solution that uses two interest flags and a turn variable, including a back-off step when both processes compete.
What is Peterson’s algorithm in OS?
Peterson’s algorithm is a two-process critical-section solution that uses two interest flags and a turn variable to provide mutual exclusion, progress and bounded waiting under classical assumptions.
What is the main difference between Dekker and Peterson?
Dekker uses a more complex back-off mechanism when both processes compete, while Peterson solves the same two-process problem with a shorter flag-and-turn rule.
Why does Peterson use a turn variable?
The turn variable breaks the tie when both processes want to enter the critical section at the same time.
Do Dekker and Peterson satisfy bounded waiting?
Yes, under the classical textbook assumptions, both are designed to satisfy mutual exclusion, progress and bounded waiting for two processes.
Why are Peterson and Dekker mostly studied theoretically today?
They are excellent for understanding software mutual exclusion, but real systems normally use tested mutexes, semaphores and atomic synchronization primitives that also handle modern memory-ordering requirements.
What Should You Learn Next?
Next: Dining Philosophers Problem
After understanding two-process mutual exclusion, move to Dining Philosophers Problem in OS: Deadlock & Semaphore Solutions Explained. It shows what happens when several processes compete for multiple shared resources.
You can also revise Producer-Consumer Problem in OS to strengthen semaphore-based synchronization before the next classical problem.
