Deadlock

A two-process deadlock. Source: Harvard 2018.
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.
    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.
    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. 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.
    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.
    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
Deadlock due to improper memory allocation. Source: Dijkstra 1968, pp. 74.
Deadlock due to improper memory allocation. Source: Dijkstra 1968, pp. 74.

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.
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.
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

  1. AIIMS. 2013. "Dining Philosophers and Uniprocessor Scheduling." Chapter 9 in: Operating Systems, Lecture 16, All India Institute of Medical Sciences. Accessed 2020-05-12.
  2. Anthony, Richard John. 2016. "Systems Programming: Designing and Developing Distributed Applications." Morgan Kaufmann, Elsevier, Inc. Accessed 2020-05-12.
  3. Apache Software Foundation. 2020. "Deadlocks." Documentation, Apache Derby 10.0, Apache Software Foundation, May 8. Accessed 2020-05-12.
  4. Bell, John T. 2006. "Deadlocks." CS 385 Course Notes: Operating Systems, Dept. of CS, Univ. of Illinois Chicago. Updated 2013. Accessed 2020-05-12.
  5. Bernstein, Philip, and Eric Newcomer. 2009. "Principles of Transaction Processing." Second Edition, Morgan Kaufmann, Elsevier, Inc. Accessed 2020-05-14.
  6. Campione, Mary and Kathy Walrath. 1997. "Deadlock and the Dining Philosophers." In: The Java Tutorial: Object-Oriented Programming for the Internet, online version of the book, Addison-Wesley, July 8. Accessed 2020-05-12.
  7. Chen, Robert C. 1974. "Deadlock prevention in message switched networks." ACM '74: Proceedings of the 1974 annual conference, vol. 1, pp. 306-310, January. Accessed 2020-05-12.
  8. Coffman, E.G. Jr., M.J. Elphick, and A. Shoshani. 1971. "System Deadlocks." Computing Surveys, vol. 3, no. 2, pp. 67-78, June. Accessed 2020-05-12.
  9. Dijkstra, E. W. 1968. "Co-operating sequential processes." In Programming languages: NATO Advanced Study Institute : lectures given at a three weeks Summer School held in Villard-le-Lans, 1966, ed. by F. Genuys, pp.43-112, London: Academic Press Inc. Accessed 2020-05-12.
  10. Goodwin, David. 2013. "Operating Systems: Lecture #7: Deadlock Resolution." Dept. of Comp Sci and Tech, Univ. of Bedfordshire, March 11. Accessed 2020-05-12.
  11. Harvard. 2018. "Synchronization 5: Deadlock and Server Programming." CS 61: Systems Programming and Machine Organization, Harvard University. Accessed 2020-05-12.
  12. Holt, Richard C. 1971. "On Deadlock In Computer Systems." Technical Report CSRG-6, Computer Systems Research Group, University of Toronto. Accessed 2020-05-12.
  13. Isloor, S. S., and T. A. Marsland. 1980. "The Deadlock Problem: An Overview." Computer, IEEE Computer Society Press, vol. 13, no. 9, pp. 58-78, September. doi:10.1109/MC.1980.1653786. Accessed 2020-05-12.
  14. Knapp, Edgar. 1987. "Deadlock Detection in Distributed Databases." ACM Computing Surveys, vol. 19, no. 4, pp. 303-328, December. Accessed 2020-05-12.
  15. McCool, Michael, Arch D. Robison, and James Reinders. 2012. "Structured Parallel Programming: Patterns for Efficient Computation." Morgan Kaufmann, Elsevier, Inc. Accessed 2020-05-12.
  16. Oracle Docs. 2020. "Starvation and Livelock." The Java™ Tutorials, JDK 8, Oracle. Accessed 2020-05-12.
  17. RPI. 2004. "Deadlock." CSCI.4210 Operating Systems, Rensselaer Polytechnic Institute. Accessed 2020-05-12.
  18. Singhal, Mukesh. 1989. "Deadlock Detection in Distributed Systems." Computer, IEEE, vol. 22, no. 11, pp. 37-48, November. Accessed 2020-05-12.
  19. Wikipedia. 2020. "Deadlock." Wikipedia, April 25. Accessed 2020-05-12.

Further Reading

  1. Bell, John T. 2006. "Deadlocks." CS 385 Course Notes: Operating Systems, Dept. of CS, Univ. of Illinois Chicago. Updated 2013. Accessed 2020-05-12.
  2. Coffman, E.G. Jr., M.J. Elphick, and A. Shoshani. 1971. "System Deadlocks." Computing Surveys, vol. 3, no. 2, pp. 67-78, June. Accessed 2020-05-12.
  3. Singhal, Mukesh. 1989. "Deadlock Detection in Distributed Systems." Computer, IEEE, vol. 22, no. 11, pp. 37-48, November. Accessed 2020-05-12.
  4. Isloor, S. S., and T. A. Marsland. 1980. "The Deadlock Problem: An Overview." Computer, IEEE Computer Society Press, vol. 13, no. 9, pp. 58-78, September. doi:10.1109/MC.1980.1653786. Accessed 2020-05-12.
  5. Chahar, Pooja, and Surjeet Dalal. 2013. "Deadlock Resolution Techniques: An Overview." International Journal of Scientific and Research Publications, vol. 3, no. 7, July. Accessed 2020-05-12.
  6. Jain, Kamal, Mohammad Taghi Hajiaghayi, and Kunal Talwar. 2005. "The Generalized Deadlock Resolution Problem." In: Caires L., Italiano G.F., Monteiro L., Palamidessi C., Yung M. (eds), Automata, Languages and Programming, ICALP 2005, Lecture Notes in Computer Science, vol. 3580, pp. 853-865, Springer, Berlin, Heidelberg. Accessed 2020-05-12.

Article Stats

Author-wise Stats for Article Edits

Author
No. of Edits
No. of Chats
DevCoins
3
0
1729
1
0
15
1671
Words
5
Likes
9031
Hits

Cite As

Devopedia. 2020. "Deadlock." Version 4, May 14. Accessed 2024-06-25. https://devopedia.org/deadlock
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