操作系统概念阅读笔记7

死锁

本文总阅读量
Posted by Xiaoxi on January 13, 2016

#死锁 在多道程序环境下,多个进程可能竞争一定数量的资源。而当某个进程申请资源时,而如果这是该资源不可用,那么该进程便进入等待状态。而如果所申请的资源是被其他等待进程占有,那么该等待进程有可能再也无法改变其状态。这种状况就叫做死锁。即在无外力作用下,两个互相等待的进程将永远无法执行完成,只能保持互相等待的状态。


##系统模型

  1. 资源:资源可分为多种类型,每种类型具有一定数量的实例。比如,内存空间、cpu周期、文件、I/O设备(打印机或DVD驱动器)
  2. 使用模型:“申请–分配–使用–释放”模式

    进程在使用资源前必须申请资源,在使用完毕前必须释放资源。申请不被允许(申请的资源被其他进程所使用)时,申请进程必须等待,直到它获得该资源位置。


##必要条件

  1. 互斥:至少有一种资源必须处于非共享模式。即一个资源在被一个进程使用时,另一个进程是无法使用该资源的。除非正在使用的进程执行完毕,释放了该资源。
    1. 占有并等待:一个进程必须占有至少一个资源,并等待一被另外进程资源占有的资源。
  2. 非抢占:资源不能被抢占
  3. 循环等待:在资源分配图中,存在环。比如,P0等待P1占有的资源,P1等待P2占有的资源,而且P2等待P0占有的资源。

##死锁处理方法

  1. 使用协议来预防或避免死锁
  2. 忽略死锁,再通过周期检测。检测到死锁,对此加以恢复。
  3. 忽略死锁问题,认为死锁不会发生。(让程序开发者,写程序时,自己处理,保证不会有死锁产生)

###死锁预防 死锁预防是一组方法,以确保至少一个必要条件不成立。(缺点:导致低设备利用率和系统吞吐率)

  1. 破坏“互斥” 保证所有资源都是共享资源。比如 多次读取文件
  2. 破坏“占有并等待”:
    1. 要求每个进程在运行前必须一次性申请它所要求的所有资源,且仅当该进程所要资源均可满足时才给予一次性分配。
    2. 允许进程在没有资源时,才可申请资源。
  3. 破坏“非抢占” 在允许进程动态申请资源前提下规定,一个进程在申请新的资源不能立即得到满足而变为等待状态之前,必须隐式释放已占有的全部资源,若需要再重新申请

  4. 破坏“循环等待”条件

    采用资源有序分配法: 把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配。

###死锁避免 通过一些额外的信息,来衡量某些进程申请的资源是否分配。 ​ ####安全状态#### (概念补充): - 存在一个安全的序列,使进程能按该序列不死锁的运行,则说明系统处于安全状态。 - 安全状态不是死锁状态。相反,死锁状态是不安全状态。然而,不是所有不安全状态都能导致死锁状态。不安全状态,主要表明的是 操作系统不能阻止进程以会导致死锁的方式申请资源。关系图,如图所示:

  1. 资源分配图算法

    针对的是每种资源只有一个实例的情况。其主要就是保证在资源分配图中不存在环即可。

  2. 银行家算法 针对的是每种资源类型有多个实例的资源分配系统。这个具体细节 下篇博文发^v^.

###死锁检测 通过一个算法周期检测当前状态下是否存在死锁。若有,则纠正死锁状态。 1.每种资源只有单个实例情况 从资源分配图中,删除所有资源类型节点,合并适当边,就可以得到等待图。如图所示: 接下来只需要维护等待图,保证其不出现环即可。(若出现,则通过一定策略,消去)

###死锁恢复 ####1.进程终止

  1. 终止所有死锁进程
  2. 一次终止一个进程直到取消死锁循环为止。 (最好选择一个“代价最小”的进程先终止)

####2.资源抢占 通过资源抢占来取消死锁,逐步从进程中抢占资源给其他进程使用,直到死锁环被打破为止。 问题:

  1. 如何选择牺牲品(代价最小)
  2. 如何回滚:即执行完毕后,必须将进程回滚到某个安全状态,以便从该状态重启进程。
  3. 如何确保不会发生饥饿

典型习题

####7.2 考虑如下的死锁可能发生在哲学家进餐中,哲学家在同个时间获得筷子。讨论此种情况下死锁的四个必要条件的设置。讨论如何在消除其中任一条件来避免死锁的发生。
死锁是可能的,因为哲学家进餐问题是以以下的方式满足四个必要条件:

1)互斥 所需的筷子互斥,一个哲学家两边只有两只筷子

2)持有并等待:哲学家手里拿着一只筷子,并等待另一只筷子

3)非抢占:一只筷子分配给一个哲学家后不能被强行拿走

4)循环并等待:可能出现一种情况,每个哲学家都有一双筷子并等待另一只筷子的到来。

死锁可避免克服的条件方式如下:

1)破坏互斥:允许同时分享筷子

2)破坏持有并等待:若哲学家无法获得第二双筷子,则立即放弃第一双筷子

3)允许抢占:如果另一哲学家已等待这一哲学家筷子很久,则允许筷子被另一哲学家强行拿走

4)破坏循环等待:实施筷子编号,总是获得较低编号的筷子,之后才能获得较高的编号的筷子。

####7.5 在一个真实的计算机系统中,可用的资源和进程命令对资源的要求都不会持续很久是一致的长期(几个月)。资源会损坏或被替换,新的进程会进入和离开系统,新的资源会被购买和添加到系统中。如果用银行家算法控制死锁,下面哪些变化是安全的(不会导致可能的死锁) ,并且在什么情况下发生?

a. 增加可用资源(新的资源被添加到系统)
b. 减少可用资源(资源被从系统中永久性地移出)
c. 增加一个进程的Max(进程需要更多的资源,超过所允许给予的资源) d. 减少一个进程的Max(进程不再需要那么多资源) e. 增加进程的数量 f. 减少进程的数量

解答:

a. 增加可用资源(新的资源被添加到系统):这个可以在没有任何问题的情况下安全地改变 b. 减少可用资源(资源被从系统中永久性地移出):这可能会影响到系统,并导致可能性死锁,因为系统的安全性假定其拥有一定数量的可用资源 c. 增加一个进程的Max(进程需要更多的资源,超过所允许给予的资源):这可能会影响到系统,并可能导致死锁 d. 减少一个进程的Max(进程不再需要那么多资源):这个可以在没有任何问题的情况下安全地改变 e. 增加进程的数量:如果允许分配资源给新进程,那么该系统可能进入一个不安全的状态。 f. 减少进程的数量:这个可以在没有任何问题的情况下安全地改变

####7.6 假设系统中有四个相同类型的资源被三个进程共享。每个进程最多需要两个资源。证明这个系统不会死锁。
证明:假设该系统陷入死锁。这意味着,每一个进程持有一个资源,并且正等待另一个资源。因为有三个进程和四个资源,一个进程就必须获取两个资源。这一进程并不需要更多的资源,它可以立即执行,不需等待。因此当其完成时会返回其资源。

####7.7 假设一个系统有 m 个资源被 n 个进程共享,进程每次只请求和释放一个资源。证明只要系统符合下面两个条件,就不会发生死锁: a.每个进程需要资源的最大值在 1 到 m 之间 b.所有进程需要资源的最大值的和小于 m+n

证明: 假设n个进程的MAXi={x1,x2,…xn} x1+x2+…xn<m+n 1<Max{x1,x2,..xn}<m 如果存在死锁,那么发生死锁时,所有资源都被分配,即Allocationi的累加和应为m。而Allocation与Need的累加和等于MAXi的累加和,即累加和Allocation+Need=MAX<m+n => m+Need<m+n =»Need<n 得到Need的累加和小于n。那么,对于n个进程必有一个进程其仍需的资源为0.而所需资源为0的进程,可直接执行,执行完后释放资源。即不可能存在死锁