Thread Synchronization: Dekker's and Peterson's Algorithms and Semaphore Applications

Modern software rarely runs one thing at a time. Web servers handle many requests at once, background jobs run alongside user actions, and multiple threads often need to read or update the same data. When this shared access isn’t carefully controlled, bugs like race conditions and corrupted data start to appear, often in ways that are difficult to debug (especially on weekends🫠).

Consider a simple example: two threads updating the same bank account balance at the same time. If both read the old value before either writes the new one, the final result can be wrong. This is the kind of problem thread synchronization is designed to prevent.

At the core of these issues is the critical section problem, which is simply the challenge of ensuring that when multiple processes or threads share data, only one of them can access the shared part of the code at a time, so the data remains consistent.

Any solution must ensure three things:

• Only one process accesses the critical section at a time

• The system keeps making progress

• No process waits forever.

This article briefly explores two classic software-based solutions—Dekker’s algorithm and Peterson’s algorithm—and then shows how semaphores are used to solve common synchronization problems in practice.

Dekker’s Algorithm

Dekker's algorithm, developed by Dutch mathematician Theodorus Dekker in the 1960s, was the first correct software-based solution to the mutual exclusion problem for two processes.
Before mutexes, monitors, and high-level concurrency tools existed, synchronization had to be solved using nothing but shared variables and careful logic.

One of the earliest and most impressive attempts at this was Dekker’s algorithm. Beyond the technical achievement, there’s something undeniably cool about having an algorithm named after you 🤔.

It addresses the critical section problem for two processes and demonstrates how mutual exclusion, progress, and bounded waiting can be achieved purely in software.

While it’s not something you’d implement in modern production code, it remains a foundational idea that helps explain how concurrent systems work under the hood. It typically handles orchestration for two process, which would need to access a critical section

The algorithm basically uses two flags (one for each process) and a turn variable:

boolean flag[2] = {false, false}; 
int turn = 0;

Process P0:
    flag[0] = true;
    while (flag[1]) {
        if (turn == 1) {
            flag[0] = false;
            while (turn == 1) {
                // Busy waiting
            };
        }
    }
    // Critical Section
    turn = 1;
    flag[0] = false;

boolean flag[2] = {false, false}; 
int turn = 0;

Process P1:
    flag[1] = true;
    while (flag[0]) {
        if (turn == 0) {
            flag[1] = false;
            while (turn == 0) {
                // Busy waiting
            };
        }
    }
    // Critical Section
    turn = 0;
    flag[1] = false;

Each process raises its flag to indicate it wants to enter the critical section. If both flags are up, the turn variable decides who goes first. The process that doesn't have the turn lowers its flag, waits, and then tries again.

Dekker’s algorithm is notable because it shows that mutual exclusion can be achieved using software alone, while still guaranteeing progress and bounded waiting. However, in practice it’s limited to just two processes, relies on strict memory ordering, and uses busy-waiting, which wastes CPU time. These drawbacks make it more of a learning tool than a solution you’d use in modern systems.

Peterson’s Algorithm

Peterson’s algorithm builds on the ideas introduced by Dekker and presents a simpler and more elegant software-based solution to the mutual exclusion problem for two processes. Proposed by Gary Peterson in the early 1980s, the algorithm shows how careful coordination using shared variables can reliably control access to a critical section without relying on special hardware support.

Like Dekker’s algorithm, it guarantees mutual exclusion, progress, and bounded waiting, but does so with significantly less complexity.

By combining just two intent flags and a single turn variable, Peterson’s algorithm makes the core principles of synchronization easier to reason about and verify.

Although it is not commonly used in modern production systems due to busy-waiting and scalability limitations, it remains a widely taught example because of its clarity and correctness, serving as a bridge between theoretical concurrency concepts and practical synchronization mechanisms.

boolean flag[2] = {false, false};
int turn = 0;
Process Pi (where i = 0 or 1, j = 1 - i):

    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);

    // Critical Section
    flag[i] = false;

Semaphores

A Practical Step Forward

Dekker’s and Peterson’s algorithms are great for understanding how synchronization works at a fundamental level, but they’re not something you’d want to rely on in real-world systems. That’s where semaphores come in. Semaphores are a more practical and scalable synchronization tool, designed to work cleanly with many processes and threads.

At their core, a semaphore is just an integer paired with two atomic operations. The wait() (also called P) operation decrements the value and blocks the process if the resource isn’t available (when the semaphore value is negative). The signal() (or V) operation increments the value and wakes up a waiting (blocked) process if there is one. This simple mechanism allows processes to coordinate access to shared resources without stepping on each other.

There are two common types of semaphores. A binary semaphore only takes the values 0 or 1 and behaves much like a mutex lock. A counting semaphore, on the other hand, can hold any non-negative integer and is useful when multiple instances of a resource are available.

Semaphores improve on early algorithms like Dekker’s and Peterson’s in a few important ways:

• They work with more than just two processes, making them practical for real systems

• They avoid busy-waiting by putting processes to sleep until a resource is available

• They lead to cleaner and easier-to-read code

• They can be efficiently implemented by the OS or hardware, so they scale well

To better understand this, we’ll explore it’s application into two common problems:

• Producer-Consumer (Bounded Buffer) Problem

• Readers-Writers Problem

The Producer-Consumer (Bounded Buffer) Problem

The Producer–Consumer problem (also known as the Bounded Buffer problem) describes a situation where two types of processes share a fixed-size buffer: producers, which generate data, and consumers, which use that data.

The main challenge is coordinating access so that producers do not add items to a full buffer, consumers do not remove items from an empty buffer, and multiple producers or consumers do not corrupt the shared data.

This problem is typically solved using three semaphores:

• mutex:a binary semaphore initialized to 1 to ensure mutual exclusion when accessing the buffer;

• empty: a counting semaphore initialized to the buffer size N to track available slots;

• full: a counting semaphore initialized to 0 to track filled slots.

int mutex = 1;
int empty = N; // N is buffer size
int full = 0;
Producer:
    while (true) {
      // Produce item
      wait(empty); // Wait for empty slot
      wait(mutex); // Enter critical section

      // Add item to buffer

      signal(mutex); // Leave critical section
      signal(full); // Signal item added
    }
//______________________________________________________________________________

Consumer:
    while (true) {
       wait(full); // Wait for filled slot
       wait(mutex); // Enter critical section

       // Remove item from buffer

       signal(mutex); // Leave critical section
       signal(empty); // Signal slot freed
       // Consume item
    }

The empty semaphore prevents producers from overfilling the buffer, while the full semaphore prevents consumers from accessing an empty buffer. The mutex semaphore ensures that only one process modifies the buffer at a time.

This bounded-buffer problem appears in many real world systems such as network packet buffers, message queues in distributed systems and streaming media buffers, and the solution using semaphores is widely implemented handle these issues.

The Reader-Writer Problem

The Readers-Writers problem involves a shared data structure that can be accessed by two types of processes:

• Readers: Only read the data (multiple readers can access simultaneously)

• Writers: Modify the data (exclusive access required)

Also has 3 constraints are:

1. Multiple readers can read simultaneously

2. Only one writer can write at a time

3. Readers and writers cannot access the data simultaneously

There are 2 techniques to solve this problem using semaphore. One prioritizes the “readers” process to prevent reader starvation, and the other prioritizes the “writers” process to prevent writer starvation.

Readers Priority Solution

This solution gives priority to readers. Once the first reader enters, subsequent readers can also enter even if a writer is waiting. Utilizing 2 semaphores and one variable as shown below:

int mutex = 1; //-Semaphore Protects read_count

int write_lock = 1; //-Semaphore Controls write access

int read_count = 0; //-Variable Number of active readers

// READER
wait(mutex);
    read_count++;
    if (read_count == 1){
        // First reader locks writers
        wait(write_lock);
    }
    signal(mutex);

    // Read data here

    wait(mutex);
    read_count--;
    if (read_count == 0){
        // Last reader unlocks writers
        signal(write_lock);
    }

    signal(mutex);

// WRITER
    wait(write_lock);

    // Write data here

    signal(write_lock);

The first reader to arrive acquires the write_lock, preventing writers from entering. Additional readers simply increment the counter. The last reader to leave releases the write_lock, allowing writers to proceed.

Writers Priority Solution

As mentioned before, this variant gives priority to writers to prevent writer starvation:

int mutex = 1; //-Semaphore Protects read_count

semaphore read_lock = 1; //-Semaphore Controls read access

semaphore write_lock = 1; //-Semaphore Controls write access

semaphore read_try = 1; //-Semaphore Gives writers priority

semaphore mutex_r = 1; //-Semaphore Protects read_count

semaphore mutex_w = 1; //-Semaphore Protects write_count

int read_count = 0: //-Variable

int write_count = 0; //-Variable

// Reader:
    // Check if writers waiting
    wait(read_try)
    wait(read_lock);
    wait(mutex_r);
    read_count++;

    if (read_count == 1){
        wait(write_lock);
    }

    signal(mutex_r);
    signal(read_lock);
    signal(read_try);

    // Read data

    wait(mutex_r);
    read_count--;
    if (read_count == 0){
        signal(write_lock);
    }
    signal(mutex_r);

// Writer:
    wait(mutex_w);
    write_count++;

    if (write_count == 1){
         // First writer blocks new readers
        wait(read_lock); 
    }      

    signal(mutex_w);
    wait(write_lock);

    // Write data

    signal(write_lock);
    wait(mutex_w);
    write_count--;
    if (write_count == 0){
        // Last writer allows readers
        signal(read_lock);
    }
    signal(mutex_w);

Technique Tradeoffs

Wrapping Up

So, that’s the lowdown on thread synchronization. We looked at the classics—Dekker’s and Peterson’s—which, let's be honest, are a bit like the vintage cars of programming: beautiful to look at, but maybe not what you want to drive to work every day (especially with that busy-waiting limitation).

However, the concepts behind them are still very much alive. If you’ve ever debugged a race condition in a Producer-Consumer job queue or tried to stop a "flash sale" from crashing your inventory service (hello, Bounded-Buffer problem ), you’ve dealt with these exact challenges. Modern abstractions might hide the semaphores, but the principles of locking and data consistency haven't changed.

But enough theory, let's write some code 🤓.

I’m getting ready to drop a brand new series of tutorials that take these concepts and apply them to the frameworks you use every day. I’ll be showing you how to handle concurrency in Node.js, NestJS, and Spring Boot specifically for high-stakes scenarios like Finanacial or E-commerce application.

Stay tuned: The first guide drops soon. You could follow me here so you're the first to know when we start writing the code that keeps the ledger safe 🔒.