![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
Deadlock, in the abstract sense, is just a group of member waiting for each other to do some thing. That thing might be anything, sending a message, releasing a resource, a series of events occurring in a specific order.
Deadlock, therefore, has *little* to do with locks. Locks are just one manner of not being able to access a resource. The book referenced in the introduction *falsely* narrows this common definition to locked resources only, which is what that book likely is about, but has nothing to do with this phenomenon in the abstract sense.
Deadlock can always be abstractly modeled into *any* system which allows for concurrently communicating processes to be modeled, independent of the means of communication. Process A waiting for process B to send a message, and process B waiting for process A to send a message, is enough. — Preceding unsigned comment added by 86.82.44.193 ( talk) 01:38, 11 August 2017 (UTC)
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)
Defiantly not 196.210.142.17 ( talk) —Preceding undated comment added 19:54, 7 October 2010 (UTC).
I was looking for the film "Deadly Embrace" and was redirected here, with no explanation as to why. Then there is a "Deadlock" disambiguation page, which has no references to "Deadly Embrace" either. I think this is a bad redirect. — Preceding unsigned comment added by 47.23.40.34 ( talk) 17:00, 18 April 2017 (UTC)
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:
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:
- 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,
Deadlock -in the general sense- is just processes waiting for each other and can always occur even with one resource. That one resource is enough to model communication, and communication is enough to model a scenario where process A and B are mutually waiting for the other to send a message. — Preceding unsigned comment added by 86.82.44.193 ( talk) 01:49, 11 August 2017 (UTC)
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)
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.
"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)
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)
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)
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":
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)
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'm quite confused by the following sections, which seem to be primarily discussing:
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:
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)
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:
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)
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)
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)
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)
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 (
talk •
contribs)
11:00, 10 December 2009 (UTC)
References
"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)
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?
"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.
"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)
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)
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)
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)
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)
Changes made:
Tyler.norton12 00:01, 29 January 2012 (UTC)
For:
Against:
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)
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)
The current text says: "In a commitment ordering-based distributed environment (including the strong strict two-phase locking (SS2PL, or rigorous) special case) distributed deadlocks are resolved automatically by the atomic commitment protocol (like a two-phase commit (2PC)), and no global wait-for graph or other resolution mechanism is needed. Similar automatic global deadlock resolution occurs also in environments that employ 2PL that is not SS2PL (and typically not CO; see Deadlocks in 2PL)."
WHAT!??? this is complete rubbish! 1. 2PC (2 Phase COMMIT) can definitely not prevent deadlocks! It is used to guarantee atomicity! The deadlock occurs before a transaction decides to commit - before 2PC even starts. Distributed 2PC can actually cause a blocking situation, when a subtransaction has precommitted and is waiting for the global commit-decision (in-doubt-transaction). This, however, is not a deadlock. 2. 2PL will not automatically prevent deadlocks! In contrast: It is the reason for deadlocks!! 2PL guarantees serializable histories at the risk of deadlocks. Preclaiming could actually prevent deadlocks (request all locks at the beginning). Strict locking (Hold all locks until the end) has nothing to to with deadlocks! It guarantees recoverability, avoids cascading aborts and allows undoing a transactions updates by using before-images. — Preceding unsigned comment added by 84.147.184.89 ( talk) 20:14, 26 May 2014 (UTC)
"That and the use of the strong word "dead" in front of lock are some of the reasons why deadlocks have a "this is a big problem" reputation."
I would personally like to eliminate that sentence altogether - the section and paragraph were not about the "reputation" of deadlocks. It sounds like this translates to "...and it has a scary name, which is why you should be afraid of it." Does the sentence serve a purpose I'm missing? Sobeita ( talk) 02:33, 24 September 2014 (UTC)
Hello fellow Wikipedians,
I have just modified one external link on Deadlock. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 5 June 2024).
Cheers.— InternetArchiveBot ( Report bug) 04:39, 6 December 2017 (UTC)
![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
Deadlock, in the abstract sense, is just a group of member waiting for each other to do some thing. That thing might be anything, sending a message, releasing a resource, a series of events occurring in a specific order.
Deadlock, therefore, has *little* to do with locks. Locks are just one manner of not being able to access a resource. The book referenced in the introduction *falsely* narrows this common definition to locked resources only, which is what that book likely is about, but has nothing to do with this phenomenon in the abstract sense.
Deadlock can always be abstractly modeled into *any* system which allows for concurrently communicating processes to be modeled, independent of the means of communication. Process A waiting for process B to send a message, and process B waiting for process A to send a message, is enough. — Preceding unsigned comment added by 86.82.44.193 ( talk) 01:38, 11 August 2017 (UTC)
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)
Defiantly not 196.210.142.17 ( talk) —Preceding undated comment added 19:54, 7 October 2010 (UTC).
I was looking for the film "Deadly Embrace" and was redirected here, with no explanation as to why. Then there is a "Deadlock" disambiguation page, which has no references to "Deadly Embrace" either. I think this is a bad redirect. — Preceding unsigned comment added by 47.23.40.34 ( talk) 17:00, 18 April 2017 (UTC)
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:
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:
- 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,
Deadlock -in the general sense- is just processes waiting for each other and can always occur even with one resource. That one resource is enough to model communication, and communication is enough to model a scenario where process A and B are mutually waiting for the other to send a message. — Preceding unsigned comment added by 86.82.44.193 ( talk) 01:49, 11 August 2017 (UTC)
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)
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.
"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)
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)
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)
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":
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)
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'm quite confused by the following sections, which seem to be primarily discussing:
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:
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)
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:
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)
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)
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)
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)
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 (
talk •
contribs)
11:00, 10 December 2009 (UTC)
References
"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)
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?
"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.
"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)
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)
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)
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)
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)
Changes made:
Tyler.norton12 00:01, 29 January 2012 (UTC)
For:
Against:
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)
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)
The current text says: "In a commitment ordering-based distributed environment (including the strong strict two-phase locking (SS2PL, or rigorous) special case) distributed deadlocks are resolved automatically by the atomic commitment protocol (like a two-phase commit (2PC)), and no global wait-for graph or other resolution mechanism is needed. Similar automatic global deadlock resolution occurs also in environments that employ 2PL that is not SS2PL (and typically not CO; see Deadlocks in 2PL)."
WHAT!??? this is complete rubbish! 1. 2PC (2 Phase COMMIT) can definitely not prevent deadlocks! It is used to guarantee atomicity! The deadlock occurs before a transaction decides to commit - before 2PC even starts. Distributed 2PC can actually cause a blocking situation, when a subtransaction has precommitted and is waiting for the global commit-decision (in-doubt-transaction). This, however, is not a deadlock. 2. 2PL will not automatically prevent deadlocks! In contrast: It is the reason for deadlocks!! 2PL guarantees serializable histories at the risk of deadlocks. Preclaiming could actually prevent deadlocks (request all locks at the beginning). Strict locking (Hold all locks until the end) has nothing to to with deadlocks! It guarantees recoverability, avoids cascading aborts and allows undoing a transactions updates by using before-images. — Preceding unsigned comment added by 84.147.184.89 ( talk) 20:14, 26 May 2014 (UTC)
"That and the use of the strong word "dead" in front of lock are some of the reasons why deadlocks have a "this is a big problem" reputation."
I would personally like to eliminate that sentence altogether - the section and paragraph were not about the "reputation" of deadlocks. It sounds like this translates to "...and it has a scary name, which is why you should be afraid of it." Does the sentence serve a purpose I'm missing? Sobeita ( talk) 02:33, 24 September 2014 (UTC)
Hello fellow Wikipedians,
I have just modified one external link on Deadlock. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 5 June 2024).
Cheers.— InternetArchiveBot ( Report bug) 04:39, 6 December 2017 (UTC)