Why won't the following Deadlock? Exam 2 q.16

[Ai Ayumi]

public class Stubborn implements Runnable {   
             static Thread t1;   
             static int x = 5;   
             public void run() {   
               if(Thread.currentThread().getId() == t1.getId()) shove();   
               else push();   
             }   
            static synchronized void push() { shove(); }   
            static void shove() {   
              synchronized(Stubborn.class) {   
                System.out.print(x-- + " ");   
                try { Thread.sleep(2000); } catch (Exception e) { ; }   
                if(x > 0) push();   
            } }   
            public static void main(String[] args) {   
              t1 = new Thread(new Stubborn());   
              t1.start();   
              new Thread(new Stubborn()).start();   
          } }  

From K&B Practice Exam 2, q16:

Answer: there is only one lock, so no deadlock can occur.

Aren't synchronize(Stubborn.class) and static synchronized void push() locked seperately?
If only one lock, Does that mean if t1 is using synchronize(Stubborn.class), t2 won't be able to access static synchronized void push()?

Also, the output prints 5 4 3 2 1 (by t1), then 0 (by t2). Why is it not alternatingly by t1, t2?

Can someone help clarify?

[Henry Wong]

Ai Ayumi wrote:

public class Stubborn implements Runnable {   
             static Thread t1;   
             static int x = 5;   
             public void run() {   
               if(Thread.currentThread().getId() == t1.getId()) shove();   
               else push();   
             }   
            static synchronized void push() { shove(); }   
            static void shove() {   
              synchronized(Stubborn.class) {   
                System.out.print(x-- + " ");   
                try { Thread.sleep(2000); } catch (Exception e) { ; }   
                if(x > 0) push();   
            } }   
            public static void main(String[] args) {   
              t1 = new Thread(new Stubborn());   
              t1.start();   
              new Thread(new Stubborn()).start();   
          } }  

From K&B Practice Exam 2, q16:

Answer: there is only one lock, so no deadlock can occur.

Ai Ayumi wrote:
Aren't synchronize(Stubborn.class) and static synchronized void push() locked seperately?

Synchronized static methods use the instance of Class class (that represents the class which the method is declared) as its lock. So, a thread that calls a synchronized static method of the Stubborn class, and a thread that locks on the Stubborn.class instance, are locking on the same object.

Ai Ayumi wrote:
If only one lock, Does that mean if t1 is using synchronize(Stubborn.class), t2 won't be able to access static synchronized void push()?

Two different threads can't own the same lock at the same time.

Ai Ayumi wrote:
Also, the output prints 5 4 3 2 1 (by t1), then 0 (by t2). Why is it not alternatingly by t1, t2?

Take a look at the code. You will see that one thread is not releasing the lock -- so alternating is not possible.

Henry

[Pritish Chakraborty]

What Henry said.

Additionally, sleep() will not release object lock. wait() could though.

[Ai Ayumi]

Henry Wong wrote:

Ai Ayumi wrote:
Aren't synchronize(Stubborn.class) and static synchronized void push() locked seperately?

Synchronized static methods use the instance of Class class (that represents the class which the method is declared) as its lock. So, a thread that calls a synchronized static method of the Stubborn class, and a thread that locks on the Stubborn.class instance, are locking on the same object.

Henry

Ok I see....

Does this also occur in non-static synchronizations? If one has synchronized block synchronized(this){} and a synchronized method(), assuming using the same object, if one Thread accesses the Block, another can't access the synchronized method at the same time?

[Pritish Chakraborty]

If I know my basics right, the following -:

AccessMod synchronized ReturnType MethA()
{
   ....
}

is equivalent to

AccessMod ReturnType MethA()
{
   synchronized(this)
  { 
    ....
  }
}

If I recall, this is given in K&B, Chapter-9. Being non-static, both synchronize on the object that started the thread (this refers to that object).

So yes, the other thread is blocked from accessing the lock while one thread is executing in its critical section.

[Cyril Sadasivan]

Are questions like 'will the following deadlock?' expected on OCPJP 6 exam?

[Amit Ramesh]

Can someone please correct my logic:

I see t1 and the new nameless thread are both started. Both become runnable.
The scheduler will pick one of the two threads to run. Lets say it is t1 first.
So t1's run method executes, and it invokes shove().
Static shove has a synchronized block of code that locks on Stubborn.class lock. t1 obtains the Stubborn class lock.
Inside shove(), t1 prints x and decrements it.
Then goes to sleep for 2000 seconds taking it out of runnable state, into a timed sleep.

At this point, two things can happen: 1) the second un-named thread in runnable state could get scheduled to run. Or 2) t1 could be potentially chosen to run if it finishes its timed sleep and wakes back up into runnable state.
But lets assume the nameless thread was chosen for now instead.

The nameless thread starts it's run method. From within run(), it invokes push().
Push() is a static synchronized method, which means the nameless thread must obtain the Class lock for Stubborn to proceed, but t1 still has it. So the nameless thread gets stuck in Running state trying to obtain the class lock for Stubborn that t1 owns.


Lets say, t1 has now woken up from its timed sleep of 2000 milliseconds. This is where I am unsure. I think t1 has woken up, is in runnable state, but cant transition back to Running, because the nameless thread is stuck in Running state waiting for the Stubborn.class lock to be released by t1. So wouldnt t1 be deadlocked now as well. Both threads are deadlocked. So shouldn't answers D and E be correct?

The only way I could see the answer being C is if the same thread that sleeps in shove() always gets picked first by the thread scheduler first when it wakes up. But that is not guaranteed by the thread scheduler. Isn't there a vulnerability that the other thread could get scheduled while one is sleeping?

Thanks,
Amit

[Henry Wong]

Amit Ramesh wrote:
At this point, two things can happen: 1) the second un-named thread in runnable state could get scheduled to run. Or 2) t1 could be potentially chosen to run if it finishes its timed sleep and wakes back up into runnable state.
But lets assume the nameless thread was chosen for now instead.

Although option 2 is technically possible, it is very highly unlikely that the OS/JVM can't get the other thread started and running within the two seconds that the t1 thread is sleeping. The OS/JVM tends to be much faster than that.

Henry

[Henry Wong]

Amit Ramesh wrote:
The nameless thread starts it's run method. From within run(), it invokes push().
Push() is a static synchronized method, which means the nameless thread must obtain the Class lock for Stubborn to proceed, but t1 still has it. So the nameless thread gets stuck in Running state trying to obtain the class lock for Stubborn that t1 owns.

Not sure what you mean by "stuck in a runnable state" -- it is blocked waiting for a lock. How is that runnable? It is in the blocked state.

Amit Ramesh wrote:
Lets say, t1 has now woken up from its timed sleep of 2000 milliseconds. This is where I am unsure. I think t1 has woken up, is in runnable state, but cant transition back to Running, because the nameless thread is stuck in Running state waiting for the Stubborn.class lock to be released by t1. So wouldnt t1 be deadlocked now as well. Both threads are deadlocked. So shouldn't answers D and E be correct?

First of all, why can't two threads be in a runnable state? This happens all the time. And the OS will simply timeslice the runnable threads -- that is the job of the scheduler. Also, modern processors support multiple cores too, so you can have multiple threads in a running state too.

And second, as mentioned, at this point in the example, you only have one thread that is runnable, so the OS will pick the t1 thread.


And ... the original question doesn't give the possible answers, so can't discuss the parts about C, D, E, etc. as we don't know what they are...

Henry

[Amit Ramesh]

Henry,

Thank yo so much for this. I forgot that once a thread attempts to obtain a lock, and cannot do so, it goes into blocked/waiting state, until the lock is released.
Therefore, the nameless thread would go into blocked/waiting state until Stubborn class lock is released.
Stubborn class lock will be released after t1 prints 5 4 3 2 1. Then nameless thread will get the class lock and print 0. So C is correct. It makes sense now why the others are incorrect.

These were the original answers to choose from:
Which are true? (Choose all that apply.)
A. Compilation fails. //incorrect
B. The output is 5 4 3 2 1 //incorrect because when second thread obtains the class lock, it will run and print 0.
C. The output is 5 4 3 2 1 0 //correct
D. The program could deadlock. //program cannot deadlock. t1 holds its lock until it is done, releases it and ends. then second thread obtains lock and runs.
E. The output could be 5, followed by deadlock. //no because t1 will keep the lock while it sleeps. when it wakes, it will still hold the lock and will continue.
F. If the sleep() invocation was removed, the chance of deadlock would decrease. //incorrect, because there is no possibility of deadlock
G. As it stands, the program can’t deadlock, but if shove() was changed to synchronized, then the program could deadlock. //incorrect because the code inside shove() is already synchronized.

[Henry Wong]

Amit Ramesh,

Normally, I think followup questions are a good idea. After all, you got an answer, and it flows to the next question. However, in this case, keep in mind that you are not the OP for the topic, so please do not detour the topic.

Anyway, your post was moved to a new topic.
(This informational message will self destruct in two days)


Also, thanks for posting the choices for the original question. Have a cow.

Henry