操作系统死锁

发表于 更新于 分类于 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 3 分钟
引言：操作系统死锁

操作系统死锁

死锁的基本概念

产生死锁的原因：

多个进程之间竞争共享的资源

在进程一节讨论过原因

假设：有两个临界资源为Q与W，我们使用记录型信号量处理以下两个进程的任务

1
2
3
4
5
A进程：				B进程：
	P(Q)					P(W)
	P(W)					P(Q)
	V(Q)					V(W)
	V(W)					V(Q)
  1. 进程A抢到了资源Q
  2. 进程B抢到了资源W
  3. 进程A想要资源W，没有，进入阻塞状态
  4. 进程B想要资源Q，没有，进入阻塞状态

我们发现两个进程都进入了阻塞状态，并且都不会释放他们已有的资源，这种情况叫做死锁状态

死锁的一些结论

由于死锁是进程间竞争共享资源产生的，所以由如下结论

  • 死锁的进程至少是两个
  • 死锁的进程至少有两个已经占有了资源
  • 死锁的所有进程都在等待资源
  • 死锁的进程是当前进程中所有进程的子集

永久性资源和临时性资源

永久性资源（可再用资源）：可以被多个进程多次使用，使用模式为“申请—分配—使用—释放模式”

  • 可抢占资源(可剥夺)；如：主存、CPU（不会引起死锁）
  • 不可抢占资源（不可剥夺）；如：打印机

临时性资源（可消耗性资源）：只可使用一次的资源；

  • 如信号量，中断信号，同步信号

产生死锁的根本原因

死锁起因是并发进程的资源竞争，但资源竞争并不一定产生死锁

所以，死锁产生的原因是：

系统能够提供的资源数少于需要该资源的进程数

  1. 竞争不可抢占资源
  2. 竞争可消耗资源
  3. 进程推进顺序不当

其中1与2可以归为一点——竞争系统资源（非可剥夺）

产生死锁的必要条件

必须同时具备以下条件，否则不会成立：

  1. 互斥条件：进程对其所要求的资源进行排它性控制，即一次只有一个进程可以使用一个资源。
  2. 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求。
  3. 不可剥夺条件：进程所获得的资源在未被释放之前，不能被其它进程强行剥夺。
  4. 环路条件：在发生死锁时，必然存在一个进程资源的循环等待链，

死锁的处理

  1. 预防死锁
  2. 避免死锁
  3. 检测死锁
  4. 解除死锁

预防死锁

只需要破坏四个条件之一，即可避免死锁

优点：直观、简单

缺点：导致系统资源利用率和系统吞吐量降低

  1. 破坏互斥条件：做不到，对于抢占式资源来说，不能共享操作
  2. 破坏请求和保持条件：
    • 第一种策略：保证资源的一次性分配（AND型信号量）
      • 但是会导致资源的浪费、饥饿现象的产生
    • 第二种策略：只获得初期所需资源后，开始运行。运行过程逐步释放已分配、已用完的全部资源，再请求新的所需资源
  3. 破坏不可剥夺条件：申请未果，则放弃
    • 难度大、可能会使资源出现错误
  4. 破坏环路等待条件：资源有序分配
    • 做法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反
    • 编号的原则：较为紧缺的资源给以一个较大的序号
    • 优点：较前两种策略，资源利用率和系统吞吐量，都有显著的改善。
    • 问题：
      • 限制了新设备类型的增加
      • 发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费，如：某进程先用磁带机，后用打印机，但按系统规定，它应先申请打印机，后申请磁带机，致使打印机长期闲置
      • 限制了用户简单、自由的编程。

避免死锁

允许动态的申请资源，提高了系统的资源利用率

​ 系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。

首先要明确两个概念：安全状态和不安全状态

安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。

注意：

  1. 安全状态一定没有死锁发生
  2. 并非所有的不安全状态都会转化为死锁状态
  3. 避免死锁的实质：系统在进行资源分配时，使系统不进入不安全状态

例如：

​ 假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配。

进程 最大需求 已分配 可用
P1 10 5 3
P2 4 2
P3 9 2

​ 此时可以先给P2分配，等P2运行完毕后，就有5个磁带机了，此时满足了P1的要求，等P1结束后，也满足了P3的要求，三个进程都可以完成，此时就可以找到安全序列：P2 -> P1 -> P3

​

​ 假如T0时刻P3要求3台磁带机

进程 最大需求 已分配 可用
P1 10 5 2
P2 4 2
P3 9 3

​ 此时不管如何寻找，都找不到一个安全序列，所以此时不可以进行分配

代表算法：

  • 银行家算法
  • 安全性算法

银行家算法

Dijkstra设计的给银行发放贷款使用的算法，由此得名

数据结构：

  • 可利用资源向量Available：含有m个元素的数组
    • 如：Available[j]=K，表示系统中现有Rj类资源K个
    • 初始值是系统中所配置的该类全部可用资源的数目。
  • 最大需求矩阵Max：一个n*m的矩阵，表示系统中n个进程中的每一个进程对m类资源的最大需求
    • 如：Max[i,j]=K，表示进程i需要Rj类资源的最大数目为K。
  • 分配矩阵Allocation：一个n*m的矩阵，
    • 如:Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
  • 需求矩阵need：一个n×m的矩阵
    • Need[i,j]=K，则表示进程i还需要R j类资源K个，才能完成其任务。

上述三个矩阵存在以下关系：

1
Need[i, j] = Max[i, j]-Allocation[i, j]

算法过程：

设Requesti是进程Pi的请求向量，如果Requesti[j]=K表示进程pi的请求向量

image-20201227165507824

安全性算法

安全性算法：对银行家算法改进后的更通用的算法

作用：判断状态是否安全，关键是寻找一个进程安全推进序列

另外设置：

  1. 工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available
  2. Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false;当有足够资源分配给进程时，再令Finish[i]:=true

image-20201227165605203

例1：

​ 假定系统中有五个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下：

Max Allocation Need Available
P0 7 5 3 0 1 0 7 4 3 3 3 2
P1 3 2 2 2 0 0 1 2 2
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1 
     可以找安全的进程推进序列：`P1->P3->P4->P2->P0`
work Need Allocation work+Allocation Finish
P1 3 3 2 1 2 2 2 0 0 5 3 2 true
P3 5 3 2 0 1 1 2 1 1 7 4 3 true
P4 7 4 3 4 3 1 0 0 2 7 4 5 true
P2 7 4 5 6 0 0 3 0 2 10 4 7 true
P0 10 4 7 7 4 3 0 1 0 10 5 7 true

​ work就是当前的available值

此时系统处于安全状态

例2：

某系统有同类资源m个，可并发执行且共享该类资源的进程最多n个，而每个进程申请该类资源的最大量为x(1≤x≤m)，只要不等式n(x-1)+1≤m成立，则系统一定不会发生死锁。

​ 例题: 某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台。但N的取值不超过____时，系统不会发生死锁。

​ 计算：m = 11，N，x=3，代入公式n(x-1)+1<=m即可算出n<=5

死锁检测

当系统为进程分配资源时，若未采取任何限制性措施来保证不进入死锁状态，则系统必须提供检测和解除死锁的手段。

系统检测要求系统做到：

  1. 保存有关资源的请求和分配信息
  2. 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态

发现死锁：根据死锁状态的定义，利用死锁描述中介绍的资源分配图来考察某一时刻系统状态是否合理，即是否能使所有进程都得到它们所申请的资源而运行结束。

死锁解除

解除死锁：与检测死锁相配套的一种措施。

方法：剥夺资源、撤消进程 ；
死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。