A situation in which several entities (e.g. processes) wait in a circular fashion for each other. Each entity waits for a resource held by another entity which will never be freed because that entity again waits for a resource held by yet another entity until the loop is closed. Instead for waiting on resources the entities could also wait for actions of another entity. You can imagine it as 4 cars reaching at the same time an intersection with a "give way to right"-rule.

More technically there are four preconditions for a deadlock to occur:

  1. Mutual Exclusion: Each resource can only be used by one entity. (More generally: by a fixed number of entities. If a resource can be used by e.g. three entities at the same time, it can still be modeled with mutual exclusion by splitting it up into three resources .)

  2. Wait and Hold: Entities which wait for a resource hold on to the resources they have already allocated.

  3. No preemption: None of the allocated resources can be withdrawn from an entity by another.

  4. Circular wait: The waiting graph forms a circle.

There are three things one can do against deadlocks: First, design your system so that at least one of the above preconditions does not hold. This is called deadlock prevention. If no deadlock prevention is there but the resource allocation algorithm uses a strategy to hand out resources that always keeps the system in a deadlock-safe state, it is called deadlock avoidance. The algorithm every computer scientist has to learn is Dijkstra's Banker's Algorithm. If neither of the two is there but the system is monitoring its entities and e.g. kills one of those in a deadlock circle, it is called deadlock detection (and resolution). Each of these solutions becomes more difficult in a distributed system.

DEADBEEF = D = deadly embrace

deadlock n.

1. [techspeak] A situation wherein two or more processes are unable to proceed because each is waiting for one of the others to do something. A common example is a program communicating to a server, which may find itself waiting for output from the server before sending anything more to it, while the server is similarly waiting for more input from the controlling program before outputting anything. (It is reported that this particular flavor of deadlock is sometimes called a `starvation deadlock', though the term `starvation' is more properly used for situations where a program can never run simply because it never gets high enough priority. Another common flavor is `constipation', in which each process is trying to send stuff to the other but all buffers are full because nobody is reading anything.) See deadly embrace. 2. Also used of deadlock-like interactions between humans, as when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they always move the same way at the same time.

--The Jargon File version 4.3.1, ed. ESR, autonoded by rescdsk.

The following is an example of how deadlock can occur (the original was nuked, possibly due to a somewhat inappropriate title; this is a repost under a different title, which I hope will prove more educational). Think of this as a nontechnical description of deadlock. I do mention computers, but they feature only as part of the deadlock. The deadlocked system is carbon-silicon based, not silicon based.

I managed to become deadlocked with my computer! This occured after I had installed a new version of my printing system (apsfilter) on my home Linux box. The new daemon was set up to detect special file types sent to the printer, and run the appropriate conversions to make it something the printer could understand.. Thus, I can send PostScript to my poor little old HP DeskJet 690C, and apsfilter intercepts it and runs GhostScript to convert it to HP PCLese, before sending it on and causing the printer to spit out pages.

My old apsfilter setup used a temporary file for these conversions, and ran the entire conversion process before starting to print anything. Unknown to me, the new system would spool everything directly on to a pipe: each page hits the printer as soon as it's ready.

I was in a bit of a hurry as I ran "lpr foo.ps" to print out my PostScript file. I hadn't switched the printer on yet. My reasoning was that my time would be better spent doing other things, because meanwhile the spooler was converting the file for me, and nothing would come out if I did switch on the printer. Since I could tell (by the load on my computer suddenly dropping) that the conversion process was done, I could continue doing other stuff until that happened. Except nothing happened. Eventually, I finished everything else I had to do, and the computer still hadn't even started working on the conversion.

After another 5 minutes, I finally got it. Since the new system was spooling on to a pipe, it wouldn't run if the pipe was blocked. Since the printer was off, the pipe was blocked. In other words, the computer was waiting for me to turn the printer ON, before it would start converting. Meanwhile, I was waiting for the computer to finish converting, after which I'd turn the printer ON.

DEADLOCK! Neither of us could progress. Luckily, my advanced deadlock detection algorithms kicked in. Or I would still be sitting there today, blocked doing an infinite amount of nothing.

A deadlock is a problem that can occur to two different processes

Like playing solitaire and hearts at the same time?

While it's not exactly like playing solitaire and hearts at the same time. It happens when two different tasks the computer is running try to use the same device, like a scanner, CD-Rom drive, tape drive, plotter, etc. A process needs to maintain a constant "connection" with the device it needs to use. It uses a bunch of mutual exlcusion switches to do this. Deadlocks can also occur over networks, with different networked devices. Your printer is cool because of a program referred to as a daemon. That's just a program that sits around and interfaces with the printer so you don't have to worry about your printer causing a deadlock.

A deadlocked system is a halted system. Your computer is on, but the hamsters are not running in their wheels would be the best way to paraphrase this. Like the two stubborn green guys Dr. Seuss talked about the two different process butt heads and just sit there while a highway is built around them. This can occur when one process has one resource and wants another, while another process has the another resource and wants the first one. Yeah, it really is that messy. It falls upon the operating system to notice these problems and fix them so that the system can keep on running fine.

One way to notice if either the system is in a deadlock or could be real soon is to draw out the processes and resources in a graph. Draw out the resources in squares and the processes in circles. If a process is holding a resource, draw an arrow to it from the resource. Be sure to mark the point only at one end ( -->|do this] , not this). Formally, "The resource has previously been requested by, granted to, and is currently held by that process."

Now, if a process is waiting for a resource, draw an arrow in a similar manner, but put the pointy end towards the resource. You should end up with something like this, depending on the number of processes. This would be a hard process to do by hand for large systems, of course.

Processes:  A, B, C, D...    In bad ascii boxagons
Resources:  1, 2, 3, 4...    In bad ascii hexagons


                        /  \
		     | 1 |
	             _ \ /
                       |    \                 		          
                     /        \  
                   /            \  
                 /               _|
            |---|                |---|                / \
            | A |                | B |-------------> | 3 |
            |___|                |___|                \ / \ 
                \                                          \
                  \                                         _| 
                    \                                       |---|
                     _|                                     | C | 
                       / \                                  |___|
                      | 2 |----------------->|---|            |
                       \ /                   | D |            |
                                             |___|\           |
                                                    \         |
                                                      \      \|/
                                                        \    / \
                                                         -->| 4 |
                                                             \ /
                              

What this graph clearly shows is a cycle. Each process is waiting for a resource, and each resource is possessed by a different process. There are varying approaches to how to solve a deadlock once it has occured. I'm sure everyone who's touched a windows machine has used the "task manager" to kill non-responsive programs. But mass program slaughter is only one option. That usually occurs because of the Ostrich Algorithm, which pretty much ignores the deadlock and hope the deadlock elves come waddling down the street singing Come On Eileen. This, obviously, was not going to cut it.

What cut like a ginsu was using a pair of matrices to keep track of the processes on the system and how many resources they need, and the total resources availible to the system. However a chainsaw was around the corner. Finally materializing were two matrices with two one line keys above each, keeping track of the system's resources and requests.

     The existing resources (total)                The available resources
     E = | 5, 3, 6, 2|                             A = | 2, 1, 5, 0|

      Currently Allocated                          Requesting for resources
        |------------|                                 |------------|
     p1 | 1, 0, 0, 1 |                              p1 | 0, 0, 3, 0 |
     p2 | 1, 0, 1, 1 |                              p2 | 0, 2, 0, 0 |
     p3 | 0, 2, 0, 0 |                              p3 | 1, 0, 1, 1 |
     p4 | 1, 0, 0, 0 |                              p4 | 0, 0, 3, 0 |
        |------------|                                 |------------|

The matrices above show both what resources the processes require for finishing and which resources they already have. Through both of these matrices we can see that this system is not in deadlock. p1 has plenty of resources for p1 to finish. With p1 finished, and it's resources reallocated, p3 can finish, followed by p2 and p4.

     The existing resources (total)                The available resources
     E = | 5, 3, 6, 2|                             A = | 2, 1, 5, 0|

      Currently Allocated                          Requesting for resources
        |------------|                                 |------------|
     p1 | 1, 0, 0, 1 |                              p1 | 3, 0, 3, 1 |
     p2 | 1, 0, 1, 1 |                              p2 | 0, 2, 0, 0 |
     p3 | 0, 2, 0, 0 |                              p3 | 1, 0, 1, 1 |
     p4 | 1, 0, 0, 0 |                              p4 | 0, 2, 3, 0 |
        |------------|                                 |------------|

This system is completely fuX0r3d. These four resource munching processes are too greedy and deadlock occurred. Normally one would not see four intensive processes like this, but several smaller, less resourceful ones. Each column represents an individual resource, and the number represents the number of this resource available.

So we know we're locked, how do we escape?

One method is to make like a Final Fantasy game and set up save points where your processes progress can be recorded and resumed from later. While this method is effective in getting your computer out of a frozen state, it's still possible it can happen again. Edsger W. Dijkstra composed the Banker's Algorithm to solve this problem. This algorithm is pretty similar to the dual matrices above, but is used for only one resource, when generalized two all resources it looks exactly like the matrices above. For one resource, the matrix has three columns, process, resources held, and the maximum amount of resources needed by the process. This allowed the manager to know how many resources a process is going to need and to provide for that resources when it needs it.

A deadlock is something to be avoided, as if akin to the Noid. Deadlocks occur because the system does not allow for pre-emption, meaning a process can't come in and steal a resource away from another process. That would garble the system and could cause much anger from the user (print 500 pages only for it to get stopped in the middle and have something else print out). Another thought came by, one of having processes release a resource they wanted to use another. However, this too had it's flaws, for similar reasons as the pre-emption.

The best way to keep track of Deadlocks is to pay attention to the safe and unsafe states of a system and attempt to prevent the unsafe states as much as possible. This, of course, can sometime be easier said than done and your mileage may vary. A cycle on the graph denotes a Deadlock. A good resource manager, and a copious amount of resources are the best bets for preventing deadlocks.


Modern Operating Systems, second edition, Andrew S. Tanenbaum. Prentice Hall, 2001.


Ph34r my l33t ascii!

Dead"lock` (?), n.

1.

A lock which is not self-latching, but requires a key to throw the bolt forward.

2.

A counteraction of things, which produces an entire stoppage; a complete obstruction of action.

Things are at a deadlock. London Times.

The Board is much more likely to be at a deadlock of two to two. The Century.

 

© Webster 1913.

Log in or register to write something here or to contact authors.