线程

做一个超额的线程

( 手记 ) 系统进程死锁

目录

死锁的形成

假如系统中有一组进程,每个进程都占用了某种资源,又在等待该组中其他进程占用的资源,如果这种等待永远结束不了(死循环),则说明系统出现了死锁,或这组进程处于死锁状态.
系统中有两个并发进程A和B,它们都要使用资源R1和R2

  1. A当前占用R1,等待资源R2.
  2. B当前占用R2,等待资源R1.
    这组进程的资源分配不会结束, 形成死锁.
    形成死锁的起因是若干个进程要求的资源总数大于系统能提供的资源数,这时进程间就会出现相互竞争的情况,就会引起死锁,死锁的出现与进程资源分配策略和进程并发执行的速度有关.

Example

  1. 某个系统有某类资源M个,被N个进程共享,每个进程需要X个资源(X 小于等于 M), 则如果出现M < N*X 时,即资源数小于进程所需要的资源总数时,如果分配不当,就会引起死锁.假定M=5, N=5, X=2,采用 的分配策略是只要资源还未分配完,每次有进程申请资源时,则按进程的申请要求分配给它,现在五个进程都提出申请一个资源,分配给它们后,剩余资源为0,这时进程再提出申请第二个进程的时候,资源库已经没 有资源了,于是各个进程都在等待其他进程释放资源,形成死锁.
  2. 进程并发执行的速度也会引起死锁.
    有五个哲学家P1、P2、P3、P4、P5, 围在一张圆桌上,每人面前有一个盘子,桌子中间有一盘面条,另有五根共享的筷子F1、F2、F3、F4、F5,分别放于两人之间,每个哲学家或思考问题或吃面条,当思考问题时放下筷子,吃面条时需要两根筷子才能取到面条到自己盘里,且各人只能从自己的左右两旁取筷子,用过后把筷子仍放到左右两旁,以供他人或自己需要时使用(哲学家不怕脏).
    把每个哲学家看成一个进程,共有五个进程. 每个进程调用P操作来测试是否能取共享的筷子.调用V操作归还筷子的使用权.定义五个信号量S1、S2、S3、S4、S5. 初始值都是1,如果五个哲学家进程互斥的使用筷子
    a. 哲学家P1
    思考问题
    调用P(S1)
    取(F1)
    调用P(S2)
    取(F2)
    吃面条
    放下F1和F2
    V(S1)
    V(S2)

    b.哲学家P2
    思考问题
    调用P(S2)
    取(F2)
    调用P(S3)
    取(F3)
    吃面条
    放下F2和F3
    V(S2)
    V(S3)

    c. 哲学家P3
    思考问题
    调用P(S3)
    取(F3)
    调用P(S4)
    取(F4)
    吃面条
    放下F3和F4
    V(S3)
    V(S4)

    d. 哲学家P4
    思考问题
    调用P(S4)
    取(F4)
    调用P(S5)
    取(F5)
    吃面条
    放下F4和F5
    V(S4)
    V(S5)

    e. 哲学家P5
    思考问题
    调用P(S5)
    取(F5)
    调用P(S1)
    取(F1)
    吃面条
    放下F5和F1
    V(S5)
    V(S1)

    以上是每位哲学家顺序吃面条时无死锁问题,但是当五位哲学家(进程)同时想吃面条时,可能会发生这种情况,哲学家P1调用P(S1)取到筷子F1后被打断,哲学家P2调用P(S2)取到筷子F2后被打断,哲学家P3调用P(S3)取到筷子F3后被打断,哲学家P4调用P(S4)取到筷子F4后被打断,哲学家P5调用P(S5)取到筷子F5后被打断,这样每个人都拿到了左边的一个筷子,这时任何一个哲学家想调用P操作拿到第二根筷子都会处于等待,因为资源库已经没有筷子了,每个人都拿着一根筷子吃不到面条,每个人都希望别人放下筷子,但由于每个人都没有吃到面条,都不会放下筷子,于是形成死锁. 这种死锁的起因既与资源分配的策略有关,又与进程执行的速度有关,也就是说如果操作系统对资源管理不得当或没有估计进程并发执行时可能出现的情况,就会形成死锁.
    PV操作可以实现共享资源的互斥使用,但不能排除死锁

死锁的特征

  1. 死锁的必要条件
    a. 互斥的使用资源(每个资源每次只能给一个进程使用)
    b. 占用且等待资源
    c. 不可抢夺资源
    d. 循环等待资源
    只要发生死锁,那么这四个条件必然成立,但反过来这四个条件成立,不一定发生死锁.
  2. 资源分配图
    a. 如果资源分配图中没有环路,则一定没有死锁
    b. 如果资源分配图中有环路,且每个资源类只有一个资源,则环路存在就意味着死锁的形成.
    c. 如果资源分配图中有环路,但每个资源类有多个资源,则环路存在未必会形成死锁.

死锁的防止

产生死锁,则四个条件必然存在,换言之,如果操作系统的资源分配策略使四个条件中有一个条件不成立,就可以防止死锁的发生.

  1. 互斥的使用资源
    要使互斥条件不成立,唯一的办法就是实现进程共享资源(一个资源可以给多个进程使用),”只读文件”就是一种可以共享使用的资源,多个进程可以同时打开文件进行”读”操作,进程在使用”只读文件”时不会处于等待状态, 但是在计算机系统中,往往由于资源本身的固有特性,使得大多数资源都得互斥使用,例如”打印机”,再如,对可共享的磁盘来说,任何时刻也只允许一个进程使用它,所以想要破坏”互斥的使用资源”这个条件经常是行不通的.
  2. 占用且等待资源
    要使”占用且等待资源”条件不成立,通常有两种办法.
    a. 静态分配资源
    静态分配资源是指进程在执行前就得申请自己所要的全部资源,仅当系统能满足进程所需的资源时进程才会被执行.
    b. 释放已占资源
    这种分配策略是:仅当进程当前没有占用其他资源时,才允许它去申请资源.
  3. 不可抢夺条件
    a. 若进程A申请的资源R尚未被占用,则把资源R分配给进程A.
    b. 若进程A申请的资源R已经被进程B占用,则查看进程B的状态,如果进程B处于等待另一个资源的状态,那么抢夺进程B占用的资源R,并把资源R分配给进程A,否则让进程A处于等待状态.
    c. 一个等待资源的进程只有得到自己所申请的新资源和被其他进程抢夺去的老资源后,才能继续执行.
  4. 循环等待条件
    对资源使用按序分配的策略可以使循环等待条件不成立.
    按序分配是指对系统中的所有资源排一个顺序,对每个资源给出一个确定的编号,规定任何一个进程申请两个以上资源的时候总是先申请编号小的资源,再申请编号大的资源.
    任何进程在申请到进程Ri时,如果要再申请Rj,则i<j
    可以证明按此策略分配资源时,一定不会出现循环等待资源的情况.

死锁的避免

解决死锁问题的另一种方法是避免死锁.

  1. 安全状态
    如果操作系统能保证所有进程在有限的时间内得到需要的所有资源,那么称系统处于安全状态,否则说系统是不安全的,处于安全状态的系统不会发生死锁,
    Example:
    系统共有12个同类资源,有3个进程请求资源,进程A共需9个资源,但第一次只需要申请2个资源,进程B共需10个资源,但第一次只需要5个资源,进程C共需4个资源,但第一次只需要两个资源,
    这样第一轮分配完系统共分配2+5+2=9个资源,还剩3个资源,这时候如果从剩余的3个资源中拿出两个分配给进程C,则进程C完成,归还4个资源,加上原来的1个,共有5个资源,再把这5个分配给进程B,则进程B完成,归还10个资源,再分配给进程A7个资源,则所有进程完成.系统处于安全状态.
    但是如果在第一轮分配结束系统还剩3个资源时,进程A申请再分配一个资源给它,这时候剩余资源还有2个,把这两个资源分配给进程C,则进程C完成返还4个资源,现在问题出现了,剩下的4个资源无论是分配给进程A还是进程B,都不能让它们完成各自的任务,此时系统处于不安全状态,会发生死锁.这种不安全状态显然是由资源分配不当引起的.
    不安全状态和死锁并不相同,上述例子把最后两个资源分配给进程C后,此时死锁并未发生,但如果进程A继续提出申请6个资源,则会发生死锁
    在分配资源时,只要系统能处于安全状态,就能避免死锁的发生.
  2. 银行家算法
    a. 当一个进程对资源的最大需求量不超过系统剩余资源数时,则可以接纳该进程.
    b. 进程可以分期贷资源,但贷资源的总数不能超过最大需求量
    c. 当系统剩余的资源不能满足进程尚需贷资源量时,可以推迟支付,但总能使进程在有限的时间内得到需要的资源.
    d. 当进程得到所需全部的资源时,一定能在有限时间内归还资源.
    当一个进程向系统申请分配资源时,系统首先会检查当前所剩余的资源数能不能满足该进程的最大需求量,如果能则按当前的申请量分配资源,如果不能,则推迟分配.当进程在执行过程中继续申请资源时,先检查该进程已占用的资源数与本次所申请的资源数之和是否大于该进程的最大需求量,如果大于,则系统拒绝分配,否则系统继续检查目前剩余资源能否满足进程剩需的最大资源数,若能满足,则按当前的申请量分配资源,否则也要推迟分配.

死锁的检测

  1. 死锁的检测方法
    可以定时运行一个死锁检测程序,该程序按照一定的算法去检测系统中是否有死锁
    a. 每类资源中只有一个资源.
    可以设置两张表格记录,一张为占用表,记录进程占用资源的情况,另一张为等待表,记录进程正在等待资源的情况.任意进程申请系统资源时,若该资源空闲,则把资源分配给该进程并在占用表中登记项,否则把申请者登入等待表中,死锁检测程序定时循环检查这两张表,如果有循环等待资源的进程则说明有死锁出现.
    b. 资源类中有若干个资源.
    1. 第一步:初始检测. 找出资源已经满足的进程,则不再申请资源的进程,如果有,那么它们一定能在有限时间内执行结束,且归还资源,同时给这些进程置上标志.
    2. 第二部:循环检测. 检测所有无标志的进程,找出一个尚需量不超过系统目前可分配资源量的进程,如果找到,则只要把资源分配给进程,那么该进程一定能在有限时间内执行结束,且归还资源,同时给该进程置上标志,重复循环第二步,直到所有进程都有标志或无标志的进程尚需量超过目前系统可分配资源量.
    3. 第三部:结束检测. 若进程均有标志,则当前不存在永远等待资源的进程,也就是不存在死锁,若存在无标志的进程,则说明系统出现死锁,检测结束时,清除检测过程中设置的所有标志.
  2. 死锁的解除
    a. 终止进程
    终止设计死锁的进程执行,系统可收回被终止进程的所占资源用于分配,已达到解除死锁的目的

    1. 终止设计死锁的所有进程
      一次终止所有涉及死锁的进程
    2. 每次终止一个进程
      每终止一个进程,让死锁检测程序再次检测判断是否还有死锁存在,如若还有,则再终止一个进程,直至死锁解除.
      死锁解除后,系统应该在适当的时候让被终止的进程重新运行

    b. 抢夺资源
    从涉及死锁的进程中抢夺资源,把夺得的资源再分配给卷入死锁的进程,直至死锁解除