Deadlock

Article Info

Contributed by
2 authors

Last updated on
2020-05-14 07:14:20

Deadlock Avoidance
Deadlock Recovery
Deadlocks in Databases
Dining Philosophers Problem
Mutex
Concurrent Computing

Article Versions

4 2020-05-14 07:14:20
2061,2060 4,2061 1

By kkris

Added missing citation in Milestone.
3 2020-05-14 07:09:58
2060,2059 3,2060 1

By arvindpdmn

Publishing. Could add milestones from recent past.
2 2020-05-14 06:38:51
2059,2054 2,2059 1

By kkris

Done with all sections.
1 2020-05-08 04:34:45
1,2054

By kkris

First version with initial questions

Chat Room

Submitting ...

You are editing an existing chat message.

A two-process deadlock. Source: Harvard 2018.

Deadlock is a problem that can occur when resources are shared among multiple processes. Suppose process P1 is waiting for a resource R1 currently being used by process P2. Meanwhile, P2 is waiting for resource R2 that's being used by P1. Neither process is able to proceed. This is an example of deadlock.

Shared resources could be files, database tables, memory, peripherals (printers, tape drives), network, etc. While we commonly talk of deadlocks among processes, it could be among threads, users, transactions, computers in a distributed system, etc.

While it's possible to design systems completely free of deadlocks, it's inefficient not to share resources or avoid multiprocessing. Instead, there are techniques to avoid, detect and recover from deadlocks.

Discussion

Could you explain deadlocks with an example?
Five philosophers (processes) shared resources (forks). Source: AIIMS 2013, slide 3.
In real life, traffic deadlocks can occur at intersections. In computer science, the classic example used to illustrate deadlock is the Dining Philosophers Problem.
Five philosophers are seated at a round dining table. There are five forks, each placed between two philosophers. Philosophers alternate between eating and thinking. To eat, a philosopher has to acquire both forks on either side of her plate but acquire them one at a time. Once a philosopher successfully gets both forks, she eats for a while, then puts down both forks and thinks for a while. Now her neighbouring philosophers can acquire one of the released forks and start eating if they already have another fork.
Deadlock can occur when each philosopher acquires one fork and waits indefinitely for another fork. Thus, no philosopher can start to eat. They'll wait forever, neither eating nor thinking.
In this analogy, philosophers are the processes. Forks are the shared resources. If resource sharing is poorly coordinated, deadlocks can occur. The system stalls. No useful work gets done.
What are some areas in computer science where deadlocks can occur?
Locks on database tables can create a deadlock. Source: Apache Software Foundation 2020.
Deadlocks can occur in database applications. For example, two transactions have locks on two different tables but also require access to the other table. This happens because operations within one transaction executes between operations of the other transaction, something that's common in concurrent systems. The problem is worse when databases are distributed.
Deadlocks can occur in multithreaded applications or multiprocessing systems with shared resources. For example, one process is reading a file and then attempts to print the file. However, another process is using the printer and suddenly wants access to the file held by the first process. Both processes are now deadlocked.
Exclusive access to a resource is typically implemented as a lock or mutex. The term mutex is common when accessing critical sections of code. The term lock is common in databases.
Which are the necessary conditions for a deadlock to arise?
There are four necessary conditions for a deadlock:
- Mutual Exclusion: A resource can't be assigned to more than one process at a time.
- Hold-and-Wait: A process that's holding a resource is also waiting for another resource.
- No Pre-emption: Process that's holding a resource can't be forced to or doesn't voluntarily give up that resource.
- Circular Wait: Each process is waiting for a resource held by another process. This condition implies the hold-and-wait condition.
How do I analyze or visualize a deadlock?
Resource allocation graphs. Source: Adapted from Bell 2006, figs. 7.2-7.3.
Resource allocation graphs help us understand or analyze deadlocks. Resources and processes are nodes of the graphs. Directed edges connect the nodes. A directed edge from a resource to a process implies that the resource is assigned to that process. A directed edge from a process to a resource implies that the process is requesting that resource.
Where there are multiple instances of a resource, a request edge terminates at the edge of the resource box. On the other hand, an assignment edge always terminates at an instance. Each instance is represented as a dot within the resource box.
In the figure we note two examples. Both have circular waits but only one of them is a deadlock. In sub-figure (b), P1 and P3 are waiting for R1 and R2 respectively. However, instances of R1 and R2 will become available once released by P2 and P4 respectively. There's no deadlock since P2 and P4 are not part of the circular wait and neither do they fulfil the hold-and-wait condition.
Which are some techniques to handle a deadlock?
Techniques for handling system deadlocks. Source: Isloor and Marsland 1980, table 1.
The four common ways to handle deadlocks are:
- Prevention: System is designed with constraints to prevent at least one of the conditions required for a deadlock.
- Avoidance: Algorithms decide at runtime to deny a resource request if subsequent requests might lead to a deadlock. Decisions may be conservative resulting in lower resource utilization.
- Detection: Periodically check for deadlocks. Frequent checks imply a performance overhead. Infrequent checks imply deadlocks are not caught soon enough. Use triggers such as a drop in CPU utilization to start a check. Perhaps check when a resource request can't be granted.
- Recovery: Take action to break one of the conditions for a deadlock. One of the processes could be terminated, called victim selection. Or the process is forced to release resources it holds.
Deadlock prevention is easier than deadlock detection. For example, in the Dining Philosophers Problem, a simple rule will prevent deadlocks: given that the forks are numbered, each philosopher must first pick the lower-numbered fork before attempting to pick the higher-numbered fork.
Which are some concepts closely related to deadlock?
Blocking calls can lead to communication deadlocks. Source: Anthony 2016, fig. 3.40.
While we often talk about processes blocked on resources, there are also communication deadlocks. In these cases, processes are waiting for messages from other processes. If two processes are waiting on each other for messages, they're in a communication deadlock. For generalization, we could consider messages as resources. Communication deadlocks are possible in distributed databases where a transaction requests some nonlocal data and is blocked until a response arrives.
Sometimes the system is not in a deadlock but work is not getting or progressing slowly. For instance, a process is unable to obtain a resource for long periods of time while other processes easily obtain the same resource, perhaps because they have a higher priority. This is called starvation.
Another problem is when processes are doing something, such as continually responding to each other or changing states, but not getting their tasks done. This is not a deadlock since processes are still running. It's called a livelock.
As a developer, what best practices should I follow to prevent deadlocks?
To prevent deadlocks, request all necessary resources together. In other words, a process is not allowed to obtain one resource and then request another. If for some reason a process holds a resource and its request for another resource is denied, it must give up the first resource. Another best practice is to impose a linear order in which resources must be requested. For example, always request file access before a printer access.
Impose a constraint that a process can hold at most one lock at a time. It's also been said, "never call other people's code while holding a lock", unless that code doesn't acquire a lock.
To share resources, prefer alternatives to mutexes or locks. The resource could be replicated. Use a higher-level pattern to synchronize operations. For instance, the pipeline pattern serializes accesses without using mutexes.
To prevent communication deadlocks, at least one process must use non-blocking IO. An alternative is to use separate threads for send and receive operations, so that the process can still send messages while blocked on the receive thread.

Milestones

1961

E. J. Braude publishes an IBM technical report titled An algorithm for the detection of system deadlocks.

1968

In his paper titled Co-operating sequential processes, Dijkstra explains mutual exclusion and the use of semaphores or status variables to solve this. He then points out that the problem of deadlock, though he uses the term deadly embrace instead. He gives an example of processes holding some memory and requesting more memory, leading to a deadlock. He proposes Banker's algorithm as a method to avoid deadlocks.

1968

Some IBM publications describe the problem of deadlocks observed in ASP/OS/360. For example, when spooling disk space is full with input and output records, an input process and an output process can both be waiting for more disk space. Deadlocks could be avoided by rejecting new jobs once spool utilization reaches 80%; or cancelling a blocked job after a defined timeout.

Jun
1971

Deadlock is inevitable once system enters region D. Source: Coffman et al. 1971, fig. 2.

Coffman et al. introduce the four necessary conditions for a deadlock. In time, these are called Coffman conditions. They also present sequence and state diagrams to explain deadlocks.

Jan
1974

Within the ARPA network (precursor to the Internet), deadlocks are being observed as resources are shared over the network. Robert Chen notes that the deadlock problem in networks requires a different approach from deadlocks on resources managed by a single operating system. In a message-switched system, a message travels through many store-and-forward buffers. A buffer can't be released until the message is transferred to the next buffer along the route. Deadlocks are more easily realizable (reachable from an empty system state) if routes are fixed and less realizable if alternatives routes (free buffers) can be found.

Dec
1987

A wait-for-graph model for distributed databases. Source: Knapp 1987, fig. 1.

Edgar Knapp writes about deadlocks in distributed databases. He presents different models of deadlocks and various deadlock detection algorithms. He models resource requests using what he calls a wait-for-graph (WFG). In the figure, the circles are nodes. Node t11 has two outstanding requests to t21 and t31. The cycle t11-t31-t33-t43-t41-t11 is in fact a deadlock. Mukesh Singhal extends this work in November 1989.

References

Article Stats

1671

Words

Authors

Edits

Chats

Likes

7210

Hits

Cite As

Devopedia. 2020. "Deadlock." Version 4, May 14. Accessed 2023-11-12. https://devopedia.org/deadlock

Contributed by
2 authors

Last updated on
2020-05-14 07:14:20

embedded networking contention shared resource

Deadlock Avoidance
Deadlock Recovery
Deadlocks in Databases
Dining Philosophers Problem
Mutex
Concurrent Computing

Deadlock

Discussion

Milestones

References

Further Reading

Article Stats

Cite As

See Also

Deadlock

Discussion

Milestones

References

Further Reading

Article Stats

Author-wise Stats for Article Edits

Cite As

See Also

Login