Requirements For Solutions - Learning Module

Loading content...

0/227

Progress: Preventing Unnecessary Blocking

Beyond Safety: Enabling Actual Work

Mutual exclusion ensures safety—no two processes can corrupt shared data by accessing it simultaneously. But safety alone is not enough. A system that is perfectly safe yet never allows any work to happen is useless.

This brings us to the second fundamental requirement: Progress. Also known as the liveness property, progress ensures that the system actually moves forward—that processes wanting to enter their critical sections eventually get to do so.

Consider a locked bank vault. Perfect safety! No one can access the money. But if the bank can never open the vault, safety has defeated the entire purpose of having a bank. Progress is the requirement that ensures the vault can actually be opened when legitimate access is needed.

This page explores the progress requirement in depth: its formal definition, its necessity, how violations occur, and how to verify that a solution provides progress.

What You Will Learn

By the end of this page, you will understand the formal definition of the progress requirement, distinguish it from mutual exclusion and bounded waiting, identify common progress violations in synchronization algorithms, and apply progress analysis to evaluate proposed solutions to the critical section problem.

Defining Progress

The progress requirement ensures that the decision of which process enters the critical section next is made in a timely manner by processes that are actually contending for entry.

The Formal Definition

Progress Requirement:

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

Let us unpack this definition carefully:

"If no process is currently executing in its critical section" — This condition establishes when the progress requirement is relevant. If a process IS in its critical section, we don't require immediate entry of others (that would violate mutual exclusion).

"and some processes wish to enter their critical sections" — There must be actual demand. If no process wants entry, progress is trivially satisfied.

"only those processes that are not executing in their remainder sections can participate in the decision" — Processes doing unrelated work (remainder section) should not block the entry of processes that want to enter. The remainder section is explicitly excluded from the decision protocol.

"this decision cannot be postponed indefinitely" — The core requirement: a decision must eventually be made. We cannot have perpetual deadlock or livelock preventing entry.

Progress vs. Mutual Exclusion: Complementary Requirements

Mutual exclusion says: 'At most one process in the critical section at any time.' Progress says: 'If the critical section is empty AND someone wants in, they will eventually get in.' Together, they ensure the system is both safe (no corruption) and live (work happens).

The Mathematical Formulation

We can express progress more formally using temporal logic. Let:

want_cs[i] = process i is in its entry section, wanting to enter its critical section
in_cs[i] = process i is in its critical section
in_remainder[i] = process i is in its remainder section

Progress Property:

(¬∃i. in_cs[i]) ∧ (∃j. want_cs[j]) → ◇(∃k. in_cs[k])

In words: If no process is in the critical section AND at least one process wants to enter, then eventually some process will be in the critical section.

The ◇ (diamond) is the temporal logic operator meaning "eventually"—at some future point in time.

Key Insight: Remainder Section Exclusion

The requirement explicitly excludes processes in their remainder section from affecting the decision. This is crucial:

Processes doing unrelated work shouldn't block progress — If process A is computing locally (remainder section), it shouldn't prevent process B from entering the critical section.
The decision is made only by contenders — Only processes actively trying to enter (in the entry section) participate in deciding who goes next.
Crashed or slow remainder-section processes don't block others — If a process is stuck in an infinite loop in its remainder section, other processes should still be able to use the critical section.

progress_visualization.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
// Visualizing Progress: When is the requirement invoked?
 
Process States:
┌─────────────────┐  ┌────────────────────┐  ┌──────────────────┐
│ REMAINDER       │→ │ ENTRY (wanting)    │→ │ CRITICAL SECTION │
│ Not contending  │  │ Contending         │  │ Executing        │
└─────────────────┘  └────────────────────┘  └──────────────────┘
                              ↑                       │
                              └───────────────────────┘
                                    (via Exit Section)
 
Progress requirement applies when:
  • Critical section is EMPTY (no process currently inside)
  • At least one process is in ENTRY state (wants to enter)
  
What progress guarantees:
  • Eventually, one of the ENTRY-state processes will enter
  • Processes in REMAINDER state have no say in this decision
  • The decision process terminates in finite time
 
Progress is VIOLATED when:
  • Critical section is empty
  • Processes are waiting in entry section
  • But no process ever enters (perpetual waiting)

Why Progress Matters

Progress may seem like an obvious requirement, but its importance is often underappreciated until a system fails to provide it. Let's examine why progress is essential.

The System Availability Perspective

From a systems perspective, lack of progress means unavailability. Resources exist but cannot be accessed. The system is running but not doing useful work.

Consider a database system:

Without progress, transactions may queue indefinitely
Users see timeouts and failures
The system appears hung even though no crash occurred
Restarting may not help if the algorithm design lacks progress

Progress Violations Often Look Like Deadlocks

When progress fails, the symptom is often indistinguishable from deadlock:

Processes are waiting
No process is making progress
The system appears frozen

However, the root cause is different:

Deadlock: Circular waiting for resources held by others
Lack of progress: Algorithmic flaw preventing entry even when resources are free

Distinguishing these requires understanding the synchronization algorithm.

Manifestations of Progress Failures

•Infinite Waiting: Processes sit in their entry section forever, even though no one is in the critical section. The decision mechanism is broken.
•Livelock: Processes are active (not blocked), but keep retrying and failing. Like two people in a hallway who keep side-stepping the same direction.
•Protocol Deadlock: The synchronization protocol itself creates a circular dependency that prevents any process from proceeding.
•Starvation of All: Unlike bounded-waiting violations that starve specific processes, progress failures can starve everyone—the entire system grinds to a halt.

Real-World Impact

Progress failures have significant business and operational impact:

Web Services: A load balancer synchronization bug that lacks progress can take down an entire cluster, even though individual servers are healthy.

Transaction Processing: Credit card transactions queue indefinitely; customers are neither charged nor declined; money is in limbo.

Industrial Control: Safety interlocks that fail to progress can either prevent necessary shutdowns (dangerous) or prevent necessary operations (costly).

Database Systems: Table locks that never release due to progress failures can halt all transactions touching those tables.

Progress Failures Can Be Subtle

Unlike mutual exclusion violations (which corrupt data and may be detected quickly), progress failures are insidious. The system doesn't crash—it just stops making progress. Monitoring may not catch it immediately, especially if the progress failure only occurs under specific contention patterns that don't appear frequently.

Common Progress Violations

Let's examine concrete examples of algorithms that violate progress. Understanding these failure patterns helps in designing correct solutions.

Violation 1: Strict Alternation

The simplest incorrect approach to mutual exclusion is strict alternation:

// Shared variable
int turn = 0;  // Whose turn it is (0 or 1)

// Process 0
void process_0() {
    while (true) {
        while (turn != 0) { /* wait */ }  // Entry section
        // Critical section
        turn = 1;                          // Exit section
        // Remainder section
    }
}

// Process 1
void process_1() {
    while (true) {
        while (turn != 1) { /* wait */ }  // Entry section
        // Critical section
        turn = 0;                          // Exit section
        // Remainder section
    }
}

Does this satisfy mutual exclusion? Yes! Only the process whose turn it is can enter.

Does this satisfy progress? NO!

Why Strict Alternation Violates Progress

Consider: turn = 0, P₀ is in its remainder section computing for a long time, P₁ wants to enter but turn ≠ 1. P₁ is blocked EVEN THOUGH the critical section is empty! A process in its remainder section (P₀) is preventing a contending process (P₁) from entering. This directly violates the progress definition.

Violation 2: Naive Flag-Based Approach

Another common incorrect approach uses flags:

incorrect_flag_approach.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
// Shared variables
bool flag[2] = {false, false};  // flag[i] = true means process i wants to enter
 
// Process i (where i is 0 or 1, j is the other)
void process_i() {
    int j = 1 - i;  // The other process
    
    while (true) {
        // Entry section
        flag[i] = true;              // I want to enter
        while (flag[j]) { /* wait */ }  // Wait for other to not want
        
        // Critical section
        access_shared_resource();
        
        // Exit section
        flag[i] = false;             // I no longer want to enter
        
        // Remainder section
        do_other_work();
    }
}
 
/*
 * ANALYSIS:
 * 
 * Mutual exclusion? Actually, NO! 
 * Race condition: Both can set flags true, both can see other's flag false
 * (due to interleaving), and both enter.
 * 
 * But even if we ignore that, there's a PROGRESS VIOLATION:
 * 
 * Consider this interleaving:
 * 1. P₀ sets flag[0] = true
 * 2. P₁ sets flag[1] = true  
 * 3. P₀ checks flag[1], sees true, waits
 * 4. P₁ checks flag[0], sees true, waits
 * 
 * DEADLOCK! Both are waiting for the other to lower their flag.
 * Neither will ever enter the critical section.
 * The critical section is empty and both want to enter, but neither can.
 * Progress is violated.
 */

Violation 3: Incorrect Priority Scheme

Some attempts at fixing the flag problem introduce priority or deference:

incorrect_priority.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
44
45
// Attempt to fix with priority: lower-numbered process yields
// Shared variables
bool flag[2] = {false, false};
 
// Process 0 (lower priority - always defers)
void process_0() {
    while (true) {
        flag[0] = true;
        while (flag[1]) {
            flag[0] = false;  // Back off
            // Wait a bit
            flag[0] = true;   // Try again
        }
        // Critical section
        flag[0] = false;
    }
}
 
// Process 1 (higher priority - never defers)  
void process_1() {
    while (true) {
        flag[1] = true;
        while (flag[0]) { /* just wait */ }
        // Critical section
        flag[1] = false;
    }
}
 
/*
 * PROGRESS VIOLATION:
 * 
 * If P₁ is in its remainder section (forever), and P₀ wants to enter:
 * - P₀ sets flag[0] = true
 * - P₀ checks flag[1], sees false (P₁ not interested)
 * - P₀ enters critical section ✓
 * 
 * So far so good. But now consider:
 * - P₁ rapidly enters and exits critical section repeatedly
 * - Each time P₁ sets flag[1] = true, P₀ defers
 * - P₀ keeps backing off and retrying
 * - P₀ may NEVER get in (starvation, also a bounded waiting issue)
 * 
 * This shows how priority schemes can violate both progress 
 * (under specific timings) and bounded waiting.
 */

The Pattern of Progress Violations

Most progress violations share a common pattern: processes end up waiting for conditions that never become true, even though no process is in the critical section. This can happen through deadlock (circular waiting), through dependency on processes in remainder section, or through livelock (active but unproductive retrying).

Progress and Livelock

Livelock is a particularly insidious form of progress violation where processes are actively executing (not blocked) but making no forward progress. Unlike deadlock, where processes are stuck waiting, livelocked processes are busy doing work—just not useful work.

The Hallway Analogy

Imagine two people approaching each other in a narrow hallway:

Both step left to avoid collision
Now they're still facing each other
Both step right
Still facing each other
This repeats indefinitely

Neither is blocked—both are moving—but neither makes forward progress toward their destination. This is livelock.

Livelock in Synchronization

In synchronization algorithms, livelock occurs when processes repeatedly retry an operation, interfering with each other in a way that prevents any from succeeding:

livelock_example.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
44
45
46
47
48
49
50
51
52
// Example of livelock-prone synchronization
 
bool lock1 = false, lock2 = false;
 
// Process 0 needs both locks
void process_0() {
    while (true) {
        // Try to acquire both locks
        retry_0:
        lock1 = true;  // Acquire lock1
        if (lock2) {   // Check if lock2 is taken
            lock1 = false;  // Release lock1 to avoid deadlock
            goto retry_0;   // Retry
        }
        // Got both locks, execute critical section
        // ...
        lock1 = false;  // Release
    }
}
 
// Process 1 needs both locks (in opposite order)
void process_1() {
    while (true) {
        retry_1:
        lock2 = true;  // Acquire lock2
        if (lock1) {   // Check if lock1 is taken
            lock2 = false;  // Release lock2 to avoid deadlock
            goto retry_1;   // Retry
        }
        // Got both locks, execute critical section
        // ...
        lock2 = false;  // Release
    }
}
 
/*
 * LIVELOCK SCENARIO:
 * 
 * If P₀ and P₁ execute with synchronized timing:
 * 
 * 1. P₀: lock1 = true
 * 2. P₁: lock2 = true
 * 3. P₀: sees lock2 = true, releases lock1
 * 4. P₁: sees lock1 = true, releases lock2  (but lock1 is now false!)
 * 5. P₀: retries, lock1 = true
 * 6. P₁: retries, lock2 = true
 * 7. Back to step 3...
 * 
 * Both processes are actively executing, but neither ever enters
 * the critical section. This can continue indefinitely under
 * unfortunate (but possible) timing conditions.
 */

Livelock vs Deadlock

Understanding the distinction is important for diagnosis and resolution:

Comparing Livelock and Deadlock
Aspect	Deadlock	Livelock
Process state	Blocked, waiting	Active, executing
CPU usage	Low (waiting)	High (busy-looping)
Detection	Often easier (blocked threads)	Harder (appears normal from OS view)
Root cause	Circular wait on resources	Conflicting retry logic
Resolution	Break circular wait	Add randomization/backoff
Example fix	Lock ordering	Exponential backoff

Breaking Livelock: Randomized Backoff

The standard technique for preventing livelock is to introduce randomization into retry logic. If processes back off for random durations before retrying, they will eventually desynchronize and one will succeed:

void process_with_backoff() {
    retry:
    int backoff = 1;
    lock1 = true;
    if (lock2) {
        lock1 = false;
        // Random delay between 0 and backoff time units
        delay(random() % backoff);
        backoff = min(backoff * 2, MAX_BACKOFF);  // Exponential backoff
        goto retry;
    }
    // Success
}

Exponential backoff is particularly effective: each failed attempt doubles the maximum wait time. This ensures that even if two processes start in lockstep, they quickly diverge.

This technique is used extensively in network protocols (Ethernet CSMA/CD) and database retry logic.

Randomization Provides Probabilistic Progress

With randomized backoff, progress is guaranteed with probability 1 (almost surely) but not deterministically. For most practical systems, this is sufficient. However, some real-time systems require deterministic progress guarantees, which requires different algorithmic approaches.

Analyzing Solutions for Progress

How do we systematically verify that a synchronization algorithm satisfies progress? This section provides a structured approach.

Progress Analysis Checklist

When analyzing a proposed solution, consider these questions:

Can processes block on remainder-section processes?
- If yes, progress is likely violated
- The protocol should not reference or depend on remainder-section state
Is there a scenario where all contending processes wait indefinitely?
- Enumerate possible states where multiple processes are in entry section
- Check if there's a state from which no process can proceed
Are there cyclic dependencies in the waiting logic?
- If P₀ waits for a condition set by P₁, and P₁ waits for a condition set by P₀, deadlock is possible
Does the algorithm have livelock potential?
- Look for retry-after-backing-off patterns
- Check if synchronized retries can continue indefinitely

Steps for Progress Verification

•Identify waiting conditions: What must be true for a process to enter its critical section?
•Determine who changes conditions: Which processes can make the waiting condition true?
•Check for remainder-section independence: Does the answer to #2 include processes in remainder section?
•Construct adversarial schedules: Try to find an execution order that causes all contenders to wait forever.
•Prove absence of such schedules: Show that no such execution exists (often by proving a progress variant).

Example: Analyzing Peterson's Algorithm for Progress

Let's apply this framework to Peterson's Algorithm (which we'll study in detail later):

petersons_progress_analysis.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
// Peterson's Algorithm (brief version for analysis)
// Shared: bool flag[2], int turn
 
// Entry section for process i (j = 1-i is the other):
flag[i] = true;        // I want to enter
turn = j;              // Give priority to the other
while (flag[j] && turn == j) { /* wait */ }
 
// Exit section for process i:
flag[i] = false;
 
// PROGRESS ANALYSIS:
 
// Step 1: Identify waiting condition
// Process i waits while: flag[j] == true AND turn == j
 
// Step 2: Who changes these?
// - flag[j] is set to false by process j's exit section
// - turn is set by the entry sections of both processes
 
// Step 3: Remainder section independence?
// - A process in remainder section does NOT maintain flag = true
// - flag[j] = true only when j is CONTENDING (in entry, in CS, or exiting)
// - Remainder section processes have flag = false
// ✓ No remainder section dependency
 
// Step 4: Construct adversarial scenario
// Assume both P₀ and P₁ are in entry section:
// - flag[0] = true, flag[1] = true
// - Either turn = 0 or turn = 1 (whoever wrote last)
// - If turn = 0: P₀ waits (flag[1] && turn==1 is false), P₀ enters ✗
//              : Actually, turn = 0 means P₁ sets turn = 0 (giving priority to P₀)
//              : P₀ checks flag[1] && turn==0: false branch, P₀ enters ✓
// - Similarly for turn = 1: P₁ enters
 
// Step 5: Prove no permanent wait
// In any state with both processes waiting:
// - turn is either 0 or 1
// - The process who did NOT set turn last can proceed
// - Therefore, at least one process will enter
// ✓ Progress is guaranteed

The "Turn" Variable is Key

In Peterson's Algorithm, the turn variable breaks symmetry. When both processes want to enter, turn determines who goes first. Crucially, the process that sets turn LAST gives priority to the other, ensuring that at least one can proceed. This demonstrates a general principle: symmetric algorithms need asymmetry (like turn or priorities) to guarantee progress.

Progress vs. Bounded Waiting

Progress and bounded waiting are related but distinct requirements. Understanding their difference is crucial for precise analysis of synchronization algorithms.

The Distinction

Progress answers: "Will SOME process eventually enter the critical section?"

Bounded Waiting answers: "Will THIS PARTICULAR process eventually enter the critical section?"

Progress is about the system making forward progress. Bounded waiting is about fairness to individual processes.

A Solution Can Have Progress But Not Bounded Waiting

Consider a solution where:

If the critical section is empty and processes want to enter, one will enter (progress ✓)
But the same process might be repeatedly chosen, starving others (bounded waiting ✗)

Progress vs. Bounded Waiting
Requirement	Guarantees	Violation Means	Prevents
Progress	Some process enters eventually	ALL processes wait forever	System-wide deadlock
Bounded Waiting	EACH process enters eventually	ONE process waits forever	Individual starvation

Example: Progress Without Bounded Waiting

Consider a lock implementation using test-and-set:

progress_without_bw.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
// Simple spinlock with test-and-set
// Has progress but NOT bounded waiting
 
volatile bool lock = false;
 
void acquire() {
    // test_and_set atomically reads lock and sets it to true
    // Returns the old value
    while (test_and_set(&lock)) {
        // Lock was held, keep trying
    }
    // Lock acquired
}
 
void release() {
    lock = false;
}
 
/*
 * PROGRESS: ✓
 * - If lock is false (no one in CS) and processes are waiting,
 *   one will successfully acquire (the one whose test_and_set 
 *   sees false first)
 * 
 * BOUNDED WAITING: ✗
 * - Nothing prevents the same process from immediately re-acquiring
 *   the lock after release
 * - A "lucky" process might always win the race
 * - An "unlucky" process might spin forever while others continually
 *   grab and release the lock
 * 
 * REAL-WORLD IMPACT:
 * - Under high contention, this can cause severe unfairness
 * - Some processes experience minimal latency; others experience
 *   extremely long waits
 * - Modern systems use more sophisticated locks (queue-based, etc.)
 *   to ensure bounded waiting
 */

Progressive Strengthening of Requirements

The three requirements form a hierarchy of strength: Mutual Exclusion (safety) → Progress (liveness) → Bounded Waiting (fairness). Each builds on the previous. A correct solution must satisfy all three.

Progress in Modern Systems

Modern operating systems and synchronization primitives are designed with progress as a core requirement. Let's examine how progress is ensured in practice.

OS-Level Progress Mechanisms

1. Blocking Primitives with Timeouts

Modern systems allow operations to specify timeouts, preventing indefinite waits:

timed_operations.c
1
2
3
4
5
6
7
8
9
10
11
12
// pthread_mutex_timedlock - blocks with timeout
int result = pthread_mutex_timedlock(&mutex, &timeout);
if (result == ETIMEDOUT) {
    // Lock acquisition timed out - handle gracefully
    // This ensures progress at the application level
    // even if lower-level progress is violated
}
 
// Similar constructs exist in many languages/platforms:
// - Java: tryLock(timeout, unit)
// - Python: lock.acquire(blocking=True, timeout=5)
// - C#: Monitor.TryEnter(obj, timespan)

2. Priority Inheritance

Priority inheritance prevents priority inversion from blocking progress. When a low-priority process holds a resource needed by a high-priority process, the low-priority process temporarily inherits the high priority, ensuring it runs and releases the resource.

3. Kernel-Level Fair Scheduling

OS schedulers are designed to ensure progress at the process/thread level. Even if a synchronization algorithm has potential for blocking, the OS scheduler ensures waiting threads eventually get CPU time to check conditions.

Hardware Progress Guarantees

Modern hardware provides progress guarantees for atomic operations:

LL/SC (Load-Linked/Store-Conditional) guarantees that store-conditional will eventually succeed if the location is not modified by others.

Hardware Lock Elision (HLE) uses transactional memory to optimistically execute critical sections, falling back to locks only on conflicts.

NUMA-Aware Locks prevent progress failures due to memory access asymmetries in multi-socket systems.

Modern Progress Guarantees

•Timeouts: Application-level insurance against progress violations
•Priority Inheritance: Prevents priority inversion from blocking high-priority work
•Fair Scheduling: OS guarantees all runnable threads eventually execute
•Wait-Free/Lock-Free Algorithms: Guarantee progress without traditional locks
•Hardware Transactional Memory: Provides progress through optimistic execution

Defense in Depth

Production systems employ multiple layers of progress protection. Even if one mechanism fails, others catch the failure. Timeouts are the ultimate backstop—even if a lock implementation somehow violates progress, timeouts prevent indefinite waiting at the application level.

Summary: The Progress Requirement

We have thoroughly explored the progress requirement—the second essential property of correct synchronization solutions. Let's consolidate the key concepts.

Key Takeaways

•Progress ensures that if no process is in the critical section and some processes want to enter, one will eventually enter. It prevents system-wide blocking.
•Remainder section exclusion is critical: processes not contending should not block contending processes. The decision is made only by those actually wanting entry.
•Common violations include strict alternation (remainder section dependency), naive flag approaches (deadlock), and livelock (active but unproductive processes).
•Livelock differs from deadlock: processes are active but making no forward progress. Randomized backoff is the standard solution.
•Progress analysis involves checking remainder-section independence, searching for deadlock states, and verifying that at least one contender can always proceed.
•Progress vs. bounded waiting: progress guarantees SOME process enters; bounded waiting guarantees EACH process enters. Both are required for correctness.

Looking Ahead

With mutual exclusion and progress under our belt, we now understand:

Mutual Exclusion: At most one process in the critical section (safety)
Progress: Some process will eventually enter (liveness)

But these two requirements alone permit unfairness—a system where some processes enter repeatedly while others starve. The third requirement, Bounded Waiting, addresses this by ensuring every waiting process eventually gets its turn.

In the next page, we explore bounded waiting in depth, completing our understanding of what makes a synchronization solution truly correct.

Page Complete

You now understand the progress requirement—what it means, why it matters, how violations manifest, and how to analyze solutions for progress. In the next page, we will explore Bounded Waiting—the fairness guarantee that prevents individual starvation.