Deadlocking

Understanding Locks

In Java, Lock is an interface available in the Java.util.concurrent.locks package. Java lock acts as thread synchronization mechanisms that are similar to the synchronized blocks.

When threads in a process share and update the same data, their activities must be synchronized to avoid errors. In Java, this is done with the "synchronized" keyword, or with wait and notify. Synchronization is achieved by the use of locks, each of which is associated with an object by the JVM (Java Virtual Machine). For a thread to work on an object, it must have control over the lock associated with it, it must "hold" the lock. Only one thread can hold a lock at a time. If a thread tries to take a lock that is already held by another thread, then it must wait until the lock is released. When this happens, there is so called "contention" for the lock.
There are four kinds of locks:

• Fat Locks: A fat lock is a lock with a history of contention (several threads trying to take the lock simultaneously), or a lock that has been waited on.

• Thin Locks: A thin lock is a lock that does not have any contention.

• Recursive Locks: A recursive lock is a lock that has been taken by a thread several times without having been released.

• Lazy Locks: A lazy lock is a lock that is not released when a 'critical section' is excited. Once a lazy lock is acquired by a thread, other threads that try to acquire the lock have to ensure that the lock is, or can be, released.

Spinning and Sleeping

Spinning occurs when a thread that wants a specific lock continuously checks that lock to see if it is still taken, instead of yielding CPU-time to another thread.
Alternatively, a thread that tries to take a lock that is already held waits for notification from the lock and goes into a sleeping state. The thread will then wait passively for the lock to be released.

Lock Chains

Several threads can be tied up in what is called lock chains. Although they appear somewhat complex, lock chains are fairly. They can be defined as follows:

• Threads A and B form a lock chain if thread A holds a lock that thread B is trying to take. If A is not trying to take a lock, then the lock chain is 'open'.
• If A->B is a lock chain, and B->C is a lock chain, then A->B->C is a more complete lock chain.
• If there is no additional thread waiting for a lock held by C, then A->B->C is a complete and open lock chain.

Lock Chain Types

There are three possible kinds of lock chains: open, Deadlock and Blocked lock chains.

Open Chains

Open lock chains represent a straight dependency, thread A is waiting for B which is waiting for C, and so on. If we have long open lock chains, the application might be wasting time waiting for locks. We then want to consider how locks are used for synchronization in the application.

Deadlock Chains

A deadlocked, or circular, lock chain consists of a chain of threads, in which the first thread in the chain is waiting for the last thread in the chain. In the simplest case, thread A is waiting for thread B, while thread B is waiting for thread A.
"A deadlocked chain has no head."

Blocked Chains

A blocked lock chain is made up of a lock chain whose head thread is also part of another lock chain, which can be either open or deadlocked.