Talk:Deadlock

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
 

Deadly embrace?[edit]

Shouldn't this article have the term "Deadly Embrace" somewhere in it as an alternate term for Deadlock? --grr 23:12, 12 December 2006 (UTC)

...No? Lx45803 (talk) 04:42, 28 January 2009 (UTC)

Defiantly not 196.210.142.17 (talk) —Preceding undated comment added 19:54, 7 October 2010 (UTC).

Poor examples[edit]

An example of a deadlock occurs frequently in database products. Client applications using the database may require exclusive access to a given table, and in order to gain exclusive access they ask for a lock. If two client applications both attempt to lock the same table at the same time, neither will receive it, there is no general way to decide who to give the lock to. In this case both clients will wait for the lock forever.

Um, no. Just give it to one of the clients which will run and finish, then the other one gets a chance to run. I'm giong to replace this with a better example MatthewWilcox 12:55, 15 Dec 2004 (UTC)

Agreed; deadlock is impossible with only one resource, which is what that text describes. I'd guess the original writer had encountered a deadlock with row-level locking and misunderstood. PostgreSQL's documentation describes this.[1] I'd say this is a better example than two tables, because it's best to avoid contributing to the perception that databases use table-level locks internally. Specifically, by your text here:

(But this particular type of deadlock is easily prevented, e.g., by using an all-or-none resource allocation algorithm.)

are you proposing something like LOCK table_1, table_2 IN EXCLUSIVE MODE; at the beginning of the transaction? That severely limits concurrency. I'd say it's better to use a per-row example like the PostgreSQL one and suggest resolving it application-side in one of two ways:

  • using a consistent ordering
  • catch the "would deadlock" exception generated by the database server and replay the transaction

- Slamb 20:37, 20 August 2006 (UTC)

Diagree w/ Matthew & Slamb; In practice, most database systems can deadlock on what seems to be a single resource, and independent of granularity (table, row, etc.) This is due to the use of a reader-writer lock, used to improve concurrency. Unfortunatly reader-writer locks can introduce a deadlock condition sometimes called a conversion deadlock, where two threads both obtain a read lock on the resource, and then attempt to convert it to a write lock. In my experience, at least for databases, this form of deadlock is far more common in practice than a "classic" deadlock involving two seperate resources. I can come up with an example... --Burt Harris 15:42, 24 August 2006 (UTC)

Burt: I'm sold; I think your explanation belongs in the article. In hindsight, I think I've only avoided getting bitten by this because,

  • in general, I use fancy MVCC databases in the read committed isolation level. I'm cautious about changing things based on a non-repeatable read, so if I do a select then update, I always do "select ... for update". As a side effect, I never upgrade the lock.
  • the homegrown database I use at work doesn't even allow upgrading a lock from shared to exclusive. I should ask if this is why.

Maybe this should go in a new section? Even as common as you say it is, it's a little more complex and so maybe shouldn't be the first example. -Slamb 03:08, 25 August 2006 (UTC)

Link to Henry Wong[edit]

In the "External links" section, the link to Henry Wong, author of "Advanced Synchronization in Java Threads", leads to the wikipedia page of a fictional character from the Digimon series.

Definition[edit]

"In the computing world deadlock refers to a specific problem when two or more processes are waiting on the same shared resource."

Is this correct? AFAIK, two or more processes are not waiting on the same resource in a deadlock. If I'm correct, what would be the correct definition be worded like?

LjL 00:19, 19 Apr 2005 (UTC)

Yes you are right. I tried to rephrase it. Matteo
Thanks. Sounds quite OK now, although it might not be 100% correct in the case of more than two processes... but I doubt there is a short definition for that case. Hmm... what about stating the definition for two processes only, and then mentioning that it has to be extended to treat cases when more are involved? LjL 10:50, 19 Apr 2005 (UTC)
What do you say if we put a link to the section with the Coffman conditions? Something like: In the computing world deadlock refers to a state of the system where two or more processes are blocked waiting for a resource (see Necessary conditions for a detailed description). This is not perfect but maybe better that the previous one. What do you say? Matteo 11:04, 2005 Apr 19 (UTC)
No, I like your current definition better. I'd mix the two like this, "... when two processes are each waiting for the other to release a resource, or more than two processes are waiting for resources in a circular chain (see Necessary conditions)". Besides, the Coffman conditions are only necessary, not sufficient, and so do not make a definition, do they? LjL 11:54, 19 Apr 2005 (UTC)
Nice! I changed it ... Matteo 12:21, 2005 Apr 19 (UTC)

Article naming[edit]

Seems to me the term "deadlock" doesn't apply primarily to computing. The more general term 'deadlock' meaning any stalemate situation is probably more deserving of the article title, as long as it doesn't end up being just a dicdef. The other meaning of deadlock - a type of mechanical lock mechanism - should also go somewhere, I think. Should this be moved to Deadlock (computing) leaving the main title for a disambiguation page? Graham 11:52, 7 October 2005 (UTC)

Decidability of Deadlock Detection[edit]

The article said:

Instead deadlock detection and clean up is used by employing an algorithm that tracks the circular waiting and kills one or more of the processes such that the deadlock is removed.

This problem is undecidable in general, because the halting problem can be rephrased as a deadlock scenario.

This is not true, or at least confusing. Detecting a deadlock that has already happened is, given sufficient information about actors (threads, clients etc.) and the resources they have locked and requested in a blocking manner, simple. Telling whether a given program will or may cause deadlocks, on the other hand, is very hard, and in general undecidable.

Or, if that explanation doesn't suffice: Imagine a program that controls train traffic. When it contains a bad bug, trains may crash into one another. When a train wreck happens in this way, it's easy to detect: Just follow the smoke and the trail of ambulances. ;-) However, telling whether execution of the program may lead to a train crash before a train crash actually occurred is difficult (undecidable) in the general case. What people usually do in order to be sure is to write the program in such a way that its correctness (impossibility of train crashes) can be proven. This of course requires adherence to a subset of possible programs, since not all correct programs can be proven to be correct (-> Gödel's incompleteness theorem). Aragorn2 18:36, 16 March 2006 (UTC)

Another method for preventing deadlocks?[edit]

I'm not really an expert on concurrency and I've only skimmed over the current article, but it seems to me as though one of the methods the Linux kernel uses for avoiding deadlocks is missing from the article. My understanding is that for fine-grained locking, the Linux kernel requires that locks on resources always be obtained in a fixed order. For example, assuming that locks with a lower order need to be locked first, this means that a thread with a lock on resource 5 is not allowed to request a lock on resource 3 without relinquishing its lock on resource 5. Perhaps someone with a greater knowledge and better understanding of concurrency would like to correct me about this or add it to the article? - James Foster 14:43, 2 May 2006 (UTC)

The article (as of today's viewing) does mention this approach under "Deadlock prevention":

The circular wait condition: A process ranking may be imposed such that the highest ranking process will always obtain its resources, by preemption if necessary. A hierarchy may be used to determine a partial ordering of resources; where no obvious hierarchy exists, even the memory address of resources has been used to determine ordering.

though I say it's worthy of expansion. Specifically with regard to the Linux kernel, LWN has a good article.[2] I'm also not sure why this text says "partial ordering" - to avoid all deadlock in this way, there must be, for all sets of simultaneously-held locks, a total ordering. You can't just know class A locks come before class B locks; you need to know that instance A1 comes before instance A2. (The writer might have been trying to say that if locks A and B will never be held at the same time, you don't need to order them. But that's a different statement.) If I find some time, I'll try to dig up some papers on CiteSeer to use as references.

Also, I don't think the preemption sentence really belongs here. Giving priority to one process is a strategy to take after detection of circular wait requests, not prevention of them. And it certainly needs more explanation - if process A's already-held locks are released, there needs to be a strategy for rolling back the work it's already done, waiting for the other process to finish, then trying to replay process A's work later. -Slamb 21:13, 20 August 2006 (UTC)

You can't just know class A locks come before class B locks -- and why not?
Imagine we extend the pencil-and-ruler example in the article to a bunch of people trying to draw straight lines. As long as everyone agrees to grab class A locks (the rulers) before grabbing a class B locks (the pencils), then there will be no deadlock, right? The people do *not* need to know that instance "red pencil" comes before instance "black pencil", right? --70.189.73.224 20:15, 27 September 2006 (UTC)
The people do need to know "red pencil" comes before "black pencil" if they will be grabbing both specifically - "I need the red pencil", then "I need the black pencil" rather than "I need a pencil", then "I need another pencil". The former is the situation the LWN article is describing with its "locks that are allocated dynamically". The latter is the situation described in, say, the Banker's algorithm. (I think the LWN article writer would say that each resource type in the Banker's algorithm is a statically-allocated N-ary semaphore, and each lock type in Linux is N dynamically-allocated binary semaphores.) -Slamb 22:09, 27 September 2006 (UTC)

Merge?[edit]

Should this article be merged with the preemption (computing) and circular wait articles? (There is no hold-and-wait page, and the mutual_exclusion page probably contains enough information to be seperated.) Another possibility would be to make a seperate page for Coffman conditions and merge preemption, circular wait and mutual exclusion with that. MagiMaster 08:47, 10 July 2006 (UTC)

  • I agree for circular wait but not for preemption. Preemption is a general concept that should be defined on his own without necessarily speaking about deadlocks. Matteo 09:19, 10 July 2006 (UTC)
  • Perfect. Circular wait(one of the methods of deadlock prevention) is quite relevent. Definitely deserves to be merged with this article.
  • I'm OK with merging this with circular wait, but as Matteo has already stated, preemption isn't exlusively linked to deadclocks and most people would expect it to have an article of its own when searching for it. Denis Kasak 16:34, 15 August 2006 (UTC)
  • I'm with Matteo; agree on circular wait, since it's only ever discussed as a precondition to deadlock, but not preemption (computing). The latter is a topic in its own right, relevant to lockless systems. The usage of "preemption" here is talking about lock-breaking and rollback, which is a more complex, deadlock-specific subject. Slamb 21:20, 20 August 2006 (UTC)
  • Yes, I agree as well on both points. Circular wait does not belong as an independent topic. JWHPryor 14:45, 26 August 2006 (UTC)
  • Circular wait should be merged, no question. Preemption, though, should remain as is. « SCHLAGWERKTalk to me! 17:59, 10 November 2006 (UTC)
  • Agree--Yxen 22:32, 22 November 2006 (UTC)

Organization[edit]

I'm quite confused by the following sections, which seem to be primarily discussing:

  • Deadlock avoidance - resource manager detecting potential deadlock and raising error
  • Deadlock prevention - resource consumer avoiding deadlock in the first place
  • Deadlock detection - (1) resource manager/consumer post-detection rollback process, (2) static verification that a consumer is deadlock-free

I'd like to explicitly mention that there are often two players involved - the manager (perhaps a kernel or RDBMS) and the consumer (application), and then break them apart into:

  • Deadlock avoidance - consumer avoiding deadlock in the first place, passing mention of static verification
  • Deadlock detection - manager detecting deadlock as it happens
  • Deadlock recovery - consumer/manager rollback process

and keep the roles clear in the writing of each section. Comments? Agree/disagree? -Slamb 21:37, 20 August 2006 (UTC)

Hmm. This paper talks about the "prevention" vs. "avoidance" distinction and argues that it's erroneous. Apparently algorithms that require each transaction to start by declaring all the resources it might later acquire (like the Banker's algorithm) are typically called "avoidance"...except for some reason resource preallocation. Other algorithms (like a static ordering, which they argue that doesn't actually work with semaphores) are called "prevention".

What actually seems to set apart the prevention schemes from the avoidance schemes is that the prevention ones involve just the consumer; the avoidance ones involve the consumer giving the manager information it needs to consider "safe states" when scheduling resource acquisitions. I don't (yet) see any material that really gives a good definition of the two terms, though. Unfortunately, I don't have easy access to a lot of the books these papers reference. -Slamb 02:08, 28 August 2006 (UTC)

Neglected deadlock situations[edit]

I think many developers have the misconception that "resource" = "mutex", and that's not necessarily true. I'd like to add counterexamples to the page. I'm trying to avoid original research, though. Are there good citable examples around?

Here's a situation that came up in my own work:

  1. My Python graphing program writes to a gnuplot control pipe.
  2. gnuplot writes a bunch of stupid warnings to stderr, a pipe back to my Python graphing program.
  3. gnuplot blocks at PIPEBUF bytes, waiting for my program to consume them.
  4. My program blocks at PIPEBUF bytes, waiting for gnuplot to consume them.
  5. Deadlock.

I think it's a good counterexample. No locks involved and furthermore, the program that acquires a release isn't even the one expected to release it! The solution is also interesting - I essentially removed one of the shared resources by making gnuplot write to a temporary file, which my program examines after the fact.

Another neglected situation is a deadlock where a single context of execution has both resources and is waiting for itself. This can sometimes happen in asynchronous designs. I can come up with an example of this, but again it'd be from my own work, not something citable. -Slamb 21:56, 20 August 2006 (UTC)

There are lots of deadlocks that don't involve the Coffman conditions. For example, your web browser is waiting for a website but the network cable was unplugged. The problem is that some people wish to use a narrow definition of deadlock that is crafted to make the Coffman conditions necessary. And those people write the textbooks. —Preceding unsigned comment added by 72.196.244.178 (talk) 18:06, 23 March 2010 (UTC)

Kansas State Legislature quote -- citation?[edit]

Does anyone have a citation for this amusing quote? Granted, it's entertaining and illustrative, but a Google search for that phrase brings back exactly one hit. Even if it's just another published reference, rather than the primary source, it would make it look less like an urban legend. Andrew B Clegg 12:08, 13 September 2007 (UTC)

I've tagged it for now.—DMCer 17:42, 17 February 2008 (UTC)
Actually, I'm not sure what you searched, but Google just turned up 445,000 hits for me. I'm citing a book result.—DMCer 17:48, 17 February 2008 (UTC)
Chasing down some references leads to the 1884 joke book Railway Adventures and Anecdotes, edited by Richard Pike. On pp. 252–3 the text
A REMARKABLE NOTICE.
On a certain railway, the following notice appeared:—
“Hereafter, when trains moving in opposite directions are / approaching each other on separate lines, conductors and / engineers will be required to bring their respective trains / to a dead halt before the point of meeting, and be very / careful not to proceed till each train has passed the other.”
appears. I suspect the attribution to the Kansas legislature is embroidery. Michael Slone (talk) 00:25, 11 July 2008 (UTC)

Y dies?[edit]

In the table in the section Deadlock#Avoidance, I suspect (by symmetry) that the top right cell should say "O dies" rather than "Y dies". However I'm not sure the table adds anything that couldn't be better provided by another sentence or two of explanation - are these two strategies simply "when the OS detects that a resource request would cause a deadlock, it kills (in one case) the oldest, and (in the other case) the youngest of the processes involved in the cycle"? Hv (talk) 21:40, 14 July 2008 (UTC)

Possible wrong year for a reference[edit]

The original paper "Eliminating Receive Livelock in an Interrupt-driven Kernel" by Mogul, Jeffrey C., K. K. Ramakrishnan was published in 1995 and not in 2007. Do they have an update in 2007? —Preceding unsigned comment added by 208.51.227.50 (talk) 15:04, 4 August 2009 (UTC)

Hold and Wait[edit]

To ensure that the hold-and-wait condition never occurs in the system,we must guarantee that,whenever a process requests a resource, it does not hold any other resources.One protocol that can be used requires each process to request and be allocated all its resources before it begins execution.We can implement this provision by requiring that system calls requesting resources for a process precede all other system calls.
An alternative protocol allows a process to request resources only when the process has none.A process may request some resources and use them.Before it can request any additional resources, however,it must release all the resources that it is currently allocated.[1] —Preceding unsigned comment added by Sth.pratik (talkcontribs) 11:00, 10 December 2009 (UTC)

Phantom deadlocks[edit]

"Phantom deadlocks are deadlocks that are detected in a distributed system due to system internal delays, but no longer actually exist at the time of detection. deadlock prevents devices to stop functions."

First, if there is no more deadlock, i.e. the deadlock was resolved without the help of a detection/resolution mechanism, doesn't that imply that there was no deadlock, just a delay? And secondly, that last sentence makes no sense, and I can't figure out what it's supposed to mean, so I'm going to remove it. Please someone put it back in (corrected) if you know what that is supposed to say. Chaos.squirrel (talk) 07:13, 23 June 2010 (UTC)

Deadlocking Without Locking?[edit]

My understanding is that deadlocks can only happen through explicit locking. If they happen outside of locking, they need to be called by a different term which does not have the word "lock" in it. This is very confusing if they are grouped together.

Does anyone have an idea what to call this term? And does it already exist?

Also, is there a difference between hard-locks and deadlocks? Or is the term hard-lock a made up term?

Misconception[edit]

"Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable, because the halting problem can be rephrased as a deadlock scenario."

This is misleading because it gives the impression that within the locking mechanism, we have no control over the condition in which halting occurs. The Halting problem states, "The proof shows there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x."

Distributed deadlock prevention within the article shows that the halting issue and locking are mutually exclusive, because all conditions within it are known. It would be valid to re-defining the halting problem in terms of locking, but this requires locking to use unknown/arbitrary conditions. Though I guess this is valid, it is not logical as to why anyone would want to intentionally do this.

Quote

"If I shook a magic 8 ball with digital text that I could change after seeing the initial answer, I believe that "without-a-doubt, all signs point to yes" (given I had the room to write that)." -- TamusJRoyce (please re-quote if I heard it/similar elsewhere and I don't remember it).

TamusJRoyce (talk) 01:17, 30 September 2010 (UTC)

Wording in Example Section[edit]

In the article's examples section I see that there are currently constructions like:

"(there is, but until this is edited otherwise, assume there isn't until reading Distributed deadlock prevention)"

and

"I believe Preemption_(computing) is the term being looked for here?"

Shouldn't self referential statement about the article or comments about what edits need to be made go into the talk page rather than the text of the article itself? It seems out of place in an encyclopedia.

Jbpayton (talk) 18:36, 14 October 2010 (UTC)

Yes. I think that is my mistake. But I didn't know how else to leave it in while notifying readers that the information could be wrong or it could be right. I also have it commented out now (didn't know how to do that at the time), as it contradicts itself.

I am also kind of new to editing wiki, so it was defiantly my fault. I won't have it happen again (thanks for pointing it out).

TamusJRoyce (talk) 15:02, 27 October 2010 (UTC)

Thread vs Process[edit]

The article has inconsistent use of "Process" and "Thread" - the Distributed deadlock section of the article uses the term "Thread", whereas the rest of the article uses the term "Process". Unless "Process" has some alternative meaning in this context (that is not described in this article), then I believe "Thread" is the more accurate term to use. --Kragen2uk (talk) 23:44, 12 January 2011 (UTC)

They are synonymous in this context --92.32.245.160 (talk) 13:17, 18 July 2012 (UTC)

Hardware lock[edit]

This sentence "Computers intended for the time-sharing and/or real-time markets are often equipped with a hardware lock (or hard lock) which guarantees exclusive access to processes, forcing serialized access." has nothing whatsoever to do with deadlocks. It's evidently some kind of misconception by the author that locking is related to deadlocking and it's not really. I'm going to remove this sentence in the next week or so unless someone can tell me exactly how hardware locking is related to deadlocking. Wjhonson (talk) 17:01, 25 October 2011 (UTC)

Commitment ordering[edit]

The neutrality of part of this page is disputed, as part of a wider discussion. See Talk:Commitment ordering and Wikipedia talk:WikiProject Computer science#User:Comps / Commitment ordering. —Ruud 14:27, 23 December 2011 (UTC)

Article Rewrite (29 Jan, 2012)[edit]

Changes made:

  • Header rewritten and rephrased
  • Uncited info deleted from header (related to real-time systems and hardware locks)
  • Citations added for deadlock and telecommunication deadlock definitions.
  • Citations added for examples (chicken and egg, and catch-22)
  • Conditions expanded
  • Citations added for Coffman conditions.
  • Subsections regarding Deadlock Handling restructured and rephrased. Citations added.
  • Ignoring Deadlocks subsection added. Citations added.

Tyler.norton12 00:01, 29 January 2012 (UTC)

Suggestion: Splitting Section "Distributed Deadlocks" into new page[edit]

For:

  • Even though most classical deadlock handling techniques can be extended to Distributed Systems, distributed deadlocks are a vast and more complex concept. They involved methods like edge-chasing algorithms, probe-based algorithms, etc. It is a more advanced and newer field compared to deadlocks in simpler multiprocessing systems. Tyler.norton12 00:08, 29 January 2012 (UTC)

Against:

  • The section has not been referenced and therefore the new article would be subject to being deleted.
  • The section as it stands has several problems that need to be sorted out before the article is split
  • Even when sorted, the section reads more like a computer science lecture than an encyclopedia article. It ought to be cut down to give a brief summary and when it is, the split will not be required. Op47 (talk) 19:59, 14 April 2012 (UTC)
Reply

I am against splitting what I had added into a single new page. I had not realized how disjointed what I had put there was.

And I did not realize that my content was really preventing one of Coffeman Deadlock Condition dealing with preemption. I was using the preemption definition on this page, which is/was not entirely accurate or descriptive.

My suggestion is that if a new page be made, that a single new page which lists all deadlock prevention techniques in a table be done. This table could either categorized by or indicated in the table which Coffeman Deadlock Condition it solves.

Simple deadlock prevention techniques could be listed at the bottom of this link page, in which, when you click a link to that technique, it directs you to its location at the bottom of the same page. Otherwise, it redirects you to an entirely new page dedicated to the complex algorithm.

TamusJRoyce (talk) 14:18, 30 April 2012 (UTC)

Danish translation[edit]

The translation to Denmark is the wrong.. It has nothing todo with computer "deadlock". — Preceding unsigned comment added by 87.55.62.15 (talk) 21:14, 20 May 2012 (UTC)

deadlock is a lock in which everybody is locked — Preceding unsigned comment added by 27.124.23.170 (talk) 05:25, 12 April 2013 (UTC)
Cite error: There are <ref> tags on this page, but the references will not show without a {{reflist}} template (see the help page).