操作系统之死锁

什么是死锁

操作系统之进程同步中我们讨论进程间的同步,其中哲学家吃饭问题时就有一个死锁的现象,某一个进程A已经占用一些资源,同时又等待某一些资源,而等待的某些资源又被另外的进程B占用,而这些进程B正在等待进程A占用的资源,因此就造成了死锁。在操作系统中,这些会被占用的资源类型有很多,比如:I/O设备、内存空间,还有比如操作系统之进程同步中的信号量等等

死锁的必要条件

如果要发生死锁,必须满足四个条件,这四个条件为:

  1. 任何时候,某一个资源最多只能被一个进程使用
  2. 任一个进程,至少占用一个资源,同时又等待至少一个资源,等待资源是被占用的
  3. 进程只能自己释放资源
  4. 循环等待,比如P1等待P2的资源,P2等待P3的资源,P3等待P1的资源……

操作系统死锁的处理方法

死锁的预防

解决的思路为:防止死锁的四个条件同时满足

  1. 破坏互斥:通过逻辑部件代替某个资源,部分资源可以通过这个方法实现,不能解决所有的资源共享问题
  2. 有两种策略:
    • 确保申请一个资源时,它不占用其他资源
    • 或者在执行前,申请获得所有资源
    • 但是这种方式的资源利用率低,还可能会引起饥饿
  3. 当一个进程获取一个资源没有被满足时,就释放自己已经拥有的所以资源,但是这些进程只能是当它进入等待队列时既能获取它释放的资源,又能分得它当前申请的资源,该进程才能被重新分配CPU
  4. 破坏循环等待,定义一个函数,这个函数可以给资源分配一个编号,申请资源的进程申请资源时,顺序要按照资源的编号单调递增,此方法代价较大,因为资源的数目巨大(磁盘上的文件)

在理论上,破坏死锁的必要条件是理论上可行的,即便可以实际实现,代价也非常巨大,因此操作系统不采用这种方式

死锁的避免

死锁的预防是防止死锁的发生,死锁的避免是通过某种方式,避免死锁发生,资源的分配状态取决于3个因素:

  • 可分配资源数
  • 已分配资源数
  • 进程对每种资源的最大需求数

利用这些信息,来判断系统是否处于安全状态,什么是安全状态呢,如果一个进程Pi当前申请的资源小于系统可分配资源加上进程Pj已经拥有的资源(i < j),那么系统就处于安全状态,处于安全状态的系统就不会发生死锁,因为我们可以先满足Pj,然后Pj执行完毕后可以满足Pi。但是系统如果不属于安全状态,有可能会发送死锁

银行家算法

P代表不同的进程,Allocation表示已经拥有的资源A、B、C数量,Max表示进程最多需要的资源A、B、C的数量,Available表示系统剩余的资源A、B、C数量

如果现在某个进程申请资源,系统是否分配资源给它,取决于以下条件

  1. 申请的各个资源数量是小于各个资源最大需要资源数
  2. 申请的各个资源数小于需要的各个资源数(最大的减去已经拥有的)
  3. 如果分配给该进程需要的各个资源的数量以后,系统还处于安全状态(分配以后去判断系统是非安全,就是剩下的可以让除该进程以外的进程都可以按照一定的次序申请通过)

只有满足这三个条件,当一个进程申请资源时,系统才分配给它申请的资源,否则申请被挂起

死锁的检测和恢复

上面的两个方式是通过某一些方式防止死锁的发生,死锁的检测和恢复是指,允许死锁发生,但是死锁可以被检测到,然后再从死锁中恢复正常。怎么检测死锁已经发生了呢,我们同样可以通过系统状态来判断,而这次判断的方式和上面有所不同

这个检测的算法不需要知道进程需要的最大资源数量,而是需要知道目前进程已有的资源数和申请的数量,然后还需要知道系统剩余的资源数量,现在开始判断是非发生死锁:

  1. 遍历所有进程,将请求为0的标识为已完成,图中P0和P2为已完成
  2. 将已完成进程拥有的资源回收了(加上系统剩余的),然后分配给满足申请的小于回收和剩余和的进程
  3. 如果还有进程满足不了,则这些进程就死锁了

对于上图,不存在死锁的进程,安全序列为P0、P2、P3、P1、P4。但是如果现在P2开始申请资源,情况就一样了,系统回收P0的资源,但是满足不了P2,此时P1、P2、P3、P4发生死锁。发生死锁后我们需要解决死锁,解决死锁的方式有三种:

  1. 杀死所有死锁进程,让出资源
  2. 每次只杀死一个进程,回收它的资源,直到死锁被解开
  3. 杀死死锁进程,但是恢复时,恢复点在发生死锁的前一步,操作系统需要记录进程的状态

方法3是最好的方式,方法1一般不采用,方法2需要注意杀死进程的选择,如果单纯的按优先级来杀死进程,可能会造成饥饿,就是某个进程不断的被杀死。死锁的检测和恢复和死锁的避免不一样的地方是,死锁的避免在发生死锁之前先要判断会不会死锁,如果会,是不会让死锁发生的,而死锁的检测和恢复是检测死锁已经发生后恢复死锁,因此在时间点上死锁的检测和恢复更容易选择,可以定时、可以按照第一定的事件(如CPU使用率低),但是死锁的避免是在每一次申请资源之前都必须执行方法,因此操作系统一般采用死锁的检测和恢复这种方法来解决死锁问题

坚持原创分享,您的支持将鼓励我不断前行!