The Critical Section Problem
The critical section problem is the challenge of designing a protocol that lets multiple processes safely take turns executing their critical sections, the parts of their code that access shared data. A correct solution must guarantee three requirements at the same time: mutual exclusion, progress and bounded waiting, while code outside the critical section runs without coordination.
Once you know shared data needs protecting from concurrent access, the next question is: exactly what protocol should govern that protection? This is a formally defined challenge in OS theory called the critical section problem, and any correct solution has to satisfy three specific requirements at the same time.
What a critical section is
A critical section is the specific part of a process's code where it accesses shared data that other processes could also be accessing. Everything outside that section is the "remainder section," code that doesn't touch the shared resource and can safely run without any coordination at all.
The three requirements a correct solution must satisfy
- Mutual exclusion. If one process is currently executing inside its critical section, no other process may be executing inside its own critical section for that same shared resource at the same time. This is the core safety requirement, exactly what prevents the race conditions covered in the earlier article.
- Progress. If no process is currently in its critical section, and multiple processes want to enter, the decision of who gets to go next can't be postponed indefinitely by processes that aren't even trying to enter, the system has to actually make progress toward letting someone in.
- Bounded waiting. There must be a limit on how many times other processes are allowed to enter their critical sections after a given process has requested entry and before that process's own request is granted. Without this, a process could theoretically be skipped over forever while others repeatedly cut in line, a scenario called starvation.
A solution that only satisfies mutual exclusion but not progress or bounded waiting isn't actually a correct solution to the critical section problem, all three requirements have to hold simultaneously.
A worked structural example
Picture the general shape every solution to this problem follows:
while (true) {
entry_section(); // request permission to enter
critical_section(); // access the shared resource
exit_section(); // release permission
remainder_section(); // unrelated code, no coordination needed
}
The entire challenge of the critical section problem is designing entry_section() and exit_section() correctly, code that guarantees mutual exclusion, progress, and bounded waiting, without the processes needing any special hardware support beyond what's ordinarily available (early theoretical solutions like Peterson's Solution, covered in its own article, achieve this using only ordinary shared variables).
Where this matters in real systems
Every real synchronization primitive in use today, locks, mutexes, semaphores, is ultimately an implementation of a correct entry/exit section for the critical section problem, just built using efficient hardware support (atomic CPU instructions) rather than pure software algorithms like Peterson's Solution. Database systems solving the exact same underlying problem for concurrent transactions call their equivalent mechanism locking protocols (covered in the DBMS subject), but the formal requirements they need to satisfy, safe exclusive access, guaranteed progress, no indefinite starvation, are conceptually identical to the OS-level critical section problem.
What interviewers actually ask about the critical section problem
- "What are the three requirements a correct critical section solution must satisfy?" Mutual exclusion, progress, and bounded waiting, all three simultaneously, not just mutual exclusion alone.
- "What is a critical section?" The part of a process's code that accesses shared data other processes could also be accessing concurrently.
- "Why isn't mutual exclusion alone considered a correct solution?" Because a solution could enforce exclusion but still let processes be postponed indefinitely (violating progress) or starved by others cutting in repeatedly (violating bounded waiting), both are real correctness failures even with exclusion satisfied.
- "What's the practical, real-world equivalent of the critical section problem in a database?" Locking protocols for concurrent transactions, which need to satisfy conceptually the same guarantees: safe exclusive access, guaranteed progress, and no indefinite starvation.
Key takeaways
- The critical section is the part of a process's code that touches shared data other processes might also access.
- A correct solution must guarantee mutual exclusion, progress, and bounded waiting, all three together, not just one or two.
- Bounded waiting specifically exists to prevent starvation, being indefinitely skipped over by other processes.
- Real synchronization primitives (locks, mutexes, semaphores) are all practical implementations of a correct entry/exit section for this exact problem.
More in Process Synchronization
Browse all Operating Systems topics
Log in to save which topics you've read across every subject.
Frequently asked questions
What are the three requirements a correct critical section solution must satisfy?
Mutual exclusion, progress, and bounded waiting, all three simultaneously, not just mutual exclusion alone.
What is a critical section?
The part of a process's code that accesses shared data other processes could also be accessing concurrently.
Why isn't mutual exclusion alone considered a correct solution?
Because a solution could enforce exclusion but still let processes be postponed indefinitely (violating progress) or starved by others cutting in repeatedly (violating bounded waiting), both are real correctness failures even with exclusion satisfied.
What's the practical, real-world equivalent of the critical section problem in a database?
Locking protocols for concurrent transactions, which need to satisfy conceptually the same guarantees: safe exclusive access, guaranteed progress, and no indefinite starvation.