Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

The critical-section problem

Clear, exam-oriented notes on the critical-section problem: definitions, formal requirements (mutual exclusion, progress, bounded waiting), typical failed solutions, a correct solution sketch (Peterson), worked model answers, common mistakes and exam tips.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

The critical-section problem appears whenever multiple processes or threads share data or resources and must not interfere with each other. An engineer uses these ideas when designing or debugging concurrent programs, kernel code (process/thread schedulers, device drivers), or synchronization primitives (locks, mutexes, semaphores) so that shared data remain correct and the system remains responsive.

Key ideas

  • Entry section (or entry protocol): code executed just before a process enters its critical section to ensure safety.
  • Exit section (or exit protocol): code executed right after leaving the critical section to allow others to enter.
  • Remainder section: code outside the entry/CS/exit; not involved with the shared resource.

State diagram to draw for an exam: draw one box for each of the four regions — "Remainder", "Entry", "Critical Section", "Exit" — and draw directed arrows: Remainder -> Entry, Entry -> Critical Section, Critical Section -> Exit, Exit -> Remainder. Label the arrows with the conditions or operations that cause the transition (e.g., testing a lock, setting a flag, releasing a lock).

Three formal requirements (universally used in university answers). State them exactly and give assumptions:

  1. Mutual exclusion (safety): At most one process may be executing in its critical section at any time.

    • Formal statement: For any time t, there do not exist distinct processes P_i and P_j such that both P_i and P_j are in their critical sections at t.
    • Assumptions: processes execute steps atomically at the statement level assumed by the algorithm (but atomicity of simple read/write must be clarified). If atomic read/write is assumed, some algorithms are possible; if only higher-level atomic operations are available, requirements change.
  2. Progress (liveness): If no process is in the critical section and there exist processes that wish to enter their critical section, then the selection of the next process to enter the critical section cannot be postponed indefinitely; some process that wishes to enter must be able to make progress.

    • Formal statement: If no process is in the CS and one or more processes are in their entry sections (i.e., wish to enter), then the decision of who enters next is made only among those processes and cannot be postponed indefinitely; eventually one of them enters the CS.
    • Assumptions: decision and scheduling must be made only among processes that are not in their remainder sections; steps that decide who enters are executed in finite time.
  3. Bounded waiting (no starvation): There exists a bound N such that after a process P_i indicates its desire to enter the CS, at most N other entry attempts by other processes can be granted entry before P_i is granted entry.

    • Formal statement: There exists a bound N (independent of the execution and of i, though it may depend on n) such that after any process P_i starts trying to enter, at most N other entries to the CS by other processes can occur before P_i is allowed to enter.
    • Assumptions: the algorithm must ensure fairness; the bound must be independent of the execution (but may depend on number of processes n).

Definitions of related terms:

  • Safety property: property that something bad never happens (mutual exclusion is safety).
  • Liveness property: property that something good eventually happens (progress and bounded waiting are liveness).
  • Starvation: a process never enters its CS though it repeatedly tries (violates bounded waiting).
  • Deadlock: a set of processes are blocked forever, each waiting for the other (distinct from starvation — deadlock may prevent any progress at all).

Typical solution styles and assumptions to state in exam answers:

  • Atomic read/write on single shared variables is assumed unless the question allows stronger primitives (test-and-set, compare-and-swap).
  • Scheduler fairness: whether the scheduler can indefinitely delay a ready process is an assumption; most correctness proofs assume a fair scheduler (a process that can make progress will eventually get CPU). If not specified, mention it.

Formulas

Mutual exclusion: ∀t, ¬(∃i≠j : CS(i,t) ∧ CS(j,t)) — CS(i,t) means process i is in critical section at time t.

Progress: If (no process in CS) ∧ (∃i: want(i)=true), then eventually ∃j: CS(j) — want(i) indicates process i is trying to enter.

Bounded waiting: ∃N ∀i ∀executions: after want(i) becomes true, at most N entries by others happen before i enters (N may depend on n but not on i or the execution).

Symbols:

  • i, j: process indices (unitless identifiers).
  • t: time instant (unit: seconds if you reason about real time; typically abstract discrete steps).
  • CS(i,t): predicate, true if process i is in CS at time t.

When these apply: in reasoning about algorithms for mutual exclusion under the stated atomicity and scheduling assumptions.

Worked examples

Example 1 — Simple lock variable (why it fails): model-answer style.

Question: Suppose we use a shared boolean lock initially false. Entry: while (lock) ; lock = true; // then CS. Exit: lock = false. Show this can fail to provide mutual exclusion.

Answer (model): Steps and interleaving to show failure. Label processes P and Q.

  1. Initially lock = false.
  2. P executes while (lock) ; sees lock==false, exits the loop but before it executes lock = true, it is preempted.
  3. Q runs, executes while (lock); sees false, then executes lock = true and enters CS.
  4. Q is still in CS. Scheduler switches back to P. P now executes lock = true (overwriting true with true) and enters CS.

Conclusion: both P and Q can be inside CS simultaneously. This demonstrates that the two-step entry (test then set) is not atomic, so this lock fails. To fix, use an atomic test-and-set or a proper algorithm that coordinates these two steps.

Common exam point: draw the timeline with statements numbered and show the interleaving as above. This is often asked as a diagram: two columns for P and Q, list statement sequence and times, highlight the conflicting interleaving.

Example 2 — Peterson's algorithm (model answer and sketch of correctness). This is a classical solution for two processes using only reads and writes.

C-like pseudocode for processes P0 and P1 (exam answer should be exact):

Process Pi (i = 0 or 1), with other process j = 1 - i:

flag[i] = true;
turn = j;
while (flag[j] && turn == j) { /* busy wait */ }
// critical section
flag[i] = false;

Show mutual exclusion (sketch):

  • Suppose both are in CS at same time. Then both must have passed their while loops. For Pi to pass, either flag[j]==false or turn!=j. If both are in CS, then flag[0] and flag[1] must be true (each set it) at that time. So to pass, for P0 we need turn==1 to be false (i.e., turn==0) and for P1 we need turn==0 to be false (i.e., turn==1). But turn cannot be both 0 and 1 simultaneously. Contradiction. Hence mutual exclusion holds.

Show bounded waiting (sketch):

  • If Pi sets flag[i]=true and waits, Pj can enter at most once before Pi, because Pi sets turn=j giving Pj priority, but once Pj leaves it sets flag[j]=false, so Pi's while condition becomes false and Pi enters. Thus there is a bound (in fact 1) on how many times other process can enter before Pi does. This shows no starvation for two processes.

Notes: This solution uses only atomic reads/writes and assumes each read/write is atomic and that the scheduler eventually gives CPU to waiting processes (weak fairness). For n>2, generalized algorithms exist but are more complex. Initial conditions: initially, flag[0] = flag[1] = false; turn may be initialized arbitrarily.

Worked example 3 — Exam-style long question model answer: "State the three requirements for the critical-section problem. Show by example why a naive solution using a shared integer turn that simply alternates may still starve a process."

Model answer: Provide exact three requirements (as above), then present the alternating turn approach where turn says which process may enter. Show interleaving where a process is stuck in its remainder and never sets turn, causing the other to always find turn set against it — or explain starvation caused by arbitrary scheduler delays. Conclude that turn alone gives mutual exclusion but fails progress or bounded waiting if a process does not try to enter (contradiction to the progress assumption about who decides). Always state assumptions and show timeline.

Common mistakes

  • Confusing deadlock and starvation. Deadlock: set of processes blocked forever. Starvation: one process repeatedly denied access.
  • Not showing interleaving steps when demonstrating failure of a naive solution. Examiners expect step-by-step interleaving or a timeline.
  • For Peterson's proof, claiming the contradiction without arguing why both flag[] would have to be true and why turn cannot be both values.

For your exam

Question types you will see: definitions (state and explain mutual exclusion, progress, bounded waiting), short notes (compare safety and liveness), derivations/proofs (prove Peterson's algorithm enforces mutual exclusion), diagrams (state machine for process states), and design/programming questions (show a failed algorithm interleaving; write small pseudocode for entry/exit protocols).

What a full-marks answer includes:

  • Definitions with bold terms and assumptions stated.
  • Exact formal statements of the three requirements.
  • For algorithm questions: exact pseudocode with comments, proof of mutual exclusion, argument for progress and bounded waiting (or explicit counterexample if it fails), and discussion of assumptions (atomicity, scheduler fairness).
  • For failure examples: show a clear interleaving timeline or two-column sequence for processes.

Quick check

  1. State the three formal requirements of the critical-section problem in one line each.
  2. Why does the simple while(lock) ; lock = true; lock fail? Give an interleaving.
  3. In Peterson's algorithm for two processes, what value does turn hold just before the process in CS entered, and why does that ensure mutual exclusion?

Answers: 1) Mutual exclusion, Progress, Bounded waiting. 2) Because test and set are not atomic — context switch between test and set allows two processes to both see lock==false and then both set it true and enter. 3) If both processes want to enter, just before the entering process passes the while, either the other process's flag is false or turn equals the entering process's own id (not the other's); therefore both cannot be in CS simultaneously because that would require turn to be 0 and 1 at the same time.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?