死锁

死锁（Deadlock）描述的是这样一种情况：多个进程/线程同时被阻塞，它们中的一个或者全部都在等待某个资源被释放。由于进程/线程被无限期地阻塞，因此程序不可能正常终止。

必要条件

  • 互斥条件：每个资源只能由一个进程占用。其他进程想要获取该资源时，需要阻塞等待。
  • 持有并等待条件：一个进程已经持有至少一个资源，并且正在等待获取一个被其他进程占有的资源。
  • 不可抢占条件：资源不能被强制性地从一个进程中剥夺，只能由持有它的进程显式地释放。
  • 环路等待条件：存在一个进程集 {P1, P2, …, Pn}，其中 P1 等待 P2 占有的资源，P2 等待 P3 占有的资源，…，Pn 等待 P1 占有的资源，形成一个环。

解决方法

预防

预防死锁的关键是破坏上述四个条件中的一个。
破坏 互斥条件：使得资源是可以同时访问的，这是种简单的方法，但很显然有很多资源往往是不能同时访问的 ，会存在安全风险，所以这种做法在大多数的场合是行不通的。
破坏持有并等待条件：在进程开始时一次性请求所有资源，或者在进程请求资源时，不占有任何资源。但很进程运行过程中资源消耗时间可能相隔很久，而这段时间资源却始终无法被其他进程使用，这导致资源利用率下降。
破坏 不可抢占条件：也就是剥夺式调度算法，但剥夺式调度方法可能导致进程间互相抢夺资源，会导致资源利用率下降。
破坏环路等待条件：对资源进行全局排序，进程必须按照顺序请求资源，防止形成环。

避免

通过资源分配算法来避免死锁，其中最著名的是银行家算法（Banker’s Algorithm），它在资源分配之前检查系统状态，确保不会进入不安全状态。算法的步骤如下：

  1. 初始化：输入总资源数量、各进程的最大需求和当前分配的资源，计算每个进程的剩余需求和系统的可用资源。
  2. 资源请求：当一个进程请求资源时，首先检查请求是否小于或等于其最大需求以及系统的可用资源。
  3. 试探性分配：如果资源请求合理，试探性地分配资源，即暂时将资源分配给进程，并更新相应的数据结构（可用资源、已分配资源和剩余需求）。
  4. 安全性检查：调用安全性算法，检查系统是否处于安全状态。如果系统仍然处于安全状态，正式分配资源；否则，回滚试探性分配。
  5. 恢复：如果系统不安全，撤销试探性分配，并通知进程等待资源。

检测

对资源的分配加以限制可以预防和避免死锁的发生，但是都不利于各进程对系统资源的充分共享。
死锁的检测与解除对资源的分配不加以任何限制，也不采取死锁避免措施，但系统定时地运行一个 “死锁检测” 的程序，判断系统内是否出现死锁，如果检测到系统发生了死锁，再采取措施去解除它。

解除

一旦检测到死锁，可以通过以下方法解除：

  1. 终止进程：终止部分或所有陷入死锁的进程。
  2. 资源剥夺：强制性从部分进程中剥夺资源，并将这些资源分配给其他进程，以解除死锁。

代码模拟死锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class deadLock {  
    private static final Object lock1 = new Object();  
    private static final Object lock2 = new Object();  
  
    public static void main(String[] args) {  
        Thread thread1 = new Thread(() -> {  
           synchronized (lock1){  
               System.out.println("Thread1 get Lock1");  
  
               try{  
                  Thread.sleep(1000);  
               }catch (InterruptedException e){  
                   e.printStackTrace();  
               }  
               System.out.println("Thread1 waiting for Lock2");  
               synchronized (lock2){  
                   System.out.println("Thread1 get Lock2");  
               }  
           }  
        });  
        Thread thread2 = new Thread(() -> {  
            synchronized (lock2){  
                System.out.println("Thread2 get Lock2");  
  
                try{  
                    Thread.sleep(1000);  
                }catch (InterruptedException e){  
                    e.printStackTrace();  
                }  
                System.out.println("Thread2 waiting for Lock1");  
                synchronized (lock1){  
                    System.out.println("Thread2 get Lock1");  
                }  
            }  
        });  
  
        thread1.start();  
        thread2.start();  
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {
	var lock1, lock2 sync.Mutex

	// 启动第一个协程
	go func() {
		lock1.Lock()
		fmt.Println("Goroutine 1: locked lock1")

		// 模拟一些工作
		time.Sleep(1 * time.Second)

		fmt.Println("Goroutine 1: attempting to lock lock2")
		lock2.Lock()
		fmt.Println("Goroutine 1: locked lock2")

		// 释放锁
		lock2.Unlock()
		lock1.Unlock()
	}()

	// 启动第二个协程
	go func() {
		lock2.Lock()
		fmt.Println("Goroutine 2: locked lock2")

		// 模拟一些工作
		time.Sleep(1 * time.Second)

		fmt.Println("Goroutine 2: attempting to lock lock1")
		lock1.Lock()
		fmt.Println("Goroutine 2: locked lock1")

		// 释放锁
		lock1.Unlock()
		lock2.Unlock()
	}()

	// 等待一段时间以观察死锁现象
	time.Sleep(3 * time.Second)
	fmt.Println("Main: finished")
}