Critical Regions

At its core, concurrent programming is about one thing: managing access to shared resources. When multiple threads or processes need to access the same memory, file, device, or any other resource, we face a fundamental challenge:

How do we ensure that concurrent accesses don't corrupt the resource or produce incorrect results?

The answer centers on the concept of critical regions (also known as critical sections)—the portions of code that access shared resources and must be executed without interference from other threads.

Every synchronization technique—every mutex, semaphore, condition variable, or lock-free algorithm—ultimately exists to solve the critical region problem. Understanding this concept deeply is essential for understanding all concurrent programming.

A critical region is a section of code that accesses shared resources and must not be executed concurrently by more than one thread.

More formally:

A critical region is a sequence of instructions that accesses a shared resource (memory, file, device, etc.) such that the resource could become inconsistent if the sequence is interrupted mid-execution by another thread accessing the same resource.

The key insight is that critical regions aren't about any code—they're specifically about code that:

1. Accesses something shared (e.g., global variable, shared data structure)
2. Leaves that shared resource in a temporarily inconsistent state during execution
3. Expects to complete the access without interference

Examples of critical regions:

• Incrementing a shared counter (read-modify-write)
• Adding a node to a shared linked list (updating pointers)
• Transferring money between accounts (decrement one, increment other)
• Writing to a log file (must write complete entries)
• Updating a database record (multi-field consistency)

The critical section problem is the formal statement of the challenge:

Design a protocol that processes/threads can use to coordinate access to their critical sections, ensuring that when any process is executing in its critical section, no other process is executing in its corresponding critical section for the same resource.

Notice the phrase 'corresponding critical section'—processes have separate critical sections for separate resources. Process A in a critical section for resource X doesn't prevent Process B from accessing resource Y.

The general structure of a process with a critical section:

while (true) {
    // Entry section: acquire permission to enter
    ENTRY_SECTION();
    
    // Critical section: access shared resource
    CRITICAL_SECTION();
    
    // Exit section: release permission, signal others
    EXIT_SECTION();
    
    // Remainder section: code that doesn't access the shared resource
    REMAINDER_SECTION();
}

The entry section and exit section together form the synchronization protocol. The goal is to design these sections such that certain requirements are satisfied.

A correct solution to the critical section problem must satisfy three essential requirements:

1. Mutual Exclusion

If a process is executing in its critical section, no other process can be executing in its critical section (for the same resource) at the same time.

This is the primary requirement—the whole point of identifying critical sections. Without mutual exclusion, we have a data race.

2. Progress

If no process is executing in its critical section, and some processes wish to enter their critical sections, then only those processes not in their remainder sections can participate in deciding which will enter next, and this selection cannot be postponed indefinitely.

In simpler terms: if the critical section is free and someone wants it, someone must get it. The system cannot deadlock with everyone waiting for permission when no one holds it.

3. Bounded Waiting

There exists a bound on the number of times other processes can enter their critical sections after a process has made a request to enter and before that request is granted.

In simpler terms: a process cannot be starved forever. If a process requests entry, it must eventually be allowed in—not after an unbounded number of other entries.

Why all three matter:

• Mutual exclusion alone isn't enough—you might achieve it by never letting anyone in!
• Without progress, threads could all wait forever even when the resource is free
• Without bounded waiting, 'unlucky' threads might starve while others repeatedly access the resource

Additional desirable properties:

• Fairness — Processes enter in the order they requested (FIFO) or at least with some equitable policy
• Efficiency — Low overhead when no contention; minimal CPU wasted during waiting
• Scalability — Performance doesn't degrade badly as process count increases

Understanding why naive approaches fail is illuminating. Let's examine some incorrect solutions:

Attempt 1: Taking Turns

int turn = 0;  // Whose turn (0 or 1)

// Process 0
while (turn != 0) ; // Wait
CRITICAL_SECTION();
turn = 1;  // Give turn to Process 1

// Process 1
while (turn != 1) ; // Wait
CRITICAL_SECTION();
turn = 0;  // Give turn to Process 0

Problem: Fails the progress requirement. If Process 1 finishes its critical section and sets turn = 0, but then enters a long remainder section, Process 0 cannot enter the critical section a second time (turn is 0, letting it enter once, but after that it sets turn = 1 and waits for Process 1). If Process 1 isn't ready to enter yet, Process 0 is blocked even though the resource is free.

Verdict: Mutual exclusion ✓, Progress ✗, Bounded Waiting ✗

Attempt 2: Flag Array

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

// Process 0
flag[0] = true;       // I want to enter
while (flag[1]) ;     // Wait if other wants in
CRITICAL_SECTION();
flag[0] = false;      // I'm done

// Process 1  
flag[1] = true;       // I want to enter
while (flag[0]) ;     // Wait if other wants in
CRITICAL_SECTION();
flag[1] = false;      // I'm done

Problem: Possible deadlock. Both processes could set their flags simultaneously, then both wait forever for the other's flag to clear.

Verdict: Mutual exclusion ✓, Progress ✗ (deadlock), Bounded Waiting ✗

Attempt 3: Flag with Turn

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

// Process i
flag[i] = true;       // I want to enter
turn = j;             // But let other go first
while (flag[j] && turn == j) ; // Wait if other wants in AND it's their turn
CRITICAL_SECTION();
flag[i] = false;      // I'm done

This is Peterson's Solution! It works because:

• If both want to enter, the turn variable breaks the tie
• Whoever set turn last waits (is courteous to the other)
• Combined with flags, it achieves all three requirements

Entry and exit sections can be implemented in various ways, each with different trade-offs:

Entry Section Strategies:

1. Busy Waiting (Spinning)

Repeatedly check a condition until it's true:

while (locked) ; // spin
locked = true;   // enter

• Pros: Lowest latency when lock is available; no kernel involvement
• Cons: Wastes CPU cycles; problematic if holder is on same CPU (holder can't run to release)
• Best for: Short critical sections, multi-core systems, real-time constraints

2. Blocking (Sleep/Wake)

Suspend the thread until the lock becomes available:

if (locked) {
    add_to_wait_queue();
    sleep();  // OS deschedules this thread
}
locked = true;

• Pros: Doesn't waste CPU; works well for long waits
• Cons: Context switch overhead (~1000+ cycles); wake-up latency
• Best for: Long critical sections, single-core systems, battery-constrained devices

3. Hybrid (Spin-then-Block)

Spin briefly, then block if lock isn't acquired:

for (int i = 0; i < SPIN_LIMIT; i++) {
    if (!locked) { locked = true; return; }
}
add_to_wait_queue();
sleep();

• Pros: Best of both worlds for mixed workloads
• Cons: Tuning the spin limit is workload-dependent
• Used by: Most modern mutex implementations (adaptive mutexes)

Exit Section Requirements:

The exit section must:

1. Release the lock atomically — Ensure the lock is fully released before any waiting thread can acquire it

2. Signal waiters (if blocking) — Wake up one or more waiting threads. Policies include:

   • Wake one (most common) — Reduces thundering herd
   • Wake all — Necessary for condition variables signaling multiple waiters

3. Provide memory ordering — Ensure all writes in the critical section are visible before the lock is released (release semantics)

4. Be interrupt-safe (in kernels) — On single-core systems, might need to restore interrupt state

The scope of a critical region—how much code it contains—significantly impacts both correctness and performance. This is a fundamental design decision.

Coarse-grained locking:

Use one lock for an entire data structure or subsystem.

pthread_mutex_t db_lock;  // One lock for entire database

void query(int id) {
    lock(&db_lock);
    // ALL database operations serialized
    result = search_index(id);
    data = fetch_record(result);
    unlock(&db_lock);
    return data;
}

• Pros: Simple; easy to reason about; fewer deadlock opportunities
• Cons: Low parallelism; one slow operation blocks all others; doesn't scale

Fine-grained locking:

Use separate locks for different parts of a data structure.

// Each bucket has its own lock
struct HashTable {
    struct Bucket buckets[1024];
    pthread_mutex_t bucket_locks[1024];
};

void insert(struct HashTable* ht, int key, void* value) {
    int b = hash(key) % 1024;
    lock(&ht->bucket_locks[b]);  // Only lock the relevant bucket
    insert_into_bucket(&ht->buckets[b], key, value);
    unlock(&ht->bucket_locks[b]);
}

• Pros: High parallelism; different buckets accessed concurrently
• Cons: Complex; more deadlock risk (if acquiring multiple locks); memory overhead for many locks

The Golden Rule: Hold Locks for the Shortest Time Possible

Regardless of granularity, critical sections should be as short as possible:

// WRONG: Long critical section
lock(&mutex);
data = compute_expensive_result();  // Slow! Others blocked
shared_result = data;
unlock(&mutex);

// RIGHT: Short critical section
data = compute_expensive_result();  // Do this outside lock
lock(&mutex);
shared_result = data;  // Only the shared access is protected
unlock(&mutex);

Move all computation that doesn't require the shared resource outside the critical section. Only the actual access to shared data needs protection.

When a thread in one critical region needs to enter another critical region, we have nested critical regions. This is common but introduces significant complexity.

The Deadlock Danger:

Consider two locks A and B, and two threads:

Thread 1: lock(A) → lock(B) → unlock(B) → unlock(A)
Thread 2: lock(B) → lock(A) → unlock(A) → unlock(B)

Possible interleaving:

1. Thread 1 acquires A
2. Thread 2 acquires B
3. Thread 1 waits for B (held by Thread 2)
4. Thread 2 waits for A (held by Thread 1)

Deadlock! Neither can proceed.

Solution 1: Lock Ordering

Always acquire locks in the same global order:

// Rule: Always acquire A before B
void thread1() { lock(A); lock(B); /* ... */ unlock(B); unlock(A); }
void thread2() { lock(A); lock(B); /* ... */ unlock(B); unlock(A); }
// Now deadlock is impossible

This is the most common solution. Define a total order on all locks (by address, by hierarchy, by name) and always follow it.

Solution 2: Try-Lock with Backoff

Attempt to acquire the second lock without blocking:

lock(A);
if (!try_lock(B)) {
    unlock(A);  // Back off
    // Wait, retry
}

This avoids deadlock but can cause livelock (repeated backoff without progress).

Solution 3: Lock Hierarchies

Organize locks into levels; only acquire higher-level locks, never lower:

Level 3: Application locks
Level 2: Subsystem locks
Level 1: Data structure locks
Level 0: Base layer locks

// Holding a level 2 lock, you may only acquire level 3, 4, ...
// Never acquire level 1 or 0 while holding level 2

Solution 4: Single Lock

Refactor to eliminate nesting by using one lock that covers both resources. Trades parallelism for simplicity.

// Instead of locking A and B separately
lock(&combined_lock);  // Protects both A and B
access_A();
access_B();
unlock(&combined_lock);