Critical sections and Peterson algorithm solutions

Synchronization

Processes may operate concurrently on shared data, but any process can be interrupted at any point during its execution.

A process might need to read a value and operate on it with the assumption that the value will not be modified by another thread or process until it is written back to memory.

In preemptive systems, a situation such as the following can occur:

process_1: register_1 = count
process_1: register_1 = register_1 + 1 // context switch
process_2: register_2 = count
process_2: register_2 = register_2 - 1 // context switch
process_1: count = register_1          // context switch
process_2: count = register_2

In this case, two processes attempt to update count. However, due to the context switch, the final value obtained is not the expected value (which would be the initial value since one process adds 1 and the other subtracts 1). Instead, we get count - 1 because process 1′s update is written after process 2 has already read the original value of count.

This situation is known as a race condition.

Critical section

The critical section of a process is the segment of code where the process operates on values shared with other processes.

A solution to this problem must satisfy three constraints:

• Mutual exclusion: If a process is executing within its critical section, no other process can access the same shared data.
• Progress: If no process is in its critical section and one or more processes wish to enter, the operating system cannot indefinitely postpone the request for access.
• Bounded waiting: There must be a limit to the number of times other processes are allowed to enter the critical section after a process has requested access and is waiting.

Single core solutions

One initial approach is to disable interrupts to prevent the CPU from switching to another process while inside the critical section. However, this is problematic because it grants the process the possibility to disable preemption for an arbitrarily long duration.

Alternatively, one might explore a software, turn-based solution:

// process 1
while (true) {
    while (turn == i); // wait while it is the other process's turn
    // critical section
    turn = i; // assign the turn to the other process
    // remainder section
}

// process 2
while (true) {
    while (turn == j);
    // critical section
    turn = j;
    // remainder section
}

A flaw in this approach is that if one process never requires the critical section, it may never yield the turn. Consequently, if process j is waiting but process i never uses its turn, j will wait indefinitely.

Peterson’s solution addresses this by introducing a shared boolean flag[2] array, where turn indicates which process’s turn it is to enter the critical section, and flag indicates if a process is ready to enter the critical section.

while (true) {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
    // critical section
    flag[i] = false;
    // remainder section
}

This algorithm satisfies all three requirements for a critical section:

• Mutual exclusion is preserved.
• Progress is guaranteed because the turn mechanism ensures that a process will eventually gain access when its turn arrives.
• Bounded waiting is met because, after two processes have passed through, the turn must cycle back, preventing starvation.

Caution

Peterson’s solution is not suitable for modern systems:

• It is limited to two processes.
• Modern compilers may reorder operations that have no data dependencies to improve execution speed.

Ideally, we would want a single atomic instruction for entering and exiting the critical section.

Hardware support

Hardware provides three primary mechanisms to solve the Critical Section (CS) problem:

• memory barriers;
• hardware instructions (e.g., compare_and_swap and test_and_set);
• atomic variables;

Memory barriers

Memory models define the guarantees a computer architecture makes to application programs. A strongly ordered model ensures that a memory modification by one process is immediately visible to all others. A weakly ordered model does not guarantee immediate visibility.

A memory barrier is an instruction that forces any pending memory changes to be propagated (made visible) to all other processors.

When a memory barrier is used, the system guarantees that all prior loads and stores are completed before any subsequent load or store instruction executes.

Memory barriers are powerful, but they can introduce performance overhead because their effect is global.

Atomic instructions

Atomic instructions allow for operations like “check and set” on a variable in memory, guaranteeing that no other process can intervene during the operation.

// This operation is executed atomically by the hardware. If target was already
// true, no change occurs.
boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

The CS implementation using this instruction becomes:

while (true) {
    while (test_and_set(&lock));
    // critical section
    lock = false;
    // remainder section
}

The limitation here is bounded waiting. If one process executes test_and_set faster than others, it can gain exclusive control of the CS.

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;

    // Sets new_value only if the current value matches the expected value.
    if (*value == expected) {
        *value = new_value;
    }

    return temp;
}

Using this, the CS implementation is:

while (true) {
    while (compare_and_swap(&lock, 0, 1) != 0);
    // critical section
    lock = 0;
    // remainder section
}

This solution retains the same issue regarding bounded waiting. To resolve this, more complex checks are required:

// `lock` is initialized to 0.

while (true) {
    waiting[i] = true;
    key = 1;

    // Attempt to acquire the lock for the CS.
    // Process `i` can enter the CS if either waiting[i] is false or key is 0.
    while (waiting[i] && key == 1) {
        key = compare_and_swap(&lock, 0, 1);
    }

    waiting[i] = false;

    // critical section

    j = (i + 1) % n;
    // Check all other processes to see if any are waiting.
    while ((j != i) && !waiting[j]) {
        j = (j + 1) % n;
    }

    // If no other process is waiting, we release the lock.
    if (j == 1) {
        lock = 0;
    } else {
        // Allow another waiting process to proceed by bypassing its waiting condition.
        // The queue remains locked, and we manually signal control to the next thread.
        waiting[j] = false;
    }

    // remainder section
}

Atomic variables

Atomic variables are provided by a language’s standard library, leveraging atomic hardware instructions to ensure safe operations on basic data types.