Requirements For Solutions - Learning Module

Loading content...

0/227

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

Bounded waiting (also called starvation-freedom or finite bypass) ensures that no process waits indefinitely while other processes repeatedly enter their critical sections.

The Formal Definition

Bounded Waiting Requirement:

There exists a bound (limit) on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

Let's unpack this carefully:

"There exists a bound" — A specific, finite number B exists. This bound might depend on the number of processes n but must be finite.

"on the number of times that other processes are allowed to enter" — We count entries by OTHER processes, not iterations or time. Each time another process enters its critical section, that's one count.

"after a process has made a request" — The counting starts when a process signals intent to enter (reaches the entry section).

"before that request is granted" — The counting stops when the requesting process enters its critical section.

The Mathematical Formulation

Let request_time[i] be the time when process i enters its entry section, and grant_time[i] be the time when it enters its critical section. Let entries(j, t₁, t₂) count how many times process j entered its critical section between times t₁ and t₂.

Bounded Waiting Property:

∃B. ∀i. ∀request. Σⱼ≠ᵢ entries(j, request_time[i], grant_time[i]) ≤ B

In words: There exists a bound B such that for every process i and every request by that process, the total number of entries by other processes between the request and grant is at most B.

A Typical Bound: n - 1

Many fair algorithms achieve a bound of n - 1, where n is the number of processes. This means that after a process makes a request, each other process can enter its critical section at most once before the requesting process gets its turn.

This bound corresponds to a FIFO (First-In, First-Out) discipline: processes are served in the order they requested.

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.

Summary: The Bounded Waiting Requirement

We have completed our exploration of bounded waiting—the third and final fundamental requirement for correct synchronization solutions. Let's consolidate our understanding.

Key Takeaways

•Bounded waiting guarantees that no process waits indefinitely while others repeatedly enter the critical section. A finite bound B exists on bypass count.
•Starvation is the failure of bounded waiting—a process waits forever while the system makes progress. It's particularly dangerous because it's hard to detect and reproduce.
•Techniques for ensuring bounded waiting include FIFO queuing, ticket locks, aging, and round-robin selection. All require explicit ordering mechanisms.
•Classic algorithms differ in bounded waiting: Peterson's and Bakery provide it; simple test-and-set does not.
•Proofs of bounded waiting require showing all paths lead to entry within the bound; counterexamples showing unbounded bypass disprove it.
•Tradeoffs exist between fairness and throughput. Fair locks may have higher overhead but provide predictable worst-case behavior.

The Complete Picture

With mutual exclusion, progress, and bounded waiting, we now have a complete framework for evaluating synchronization solutions:

Mutual Exclusion: Safety — No concurrent access Progress: Liveness — System makes forward progress
Bounded Waiting: Fairness — Every process gets its turn

A solution that satisfies all three is correct. Missing any requirement means the solution is flawed, even if it appears to work in testing.

In the next page, we will learn how to evaluate proposed solutions against these requirements systematically, building a toolkit for analyzing any synchronization algorithm.

Page Complete

You now understand bounded waiting—the fairness requirement that prevents starvation. You can identify algorithms that satisfy or violate this requirement, apply techniques to ensure bounded waiting, and reason about the fairness-throughput tradeoff. In the next page, we will develop systematic methods for evaluating synchronization solutions.