Editing Deadlock (computer science) (section)

==Individually necessary and jointly sufficient conditions for deadlock==
A deadlock situation on a resource can arise only if all of the following conditions occur simultaneously in a system:<ref>{{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=7|page=239|isbn=9788126509621|access-date=16 October 2020|archive-date=18 April 2021|archive-url=https://web.archive.org/web/20210418013932/https://books.google.com/books?id=WjvX0HmVTlMC&q=deadlock+operating+systems|url-status=live}}</ref>
# ''[[Mutual exclusion]]:'' multiple resources are not shareable; only one process at a time may use each resource.<ref>{{Cite book|title=Operating System Concepts|publisher=Wiley|year=2012|isbn=978-1-118-06333-0|pages=319}}</ref><ref>{{cite web|url=http://nob.cs.ucdavis.edu/classes/ecs150-1999-02/dl-cond.html|title=ECS 150 Spring 1999: Four Necessary and Sufficient Conditions for Deadlock|website=nob.cs.ucdavis.edu|access-date=29 April 2018|url-status=live|archive-url=https://web.archive.org/web/20180429180831/http://nob.cs.ucdavis.edu/classes/ecs150-1999-02/dl-cond.html|archive-date=29 April 2018}}</ref>
# ''Hold and wait'' or ''resource holding:'' a process is currently holding at least one resource and requesting additional resources which are being held by other processes.
# ''No [[Preemption (computing)|preemption]]:'' a resource can be released only voluntarily by the process holding it. 
# ''Circular wait:'' each process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a [[set (mathematics)|set]] of waiting processes, ''P'' = {''P''<sub>1</sub>, ''P''<sub>2</sub>, ..., ''P''<sub>''N''</sub>}, such that ''P''<sub>1</sub> is waiting for a resource held by ''P''<sub>2</sub>, ''P''<sub>2</sub> is waiting for a resource held by ''P''<sub>3</sub> and so on until ''P''<sub>''N''</sub> is waiting for a resource held by ''P''<sub>1</sub>.<ref name="os_galvin"/><ref name=embb>{{cite book |last=Shibu |first=K. |url=https://books.google.com/books?id=8hfn4gwR90MC&q=%22waiting+for+a+resource%22&pg=PA446 |publisher=Tata McGraw-Hill Education |year=2009 |title=Intro To Embedded Systems |edition=1st |page=446 |isbn=9780070145894 |access-date=16 October 2020 |archive-date=18 April 2021 |archive-url=https://web.archive.org/web/20210418013931/https://books.google.com/books?id=8hfn4gwR90MC&q=%22waiting+for+a+resource%22&pg=PA446 |url-status=live }}</ref>

These four conditions are known as the ''Coffman conditions'' from their first description in a 1971 article by [[Edward G. Coffman, Jr.]]<ref name="embb"/>

While these conditions are sufficient to produce a deadlock on single-instance resource systems, they only indicate the possibility of deadlock on systems having multiple instances of resources.<ref>{{Cite web|url=https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html|title=Operating Systems: Deadlocks|website=www.cs.uic.edu|access-date=2020-04-25|quote=If a resource category contains more than one instance then the presence of a cycle in the resource-allocation graph indicates the possibility of a deadlock, but does not guarantee one. Consider, for example, Figures 7.3 and 7.4 below:|archive-date=28 May 2020|archive-url=https://web.archive.org/web/20200528052638/https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html|url-status=live}}</ref>