Critical Section Problems

Definition

A Critical Section Problem refers to the challenge of managing multiple processes accessing shared resources simultaneously. It’s the fundamental synchronization problem in operating systems. The goal is to design algorithms that ensure correct concurrent access while maintaining efficiency.

What Makes Critical Section Complex?

Multiple Processes Needing Access

Process 1: Wants to access file
Process 2: Wants to access file
Process 3: Wants to access file
Process 4: Wants to access file

File (Shared Resource)

Problem: Who goes first? How to ensure consistency?

Concurrent Execution

Processes don’t execute in predictable order - execution interleaving is arbitrary:

Scenario A:
Process 1: [CS] [CS] [CS]
Process 2: [CS] [CS] [CS]
Result: Correct

Scenario B (different timing):
Process 1: read() | yield | write()
Process 2:         read() | write()
Result: WRONG! (race condition)

The Critical Section Problem

Definition

A system with N processes, each with code section accessing shared resource (critical section). Problem: Design algorithm such that:

1. Mutual Exclusion: Only one process in CS at a time
2. Progress: If no process in CS, waiting process enters
3. Bounded Waiting: No process waits indefinitely

Structure of Each Process

while (true) {
    // Entry Section
    // Algorithm to enter CS

    // CRITICAL SECTION
    // Access shared resource

    // Exit Section
    // Release CS for others

    // Remainder Section
    // Non-critical work
}

Examples of Critical Section Problems

Example 1: Bank Account (2 Processes)

Initial Balance: 1000

Thread 1:                    Thread 2:
read balance (1000)          read balance (1000)
add 100                      subtract 500
write (1100)                 write (500)

Expected: 600 (1000+100-500)
Actual (bad timing): 500 or 1100 (one update lost!)

Example 2: Print Spooler (Multiple Processes)

Process 1: wants to print (adds to queue)
Process 2: wants to print (adds to queue)
Process 3: wants to print (adds to queue)

Queue: [1000][1001][1002] (next free slot)

Problem: All three processes try to write to slot 1000 simultaneously
Result: Some jobs never print!

Example 3: Database Update (Multiple Processes)

Database Record:
  name = "John"
  age = 30

Process 1: Update name to "Jane"
  read record
  modify name
  write back

Process 2: Update age to 31
  read record
  modify age
  write back

Bad timing:
Process 1: read (John, 30)
Process 2: read (John, 30)
Process 1: write (Jane, 30)
Process 2: write (John, 31) ← overwrites Process 1's change!

Result: name is John (change lost), age is 31

Software Solutions to Critical Section Problem

Solution 1: Strict Alternation

Use shared variable to track whose turn it is:

int turn = 0;  // Process 0's turn initially

Process 0:
while (true) {
    while (turn != 0) {
        // Wait for my turn
    }
    // CRITICAL SECTION
    shared_variable++;
    turn = 1;  // Give turn to Process 1
}

Process 1:
while (true) {
    while (turn != 1) {
        // Wait for my turn
    }
    // CRITICAL SECTION
    shared_variable--;
    turn = 0;  // Give turn to Process 0
}

Problems:

• ❌ Violates Progress: If Process 1 crashes in CS, Process 0 waits forever
• ❌ Violates Fairness: Both must alternate (Process 0 can’t go twice)
• ❌ Process must alternate even if one has nothing to do

Solution 2: Flag-Based Approach

Use shared boolean array to track interest:

bool interested[2] = {false, false};

Process 0:
while (true) {
    interested[0] = true;
    while (interested[1]) {
        // Wait if Process 1 also interested
    }
    // CRITICAL SECTION
    shared_variable++;
    interested[0] = false;  // Done, not interested anymore
}

Process 1: Similar with 0 and 1 swapped

Problems:

• ❌ Still has race condition!
• Both processes set interested=true simultaneously
• Both think other isn’t interested yet
• Both enter CS (violates mutual exclusion)

Solution 3: Peterson’s Algorithm

Combines flag and turn:

bool interested[2] = {false, false};
int turn = 0;

Process 0:
while (true) {
    interested[0] = true;
    turn = 1;  // Give turn to Process 1
    while (interested[1] && turn == 1) {
        // Wait if Process 1 interested AND it's their turn
    }
    // CRITICAL SECTION
    shared_variable++;
    interested[0] = false;
}

Process 1: Similar with 0 and 1 swapped

Properties:

• ✓ Mutual Exclusion
• ✓ Progress
• ✓ Bounded Waiting

Proven correct for 2 processes!

Solution 4: Bakery Algorithm

Generalization of Peterson’s for N processes

Each process takes “ticket” like at bakery:

bool choosing[n] = {false};
int ticket[n] = {0};

Process i:
while (true) {
    choosing[i] = true;
    ticket[i] = max(ticket[0], ..., ticket[n-1]) + 1;
    choosing[i] = false;

    for (j = 0; j < n; j++) {
        while (choosing[j]) {
            // Wait
        }
        while ((ticket[j] != 0) &&
               ((ticket[j], j) < (ticket[i], i))) {
            // Wait for higher priority
        }
    }

    // CRITICAL SECTION
    shared_variable++;
    ticket[i] = 0;  // "Leave" and reset
}

Properties:

• ✓ Works for any N processes
• ✓ All three properties satisfied
• ❌ Busy waiting (spinning wastes CPU)

Hardware-Based Solutions

Test-and-Set Instruction

CPU provides atomic operation:

bool test_and_set(bool *target) {
    bool rv = *target;
    *target = true;
    return rv;
}

// Usage:
while (test_and_set(&lock)) {
    // Spin if lock taken
}
// CRITICAL SECTION
lock = false;

Compare-and-Swap

bool compare_and_swap(int *value, int expected, int new) {
    if (*value == expected) {
        *value = new;
        return true;
    }
    return false;
}

// Usage:
while (!compare_and_swap(&lock, 0, 1)) {
    // Spin
}
// CRITICAL SECTION
lock = 0;

OS-Level Solutions

Mutex Lock

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock);
// CRITICAL SECTION
pthread_mutex_unlock(&lock);

No busy waiting - process sleeps if unavailable.

Semaphore

Semaphore s = 1;

wait(s);
// CRITICAL SECTION
signal(s);

Monitor

Language-level abstraction (Java, C#):

synchronized void critical_section() {
    // Only one thread can be here
    shared_variable++;
}

Evaluation Criteria for Solutions

Modern Approach

Modern systems use OS-level synchronization primitives (locks, semaphores, monitors) rather than implement from scratch:

Why?:

1. ✓ Tested and proven correct
2. ✓ Optimized by kernel
3. ✓ No busy waiting
4. ✓ Works with multi-core
5. ✓ Programmers don’t need to implement

Summary

Critical section problem is fundamental to concurrent systems. Solutions exist at three levels: software (Peterson’s, Bakery), hardware (atomic instructions), and OS-level (locks, semaphores). Software solutions like Peterson’s are good for understanding but waste CPU via busy waiting. Modern systems use OS-level primitives that efficiently implement mutual exclusion, progress, and fairness. Understanding the problem and its solutions is essential for writing correct concurrent code.