Can a single threaded application have a deadlock? If so, please provide an example.
+2
A:
Yes, a single-threaded application can deadlock if you have threads that are not re-entrant and a thread attempts to reacquire a lock that it owns already (like via a recursive call).
Edit: I see that the post has been tagged "Java"; I don't know if that was an update or if I missed it before, but in any case locks in Java ARE re-entrant, so you won't be able to deadlock a single-threaded application in this manner.
danben
2010-01-29 15:33:02
Normally, that will result in some kind of error indicating that the thread already owns the lock.
Thorarin
2010-01-29 15:37:52
Wouldn't that depend on the platform?
danben
2010-01-29 15:38:36
@danben: It could possibly lock up, but by definition of the term, this would not be deadlock. Admittedly I would probably call it deadlock for lack of a better word :)
Thorarin
2010-01-29 15:48:43
"...a single-threaded application can deadlock if you have threads..." -- sounds like a contradiction in terms. Single-threaded application, by definition, has no threads.
atzz
2010-01-29 15:50:53
@atzz: first of all, a single-threaded application has ONE thread, not none. Second of all, my post is clearly referring to whether threads can reacquire locks in the particular platform. Your downvote is ill-informed.
danben
2010-01-29 15:56:34
Please see http://meta.stackoverflow.com/questions/15650/ban-lmgtfy-let-me-google-that-for-you-links
Bedwyr Humphreys
2010-01-29 15:41:30
It is not a "ltgtfy" link. But even if it was I wouldn't mind to be offensive - that's what I did.
queen3
2010-01-29 15:50:27
+2
A:
It depends a little on how you interpret the question. If resources that are shared with other applications are involved, then yes. Without shared resources, no.
A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does.
With a single thread, there is only one action, which can't compete with itself.
From Wikipedia:
Necessary conditions
There are four necessary and sufficient conditions for a deadlock to occur, known as the Coffman conditions from their first description in a 1971 article by E. G. Coffman.
- Mutual exclusion condition: a resource that cannot be used by more than one process at a time
- Hold and wait condition: processes already holding resources may request new resources
- No preemption condition: No resource can be forcibly removed from a process holding it, resources can be released only by the explicit action of the process
- Circular wait condition: two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds
By this definition, two processes are required to consitute a deadlock.
Thorarin
2010-01-29 15:35:45
You do mean "in Java", right? Otherwise, MSDN disagrees with you. http://msdn.microsoft.com/en-us/library/ms792855.aspx
danben
2010-01-29 15:42:10
And that link describes a scenario in which it can happen - do you disagree with it?
danben
2010-01-29 15:58:36
@danben: I disagree in the sense that the case described shouldn't be called deadlock (by the quoted definition). As such, not mentioning the case is at the very least defendable, especially if there is a much simpler example of deadlock occurring.
Thorarin
2010-01-29 16:01:56
Well, if you insist on using that Wikipedia article as the authority on deadlocking, then you would also have to say that a single multithreaded Java application can never deadlock, because Wikipedia claims deadlock only occurs between two processes, and threads are not processes. At some point, it might be prudent to start questioning your definitions.
danben
2010-01-29 16:06:15
@danben: a thread *is* a process. The term process is used very loosely here, not as some kind of platform specific concept that you are referring to.
Thorarin
2010-01-29 16:17:09
Then how do you know which definitions should be interpreted strictly (deadlock) and which should be interpreted loosely (thread)?
danben
2010-01-29 16:26:26
@danben: You're mixing things up again. The concept of a thread is a pretty strictly defined (albeit somewhat platform specific). I said the term *process* was used loosely in the definition of deadlock, from which you draw an invalid conclusion. Just because a horse is an animal, doesn't mean every animal is a horse :P
Thorarin
2010-01-29 16:36:56