Requirements for Solutions to the Critical Section Problem
Progress: Preventing Unnecessary Blocking
Read aloud is unavailable in this browser.
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.
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.
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]= processiis in its entry section, wanting to enter its critical sectionin_cs[i]= processiis in its critical sectionin_remainder[i]= processiis 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.
123456789101112131415161718192021222324
// 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.
- •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.
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!
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:
12345678910111213141516171819202122232425262728293031323334353637383940414243
// Shared variablesbool 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:
123456789101112131415161718192021222324252627282930313233343536373839404142434445
// Attempt to fix with priority: lower-numbered process yields// Shared variablesbool 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. */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:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
// Example of livelock-prone synchronization bool lock1 = false, lock2 = false; // Process 0 needs both locksvoid 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:
| 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.
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
- •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):
1234567891011121314151617181920212223242526272829303132333435363738394041
// 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 enterturn = j; // Give priority to the otherwhile (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 guaranteedIn 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 ✗)
| 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:
1234567891011121314151617181920212223242526272829303132333435363738
// 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 */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:
123456789101112
// pthread_mutex_timedlock - blocks with timeoutint 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.
- •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
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.
KEEP LEARNING
There’s more to understand.
You’re reading the introduction. Create a free account to read the complete lesson, save notes and keep track of your progress.