【操作系统】死锁

一、做题！资源分配问题（计算类）

1. 最小死锁条件计算

2. 死锁进程数判定

案例：3设备4进程
结论：最少需要3个进程形成循环等待链才会死锁

二、必背！死锁处理策略对比

1. 三大解决策略

2. 死锁预防具体措施-破坏四大必要条件

3. 死锁避免-避免系统处于不安全状态

银行家算法：当申请资源时，系统会预分配并检查预分配后是否是安全状态。

我也不背代码，遇到题目现推：5个苹果，分了3个，还剩2个，如果有人释放1个，那么现在还有3个能分，以此类推。

/**
 * 银行家算法实现类
 */
class BankersAlgorithm {
            
  /**
   * @param {number} processCount - 进程数量
   * @param {number} resourceCount - 资源类型数量
   * @param {number[][]} maxDemand - 最大需求矩阵 [进程][资源]
   * @param {number[][]} allocation - 已分配矩阵 [进程][资源]
   * @param {number[]} available - 可用资源向量
   */
  constructor(processCount, resourceCount, maxDemand, allocation, available) {
            
    this.processCount = processCount;
    this.resourceCount = resourceCount;
    this.max = maxDemand;
    this.allocation = allocation;
    this.available = [...available];
    // 计算需求矩阵 = 最大需求 - 已分配
    this.need = maxDemand.map((proc, i) => 
      proc.map((res, j) => res - allocation[i][j])
    );
    this.safeSequence = [];
  }

  /**
   * 检查当前系统状态是否安全
   * @returns {boolean|number[]} 安全序列数组或false
   */
  isSafe() {
            
    const work = [...this.available];
    const finish = new Array(this.processCount).fill(false);
    this.safeSequence = [];

    // 尝试找到可以完成的进程
    let found;
    do {
            
      found = false;
      for (let i = 0; i < this.processCount; i++) {
            
        // 检查进程是否未完成且需求可满足
        if (!finish[i] && this.canFulfill(i, work)) {
            
          // 模拟释放资源
          for (let j = 0; j < this.resourceCount; j++) {
            
            work[j] += this.allocation[i][j];
          }
          finish[i] = true;
          this.safeSequence.push(i);
          found = true;
        }
      }
    } while (found);

    // 检查所有进程是否完成
    return finish.every(f => f) ? this.safeSequence : false;
  }

  /**
   * 检查资源请求是否安全
   * @param {number} processId - 请求进程ID
   * @param {number[]} request - 请求资源向量
   * @returns {boolean} 是否允许分配
   */
  requestResources(processId, request) {
            
    // 1. 检查请求是否超过需求
    for (let j = 0; j < this.resourceCount; j++) {
            
      if (request[j] > this.need[processId][j]) {
            
        console.error(`错误：进程${
              processId}请求超过最大需求`);
        return false;
      }
    }

    // 2. 检查请求是否超过可用资源
    for (let j = 0; j < this.resourceCount; j++) {
            
      if (request[j] > this.available[j]) {
            
        console.error(`错误：进程${
              processId}请求超过可用资源`);
        return false;
      }
    }

    // 3. 尝试分配资源
    for (let j = 0; j < this.resourceCount; j++) {
            
      this.available[j] -= request[j];
      this.allocation[processId][j] += request[j];
      this.need[processId][j] -= request[j];
    }

    // 4. 检查分配后是否安全
    const isSafe = this.isSafe();
    if (!isSafe) {
            
      // 回滚分配
      for (let j = 0; j < this.resourceCount; j++) {
            
        this.available[j] += request[j];
        this.allocation[processId][j] -= request[j];
        this.need[processId][j] += request[j];
      }
      console.warn(`警告：分配给进程${
              processId}会导致系统不安全`);
    }
    return !!isSafe;
  }

  /**
   * 检查当前工作资源能否满足进程需求
   * @private
   */
  canFulfill(processId, work) {
            
    return this.need[processId].every((res, j) => res <= work[j]);
  }
}

// ================= 测试用例 =================
// 示例系统状态（3个进程，4类资源）
const processCount = 3;
const resourceCount = 4;

// 最大需求矩阵
const maxDemand = [
  [3, 1, 4, 2],
  [2, 5, 1, 3],
  [4, 2, 3, 1]
];

// 已分配矩阵
const allocation = [
  [1, 0, 2, 1],
  [0, 2, 1, 0],
  [1, 0, 1, 1]
];

// 可用资源
const available = [1, 2, 0, 1];

// 初始化银行家算法
const banker = new BankersAlgorithm(
  processCount, 
  resourceCount, 
  maxDemand, 
  allocation, 
  available
);

// 测试1：检查初始状态安全性
const safeSeq = banker.isSafe();
console.log('安全序列:', safeSeq || '不安全');

// 测试2：进程1请求资源 [1, 0, 0, 1]
const request1 = [1, 0, 0, 1];
console.log('
进程1请求[1,0,0,1]:', 
  banker.requestResources(1, request1) ? '允许' : '拒绝');

// 测试3：进程0请求资源 [2, 0, 1, 0]（超过可用）
const request2 = [2, 0, 1, 0];
console.log('进程0请求[2,0,1,0]:', 
  banker.requestResources(0, request2) ? '允许' : '拒绝');

三、临界区互斥原则

1. 四大基本原则

下列同步机制中能实现让权等待的是：信号量方法【主动放弃CPU

让权等待：进程不能进入临界时，应马上主动放开CPU，防止忙等待

2. 实现方法对比

四、结论

死锁特征：

系统死锁时必然有两个或两个以上进程会处于阻塞态
存在循环等待链
系统吞吐量骤降

银行家算法核心：

安全状态 ⇔ ∃安全序列使得: 
∀i, 已分配_i + 剩余 ≥ 最大需求_i

实际系统应用：

Linux默认采用死锁检测（OOM Killer）
数据库系统多使用超时回滚机制