死锁

1. 死锁的基本概念

1.1. 定义

一组进程死锁（deadlock）：一组进程中的每个进程都的在等待仅由该组进程中的其它进程才能引发的事件的状态。

1.2. 产生死锁的四个必要条件

  • 互斥条件：进程对所分配到的资源进行排他性使用
  • 请求和保持条件：进程已经至少保持一个资源，同时又提出对已被其他进程占用的资源的请求
  • 不可抢占条件：进程已获得资源不可被抢占
  • 循环等待条件：存在一个进程——资源的循环链

2. 预防死锁

破坏后三个条件

2.1. 破坏「请求和保持」条件

保证当一个进程在请求资源时，不能持有不可抢占资源。

第一种协议

所有进程开始运行之前，必须一次性申请其在整个运行过程中所需的全部资源。

优点是简单易行且安全，缺点是资源严重浪费且进程经常饥饿。

第二种协议

允许一个进程只获得运行初期所需的资源后便开始运行，进程运行过程中逐步释放分配给自己且已用毕的全部资源，再请求新的所需资源。

2.2. 破坏「不可抢占」条件

当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时重新申请。

缺点是实现复杂，容易造成前后两次运行不连续。

2.3. 破坏「循环等待」条件

对系统所有资源类型进行线性排序，并赋予不同的序号，规定每个进程必须按序号递增的顺序请求资源。当需要请求一个低序号的资源时，要先释放高序号的资源。

优点是资源利用率和系统吞吐量都较高，缺点是限制添加新设备、作业实际使用各类资源的顺序与标号顺序不一致、用户和程序申请各类资源的顺序与标号顺序不一致。

3. 避免死锁

3.1. 系统安全状态

若系统能按照某种推进顺序（P1,P2,...,Pn）为每个进程 Pi 分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成，其中（P1,P2,...,Pn）为安全序列。若系统找到一个安全序列并按此分配资源，则系统处于安全状态，否则系统处于不安全状态。

3.2. 银行家算法

数据结构

  • 可利用资源向量 Available：含有 m 个元素，其中每个元素代表一类可利用的资源数目
  • 最大需求矩阵 Max：是个 n*m 矩阵，代表系统中 n 个进程，每个进程对 m 类资源的最大需求量
  • 分配矩阵 Allocation：是个 n*m 矩阵，代表系统中每类资源当前分配给每个进程的资源数
  • 需求矩阵 Need：是个 n*m 矩阵，代表系统中每个进程尚需的各类资源数

银行家算法

设 Requesti 是进程 Pi 的请求向量，Request i [j] = K 表示进程 Pi 需要 K 个 Rj 类型资源，则系统按照以下步骤检查

  1. 若 Request i [j] ≤ Need[i,j]，则转向2；否则出错，进程需要的资源数超过其宣布的最大值
  2. 若 Request i [j] ≤ Available[j]，转向3；否则尚无足够资源，Pi 须等待
  3. 系统试探着把资源分配给进程 Pi，并修改数据结构中的数值
    • Available[j] -= Requesti[j]
    • Allocation[i,j] += Requesti[j]
    • Need[i,j] -= Requesti[j]
  4. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态，若安全，则系统正式把资源分配给进程 Pi；否则本次试探作废，恢复数据结构中的数值

安全性算法

  1. 设置两个向量

    • 工作向量 Work：含有 m 个元素，表示系统可提供给进程继续运行所需的各类资源数目，执行安全算法开始时，Work=Available
    • Finish：表示系统是否有足够的资源分配给进程，初始值为 false，当有足够资源分配给进程时，令 Finish[i] = true

  2. 从进程集合中找到一个满足一下条件的进程

    • Finish[i] = false
    • Need[i,j] ≤ Work[i]

    若找到，则执行3；否则执行4

  3. 当 Pi 进程获得资源并顺利执行至完成，释放出分配给它的资源，故执行

    • Work[j] = Work[j] + Allocation[i,j]
    • Finish[i] = true
    • 转到2

  4. 若所有进程的 Finish[i] = true 都满足，则系统处于安全状态；否则系统处于不安全状态

4. 死锁的检测与解除

4.1. 死锁检测

死锁定理

资源分配图的节点为 N，变为 E。进程节点 P={P1,P2,...,Pn}，资源节点 R={R1,R2,...,Rm}，N=PUR。e={Pi,Rj}表示资源请求，e={Rj,Pi}表示资源分配，E 为 e 的集合。

在资源分配图中，找出一个即不阻塞又非独立的进程节点 Pi，在顺利的情况下 Pi 可获得所需资源而继续运行至完毕，并释放其所占有的全部资源（相当于去 Pi 的请求边和分配边）。按同样的方法简化资源分配图至不能再简化。

S 为死锁状态的充分条件为：当且仅当 S 状态的资源分配图是不完全简化的。

死锁检测数据结构

Work=Available;
L={Li|Allocation_i=0 && Request_i=0};

for(all Li not in L){
    for(all Request_i <= Work){
        Work+=Allocation_i;
        Li add to L;
    }
}
deadlock=(L={P1,P2,...,Pn});

4.2. 死锁解除

常用解除死锁的方法有抢占资源和终止进程。

付出代价最小的死锁解除算法

  • 从死锁状态 S 中先终止一个死锁进程 P1，是状态演变为 U1，将 P1 记入终止进程的集合 d(T)，把所付出代价 C1 加入 Rc(T) 中。
  • 对 P2,P3...重复上述操作，得到状态 U1,U2,...,Un 后，选择由 S 状态演变代价最小的状态 Ui，终止相应进程 Pi。
  • 若死锁仍未解除，则将 Ui 状态作为新的 S 状态，直至死锁解除。

5. ChangeLog

2018.08.28 初稿

results matching ""

    No results matching ""