Deadlock in a single threaded java program?

It's a matter of how exactly you define "deadlock.

It's a matter of how exactly you define "deadlock". For example, this scenario is somewhat realistic: a single-threaded application that uses a size-limited queue that blocks when its limit is reached. As long as the limit is not reached, this will work fine with a single thread.

But when the limit is reached, the thread will wait forever for a (non-existing) other thread to take something from the queue so that it can continue.

1 I don't think this is a deadlock. Or else while(true){} is a deadlock – Bozho Oct 14 '10 at 16:27.

Before multicore processors became cheap, all desktop computers had single-core processors. Single-core processors runs only on thread. So how multithreading worked then?

The simplest implementation for Java would be: thread1's code: doSomething(); yield(); // may switch to another thread doSomethingElse(); thread2's code: doSomething2(); yield(); // may switch to another thread doSomethingElse2(); This is called cooperative multithreading - all is done with just 1 thread, and so multithreading was done in Windows 3.1. Today's multithreading called preemptive multithreading is just a slight modification of cooperative multithreading where this yield() is called automatically from time to time. All that may reduce to the following interlacings: doSomething(); doSomething2(); doSomethingElse2(); doSomethingElse(); or: doSomething(); doSomething2(); doSomethingElse(); doSomethingElse2(); And so on... We converted multithreaded code to single-threaded code.So yes, if a deadlock is possible in multithreaded programs in single-threaded as well. For example: thread1: queue.

Put(x); yield(); thread2: x = queue.waitAndGet() yield(); It's OK with this interlace: queue. Put(x); x = queue.waitAndGet() But here we get deadlock: x = queue.waitAndGet() queue. Put(x); So yes, deadlocks are possible in single-threaded programs.

– Frank Oct 14 '10 at 10:32 With those 2 'threads' and yield() it will happen in random, with modern operating systems (which use no yield() but preemptive threading) it will work, with the second single-threaded solution, deadlock will happen every time, just replace my 'queue.xxxx()' methods with appropriate methods from BlockingQueue. The thread will think it waits for some other thread, whereas it waits for itself. :-) – iirekm Oct 14 '10 at 12:59.

Well I dare say yes If you try to acquire the same lock within the same thread consecutively, it depends on the type of lock or locking implementation whether it checks if the lock is acquired by the same thread. If the implementation does not check this, you have a deadlock. For synchronized this is checked, but I could not find the guarantee for Semaphore.

If you use some other type of lock, you have to check the spec as how it is guaranteed to behave! Also as has already been pointed out, you may block (which is different from deadlock) by reading/ writing to a restricted buffer. For instance you write things into a slotted buffer and only read from it on certain conditions.

When you can no longer insert, you wait until a slot becomes free, which won't happen since you yourself do the reading. So I daresay the answer should be yes, albeit not that easy and usually easier to detect. Hth Mario.

Even if your java stuff is single-threaded there are still signal handlers, which are executed in a different thread/context than the main thread. So... deadlock can indeed happen even on single-threaded solutions, if/when java is running on linux. QED.

-pbr.

1 didn't think about signals! – Mario The Spoon Oct 14 '10 at 8:28.

No, Sounds pretty impossible to me. But you could theoretically lock a system resource while another app locks another that you're going to request and that app is going to request the one you've already locked. Bang Deadlock.

But the OS should be able to sort this thing out by detecting that and give both resources to one app at the time. Chances for this to happen is slim to none, but any good OS should be able to handle this one-in-a billion chance. If you make the design carefully and only locks one resource at a time, this can not happen.

This answer is accurate discussing a thing that could happen once in a billion. – Frank Oct 14 '10 at 10:02 I didn't down vote you, but I almost did. Your 2nd paragraph is correct, hence the chance of this happening are very high if the design of the application(s) operate in the manner you describe.

So your 3rd para is wrong (for most resources on most OS). After all, exactly what would the OS do to avoid the deadlock? – Carter Galle Oct 16 '10 at 18:38 And your 3rd paragraph presumes that the app can accomplish its goals with only a single resource, which simply doesn't work for a huge number of problems.

– Carter Galle Oct 16 '10 at 18:39 The OS can do resource scheduling, but that is pretty hard on a programmers head. Or at least it was hard for me when I did a hobby kernel 7 years ago. One most think of many cases, worst case is that both processes have done something to the resource they have got a lock to - if so one cannot just hand over one of the resources to the other process and let it have it's go.

My own solution that I did 7 years ago was crude - it just flipped a coin and hoped for the best. – Frank Oct 17 '10 at 6:33.

No. Deadlock is a result of multiple threads (or processes) attempting to acquire locks in such a way that neither can continue. Consider a quote from the Wikipedia article: (en.wikipedia.org/wiki/Deadlock) "When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.

Multiple threads or processes.... – Carter Galle Oct 16 '10 at 18:33 Good point Carter. I've edited my comment. Thanks.

– philipk Oct 17 '10 at 19:25.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.