I have just gotten out of yet another interview with a “senior” Java candidate who doesn’t know threading at all. Please don’t claim you are a senior candidate unless you can answer this basic question.
public class Foo {
public static final Foo INSTANCE_1 = new Foo();
public static final Foo INSTANCE_2 = new Foo();
public static synchronized method1() { /* really long execution */ }
public synchronized method2() { /* really long execution */ }
public static method3() { /* really long execution */ }
public method4() { /* really long execution */ }
public static synchronized method5() { /* really long execution */ }
public synchronized method6() { /* really long execution */ }
}
Now pretend that there are these threads running on a 64000-core machine. Each thread, at the exact same picosecond, makes a call to the method listed:
| Thread | Method call |
|---|---|
| Thread 101 | Foo.INSTANCE_1.method1(); |
| Thread 102 | Foo.INSTANCE_1.method2(); |
| Thread 103 | Foo.INSTANCE_1.method3(); |
| Thread 104 | Foo.INSTANCE_1.method4(); |
| Thread 105 | Foo.INSTANCE_1.method5(); |
| Thread 106 | Foo.INSTANCE_1.method6(); |
| Thread 111 | Foo.INSTANCE_1.method1(); |
| Thread 112 | Foo.INSTANCE_1.method2(); |
| Thread 113 | Foo.INSTANCE_1.method3(); |
| Thread 114 | Foo.INSTANCE_1.method4(); |
| Thread 115 | Foo.INSTANCE_1.method5(); |
| Thread 116 | Foo.INSTANCE_1.method6(); |
| Thread 201 | Foo.INSTANCE_2.method1(); |
| Thread 202 | Foo.INSTANCE_2.method2(); |
| Thread 203 | Foo.INSTANCE_2.method3(); |
| Thread 204 | Foo.INSTANCE_2.method4(); |
| Thread 205 | Foo.INSTANCE_2.method5(); |
| Thread 206 | Foo.INSTANCE_2.method6(); |
| Thread 211 | Foo.INSTANCE_2.method1(); |
| Thread 212 | Foo.INSTANCE_2.method2(); |
| Thread 213 | Foo.INSTANCE_2.method3(); |
| Thread 214 | Foo.INSTANCE_2.method4(); |
| Thread 215 | Foo.INSTANCE_2.method5(); |
| Thread 216 | Foo.INSTANCE_2.method6(); |
| Thread 301 | new Foo(){ }.method1(); |
| Thread 302 | new Foo(){ }.method2(); |
| Thread 303 | new Foo(){ }.method3(); |
| Thread 304 | new Foo(){ }.method4(); |
| Thread 305 | new Foo(){ }.method5(); |
| Thread 306 | new Foo(){ }.method6(); |
Questions:
- Now which threads will block each other and why?
- Where are locks stored? (The JVM has to store the information some place!)
- What is a deadlock?
- When do deadlocks occur? Does the above code experience a deadlock?
No, the answer is not going to be given.
This post is labeled Part 1 because there will be more rants in this area I am sure!
Update: 12 April 2011: more detailed!
I’m not a java guy so short answer: I don’t know. Best guess would be any threads that call a synchronized method on the same instance would block each other. Then again the static synchronized methods afaik use a different lock (lock on the class versus lock on the object instance). Deadlock occurs with a shared resource and a circular wait. Could these exist since the Foo class contains members which themselves are Foo? Educate me?
Question 1.
When a thread invokes a (non static) synchronized method, it automatically acquires the intrinsic lock for that method’s object and releases it when the method returns.
In the example above, method2 and method6 are non static synchronized methods. Thus we have the following 2 groups of threads that block each other:
– Group 1: Threads 102, 106, 112 and 116
– Group 2: Threads 202, 206, 212 and 216
When static synchronized methods are invoked, and since a static method is associated with a class, the threads acquire the intrinsic lock for the Class object associated with the class. Thus access to class’s static fields is controlled by a lock that’s distinct from the lock of any instance of the class.
In the example above, method1 and method5 are static synchronized methods. Thus we have the following group of threads that block each other:
Threads 101, 105, 111, 115, 201, 205, 211, 215, 301 and 305.
Question 2.
I don’t know really the answer to this question, but I believe that the JVM stores the locks in memory.
Question 3.
In Java, deadlocks occur when two threads each hold an exclusive lock that the other thread needs in order to continue. In principle, there could actually be more threads and locks involved. It is generally liable to occur when threads acquire the same locks in different orders.
Question 4.
In theory, deadlock situations can arise if one of the following conditions hold simultaneously in a system:
– Mutual Exclusion
– Hold and Wait
– No Preemption
– Circular Wait
For example, lets consider the following class Counter:
class Counter {
private int c = 0;
public void increment() {
c++;
}
public int value() {
return c;
}
}
When two increment operations run in different threads, but acting on the same data, they might interleave. This means that the increment() method consist of multiple steps,
and the sequences of steps might overlap producing inconsistent data.
For example, the single expression c++ could be decomposed into three steps:
1. Retrieve the current value of c.
2. Increment the retrieved value by 1.
3. Store the incremented value back in c.
If the two threads execute the increment method at the same time, the resulting value of c could be 1 or 2.
In the initial example, deadlock might occur if method2, method4 and method6 of the class Foo share resources, because method3 does not acquire a lock for accessing a critical area where resources are shared.
First of all let me say thank you for the good question 🙂
In order to answer these questions one should understand how locks work for different cases:
Case1: method is neither synchronized nor static = no locking, subject to race conditions.
Case2: method is static and not synchronized = same here, no locking and race conditions.
Case3: method is synchronized and not static = different threads sequentially acquire/release locks on the object instance (INSTANCE_1 or INSTANCE_2). Two threads can execute method on different instances in parallel.
Case4: method is synchronized and static = In this case locking is imposed on class rather than instance. That means that different threads executing same static method (even on different instances) will acquire/release lock sequentially.
Having that said, let me answer your questions:
Now which threads will block each other and why?
— Threads that invoke non-static synchronized methods (method2 and method6) on INSTANCE_1 will block each other:
— Threads that invoke non-static synchronized methods (method2 and method6) on INSTANCE_2 will block each other;
— Threads that invoke static synchronized methods (method1 and method5) on any instance will block each other;
Where are locks stored? (The JVM has to store the information some place!)
— Lock is stored in java.lang.Object
What is a deadlock?
— Situation when several threads can’t proceed because they are waiting for each other to release some lock.
When do deadlocks occur? Does the above code experience a deadlock?
— This may be due to the different sequence of lock acquisition.
(e.g. Thread1 locks A then B and thread2 locks B then A). In our example if all the threads do is invocation of 1 method then answer is no.
Cheers!
Ans 1) All the thread which call the method3 (Thread 103 , Thread 113 , Thread 203 , Thread 213 , Thread 303 ) block each othere because method3 is static means one existence for every thread .
Ans 2) In the main memory.
Ans 3) Deadlock is a situation where 2 or multiple thread are waiting for each other work completion.
Ans 4) Dead locks occue when 2 or multiple thread are waiting to complete each other work . this code did not experience a deadlock situation.