Editing Deadlock (computer science) (section)

== Livelock ==
{{redirect|Livelock|the video game|Livelock (video game)}}
A ''livelock'' is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing.

The term was coined by [[Edward A. Ashcroft]] in a 1975 paper<ref>{{cite journal|title=Proving assertions about parallel programs|journal=Journal of Computer and System Sciences|volume=10|pages=110–135|doi=10.1016/S0022-0000(75)80018-3|year=1975|last1=Ashcroft|first1=E.A.|doi-access=free}}</ref> in connection with an examination of airline booking systems.<ref>{{cite book|chapter=On the absence of livelocks in parallel programs|doi=10.1007/BFb0022469|title=Semantics of Concurrent Computation|volume=70|pages=172–190|series=Lecture Notes in Computer Science|year=1979|last1=Kwong|first1=Y. S.|isbn=3-540-09511-X}}</ref> Livelock is a special case of [[resource starvation]]; the general definition only states that a specific process is not progressing.<ref>{{cite web|url=http://citeseer.ist.psu.edu/anderson01sharedmemory.html|first=James H.|last=Anderson|author1-link=James H. Anderson (computer scientist)|author2=Yong-jik Kim|title=Shared-memory mutual exclusion: Major research trends since 1986|year=2001|url-status=live|archive-url=https://web.archive.org/web/20060525013335/http://citeseer.ist.psu.edu/anderson01sharedmemory.html|archive-date=25 May 2006}}</ref>

Livelock is a risk with some [[algorithm]]s that detect and recover from ''deadlock''. If more than one process takes action, the [[deadlock detection algorithm]] can be repeatedly triggered. This can be avoided by ensuring that only one process (chosen arbitrarily or by priority) takes action.<ref>{{cite journal|doi=10.1145/850752.850753 |title=The Deadlock problem: a classifying bibliography | first = Dieter |last = Zöbel | journal = ACM SIGOPS Operating Systems Review |volume=17 |issue=4 |date=October 1983 |issn=0163-5980 |pages = 6–15|s2cid=38901737 |doi-access=free }}</ref>