The Resource Allocation Problem
Reading 2 painted a picture of multiprogramming as an elegant solution: many processes share a CPU by taking turns, each advancing a little at a time, with the OS managing the choreography invisibly. And most of the time, that picture is accurate.
But processes do not only share the CPU. They also share other resources: printers, files, network connections, memory regions, database records. And unlike CPU time — which can be divided into time slices and given to multiple processes in alternation — some resources cannot be shared simultaneously. Only one process at a time can write to a file without corrupting it. Only one process at a time can send output to a printer without the pages becoming garbled.
These are called nonshareable resources. Managing access to them is one of the most subtle and important challenges in operating system design. The difficulty comes from a property you might not have considered: a process can be interrupted by the dispatcher at any moment, including in the middle of what looks like a simple, single operation.
Why a Simple Flag Is Not Enough
Suppose the OS wants to control access to a single printer. A natural approach: keep a flag in memory. A clear flag (0) means the printer is available. A set flag (1) means the printer is in use. When a process requests the printer, the OS checks the flag — if clear, grant access and set the flag; if set, make the process wait.
This sounds reasonable. But it has a fatal flaw, and the flaw is rooted in something you learned in Topic 2c: the CPU executes one instruction at a time. Checking a flag and then setting it are two separate instructions. The dispatcher can interrupt a process between any two instructions. Consider what can happen:
| Step | Process A | Process B | Flag Value |
|---|---|---|---|
| 1 | Checks flag — finds it clear (printer available) | — | 0 (clear) |
| 2 | Interrupted before setting the flag | — | 0 (still clear) |
| 3 | — | Checks flag — finds it clear (printer "available") | 0 (still clear) |
| 4 | — | Sets flag, begins using printer | 1 (set) |
| 5 | Resumes, sets flag, begins using printer | Also using printer | 1 (set) |
Two processes are now sending output to the same printer simultaneously. The output from both will be interleaved into garbage. The simple flag approach has failed — not because the logic was wrong, but because the check and the set were not guaranteed to happen together as a single, uninterruptible unit.
This kind of problem — where the outcome depends on the precise timing of interrupts between two processes — is called a race condition. Race conditions are notoriously difficult to debug because they are intermittent: the problem only appears when the interrupt happens at exactly the wrong moment, which may be rare. The system works correctly 999 times and fails the 1000th, with no obvious explanation.
Semaphores: A Properly Implemented Flag
The solution is to ensure that the act of checking and setting a flag happens as a single, atomic (uninterruptible) operation. A flag implemented with this guarantee is called a semaphore — a term borrowed from the railroad signals used to control access to sections of track.
Modern CPUs provide a machine instruction called test-and-set that performs the check and the set in a single, uninterruptible step. Because the CPU always completes a full instruction before responding to an interrupt, no other process can slip in between the check and the set when they are implemented as one instruction.
The railroad analogy: A semaphore on a railway line signals whether a section of track is occupied. A train must check the signal and, if clear, claim the track before proceeding. The key is that the signal check and the track claim happen as part of a single coordinated action — a train cannot be preempted between checking the signal and entering the track. Semaphores in computing work on the same principle.
With a proper semaphore, the access protocol for a nonshareable resource works reliably:
- A process that wants the resource checks the semaphore atomically. If it is clear, the process sets it and proceeds. If it is set, the process waits.
- When the process finishes with the resource, it clears the semaphore, allowing a waiting process to proceed.
Critical Regions and Mutual Exclusion
The section of code that accesses a nonshareable resource — the part that must be executed by only one process at a time — is called a critical region. The requirement that only one process at a time may execute a critical region is called mutual exclusion.
Mutual exclusion is enforced by guarding the critical region with a semaphore. Before entering the critical region, a process must find the semaphore clear and set it. Upon leaving the critical region, the process clears the semaphore. Any process that finds the semaphore set when it tries to enter must wait.
Critical regions in everyday computing: Database systems use mutual exclusion constantly. When two users try to update the same bank account balance at the same moment, the database must ensure that their updates happen sequentially, not simultaneously. Without mutual exclusion, one update could overwrite the other, and money could disappear or be created from nothing.
Deadlock: When Waiting Becomes Permanent
Semaphores solve the race condition problem, but they introduce a new one: deadlock. Deadlock is the condition in which two or more processes are each waiting for a resource held by the other, so neither can ever proceed.
A classic example: Process A holds the printer and is waiting for the DVD drive. Process B holds the DVD drive and is waiting for the printer. Neither process can release what it holds until it gets what it is waiting for. Neither will ever get what it is waiting for. Both are frozen. Forever.
A traffic analogy: Imagine a four-way intersection where each car has entered the intersection from one direction and is waiting for the car ahead of it to move. No car can move because each is blocked by the next. All four sit permanently. This is deadlock — a circular dependency where everyone is waiting for someone else to go first.
The Three Conditions for Deadlock
Research has shown that deadlock cannot occur unless all three of the following conditions are present simultaneously:
| Condition | What It Means |
|---|---|
| 1. Competition for nonshareable resources | At least one resource in the system cannot be used by more than one process at a time. |
| 2. Partial allocation | Processes hold some resources while waiting for others. A process does not acquire all its needed resources at once before starting. |
| 3. No preemption | Once a resource has been allocated to a process, it cannot be forcibly taken away. The process must release it voluntarily. |
The critical insight: if any one of these three conditions is eliminated, deadlock becomes impossible. This gives OS designers a menu of strategies.
Dealing with Deadlock
Operating systems handle deadlock through two broad categories of strategy: detection and correction, and avoidance.
Detection and Correction
Detection and correction schemes accept that deadlock may occasionally occur and deal with it when it does. The OS monitors the system for signs of deadlock (circular waiting dependencies in the process table) and, when detected, breaks the deadlock by forcibly reclaiming resources from one or more processes — which may mean terminating those processes entirely.
On Unix-based systems, the command for forcibly terminating a process is literally
called kill. On Windows, Task Manager's "End Task" button serves the
same purpose. When you use either of these to unfreeze a stuck application, you are
manually performing deadlock correction.
A system administrator with elevated privileges (sometimes called a super user or administrator) has the ability to terminate any process on the system, including those belonging to other users. This power is essential for breaking deadlocks that individual users cannot resolve themselves.
Avoidance: Attacking the Conditions
Avoidance schemes try to prevent deadlock from occurring in the first place by eliminating one of the three necessary conditions.
- Attacking condition 2 (partial allocation): Require each process to request all the resources it will ever need before it begins executing. If all resources are available, the process starts with everything it needs and never has to wait for more. If any resource is unavailable, the process waits before starting rather than holding some resources while waiting for others.
- Attacking condition 1 (nonshareable resources) — spooling: Convert a nonshareable resource into an apparently shareable one by creating an illusion. Suppose many processes need to print. Rather than giving each process direct access to the printer (which is nonshareable), the OS gives each process access to a virtual printer that simply stores the print data in mass storage. Later, when the real printer is free, the OS sends the stored data to it. Each process believes it printed successfully; the actual printing happened sequentially. This technique is called spooling, and it is exactly how print queues have worked for decades.
Spooling in your daily life: Every time you send a document to a shared office printer and it goes into a print queue, you are benefiting from spooling. Your process finished immediately (as far as your computer was concerned), and the printer is handling jobs one at a time from the queue. The nonshareable resource appears shareable to every user.
The Bigger Picture
Race conditions, semaphores, critical regions, mutual exclusion, deadlock — these are not obscure edge cases. They are fundamental challenges that appear wherever concurrent processes share limited resources. They show up in operating systems, databases, network protocols, multi-threaded programs, and distributed cloud systems.
For K-12 teachers, the most valuable takeaway may be this: a computer that "hangs," "freezes," or "stops responding" is almost always in a waiting state of some kind — often a deadlock or a process blocked on a resource it cannot get. The solution (restarting the application, or in severe cases rebooting the machine) is a brute-force deadlock correction: give up on the stuck processes, release all their resources, and start fresh. The OS designers tried to be more elegant. Sometimes the brute force approach is what works.