Dekker’s Algorithm for Mutual Exclusion

Introduction

Dekker’s Algorithm is an early software-only solution for the critical section problem. It uses shared variables instead of special atomic hardware instructions.

The algorithm is designed for two processes. Its main value is conceptual: it shows how mutual exclusion can be achieved with careful shared-variable coordination, while also showing why modern systems use stronger synchronization primitives.

Why Dekker’s Algorithm Matters

Dekker’s Algorithm is important in operating system history because it tries to solve mutual exclusion without hardware locks, test-and-set, or compare-and-swap instructions.

It matters for a few clear reasons:

• Software-only design: It depends on shared variables, not special hardware instructions.

• Two-process scope: It is meant for two processes, usually named P0 and P1.

• Critical-section link: It tries to satisfy mutual exclusion, progress, and bounded waiting.

• Conceptual role: It prepares the idea behind cleaner algorithms such as Peterson’s Algorithm.

• Practical limit: It is not treated as a modern production locking primitive.

Problem Setup

Dekker’s Algorithm uses two kinds of shared variables: flags and turn.

The flags show interest. The turn variable breaks a tie when both processes are interested at the same time.

If only one process wants to enter, it can enter. If both want to enter, the process whose turn is favored gets priority, while the other process waits and retries.

Goal of the Algorithm

Dekker’s Algorithm aims to satisfy the three main critical-section requirements.

• Mutual exclusion: Both processes must not be inside the critical section together.

• Progress: If the critical section is free, entry should not be postponed forever.

• Bounded waiting: A waiting process should not be bypassed endlessly.

These goals are what make the algorithm more than a simple “take turns” idea. It must prevent simultaneous entry, but it must also avoid unnecessary waiting and starvation.

Working Intuition

A process first announces that it wants to enter by setting its flag. Then it checks whether the other process is also interested.

The working flow is:

• Raise own flag: The process marks that it wants the critical section.

• Check other flag: It checks whether the other process also wants to enter.

• Enter if no conflict exists: If the other process is not interested, the process enters.

• Use turn during conflict: If both processes are interested, turn decides who should wait.

• Back off temporarily: The process without priority lowers its flag for the moment.

• Retry later: After the turn changes, it raises interest again and checks once more.

This back-off step is the key idea. When both processes are competing, one process gives way instead of both staying committed to entry at the same time.

Compact Pseudocode Shape

For process Pi, where the other process is Pj, the logic can be viewed like this:

This is a compact teaching shape, not a recommendation for writing modern lock code. The important idea is how flag and turn cooperate.

Why the Back-Off Works

If both processes want to enter, both flags may become true. The turn variable then decides which process has priority.

The process without the turn backs off by lowering its flag and waiting. This gives the favored process a chance to enter and complete its critical section.

After the favored process exits, it gives the turn to the other process. This helps prevent one process from winning repeatedly while the other waits.

Assumptions and Limitations

Dekker’s Algorithm works in the classic teaching model because certain assumptions are made.

• Atomic reads and writes: Reading or writing a shared variable is treated as one indivisible action.

• Expected memory ordering: Operations are assumed to be seen in the order required by the algorithm.

• Two-process design: The algorithm is not directly built for many processes.

• Busy waiting: A waiting process may spin while checking shared variables.

• Not modern lock design: Real systems usually use mutexes, semaphores, monitors, atomic instructions, or language/runtime synchronization tools.

On modern hardware and compilers, memory operations may need explicit ordering guarantees, so this algorithm should be understood as a conceptual OS algorithm rather than a direct production tool.

Summary

Dekker’s Algorithm is an early software-only mutual exclusion algorithm for two processes. It uses flag[0] and flag[1] to show interest, and turn to decide priority when both processes want the critical section.

The core idea is to raise interest, check the other process, back off when the turn favors the other process, and retry later. Under its teaching-model assumptions, Dekker’s Algorithm supports mutual exclusion, progress, and bounded waiting.