Imagine two cars that have entered a narrow one-lane bridge from opposite ends and come face to face in the middle. If both drivers stay put, each waiting for the other to back up first, neither car will ever cross the bridge. It is hard to say whose fault it is, yet a situation has been created in which no one can move forward.
Exactly the same thing happens inside computers, and it is called a “deadlock.” Put simply, a deadlock is a state in which several programs are each waiting for a resource held by another, so none of them can continue its work and everything comes to a halt. Many of the cases in which a computer suddenly seems to freeze even though nothing is broken are caused by this very deadlock.
In this article, we will look in turn at what a deadlock looks like, the four conditions under which a deadlock occurs, a famous example used to explain it, and the ways computers deal with deadlocks.
Computers That Stop While Waiting on Each Other
How Does a Deadlock Happen?
Inside a computer, many programs run at the same time and share resources such as printers, files, and memory.
(1) Resources Used One at a Time
Some resources get their contents jumbled if several programs use them at once, so while one program is using such a resource, the others must wait. The mechanism that lets a program temporarily take exclusive hold of a resource is called a lock.
(2) A Halt Caused by Crossed Order
For example, the first program may lock file A while waiting for file B, while the second program locks file B while waiting for file A. Because both programs refuse to let go of what they have and only wait for what the other has, both remain stuck forever.
(3) What It Looks Like from the Outside
A program caught in a deadlock simply stops responding, without even an error message. In places that handle many requests at once, such as banking networks or reservation systems, this kind of halt can lead to serious problems.
The Four Conditions for a Deadlock
In 1971, computer scientist Edward G. Coffman Jr. set out four conditions that must all hold at the same time for a deadlock to occur. They are called the Coffman conditions after him.
- Mutual Exclusion: A resource can be used by only one program at a time.
- Hold and Wait: A program already holding one resource waits for additional resources.
- No Preemption: A resource held by another cannot be forcibly taken away; the holder must release it voluntarily.
- Circular Wait: Program 1 waits for program 2, program 2 waits for program 3, and program 3 waits for program 1 again, so the waiting links up into a loop.
(1) Breaking Just One Resolves It
If even one of the four conditions is missing, a deadlock cannot occur. That is why most methods of preventing deadlocks start by breaking one of these four links.
The Dining Philosophers Problem
The story most often used to explain deadlocks is the “Dining Philosophers Problem,” which grew out of a problem posed by the Dutch computer scientist Edsger W. Dijkstra.
(1) The Setup
Five philosophers sit at a round table, with one fork placed between each pair of neighbors, for five forks in all. A philosopher spends time thinking, and when hungry, can eat only after picking up both forks, the one on each side.
(2) The Moment Everyone Goes Hungry
If all five pick up their left forks at the same moment, every one of them ends up waiting for the right fork. Since no one puts down the left fork, in the end none of the five can eat, and they all just keep waiting. This is a textbook deadlock in which all four conditions are met.
(3) A Simple Solution
If every fork is numbered and everyone agrees to pick up the lower-numbered fork first, no loop of waiting can form. It shows well that simply setting one order is enough to break the circular wait.
How Computers Deal with Deadlocks
Operating systems and databases choose among several methods depending on the situation.
(1) Prevention
They fix the order in which resources are used, or require programs to request all the resources they need at the very start, so that one of the four conditions never arises at all.
(2) Avoidance
Before granting a resource, the system calculates in advance whether fulfilling the request could lead to a deadlock later. The Banker’s Algorithm devised by Dijkstra is a typical example; it resembles a bank checking, before it grants a loan, whether it can fully meet the needs of all its customers to the end.
(3) Detection and Recovery
The system allows deadlocks to occur for the time being, keeps track of who is waiting for whom, and, if a loop is found, stops one program or restarts it from the beginning to untie the knot. Many databases use this approach.
(4) Ignoring It
If deadlocks occur only very rarely and do little harm, the system may choose not to bother preventing them and simply restart when one happens. Likened to an ostrich burying its head in the sand, this is called the Ostrich Algorithm.
A deadlock is a problem that arises not because any one party did something wrong, but because everyone holds on to their own share while waiting only for the others. That is why the solution, too, begins with setting an order and sometimes letting go of what you hold first.
Knowing that letting go of just one of the hands gripping each other can open the way: that is the first step of the wisdom that gets a stalled system moving again.
