Deadlock
When a resource is available to more than one process but can only be used by one of them at a time, it is necessary for a process to use a "lock" that would prevent another process from accessing the resource simultaneously. If such a resource has already been locked by another process, then it is necessary to wait until the holder of the lock has released it for another to use.
Using such locks can sometimes result in a condition called deadlock. A trivial example of this is when a process holding a lock dies, so that the lock it placed on a resource remains in place forever, thus preventing all other processes from ever accessing the resource. Another situation where deadlock can occur is if a process needs to acquire two locks on two separate resources, in order to execute an action. In this case, it is possible that two processes will acquire one lock each, and will wait forever for the other to release a lock so that they can acquire two and complete their tasks.
Formally, we may say that deadlock is a state where each member of a certain group of processes is waiting for some other member to release a lock. These processes may all be running on a single server or system, or may be running on different servers in a distributed system. A wait-for graph can be used to represent the waiting relationships between processes. In a wait-for graph, the nodes represent processes, and edges represent the wait-for relationship between them. There is an arrow from node P to node Q when process P is waiting for process Q to release a lock. Now if there is a cycle in the wait-for graph, so that two or more processors wait and upon tracing the chain of successors one is led back to the original node, we have a deadlock. None of the locks can ever be released by the waiting processes, and all processes are deadlocked.
Deadlocks are obviously highly undesirable in computer systems, and some thought is given to avoiding them. One way is to prevent deadlocks altogether--this is possible when locking can be done "atomically," i.e., when it is possible to lock every resource one needs in a single step, without there being the possibility of another process being able to lock a needed resource. Otherwise, a process may have to state in advance at the time of its creation what all the resources are that it proposes to use during its lifetime, so that deadlocks can be prevented by making sure that they are all available to it. However, this rather simplistic solution is not very practical in most cases.
A better way is to detect deadlocks, should they occur, and then try to deal with them in the best manner possible. Deadlocks can be detected by finding cycles in wait-for graphs. Once a deadlock is detected, a process must be forced to give up a lock on a resource so as to break the cycle. When the issue is with deadlocks involving processes on a single server, there can be a special software program called a lock manager, whose sole function is to keep track of locks invoked by processes, and which has authority over the locks. Such a program can either prevent a process from acquiring a lock that would cause a cycle in a wait-for graph, or else can force a process already in a cycle to give up its lock.
A second way to deal with deadlocks is to have timeouts on locks. If each lock on a resource is only considered to be good for a specified finite time, then even if there is a cycle in a wait-for graph, locks are automatically released when they time out, and the cycle is broken. This solution is however prone to many of its own problems as well--for instance, it should be noted that processes may be forced to give up their locks upon timeout even when there is no deadlock situation, thus creating a problem where none existed previously. It can also be hard for a designer, programmer, or user to know exactly what period of time is appropriate for timeout.
Deadlock detection can also be difficult if a single specialized process or server is relied upon, because there is then a single point of failure for the whole system. All information about locks must then also be always transmitted to a central location, possibly causing a significant burden on system bandwidth. Another problem is the detection of phantom deadlocks--it is possible to find cycles in wait-for graphs that don't really exist. This happens because the wait-for information is not all gathered at the same instant--thus the server may use outdated information about locks that were held earlier, along with new information, to infer that a cycle exists. In case of distributed systems, such centralized deadlock detection is thus very impractical, and is rarely used.
A distributed manner in which to detect deadlocks is the technique known as "edge chasing," where there is no single global wait-for graph constructed, but where each server has some knowledge about some of its wait-for edges. Servers that suspect they may be involved in a deadlock (such as by having been waiting for a long time for a lock to become available) send special messages called probes, which follow the wait-for edges throughout the distributed system. If a probe that was forwarded by a server is received by it again, it knows that there is a deadlock, and can communicate the information to the others involved, so that they can cooperatively resolve the problem.
This is the complete article, containing 938 words
(approx. 3 pages at 300 words per page).
