Editing Deadlock (computer science) (section)

{{short description|State in which members are blocking each other}}
{{Use dmy dates|date=April 2021}}

[[File:Process deadlock.svg|thumb|right|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.]]
[[File:Deadlock at a four-way-stop.gif|thumbnail|right|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 (computer science)|lock]].<ref name=coulouris>{{cite book|last=Coulouris|first=George|publisher=Pearson|year=2012|title=Distributed Systems Concepts and Design|page=716|isbn=978-0-273-76059-7}}</ref> Deadlocks are a common problem in [[multiprocessing]] systems, [[parallel computing]], and [[Distributed computing|distributed systems]], because in these contexts systems often use software or hardware locks to arbitrate shared resources and implement [[Synchronization (computer science)|process synchronization]].<ref name=para_enclo>{{cite book |last=Padua |first=David |url=https://books.google.com/books?id=Hm6LaufVKFEC&q=deadlock&pg=PA524 |publisher=Springer |year=2011 |title=Encyclopedia of Parallel Computing |page=524 |isbn=9780387097657 |access-date=16 October 2020 |archive-date=18 April 2021 |archive-url=https://web.archive.org/web/20210418033928/https://books.google.com/books?id=Hm6LaufVKFEC&q=deadlock&pg=PA524 |url-status=live }}</ref>

In an [[operating system]], a deadlock occurs when a [[process (computing)|process]] or [[thread (computing)|thread]] enters a waiting [[Process state|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.<ref name="Falsafi Midkiff Dennis Dennis 2011 pp. 524–527">{{cite book | last1=Falsafi | first1=Babak | last2=Midkiff | first2=Samuel | last3=Dennis | first3=JackB | last4=Dennis | first4=JackB | last5=Ghoting | first5=Amol | last6=Campbell | first6=Roy H | last7=Klausecker | first7=Christof | last8=Kranzlmüller | first8=Dieter | last9=Emer | first9=Joel | last10=Fossum | first10=Tryggve | last11=Smith | first11=Burton | last12=Philippe | first12=Bernard | last13=Sameh | first13=Ahmed | last14=Irigoin | first14=François | last15=Feautrier | first15=Paul | last16=Praun | first16=Christoph von | last17=Bocchino | first17=Robert L. | last18=Snir | first18=Marc | last19=George | first19=Thomas | last20=Sarin | first20=Vivek | last21=Jann | first21=Joefon | title=Encyclopedia of Parallel Computing | chapter=Deadlocks | publisher=Springer US | publication-place=Boston, MA | year=2011 | doi=10.1007/978-0-387-09766-4_282 | pages=524–527 | isbn=978-0-387-09765-7 | s2cid=241456017 | quote=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.}}</ref> 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.<ref name="os_galvin">{{cite book|last=Silberschatz|first=Abraham|url=https://books.google.com/books?id=WjvX0HmVTlMC&q=deadlock+operating+systems|publisher=Wiley-India|year=2006|title=Operating System Principles|edition=7th|page=237|isbn=9788126509621|access-date=16 October 2020|archive-date=25 January 2022|archive-url=https://web.archive.org/web/20220125085137/https://books.google.com/books?id=WjvX0HmVTlMC&q=deadlock+operating+systems|url-status=live}}</ref>

In a [[communications system]], deadlocks occur mainly due to loss or corruption of signals rather than contention for resources.<ref name=invi_comp>{{cite book |last=Schneider |first=G. Michael |url=https://books.google.com/books?id=gQK0pJONyhgC&q=deadlock+signal+lost&pg=PA271 |publisher=Cengage Learning |year=2009 |title=Invitation to Computer Science |page=271 |isbn=978-0324788594 |access-date=16 October 2020 |archive-date=18 April 2021 |archive-url=https://web.archive.org/web/20210418025125/https://books.google.com/books?id=gQK0pJONyhgC&q=deadlock+signal+lost&pg=PA271 |url-status=live }}</ref>

[[File:Two processes, two resources.gif|thumbnail|Two processes competing for two resources in opposite order.{{ordered list|style=margin-top:0.5em|list_style_type=upper-alpha
| A single process goes through.
| The later process has to wait.
| A deadlock occurs when the first process locks the first resource at the same time as the second process locks the second resource.
| The deadlock can be resolved by cancelling and restarting the first process.}}]]