第8章 死锁
单选题2题 多选题1题
8.1 死锁的基本概念
死锁的概念
死锁是指在多道程序系统中，一组进程中的每一个进程均无限期地等待被该组进程中的另一个进程所占有且永远不会释放的资源的现象。
- 当死锁发生后，死锁进程将一直等待下去，需要有来自死锁进程之外的某种干预来解除死锁。
- 系统发生死锁时，死锁进程的个数至少为两个，因为死锁进程都在等待资源，并且其中至少有两个进程已占有资源。
- 系统发生死锁不仅浪费了大量的系统资源，甚至会导致整个系统崩溃，带来灾难性的后果。
活锁与饥饿
(1) 活锁
- 活锁是指两个进程一再消耗完分配给它们的时间片，但是没有进展也没有阻塞，从现象上看，好像死锁发生了。
(2) 饥饿
- 饥饿是指进程一直得不到请求的资源，进程调度被无限退后，而且进程也没有被阻塞。
- 饥饿现象可以通过先来先服务资源分配策略来避免，等待得最久的进程会是下一个被调度的进程。
- 随着时间的推移，所有进程都最终能够获得资源而完成。
死锁产生的原因
产生死锁的原因
- 竞争资源，系统提供的资源数量有限，不能满足每个进程的需求
- 多道程序运行时，进程推进顺序不合理
死锁是若干进程因使用资源不当而造成的现象。
按照资源的使用性质，一般把系统中的资源分成两类：
- 永久性资源（可重用资源）：是指系统中那些可供进程重复使用、长期存在的资源。
- 临时性资源（消耗性资源）：是指由某个进程所产生、只为另一个进程使用一次或经过短暂时间后便不再使用的资源。
死锁类别
- 申请不同类资源产生死锁
- 申请同类资源产生死锁
- 假设有一类可重用资源R，如主存（或磁盘），它包含有m个页面（或扇区），由n个进程P1，P2，...，Pn(2≤m≤n )共享。
- P、V操作使用不当产生死锁
- 进程在相互同步与通信中也可能产生死锁现象，比如生产者和消费者问题，若把生产者和消费者程序中前面两个P操作位置颠倒
- 当进行了n次生产后（或n个生产者，每人都送了一个产品后），缓冲区全部占满, empty=0。
- 若生产者执行了P(mutex)后（此时mutex=0），又执行了P(empty) ，由于empty=-1，使生产者因无可用缓冲区而在empty上等待。
- 若又有一个消费者进程到达，并执行了P(mutex)，使mutex=-1。
- 生产者等待消费者释放一个空缓冲区，而消费者等待生产者释放互斥信号量mutex
- 对临时性资源的使用不加限制而引发的死锁
- 在进程通信时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁。
产生死锁的必要条件
- 互斥条件——资源是独占的且排他使用
- 不可剥夺条件——又称不可抢占或不可强占，获得资源的进程资源释放
- 请求和保持条件——又称部分分配或占有申请在申请新的资源的同时，继续占用已分配到的资源
- 循环等待——又称环路等待，前一个进程占有后一个进程所请求的资源
解决死锁的办法
- 忽视它（鸵鸟算法）——当死锁真正发生且影响系统正常运行时， 手动干预重新启动。
- 预防死锁——通过设置某些严格限制，破坏产生死锁的条件以防止死锁发生。
- 避免死锁——在资源的动态分配过程中，采取某种方法防止系统进入不安全状态，从而避免死锁的发生
- 检测死锁——通过在系统中设置检测机构，可以及时检测出死锁是否真的发生
- 解除死锁——用于将进程从死锁状态下解脱出来。
8.2 死锁的检测及预防
死锁检测
- 检测死锁的实质是确定是否存在“循环等待”条件，检测算法确定死锁的存在并识别出与死锁有关的进程和资源，以供系统采取适当的解除死锁措施。
- 死锁检测机制的步骤：
- 为每个进程和每个资源指定唯一编号
- 设置一张资源分配状态表，每个表目包含“资源号”和占有该资源的“进程号”两项
- 设置一张进程等待分配表，每个表目包含“进程号”和该进程所等待的“资源号”两项
- 死锁检测算法：当任一进程Pj申请 个已被其他进程 占用的资源ri时，进行死锁检测。
死锁解除
(1) 介绍
- 死锁解除实质上就是如何让释放资源的进程能够继续运行。
- 为解除死锁就要剥夺资源，需要考虑以下几个问题：
- 选择一个牺牲进程，即要剥夺哪个进程的哪些资源
- 重新运行或回退到某一点开始继续运行
- 怎样保证不发生“饿死”现象
- 最小代价
- 进程的优先级
- 进程已经运行了多长时间，该进程完成其任务还需要多长时间？
- 该进程使用的资源种类和数量？这些资源能简单地被剥夺吗？
- 为完成其任务，进程还需要多少资源？
- 有多少进程要被撤销？
- 该进程被重新启动运行的次数？
(2) 常用方法
- 死锁解除 = 剥夺资源 + 撤销进程
- 剥夺资源
- 使用挂起/激活机制挂起一些进程，剥夺占有的资源给死锁进程，以解除死锁，待以后条件满足时，再激活被挂起的进程。
- 剥夺的顺序可以是以花费最小资源数为依据每次剥夺后，需要再次调用死锁检测算法。
- 为了安全地释放资源,该进程就必须返回到分配资源前的某一点，经常使用的方法有:
- 还原算法：恢复计算结果和状态。
- 建立检查点：主要是用来恢复分配前的状态。
- 撤销进程
- 撤销死锁进程，将占有的资源分配给另一些死锁进程，直到死锁解除为止。
- 撤销的方法：撤销那些代价最小的进程，或者使撤销进程的数目最小。
- 进程优先数：被撤销进程的优先数。
- 进程类的外部代价：不同类型的进程可以规定出各自的撤销代价。
- 运行代价：重新启动进程并运行到当前撤销点所需要的代价。
(3) 其他方法
- 内部资源（由系统使用，如PCB表）：利用资源编号可以预防死锁，因为在运行时对各种不能确定的申请不必进行选择。
- 内存（由用户作业使用）：可用抢占式进行预防，因为作业始终是可换出内存的，而内存是可抢占的。
- 作业资源（指可分配的设备和文件）：可采用死锁避免措施，因为有关资源申请的信息可从作业说明书或作业控制说明中得到。
- 对换空间（指每个用户作业在辅助存储器上的空间）：采用预先分配方式，因为通常知道最大存储需求量。
死锁预防
(1) 破坏“互斥条件”
- 实施方案：通过采用假脱机(SPOOLing)技术，允许若干个进程同时产生输出
- 设计思想（以打印机为例）：创建管理真正打印机的打印机守护进程，守护进程决不会请求别的资源，从而可以消除因打印机而产生的死锁
(2) 破坏“不可剥夺”条件
- 实施方案：
- 进程申请资源
- 检查资源是否可用
- 检查是否分配给其他等待进程
- 若是，系统将剥夺所需资源，分配给这个进程
- 若否，进程必须等待
- 缺点：
- 实现起来较复杂，增加系统开销，延长了进程的周转时间，降低系统的吞吐量和性能
- 资源被强行剥夺,会造成前阶段工作失效
- 可能出现某个进程反复申请和释放资源，使进程执行无限推迟
(3) 破坏“请求和保持”条件
- 实时方案：
- 静态分配资源策略
- 每个进程必须在开始执行前就申请它所需要的全部资源，等资源全部满足时，进程才开始执行
- 优点是简单、安全、容易实施
- 缺点是严重浪费系统资源，会造成一些资源在很长时间内得不到使用，降低资源利用率
- 动态分配资源策略
- 指进程需要使用资源时才提出申请，系统再进行分配
- 仅当进程没有占用资源时才允许它去申请资源
- 进程已经占用了某些资源而又要再申请资源，则应先归还所占的资源后再申请新资源
- 静态分配资源策略
(4) 破坏”循环等待“条件
- 实施方案：采用资源有序分配策略，破坏了循环等待条件
- 基本思想：将系统中所有资源顺序编号，进程申请资源时，必须严格按照资源编号的顺序进行，否则系统不予分配。
- 有5个哲学家以思考、用餐交替进行的方式生活，他们坐在一-张圆桌边，桌子上有5个盘子和5只筷子。
- 为了防止死锁的产生，可采取一些措施：
- 至多只允许4个哲学家同时坐在桌子的周围。
- 仅当一哲学家左右两边的筷子都可用时，才允许他抓起筷子。
- 让所有哲学家顺序编号：对于奇数号的哲学家必须首先抓起左手的筷子，然后抓起右手的；而对偶数号哲学家则反之。
- 为了防止死锁的产生，可采取一些措施：
8.3 死锁避免（银行家算法）
死锁避免的概念
- 基本思想：系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配。
- 死锁避免和死锁预防的区别：
- 死锁预防：设法至少破坏产生死锁的四个必要条件之一，严格地防止死锁的出现。
- 死锁避免：不严格地限制产生死锁的必要条件的存在，在系统运行过程中注意避免死锁的最终发生。
安全与不安全状态
- 操作系统能保证所有的进程在有限时间内得到所需的全部资源，则称系统处于“安全状态”。
- 安全状态：是指如果存在一个由系统中所有进程构成的安全序列{P1，...，Pn}，则系统处于安全状态，系统处于安全状态则不会发生死锁。
- 不安全状态：是指如果不存在任何一个安全序到，则系统处于不安全状态。
- 不安全状态一定导致死锁，但不安全状态不一定是死锁状态，系统若处于不安全状态则可能发生死锁。
银行家算法（重点）
- 基本思想：将操作系统比作一个银行家，操作系统的各种资源比作周转资金，申请资源的进程比作向银行贷款的顾客。
- 操作系统的资源分配问题——银行家利用其资金贷款的问题
- 为保证资金的安全，银行家规定：
- 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客
- 顾客可以分期贷款，但贷款的总数不能超过最大需求量
- 当银行家现有的资金不能满足顾客尚需的贷款数额时，可推迟支付，但总能使顾客在有限的时间里得到贷款
- 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金
(1) 数据结构
- 可使用资源向量Available
- 一个具有m个元素的数组，每一个元素代表一类可使用资源的数目，其初值为系统中所配置的该类全部可使用资源的数目
- 其数值随该类资源的分配与回收而动态改变，若Available[j] = k，表示系统中有k个rj类资源
- 最大需求矩阵Max
- 一个n*m的矩阵,它定义了系统中n个进程中每一个进程对m类资源的最大需求。
- 如果Max(i, j) = k，表示进程Pi至多需要k个rj类资源
- 分配矩阵Allocation
- 一个n*m矩阵，它定义了系统中每类资源当前已分配给一个进程的资源数。
- 如果Allocation(i, j)=k,表示进程Pi当前已分得k个rj类资源。
- 需求矩阵Need
- 一个n*m矩阵，用以表示每一个进程尚需的各类资源数目。
- 如果Need[i, j] = k表示进程Pi还需要k个rj类资源才能完成任务。
- 工作向量Work
- 一个具有w个元素的数组，每一个元素代表系统可提供给进程继续运行所需的各类资源数目。
- 在执行安全性检查开始时，Work= Available。
- 状态标志Finish
- 一个具有n个元素的数组，每一个元素表示进程Pi已获得足够的资源可以执行完毕并能释放全部获得资源的状态。其初始值为false，达到上述要求时其值为true。
- 进程申请资源向量Request
- 若Request[i, j] = k，表示进程Pi需要申请k个rj类资源
(2) 算法介绍——银行家算法
- Request(i) > need(i)
- 表示出错，因为进程申请的资源多余它自己申报的最大量
- Request(i) > Available
- 则Pi必须等待
- Request(i) > Available
- 系统假设已分给Pi所申请的资源（试探性分配），并修改系统状态
- 调用安全性算法，判断现在的系统是否仍处于安全状态
- 则真正实施分配；否则，拒绝此次分配，恢复原来的系统状态，进程Pi等待
(3) 银行家算法应用实例
假定某系统有三类资源A、B、C，A类资源共有10个资源实例，B类资源共有5个资源实例，C类资源共有7个资源实力，则5个进程P1、P2、P3、P4、P5，它们对各类资源的最大需求量和第一次分配后已占有的资源量如下表所示。
目前占有量 最大需求量 尚需求量 P1 0 1 0 7 5 3 7 4 3 P2 2 0 0 3 2 2 1 2 2 P3 3 0 2 9 0 2 6 0 0 P4 2 1 1 2 2 2 0 1 1 P5 0 0 2 4 3 3 4 3 1 系统剩余资源量：3 3 2
应用银行家算法，找到一个进程安全序列P2->P4->P5->P3->P1，可以得出结论该系统状态是安全状态。
- 银行家算法是通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源的，在能确保系统处于安全状态时才把资源分配给申请者，从而避免系统发生死锁。
- 银行家算法是在系统运行期间实施的，要花费相当多的时间，该算法需要m*n2操作。
- 银行家算法要求每类资源的数量是固定不变的，而且必须事先知道资源的最大需求量。
8.4 资源分配图
- 死锁的表示——资源分配图
- 资源分配图是刻画进程的资源分配的有效方法，是一种有向图，用于描述系统中资源和进程的状态。
- 一个系统资源分配图可定义为一个二元组，即SRAG=(V, E)，其中V是顶点的集合，而E是有向边的集合。
- 顶点集合可分为两个部分P= (P1, P2, ..., Pn)，是由系统内的所有进程组成的集合，每一个Pi代表一个进程；R = (r1, r2, ..., rm)，是系统内所有资源组成的集合，每一个代表一类资源。
- 边集E中的每一条边是一个有序对<Pi, ri>或<ri, Pi>，Pi是进程(Pi∈P) ri是资源类(ri∈R)。
- <Pi, ri> 申请边，表示进程Pi等待获得ri类资源
- <ri, Pi> 分配边，表示进程Pi已经占用ri类资源
- 基于资源分配图的定义，可给出判定死锁的法则，又称为死锁定理
- 如果资源分配图中没有环路，则系统没有死锁。
- 如果资源分配图中出现了环路，则系统中可能存在死锁。
- 资源分配图化简法
- 可以利用简化资源分配图的方法，来检测系统是否为死锁状态。
- 化简：是指若一个进程的所有资源请求均能被满足的话，可以设想该进程得到其所需的全部资源，最终完成任务，运行完毕，并释放所占有的全部资源。
- 在资源分配图中，找出一一个既非等待又非孤立的进程结点Pi
- 将Pi所释放的资源分配给申请它们的进程
- 重复上述两步骤，直到找不到符合条件的进程结点
预览: