3.4. 死锁

1. 概念

1.1. 死锁

如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞都无法向前推进的现象。

1.2. 对比

饥饿

由于长期得不到想要的资源，某进程无法向前推进的现象。

比如短进程优先算法，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。

死循环

某进程执行过程中，一直跳不出某个循环的现象。

1.3. 产生死锁的条件

互斥条件：进程互斥使用资源
占有和等待条件（请求和保持条件）：申请新资源时不释放已占有资源
不剥夺条件：一个进程不能抢夺其他进程占有的资源
环路条件：存在一组进程循环等待资源的

破坏任意一个条件即不会发生死锁。

1.4. 什么时候会发生死锁

对于系统资源的竞争，各进程对不可剥夺的资源的竞争可能引起死锁。
进程推进顺序非法。请求和释放资源的顺序不当。
信号量的使用不当。

2. 预防死锁

2.1. 破坏死锁产生条件

破坏任意一个条件即不会发生死锁。

互斥条件

把只能互斥使用的资源改造为允许共享使用。例如打印机。

不剥夺条件

当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏不可剥夺条件。

当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级。

请求和保持条件

采用静态分配方法，即进程在运行前，一次申请完他需要的全部资源。在它的资源未满足前不让他投入运行。一旦投入运行后，这些资源就一直归他所有，该进程就不会再请求别的任何资源。

循环等待条件

采用顺序资源分配法，首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源。同类资源一次申请完。

将循环队列变为顺序单向队列。

3. 避免死锁（银行家算法）

3.1. 安全序列

如果系统按照这种序列分配资源，则每个进程都能顺利完成，只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

3.2. 银行家算法

问题描述

银行家拥有一笔周转资金
客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款
银行家应谨慎的贷款，防止出现坏帐

数据结构

一个系统有 $\displaystyle{ n }$ 个进程和 $\displaystyle{ m }$ 种不同类型的资源,定义包含以下向量和矩阵的数据结构

系统中每类资源总数向量 Resource=[R1, R2, ..., Rm]
系统中每类资源当前可用数向量 Available=[V1, V2, ..., Vm]
每个进程对各类资源的最大需求矩阵 Claim[i,j]
每个进程已占有各类资源数量矩阵 Allocation[i,j]
每个进程还需各类资源数量矩阵 Need[i,j]，有 $\displaystyle{ N e e d \left[ i , j \right] = C la i m \left[ i , j \right] - A l lo ca ti o n \left[ i , j \right] }$
每个进程当前申请各类资源数量矩阵 Request[i,j]

系统若要启动一个新进程工作，其对资源 Resource[i] 即 Ri 的需求应满足不等式

R_i\geqslant Claim[(n+1),i]+\sum_{k=1}^{n}Claim[k,i],i=1,\cdots,m;k=1,\cdots,n

系统安全性定义：在时刻 $\displaystyle{ T _{ 0 } }$ 是安全的，仅当存在一个进程序列 $P_1,\cdots,P_n$ 对进程 $P_k(k=1,\cdots,n)$ 满足以下公式，才被称为安全序列。

Need[k,i]\leqslant Available[i]+\sum_{j=1}^{k-1}Allocation[j,i],i=1,\cdots,m;k=1,\cdots,n

算法步骤

如果 $Request[i,*]\leqslant Need[i,*]$ 则转步骤 2；否则出错处理
如果 $Request[i,*] \leqslant Available[*]$ 则转步骤 3；否则超出可分配量，等待
系统对 $\displaystyle{ P _{ i } }$ $P_{i}$ 请求的资源试探性分配
- $\displaystyle{ A l lo c \left[ i , \cdot \right] = A l lo c \left[ i , \cdot \right] + R e qu e st \left[ i , \cdot \right] ; }$
- $\displaystyle{ A va i l \left[ \cdot \right] = A va i l \left[ \cdot \right] - R e qu e st \left[ i , \cdot \right] ; }$
- $\displaystyle{ N e e d \left[ i , \cdot \right] = N e e d \left[ i , \cdot \right] - R e qu e st \left[ i , \cdot \right] ; }$
转向 5 执行安全性测试算法，如果安全，则承认试分配；否则抛弃试分配且等待
安全性测试算法
- 初始时安全序列为空，Work = Avail
- 从 Need 矩阵中找出符合下面的行
  - 该行对应的进程不在安全序列中，而且该行小于等于 Work 向量，找到后，把对应的进程加入安全序列
  - 若找不到，则执行步骤④
- 进程 $\displaystyle{ P _{ \left\lbrace i \right\rbrace } }$ 进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，因此应执行 $\displaystyle{ W \text{ or } k = W \text{ or } k + A l lo c \left[ i , \cdot \right] }$ ，返回步骤②
- 若此时安全序列中已有所有进程，则系统处于安全状态，否则处于不安全状态

bool checkSafety() {
    vector Work[i]; bool possible; set rest;  // 定义工作向量、布尔标志、进程集合
    Work[*] = Available[*]; possible=true;    // 初始化
    rest.push(P1, P2, ..., Pn);  // 全部进程进入 rest
    while (1) {
        pk = find(rest, query(Need[k,*]<=Work[*]));  // 找出满足的进程 Pk
        if (pk == NULL) {  // 找不到
            possible = false;  // 置否
            return;  // 停止算法
        }
        else {
            free(pk.resource);  // 释放 Pk 所占用的资源
            Work[*] = Work[*] + Allocation[k,*];
            rest.remove(pk);  // 将 Pk 从进程集合中去掉
        }
    }
    if (rest.isEmpty())
        return true;
    else
        return false;
}

bool checkSafety() {
    vector Work[i]; bool possible; set rest;  // 定义工作向量、布尔标志、进程集合
    Work[*] = Available[*]; possible=true;    // 初始化
    rest.push(P1, P2, ..., Pn);  // 全部进程进入 rest
    while (1) {
        pk = find(rest, query(Need[k,*]<=Work[*]));  // 找出满足的进程 Pk
        if (pk == NULL) {  // 找不到
            possible = false;  // 置否
            return;  // 停止算法
        }
        else {
            free(pk.resource);  // 释放 Pk 所占用的资源
            Work[*] = Work[*] + Allocation[k,*];
            rest.remove(pk);  // 将 Pk 从进程集合中去掉
        }
    }
    if (rest.isEmpty())
        return true;
    else
        return false;
}

举例

假设系统中共有5个进程 $\displaystyle{ \ \left\lbrace P _{ 0 } , P _{ 1 } , P _{ 2 } , P _{ 3 } , P _{ 4 } \ \right\rbrace }$ 和 $\displaystyle{ A , B , C }$ 三类资源，资源矩阵为 $\displaystyle{ \left[ 10 , 5 , 7 \right] }$ . 在 $\displaystyle{ T _{ 0 } }$ 时刻，系统资源分配情况如下

进程	已分配	总需求	空闲	当前需求
$\displaystyle{ P _{ 0 } }$	$\displaystyle{ \left( 0 , 1 , 0 \right) }$	$\displaystyle{ \left( 7 , 5 , 3 \right) }$	$\displaystyle{ \left( 3 , 3 , 2 \right) }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$
$\displaystyle{ P _{ 1 } }$	$\displaystyle{ \left( 2 , 0 , 0 \right) }$	$\displaystyle{ \left( 3 , 2 , 2 \right) }$		$\displaystyle{ \left( 1 , 2 , 2 \right) }$
$\displaystyle{ P _{ 2 } }$	$\displaystyle{ \left( 3 , 0 , 2 \right) }$	$\displaystyle{ \left( 9 , 0 , 2 \right) }$		$\displaystyle{ \left( 6 , 0 , 0 \right) }$
$\displaystyle{ P _{ 3 } }$	$\displaystyle{ \left( 2 , 1 , 1 \right) }$	$\displaystyle{ \left( 2 , 2 , 2 \right) }$		$\displaystyle{ \left( 0 , 1 , 1 \right) }$
$\displaystyle{ P _{ 4 } }$	$\displaystyle{ \left( 0 , 0 , 2 \right) }$	$\displaystyle{ \left( 4 , 3 , 3 \right) }$		$\displaystyle{ \left( 4 , 3 , 1 \right) }$

安全序列的计算，查找顺序可以是不严格的

	Work	Need	Alloc	Work+Alloc	possible	choice
$\displaystyle{ P _{ 0 } }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 0 , 1 , 0 \right) }$
$\displaystyle{ P _{ 1 } }$	$\displaystyle{ \left( 3 , 3 , 2 \right) }$	$\displaystyle{ \left( 1 , 2 , 2 \right) }$	$\displaystyle{ \left( 2 , 0 , 0 \right) }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	true	No.1
$\displaystyle{ P _{ 2 } }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	$\displaystyle{ \left( 6 , 0 , 0 \right) }$	$\displaystyle{ \left( 3 , 0 , 2 \right) }$
$\displaystyle{ P _{ 3 } }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	$\displaystyle{ \left( 0 , 1 , 1 \right) }$	$\displaystyle{ \left( 2 , 1 , 1 \right) }$
$\displaystyle{ P _{ 4 } }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	$\displaystyle{ \left( 4 , 3 , 1 \right) }$	$\displaystyle{ \left( 0 , 0 , 2 \right) }$

	Work	Need	Alloc	Work+Alloc	possible	choice
$\displaystyle{ P _{ 1 } }$	$\displaystyle{ \left( 3 , 3 , 2 \right) }$	$\displaystyle{ \left( 1 , 2 , 2 \right) }$	$\displaystyle{ \left( 2 , 0 , 0 \right) }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	true	No.1
$\displaystyle{ P _{ 0 } }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 0 , 1 , 0 \right) }$
$\displaystyle{ P _{ 2 } }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 6 , 0 , 0 \right) }$	$\displaystyle{ \left( 3 , 0 , 2 \right) }$
$\displaystyle{ P _{ 3 } }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	$\displaystyle{ \left( 0 , 1 , 1 \right) }$	$\displaystyle{ \left( 2 , 1 , 1 \right) }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	true	No.2
$\displaystyle{ P _{ 4 } }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 4 , 3 , 1 \right) }$	$\displaystyle{ \left( 0 , 0 , 2 \right) }$

	Work	Need	Alloc	Work+Alloc	possible	choice
$\displaystyle{ P _{ 1 } }$	$\displaystyle{ \left( 3 , 3 , 2 \right) }$	$\displaystyle{ \left( 1 , 2 , 2 \right) }$	$\displaystyle{ \left( 2 , 0 , 0 \right) }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	true	No.1
$\displaystyle{ P _{ 3 } }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	$\displaystyle{ \left( 0 , 1 , 1 \right) }$	$\displaystyle{ \left( 2 , 1 , 1 \right) }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	true	No.2
$\displaystyle{ P _{ 0 } }$	$\displaystyle{ \left( 7 , 4 , 5 \right) }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 0 , 1 , 0 \right) }$
$\displaystyle{ P _{ 2 } }$	$\displaystyle{ \left( 7 , 4 , 5 \right) }$	$\displaystyle{ \left( 6 , 0 , 0 \right) }$	$\displaystyle{ \left( 3 , 0 , 2 \right) }$
$\displaystyle{ P _{ 4 } }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 4 , 3 , 1 \right) }$	$\displaystyle{ \left( 0 , 0 , 2 \right) }$	$\displaystyle{ \left( 7 , 4 , 5 \right) }$	true	No.3

	Work	Need	Alloc	Work+Alloc	possible	choice
$\displaystyle{ P _{ 1 } }$	$\displaystyle{ \left( 3 , 3 , 2 \right) }$	$\displaystyle{ \left( 1 , 2 , 2 \right) }$	$\displaystyle{ \left( 2 , 0 , 0 \right) }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	true	No.1
$\displaystyle{ P _{ 3 } }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	$\displaystyle{ \left( 0 , 1 , 1 \right) }$	$\displaystyle{ \left( 2 , 1 , 1 \right) }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	true	No.2
$\displaystyle{ P _{ 4 } }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 4 , 3 , 1 \right) }$	$\displaystyle{ \left( 0 , 0 , 2 \right) }$	$\displaystyle{ \left( 7 , 4 , 5 \right) }$	true	No.3
$\displaystyle{ P _{ 0 } }$	$\displaystyle{ \left( 10 , 4 , 7 \right) }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 0 , 1 , 0 \right) }$
$\displaystyle{ P _{ 2 } }$	$\displaystyle{ \left( 7 , 4 , 5 \right) }$	$\displaystyle{ \left( 6 , 0 , 0 \right) }$	$\displaystyle{ \left( 3 , 0 , 2 \right) }$	$\displaystyle{ \left( 10 , 4 , 7 \right) }$	true	No.4

	Work	Need	Alloc	Work+Alloc	possible	order
$\displaystyle{ P _{ 1 } }$	$\displaystyle{ \left( 3 , 3 , 2 \right) }$	$\displaystyle{ \left( 1 , 2 , 2 \right) }$	$\displaystyle{ \left( 2 , 0 , 0 \right) }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	true	No.1
$\displaystyle{ P _{ 3 } }$	$\displaystyle{ \left( 5 , 3 , 2 \right) }$	$\displaystyle{ \left( 0 , 1 , 1 \right) }$	$\displaystyle{ \left( 2 , 1 , 1 \right) }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	true	No.2
$\displaystyle{ P _{ 4 } }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 4 , 3 , 1 \right) }$	$\displaystyle{ \left( 0 , 0 , 2 \right) }$	$\displaystyle{ \left( 7 , 4 , 5 \right) }$	true	No.3
$\displaystyle{ P _{ 2 } }$	$\displaystyle{ \left( 7 , 4 , 5 \right) }$	$\displaystyle{ \left( 6 , 0 , 0 \right) }$	$\displaystyle{ \left( 3 , 0 , 2 \right) }$	$\displaystyle{ \left( 10 , 4 , 7 \right) }$	true	No.4
$\displaystyle{ P _{ 0 } }$	$\displaystyle{ \left( 10 , 4 , 7 \right) }$	$\displaystyle{ \left( 7 , 4 , 3 \right) }$	$\displaystyle{ \left( 0 , 1 , 0 \right) }$	$\displaystyle{ \left( 10 , 5 , 7 \right) }$	true	No.5

由此可知， $\displaystyle{ T _{ 0 } }$ 时刻是安全的。

3.3. 死锁的检测

检测有向图是否存在环。

系统处于死锁状态的充分条件是：当且仅当此状态的进程-资源分配图是不可完全简化的，这一充分条件称为死锁定理。

3.4. 死锁的恢复

资源剥夺法
- 挂起某些死锁进程，并抢占它的资源，将资源分配给其他死锁进程
进程回退法
- 让若干个进程回退到足以回避死锁的地步，进程回退时资源释放资源而非被剥夺，要求系统保持进程的历史信息，设置还原点
进程撤销法
- 强制撤销部分甚至全部死锁进程并剥夺这些进程的资源，者嚣的原则可以按进程优先级和撤销进程代价的高低进行
系统重启法

Java

netty

Linux

manim

web

algorithm

compilers

computer-network

cryptography

cs

data-structure

Intel8086

Math

gaoshu

linear

probability

os

pratice