Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Deadlock in a single threaded java program [duplicate]

Tags:

java

deadlock

Read that deadlock can happen in a single threaded java program. I am wondering how since there won't be any competition after all. As far as I can remember, books illustrate examples with more than one thread. Can you please give an example if it can happen with a single thread.

like image 320
Ajex Avatar asked Oct 14 '10 07:10

Ajex


People also ask

Can a deadlock arise when you only have a single single threaded process?

It is impossible to have circular-wait when there is only one single-threaded process. There is no second process to form a circle with the first one. One process cannot hold a resource, yet be waiting for another resource that it is holding. So it is not possible to have a deadlock involving only one process.

Can a program with a single thread deadlock when misusing mutexes?

Yes, single threaded event-driven (non-blocking) app definitely can deadlock. Even without any OS synchronization primitives like mutexes and even without OS at all.

Is it possible for two threads in a process to have a deadlock?

Unfortunately, deadlock can potentially occur in any situation where there are at least two threads and at least two resources. Anytime that more than one thread tries to access a given resource at the same time, developers will have to find a workaround.

How can we avoid deadlock multithreading in Java?

We can avoid Deadlock situation in the following ways: Using Thread. join() Method: We can get a deadlock if two threads are waiting for each other to finish indefinitely using thread join. Then our thread has to wait for another thread to finish, it is always best to use Thread.


3 Answers

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.

like image 50
Michael Borgwardt Avatar answered Sep 30 '22 14:09

Michael Borgwardt


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.

like image 37
iirekm Avatar answered Sep 30 '22 14:09

iirekm


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

like image 26
Mario The Spoon Avatar answered Sep 30 '22 13:09

Mario The Spoon