Introduction to Operating System Deadlocks
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Deadlock can be defined formally as follows:
A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause.
Because all the processes are waiting, none of them will ever cause any of the events that could wake up any of the other members of the set, and all the processes continue to wait forever. For this model, we assume that processes have only a single thread and that there are no interrupts possible to wake up a blocked process. The no-interrupts condition is needed to prevent an otherwise deadlocked process from being awakened by, say, an alarm, and then causing events that release other processes in the set.
In most cases, the event that each process is waiting for is the release of some resource currently possessed by another member of the set. In other words, each member of the set of deadlocked processes is waiting for a resource that is owned by a deadlocked process. None of the processes can run, none of them can release any resources, and none of them can be awakened. The number of processes and the number and kind of resources possessed and requested are unimportant. This result holds for any kind of resource, including both hardware and software.
3.2.1 Conditions for Deadlock
Coffman et al. (1971) showed that four conditions must hold for there to be a deadlock:
Mutual exclusion condition. Each resource is either currently assigned to exactly one process or is available.
Hold and wait condition. Processes currently holding resources granted earlier can request new resources.
No preemption condition. Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them.
Circular wait condition. There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain.
All four of these conditions must be present for a deadlock to occur. If one of them is absent, no deadlock is possible.
It is worth noting that each condition relates to a policy that a system can have or not have. Can a given resource be assigned to more than one process at once? Can a process hold a resource and ask for another? Can resources be preempted?
Can circular waits exist? Later on we will see how deadlocks can be attacked by trying to negate some of these conditions.