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.