CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 2 of 8 · 2 min read

The idea

Think of it this way. A town with a one-lane bridge can solve the jam in several ways. It can allow traffic in one direction at a time (removing the meeting in the middle), build a second bridge, or station a guard who orders a car to reverse. Each rule changes the structure of the road, so that the jam cannot occur at all. The analogy stops here: the town can pick any one rule, but a program must often live with several users at once, each with its own habits.

Prevention works the same way. For each of the four conditions, there is a rule that makes it impossible:

Condition Rule that removes it Main cost
Mutual exclusion Make the resource shareable, or let only one thread ever ask for it Many resources cannot be shared
Hold and wait Take every resource at once, or hold nothing while asking Resources sit idle; the need must be known early
No preemption If a request fails, give back what is held and try again Wasted work; risk of livelock (page 6)
Circular wait Number the resources; ask only in increasing order The order must be known and respected everywhere

In plain words: The experiment in the rest of the page uses one task: moving money between four bank accounts, each protected by its own lock. Every run kept the total at 4,000, so no money was lost or created.

Deadlock prevention

Deadlock prevention is the design of a system or program so that at least one of the four necessary conditions can never hold, which makes a deadlock impossible by construction.

Example: a rule that all threads lock accounts in order of account number makes circular wait impossible, so the transfer code cannot deadlock.

Check yourself: 1. Why does removing just one of the four conditions make a deadlock impossible? 2. Which condition does the "one-way bridge" rule most resemble? 3. What is the main difference between prevention and detection?