The Critical Section Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// Example: Optimizing by expanding the remainder section
 
// BEFORE: Excessive code in critical section
void process_request_bad(Request* req) {
    mutex_lock(&processing_mutex);
    // ====== CRITICAL SECTION (too large) ======
    validate_request(req);           // Pure computation - no shared state!
    parse_request(req);              // Pure computation - no shared state!
    Response resp = compute_response(req);  // Expensive, but no shared state!
    update_statistics(&global_stats, req);  // Needs synchronization
    write_to_log(req, resp);         // Could use thread-local buffer!
    // ===========================================
    mutex_unlock(&processing_mutex);
    
    send_response(req->client, resp);
}
// Problem: Most work doesn't need the lock!
 
// AFTER: Minimized critical section, expanded remainder section
void process_request_good(Request* req) {
    // ====== REMAINDER SECTION (before CS) ======
    // All this work is thread-local, runs while others work
    validate_request(req);           // Pure function
    parse_request(req);              // Pure function
    Response resp = compute_response(req);  // Expensive but local
    
    // ====== ENTRY SECTION ======
    mutex_lock(&processing_mutex);
    
    // ====== CRITICAL SECTION (minimal) ======
    update_statistics(&global_stats, req);  // Only this needs the lock!
    // ===========================================
    
    // ====== EXIT SECTION ======
    mutex_unlock(&processing_mutex);
    
    // ====== REMAINDER SECTION (after CS) ======
    write_to_thread_local_log(req, resp);  // Thread-local buffer
    send_response(req->client, resp);      // Per-connection, no sharing
}
// Benefit: Threads can process in parallel, only statistics update is serialized

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

// ANTIPATTERN: Single global lock
struct GlobalState {
    Counter counter;
    UserDatabase users;
    TransactionLog log;
    SessionCache cache;
};
 
mutex_t global_lock;  // One lock for everything!
 
void process_user_request(Request* r) {
    mutex_lock(&global_lock);  // Everyone waits here
    
    // Even if we only touch the cache, 
    // we block access to counter, users, and log!
    Session* s = cache_lookup(&state.cache, r->session_id);
    
    mutex_unlock(&global_lock);
}
 
// BETTER: Fine-grained locks
struct GlobalState {
    struct {
        Counter counter;
        mutex_t lock;
    } counter_data;
    
    struct {
        UserDatabase users;
        rwlock_t lock;  // Multiple readers OK
    } user_data;
    
    struct {
        TransactionLog log;
        mutex_t lock;
    } log_data;
    
    struct {
        SessionCache cache;
        mutex_t lock;
    } cache_data;
};
 
void process_user_request_better(Request* r) {
    mutex_lock(&state.cache_data.lock);  // Only cache lock
    
    // Other threads can access counter, users, log concurrently!
    Session* s = cache_lookup(&state.cache_data.cache, r->session_id);
    
    mutex_unlock(&state.cache_data.lock);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// HYPOTHETICAL BROKEN ALGORITHM that violates progress
// by involving remainder section processes
 
// Each process must "vote" before anyone enters CS
volatile int vote[N];  // 0 = no opinion, 1 = OK to enter
 
void broken_entry_section(int process_id) {
    // Request votes from ALL processes
    for (int i = 0; i < N; i++) {
        vote[i] = 0;  // Reset votes
    }
    
    // Wait until all processes vote OK
    for (int i = 0; i < N; i++) {
        while (vote[i] == 0) {
            // BLOCKED! If process i is in remainder section doing
            // a long computation, it might never vote.
            // Progress is violated!
        }
    }
}
 
// In remainder section, each process periodically:
void remainder_section_processing(int process_id) {
    // ... long computation ...
    
    // Maybe eventually vote
    vote[process_id] = 1;  // But this might take forever!
    
    // ... more computation ...
}
 
// FIX: Correct algorithms (like Peterson's) only involve
// processes that are actively trying to enter CS:
void peterson_entry(int process_id) {
    flag[process_id] = 1;  // I WANT IN
    turn = other;
    
    // Only waits for the OTHER process IF:
    // - Other wants in (flag[other] == 1), AND
    // - It's other's turn
    // If other is in remainder section, flag[other] = 0, we enter immediately!
    while (flag[other] == 1 && turn == other);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

// Analyzing access patterns to choose synchronization strategy
 
// Pattern A: SHORT REMAINDER, SHORT CS
// Example: Updating a shared counter for every operation
void pattern_a_counter_update(void) {
    for (int i = 0; i < MILLION; i++) {
        // Remainder: almost nothing
        // CS: increment shared counter
        mutex_lock(&counter_lock);
        shared_counter++;  // 1 instruction
        mutex_unlock(&counter_lock);
        // Back to remainder immediately
    }
}
// Best approach: atomic increment (no lock at all)
// atomic_fetch_add(&shared_counter, 1);
 
// Pattern B: LONG REMAINDER, SHORT CS
// Example: Worker threads processing independent jobs
void pattern_b_worker_thread(void) {
    while (true) {
        Job* job;
        
        // ENTRY + CS: Get next job (brief)
        mutex_lock(&queue_lock);
        job = dequeue(&job_queue);
        mutex_unlock(&queue_lock);
        
        // REMAINDER: Do the work (long)
        process_job(job);  // Might take seconds
        save_results(job);
    }
}
// Best approach: simple mutex, contention is rare
 
// Pattern C: SHORT REMAINDER, LONG CS
// Example: Database transactions
void pattern_c_database_transaction(void) {
    // Remainder: prepare transaction (brief)
    Transaction* tx = prepare();
    
    // CS: execute transaction (long)
    db_lock();
    execute_multiple_queries(tx);  // Many operations
    update_indexes(tx);
    flush_to_disk(tx);  // I/O!
    db_unlock();
    
    // Remainder: notify (brief)
    notify_completion(tx);
}
// Problem: Long CS hurts concurrency
// Better approach: Fine-grained locking (per-table or per-row)
// Or: Optimistic concurrency (check conflicts at commit)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// Real-time task structure example
typedef struct {
    int period_ms;           // How often task runs
    int computation_ms;      // Time when not in CS (remainder)
    int critical_section_ms; // Time in CS
    int deadline_ms;         // When task must complete
    int priority;            // Scheduling priority (higher = more important)
    mutex_t* required_lock;  // Lock this task needs
} RealtimeTask;
 
// Example real-time system
RealtimeTask tasks[] = {
    // High priority: Quick sensor read, long remainder (analysis)
    {.period_ms = 100, .computation_ms = 80, .critical_section_ms = 2,
     .deadline_ms = 100, .priority = 10, .required_lock = &sensor_lock},
    
    // Medium priority: Control loop, balanced remainder/CS
    {.period_ms = 50, .computation_ms = 20, .critical_section_ms = 10,
     .deadline_ms = 50, .priority = 5, .required_lock = &actuator_lock},
    
    // Low priority: Logging, long CS (file I/O), long period
    {.period_ms = 1000, .computation_ms = 50, .critical_section_ms = 100,
     .deadline_ms = 1000, .priority = 1, .required_lock = &log_lock},
};
 
// Blocking time analysis:
// - High priority task uses sensor_lock: Not shared by others, no blocking
// - Medium priority uses actuator_lock: Not shared by others, no blocking  
// - BUT if they shared a lock, high priority could be blocked by low
//   for up to 100ms (low's CS duration)!
 
// With priority inheritance mutex:
void high_priority_task_with_inheritance(void) {
    // When we block on lock held by low-priority task,
    // low-priority task's priority is boosted to ours
    // This ensures low finishes quickly, minimizing our blocking time
    pthread_mutex_lock(&shared_lock);  // Uses PTHREAD_PRIO_INHERIT
    // ... critical section ...
    pthread_mutex_unlock(&shared_lock);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// Copy-on-entry pattern
void process_with_copy(void) {
    DataCopy local_copy;
    
    // Brief CS: just copy the data
    mutex_lock(&data_lock);
    local_copy = shared_data;  // Shallow or deep copy
    mutex_unlock(&data_lock);
    
    // Long remainder: work on the copy
    Result result = expensive_computation(&local_copy);
    
    // Brief CS: merge results back
    mutex_lock(&data_lock);
    merge_result(&shared_data, &result);
    mutex_unlock(&data_lock);
}
 
// Trade-off: Works well for read-heavy workloads
// Caveat: May need conflict detection if data changed while computing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Thread-local accumulation pattern
__thread int local_counter = 0;  // Each thread has its own
int global_counter = 0;
mutex_t counter_lock;
 
void increment(void) {
    // REMAINDER: Update thread-local (no synchronization!)
    local_counter++;
    
    // Only occasionally merge to global
    if (local_counter >= BATCH_SIZE) {
        mutex_lock(&counter_lock);
        global_counter += local_counter;  // CS: quick bulk update
        mutex_unlock(&counter_lock);
        local_counter = 0;
    }
}
 
// Results:
// - 99% of increments are lock-free
// - CS occurs only every BATCH_SIZE operations
// - Dramatically reduces contention

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// RCU-style optimization (simplified concept)
struct Data {
    // ... lots of fields ...
};
 
atomic_ptr<Data> shared_ptr;  // Atomic pointer to current data
 
// Readers: No lock, no waiting! (all in "remainder")
Data* read_data(void) {
    Data* ptr = atomic_load(&shared_ptr);  // Atomic read
    // Use ptr freely - the data won't be freed while we're using it
    // (Requires a grace period mechanism)
    return ptr;
}
 
// Writer: Does heavy work in remainder, brief atomic swap
void update_data(UpdateInfo* info) {
    // REMAINDER: Prepare new version (no lock)
    Data* old_ptr = atomic_load(&shared_ptr);
    Data* new_ptr = malloc(sizeof(Data));
    *new_ptr = *old_ptr;  // Copy old data
    apply_update(new_ptr, info);  // Modify the copy
    
    // CS: Just an atomic pointer swap!
    atomic_store(&shared_ptr, new_ptr);
    
    // REMAINDER: Reclaim old data after grace period
    // (Wait until all readers using old_ptr have finished)
    synchronize_rcu();
    free(old_ptr);
}
 
// RCU is used extensively in the Linux kernel for read-mostly structures