# 死锁的概念
死锁 Deadlock:计算机系统中多道程序并发执行时,两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象(僵局),如无外力作用,这些进程将永远不能再向前推进。
# 共享资源的获取和释放
request (申请):如果申请不能立即被允许,那么进程必须等待直到能获取资源。(通过系统调用或者信号量来进行资源的申请和释放)
use (使用):进程使用资源进行相关操作
Release(释放):进程释放资源
如果一个进程要使用 OS 管理的资源,需先向系统提出申请,如果有可用资源,系统才进行分配。
# 资源的分类
- 可抢占资源 — 指资源占有进程虽然需要使用该资源,但另一个进程却可强行把资源从占有者进程处抢来。
- 不可抢占资源 — 指只有占用者进程不再需要使用该资源而主动释放资源外,其它进程不得在占有者进程使用资源过程中强行抢占。
- 根据使用方式:共享资源和独占资源。
- 根据使用期限;永久资源和临时性资源。
# 死锁的原因
- 竞争资源引起死锁
当系统中供多个进程所使用的资源,不足以同时满足它们的需要时,引起它们对资源的竞争而产生死锁 - 进程推进顺序不当引起死锁
在多道程序系统中,并发执行的进程推进序列不可预测
有些推进顺序,进程可以顺利完成
有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进,造成死锁
# 死锁的特性
四个条件同时出现,死锁将会发生
- 互斥:一次只有一个进程可以使用一个资源
- 占有并等待:一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源 (请求与保持)
- 不可抢占:一个资源只有当持有它的进程完成任务后,自由的释放 (非剥夺)
- 循环等待:等待资源的进程之间存在环
# 资源分配图
- 如果图没有环,那么不会有死锁
- 如果图有环
- 如果每一种资源类型只有一个实例,那么死锁发生
- 如果每种资源类型有多个实例,可能死锁
# 处理死锁的方法
- 忽略、预防、避免、检测、解除
- 忽略这个问题,假装系统中从未出现过死锁。这个方法被大部分的操作系统采用,包括 UNIX)鸵鸟策略
- (确保系统永远不会进入死锁状态)预防死锁,避免死锁
- (允许系统进入死锁状态,然后恢复系统)死锁检测
像鸵鸟一样对死锁视而不见
处理死锁的代价很大,而且常常给用户带来许多不便的限制。
大多数用户宁可在极偶然的情况下发生死锁,也不愿限制每个用户只能创建一个进程、只能打开一个文件等等。
于是不得不在方便性和正确性之间作出折衷。
# 死锁的预防
- 抑制死锁发生的必要条件
- 互斥:共享资源不是必须的,必须保持非共享资源
- 占有并等待:必须保证进程申请资源的时候没有占有其他资源
- 要求进程在执行前一次申请全部的资源
- 没有资源时,可以申请资源。在申请更多其它资源之前,需要释放已有资源
- 利用率低,可能出现饥饿
- 非抢占
- 如果一个进程的申请没有实现,它所占有的资源可以被抢占
- 抢占的资源放入进程等待资源列表中
- 只有进程能够重新得到旧的资源和新申请的资源时,才可以重新开始
- 当进程 A 提出资源申请时,首先检查这些资源是否可用
- 是,则分配之,否则检查这些资源是否已分配给了另外的进程 (而这个进程又在等待其他的资源)
- 如果存在这样的进程 B, 从进程 B 剥夺进程 A 所需的资源分配给进程 A 使用。相反,则进程 A 等待,当进程 A 在等待的过程中,它所持有资源可能会被剥夺分配给其他的进程。这样,进程 A 只有得到了它正在申请有资源以及等待过程中被剥夺的资源后,才能恢复运行.
- 循环等待:将所有的资源类型放入资源列表中,并且要求进程按照资源表申请资源
- 所有进程对资源的请求必须严格按资源序号递增的次序提出。
- 总有一个进程占据了较高序号的资源,它继续请求的资源必然是空闲的,可以一直向前推进。
- 在资源分配图中不可能出现环路,因而摒弃了 “环路等待” 条件
- 这种策略可以提高资源利用率,但在进程使用各类资源的顺序与系统规定的顺序不同时会造成资源浪费的情况。
- 上述预防死锁的方法通过限制资源请求来打破死锁的四个必要条件之一,从而预防死锁的发生。
其可能的副作用:
降低设备利用率和吞吐量
可能有进程饥饿
# 死锁避免
- 允许进程动态地申请资源,系统在进行资源分配之前,先计算资源分配的安全性
- 若此次分配不会导致系统从安全状态向不安全状态转换,便可将资源分配给进程;否则不分配资源,进程必须阻塞等待。
- 安全状态是指系统的一种状态,在此状态下,系统能按某种顺序(例如 P1、P2……Pn)来为各个进程分配其所需资源,直至最大需求,使每个进程都可顺序地一个个地完成。这个序列(P1、P2…….Pn)称为安全序列。
- 若某一时刻不存在一个安全序列,则称系统处于不安全状态。
- 当进程申请一个有效的资源的时候,系统必须确定分配后是安全的
- 如果存在一个安全序列系统处于安全态
- 进程序列是安全的,如果每一个进程 Pi 所申请的资源小于当前可用资源数加上其他进程 Pj 所持有的该资源数
如果一个系统在安全状态,就没有死锁
如果系统死锁,则处于不安全状态
如果一个系统处于不安全状态,就有可能死锁
避免:确保系统永远不会进入不安全状态
# 资源分配图算法
-
资源有单个实例
- 资源分配图
-
资源有多个实例
- 银行家算法
-
Claim edge Pi -> Rj indicated that process Pj may request resource Rj; represented by a dashed line.(claim edge 需求边 Pi -> Rj 代表进程 Pi 可能会申请资源 Ri,表示为虚线)
-
Claim edge converts to request edge when a process requests a resource.(一个进程申请资源的时候,需求边转化为请求边)
-
When a resource is released by a process, assignment edge reconverts to a claim edge.(当资源被进程释放的时候,分配边转化为需求边)
-
Resources must be claimed a priori in the system.
(系统中的资源必须被事先声明) -
当一个进程 Pi 申请资源 Rj 时,由循环检测算法来检查:
如果把图中的申请边 Pi Rj 转为分配边 Rj -> Pi ,图中是否会出现环路,只有不出现环路,才实施资源分配
# 银行家算法
- Multiple instances.(多个实例)
- Each process must a priori claim maximum use.
(每一个进程必须事先声明使用的最大量) - When a process requests a resource it may have to wait.
(当一个进程请求资源,它可能要等待) - When a process gets all its resources it must return them in a finite amount of time.
(当一个进程得到所有的资源,它必须在有限的时间释放它们)
# 死锁检测
- 允许进入死锁状态
- 检测死锁
- 恢复策略
每种资源只有一个实例:定期调用算法来检查是否有环
每种资源有多个实例:检测算法
# 死锁恢复
- 死锁发生后,如何处理死锁?
- 操作员人工处理
- 进程终止
- 资源抢占
- 终止所有的死锁进程
- 一次终止一个进程直到死锁环消失
- 选择终止顺序
- 进程的优先级
- 进程计算了多少时间,还需要多长时间
- 进程使用的资源
- 进程完成还需要多少资源
- 多少个进程需要被终止
- 进程是交互的还是批处理
- 逐步从进程中抢占资源,直到打破死锁
- 选择一个牺牲品:最小化代价
- 回退:返回到安全的状态,然后重新开始进程
- 饥饿:同一个进程可能总是被选中,包括在回退时