1、死锁场景

🤪

举例场景：两个憨憨Tom和Sam去西餐厅吃牛排，桌子上只有一把刀和一把叉，Tom先拿到了叉子，Sam拿到了刀。只有同时拿到刀叉才能吃牛排，于是两个憨憨陷入如下的僵局。

这个场景中，就存在死锁形成的条件：

✍️

互斥条件：一张桌子上只有一把餐刀和一把叉子，且只能由一个人同时使用。Tom和Sam需要同时拿到餐刀和叉子才能吃饭，他们不能共享餐具。餐刀和叉子是资源，它们只能由一个人独占使用，另一个人必须等待餐具的释放。

✍️

请求与保持条件：Sam已经拿到了餐刀，但还在等待拿到叉子；同时，他不会放下已经拿到的餐刀。Tom已经拿到了叉子，但在等待餐刀，也不会先放下叉子。Sam拥有一部分资源（餐刀），并且在等待另一部分资源（叉子），而Tom则持有叉子，等待餐刀。这导致两个人都无法继续用餐

✍️

不剥夺条件：一旦一个人拿到了餐刀或叉子，另一个人不能强行夺走它，必须等第一个人自愿放下餐具。

✍️

循环等待条件：Sam拿着餐刀，等待叉子，而Tom拿着叉子，等待餐刀。这样就形成了一个循环：Tom等待Sam释放资源，Sam等待Tom释放资源，两者都陷入了无限等待的状态。

2、死锁形成的原因

形成死锁有四个必要条件，分别是：

互斥条件（Mutual Exclusion）：资源是独占的，即某个资源一次只能被一个线程持有。如果有其他线程请求资源，就必须等待。
请求与保持条件（Hold and Wait）：一个线程已经持有了一个资源，并且还在等待获取其他线程持有的资源，而不释放它已占有的资源。
不剥夺条件（No Preemption）：已经获得的资源在未使用完之前不能被强制剥夺，只能由持有该资源的线程主动释放。
循环等待条件（Circular Wait）：存在一个线程等待的循环链，每个线程都在等待下一个线程所持有的资源，从而形成了一个闭环。

3、如何预防死锁

接着看怎么来解决这两个憨憨的吃饭问题。

3.1 破坏互斥条件

第一种避免死锁的方法就是破坏互斥条件：通过增加资源的数量（例如多备几套餐具），可以避免资源独占，从而打破互斥条件。现实中，可以通过增加并行资源或共享资源的方式来减少死锁的可能性。

3.2 破坏请求与保持条件

第二种避免死锁的方法就是破坏请求与保持条件：规定每个人必须在没有拿任何餐具的时候，先一次性拿好所需的餐刀和叉子。如果他发现没有足够的餐具可用（例如只剩餐刀或叉子），他必须先放下自己手中的餐具，等待下一轮再尝试拿齐。

这种方法避免了“请求与保持”，要求在拥有资源之前确保拿到所有需要的资源。如果无法一次性拿到，必须释放已经持有的资源，这样不会出现资源的相互依赖。

3.3 破坏不剥夺条件

第三种预防死锁的方式就是破坏不剥夺条件：设定一个规则，如果某个人在拿到餐刀后长时间没有拿到刀，就必须自动放下餐具，以便其他人使用。

这种方式打破了不剥夺条件，使资源能够被强制释放。对于计算机系统，可以通过设置超时机制或者资源预占的方式来避免死锁。例如，当一个线程长时间占有资源而没有完成任务时，可以强制回收资源，让其他线程使用。

3.4 破坏循环等待条件

第四种预防死锁的方式就是破坏循环等待条件：规定用餐时必须按照固定顺序拿餐具，例如每个人必须先拿叉，再拿刀。这样，就不会出现两个人一个拿刀一个拿叉、互相等待的情况。

通过规定资源获取的顺序，可以避免形成环形依赖链。在计算机系统中，也可以通过全局的资源顺序策略，确保线程在请求多个资源时，必须按照固定的顺序请求，从而避免循环等待。

4、如何避免死锁

银行家算法是一种资源分配和死锁避免算法，主要用于确保在多个进程并发运行时系统不会进入不安全状态。以下是其原理和实现的详细介绍。

4.1 原理

安全状态与不安全状态：
- 系统在资源分配时要确保处于安全状态。如果有一种资源分配方式，能够保证所有进程最终都能完成，那么系统就是安全的。
- 如果不能找到这样的分配方式，系统则处于不安全状态。
请求与分配：
- 每个进程在运行时会声明其最大资源需求（最大资源向量）。
- 进程在执行期间会请求资源。算法会检查这个请求是否会导致系统进入不安全状态。
资源分配步骤：
- 当一个进程请求资源时，算法会进行以下检查：
  1. 检查请求是否小于或等于最大需求。
  2. 检查请求是否小于或等于当前可用资源。
  3. 假设资源被分配给该进程，检查系统是否依然安全。
- 如果所有检查都通过，资源将被分配；否则，进程需要等待。

4.2 实现

以下是一个简单的银行家算法的实现思路：

数据结构：
- max[][]：每个进程的最大需求。
- allocation[][]：当前已分配给每个进程的资源。
- need[][]：每个进程还需要的资源，need[i][j] = max[i][j] - allocation[i][j]。
- available[]：当前可用的资源。

算法步骤：

public boolean requestResources(int processID, int[] request) {
    // 1. 检查请求是否有效
    for (int i = 0; i < resources.length; i++) {
        if (request[i] > need[processID][i] || request[i] > available[i]) {
            return false; // 请求无效
        }
    }

    // 2. 假设分配资源
    for (int i = 0; i < resources.length; i++) {
        available[i] -= request[i];
        allocation[processID][i] += request[i];
        need[processID][i] -= request[i];
    }

    // 3. 检查系统安全性
    if (isSafe()) {
        return true; // 资源分配成功
    } else {
        // 4. 回滚
        for (int i = 0; i < resources.length; i++) {
            available[i] += request[i];
            allocation[processID][i] -= request[i];
            need[processID][i] += request[i];
        }
        return false; // 资源分配失败
    }
}

private boolean isSafe() {
    boolean[] finish = new boolean[numProcesses];
    int[] work = available.clone();
    int count = 0;

    while (count < numProcesses) {
        boolean found = false;
        for (int i = 0; i < numProcesses; i++) {
            if (!finish[i] && canProceed(i, work)) {
                for (int j = 0; j < resources.length; j++) {
                    work[j] += allocation[i][j];
                }
                finish[i] = true;
                found = true;
                count++;
            }
        }
        if (!found) break; // 无法找到可以执行的进程
    }

    // 如果所有进程都完成，则安全
    return count == numProcesses;
}

private boolean canProceed(int processID, int[] work) {
    for (int i = 0; i < resources.length; i++) {
        if (need[processID][i] > work[i]) {
            return false;
        }
    }
    return true;
}