Dekker's Algorithm vs Peterson's Algorithm for Mutual Exclusion

Mutual exclusion is the concurrency requirement that only one process or thread can enter a critical section at a time. Dekker's algorithm and Peterson's algorithm are classic two-process solutions that show how mutual exclusion can be built from shared variables, flags, and a turn variable.

The practical difference is this: Dekker's algorithm is historically important but harder to reason about, while Peterson's algorithm is simpler and is usually the cleaner teaching example. Both are mainly educational today because modern CPUs, compilers, caches, and memory models can break their assumptions unless memory ordering is controlled explicitly.

Dekker's Algorithm vs Peterson's Algorithm: Quick Comparison

What Problem Do These Algorithms Solve?

A critical section is a part of a program that reads or writes shared state. If two threads execute that code at the same time, the result may depend on timing rather than logic.

A mutual exclusion algorithm should provide three properties:

• Mutual exclusion: two processes cannot be in the critical section at the same time.
• Progress: if no process is in the critical section, a waiting process can eventually enter.
• Bounded waiting: a process should not wait forever while the other process repeatedly enters.

Dekker's algorithm and Peterson's algorithm try to provide those properties for two processes without using hardware locks.

Dekker's Algorithm

Dekker's algorithm is a mutual exclusion algorithm for two concurrent processes. It uses two shared intent flags and a shared turn variable.

A simplified version for process i, where j is the other process, is:

1want[i] = true;
2
3while (want[j]) {
4  if (turn == j) {
5    want[i] = false;
6    while (turn == j) {
7      // busy wait
8    }
9    want[i] = true;
10  }
11}
12
13// critical section
14
15turn = j;
16want[i] = false;

The important idea is that each process announces intent. If both processes want to enter, the turn variable breaks the tie. The process whose turn it is not backs off temporarily, then tries again.

Dekker Algorithm in OS Courses

Dekker's algorithm appears in operating systems courses because it demonstrates that mutual exclusion is possible with ordinary shared variables under a strict memory model. It is useful for explaining:

• critical sections
• busy waiting
• turn-based fairness
• why concurrent code needs precise ordering rules

It is not a modern operating system primitive. Real kernels use hardware-supported atomic instructions, spinlocks, mutexes, semaphores, futexes, scheduler-aware locks, and memory barriers. The Linux-side view is covered in Linux kernel concurrency mechanisms.

Peterson's Algorithm

Peterson's algorithm is another two-process mutual exclusion algorithm. It uses the same categories of state as Dekker's algorithm, but the entry protocol is cleaner.

For process i, where j is the other process:

1want[i] = true;
2turn = j;
3
4while (want[j] && turn == j) {
5  // busy wait
6}
7
8// critical section
9
10want[i] = false;

Peterson's algorithm is easier to read:

• want[i] = true says "I want to enter."
• turn = j says "If we both want to enter, let the other process go first."
• The while loop waits only if the other process wants entry and it is the other process's turn.

That is why Peterson's algorithm is often the preferred teaching example for two-process mutual exclusion.

Difference Between Peterson and Dekker Algorithm

The main difference between Peterson's algorithm and Dekker's algorithm is how they handle contention.

Dekker's algorithm uses a more involved back-off protocol. If both processes want to enter and it is not process i's turn, process i temporarily clears its intent flag, waits for its turn, then raises its intent flag again.

Peterson's algorithm is more direct. Process i raises its intent flag, assigns priority to process j, and waits only while j wants entry and turn == j.

In practical terms:

• Dekker's algorithm is historically significant.
• Peterson's algorithm is simpler to explain and verify.
• Both classic versions are for two processes only.
• Neither should be copied into production code as a replacement for real synchronization primitives.

Does Peterson's Algorithm Work for More Than Two Processes?

The classic Peterson's algorithm is for two processes. There are generalized algorithms inspired by Peterson's idea, such as tournament-tree style constructions, but the simple two-flag, one-turn version does not directly solve mutual exclusion for arbitrary numbers of processes.

This matters because many summaries incorrectly say Peterson's algorithm is scalable in its basic form. It is not. It is elegant for two participants, not a drop-in multi-threaded lock.

Peterson's Algorithm, Memory Fences, and Store Buffers

The textbook proof of Peterson's algorithm usually assumes sequential consistency: every process observes memory operations in a single global order that matches program order.

Modern systems are more complicated. CPUs may use store buffers, caches, and memory reordering. Compilers may also reorder operations unless the code uses appropriate atomic operations or barriers.

The fragile part is the entry protocol:

1want[i] = true;
2turn = j;
3while (want[j] && turn == j) {
4  // wait
5}

If writes to want[i] or turn are delayed, reordered, or not made visible in the expected order, both processes may make decisions using stale information. On weak memory models, Peterson's algorithm needs carefully placed memory fences or language-level atomic operations with the right ordering constraints.

That is why a query like "Peterson algorithm memory fence write buffer store bypass" points to the real lesson: the algorithm is not just about flags and turns. It is also about what memory ordering the hardware and compiler promise.

For a related hardware-level explanation, see cache coherence and synchronization.

Why Modern Code Uses Locks Instead

Real systems normally use synchronization primitives built on atomic hardware instructions and language memory models:

• mutexes
• spinlocks
• semaphores
• condition variables
• compare-and-swap based algorithms
• load-linked/store-conditional based algorithms

These tools handle practical concerns that Dekker's and Peterson's algorithms do not address cleanly, including preemption, scheduling, multi-core memory visibility, fairness, and power usage.

Classical problems such as the dining philosophers problem are still useful because they teach the shape of concurrency failures. Production code needs stronger primitives.

You can view a small Dekker's algorithm example here: dekker.c

You can also view the corresponding Peterson's algorithm example here: petterson.c

FAQ

What is the difference between Dekker's algorithm and Peterson's algorithm?

Dekker's algorithm and Peterson's algorithm both solve two-process mutual exclusion with shared flags and a turn variable. Dekker's algorithm uses a more complex back-off protocol, while Peterson's algorithm uses a simpler "declare intent, give priority, then wait" protocol.

What is Dekker's algorithm in operating systems?

In operating systems education, Dekker's algorithm is a classical two-process mutual exclusion algorithm. It demonstrates how critical-section access can be coordinated using shared variables under a strict memory model.

Is Peterson's algorithm better than Dekker's algorithm?

Peterson's algorithm is usually easier to understand and prove, so it is often preferred as a teaching example. Dekker's algorithm is historically important but more complicated.

Does Peterson's algorithm work on modern CPUs?

The textbook version only works under strong memory-ordering assumptions. On modern CPUs and compilers, you need atomic operations and memory ordering controls, otherwise store buffers and reordering can break the proof.

Are Dekker's and Peterson's algorithms used in production?

Rarely, if ever, as direct production locks. They are mainly educational. Production systems use hardware-supported synchronization primitives and language-level atomic APIs.