Computer Science › Section D · Operating systems › Topic D.5

Competition among processes: semaphores and deadlock

When many processes share one printer, one file or one bank balance, a badly timed switch can corrupt data or freeze the system. This topic shows how operating systems use semaphores to let only one process at a time into a critical region, and how they prevent or escape deadlock.

Sharing is harder than it looks

The operating system constantly hands out resources: files, memory, printers and drives. Some are nonshareable: if two processes printed on one printer at once, their pages would be interleaved and useless to both. So the OS must record whether each such resource is free and make other processes wait while it is in use. That sounds simple, but as the topic Coordinating the machine: processes and scheduling showed, the dispatcher can interrupt a process between any two machine instructions, and badly placed interruptions break naive solutions.

A flag that fails

Suppose the OS keeps a one-bit flag for the printer: clear (0) for free, set (1) for in use. To grant the printer, it reads the flag and, if clear, sets it. But this takes several machine instructions. Process A reads the flag and finds it clear; before A sets it, A's time slice ends. Process B reads the still-clear flag, sets it and starts printing. A then resumes where it stopped, sets the flag and prints too. When the outcome depends on the exact timing of switches like this, the bug is called a race condition.

Worked example: a lost update

A shared balance holds $100. Two processes each add $50 using three steps: load the balance into a register, add 50, store the result. 1. If one finishes before the other starts, the second loads 150 and stores 200: correct. 2. Now interleave them: A loads 100, then is switched out. 3. B loads 100, adds 50 and stores 150. 4. A resumes with 100 still in its saved register, adds 50 and stores 150. 5. The final balance is $150: B's deposit has vanished. Check: every possible interleaving of the six steps gives either 200 or 150. The fix is to let only one process at a time run the three steps.

Making test-and-set indivisible

The flag fails because an interrupt can split testing from setting. One fix is to disable interrupts before testing the flag and enable them again after setting it, so nothing can cut in. A neater fix is a test-and-set instruction, which many processors provide: in one machine instruction it reads the flag, notes its old value and sets it. A processor finishes its current instruction before responding to an interrupt, so the test and the set stay together. An operation that cannot be split is called atomic. On multicore machines disabling interrupts is not enough, because another core keeps running, so atomic instructions are essential.

Semaphores and critical regions

Code that only one process may run at a time, such as updating the balance, is a critical region, and the rule that only one process at a time may be inside it is mutual exclusion. A properly protected flag guarding a critical region is a binary semaphore, named after railway signals that admit one train at a time to a stretch of track; programmers also call it a lock or mutex. To enter, a process must find it clear and set it in one atomic step; on leaving, it clears it. Edsger Dijkstra introduced semaphores in the 1960s in a more general form: a counter with two atomic operations, wait (P) and signal (V).

Worked example: a counting semaphore

Two printers are guarded by a semaphore S starting at 2. Wait: if S is above 0, subtract 1 and continue; otherwise block. Signal: wake one blocked process if any, otherwise add 1 to S. 1. A calls wait: S becomes 1 and A gets a printer. 2. B calls wait: S becomes 0 and B gets the other. 3. C calls wait: S is 0, so C blocks. 4. A signals: C is waiting, so C wakes and takes A's printer, and S stays 0. 5. B signals: no one waits, so S becomes 1. 6. C signals: S becomes 2. Check: S ends where it began, and no more than two processes ever held printers.

Deadlock

Deadlock is a state where a group of processes can never proceed, since every one of them needs a resource held by another member of the group. Process P holds the scanner and waits for the printer; process Q holds the printer and waits for the scanner. Neither will ever move. Other resources can deadlock too. If the process table is full and every process must create one more process before it can finish, a step UNIX calls forking, then none can continue.

The four conditions

A 1971 analysis by Edward Coffman and colleagues showed that deadlock can happen only when four conditions all hold. 1. Mutual exclusion: at least one resource is nonshareable. 2. Hold and wait: a process holds some resources while requesting more. 3. No preemption: a resource cannot be taken away from a process that holds it. 4. Circular wait: there is a closed chain of processes, each waiting for a resource held by the next. Some textbooks list only the first three, but the four-condition form is standard. Break any one and deadlock cannot occur.

Worked example: finding and breaking a cycle

P1 holds the scanner and wants the printer. P2 holds the printer and wants the plotter. P3 holds the plotter and wants the scanner. Is this deadlock? 1. Draw a wait-for graph, with an arrow from each process to the one holding what it wants: P1 to P2, P2 to P3, P3 to P1. 2. The arrows form a closed loop, a circular wait, so all four conditions hold: deadlock. 3. To prevent it, number the resources, scanner 1, printer 2, plotter 3, and make every process request them in increasing order. 4. P3 must then get the scanner before the plotter, so it can never hold the plotter while waiting for the scanner. Check: with ordered requests no loop can form.

Three ways to handle deadlock

Prevention makes one condition impossible. Making a process ask for everything it needs in a single request removes hold and wait. Ordered requests remove circular wait. Spooling attacks mutual exclusion: processes send output to a file on disk, and the OS prints the files one at a time later, so the printer appears shareable. Avoidance lets the OS refuse any request that could lead to deadlock; Dijkstra's banker's algorithm is the classic example. Detection and recovery lets deadlock happen, finds it, then breaks the cycle by killing processes or forcibly taking resources back. Files can be shared by many readers at once, but a writer needs exclusive access.

Common mistakes to avoid

Checking a flag and then setting it in separate instructions is not mutual exclusion; the two steps must be atomic. A race condition is not deadlock: a race gives wrong results; deadlock gives no progress. Deadlock is not mere slowness; without outside help the processes never continue. Signal does not always add 1 to a semaphore: if a process is blocked, signal wakes it instead. And breaking any one of the four conditions is enough; you do not need to remove all of them.

Key takeaways

Nonshareable resources need mutual exclusion; a test and set split by an interrupt causes race conditions such as lost updates. Disabling interrupts or an atomic test-and-set instruction fixes this. Binary semaphores act as locks on critical regions, and counting semaphores manage several identical resources with wait and signal. Deadlock requires mutual exclusion, hold and wait, no preemption and circular wait together. It can be prevented by breaking a condition, avoided by refusing unsafe requests, or detected and recovered from by killing processes or reclaiming resources.

Flashcards

Flashcard

Nonshareable resource

A resource only one process can use at a time

A printer mid-job.

Test your understanding

Question 1 of 5

A shared counter holds 10. Two processes each add 5 by loading the counter, adding 5 and storing the result, with no lock. Which final value, besides 20, is possible?

Question 2 of 5

Why is a test-and-set instruction safe where a separate test followed by a set is not?

Question 3 of 5

A counting semaphore starts at 3. Five processes each call wait, and none has called signal yet. What is the result?

Question 4 of 5

A system makes every process request all the resources it will need before it starts running. Which deadlock condition does this remove?

Question 5 of 5

Instead of connecting processes to the printer, the OS stores each print job on disk and prints the jobs one by one later. Which deadlock condition does this attack?

← Previous topicNext topic →