OS Notes

Critical Section Problem

Deep dive into the critical section problem — requirements, software solutions (Peterson\

Introduction

The critical section problem is the fundamental challenge of concurrent programming. When multiple processes need to access shared resources, how do we ensure only one accesses it at a time without creating deadlocks or starvation? Solving this elegantly and correctly has been a focus of computer science research since the 1960s.

Think about a shared printer in an office. If two people send print jobs simultaneously without coordination, pages from different documents would interleave, producing gibberish. The critical section is the act of printing — only one job should print at a time. The solution must ensure mutual exclusion while being fair and not creating unnecessary delays.

Formal Definition

Consider n processes {P0, P1, ..., Pn-1}. Each process has a segment of code called the critical section where it accesses shared data. The problem is to design a protocol ensuring:

Mutual Exclusion: At most one process executes in its critical section at any time
Progress: If no process is in the critical section and some processes wish to enter, the selection of who enters next cannot be postponed indefinitely. Only processes trying to enter participate in the decision.
Bounded Waiting: After a process requests entry, there is a bound on the number of times other processes can enter before it gets its turn.

Software Solution: Peterson's Algorithm (2 Processes)

Example

// Shared variables int turn; bool flag[2] = {false, false}; // Process 0 void process_0() { while (true) { flag[0] = true; // P0 wants to enter turn = 1; // Give P1 priority while (flag[1] && turn == 1) ; // Wait if P1 wants in and it is P1s turn // === CRITICAL SECTION === // Access shared resource safely flag[0] = false; // P0 is done // === REMAINDER SECTION === } } // Process 1 void process_1() { while (true) { flag[1] = true; // P1 wants to enter turn = 0; // Give P0 priority while (flag[0] && turn == 0) ; // Wait if P0 wants in and it is P0s turn // === CRITICAL SECTION === flag[1] = false; // P1 is done // === REMAINDER SECTION === } }

Proof of Correctness

Mutual Exclusion: Both processes cannot be in their CS simultaneously. If P0 is in CS, then either flag[1]=false OR turn=0. If P1 is also trying to enter, flag[1]=true and turn would equal either 0 or 1 (set by whoever wrote last). Only one value is possible, so one must be spinning.

Progress: If P0 wants to enter and P1 is in remainder section (flag[1]=false), P0 enters immediately without waiting.

Bounded Waiting: P0 gives priority to P1 (sets turn=1). If both want in, whoever set turn last loses one round. After P1 enters and exits, P0 will enter next.

Bakery Algorithm (N Processes)

Lamport's Bakery Algorithm extends the solution to N processes using a "take a number" approach (like a bakery queue):

Example

bool choosing[N] = {false}; // Is process i picking a number? int number[N] = {0}; // Ticket number for each process void lock(int i) { choosing[i] = true; number[i] = max(number[0], ..., number[N-1]) + 1; choosing[i] = false; for (int j = 0; j < N; j++) { // Wait while j is choosing while (choosing[j]) ; // Wait while j has a smaller ticket (or same ticket but lower PID) while (number[j] != 0 && (number[j] < number[i] || (number[j] == number[i] && j < i))) ; } } void unlock(int i) { number[i] = 0; // Release ticket }

The process with the smallest non-zero ticket number enters. Ties are broken by process ID. This satisfies all three requirements for any number of processes.

Hardware-Assisted Solutions

Disabling Interrupts (Uniprocessor Only)

c example

void enter_critical_section() {
    disable_interrupts();  // Cannot be preempted
}

void exit_critical_section() {
    enable_interrupts();
}

Simple but dangerous — a process can monopolize the CPU. Only works on single-core systems (other cores are not affected by disabling one core's interrupts).

Atomic Test-and-Set Lock (TSL)

c example

// Implementation using hardware TSL instruction
bool lock = false;

void acquire() {
    while (test_and_set(&lock) == true)
        ;  // Spin (busy wait)
}

void release() {
    lock = false;
}

Satisfies mutual exclusion but NOT bounded waiting — a process can be starved if others keep getting the lock.

Bounded Waiting with Test-and-Set

Example

bool lock = false; bool waiting[N] = {false}; void acquire(int i) { waiting[i] = true; bool key = true; while (waiting[i] && key) key = test_and_set(&lock); waiting[i] = false; } void release(int i) { int j = (i + 1) % N; while (j != i && !waiting[j]) j = (j + 1) % N; if (j == i) lock = false; // No one waiting, release lock else waiting[j] = false; // Pass to next waiting process }

This ensures bounded waiting by explicitly passing the lock to the next waiting process in circular order.

Busy Waiting vs Blocking

Busy waiting (Spinlock): Process loops continuously checking if it can enter. Wastes CPU cycles but no context switch overhead. Good for short critical sections.

Blocking (Sleep/Wake): Process is put to sleep (moved to wait queue) when it cannot enter. Woken up when the CS becomes available. No CPU waste but context switch overhead. Good for long critical sections.

Real-World Analogy

The critical section problem is like managing a single conference room. Mutual exclusion means only one meeting at a time. Progress means if the room is empty and someone wants it, they can take it immediately (no bureaucratic delays). Bounded waiting means no one is permanently locked out while others keep booking. Peterson's solution is like two polite people who both say "after you" — whoever says it last actually goes first.

Key Takeaways

The critical section problem requires mutual exclusion, progress, and bounded waiting
Peterson's Algorithm solves it for 2 processes; Bakery Algorithm solves it for N processes
Software solutions are elegant but impractical on modern multi-core CPUs without memory barriers
Hardware atomic instructions (test-and-set, CAS) provide the foundation for practical solutions
Bounded waiting requires explicit fairness mechanisms (passing the lock in order)
Spinlocks waste CPU but avoid context switch cost; blocking saves CPU but has switch overhead
Modern systems use a combination: spin briefly, then block if still waiting

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Critical Section Problem.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, process, synchronization, critical, section

Continue learning this concept

Process SynchronizationDining Philosophers ProblemThe classic dining philosophers problem — problem statement, naive solution showing deadlock, correct solutions using semaphores, monitors, and resource hierarchy.Process SynchronizationProducer-Consumer ProblemThe classic producer-consumer (bounded buffer) synchronization problem — solutions using semaphores, mutex locks, and monitors with complete code examples.Process SynchronizationReaders-Writers ProblemThe readers-writers synchronization problem — first readers-writers problem (readers preference), second variant (writers preference), and starvation-free solutions.Process SynchronizationMonitorsUnderstanding monitors as a high-level synchronization construct — encapsulation, condition variables, wait and signal operations, and comparison with semaphores.Process SynchronizationMutex LocksUnderstanding mutex locks for mutual exclusion — acquire and release operations, spinlocks vs blocking mutexes, recursive mutexes, and practical mutex usage patterns.Process SynchronizationSemaphoresComplete guide to semaphores — counting and binary semaphores, wait() and signal() operations, implementation, usage patterns, and solving synchronization problems with semaphores.

PreviousThreads NextDining Philosophers Problem

OS Notes

Critical Section Problem

Deep dive into the critical section problem — requirements, software solutions (Peterson\

Introduction

Formal Definition

Consider n processes {P0, P1, ..., Pn-1}. Each process has a segment of code called the critical section where it accesses shared data. The problem is to design a protocol ensuring:

Mutual Exclusion: At most one process executes in its critical section at any time
Progress: If no process is in the critical section and some processes wish to enter, the selection of who enters next cannot be postponed indefinitely. Only processes trying to enter participate in the decision.
Bounded Waiting: After a process requests entry, there is a bound on the number of times other processes can enter before it gets its turn.

Software Solution: Peterson's Algorithm (2 Processes)

Example

Proof of Correctness

Progress: If P0 wants to enter and P1 is in remainder section (flag[1]=false), P0 enters immediately without waiting.

Bounded Waiting: P0 gives priority to P1 (sets turn=1). If both want in, whoever set turn last loses one round. After P1 enters and exits, P0 will enter next.

Bakery Algorithm (N Processes)

Lamport's Bakery Algorithm extends the solution to N processes using a "take a number" approach (like a bakery queue):

Example

The process with the smallest non-zero ticket number enters. Ties are broken by process ID. This satisfies all three requirements for any number of processes.

Hardware-Assisted Solutions

Disabling Interrupts (Uniprocessor Only)

c example

void enter_critical_section() {
    disable_interrupts();  // Cannot be preempted
}

void exit_critical_section() {
    enable_interrupts();
}

Simple but dangerous — a process can monopolize the CPU. Only works on single-core systems (other cores are not affected by disabling one core's interrupts).

Atomic Test-and-Set Lock (TSL)

c example

// Implementation using hardware TSL instruction
bool lock = false;

void acquire() {
    while (test_and_set(&lock) == true)
        ;  // Spin (busy wait)
}

void release() {
    lock = false;
}

Satisfies mutual exclusion but NOT bounded waiting — a process can be starved if others keep getting the lock.

Bounded Waiting with Test-and-Set

Example

This ensures bounded waiting by explicitly passing the lock to the next waiting process in circular order.

Busy Waiting vs Blocking

Busy waiting (Spinlock): Process loops continuously checking if it can enter. Wastes CPU cycles but no context switch overhead. Good for short critical sections.

Real-World Analogy

Key Takeaways

The critical section problem requires mutual exclusion, progress, and bounded waiting
Peterson's Algorithm solves it for 2 processes; Bakery Algorithm solves it for N processes
Software solutions are elegant but impractical on modern multi-core CPUs without memory barriers
Hardware atomic instructions (test-and-set, CAS) provide the foundation for practical solutions
Bounded waiting requires explicit fairness mechanisms (passing the lock in order)
Spinlocks waste CPU but avoid context switch cost; blocking saves CPU but has switch overhead
Modern systems use a combination: spin briefly, then block if still waiting

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Critical Section Problem.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, process, synchronization, critical, section

Continue learning this concept

PreviousThreads NextDining Philosophers Problem