aspose file tools*
The moose likes Threads and Synchronization and the fly likes How exactly threads work in this situation (Alphonse and Gaston Deadlock)? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Threads and Synchronization
Bookmark "How exactly threads work in this situation (Alphonse and Gaston Deadlock)?" Watch "How exactly threads work in this situation (Alphonse and Gaston Deadlock)?" New topic
Author

How exactly threads work in this situation (Alphonse and Gaston Deadlock)?

Saleh Feek
Greenhorn

Joined: Sep 19, 2012
Posts: 14
I think I misunderstand how exactly threads work in this situation

I copied these code from http://docs.oracle.com/javase/tutorial/essential/concurrency/deadlock.html

I made slight changes:



The output is:

run:

bow() methode invoked on Alphonse object
bowBack() methode invoked on Gaston object
bow() methode invoked on Gaston object
bowBack() methode invoked on Alphonse object

BUILD SUCCESSFUL (total time: 0 seconds)

Now, if you uncomment line 25: Thread.sleep(50);

the output will be

run:

bow() methode invoked on Alphonse object
bow() methode invoked on Gaston object
...... Deadlock ......

The first case (with no deadlock) is not a problem for me. The second case where deadlock happened when uncommenting Thread.sleep(50) is the problem.

The way these threads work (violates) the rule(s) that I understand about threads.

1- On a single processor machine only one thread can actually be running at a time
2- Each object in Java is said to have a lock.
3- A thread entering a synchronized method gains the lock on the object that contains the method
4- No other thread can access any synchronized method in that object until the lock is released - by thread completing the processing inside the method.
.......

When the start() method is sent to both threads alphonse.bow(gaston) & gaston.bow(alphonse), they are both moved to the runnable state.

name the threads
Thread1: alphonse.bow(gaston)
Thread2: gaston.bow(alphonse)

If the selected thread say Thread1 by the processor to be moved to the running state is alphonse.bow(gaston), then it is running, and no other thread can start running until Thread1 completes the processing of the method bow() on alphonse object.

The processing steps is to print: bow() methode invoked on Alphonse object
Then sleep(50) - note that sleep() will not move Thread1 to the blocked state because the method is labelled with synchronized .
Finally invoke gaston.bowBack(alphonse)

It is expected that gaston.bowBack(alphonse) completes and prints: bowBack() methode invoked on Gaston object (which didn't happen)
and at this point Thread1 completes processing method bow() and Thread1 moved to the finished state (which didn't happen).

But instead of that, another thread Thread2 had moved to the running state before Thread1 completed processing of method bow() which violates rule 4. (I need explanation?)

So Thread2 gaston.bow(alphonse) is now running

The processing of gaston.bow(alphonse) is to print: bow() methode invoked on Gaston object
Then sleep(50)
Finally invoke alphonse.bowBack(gaston) which didn't proceed. (why?)

Thank you
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

Saleh Feek wrote:The way these threads work (violates) the rule(s) that I understand about threads.

1- On a single processor machine only one thread can actually be running at a time


That is one mistake. All the threads should be considered 'running' at the same time - they are running concurrently. It might be that lines of code can't actually be executed at the same time, because there isn't the processing power (this assumes something about the OS and processor you shouldn't assume though), but in these cases there would be 'time slicing' where each thread gets some portion of the processor's cycles, so at any given time each thread is in some uncertain point of execution relative to the other threads.

2- Each object in Java is said to have a lock.
3- A thread entering a synchronized method gains the lock on the object that contains the method
4- No other thread can access any synchronized method in that object until the lock is released - by thread completing the processing inside the method.

Correct. You should note you have two Objects in this case, and therefore two locks.

When the start() method is sent to both threads alphonse.bow(gaston) & gaston.bow(alphonse), they are both moved to the runnable state.

name the threads
Thread1: alphonse.bow(gaston)
Thread2: gaston.bow(alphonse)

If the selected thread say Thread1 by the processor to be moved to the running state is alphonse.bow(gaston), then it is running, and no other thread can start running until Thread1 completes the processing of the method bow() on alphonse object.

Incorrect. Other threads can execute, they just can't access synchronized blocks / methods that use the lock on the alphonse Object. The other thread could still execute code which is, for example, synchronized on the gaston Object.

The processing steps is to print: bow() methode invoked on Alphonse object
Then sleep(50) - note that sleep() will not move Thread1 to the blocked state because the method is labelled with synchronized .

Sleep also frees up processor cycles for use by another thread. Since there is the gaston thread waiting for processor cycles, it is free to execute. When it does it gains the lock on the gaston Object, displays the message, and then sleeps.
Finally invoke gaston.bowBack(alphonse)

And at this point the gaston thread already has the lock for the gaston Object, so the alphonse thread is blocked. Then, when gaston wakes up, it tries to do alphonse.bowBack(gaston) but the alphonse thread already has a the alphonse Object lock, so gaston can't proceed. Neither thread can proceed because they are blocked by the other, which is pretty much the definition of dead lock.

Why doesn't this happen without the sleep? Probably because all the actions run by a single thread are so quick there is no opportunity for the processor to switch the thread context (share cycles with another thread), so the first thread that gets started hogs it until it is done. You can't be positive that will always happen though...


Steve
Saleh Feek
Greenhorn

Joined: Sep 19, 2012
Posts: 14
Thank you Steve

I have been searching intensively about this problem (Alphonse and Gaston Deadlock). Your help made it more clear for me to understand.

I want to say something about this problem (Alphonse and Gaston Deadlock).

At the beginning when I started searching about it, I thought that I exceptionally don't understand it correctly. But I found that there are a number of people who share with me the same misunderstanding, and the same point of confusion about how do these threads work.

The confusion that those people - including me - have is that they don't discriminate between two things:

A- Invoking a synchronized method of a particular object from several threads.
B- Invoking a synchronized method of different objects from several threads. (here, even if the objects are of the same class)


In A, once a thread say thread1 invokes a synchronized methods of a particular object, no other thread can invoke any synchronized method of that particular object, until thread1 finishes processing that method of that particular object.

In B, if there are two different objects of the same class say obj1 and obj2, and if one thread say thread1 invokes any synchronized method of obj1, another thread say thread2 can invoke any method of obj2, but cannot invoke any synchronized method of obj1 until thread1 finishes processing the synchronized method of obj1.

that confusion made me to think that threads violates (rule 4 - I talked about it above).


It is clear now, Thank you again..
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Saleh Feek wrote:
A- Invoking a method of a particular object from several threads.
B- Invoking a method of different objects from several threads. (here, even if objects are of the same class)


In A, once a thread invokes a synchronized methods of a particular object, no other thread can invoke any synchronized method of that particular object, until that thread finishes processing that method of that particular object.

In B, if there are two objects of the same class say obj1 and obj2, and if one thread say thread1 invokes any synchronized method of obj1, another thread say thread2 can invoke any method of obj2, but cannot invoke any synchronized method of obj1 until thread1 finishes processing the synchronized method of obj1.


This is correct, and it's the consequence of a couple of other simpler (more "primitive") facts:

1. Every object has exactly one lock that is implicitly associated with that object, and only that object.

2. The only thing the synchronized keyword does in terms of mutual exclusion is that it obtains an object's lock, waiting first if some other thread already holds that lock.

3. Declaring a method synchronized is just syntactic sugar. It's the same as putting synchronized (this) { ... } around the method body (or, for a static method, instead of "this", we would be synchronizing on the Class object).

So your statements above simply special cases that arise from these 3 points.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: How exactly threads work in this situation (Alphonse and Gaston Deadlock)?