Software-Based Solutions for Process Synchronization

Unlike hardware-based approaches that rely on special CPU instructions, software-based solutions handle synchronization purely through algorithms and programming logic. No special hardware support is needed.

Three algorithms stand out here: Peterson's Algorithm, Dekker's Algorithm, and the Bakery Algorithm. Each solves the mutual exclusion problem in a different way, with different trade-offs in complexity and scalability.

Peterson's Algorithm

Peterson's Algorithm is the classic starting point for understanding mutual exclusion between two processes. It uses two shared variables to coordinate access:

1. A flag array where each process signals whether it wants to enter its critical section.

2. A turn variable that decides who gets to go when both processes want in at the same time.

The flow is straightforward. A process sets its flag to true, hands the turn to the other process (a polite "after you" gesture), and then waits if the other process also wants in and it is actually their turn. Once the other process is done, the waiting process enters its critical section and sets its flag back to false when finished.

cpp

#include <iostream>
#include <thread>
#include <atomic>
using namespace std;

atomic<bool> flag[2] = {false, false};
atomic<int> turn;

void peterson_process(int i) {
    int j = 1 - i;           // The other process
    while (true) {
        flag[i] = true;      // I want to enter
        turn = j;            // But I'll let you go first
        while (flag[j] && turn == j) {
            // Busy wait: other wants in AND it's their turn
        }
        // --- Critical Section ---
        cout << "Process " << i << " in critical section" << endl;
        // --- Exit Section ---
        flag[i] = false;     // I'm done, you can go
        cout << "Process " << i << " in remainder section" << endl;
    }
}

int main() {
    thread t1(peterson_process, 0);
    thread t2(peterson_process, 1);
    t1.join();
    t2.join();
    return 0;
}

Output:

text

Process 0 in critical section
Process 0 in remainder section
Process 1 in critical section
Process 1 in remainder section
...

Why Set turn = j (the other process)?

This is the key insight of Peterson's Algorithm. By setting turn to the OTHER process, each process is essentially saying "I want in, but if we both want in at the same time, you go first." This polite yielding is what guarantees mutual exclusion without deadlock. If both processes set turn simultaneously, only one write survives (the last one), and that process defers to the other.

Dekker's Algorithm

Dekker's Algorithm solves the same two-process problem but takes a different route. It is historically the first known correct solution to the mutual exclusion problem. Each process has its own flag to express intent, and there is a turn variable called "favoured" that breaks ties when both want in simultaneously.

What makes Dekker's approach distinct is how it handles contention. If both processes want in at the same time, the one that is not favoured temporarily backs off, drops its flag, and waits until the turn shifts in its favour before trying again. After finishing its critical section, a process hands the favour over to the other one.

cpp

#include <iostream>
#include <thread>
#include <atomic>
#include <chrono>

std::atomic<bool> want1{false};
std::atomic<bool> want2{false};
std::atomic<int> favoured{1};
const int ITERATIONS = 10;

void thread1() {
    for (int i = 0; i < ITERATIONS; ++i) {
        want1.store(true);                    // I want in
        while (want2.load()) {                // But does the other want in too?
            if (favoured.load() == 2) {       // If it's their turn...
                want1.store(false);           // Back off
                while (favoured.load() == 2) {
                    std::this_thread::yield(); // Wait for my turn
                }
                want1.store(true);            // Try again
            }
        }
        // --- Critical Section ---
        std::cout << "Thread 1 entering critical section" << std::endl;
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        std::cout << "Thread 1 leaving critical section" << std::endl;
        // --- Exit Section ---
        favoured.store(2);                    // Hand the favour to thread 2
        want1.store(false);                   // I'm done
    }
}

void thread2() {
    for (int i = 0; i < ITERATIONS; ++i) {
        want2.store(true);
        while (want1.load()) {
            if (favoured.load() == 1) {
                want2.store(false);
                while (favoured.load() == 1) {
                    std::this_thread::yield();
                }
                want2.store(true);
            }
        }
        std::cout << "Thread 2 entering critical section" << std::endl;
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        std::cout << "Thread 2 leaving critical section" << std::endl;
        favoured.store(1);
        want2.store(false);
    }
}

int main() {
    std::thread t1(thread1);
    std::thread t2(thread2);
    t1.join();
    t2.join();
    std::cout << "Both threads completed." << std::endl;
    return 0;
}

Output:

text

Thread 1 entering critical section
Thread 1 leaving critical section
Thread 2 entering critical section
Thread 2 leaving critical section
...
Both threads completed.

Bakery Algorithm

Peterson's and Dekker's both work fine, but only for two processes. The Bakery Algorithm scales to any number of processes. The idea is borrowed from how a bakery hands out numbered tokens to customers. Whoever has the lowest number gets served first.

Each process picks a number that is one higher than the current maximum among all processes. From that point, processes are served in order of their numbers. If two processes happen to pick the same number, the one with the lower process ID goes first.

Two shared arrays keep track of things: one to store the chosen numbers, and another (the choosing array) to flag when a process is in the middle of picking its number so others know to wait before comparing.

cpp

#include <iostream>
#include <thread>
#include <vector>
#include <algorithm>
#include <atomic>
using namespace std;

const int NUM_PROCESSES = 5;
atomic<bool> choosing[NUM_PROCESSES];
atomic<int> number[NUM_PROCESSES];

void bakery_process(int i) {
    for (int iter = 0; iter < 5; iter++) {
        // Doorway: Pick a ticket number
        choosing[i] = true;
        number[i] = 1 + *max_element(number, number + NUM_PROCESSES);
        choosing[i] = false;

        // Wait for all other processes
        for (int j = 0; j < NUM_PROCESSES; j++) {
            while (choosing[j]);          // Wait if they're picking a number
            while (number[j] != 0 &&      // Wait if they have a ticket AND
                  (number[j] < number[i] || // their number is smaller, OR
                  (number[j] == number[i] && j < i))); // same number but lower ID
        }

        // --- Critical Section ---
        cout << "Process " << i << " is in its critical section." << endl;
        // --- Exit Section ---
        number[i] = 0;                    // Discard the ticket
        cout << "Process " << i << " is in its remainder section." << endl;
    }
}

int main() {
    vector<thread> processes;
    for (int i = 0; i < NUM_PROCESSES; i++) {
        choosing[i] = false;
        number[i] = 0;
    }
    for (int i = 0; i < NUM_PROCESSES; i++) {
        processes.push_back(thread(bakery_process, i));
    }
    for (auto &process : processes) {
        process.join();
    }
    return 0;
}

Output:

text

Process 0 is in its critical section.
Process 0 is in its remainder section.
Process 1 is in its critical section.
Process 1 is in its remainder section.
...

How Do They Compare?

Factor	Peterson's	Dekker's	Bakery
Number of Processes	Two only	Two only	Multiple (N)
Complexity	Simple	More complex	Most complex
Fairness	Fair	Fair, minor starvation risk	Fair (ticket-based ordering)
Performance	Good for two processes	Less efficient due to back-off logic	Overhead from ticketing and max scan
Practical Use	Two-process scenarios	Mostly theoretical and academic	Multi-process scenarios

Peterson's Algorithm is the go-to when you just need two processes to stay out of each other's way. Dekker's covers the same ground but is harder to follow and rarely used outside of academic contexts. The Bakery Algorithm is the one to reach for when you have more than two processes competing for the same resource.

Each has its place, though in real systems today, most of this is handled at the hardware level with atomic instructions like Test-and-Set and Compare-and-Swap, which are far more efficient on modern multi-core processors.