Operating System——Deadlock

Posted by Sakura on June 24, 2018

操作系统——死锁

前言

操作系统原理是武汉大学计算机学院软件工程专业大二下半学期所学习的一门专业课,教材为西安电子科技大学出版社的计算机操作系统第4版,这个专题的博客为该课程的学习笔记,该博客的主要内容是死锁以及处理死锁的四种方法


死锁概述

死锁

死锁是指多个进程因竞争系统资源而造成的一种僵局,若无外力作用,这些进程都将永远不能向前推进。

一般地说,如果在一组进程的每个进程都在等待只能由该组中的其他一个进程才能引发的事件,则称这组进程处于死锁状态。

一般说来,死锁产生的原因是:

  • 竞争不可抢占性资源引起死锁;
  • 竞争可消耗资源引起死锁;
  • 进程推进顺序不当引起死锁:申请和释放资源的顺序不当。

example

死锁举例2—竞争临时资源

进程P1产生消息S1,又要求从P3处接收消息S3;

进程P3产生消息S3,又要求从P2接收消息S2;

进程P2产生消息S2,又需要接收P1产生的消息S1。

如果消息通信按下述顺序进行:

P1: …Release(S1); Request(S3); …

P2: …Release(S2); Request(S1); …

P3: …Release(S3); Request(S2); …  

并不可能发生死锁,但若改成下述的运行顺序:

P1: …Request(S3); Release(S1); …

P2: …Request(S1); Release(S2); …

P3: …Request(S2); Release(S3); …

则可能发生死锁。

死锁举例3—推进顺序不当 example

死锁的必要条件和处理方法

产生死锁的必要条件:

  • 互斥条件:在一段时间内某资源仅为一个进程所占有。
  • 请求和保持条件:当进程因请求资源被阻塞时,已分配资源保持不放。
  • 不可剥夺条件:进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走。
  • 环路等待条件:存在一个循环等待链,其中,每一个进程分别等待它前一个进程所持有的资源,造成永远等待。

★只要能破坏这四个必要条件之一,死锁就可防止。

处理死锁的方法:

  • 预防死锁:设置某些限制条件,通过破坏死锁产生的四个必要条件之一来预防死锁。
  • 避免死锁:在资源的动态分配过程中,用某种方法来防止系统进入不安全状态。
  • 检测死锁及解除:系统定期检测是否出现死锁,若出现则解除死锁。

这四种方法对死锁的防范程度逐渐减弱,但对应的是资源利用率的提高,以及进程因资源因素而阻塞的频度下降(即并发程度提高)


预防死锁

预防死锁:通过破坏产生死锁的四个必要条件中的一个或几个条件,来防止发生死锁。

特点:较易实现,广泛使用,但限制较严,资源利用率低。

  • 破坏“互斥”条件:互斥是设备本身固有的属性,此条件不能破坏。
  • 破坏“请求和保持”条件
    • 第一种协议:规定所有进程在开始运行之前,必须一次性地申请其在整个运行过程中所需的全部资源。
      • 简单、易行、安全,但资源被严重浪费、恶化了资源利用率,使进程经常饥饿
    • 第二种协议:允许一个进程只获得运行初期所需的资源后便开始运行
  • 破坏“不可抢占”条件
    • 一个已保持了某些资源的进程,若新的资源请求得不到满足,则它必须释放已获得的所有资源,待以后需要时再重新申请。
    • 特点:实现较复杂,释放已获得资源可能造成前一段工作的失效,重复申请和释放资源会增加系统开销,降低系统吞吐量。
    • 只适用于其状态可以保存和恢复的资源,如对主存资源和处理器资源的分配
  • 破坏“循环等待”条件
    • 将所有资源按类型排队,并赋予不同序号,要求进程均严格按照序号递增的次序请求资源,同类资源一次申请完。这种方法称为有序资源分配法。
    • 换句话说,要求:当一个进程申请一个资源时,必须释放其占有的序号大于该资源的其它资源。

避免死锁

系统安全状态

预防死锁方法一般都对资源的申请使用施加了较强限制条件,而死锁避免对资源的申请使用限制条件较弱,系统性能较好。

死锁避免:允许进程动态申请资源,系统在为申请者分配资源前先检查资源分配的安全性。并根据检查结果决定是否分配资源,若分配后系统可能发生死锁(即不安全),则不予分配,否则予以分配。

死锁避免方法中将系统状态分为安全状态和不安全状态,只要系统始终都处于安全状态便可避免死锁的发生。

安全状态是指系统能按某种顺序如< P1, P2 , …, Pn >来为每个进程分配其所需的资源,直至最大需求,使每个进程都可以顺利完成,则称此时的系统状态为安全状态,称序列< P1, P2 , …, Pn > 为安全序列。

即在当前状态下能够找到一个安全序列,则是安全状态。

避免死锁的本质是使系统不进入不安全状态。

example

T0时刻存在一个安全序列<P2,P1,P3>,系统状态安全。

example

利用银行家算法避免死锁


死锁的检测与解除

死锁的检测

通过系统的检测机构及时地检测出死锁的发生,然后采取某种措施解除死锁。为此,系统必须做到:

(1) 保存有关资源的请求和分配信息。 →资源分配图

(2) 提供一种算法,以利用这些信息来检测系统是否已进入死锁状态。 →死锁检测算法

特点:死锁检测和解除可使系统获得较高的利用率,但是实现难度最大。

example

将资源分配图简化可以检测是否死锁,方法如下:

在资源分配图中,找出一个既不阻塞又非孤立的进程结点pi,进程pi获得了它所需要的全部资源,能运行完成然后释放所有资源。这相当于消去pi的所有请求边和分配边,使之成为孤立结点。

进程pi释放资源后,可以唤醒因等待这些资源而阻塞的进程,从而可能使原来阻塞的进程变为非阻塞进程。

在进行一系列化简后,若能消去图中所有的边,使所有进程都成为孤立结点,则称该图是可完全简化的;若不能使该图完全化简,则称该图是不可完全简化的。

可以证明:所有的简化顺序将得到相同的结果。

example

S为死锁状态的条件是当且仅当S状态的资源分配图是不可完全简化的。该条件称为死锁定理

死锁的解除

一旦检测出系统中出现了死锁,就应将陷入死锁的进程从死锁状态中解脱出来,方法如下:

资源剥夺法:当发现死锁后,从其他进程那里剥夺足够数量的资源给死锁进程,以解除死锁状态。

撤消进程法:最简单的方法是撤消全部死锁进程,使系统恢复到正常状态。但这种做法付出的代价太大。另一方法是按照某种顺序逐个撤消死锁进程,直到有足够的资源供其他未被撤消的进程使用,消除死锁状态为止。