The Critical Section Problem
Didn't we cover this already?
We mentioned it last lesson, but now we'll also outline some requirements for any good solution to the critical section problem.
The Problem
Consider the example of a microwave. You'd like to heat up some “Hot Pockets”™ as a snack, whereas your roommate wants to soften some butter for a recipe. It would be disastrous if, while your roommate was in the middle of trying to soften the butter on the lowest setting, you obliviously opened the door, tossed in your “Hot Pockets”™, and set the microwave to “maximal nuke” for 3 minutes. It would be a mess.
Meh. That isn't a very computer-science-y example.
-
Well, we looked at the example of incrementing a counter in the last lesson.
I thought it was fine. And I'd totally eat hot-buttered Hot Pockets.
Often, when dealing with a shared resource, we need a strict one-at-a-time policy (a.k.a. mutual exclusion). This is the essence of the critical section problem.
A critical section is a segment of code that accesses shared resources and must be executed by only one thread at a time. The critical section problem is coming up with a workable way to provide mutual exclusion to these critical sections.
Solution Requirements
A proper solution to the critical section problem must satisfy three requirements:
- Mutual Exclusion: Only one thread can execute the critical section at a time.
- Progress: If no thread is in the critical section and some threads want to enter, then one of them must eventually enter.
- The rule outlaws turn-taking solutions where threads must enter in a predefined sequence, such as A, then B, then C, and so on. C can't be kept waiting just because it's B's turn and B doesn't want the resource right now.
- Bounded Waiting: There must be a limit on how long you're kept waiting while other threads get access to the critical section you want.
- The solution does not have to be completely fair; just not grotesquely unfair. For example, a solution that gives access in a random order would be acceptable, since there is an (expected) finite wait time.
-
Progress and Bounded Waiting seem similar to me, since they're both about some kind of fairness and not locking out a thread indefinitely.
-
The difference is whether anyone gets to be in the critical section. When there is no progress, it means that the critical section is not being used by any thread at all, even though some threads want to use it. In contrast, when bounded waiting is violated, other threads are getting to go into the critical section just fine, but one or more threads are never getting a turn.
How an Operating System Can Help
Operating systems need to deal with shared resources all the time, so the critical section problem comes up a lot inside operating system code.
Moreover, operating systems provide processes and threads, so it makes sense for the operating system to also provide a solution to the critical section problem for user programs. The OS is, after all, in a unique position to control which processes run and which ones must wait.
Thus an operating system should provide some generalized primitives that can be used to solve the critical section problem. These primitives should follow the requirements above, and be efficient and easy to use.
Programming Language Support
Although operating systems usually provide the foundational synchronization mechanisms for user programs (beyond facilities built directly into the processor itself), in many cases programming languages take these primitives and build higher-level synchronization constructs on top of them that feel natural for that particular language.
Next we'll look at one such primitive: semaphores.
(When logged in, completion status appears here.)