目录
资源分配图（Resource Allocation Graph）：
超时和回退（Timeouts and Rollbacks）：
一、死锁的概念
死锁（Deadlock）是指在计算机科学和操作系统中的一种状态，其中两个或多个进程无法继续执行，因为每个进程都在等待其他进程释放资源，而这些资源却永远无法被释放。死锁是一种严重的系统问题，因为它导致一组进程无法继续执行，从而降低了系统的效率和可用性。
死锁通常涉及系统中的有限资源，这些资源只能由一个进程使用。这些资源可以是硬件设备（如打印机、磁盘驱动器）或软件资源（如内存、文件）。为了避免死锁，操作系统必须能够有效地管理这些资源的分配和释放。
死锁发生的条件通常包括以下四个要素，这些要素被称为死锁的必要条件：
- 互斥条件（Mutual Exclusion）： 进程对所分配到的资源具有排他性的控制权，即一次只能有一个进程使用该资源。
- 占有和等待条件（Hold and Wait）： 进程可以请求一些资源，同时保持对其他资源的控制，即进程在请求资源时不会释放已经占有的资源。
- 非抢占条件（No Preemption）： 系统不能抢占进程占有的资源，只能在进程自愿释放资源后才能重新分配。
- 环路等待条件（Circular Wait）： 存在一个等待链，使得每个进程都占有下一个进程所需的至少一种资源。
当以上四个条件同时满足时，就可能导致死锁的发生。为了解决或避免死锁，操作系统采用了各种策略，包括死锁检测、死锁避免和死锁恢复等机制。这些策略的目标是确保系统能够高效地使用资源，同时最小化或消除死锁的发生。
1、互斥条件
互斥条件指的是一种资源一次只能被一个进程占用的特性。这意味着在任何给定的时刻，一个资源只能由一个进程使用。例如，如果一个进程正在写入某个文件，其他进程就不能同时写入相同的文件。这种互斥性是确保数据完整性和避免冲突的关键。
比如下图，如果线程 A 已经持有的资源，不能再同时被线程 B 持有，如果线程 B 请求获取线程 A 已经占用的资源，那线程 B 只能等待，直到线程 A 释放了资源。
2、 占有和等待条件
占有和等待条件是指一个进程可以在等待其他资源的同时保持对某个资源的占有。换句话说，当一个进程持有一些资源时，它可以请求其他资源，并在等待这些资源时不释放它已经占有的资源。这种情况可能导致资源被长时间占用，而其他进程无法得到满足。
持有并等待条件是指，当线程 A 已经持有了资源 1，又想申请资源 2，而资源 2 已经被线程 C 持有了，所以线程 A 就会处于等待状态，但是线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。 
3、非抢占条件（No Preemption）：
- 非抢占条件表示系统不能抢占已经分配给进程的资源。即使有其他进程请求这些资源，系统也不能强制终止或剥夺当前占用资源的进程。只有在进程自愿释放资源时，资源才能被重新分配给其他进程。
不可剥夺条件是指，当线程已经持有了资源 ，在自己使用完之前不能被其他线程获取，线程 B 如果也想使用此资源，则只能在线程 A 使用完并释放后才能获取。
4、环路等待条件（Circular Wait）：
- 环路等待条件指的是系统中存在一个等待链，形成一个环路，使得每个进程都在等待下一个进程所持有的资源。例如，进程1等待进程2的资源，进程2等待进程3的资源，而进程n等待进程1的资源。这样的环路等待会导致一个循环，每个进程都无法继续执行，形成死锁。
- 比如，线程 A 已经持有资源 2，而想请求资源 1， 线程 B 已经获取了资源 1，而想请求资源 2，这就形成资源请求等待的环形图。
二、防止死锁
- 死锁预防（Deadlock Prevention）：
- 互斥条件破坏： 为了破坏互斥条件，系统可以使用可共享的资源，即多个进程可以同时访问相同的资源而不会发生冲突。例如，如果多个进程只需要读取文件而不写入，可以允许它们同时访问文件而不会发生互斥。
- 占有和等待条件破坏： 破坏占有和等待条件的方法之一是采用资源分配时立即释放占有的资源的策略，或者通过一次性请求所有需要的资源，只有当所有资源都可用时才分配给进程。
- 非抢占条件破坏： 允许系统抢占部分或全部资源，确保高优先级的进程能够及时获得所需的资源。这可能涉及到挂起低优先级的进程，以便为高优先级进程腾出资源。
- 环路等待条件破坏： 引入资源分配的顺序，为资源分配定义一个全局的顺序，确保不会形成等待环路。
- 死锁避免（Deadlock Avoidance）：
- 死锁避免是基于动态系统状态的决策，以确保系统不会进入可能导致死锁的状态。银行家算法是一种常见的死锁避免算法，通过分析每个进程的最大资源需求和当前系统可用资源来决定是否分配资源。只有在找到安全序列的情况下才会分配资源，否则会等待。
- 死锁避免的方法通常需要对系统状态进行实时监测，并在需要时作出资源分配决策，以确保系统始终处于安全状态。
- 资源分配图（Resource Allocation Graph）：
- 资源分配图是一种图形化表示，用于显示系统中进程和资源之间的关系。图中的节点表示进程和资源，边表示资源的请求和分配关系。通过检查图中是否存在环路，可以判断系统是否处于死锁状态。如果图中不存在环路，系统是安全的。
- 这种方法可以用于静态分析，也可以用于动态监测系统状态。
- 超时和回退（Timeouts and Rollbacks）：
- 当进程请求资源时，系统可以为请求设置超时期限。如果在规定的时间内未能获取所需资源，进程将回退并释放已经获得的资源，以避免潜在的死锁。
- 超时和回退的机制通常需要精确的时钟和监控，以确保超时事件能够被及时检测到并处理。
- 银行家算法（Banker's Algorithm）：
- 银行家算法是由艾兹格·迪杰斯特拉（Edsger Dijkstra）提出的一种死锁避免算法。它通过分析每个进程的最大资源需求和系统当前可用资源，判断是否存在安全序列，以确定是否可以分配资源。只有在安全状态下才会进行资源分配，否则等待。
- 银行家算法可以保证系统不会进入不安全状态，从而避免死锁的发生。然而，它要求进程在开始执行之前声明其最大资源需求，这在实际情况中可能不太实际。
- 资源描述：
- 对每种资源类型，定义总的资源数目（
total[i]）和系统当前可用的资源数目（available[i]）。
- 进程描述：
- 对每个进程，定义最大需求矩阵（
max[i][j]）、已分配资源矩阵（allocation[i][j]）和需求矩阵（need[i][j]）。
max[i][j]：进程i对资源j的最大需求。allocation[i][j]：已经分配给进程i的资源j的数量。need[i][j]：进程i仍然需要资源j的数量，即need[i][j] = max[i][j] - allocation[i][j]。
- 安全性检查：
- 在运行时，系统通过检查每个进程的需求是否小于等于系统当前可用资源来判断系统是否处于安全状态。
- 如果有一个进程无法满足其需求，则系统处于不安全状态。
- 资源分配：
- 当系统要为一个进程分配资源时，需要检查分配后系统是否仍然处于安全状态。
- 如果是，那么进行分配；否则，等待分配。
Java代码示例：
以下是一个简化的Java示例代码，演示银行家算法的基本原理：
import java.util.Scanner; public class BankersAlgorithm { private int processes; // 进程数 private int resources; // 资源类型数 private int[][] max; // 最大需求矩阵 private int[][] allocation; // 已分配矩阵 private int[][] need; // 需求矩阵 private int[] available; // 可用资源向量 public BankersAlgorithm(int processes, int resources) { this.processes = processes; this.resources = resources; this.max = new int[processes][resources]; this.allocation = new int[processes][resources]; this.need = new int[processes][resources]; this.available = new int[resources]; } public void initializeData() { Scanner scanner = new Scanner(System.in); // 输入最大需求矩阵 System.out.println("Enter the maximum demand matrix:"); for (int i = 0; i < processes; i++) { for (int j = 0; j < resources; j++) { max[i][j] = scanner.nextInt(); } } // 输入已分配矩阵 System.out.println("Enter the allocation matrix:"); for (int i = 0; i < processes; i++) { for (int j = 0; j < resources; j++) { allocation[i][j] = scanner.nextInt(); } } // 计算需求矩阵 for (int i = 0; i < processes; i++) { for (int j = 0; j < resources; j++) { need[i][j] = max[i][j] - allocation[i][j]; } } // 输入可用资源向量 System.out.println("Enter the available resources vector:"); for (int i = 0; i < resources; i++) { available[i] = scanner.nextInt(); } } public boolean isSafeState() { int[] work = available.clone(); boolean[] finish = new boolean[processes]; // 检查每个进程是否满足条件 for (int i = 0; i < processes; i++) { if (!finish[i] && isNeedLessThanOrEqualWork(i, work)) { // 如果满足条件，则分配资源并释放 for (int j = 0; j < resources; j++) { work[j] += allocation[i][j]; } finish[i] = true; i = -1; // 重新从第一个进程开始检查 } } // 如果所有进程都满足条件，则系统处于安全状态 for (boolean isFinished : finish) { if (!isFinished) { return false; } } return true; } private boolean isNeedLessThanOrEqualWork(int process, int[] work) { for (int i = 0; i < resources; i++) { if (need[process][i] > work[i]) { return false; } } return true; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("Enter the number of processes:"); int processes = scanner.nextInt(); System.out.println("Enter the number of resource types:"); int resources = scanner.nextInt(); BankersAlgorithm bankersAlgorithm = new BankersAlgorithm(processes, resources); bankersAlgorithm.initializeData(); if (bankersAlgorithm.isSafeState()) { System.out.println("The system is in a safe state."); } else { Sys
这些方法和技术可以根据系统的需求和特性选择使用，通常需要根据具体情况进行权衡和调整。死锁的防止是一个复杂而关键的问题，需要在系统设计的早期考虑，并综合考虑系统性能、资源利用率和可用性等方面的因素。
