wood burning stoves 2.0*
The moose likes Threads and Synchronization and the fly likes Solution for deadlock Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Threads and Synchronization
Bookmark "Solution for deadlock" Watch "Solution for deadlock" New topic
Author

Solution for deadlock

tom osayo
Greenhorn

Joined: Nov 02, 2009
Posts: 13
Hi

Below is a code where I get a deadlock. I need a solution to overcome this deadlock first with wait and notify and secondly with Semaphore. Can someone change the below code so that it runs without a deadlock.



Thanks
Tomas
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4179
    
  21

Hi Tom, when you post code, could you please UseCodeTags, it will make it easier to read. You can go back and edit your previous post by pressing the Edit button on your original post.

Now, this sounds like a homework assignment, so we won't do it for you. But we can help you out. What parts of the code lead to the deadlock?


Steve
avi sinha
Ranch Hand

Joined: Mar 15, 2009
Posts: 452

tom osayo wrote:Hi

Below is a code where I get a deadlock. I need a solution to overcome this deadlock first with wait and notify and secondly with Semaphore. Can someone change the below code so that it runs without a deadlock.
Thanks
Tomas


how did you identify that there was a deadlock ??? and welcome to JavaRanch

avi sinha


SCJP 5.0 SCWCD 5.0
tom osayo
Greenhorn

Joined: Nov 02, 2009
Posts: 13
Hello

When the method otherX.m2 from method m1 is called there arises a deadlock.

Thanks
Tomas
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4179
    
  21

tom osayo wrote:Hello

When the method otherX.m2 from method m1 is called there arises a deadlock.

Thanks
Tomas


And why does that occur?
tom osayo
Greenhorn

Joined: Nov 02, 2009
Posts: 13
I dont know.

tomas
avi sinha
Ranch Hand

Joined: Mar 15, 2009
Posts: 452

just think about it ,, if both the threads will be inside the m1 method ever there will be a deadlock.
so now what can you do to solve it??? its pretty easy if you you just want to prevent the deadlock.

avi sinha
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4179
    
  21

tom osayo wrote:I dont know.

tomas


Write it on a piece of paper. Each time an Thread takes a lock write down locked (...). For example, when x1 enters m1, you would right:

Then do the same each time a Thread releases a lock:

Write the code that gets called for each thread in 2 different columns, then interleave them in different combinations until you see what happens (remember, x2 can't succeed in locking x1 until x1 unlocks x1, and vice versa).
avi sinha
Ranch Hand

Joined: Mar 15, 2009
Posts: 452

i am feeling sleepy. i am just posting the code . take it as an assignment to understand the code .
try to do it another way too.


avi sinha
tom osayo
Greenhorn

Joined: Nov 02, 2009
Posts: 13
hi

below i have the solution with wait and notify

tom osayo
Greenhorn

Joined: Nov 02, 2009
Posts: 13
thanks everyone . let me try to do it with Semaphore.

Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4179
    
  21

Sorry Avi, but this code is both not correct from a simple monitor example, and not thread safe.

avi sinha wrote:


Can't do otherX.wait(), it creates an illegal monitor exception. In order to do otherX.wait() you must first synchronize on otherX, which leaves you in the same exact position you were before. What actually happens is that Thread1 sets its takenLock to false, tries to do otherX.wait() which fails with an exception, so the Thread dies. Thread2 then tests otherX.takenLock == true, which always turns up false, and so the second Thread never enters the if block.

In addition, both Threads will be accessing both X's takenLock value. In order for the otherX.takenLock to be read safely it(the takenLock variable) would need to be volatile. As it is now, it is not safe (any changes one thread makes to takenLock may not be read by the other thread).

tom osayo wrote:

First, when you add code tags, surround your code with the tags ([code] <your code here> [/code]). I went ahead and fixed your previous posts.

Have you tried this code? Walk through the steps to see what happens. In my mind it goes like this:


Both threads end up waiting for a notify and so neither can be notified by the other one. You just changed the way your two threads freeze up.
avi sinha
Ranch Hand

Joined: Mar 15, 2009
Posts: 452

oops ! you are right luke ,
was feeling sleepy that's why.

one more thing , i had executed the code but didn't throw IllegalMonitorStateException.what may be the reason?



avi sinha
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4179
    
  21

Hi avi,

Closer, but still won't work. In m2 you are notifying otherX, which is the wrong X to notify. Let's run through the test:
0) <Context = x1's Thread>
1) x1's thread starts execution first.
2) x1's thread locks x1
3) x1's thread sets x1's takenLock to true
4) x1's thread checks x2's takenLock, which is false

0) <Context Switch to x2's Thread>
1) x2's thread starts execution second
2) x2's thread locks x2
3) x2's thread sets x2's takenLock to true
4) x2's thread checks x1's takenLock which is true so it goes into the if block
5) x2's thread sets x2's takenLock to false
6) x2's thread unlocks x2 - and calls wait

4) <Context Switch to x1's Thread>
5) x1's thread calls x2.m2
6) x1's thread locks x2
7) x1's thread sets x2's takenLock to false
8) x1's thread locks x1 (x2's otherX is x1)
9) x1's thread notifies x1 (x2's otherX is x1)
10) x1't thread unlocks x1
11) x1's thread unlocks x2
12) x1's thread unlocks x1

-- loop x1's thread over and over again --

The problem is that when you call otherX.notify, you are calling the wrong notify(), the first object to go into wait() will never be notified, and the other object never goes to wait(). You might change m2 to be something like this:

But that just delays the deadlock a bit (you get back to the same situation you started with, just delayed to when the wait() and notify() align with method calls).

avi sinha wrote:one more thing , i had executed the code but didn't throw IllegalMonitorStateException.what may be the reason?

It probably did happen, but you hadn't noticed. It would have occurred very near the top of the output, and you are looping a lot of times, which means the error output was probably eaten up - and perhaps even pushed out of your console's buffer. Try reducing the number of loops to 100 and you should see the error.

Also, when testing these sorts of things I like to know about which thread executes what line. One way to do that is to simply add the current thread's name to each output line so you can follow how each one runs. For example, I changes the two output statements in the code being written here to:

So the output is like:


Then, when I see long stretches of just 1 thread, I know there is a problem with the other one.
avi sinha
Ranch Hand

Joined: Mar 15, 2009
Posts: 452

Steve Luke wrote:Hi avi,


The problem is that when you call otherX.notify, you are calling the wrong notify(), the first object to go into wait() will never be notified, and the other object never goes to wait(). You might change m2 to be something like this:

But that just delays the deadlock a bit (you get back to the same situation you started with, just delayed to when the wait() and notify() align with method calls).




ya got the point here . in m2 this will refer to anotherX object .
my mistake ... :(
avi sinha

Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4179
    
  21

Ok, I have been doing a lot of 'It won't works' but not providing any 'solutions', so here is my go at it.

First, let's understand the requirements. In the original code, two methods of the same Object should not run at the same time. So x1.m1() can run at the same time as x2.m1(), but not at the same time as x1.m2().

Second, why does the synchronized method not work? Well, you are trying to lock on two separate objects (x1 and x2), and you are trying to take those locks in different orders in different threads. x1's Thread takes x1's lock then tries for x2's lock without releasing x1's lock. Meanwhile x2's Thread takes x2's lock then tries for x1's lock without releasing x2's lock. One is always waiting for the other to finish, so neither can finish.

One solution is to not attempt to hold two locks at the same time. The simplest approach is like this:

The method m1 isn't synchronized, but all the manipulation to m1's content is. When that is done, you release the lock BEFORE calling otherX.m2(). That way each Thread only has one lock at a time.

Another option would be to use one single object to lock on for both x1 and x2, rather than each object synchronizing on itself. This would work, but doesn't achieve the same concurrency as the described solution.

As far as using wait/notify on and getting the same functionality, using the same code for both threads, I can't come up with a solution. I always lose something (like x1.m1() can't run at the same time as x2.m1()) or introduce the possibility of deadlocks. Maybe someone else can ... This is as far as I got:


Some of the display was modified so I could keep track of both threads for long periods without running out of display buffer... My caution here is that some of the code is technically not protected by synchronization. I haven't really tested it if it is safe.
tom osayo
Greenhorn

Joined: Nov 02, 2009
Posts: 13
Hi

Thanks to all.
Yes i understand Steve your code.

Tomas
buntha Choudhary
Ranch Hand

Joined: Jul 03, 2009
Posts: 136

The below piece of code is as well working not sure that the solution very proper or not.

Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4179
    
  21

Hi Buntha,

Your last posted code probably does not provide the data safety that the problem requires. The problem is that by locking only once on the myX value you allow for internal data in x1 and x2 to be modified in unsafe manner. Here is an example:

user1 synchronizes on x1, and call's its m1 method, which in turn calls the m2 method of x2. While x2.m2() is running in user1, user2 synchronizes on x2 and calls x2's m1 method. Now x2.m1() and x2.m2() are both running concurrently and if they are working on the same data then you have a thread-safety problem.
buntha Choudhary
Ranch Hand

Joined: Jul 03, 2009
Posts: 136

Thanks for the clarification , but still I have some doubts.

1 problem is that I have made the object myX as synchronized , so as soon as it will go for myX, the instance of X will be make the lock and the counter will run for entire 100 and then it will go for other instance . So where may I face the situation as you mentioned.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Solution for deadlock