What is deadlock and solution to it?

Answer 1

A deadlock occurs in multi-threaded applications whenever a thread attempts to acquire a lock that can never be unlocked. Locks are necessary in order to prevent concurrent threads from accessing a shared resource while that resource is being modified. Once a thread acquires a lock, all others must wait until the lock is released. In order to prevent any unnecessary waiting, it is vital that each thread acquire a lock immediately before operating upon a shared resource, and to immediately release that lock as soon as it has finished with the resource.

Sometimes it is necessary to operate upon two (or more) resources. Ideally, those resources would be combined into a single resource with just one lock, but it is not unusual to have independent resources that are only occasionally dependant upon each other, so it makes sense to keep them as independent as possible and apply the dependency only when it is actually needed.

When we need to create a dependency to perform an operation it is vital that all the independent locks be applied in the same sequence, regardless of which order the operations must be performed. This means that we may end up holding onto locks far longer than is strictly necessary, but it is the only way to prevent a deadlock.

For example, if we have two threads, A and B, and two resources, X and Y, such that A acquires X followed by Y while B acquires Y followed by X, then we could easily end up in the situation where A acquires X while B acquires Y. A is now waiting for B to release Y, but B is waiting for A to release X. They are deadlocked. Had they both acquired X and Y in the same order, the deadlock would have been avoided.

Another situation where a deadlock often occurs is when a recursive function acquires a lock but doesn't release that lock before calling itself. The new instance cannot lock the resource because it is already locked, thus the function has deadlocked itself. The solution to that problem is to use a recursive lock rather than an ordinary lock, thus allowing a single thread to acquire the lock as often as required. Once a recursive lock is acquired, each subsequent lock by the same thread increments an internal counter while each unlock decrements that counter. When the count is zero the lock is released.