Deadlock (computer science)

Both processes need resources to continue execution. P1 requires additional resource R1 and is in possession of resource R2, P2 requires additional resource R2 and is in possession of R1; neither process can continue.
Four processes (blue lines) compete for one resource (grey circle), following a right-before-left policy. A deadlock occurs when all processes lock the resource simultaneously (black lines). The deadlock can be resolved by breaking the symmetry.

In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock.[1] Deadlocks are a common problem in multiprocessing systems, parallel computing, and distributed systems, because in these contexts systems often use software or hardware locks to arbitrate shared resources and implement process synchronization.[2]

In an operating system, a deadlock occurs when a process or thread enters a waiting state because a requested system resource is held by another waiting process, which in turn is waiting for another resource held by another waiting process.[3] If a process remains indefinitely unable to change its state because resources requested by it are being used by another process that itself is waiting, then the system is said to be in a deadlock.[4]

In a communications system, deadlocks occur mainly due to loss or corruption of signals rather than contention for resources.[5]

Two processes competing for two resources in opposite order.
  1. A single process goes through.
  2. The later process has to wait.
  3. A deadlock occurs when the first process locks the first resource at the same time as the second process locks the second resource.
  4. The deadlock can be resolved by cancelling and restarting the first process.
  1. ^ Coulouris, George (2012). Distributed Systems Concepts and Design. Pearson. p. 716. ISBN 978-0-273-76059-7.
  2. ^ Padua, David (2011). Encyclopedia of Parallel Computing. Springer. p. 524. ISBN 9780387097657. Archived from the original on 18 April 2021. Retrieved 16 October 2020.
  3. ^ Falsafi, Babak; Midkiff, Samuel; Dennis, JackB; Dennis, JackB; Ghoting, Amol; Campbell, Roy H; Klausecker, Christof; Kranzlmüller, Dieter; Emer, Joel; Fossum, Tryggve; Smith, Burton; Philippe, Bernard; Sameh, Ahmed; Irigoin, François; Feautrier, Paul; Praun, Christoph von; Bocchino, Robert L.; Snir, Marc; George, Thomas; Sarin, Vivek; Jann, Joefon (2011). "Deadlocks". Encyclopedia of Parallel Computing. Boston, MA: Springer US. pp. 524–527. doi:10.1007/978-0-387-09766-4_282. ISBN 978-0-387-09765-7. S2CID 241456017. A deadlock is a condition that may happen in a system composed of multiple processes that can access shared resources. A deadlock is said to occur when two or more processes are waiting for each other to release a resource. None of the processes can make any progress.
  4. ^ Silberschatz, Abraham (2006). Operating System Principles (7th ed.). Wiley-India. p. 237. ISBN 9788126509621. Archived from the original on 25 January 2022. Retrieved 16 October 2020.
  5. ^ Schneider, G. Michael (2009). Invitation to Computer Science. Cengage Learning. p. 271. ISBN 978-0324788594. Archived from the original on 18 April 2021. Retrieved 16 October 2020.