A deadlock

Deadlock refers to the phenomenon that two or more processes (threads) are blocked during execution due to competition for resources or communication with each other. Without external force, neither of them can advance. At this point, the system is said to be in a deadlock state or the system has produced a deadlock, and these processes (threads) that are always waiting for each other are called deadlock processes (threads).

Four conditions necessary for deadlock to occur

  • Mutual exclusion: A thread (process) is exclusive to the allocated resource, that is, a resource can only be occupied by one thread (process) until it is released by the thread (process)
  • Request and hold condition: when a thread (process) is blocked by a request for occupied resources, it holds on to acquired resources.
  • Non-deprivation condition: a thread (process) cannot deprive the resources it has obtained by other threads before it is used up, and only release the resources after it is used up.
  • Loop wait condition: When a deadlock occurs, the waiting thread (process) must form a loop (similar to an infinite loop), causing permanent blocking

How to detect

Use jStack or JConsole to view the thread stack.

"Thread-1" prio=10 tid=0x00007fe8c00a0800 nid=0x17cc waiting for monitor entry [0x00007fe8c5031000]
   java.lang.Thread.State: BLOCKED (on object monitor)
        at DeadLocakTest$DeadThread2.run(DeadLocakTest.java:61)
        - waiting to lock <0x00000000af24b248> (a java.lang.Object)
        - locked <0x00000000af24b258> (a java.lang.Object)
        at java.lang.Thread.run(Thread.java:745)
 
   Locked ownable synchronizers:
        - None
 
"Thread-0" prio=10 tid=0x00007fe8c009e800 nid=0x17cb waiting for monitor entry [0x00007fe8c5132000]
   java.lang.Thread.State: BLOCKED (on object monitor)
        at DeadLocakTest$DeadThread1.run(DeadLocakTest.java:38)
        - waiting to lock <0x00000000af24b258> (a java.lang.Object)
        - locked <0x00000000af24b248> (a java.lang.Object)
        at java.lang.Thread.run(Thread.java:745)
 
   Locked ownable synchronizers:
        - None

Copy the code

Thread-1

locked <0x00000000af24b258>

waiting to lock 0x00000000af24b248

Thread-0

locked 0x00000000af24b248

waiting to lock 0x00000000af24b258

How to solve

  • Break request and hold conditions: request all resources at once.
  • Destruct the non-deprivation condition: when a thread that occupies a part of a resource applies for other resources, it can actively release the resources it occupies if it fails to apply for other resources.
  • Break the cyclic wait condition: apply for resources in order and release resources in reverse order.

Live lock

A live lock is when a task or performer is not blocked, and because some condition is not met, it keeps trying, failing, trying, failing. The difference between a live lock and a deadlock is that an entity in a live lock is in a state of constant change, called “live”, while an entity in a deadlock is waiting. Live locks may release themselves; deadlocks do not.

Some randomness can be introduced to resolve live locks, such as suspending for a random amount of time to retry if a conflict is detected. This greatly reduces the likelihood of a collision. A typical example is Ethernet’s CSMA/CD detection mechanism.

Lock the hunger

Hunger: if thread T1 occupies resource R and thread T2 requests to block R, then thread T2 waits. T3 also requests resource R. When T1 releases the block on R, the system first approves T3’s request, and T2 still waits. T4 then requests a lockdown on R, and when T3 releases the lockdown on R, the system approves T4’s request… T2 could wait forever.