Bounded Waiting: The Fairness… — Requirements for… | OneNoughtOne

0/105

Operating SystemsRequirements for Solutions

Requirements for Solutions to the Critical Section Problem

LevelIntermediate

Duration90 mins

TopicRequirements for Solutions

3 / 5

Bounded Waiting: The Fairness Guarantee

Beyond Progress: Ensuring Every Process Gets Its Turn

We have established that mutual exclusion ensures safety (no concurrent critical section access) and progress ensures liveness (the system moves forward). But consider this scenario: Two processes, P₀ and P₁, contend for a critical section. The algorithm satisfies mutual exclusion and progress. P₀ enters, exits, and immediately re-enters. P₁ is waiting. P₀ exits, immediately re-enters again. P₁ continues waiting. This pattern repeats indefinitely. Is this acceptable? The system is making progress—P₀ is executing its critical section repeatedly. Mutual exclusion holds—only one process is ever inside. But P₁ is starving —it may wait forever while P₀ monopolizes the resource. The third fundamental requirement, Bounded Waiting, addresses exactly this unfairness. It guarantees that no process can be bypassed indefinitely—that every waiting process will eventually get its turn. This page provides a comprehensive treatment of bounded waiting: its formal definition, its importance, how to design solutions that satisfy it, and how to verify the property analytically.

What You Will Learn

By the end of this page, you will understand the formal definition of bounded waiting, distinguish it clearly from progress, identify starvation in synchronization algorithms, design fair synchronization solutions, and verify bounded waiting through analysis.

Defining Bounded Waiting

Why 'Bounded' Rather Than 'Zero'?

We allow OTHER processes to enter some finite number of times rather than requiring immediate entry. This is because: (1) already-running critical sections must complete, (2) processes already ahead in any queue should go first, and (3) requiring immediate entry could itself cause problems. The key is that the wait is BOUNDED, not minimal.

bounded_waiting_illustration.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Illustration: Bounded Waiting with Bound B = n-1 (for n processes)
 
// Timeline showing process requests and critical section entries:
 
Time:  ─────────────────────────────────────────────────────────────►
 
P₀:    ────request───────────────────────────────────enter CS─────
                     ↑                                   ↓
                     └───── waiting period ──────────────┘
                     
P₁:    ───────────enter CS────────────────────────────────────────
                         ↑
                         └─ counts toward P₀'s bound (1)
                         
P₂:    ─────────────────────enter CS──────────────────────────────
                                   ↑
                                   └─ counts toward P₀'s bound (2)
 
// If P₁ and P₂ EACH enter only once before P₀, and there are 3 processes:
// Bound = n - 1 = 2, and P₀ waited through 2 entries ✓ Bounded waiting satisfied
 
// VIOLATION would be:
// P₁ enters, P₂ enters, P₁ enters again, P₂ enters again... 
// while P₀ never gets in. That's unbounded!

Starvation and Its Consequences

Starvation is the condition where bounded waiting fails—a process waits indefinitely while others repeatedly access the critical section. Unlike deadlock (no progress) or livelock (active but no progress), starvation involves the system making progress while leaving specific processes behind. Characteristics of Starvation Starvation is particularly insidious because: The system appears healthy — Overall throughput is good; most processes are running fine Few processes are affected — Only some processes suffer; others don't notice Detection is difficult — A starving process looks like a slow process Reproduction is hard — Starvation often depends on specific timing conditions

Causes of Starvation

•Priority-based selection: If processes with higher priority are always chosen, low-priority processes may never run
•Race-based selection: If entry is determined by 'first to grab the lock', unlucky processes may always lose the race
•Positional bias: Algorithms that favor certain process IDs (like lower-numbered first) can systematically starve higher-numbered processes
•Cache-local bias: On NUMA systems, processes on the 'wrong' node may consistently lose to cache-local processes
•Temporary high contention: Bursts of activity can cause some processes to be repeatedly bypassed

Real-World Starvation Scenarios

Starvation in Real Systems
System	Starved Entity	Cause	Consequence
Web server	Requests from slow clients	Fast clients monopolize connection pool	Slow clients timeout repeatedly
Database	Low-priority queries	Continuous stream of high-priority queries	Reports never complete
File system	Large file operations	Many small file operations preempt	Backup jobs never finish
Network switch	Low-QoS traffic	High-QoS traffic saturation	Best-effort packets dropped
Memory allocator	Large allocations	Frequent small allocations fragment memory	Out-of-memory for large requests despite free memory

The Ethical Dimension of Starvation Starvation raises ethical questions about system design: Fairness vs. Throughput : Fair algorithms may sacrifice overall throughput to ensure no process is left behind. Is this tradeoff acceptable? Explicit vs. Implicit Priorities : If high-value customers get better service, is that acceptable starvation? Where is the line? Long-term vs. Short-term : A process that waited long may deserve priority (aging), but that affects currently-running processes. Operating systems and concurrent systems generally aim for bounded waiting as a minimum guarantee—even low-priority processes will eventually complete, even if they must wait longer.

The Hidden Danger of Starvation

Starvation often goes unnoticed until it becomes severe. A process waiting slightly longer than usual doesn't trigger alarms. By the time starvation is detected (timeouts, angry users, failed SLAs), it may have been happening for a long time. Design for bounded waiting from the start—it's much harder to retrofit.

Techniques for Ensuring Bounded Waiting

Achieving bounded waiting requires deliberate design. Several techniques are commonly employed: Technique 1: FIFO Queuing The most straightforward approach: maintain a queue of waiting processes. When the critical section becomes free, the process at the head of the queue enters.

fifo_queue_lock.c
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
// FIFO Queue Lock (conceptual implementation)
// Guarantees bounded waiting with bound B = n-1
 
typedef struct {
    Queue waiting_queue;  // FIFO queue of waiting process IDs
    bool lock_held;
    int current_holder;
} FIFOLock;
 
void acquire(FIFOLock *lock, int my_id) {
    // Atomically add ourselves to queue
    bool was_empty = atomic_enqueue(&lock->waiting_queue, my_id);
    
    if (!was_empty || lock->lock_held) {
        // Wait until we're at the head and lock is free
        while (queue_head(&lock->waiting_queue) != my_id || lock->lock_held) {
            // Busy wait or block
        }
    }
    
    // We're at head and lock is free
    lock->lock_held = true;
    lock->current_holder = my_id;
}
 
void release(FIFOLock *lock, int my_id) {
    // Remove ourselves from queue head
    atomic_dequeue(&lock->waiting_queue);
    lock->lock_held = false;
    
    // Next process (if any) will notice and proceed
}
 
/*
 * BOUNDED WAITING GUARANTEE:
 * 
 * When a process requests entry (enqueues):
 * - At most n-1 other processes can be ahead in the queue
 * - Each process ahead enters exactly once before leaving the queue
 * - Therefore, at most n-1 entries occur before the requesting 
 *   process reaches the head
 * - Bound B = n-1 ✓
 */

Technique 2: Ticket Locks (Bakery Algorithm Style) Processes take numbered tickets on arrival. The process with the lowest ticket number (among waiting processes) enters next.

ticket_lock.c
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
// Ticket Lock implementation
// Guarantees strict FIFO ordering, bounded waiting B = n-1
 
typedef struct {
    volatile int next_ticket;   // Next ticket to dispense
    volatile int now_serving;   // Ticket currently being served
} TicketLock;
 
void acquire(TicketLock *lock) {
    // Atomically get our ticket number
    int my_ticket = atomic_fetch_add(&lock->next_ticket, 1);
    
    // Wait until our ticket is being served
    while (lock->now_serving != my_ticket) {
        // Spin (or yield)
        // Could add: pause instruction, exponential backoff
    }
    
    // It's our turn!
}
 
void release(TicketLock *lock) {
    // Serve the next ticket
    lock->now_serving++;
}
 
/*
 * HOW IT WORKS:
 * 
 * 1. next_ticket starts at 0, now_serving starts at 0
 * 2. First process gets ticket 0, immediately enters (0 == 0)
 * 3. Second process gets ticket 1, waits for now_serving == 1
 * 4. When first releases, now_serving becomes 1, second enters
 * 
 * BOUNDED WAITING:
 * - Tickets are strictly ordered
 * - No process can be bypassed (tickets always increase)
 * - Each process ahead takes exactly one turn
 * - Bound B = number of tickets taken before mine ≤ n-1
 */

Technique 3: Aging Aging dynamically increases the priority of waiting processes over time. Eventually, even the lowest-priority process becomes the highest priority.

Aging Mechanism

•Initial priority: Process starts with its assigned priority
•Wait time accumulation: Each time unit of waiting increases effective priority
•Priority boost: After waiting long enough, even low-priority processes become highest priority
•Priority decay: Entering the critical section resets priority to the base level
•Guarantee: Eventually, any waiting process will have the highest priority

Technique 4: Round-Robin Selection Processes are served in a fixed circular order. Process 0, then 1, then 2, ..., then n-1, then back to 0. If a process isn't waiting when its turn comes, skip to the next waiting process.

Choosing a Technique

FIFO queuing and ticket locks provide strict fairness but may have higher overhead. Aging is more flexible but the bound depends on the aging rate. Round-robin is simple but may waste turns on non-waiting processes. Choose based on your system's fairness requirements and performance constraints.

Bounded Waiting in Classic Algorithms

Let's analyze bounded waiting in some classical synchronization algorithms. Peterson's Algorithm: Bounded Waiting ✓ Peterson's algorithm (for two processes) provides bounded waiting with bound B = 1: When P₀ requests entry, P₁ can enter at most once before P₀ The turn variable ensures the waiting process gets priority after the other completes Proof sketch: When P₀ sets flag[0] = true and turn = 1, if P₁ enters (because it already set flag[1] = true and turn = 0), P₁ will then set turn = 0 when it requests next. At that point, P₀'s waiting condition flag[1] && turn == 1 becomes false (since turn is now 0), so P₀ enters. Thus P₁ can bypass P₀ at most once. Simple Test-and-Set: Bounded Waiting ✗ The simple test-and-set spinlock does NOT provide bounded waiting:

tas_no_bounded_waiting.c
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
// Simple test-and-set: NO bounded waiting
 
void acquire() {
    while (test_and_set(&lock)) {
        // Keep trying
    }
}
 
void release() {
    lock = false;
}
 
/*
 * WHY NO BOUNDED WAITING:
 * 
 * Consider 3 processes: P₀, P₁, P₂
 * 
 * Initial: lock = false
 * 1. P₀ acquires lock
 * 2. P₁ and P₂ start spinning
 * 3. P₀ releases (lock = false)
 * 4. P₁ and P₂ both race for lock
 * 5. P₂ wins (happens to execute TAS first)
 * 6. P₂ executes, releases
 * 7. P₀ comes back wanting lock, races with P₁
 * 8. P₀ wins (again, timing luck)
 * 9. This pattern can repeat indefinitely with P₁ never winning
 * 
 * There is no mechanism to prevent a process from being 
 * repeatedly bypassed by "luckier" processes.
 */

Lamport's Bakery Algorithm: Bounded Waiting ✓ The bakery algorithm provides bounded waiting for n processes with bound B = n-1: Each process takes a ticket number higher than all current tickets Entry is granted to the process with the lowest ticket Ties are broken by process ID (lower ID wins) Bound: Since tickets are strictly ordered and no process can get a lower ticket after you, at most n-1 processes (those who took tickets before you) can enter before you.

Bounded Waiting in Classic Algorithms
Algorithm	Bounded Waiting?	Bound B	Notes
Simple TAS spinlock	✗ No	Unbounded	No fairness mechanism
Peterson's (2 process)	✓ Yes	1	Turn variable ensures fairness
Dekker's (2 process)	✓ Yes	1	Similar to Peterson's
Lamport's Bakery (n process)	✓ Yes	n-1	Ticket-based ordering
Ticket Lock	✓ Yes	n-1	FIFO via atomic tickets
MCS Lock	✓ Yes	n-1	Queue-based with local spinning
CLH Lock	✓ Yes	n-1	Queue-based, space efficient

Fair Locks Are More Complex

Notice that algorithms providing bounded waiting require more sophisticated mechanisms than simple test-and-set: turn variables, ticket counters, or explicit queues. This is not coincidence—fairness requires ordering, and ordering requires state that tracks request sequence.

Proving Bounded Waiting

Proving bounded waiting requires showing that a finite bound exists on bypassing. Here's a systematic approach. Proof Strategy Define the bypass count : For each process request, define what counts as a bypass. Identify the ordering mechanism : What determines who enters next? Show the ordering prevents unbounded bypass : Prove that the mechanism ensures the bound. Derive the bound value : Calculate the maximum possible bypasses.

bounded_waiting_proof.txt
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
// Proving Bounded Waiting for Peterson's Algorithm (2 processes)
 
// Algorithm (process i, j = 1-i):
// Entry: flag[i] = true; turn = j; while (flag[j] && turn == j) {}
// Exit:  flag[i] = false
 
// PROOF:
 
// Claim: After Pᵢ enters the entry section, Pⱼ can enter 
//        the critical section at most once before Pᵢ enters.
 
// Proof:
// Let time t₀ be when Pᵢ sets flag[i] = true.
// 
// Case 1: flag[j] = false at some point after t₀
//   Pᵢ's while condition is false, so Pᵢ enters.
//   Pⱼ entered 0 times after t₀. Bound satisfied.
//
// Case 2: flag[j] = true continuously after t₀
//   This means Pⱼ is in its entry, CS, or exit section.
//   
//   Subcase 2a: Pⱼ is in its exit section
//     Pⱼ will set flag[j] = false, reducing to Case 1.
//     Pⱼ entered 0 or 1 times. Bound satisfied.
//   
//   Subcase 2b: Pⱼ is in CS
//     Pⱼ will exit, set flag[j] = false, reducing to Case 1.
//     Pⱼ entered 1 time. Bound satisfied.
//   
//   Subcase 2c: Pⱼ is in entry section
//     Pⱼ must have set turn = i (giving priority to Pᵢ).
//     If Pⱼ set turn = i BEFORE Pᵢ set turn = j:
//       turn = j (Pᵢ wrote last), Pᵢ passes while, enters.
//       Pⱼ entered 0 times. Bound satisfied.
//     If Pⱼ set turn = i AFTER Pᵢ set turn = j:
//       turn = i, Pⱼ passes while, enters first.
//       But when Pⱼ next requests, it sets turn = i again.
//       Now Pᵢ sees turn = i, passes while, enters.
//       Pⱼ entered 1 time. Bound satisfied.
//
// In all cases, Pⱼ enters at most once before Pᵢ.
// Therefore, bounded waiting holds with B = 1. QED

Counter-Example Construction To prove bounded waiting does NOT hold, construct a specific execution trace showing unbounded bypass:

unbounded_counterexample.txt
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
// Proving Simple TAS Lacks Bounded Waiting (by counterexample)
 
// Algorithm:
// Entry: while (test_and_set(&lock)) {}
// Exit:  lock = false
 
// COUNTEREXAMPLE CONSTRUCTION:
 
// Setup: 2 processes P₀ and P₁
 
// Trace:
// 1. P₀ acquires lock (TAS returns false)
// 2. P₁ enters busy loop, wanting lock
// 3. P₀ completes CS, sets lock = false
// 4. P₀ immediately wants lock again, executes TAS
// 5. P₀ wins race (executes TAS before P₁'s next check)
// 6. P₀ now in CS again; P₁ still waiting
// 7. Repeat from step 3...
 
// This trace can continue indefinitely with P₀ always winning.
// P₁ is bypassed unboundedly.
 
// WHY THIS IS POSSIBLE:
// - No ordering mechanism exists
// - Whichever process executes TAS first (when lock is false) wins
// - On many CPUs, P₀ has cache-line advantage (recently accessed lock)
// - P₀ can systematically win every race
 
// CONCLUSION: No bound B exists. Bounded waiting is violated.
 
// Note: This is a valid execution trace, not just theoretical.
// It occurs frequently on real systems under high contention.

Proof Tips

To PROVE bounded waiting, show that every possible execution path leads to entry within the bound. To DISPROVE it, find just ONE execution path that bypasses infinitely. The asymmetry makes disproving easier—one counterexample suffices, while proving requires exhaustive analysis.

Bounded Waiting: Relationships and Tradeoffs

Bounded waiting interacts with other synchronization properties in important ways. Understanding these relationships guides design decisions. The Three Requirements as a Hierarchy

requirement_hierarchy.txt
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
Requirement Hierarchy (Weakest to Strongest):
 
1. MUTUAL EXCLUSION (Safety)
   ├── Requirement: At most one process in CS at a time
   ├── Failure: Data corruption
   └── A solution MUST have this
 
2. PROGRESS (Basic Liveness)
   ├── Requirement: If CS empty and someone wants in, someone enters
   ├── Failure: System-wide deadlock
   ├── Implies: Mutual exclusion alone is not sufficient
   └── A solution MUST have this
 
3. BOUNDED WAITING (Fairness/Strong Liveness)
   ├── Requirement: Each waiting process enters within finite bypasses
   ├── Failure: Individual starvation
   ├── Implies: Progress alone is not sufficient
   └── A correct solution SHOULD have this
 
Implication chain:
Bounded Waiting → Progress → Mutual Exclusion
 
(If bounded waiting holds, progress must hold because 
 every process including SOME process enters.
 If no process ever enters, every process violates bounded waiting.)

The Fairness-Throughput Tradeoff Enforcing bounded waiting often comes at a cost to throughput:

With Bounded Waiting (Fair)

•Every process eventually enters
•Latency variance is bounded
•May reduce overall throughput
•Extra overhead for ordering
•Predictable worst-case behavior

Without Bounded Waiting (Unfair)

•Some processes may starve
•Latency variance is unbounded
•Higher peak throughput possible
•Lower overhead (simpler algorithm)
•Unpredictable worst case

Bounded Waiting and Lock Contention The importance of bounded waiting depends on contention level: Low contention : Bounded waiting matters less. If contention is rare, unfair locks rarely starve anyone in practice. High contention : Bounded waiting is critical. Under heavy load, unfair locks can cause severe starvation of some threads while others monopolize access. Variable contention : The hardest case. Must design for worst-case (high contention) while not paying excessive overhead during normal operation (low contention). Adaptive Strategies Modern lock implementations often use adaptive strategies: Spin then block : Spin briefly (cheap, fast), then block if unsuccessful (fair, saves CPU) Switch to fair mode under contention : Use fast unfair lock normally, switch to fair queue when contention detected Combine with timeouts : Even if starvation is theoretically possible, timeouts provide a fallback

Practical Wisdom

In practice, most systems prefer locks with bounded waiting, accepting some throughput cost for predictability. Starvation causes unpredictable latency spikes that are difficult to diagnose and may violate SLAs. The overhead of fair locks is usually acceptable, especially with modern implementations like MCS or CLH locks.

Bounded Waiting in Modern Systems

Modern operating systems and runtime systems implement bounded waiting through various mechanisms. OS Mutex Implementations POSIX mutexes (pthread_mutex) typically provide bounded waiting through kernel-maintained wait queues:

os_mutex_queue.c
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
// Simplified view of how OS mutexes provide bounded waiting
 
struct kernel_mutex {
    atomic_t state;        // 0 = free, 1 = held
    spinlock_t wait_lock;  // Protects the wait queue
    struct list_head wait_queue;  // FIFO queue of waiting threads
};
 
void kernel_mutex_lock(struct kernel_mutex *mtx) {
    // Fast path: try to acquire unlocked mutex
    if (atomic_cmpxchg(&mtx->state, 0, 1) == 0) {
        return;  // Got it!
    }
    
    // Slow path: add to wait queue
    spin_lock(&mtx->wait_lock);
    list_add_tail(&current->wait_entry, &mtx->wait_queue);
    spin_unlock(&mtx->wait_lock);
    
    // Block until we're at the head and lock is released
    while (true) {
        schedule();  // Yield CPU
        if (/* we're at head and lock is free */) {
            break;
        }
    }
}
 
void kernel_mutex_unlock(struct kernel_mutex *mtx) {
    spin_lock(&mtx->wait_lock);
    if (!list_empty(&mtx->wait_queue)) {
        // Wake the process at the head of queue
        struct task_struct *next = list_first_entry(&mtx->wait_queue);
        wake_up_process(next);
    }
    spin_unlock(&mtx->wait_lock);
    atomic_set(&mtx->state, 0);
}
 
// FIFO queue ensures bounded waiting: each process in queue
// enters exactly once in order

Language-Level Fairness Guarantees Different languages provide different fairness guarantees:

Fairness in Language Synchronization Primitives
Language/Primitive	Fairness Guarantee	Notes
Java synchronized	Not specified	Depends on JVM implementation; typically fair in modern JVMs
Java ReentrantLock(true)	FIFO fairness	Explicit fair mode; bounded waiting guaranteed
C++ std::mutex	Not specified	Implementation-defined; usually fair on modern OS
Python threading.Lock	FIFO (CPython)	GIL-based; effectively fair
Go sync.Mutex	Mixed	Combines spinning and FIFO for efficiency
Rust std::sync::Mutex	Not specified	Uses OS primitives; typically fair

Hardware Queue Locks Advanced lock implementations like MCS and CLH locks provide bounded waiting with good scalability: MCS Lock (Mellor-Crummey and Scott): Each thread spins on its own local variable (cache-friendly) Threads form a linked list queue Strict FIFO order, bounded waiting guaranteed CLH Lock (Craig, Landin, Hagersten): Similar to MCS but different queue structure Each thread spins on predecessor's variable Strict FIFO order, bounded waiting guaranteed These locks achieve both bounded waiting AND high performance by avoiding contention on shared cache lines.

Choosing Locks for Fairness

When bounded waiting is essential: Use explicitly fair locks (Java's ReentrantLock(true), MCS, CLH). When performance is critical and starvation is acceptable: Use simpler locks (TAS, TTAS). When in doubt: Use OS-provided primitives—they're typically fair and well-optimized.

Operating SystemsRequirements for Solutions

Requirements for Solutions to the Critical Section Problem

LevelIntermediate

Duration90 mins

TopicRequirements for Solutions

3 / 5

Bounded Waiting: The Fairness Guarantee

Beyond Progress: Ensuring Every Process Gets Its Turn

We have established that mutual exclusion ensures safety (no concurrent critical section access) and progress ensures liveness (the system moves forward). But consider this scenario: Two processes, P₀ and P₁, contend for a critical section. The algorithm satisfies mutual exclusion and progress. P₀ enters, exits, and immediately re-enters. P₁ is waiting. P₀ exits, immediately re-enters again. P₁ continues waiting. This pattern repeats indefinitely. Is this acceptable? The system is making progress—P₀ is executing its critical section repeatedly. Mutual exclusion holds—only one process is ever inside. But P₁ is starving —it may wait forever while P₀ monopolizes the resource. The third fundamental requirement, Bounded Waiting, addresses exactly this unfairness. It guarantees that no process can be bypassed indefinitely—that every waiting process will eventually get its turn. This page provides a comprehensive treatment of bounded waiting: its formal definition, its importance, how to design solutions that satisfy it, and how to verify the property analytically.

What You Will Learn

By the end of this page, you will understand the formal definition of bounded waiting, distinguish it clearly from progress, identify starvation in synchronization algorithms, design fair synchronization solutions, and verify bounded waiting through analysis.

Defining Bounded Waiting

Why 'Bounded' Rather Than 'Zero'?

We allow OTHER processes to enter some finite number of times rather than requiring immediate entry. This is because: (1) already-running critical sections must complete, (2) processes already ahead in any queue should go first, and (3) requiring immediate entry could itself cause problems. The key is that the wait is BOUNDED, not minimal.

bounded_waiting_illustration.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Illustration: Bounded Waiting with Bound B = n-1 (for n processes)
 
// Timeline showing process requests and critical section entries:
 
Time:  ─────────────────────────────────────────────────────────────►
 
P₀:    ────request───────────────────────────────────enter CS─────
                     ↑                                   ↓
                     └───── waiting period ──────────────┘
                     
P₁:    ───────────enter CS────────────────────────────────────────
                         ↑
                         └─ counts toward P₀'s bound (1)
                         
P₂:    ─────────────────────enter CS──────────────────────────────
                                   ↑
                                   └─ counts toward P₀'s bound (2)
 
// If P₁ and P₂ EACH enter only once before P₀, and there are 3 processes:
// Bound = n - 1 = 2, and P₀ waited through 2 entries ✓ Bounded waiting satisfied
 
// VIOLATION would be:
// P₁ enters, P₂ enters, P₁ enters again, P₂ enters again... 
// while P₀ never gets in. That's unbounded!

Starvation and Its Consequences

Starvation is the condition where bounded waiting fails—a process waits indefinitely while others repeatedly access the critical section. Unlike deadlock (no progress) or livelock (active but no progress), starvation involves the system making progress while leaving specific processes behind. Characteristics of Starvation Starvation is particularly insidious because: The system appears healthy — Overall throughput is good; most processes are running fine Few processes are affected — Only some processes suffer; others don't notice Detection is difficult — A starving process looks like a slow process Reproduction is hard — Starvation often depends on specific timing conditions

Causes of Starvation

•Priority-based selection: If processes with higher priority are always chosen, low-priority processes may never run
•Race-based selection: If entry is determined by 'first to grab the lock', unlucky processes may always lose the race
•Positional bias: Algorithms that favor certain process IDs (like lower-numbered first) can systematically starve higher-numbered processes
•Cache-local bias: On NUMA systems, processes on the 'wrong' node may consistently lose to cache-local processes
•Temporary high contention: Bursts of activity can cause some processes to be repeatedly bypassed

Real-World Starvation Scenarios

Starvation in Real Systems
System	Starved Entity	Cause	Consequence
Web server	Requests from slow clients	Fast clients monopolize connection pool	Slow clients timeout repeatedly
Database	Low-priority queries	Continuous stream of high-priority queries	Reports never complete
File system	Large file operations	Many small file operations preempt	Backup jobs never finish
Network switch	Low-QoS traffic	High-QoS traffic saturation	Best-effort packets dropped
Memory allocator	Large allocations	Frequent small allocations fragment memory	Out-of-memory for large requests despite free memory

The Ethical Dimension of Starvation Starvation raises ethical questions about system design: Fairness vs. Throughput : Fair algorithms may sacrifice overall throughput to ensure no process is left behind. Is this tradeoff acceptable? Explicit vs. Implicit Priorities : If high-value customers get better service, is that acceptable starvation? Where is the line? Long-term vs. Short-term : A process that waited long may deserve priority (aging), but that affects currently-running processes. Operating systems and concurrent systems generally aim for bounded waiting as a minimum guarantee—even low-priority processes will eventually complete, even if they must wait longer.

The Hidden Danger of Starvation

Starvation often goes unnoticed until it becomes severe. A process waiting slightly longer than usual doesn't trigger alarms. By the time starvation is detected (timeouts, angry users, failed SLAs), it may have been happening for a long time. Design for bounded waiting from the start—it's much harder to retrofit.

Techniques for Ensuring Bounded Waiting

Achieving bounded waiting requires deliberate design. Several techniques are commonly employed: Technique 1: FIFO Queuing The most straightforward approach: maintain a queue of waiting processes. When the critical section becomes free, the process at the head of the queue enters.

fifo_queue_lock.c
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
// FIFO Queue Lock (conceptual implementation)
// Guarantees bounded waiting with bound B = n-1
 
typedef struct {
    Queue waiting_queue;  // FIFO queue of waiting process IDs
    bool lock_held;
    int current_holder;
} FIFOLock;
 
void acquire(FIFOLock *lock, int my_id) {
    // Atomically add ourselves to queue
    bool was_empty = atomic_enqueue(&lock->waiting_queue, my_id);
    
    if (!was_empty || lock->lock_held) {
        // Wait until we're at the head and lock is free
        while (queue_head(&lock->waiting_queue) != my_id || lock->lock_held) {
            // Busy wait or block
        }
    }
    
    // We're at head and lock is free
    lock->lock_held = true;
    lock->current_holder = my_id;
}
 
void release(FIFOLock *lock, int my_id) {
    // Remove ourselves from queue head
    atomic_dequeue(&lock->waiting_queue);
    lock->lock_held = false;
    
    // Next process (if any) will notice and proceed
}
 
/*
 * BOUNDED WAITING GUARANTEE:
 * 
 * When a process requests entry (enqueues):
 * - At most n-1 other processes can be ahead in the queue
 * - Each process ahead enters exactly once before leaving the queue
 * - Therefore, at most n-1 entries occur before the requesting 
 *   process reaches the head
 * - Bound B = n-1 ✓
 */

Technique 2: Ticket Locks (Bakery Algorithm Style) Processes take numbered tickets on arrival. The process with the lowest ticket number (among waiting processes) enters next.

ticket_lock.c
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
// Ticket Lock implementation
// Guarantees strict FIFO ordering, bounded waiting B = n-1
 
typedef struct {
    volatile int next_ticket;   // Next ticket to dispense
    volatile int now_serving;   // Ticket currently being served
} TicketLock;
 
void acquire(TicketLock *lock) {
    // Atomically get our ticket number
    int my_ticket = atomic_fetch_add(&lock->next_ticket, 1);
    
    // Wait until our ticket is being served
    while (lock->now_serving != my_ticket) {
        // Spin (or yield)
        // Could add: pause instruction, exponential backoff
    }
    
    // It's our turn!
}
 
void release(TicketLock *lock) {
    // Serve the next ticket
    lock->now_serving++;
}
 
/*
 * HOW IT WORKS:
 * 
 * 1. next_ticket starts at 0, now_serving starts at 0
 * 2. First process gets ticket 0, immediately enters (0 == 0)
 * 3. Second process gets ticket 1, waits for now_serving == 1
 * 4. When first releases, now_serving becomes 1, second enters
 * 
 * BOUNDED WAITING:
 * - Tickets are strictly ordered
 * - No process can be bypassed (tickets always increase)
 * - Each process ahead takes exactly one turn
 * - Bound B = number of tickets taken before mine ≤ n-1
 */

Technique 3: Aging Aging dynamically increases the priority of waiting processes over time. Eventually, even the lowest-priority process becomes the highest priority.

Aging Mechanism

•Initial priority: Process starts with its assigned priority
•Wait time accumulation: Each time unit of waiting increases effective priority
•Priority boost: After waiting long enough, even low-priority processes become highest priority
•Priority decay: Entering the critical section resets priority to the base level
•Guarantee: Eventually, any waiting process will have the highest priority

Technique 4: Round-Robin Selection Processes are served in a fixed circular order. Process 0, then 1, then 2, ..., then n-1, then back to 0. If a process isn't waiting when its turn comes, skip to the next waiting process.

Choosing a Technique

FIFO queuing and ticket locks provide strict fairness but may have higher overhead. Aging is more flexible but the bound depends on the aging rate. Round-robin is simple but may waste turns on non-waiting processes. Choose based on your system's fairness requirements and performance constraints.

Bounded Waiting in Classic Algorithms

Let's analyze bounded waiting in some classical synchronization algorithms. Peterson's Algorithm: Bounded Waiting ✓ Peterson's algorithm (for two processes) provides bounded waiting with bound B = 1: When P₀ requests entry, P₁ can enter at most once before P₀ The turn variable ensures the waiting process gets priority after the other completes Proof sketch: When P₀ sets flag[0] = true and turn = 1, if P₁ enters (because it already set flag[1] = true and turn = 0), P₁ will then set turn = 0 when it requests next. At that point, P₀'s waiting condition flag[1] && turn == 1 becomes false (since turn is now 0), so P₀ enters. Thus P₁ can bypass P₀ at most once. Simple Test-and-Set: Bounded Waiting ✗ The simple test-and-set spinlock does NOT provide bounded waiting:

tas_no_bounded_waiting.c
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
// Simple test-and-set: NO bounded waiting
 
void acquire() {
    while (test_and_set(&lock)) {
        // Keep trying
    }
}
 
void release() {
    lock = false;
}
 
/*
 * WHY NO BOUNDED WAITING:
 * 
 * Consider 3 processes: P₀, P₁, P₂
 * 
 * Initial: lock = false
 * 1. P₀ acquires lock
 * 2. P₁ and P₂ start spinning
 * 3. P₀ releases (lock = false)
 * 4. P₁ and P₂ both race for lock
 * 5. P₂ wins (happens to execute TAS first)
 * 6. P₂ executes, releases
 * 7. P₀ comes back wanting lock, races with P₁
 * 8. P₀ wins (again, timing luck)
 * 9. This pattern can repeat indefinitely with P₁ never winning
 * 
 * There is no mechanism to prevent a process from being 
 * repeatedly bypassed by "luckier" processes.
 */

Lamport's Bakery Algorithm: Bounded Waiting ✓ The bakery algorithm provides bounded waiting for n processes with bound B = n-1: Each process takes a ticket number higher than all current tickets Entry is granted to the process with the lowest ticket Ties are broken by process ID (lower ID wins) Bound: Since tickets are strictly ordered and no process can get a lower ticket after you, at most n-1 processes (those who took tickets before you) can enter before you.

Bounded Waiting in Classic Algorithms
Algorithm	Bounded Waiting?	Bound B	Notes
Simple TAS spinlock	✗ No	Unbounded	No fairness mechanism
Peterson's (2 process)	✓ Yes	1	Turn variable ensures fairness
Dekker's (2 process)	✓ Yes	1	Similar to Peterson's
Lamport's Bakery (n process)	✓ Yes	n-1	Ticket-based ordering
Ticket Lock	✓ Yes	n-1	FIFO via atomic tickets
MCS Lock	✓ Yes	n-1	Queue-based with local spinning
CLH Lock	✓ Yes	n-1	Queue-based, space efficient

Fair Locks Are More Complex

Notice that algorithms providing bounded waiting require more sophisticated mechanisms than simple test-and-set: turn variables, ticket counters, or explicit queues. This is not coincidence—fairness requires ordering, and ordering requires state that tracks request sequence.

Proving Bounded Waiting

Proving bounded waiting requires showing that a finite bound exists on bypassing. Here's a systematic approach. Proof Strategy Define the bypass count : For each process request, define what counts as a bypass. Identify the ordering mechanism : What determines who enters next? Show the ordering prevents unbounded bypass : Prove that the mechanism ensures the bound. Derive the bound value : Calculate the maximum possible bypasses.

bounded_waiting_proof.txt
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
// Proving Bounded Waiting for Peterson's Algorithm (2 processes)
 
// Algorithm (process i, j = 1-i):
// Entry: flag[i] = true; turn = j; while (flag[j] && turn == j) {}
// Exit:  flag[i] = false
 
// PROOF:
 
// Claim: After Pᵢ enters the entry section, Pⱼ can enter 
//        the critical section at most once before Pᵢ enters.
 
// Proof:
// Let time t₀ be when Pᵢ sets flag[i] = true.
// 
// Case 1: flag[j] = false at some point after t₀
//   Pᵢ's while condition is false, so Pᵢ enters.
//   Pⱼ entered 0 times after t₀. Bound satisfied.
//
// Case 2: flag[j] = true continuously after t₀
//   This means Pⱼ is in its entry, CS, or exit section.
//   
//   Subcase 2a: Pⱼ is in its exit section
//     Pⱼ will set flag[j] = false, reducing to Case 1.
//     Pⱼ entered 0 or 1 times. Bound satisfied.
//   
//   Subcase 2b: Pⱼ is in CS
//     Pⱼ will exit, set flag[j] = false, reducing to Case 1.
//     Pⱼ entered 1 time. Bound satisfied.
//   
//   Subcase 2c: Pⱼ is in entry section
//     Pⱼ must have set turn = i (giving priority to Pᵢ).
//     If Pⱼ set turn = i BEFORE Pᵢ set turn = j:
//       turn = j (Pᵢ wrote last), Pᵢ passes while, enters.
//       Pⱼ entered 0 times. Bound satisfied.
//     If Pⱼ set turn = i AFTER Pᵢ set turn = j:
//       turn = i, Pⱼ passes while, enters first.
//       But when Pⱼ next requests, it sets turn = i again.
//       Now Pᵢ sees turn = i, passes while, enters.
//       Pⱼ entered 1 time. Bound satisfied.
//
// In all cases, Pⱼ enters at most once before Pᵢ.
// Therefore, bounded waiting holds with B = 1. QED

Counter-Example Construction To prove bounded waiting does NOT hold, construct a specific execution trace showing unbounded bypass:

unbounded_counterexample.txt
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
// Proving Simple TAS Lacks Bounded Waiting (by counterexample)
 
// Algorithm:
// Entry: while (test_and_set(&lock)) {}
// Exit:  lock = false
 
// COUNTEREXAMPLE CONSTRUCTION:
 
// Setup: 2 processes P₀ and P₁
 
// Trace:
// 1. P₀ acquires lock (TAS returns false)
// 2. P₁ enters busy loop, wanting lock
// 3. P₀ completes CS, sets lock = false
// 4. P₀ immediately wants lock again, executes TAS
// 5. P₀ wins race (executes TAS before P₁'s next check)
// 6. P₀ now in CS again; P₁ still waiting
// 7. Repeat from step 3...
 
// This trace can continue indefinitely with P₀ always winning.
// P₁ is bypassed unboundedly.
 
// WHY THIS IS POSSIBLE:
// - No ordering mechanism exists
// - Whichever process executes TAS first (when lock is false) wins
// - On many CPUs, P₀ has cache-line advantage (recently accessed lock)
// - P₀ can systematically win every race
 
// CONCLUSION: No bound B exists. Bounded waiting is violated.
 
// Note: This is a valid execution trace, not just theoretical.
// It occurs frequently on real systems under high contention.

Proof Tips

To PROVE bounded waiting, show that every possible execution path leads to entry within the bound. To DISPROVE it, find just ONE execution path that bypasses infinitely. The asymmetry makes disproving easier—one counterexample suffices, while proving requires exhaustive analysis.

Bounded Waiting: Relationships and Tradeoffs

Bounded waiting interacts with other synchronization properties in important ways. Understanding these relationships guides design decisions. The Three Requirements as a Hierarchy

requirement_hierarchy.txt
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
Requirement Hierarchy (Weakest to Strongest):
 
1. MUTUAL EXCLUSION (Safety)
   ├── Requirement: At most one process in CS at a time
   ├── Failure: Data corruption
   └── A solution MUST have this
 
2. PROGRESS (Basic Liveness)
   ├── Requirement: If CS empty and someone wants in, someone enters
   ├── Failure: System-wide deadlock
   ├── Implies: Mutual exclusion alone is not sufficient
   └── A solution MUST have this
 
3. BOUNDED WAITING (Fairness/Strong Liveness)
   ├── Requirement: Each waiting process enters within finite bypasses
   ├── Failure: Individual starvation
   ├── Implies: Progress alone is not sufficient
   └── A correct solution SHOULD have this
 
Implication chain:
Bounded Waiting → Progress → Mutual Exclusion
 
(If bounded waiting holds, progress must hold because 
 every process including SOME process enters.
 If no process ever enters, every process violates bounded waiting.)

The Fairness-Throughput Tradeoff Enforcing bounded waiting often comes at a cost to throughput:

With Bounded Waiting (Fair)

•Every process eventually enters
•Latency variance is bounded
•May reduce overall throughput
•Extra overhead for ordering
•Predictable worst-case behavior

Without Bounded Waiting (Unfair)

•Some processes may starve
•Latency variance is unbounded
•Higher peak throughput possible
•Lower overhead (simpler algorithm)
•Unpredictable worst case

Bounded Waiting and Lock Contention The importance of bounded waiting depends on contention level: Low contention : Bounded waiting matters less. If contention is rare, unfair locks rarely starve anyone in practice. High contention : Bounded waiting is critical. Under heavy load, unfair locks can cause severe starvation of some threads while others monopolize access. Variable contention : The hardest case. Must design for worst-case (high contention) while not paying excessive overhead during normal operation (low contention). Adaptive Strategies Modern lock implementations often use adaptive strategies: Spin then block : Spin briefly (cheap, fast), then block if unsuccessful (fair, saves CPU) Switch to fair mode under contention : Use fast unfair lock normally, switch to fair queue when contention detected Combine with timeouts : Even if starvation is theoretically possible, timeouts provide a fallback

Practical Wisdom

In practice, most systems prefer locks with bounded waiting, accepting some throughput cost for predictability. Starvation causes unpredictable latency spikes that are difficult to diagnose and may violate SLAs. The overhead of fair locks is usually acceptable, especially with modern implementations like MCS or CLH locks.

Bounded Waiting in Modern Systems

Modern operating systems and runtime systems implement bounded waiting through various mechanisms. OS Mutex Implementations POSIX mutexes (pthread_mutex) typically provide bounded waiting through kernel-maintained wait queues:

os_mutex_queue.c
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
// Simplified view of how OS mutexes provide bounded waiting
 
struct kernel_mutex {
    atomic_t state;        // 0 = free, 1 = held
    spinlock_t wait_lock;  // Protects the wait queue
    struct list_head wait_queue;  // FIFO queue of waiting threads
};
 
void kernel_mutex_lock(struct kernel_mutex *mtx) {
    // Fast path: try to acquire unlocked mutex
    if (atomic_cmpxchg(&mtx->state, 0, 1) == 0) {
        return;  // Got it!
    }
    
    // Slow path: add to wait queue
    spin_lock(&mtx->wait_lock);
    list_add_tail(&current->wait_entry, &mtx->wait_queue);
    spin_unlock(&mtx->wait_lock);
    
    // Block until we're at the head and lock is released
    while (true) {
        schedule();  // Yield CPU
        if (/* we're at head and lock is free */) {
            break;
        }
    }
}
 
void kernel_mutex_unlock(struct kernel_mutex *mtx) {
    spin_lock(&mtx->wait_lock);
    if (!list_empty(&mtx->wait_queue)) {
        // Wake the process at the head of queue
        struct task_struct *next = list_first_entry(&mtx->wait_queue);
        wake_up_process(next);
    }
    spin_unlock(&mtx->wait_lock);
    atomic_set(&mtx->state, 0);
}
 
// FIFO queue ensures bounded waiting: each process in queue
// enters exactly once in order

Language-Level Fairness Guarantees Different languages provide different fairness guarantees:

Fairness in Language Synchronization Primitives
Language/Primitive	Fairness Guarantee	Notes
Java synchronized	Not specified	Depends on JVM implementation; typically fair in modern JVMs
Java ReentrantLock(true)	FIFO fairness	Explicit fair mode; bounded waiting guaranteed
C++ std::mutex	Not specified	Implementation-defined; usually fair on modern OS
Python threading.Lock	FIFO (CPython)	GIL-based; effectively fair
Go sync.Mutex	Mixed	Combines spinning and FIFO for efficiency
Rust std::sync::Mutex	Not specified	Uses OS primitives; typically fair

Hardware Queue Locks Advanced lock implementations like MCS and CLH locks provide bounded waiting with good scalability: MCS Lock (Mellor-Crummey and Scott): Each thread spins on its own local variable (cache-friendly) Threads form a linked list queue Strict FIFO order, bounded waiting guaranteed CLH Lock (Craig, Landin, Hagersten): Similar to MCS but different queue structure Each thread spins on predecessor's variable Strict FIFO order, bounded waiting guaranteed These locks achieve both bounded waiting AND high performance by avoiding contention on shared cache lines.

Choosing Locks for Fairness

When bounded waiting is essential: Use explicitly fair locks (Java's ReentrantLock(true), MCS, CLH). When performance is critical and starvation is acceptable: Use simpler locks (TAS, TTAS). When in doubt: Use OS-provided primitives—they're typically fair and well-optimized.

Bounded Waiting: The Fairness Guarantee

Beyond Progress: Ensuring Every Process Gets Its Turn

Defining Bounded Waiting

The Formal Definition

The Mathematical Formulation

A Typical Bound: n - 1

Starvation and Its Consequences

Characteristics of Starvation

Real-World Starvation Scenarios

The Ethical Dimension of Starvation

Techniques for Ensuring Bounded Waiting

Technique 1: FIFO Queuing

Technique 2: Ticket Locks (Bakery Algorithm Style)

Technique 3: Aging

Technique 4: Round-Robin Selection

Bounded Waiting in Classic Algorithms

Peterson's Algorithm: Bounded Waiting ✓

Simple Test-and-Set: Bounded Waiting ✗

Lamport's Bakery Algorithm: Bounded Waiting ✓

Proving Bounded Waiting

Proof Strategy

Counter-Example Construction

Bounded Waiting: Relationships and Tradeoffs

The Three Requirements as a Hierarchy

The Fairness-Throughput Tradeoff

Bounded Waiting and Lock Contention

Adaptive Strategies

Bounded Waiting in Modern Systems

OS Mutex Implementations

Language-Level Fairness Guarantees

Hardware Queue Locks

There’s more to understand.

Bounded Waiting: The Fairness Guarantee

Beyond Progress: Ensuring Every Process Gets Its Turn

Defining Bounded Waiting

The Formal Definition

The Mathematical Formulation

A Typical Bound: n - 1

Starvation and Its Consequences

Characteristics of Starvation

Real-World Starvation Scenarios

The Ethical Dimension of Starvation

Techniques for Ensuring Bounded Waiting

Technique 1: FIFO Queuing

Technique 2: Ticket Locks (Bakery Algorithm Style)

Technique 3: Aging

Technique 4: Round-Robin Selection

Bounded Waiting in Classic Algorithms

Peterson's Algorithm: Bounded Waiting ✓

Simple Test-and-Set: Bounded Waiting ✗

Lamport's Bakery Algorithm: Bounded Waiting ✓

Proving Bounded Waiting

Proof Strategy

Counter-Example Construction

Bounded Waiting: Relationships and Tradeoffs

The Three Requirements as a Hierarchy

The Fairness-Throughput Tradeoff

Bounded Waiting and Lock Contention

Adaptive Strategies

Bounded Waiting in Modern Systems

OS Mutex Implementations

Language-Level Fairness Guarantees

Hardware Queue Locks

There’s more to understand.