Questions: Critical Section Problem: Formal Definition

Question 1

A lock implementation ensures mutual exclusion (no two processes in the critical section at once) and liveness (every process that enters eventually leaves). Does this satisfy all three formal requirements of the critical section problem?

• A. Yes — mutual exclusion and liveness together imply all three requirements
• B. No — the implementation may still allow a process to be indefinitely postponed (violating bounded waiting) even while the system as a whole makes progress
• C. No — mutual exclusion already subsumes both progress and bounded waiting
• D. Yes — as long as no process waits forever overall, bounded waiting is trivially satisfied

Answer: (B)

Mutual exclusion and liveness together do NOT guarantee bounded waiting. Consider a scheduler that always grants the lock to the same process when multiple are waiting: mutual exclusion holds, the system makes progress, every holder eventually leaves — yet one process is perpetually denied. Bounded waiting requires a specific guarantee on *how many times* others can enter before a given waiting process gets its turn. Without it, indefinite starvation is possible even in a 'live' system. All three requirements are independent and necessary.

Question 2

Peterson's algorithm achieves mutual exclusion, progress, and bounded waiting for two processes on paper. Why does it fail on modern multicore hardware?

• A. Modern CPUs execute too quickly for the algorithm's timing assumptions to hold
• B. CPUs and compilers reorder memory operations for performance, invalidating the memory-ordering guarantees that Peterson's algorithm relies on
• C. The algorithm requires atomic read-modify-write operations not available without special hardware
• D. Peterson's algorithm is only defined for three or more processes, not for two

Answer: (B)

Peterson's algorithm's correctness depends on specific orderings of shared-variable reads and writes. Modern CPUs and compilers freely reorder memory operations (store buffering, out-of-order execution, caching). A process may write its flag variable, but the write may not be visible to another CPU before that CPU reads it — allowing both processes to simultaneously believe they have exclusive access, violating mutual exclusion. Memory barrier instructions are required to enforce the ordering, or hardware atomic operations (test-and-set, compare-and-swap) which provide built-in ordering guarantees.

Question 3

Bounded waiting is violated if one process is perpetually denied entry to the critical section while other processes successfully enter and exit, even if the system overall continues making progress.

• T. True
• F. False

Answer: True

This is precisely the definition of starvation, which bounded waiting prevents. Progress only requires that the decision about who enters next is made in finite time — it says nothing about fairness to any specific process. Bounded waiting adds the constraint that each process can be 'passed over' at most k times before getting its turn, for some fixed k. A simple test-and-set spinlock satisfies mutual exclusion and progress but can starve a process if the scheduler perpetually favors other threads. Bounded waiting is violated even though the system keeps moving.

Question 4

Mutual exclusion implies progress: if at most one process can be in the critical section at a time, processes waiting to enter will typically be able to do so in finite time.

• T. True
• F. False

Answer: False

Mutual exclusion and progress are independent requirements. A trivially broken solution demonstrates this: always acquire a lock that is never released — mutual exclusion holds (no two processes are ever inside simultaneously) but no process can ever enter. More subtly, a process in its *remainder section* could hold the lock indefinitely, blocking all others. Progress requires specifically that processes NOT in the critical section and NOT waiting to enter cannot influence who enters next. Mutual exclusion makes no such guarantee.

Question 5

Explain the difference between the 'progress' requirement and the 'bounded waiting' requirement in the critical section problem. Why are both necessary?

Model answer: Progress ensures that the decision of who enters the critical section next is made in finite time, and only processes actively trying to enter participate in that decision — processes in their remainder section cannot block entry. Bounded waiting ensures fairness: once a process requests entry, there is a fixed bound on how many times others can enter before it does. Progress prevents livelock and deadlock; bounded waiting prevents starvation. A system can satisfy progress by always making quick decisions while systematically picking the same process, indefinitely starving others — bounded waiting forbids this.

A useful distinction: progress asks 'will *someone* eventually get in?' while bounded waiting asks 'will *this specific process* eventually get in?' A scheduler could satisfy progress by deciding quickly who goes next, while ignoring one process forever. Bounded waiting adds the per-process fairness guarantee. Together they ensure not just that the system moves forward, but that every process participates in that forward movement within a bounded number of turns.