Race Conditions and the Critical Section

Analogy categoryAnalogies

Introduction

A race condition occurs when two or more threads or processes access shared data concurrently and the final result depends on the unpredictable timing (interleaving) of their execution. Race conditions are one of the most common sources of bugs in concurrent programs because the code often appears correct when tested serially but fails intermittently under real scheduling. The region of code where shared data is accessed and must not be interleaved with another thread's access is called the critical section.

🏏

Cricket analogy: Two fielders both call for the same catch and collide because neither hears the other's timing, dropping the ball entirely -- a race condition where the outcome depends on who shouted first; the small patch of turf under a skied catch is the critical section only one fielder should occupy.

Explanation

Consider two threads that both execute counter++. This single line of C typically compiles into three machine instructions: load counter into a register, increment the register, store the register back to counter. If both threads load the old value before either stores the new value, one increment is lost. Any solution to this problem must satisfy three requirements for the critical section: (1) Mutual Exclusion — only one process/thread may execute in its critical section at a time; (2) Progress — if no process is in its critical section, one of the processes waiting to enter must be able to do so without indefinite delay, and this decision cannot be postponed indefinitely by processes not in their critical/remainder sections; (3) Bounded Waiting — there must be a limit on the number of times other processes are allowed to enter their critical sections after a process has requested entry and before that request is granted, so no process starves forever.

🏏

Cricket analogy: Two scorers both update the team total from the same delivery: one reads '150', increments to '154' for a boundary, but before saving, the other scorer also read '150' and overwrites with their own '151' -- the six runs get lost; mutual exclusion means only one scorer touches the ledger at a time, progress means the waiting scorer isn't blocked forever by an idle one, and bounded waiting means no scorer waits through infinite overs before their turn.

Example

#include <stdio.h>
#include <pthread.h>

#define NUM_THREADS 4
#define INCREMENTS  100000

long counter = 0; /* shared, unprotected -> race condition */

void *increment(void *arg) {
    for (int i = 0; i < INCREMENTS; i++) {
        counter++;              /* NOT atomic: load, add, store */
    }
    return NULL;
}

int main(void) {
    pthread_t threads[NUM_THREADS];

    for (int i = 0; i < NUM_THREADS; i++)
        pthread_create(&threads[i], NULL, increment, NULL);

    for (int i = 0; i < NUM_THREADS; i++)
        pthread_join(threads[i], NULL);

    printf("Expected: %d, Actual: %ld\n",
           NUM_THREADS * INCREMENTS, counter);
    /* Actual is almost always LESS than Expected -> lost updates */
    return 0;
}

Analysis

Running this program repeatedly on a multi-core machine typically prints an Actual value smaller than the Expected value of 400000, and the shortfall varies from run to run because it depends on how the CPU scheduler interleaves the threads. This non-determinism is the signature of a race condition: counter++ is not atomic, so an update from one thread can be silently overwritten by another. The fix is to make the increment a critical section protected by a mutual-exclusion mechanism such as a pthread_mutex_t (covered in the next topic), which restores a deterministic, correct result on every run.

🏏

Cricket analogy: Running the same 100-over practice drill repeatedly with two scorers keeping an unsynchronized tally, the final run count usually falls short of the expected total, and by how much varies each time depending on how their updates overlap -- proof that unsynchronized scoring, like counter++, isn't atomic and needs one designated official scorer.

Key Takeaways

A race condition happens when the outcome of concurrent execution depends on timing/interleaving of accesses to shared data.
The critical section is the code region that accesses shared resources and must run without interleaving from other threads/processes.
A valid solution must guarantee Mutual Exclusion, Progress, and Bounded Waiting.
Even a single line like counter++ is usually not atomic at the machine-instruction level.
Race conditions are non-deterministic and can be hard to reproduce, making them notoriously difficult to debug.

Practice what you learned

1. What is a race condition?

2. Which of the following is NOT one of the three required properties of a critical-section solution?

3. Why does `counter++` in C typically fail to be atomic on most architectures?

4. The 'Progress' requirement means:

Was this page helpful?

Mutex and Semaphores

Topics covered

#OperatingSystemsStudyNotes#OperatingSystems#RaceConditionsAndTheCriticalSection#Race#Conditions#Critical#Section#StudyNotes#SkillVeris#ExamPrep