封面《絆きらめく恋いろは》
死锁的概念
死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进
死锁产生的原因
- 系统资源不足
- 程序执行的顺序有问题
- 资源分配不当等
死锁产生的必要条件
产生死锁必须满足四个必要条件,任意一个条件不成立,死锁就不会发生。
互斥条件
在某一段时间内,资源仅被一个进程占有。若有其他进程请求该资源,则请求进程只能等待。
不剥夺条件
进程所获得的资源在未使用完之前,不能被其他进程强行夺走,只能由获得该资源的进程自己来释放。
请求并保持条件
进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已经被其他进程占有,此时请求进程被阻塞,但对自己获得的资源保持不放。
循环等待条件
存在一种进程资源的循环等待链,链中每个进程已获得的资源同时被链中下一个进程所请求。
处理死锁
死锁预防
破坏死锁的4个必要条件
破坏互斥条件
有些资源必须互斥使用,因此无法破坏互斥条件。
破坏不剥夺条件
当进程请求新资源得不到满足时,必须释放已经持有的资源,重新申请。这个策略实现起来比较复杂,反复的申请和释放会导致系统开销增加,降低系统吞吐量。这种方式适用于容易保存和恢复的资源,例如CPU的寄存器和内存资源,一般不能用于打印机之类的资源。
破坏请求与保持条件
采用预先静态分配方法,进程在运行之前申请完它所需的所有资源,在使用过程中,这些资源一直归它所有。
容易发生两个问题:1.导致部分进程饥饿现象,永远申请不满资源。2.导致资源浪费,有些资源只在运行初期或者结束时候使用。
破坏循环等待条件
为了破坏循环等待条件,可以采用顺序资源分配法。给资源编号,进程按照编号递增的顺序请求资源。
容易造成资源使用的浪费和用户编程的麻烦。
死锁避免
在使用前进行判断,只允许不会产生死锁的进程申请资源
死锁避免是利用额外的检验信息,在分配资源时判断是否会出现死锁,只在不会出现死锁的情况下才分配资源
各种死锁防止方法能够防止发生死锁,但必然会降低系统并发性,导致低效的资源利用率
安全状态
图 a 的第二列 Has 表示已拥有的资源数,第三列 Max 表示总共需要的资源数,Free 表示还有可以使用的资源数。从图 a 开始出发,先让 B 拥有所需的所有资源(图 b),运行结束后释放 B,此时 Free 变为 5(图 c);接着以同样的方式运行 C 和 A,使得所有进程都能成功运行,因此可以称图 a 所示的状态时安全的。
定义:如果没有死锁发生,并且即使所有进程突然请求对资源的最大需求,也仍然存在某种调度次序能够使得每一个进程运行完毕,则称该状态是安全的。
银行家算法
银行家算法的主要思想是避免死锁进入不安全状态。每次进行资源分配时,它先检查系统是否有足够的资源满足要求,若有则先进行分配,并对分配后的新状态进行安全性检查。若新状态安全,则正是分配上述资源,否则拒绝分配上述资源。然后回收已分配的资源,进行下一轮分配。这样能保证资源始终处于安全状态,从而避免死锁发生。
上图c为不安全状态,因此算法会拒绝进入图c请求
死锁检测与恢复
死锁检测
资源分配图
- 圆圈代表进程
- 方框代表一类资源
- 进程到资源的有向边代表请求资源边
- 资源到进程的有向边代表资源分配边
如图所示,P1进程分得两个R1资源,又请求一个R2资源;P2进程分得一个R1资源和R2资源,又请求了一个R1资源。
简化资源分配图
简化资源分配图步骤
- 找一个非孤立、且只有分配边的进程节点,去掉分配边,将其变为孤立节点
- 再把相应的资源分配给一个等待该资源的进程,即将该进程的申请边变为分配边
- 重复1、2
- (1)到(2): R2剩余1个资源,分配给P1,释放P1
- (2)到(3): R1剩余2个资源,分配给P2,释放P2
若能消去所有的边,则该图是可完全简化的,死锁的条件是当且仅当S状态的资源分配图是不可完全简化的
死锁恢复
- 资源剥夺法。挂起某些死锁进程并抢夺它的资源,直到死锁接触。但要防止被挂起的进程长时间得不到资源而饥饿。
- 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些资源。
- 进程回退法。让一个或多个进程回退到足以回避死锁的地步。要求保持进程的历史信息,设置还原点。