Writing multi-threaded applications in Java can as you know be quite tricky, and if not done correctly, one can easily end up with deadlock situations. For example, take a look at this little code snippet. This piece of Java code implements a Node, which has three methods (that is of our interest):
Here's the implementation:This class might look okay, but it actually suffers from potential deadlock. For example what happens if, one thread T1 invokes n1.swap(n2) while an other one T2 concurrently invokes n2.swap(n1) ? Thread T1 acquires the lock for node n1, and thread T2 acquires the lock for node n2. Thread T1 now invokes n2.get() (in the swap(..) method). This invocation now has to wait since node n2 is locked by thread T2, this while the reverse holds for thread T2 (e.g. it needs to wait for node n1 which is locked by thread T1). Which means that we have a deadlock.
This program is however easily fixed by using the technique of totally ordering all objects in the system.
In this program, all locks will be acquired in increasing order, guaranteed to be the same for all threads, and thereby avoiding deadlock situations.