汽车死锁操作系统

2016-03-30 20:42:31 yuzuodeyunwcj 阅读数 329

一、要点提示

(1) 掌握死锁的概念和产生死锁的根本原因

(2) 理解产生死锁的必要条件--以下四个条件同时具备:互斥条件、不可抢占条件、占有且申请条件、循环等待条件

(3) 记住解决死锁的一般方法,掌握死锁的预防和死锁的避免二者的基本思想

(4) 掌握死锁的预防策略中资源有序分配策略

(5) 理解进程安全序列的概念,理解死锁与安全序列的关系

(6) 了解银行家算法

(7) 了解资源分配图

(8) 了解死锁的检测及恢复的思想

 

 二、内容简介

  在计算机系统中有很多一次只能由一个进程使用的资源,如打印机,磁带机,一个文件的I节点等。在多道程序设计环境中,若干进程往往要共享这类资源,而且一个进程所需要的资源不止一个。这样,就会出现若干进程竞争有限资源,又推进顺序不当,从而构成无限期循环等待的局面。这种状态就是死锁。系统发生死锁现象不仅浪费大量的系统资源,甚至导致整个系统崩溃,带来灾难性后果。所以,对于死锁问题在理论上和技术上都必须给予高度重视。

8.1 死锁的概念  

  死锁是进程死锁的简称,是由Dijkstra于1965年研究银行家算法时首先提出来的。它是计算机操作系统乃至并发程序设计中最难处理的问题之一。实际上,死锁问题不仅在计算机系统中存在,在我们日常生活中它也广泛存在。

1.什么是死锁

  我们先看看这样一个生活中的例子:在一条河上有一座桥,桥面较窄,只能容纳一辆汽车通过,无法让两辆汽车并行。如果有两辆汽车A和B分别由桥的两端驶上该桥,则对于A车来说,它走过桥面左面的一段路(即占有了桥的一部分资源),要想过桥还须等待B车让出右边的桥面,此时A车不能前进;对于B车来说,它走过桥面右边的一段路(即占有了桥的一部分资源),要想过桥还须等待A车让出左边的桥面,此时B车也不能前进。两边的车都不倒车,结果造成互相等待对方让出桥面,但是谁也不让路,就会无休止地等下去。这种现象就是死锁。如果把汽车比做进程,桥面作为资源,那麽上述问题就描述为:进程A占有资源R1,等待进程B占有的资源Rr;进程B占有资源Rr,等待进程A占有的资源R1。而且资源R1和Rr只允许一个进程占用,即:不允许两个进程同时占用。结果,两个进程都不能继续执行,若不采取其它措施,这种循环等待状况会无限期持续下去,就发生了进程死锁。  

  在计算机系统中,涉及软件,硬件资源都可能发生死锁。例如:系统中只有一台CD-ROM驱动器和一台打印机,某一个进程占有了CD-ROM驱动器,又申请打印机;另一进程占有了打印机,还申请CD-ROM。结果,两个进程都被阻塞,永远也不能自行解除。

  所谓死锁,是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然,如果没有外力的作用,那麽死锁涉及到的各个进程都将永远处于封锁状态。从上面的例子可以看出,计算机系统产生死锁的根本原因就是资源有限且操作不当。即:一种原因是系统提供的资源太少了,远不能满足并发进程对资源的需求。这种竞争资源引起的死锁是我们要讨论的核心。例如:消息是一种临时性资源。某一时刻,进程A等待进程B发来的消息,进程B等待进程C发来的消息,而进程C又等待进程A发来的消息。消息未到,A,B,C三个进程均无法向前推进,也会发生进程通信上的死锁。另一种原因是由于进程推进顺序不合适引发的死锁。资源少也未必一定产生死锁。就如同两个人过独木桥,如果两个人都要先过,在独木桥上僵持不肯后退,必然会应竞争资源产生死锁;但是,如果两个人上桥前先看一看有无对方的人在桥上,当无对方的人在桥上时自己才上桥,那麽问题就解决了。所以,如果程序设计得不合理,造成进程推进的顺序不当,也会出现死锁。

2.产生死锁的必要条件

  从以上分析可见,如果在计算机系统中同时具备下面四个必要条件时,那麽会发生死锁。换句话说,只要下面四个条件有一个不具备,系统就不会出现死锁。

    〈1〉互斥条件。即某个资源在一段时间内只能由一个进程占有,不能同时被两个或两个以上的进程占有。这种独占资源如CD-ROM驱动器,打印机等等,必须在占有该资源的进程主动释放它之后,其它进程才能占有该资源。这是由资源本身的属性所决定的。如独木桥就是一种独占资源,两方的人不能同时过桥。

    〈2〉不可抢占条件。进程所获得的资源在未使用完毕之前,资源申请者不能强行地从资源占有者手中夺取资源,而只能由该资源的占有者进程自行释放。如过独木桥的人不能强迫对方后退,也不能非法地将对方推下桥,必须是桥上的人自己过桥后空出桥面(即主动释放占有资源),对方的人才能过桥。

    〈3〉占有且申请条件。进程至少已经占有一个资源,但又申请新的资源;由于该资源已被另外进程占有,此时该进程阻塞;但是,它在等待新资源之时,仍继续占用已占有的资源。还以过独木桥为例,甲乙两人在桥上相遇。甲走过一段桥面(即占有了一些资源),还需要走其余的桥面(申请新的资源),但那部分桥面被乙占有(乙走过一段桥面)。甲过不去,前进不能,又不后退;乙也处于同样的状况。

    〈4〉循环等待条件。存在一个进程等待序列{P1,P2,...,Pn},其中P1等待P2所占有的某一资源,P2等待P3所占有的某一源,......,而Pn等待P1所占有的的某一资源,形成一个进程循环等待环。就像前面的过独木桥问题,甲等待乙占有的桥面,而乙又等待甲占有的桥面,从而彼此循环等待。

  上面我们提到的这四个条件在死锁时会同时发生。也就是说,只要有一个必要条件不满足,则死锁就可以排除。

8.2 死锁的预防  

  前面介绍了死锁发生时的四个必要条件,只要破坏这四个必要条件中的任意一个条件,死锁就不会发生。这就为我们解决死锁问题提供了可能。一般地,解决死锁的方法分为死锁的预防,避免,检测与恢复三种(注意:死锁的检测与恢复是一个方法)。我们将在下面分别加以介绍。

  死锁的预防是保证系统不进入死锁状态的一种策略。它的基本思想是要求进程申请资源时遵循某种协议,从而打破产生死锁的四个必要条件中的一个或几个,保证系统不会进入死锁状态。

   〈1〉打破互斥条件。即允许进程同时访问某些资源。但是,有的资源是不允许被同时访问的,像打印机等等,这是由资源本身的属性所决定的。所以,这种办法并无实用价值。

   〈2〉打破不可抢占条件。即允许进程强行从占有者那里夺取某些资源。就是说,当一个进程已占有了某些资源,它又申请新的资源,但不能立即被满足时,它必须释放所占有的全部资源,以后再重新申请。它所释放的资源可以分配给其它进程。这就相当于该进程占有的资源被隐蔽地强占了。这种预防死锁的方法实现起来困难,会降低系统性能。    

    〈3〉打破占有且申请条件。可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足,则不分配任何资源,此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时,才一次性地将所申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源,所以不会发生占有资源又申请资源的现象,因此不会发生死锁。但是,这种策略也有如下缺点:

(1)在许多情况下,一个进程在执行之前不可能知道它所需要的全部资源。这是由于进程在执行时是动态的,不可预测的;

(2)资源利用率低。无论所分资源何时用到,一个进程只有在占有所需的全部资源后才能执行。即使有些资源最后才被该进程用到一次,但该进程在生存期间却一直占有它们,造成长期占着不用的状况。这显然是一种极大的资源浪费;

(3)降低了进程的并发性。因为资源有限,又加上存在浪费,能分配到所需全部资源的进程个数就必然少了。    

 

(4)打破循环等待条件,实行资源有序分配策略。采用这种策略,即把资源事先分类编号,按号分配,使进程在申请,占用资源时不会形成环路。所有进程对资源的请求必须严格按资源序号递增的顺序提出。进程占用了小号资源,才能申请大号资源,就不会产生环路,从而预防了死锁。这种策略与前面的策略相比,资源的利用率和系统吞吐量都有很大提高,但是也存在以下缺点:

(1)限制了进程对资源的请求,同时给系统中所有资源合理编号也是件困难事,并增加了系统开销;

(2)为了遵循按编号申请的次序,暂不使用的资源也需要提前申请,从而增加了进程对资源的占用时间。

8.3 死锁的避免  

  上面我们讲到的死锁预防是排除死锁的静态策略,它使产生死锁的四个必要条件不能同时具备,从而对进程申请资源的活动加以限制,以保证死锁不会发生。下面我们介绍排除死锁的动态策略--死锁的避免,它不限制进程有关申请资源的命令,而是对进程所发出的每一个申请资源命令加以动态地检查,并根据检查结果决定是否进行资源分配。就是说,在资源分配过程中若预测有发生死锁的可能性,则加以避免。这种方法的关键是确定资源分配的安全性。

 

1.安全序列

  我们首先引入安全序列的定义:所谓系统是安全的,是指系统中的所有进程能够按照某一种次序分配资源,并且依次地运行完毕,这种进程序列{P1,P2,...,Pn}就是安全序列。如果存在这样一个安全序列,则系统是安全的;如果系统不存在这样一个安全序列,则系统是不安全的。

  安全序列{P1,P2,...,Pn}是这样组成的:若对于每一个进程Pi,它需要的附加资源可以被系统中当前可用资源加上所有进程Pj当前占有资源之和所满足,则{P1,P2,...,Pn}为一个安全序列,这时系统处于安全状态,不会进入死锁状态。  

  虽然存在安全序列时一定不会有死锁发生,但是系统进入不安全状态(四个死锁的必要条件同时发生)也未必会产生死锁。当然,产生死锁后,系统一定处于不安全状态。 

2.银行家算法

  这是一个著名的避免死锁的算法,是由Dijstra首先提出来并加以解决的。 

  [背景知识] 

  一个银行家如何将一定数目的资金安全地借给若干个客户,使这些客户既能借到钱完成要干的事,同时银行家又能收回全部资金而不至于破产,这就是银行家问题。这个问题同操作系统中资源分配问题十分相似:银行家就像一个操作系统,客户就像运行的进程,银行家的资金就是系统的资源。

  [问题的描述]

  一个银行家拥有一定数量的资金,有若干个客户要贷款。每个客户须在一开始就声明他所需贷款的总额。若该客户贷款总额不超过银行家的资金总数,银行家可以接收客户的要求。客户贷款是以每次一个资金单位(如1万RMB等)的方式进行的,客户在借满所需的全部单位款额之前可能会等待,但银行家须保证这种等待是有限的,可完成的。

  例如:有三个客户C1,C2,C3,向银行家借款,该银行家的资金总额为10个资金单位,其中C1客户要借9各资金单位,C2客户要借3个资金单位,C3客户要借8个资金单位,总计20个资金单位。某一时刻的状态如图所示。

  

C1 2(7)
C2 2(1)
C3 4(4)
余额2
C1 2(7)
C3 4(4)

余额4

C1 2(7)
余额8

余额10

    (a)

     (b)

     (c)

     (d)

                                       银行家算法示意

  对于a图的状态,按照安全序列的要求,我们选的第一个客户应满足该客户所需的贷款小于等于银行家当前所剩余的钱款,可以看出只有C2客户能被满足:C2客户需1个资金单位,小银行家手中的2个资金单位,于是银行家把1个资金单位借给C2客户,使之完成工作并归还所借的3个资金单位的钱,进入b图。同理,银行家把4个资金单位借给C3客户,使其完成工作,在c图中,只剩一个客户C1,它需7个资金单位,这时银行家有8个资金单位,所以C1也能顺利借到钱并完成工作。最后(见图d)银行家收回全部10个资金单位,保证不赔本。那麽客户序列{C1,C2,C3}就是个安全序列,按照这个序列贷款,银行家才是安全的。否则的话,若在图b状态时,银行家把手中的4个资金单位借给了C1,则出现不安全状态:这时C1,C3均不能完成工作,而银行家手中又没有钱了,系统陷入僵持局面,银行家也不能收回投资。

  综上所述,银行家算法是从当前状态出发,逐个按安全序列检查各客户谁能完成其工作,然后假定其完成工作且归还全部贷款,再进而检查下一个能完成工作的客户,......。如果所有客户都能完成工作,则找到一个安全序列,银行家才是安全的。

  从上面分析看出,银行家算法允许死锁必要条件中的互斥条件,占有且申请条件,不可抢占条件的存在,这样,它与预防死锁的几种方法相比较,限制条件少了,资源利用程度提高了。

这是该算法的优点。其缺点是:

   〈1〉这个算法要求客户数保持固定不变,这在多道程序系统中是难以做到的。   

   〈2〉这个算法保证所有客户在有限的时间内得到满足,但实时客户要求快速响应,所以要考虑这个因素。  

    〈3〉由于要寻找一个安全序列,实际上增加了系统的开销。

 

8.4 死锁的检测与恢复  

  一般来说,由于操作系统有并发,共享以及随机性等特点,通过预防和避免的手段达到排除死锁的目的是很困难的。这需要较大的系统开销,而且不能充分利用资源。为此,一种简便的方法是系统为进程分配资源时,不采取任何限制性措施,但是提供了检测和解脱死锁的手段:能发现死锁并从死锁状态中恢复出来。因此,在实际的操作系统中往往采用死锁的检测与恢复方法来排除死锁。

  死锁检测与恢复是指系统设有专门的机构,当死锁发生时,该机构能够检测到死锁发生的位置和原因,并能通过外力破坏死锁发生的必要条件,从而使得并发进程从死锁状态中恢复出来。

1.放大观看>>)

  图中所示为一个小的死锁的例子。这时进程P1占有资源R1而申请资源R2,进程P2占有资源R2而申请资源R1,按循环等待条件,进程和资源形成了环路,所以系统是死锁状态。进程P1,P2是参与死锁的进程。

  下面我们再来看一看死锁检测算法。算法使用的数据结构是如下这些:      

      占有矩阵A:n*m阶,其中n表示并发进程的个数,m表示系统的各类资源的个数,这个矩阵记录了每一个进程当前占有各个资源类中资源的个数。

       申请矩阵R:n*m阶,其中n表示并发进程的个数,m表示系统的各类资源的个数,这个矩阵记录了每一个进程当前要完成工作需要申请的各个资源类中资源的个数。

       空闲向量T:记录当前m个资源类中空闲资源的个数。

       完成向量F:布尔型向量值为真(true)或假(false),记录当前n个并发进程能否进行完。为真即能进行完,为假则不能进行完。

       临时向量W:开始时W:=T。

算法步骤:

     (1)W:=T,

     对于所有的i=1,2,...,n,

     如果A[i]=0,则F[i]:=true;否则,F[i]:=false

     (2)找满足下面条件的下标i:

     F[i]:=false并且R[i]〈=W

     如果不存在满足上面的条件i,则转到步骤(4)。

     (3)W:=W+A[i]

     F[i]:=true

     转到步骤(2)

     (4)如果存在i,F[i]:=false,则系统处于死锁状态,且Pi进程参与了死锁。什麽时候进行死锁的检测取决于死锁发生的频率。如果死锁发生的频率高,那麽死锁检测的频率也要相应提高,这样一方面可以提高系统资源的利用率,一方面可以避免更多的进程卷入死锁。如果进程申请资源不能满足就立刻进行检测,那麽每当死锁形成时即能被发现,这和死锁避免的算法相近,只是系统的开销较大。为了减小死锁检测带来的系统开销,一般采取每隔一段时间进行一次死锁检测,或者在CPU的利用率降低到某一数值时,进行死锁的检测。 

2.死锁的恢复  

  一旦在死锁检测时发现了死锁,就要消除死锁,使系统从死锁状态中恢复过来。  

    (1)最简单,最常用的方法就是进行系统的重新启动,不过这种方法代价很大,它意味着在这之前所有的进程已经完成的计算工作都将付之东流,包括参与死锁的那些进程,以及未参与死锁的进程。

    (2)撤消进程,剥夺资源。终止参与死锁的进程,收回它们占有的资源,从而解除死锁。这时又分两种情况:一次性撤消参与死锁的全部进程,剥夺全部资源;或者逐步撤消参与死锁的进程,逐步收回死锁进程占有的资源。一般来说,选择逐步撤消的进程时要按照一定的原则进行,目的是撤消那些代价最小的进程,比如按进程的优先级确定进程的代价;考虑进程运行时的代价和与此进程相关的外部作业的代价等因素。 

  此外,还有进程回退策略,即让参与死锁的进程回退到没有发生死锁前某一点处,并由此点处继续执行,以求再次执行时不再发生死锁。虽然这是个较理想的办法,但是操作起来系统开销极大,要有堆栈这样的机构记录进程的每一步变化,以便今后的回退,有时这是无法做到的。

2015-09-21 20:58:13 bigpudding24 阅读数 3678

2.17 死锁的概念以及产生死锁的原因

死锁的定义

在多道程序系统中,由于多个进程的并发执行,改善了系统资源的利用率并提高了系统 的处理能力。然而,多个进程的并发执行也带来了新的问题——死锁。所谓死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进

下面我们通过一些实例来说明死锁现象。

先看生活中的一个实例,在一条河上有一座桥,桥面很窄,只能容纳一辆汽车通行。如果有两辆汽车分别从桥的左右两端驶上该桥,则会出现下述的冲突情况。此时,左边的汽车占有了桥面左边的一段,要想过桥还需等待右边的汽车让出桥面右边的一段;右边的汽车占有了桥面右边的一段,要想过桥还需等待左边的汽车让出桥面左边的一段。此时,若左右两边的汽车都只能向前行驶,则两辆汽车都无法过桥。

在计算机系统中也存在类似的情况。例如,某计算机系统中只有一台打印机和一台输入设备,进程P1正占用输入设备,同时又提出使用打印机的请求,但此时打印机正被进程P2 所占用,而P2在未释放打印机之前,又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去,均无法继续执行,此时两个进程陷入死锁状态。

死锁产生的原因

1) 系统资源的竞争

通常系统中拥有的不可剥夺资源,其数量不足以满足多个进程运行的需要,使得进程在运行过程中,会因争夺资源而陷入僵局,如磁带机、打印机等。只有对不可剥夺资源的竞争才可能产生死锁,对可剥夺资源的竞争是不会引起死锁的

2) 进程推进顺序非法

进程在运行过程中,请求和释放资源的顺序不当,也同样会导致死锁。例如,并发进程 P1、P2分别保持了资源R1、R2,而进程P1申请资源R2,进程P2申请资源R1时,两者都会因为所需资源被占用而阻塞。

信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息,结果也会使得这些进程间无法继续向前推进。例如,进程A等待进程B发的消息,进程B又在等待进程A 发的消息,可以看出进程A和B不是因为竞争同一资源,而是在等待对方的资源导致死锁

3) 死锁产生的必要条件

产生死锁必须同时满足以下四个条件,只要其中任一条件不成立,死锁就不会发生。
  • 互斥条件:进程要求对所分配的资源(如打印机)进行排他性控制,即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源,则请求进程只能等待。
  • 不剥夺条件:进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能由获得该资源的进程自己来释放(只能是主动释放)。
  • 请求和保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已被其他进程占有,此时请求进程被阻塞,但对自己已获得的资源保持不放。
  • 循环等待条件:存在一种进程资源的循环等待链,链中每一个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待状态的进程集合{Pl, P2, ..., pn},其中Pi等待的资源被P(i+1)占有(i=0, 1, ..., n-1),Pn等待的资源被P0占有,如图2-15所示。

2.18 死锁的处理策略

为使系统不发生死锁,必须设法破坏产生死锁的四个必要条件之一,或者允许死锁产生, 但当死锁发生时能检测出死锁,并有能力实现恢复。

预防死锁

设置某些限制条件,破坏产生死锁的四个必要条件中的一个或几个,以防止发生死锁。

避免死锁

在资源的动态分配过程中,用某种方法防止系统进入不安全状态,从而避免死锁。

死锁的检测及解除

无需釆取任何限制性措施,允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生,然后釆取某种措施解除死锁。

预防死锁和避免死锁都属于事先预防策略,但预防死锁的限制条件比较严格,实现起来较为简单,但往往导致系统的效率低,资源利用率低;避免死锁的限制条件相对宽松,资源分配后需要通过算法来判断是否进入不安全状态,实现起来较为复杂。

死锁的几种处理策略的比较见表2-14。

表2-14 死锁处理策略的比较
-- 资源分配策略 各种可能模式 主要优点 主要缺点
死锁预防 保守,宁可资源闲置 一次请求所有资源,资 源剥夺,资源按序分配 适用于做突发式处理的进程,不必进行剥夺 效率低,进程初始化时间延长;剥夺次数过多;不便灵活申请新资源
死锁避免 是”预防“和”检测“ 的折中(在运行时判断是否可能死锁) 寻找可能的安全允许顺序 不必进行剥夺 必须知道将来的资源需求;进程不能被长时间阻塞
死锁检测 宽松,只要允许就分配资源 定期检查死锁是否已经发生 不延长进程初始化时间,允许对死锁进行现场处理 通过剥夺解除死锁,造成损失


2.19 死锁预防和死锁避免

死锁预防

防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。

1) 破坏互斥条件

如果允许系统资源都能共享使用,则系统不会进入死锁状态。但有些资源根本不能同时访问,如打印机等临界资源只能互斥使用。所以,破坏互斥条件而预防死锁的方法不太可行,而且在有的场合应该保护这种互斥性。

2) 破坏不剥夺条件

当一个已保持了某些不可剥夺资源的进程,请求新的资源而得不到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请。这意味着,一个进程已占有的资源会被暂时释放,或者说是被剥夺了,或从而破坏了不可剥夺条件。

该策略实现起来比较复杂,释放已获得的资源可能造成前一阶段工作的失效,反复地申请和释放资源会增加系统开销,降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源,如CPU的寄存器及内存资源,一般不能用于打印机之类的资源。

3) 破坏请求和保持条件

釆用预先静态分配方法,即进程在运行前一次申请完它所需要的全部资源,在它的资源未满足前,不把它投入运行。一旦投入运行后,这些资源就一直归它所有,也不再提出其他资源请求,这样就可以保证系统不会发生死锁。

这种方式实现简单,但缺点也显而易见,系统资源被严重浪费,其中有些资源可能仅在运行初期或运行快结束时才使用,甚至根本不使用。而且还会导致“饥饿”现象,当由于个别资源长期被其他进程占用时,将致使等待该资源的进程迟迟不能开始运行。

4) 破坏循环等待条件

为了破坏循环等待条件,可釆用顺序资源分配法。首先给系统中的资源编号,规定每个进程,必须按编号递增的顺序请求资源,同类资源一次申请完。也就是说,只要进程提出申请分配资源Ri,则该进程在以后的资源申请中,只能申请编号大于Ri的资源。

这种方法存在的问题是,编号必须相对稳定,这就限制了新类型设备的增加;尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序,但也经常会发生作业使甩资源的顺序与系统规定顺序不同的情况,造成资源的浪费;此外,这种按规定次序申请资源的方法,也必然会给用户的编程带来麻烦。

死锁避免

避免死锁同样是属于事先预防的策略,但并不是事先釆取某种限制措施破坏死锁的必要条件,而是在资源动态分配过程中,防止系统进入不安全状态,以避免发生死锁。这种方法所施加的限制条件较弱,可以获得较好的系统性能。

1. 系统安全状态

避免死锁的方法中,允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程; 否则,让进程等待。

所谓安全状态,是指系统能按某种进程推进顺序( P1, P2, ..., Pn),为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺序地完成。此时称 P1, P2, ..., Pn 为安全序列。如果系统无法找到一个安全序列,则称系统处于不安全状态。

假设系统中有三个进程P1、P2和P3,共有12 台磁带机。进程P1总共需要10台磁带机,P2和P3 分别需要4台和9台。假设在T0时刻,进程P1、P2 和P3已分别获得5合、2台和2台,尚有3台未分配,见表2-15。

表2-15 资源分配
进程 最大需求 已分配 可用
P1 10 5 3
P2 4 2
P3 9 2

则在T0时刻是安全的,因为存在一个安全序列P2、Pl、P3,即只要系统按此进程序列分配资源,则每个进程都能顺利完成。若在T0时刻后,系统分配1台磁带机给P3,则此时系统便进入不安全状态,因为此时已无法再找到一个安全序列。

并非所有的不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状态;反之,只要系统处于安全状态,系统便可以避免进入死锁状态。

2. 银行家算法

银行家算法是最著名的死锁避免算法。它提出的思想是:把操作系统看做是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。

1) 数据结构描述
可利用资源矢量Available:含有m个元素的歎组,其中的每一个元素代表一类可用的资源数目。Available[j]=K,则表示系统中现有Rj类资源K个。

最大需求矩阵Max:为n*m矩阵,定义了系统中n个进程中的每一个进程对m类资源的最大需求。Max[i, j]=K,则表示进程i需要Rj类资源的最大数目为K。

分配矩阵Allocation:为n*m矩阵,定义了系统中每一类资源当前已分配给每一进程的资源数。All0Cati0n[i, j]= K,则表示进程i当前已分得Rj类资源的数目为K。

需求矩阵Need:为n*m矩阵,表示每个进程尚需的各类资源数。Need[i, j]=K,则表示进程i还需要Rj类资源的数目为K。

上述三个矩阵间存在下述关系:
Need[i, j] = Max[i, j] - Allocation[i, j]

2) 银行家算法描述
设Requesti是进程Pi的请求矢量,如果Requesti[j]K,表示进程Pi需要Rj类资源K个。当Pi发出资源请求后,系统按下述步骤进行检查:

①如果Requesti[j] <= Need[i, j],便转向步骤②;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

②如果Requesti[j] <= Available[j],便转向步骤③;否则,表示尚无足够资源,Pi须等待。

③系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:
Available[j] = Available[j] - Requesti[j];
Allocation[i, j] = Allocation[i, j] + Requesti[ j];
Need[i, j] = Need[i, j] - Requesti[j];
④系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

3) 安全性算法
①设置两个矢量。工作矢量Work;它表示系统可提供给进程继续运行所需的各类资源数目,它含有所个元素,在执行安全算法开始时,Work=Available; Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时 Finish[i]=false;当有足够资源分配给进程 Pi 时,再令 Finish[i]=true。

②从进程集合中找到一个能满足下述条件的进程:Finish[i]=false;    Need[i, j]<=Work[j]; 若找到,执行下一步骤,否则,执行步骤4。

③当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
Work[j]=Work[j]+Allocation[i, j];
Finish[i]=true;
go to step <2>;
④如果所有进程的Finish[i]=tme都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

3. 银行家算法举例

假定系统中有5个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况见表2-16。

1) T0时刻的安全性。
利用安全性算法对T0时刻的资源分配进行分析,由表2-17可知,在T0时刻存在着一个安全序列{P1, P3, P4, P2, P0},故系统是安全的。

表2-16 T0时刻的资源分配
进程 / 资源情况 Max
A  B  C
Allocation
A  B  C
Need
A  B  C
Available
A  B  C
P0 7  5  3 0  1  0 7  4  3 3  3  2
(2  3  0)
P1 3  2  2 2  0  0
(3  0  2)
1  2  2
(0  2  0)

P2 9  0  2 3  0  2 6  0  0
P3 2  2  2 2  1  1 0  1  1
P4 4  3  3 0  0  2 4  3  1

表2-17 T0时刻的安全序列
进程 / 资源情况 Work
A  B  C
Need
A  B  C
Allocation
A  B  C
Work+Allocation
A  B  C
Finish
P1 3  3  2 1  2  2 2  0  0 5  3  2 true
P3 5  3  2 0  1  1 2  1  1 7  4  3 true
P4 7  4  3 4  3  1 0  0  2 7  4  5 true
P2 7  4  5 6  0  0 3  0  2 10  4  7 true
P0 10  4  7 7  4  3 0  1  0 10  5  7 true

2) P1请求资源
P1发出请求矢量Request1(l,, 0, 2),系统按银行家算法进行检查:
  • Request1(1, 0, 2) <= Need1(l, 2, 2)。
  • Request1(1, 0, 2) <= Available1(3, 3, 2)。
  • 系统先假定可为P1分配资源,并修改Available、Allocation1和Need1矢量,由此形成的资源变化情况见表2-18。
  • 再利用安全性算法检查此时系统是否安全。

表2-18 P1申请资源时的安全性检测
进程 / 资源情况 Work
A  B  C
Need
A  B  C
Allocation
A  B  C
Work+ Allocation
A  B  C
Finish
P1 2  3  0 0  2  0 3  0  2 5  3  2 true
P3 5  3  2 0  1  1 2  1  1 7  4  3 true
P4 7  4  3 4  3  1 0  0  2 7  4  5 true
P0 7  4  5 7  4  3 0  1  0 7  5  5 true
P2 7  5  5 6  0  0 3  0  2 10  5  7 true

3) P4请求资源
P4发出请求矢量Request4(3, 3, 0),系统按银行家算法进行检查:
  • Request4(3, 3, 0) <= Need4(4, 3, 1)。
  • Request4(3, 3, 0) > Available(2, 3, 0),让 P4 等待。

4) P0请求资源
P0发出请求矢量Request0(0, 2, 0),系统按银行家算法进行检查:
  • Request0(0, 2, 0) <= Need0(7, 4, 3)。
  • Request0(0, 2, 0) <= Available(2, 3, 0)。
  • 系统暂时先假定可为P0分配资源,并修改有关数据,见表2-19。

表2-19 为P0分配资源后的有关资源数据
进程 / 资源情况 Allocation
A  B  C
Need
A  B  C
Available
A  B  C
P0 0  3  0 7  2  3 2  1  0
P1 3  0  2 0  2  0
P2 3  0  2 6  0  0
P3 2  1  1 0  1  1
P4 0  0  2 4  3  1

5) 进行安全性检测。
可用资源Available(2, 1, 0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源。

2.20 死锁的检测和解除

前面绍的死锁预防和避免算法,都是在为进程分配资源时施加限制条件或进行检测,若系统为进程分配资源时不釆取任何措施,则应该提供死锁检测和解除的手段。

资源分配图

系统死锁,可利用资源分配图来描述。如图2-17所示,用圆圈代表一个进程,用框代表一类资源。由于一种类型的资源可能有多个,用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边,表示该进程申请一个单位的该类资源;从资源到进程的边叫分配边,表示该类资源已经有一个资源被分配给了该进程。


图2-17  资源分配示例图

在图2-17所示的资源分配图中,进程P1已经分得了两个R1资源,并又请求一个R2 资源;进程P2分得了一个R1和一个R2资源,并又请求一个R1资源。

死锁定理

可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。简化方法如下:

1) 在资源分配图中,找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连,且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件,则这个进程能继续运行直至完成,然后释放它所占有的所有资源)。消去它所有的请求边和分配边,使之成为孤立的结点。在图2-18(a)中,P1是满足这一条件的进程结点,将P1的所有边消去,便得到图248(b)所示的情况。

2) 进程Pi所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程。在图2-17中,进程P2就满足这样的条件。根据第1) 条中的方法进行一系列简化后,若能消去图中所有的边,则称该图是可完全简化的,如图2-18(c)所示。

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

死锁的解除

一旦检测出死锁,就应立即釆取相应的措施,以解除死锁。死锁解除的主要方法有:

1) 资源剥夺法。挂起某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源,而处于资源匮乏的状态。

2) 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。



图2-18  资源分配图的化简

3) 进程回退法。让一(多)个进程回退到足以回避死锁的地步,进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息,设置还原点。

2.21 关于进程和线程的知识点汇总

进程与程序的区别与联系

1) 进程是程序及其数据在计算机上的一次运行活动,是一个动态的概念。进程的运行实体是程序,离开程序的进程没有存在的意义。从静态角度看,进程是由程序、数据和进程控制块(PCB)三部分组成的。而程序是一组有序的指令集合,是一种静态的概念。

2) 进程是程序的一次执行过程,它是动态地创建和消亡的,具有一定的生命周期,是暂时存在的;而程序则是一组代码的集合,它是永久存在的,可长期保存。

3) 一个进程可以执行一个或几个程序,一个程序也可以构成多个进程。进程可创建进程,而程序不可能形成新的程序

4) 进程与程序的组成不同。进程的组成包括程序、数据和PCB。

死锁与饥饿

具有等待队列的信号量的实现可能导致这样的情况:两个或多个进程无限地等待一个事件,而该事件只能由这些等待进程之一来产生。这里的事件是V操作的执行(即释放资源)。当出现这样的状态时,这些进程称为死锁(Dead locked)。

为了加以说明,考虑到一个系统由两个进程P0和P1组成,每个进程都访问两个信号量S和Q,这两个信号量的初值均为1。
P0 () {
    While (1){
        P(S) ;
        P(Q);
        // …
        V(S) ;
        V(Q) ;
    }
}
p1() {
    While(1){
        P(Q);
        P(S);
        // …
        V(Q);
        V(S);
    }
}

假设进程P0执行P(S),接着进程P1执行P(Q)。当进程P0执行P(Q)时,它必须等待直到进程P1执行V(Q)。类似地,当进程P1执行P(S),它必须等待直到进程P0执行V(S)。由于这两个V操作都不能执行,那么进程P0和进程P1就死锁了。

说一组进程处于死锁状态是指:组内的每个进程都等待一个事件,而该事件只可能由组内的另一个进程产生。这里所关心的主要是事件是资源的获取和释放。

与死锁相关的另一个问题是无限期阻塞(Indefinite Blocking)或“饥饿” (Starvation),即进程在信号量内无穷等待的情况。

产生饥饿的主要原因是:在一个动态系统中,对于每类系统资源,操作系统需要确定一个分配策略,当多个进程同时申请某类资源时,由分配策略确定资源分配给进程的次序。有时资源分配策略可能是不公平的,即不能保证等待时间上界的存在。在这种情况下,即使系统没有发生死锁,某些进程也可能会长时间等待。当等待时间给进程推进和响应带来明显影响时,称发生了进程“饥饿”,当“饥饿”到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被“饿死”。

例如,当有多个进程需要打印文件时,如果系统分配打印机的策略是最短文件优先,那么长文件的打印任务将由于短文件的源源不断到来而被无限期推迟,导致最终的“饥饿”甚至“饿死”。

“饥饿”并不表示系统一定死锁,但至少有一个进程的执行被无限期推迟。“饥饿”与死锁的主要差别有:
  • 进入“饥饿”状态的进程可以只有一个,而由于循环等待条件而进入死锁状态的进程却必须大于或等于两个。
  • 处于“饥饿”状态的进程可以是一个就绪进程,如静态优先权调度算法时的低优先权进程,而处于死锁状态的进程则必定是阻塞进程。

银行家算法的工作原理

银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时,它首先检查系统是否有足够的资源满足要求,如果有,则先进行分配,并对分配后的新状态进行安全性检查。如果新状态安全,则正式分配上述资源,否则就拒绝分配上述资源。这样,它保证系统始终处于安全状态,从而避免死锁现象的发生。

进程同步、互斥的区别和联系

并发进程的执行会产生相互制约的关系:一种是进程之间竞争使用临界资源,只能让它们逐个使用,这种现象称为互斥,是一种竞争关系;另一种是进程之间协同完成任务,在关键点上等待另一个进程发来的消息,以便协同一致,是一种协作关系。

作业和进程的关系

进程是系统资源的使用者,系统的资源大部分都是以进程为单位分配的。而用户使用计算机是为了实现一串相关的任务,通常把用户要求计算机完成的这一串任务称为作业。

1) 批处理系统中作业与进程的关系(进程组织)

批处理系统中的可以通过磁记录设备或卡片机向系统提交批作业,由系统的SPOOLing 输入进程将作业放入磁盘的输入井中,作为后备作业。作业调度程序(一般也作为独立的进程运行)每当选择一道后备作业运行时,首先为该作业创建一个进程(称为该作业的根进程)。该进程将执行作业控制语言解释程序解释该作业的作业说明书。父进程在运行过程中可以动态地创建一个或多个子进程,执行说明书中的语句。
例如,对一条编译的语句,该进程可以创建一个子进程执行编译程序对用户源程序进行编译。类似地,子进程也可以继续创建子进程去完成指定的功能。因此,一个作业就动态地转换成了一组运行实体——进程族。当父进程遇到作业说明书中的“撤出作业”的语句时,将该作业从运行状态改变为完成状态,将作业及相关结果送入磁盘上的输出井。作业终止进程负责将输出井中的作业利用打印机输出,回收作业所占用的资源,删除作业有关数据结构,删除作业在磁盘输出井中的信息,等等。作业终止进程撤除一道作业后,可向作业调度进程请求进行新的作业调度。至此,一道进入系统运行的作业全部结束。

2) 分时系统中作业与进程的关系

在分时系统中,作业的提交方法、组织形式均与批处理作业有很大差异。分时系统的用户通过命令语言逐条地与系统应答式地输入命令,提交作业步。每输入一条(或一组)命令,便直接在系统内部对应一个(或若干个)进程。在系统启动时,系统为每个终端设备建立一个进程(称为终端进程),该进程执行命令解释程序,命令解释程序从终端设备读入命令解释执行用户输入的每一条命令。对于每一条终端命令,可以创建一个子进程去具体执行。若当前的终端命令是一条后台命令,则可以和下一条终端命令并行处理。各子进程在运行过程中完全可以根据需要创建子孙进程。终端命令所对应的进程结束后,命令的功能也相应处理完毕。用户本次上机完毕,用户通过一条登出命令即结束上机过程。

分时系统的作业就是用户的一次上机交互过程,可以认为终端进程的创建是一个交互作业的开始,登出命令运行结束代表用户交互作业的终止。

命令解释程序流程扮演着批处理系统中作业控制语言解释程序的角色,只不过命令解释程序是从用户终端接收命令。

3) 交互地提交批作业

在同时支持交互和批处理的操作系统中,人们可以用交互的方式准备好批作业的有关程序、数据及作业控制说明书。
比如,可用交互式系统提供的全屏幕编辑命令编辑好自编的一个天气预报程序,用编译及装配命令将程序变成可执行文件,用调试命令进行程序调试。在调试成功后,用户每天都要做如下工作:准备原始天气数据,运行天气预报执行文件处理原始数据,把结果打印出来等。这时,用交互系统提供的全屏幕编辑命令编辑好将要提交的作业控制说明书文件,如Windows系统的BAT文件和Linux系统的sh文件。然后用一条作业提交命令将作业提交给系统作业队列中。系统有专门的作业调度进程负责从作业队列中选择作业,为被选取的作业创建一个父进程运行命令解释程序,解释执行作业控制说明书文件中的命令。


2017-11-14 17:23:59 yongchaocsdn 阅读数 5570
转载自:http://blog.csdn.net/bigpudding24/article/details/48608579

2.17 死锁的概念以及产生死锁的原因

死锁的定义

在多道程序系统中,由于多个进程的并发执行,改善了系统资源的利用率并提高了系统 的处理能力。然而,多个进程的并发执行也带来了新的问题——死锁。所谓死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进

下面我们通过一些实例来说明死锁现象。

先看生活中的一个实例,在一条河上有一座桥,桥面很窄,只能容纳一辆汽车通行。如果有两辆汽车分别从桥的左右两端驶上该桥,则会出现下述的冲突情况。此时,左边的汽车占有了桥面左边的一段,要想过桥还需等待右边的汽车让出桥面右边的一段;右边的汽车占有了桥面右边的一段,要想过桥还需等待左边的汽车让出桥面左边的一段。此时,若左右两边的汽车都只能向前行驶,则两辆汽车都无法过桥。

在计算机系统中也存在类似的情况。例如,某计算机系统中只有一台打印机和一台输入设备,进程P1正占用输入设备,同时又提出使用打印机的请求,但此时打印机正被进程P2 所占用,而P2在未释放打印机之前,又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去,均无法继续执行,此时两个进程陷入死锁状态。

死锁产生的原因

1) 系统资源的竞争

通常系统中拥有的不可剥夺资源,其数量不足以满足多个进程运行的需要,使得进程在运行过程中,会因争夺资源而陷入僵局,如磁带机、打印机等。只有对不可剥夺资源的竞争才可能产生死锁,对可剥夺资源的竞争是不会引起死锁的

2) 进程推进顺序非法

进程在运行过程中,请求和释放资源的顺序不当,也同样会导致死锁。例如,并发进程 P1、P2分别保持了资源R1、R2,而进程P1申请资源R2,进程P2申请资源R1时,两者都会因为所需资源被占用而阻塞。

信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息,结果也会使得这些进程间无法继续向前推进。例如,进程A等待进程B发的消息,进程B又在等待进程A 发的消息,可以看出进程A和B不是因为竞争同一资源,而是在等待对方的资源导致死锁

3) 死锁产生的必要条件

产生死锁必须同时满足以下四个条件,只要其中任一条件不成立,死锁就不会发生。
  • 互斥条件:进程要求对所分配的资源(如打印机)进行排他性控制,即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源,则请求进程只能等待。
  • 不剥夺条件:进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能由获得该资源的进程自己来释放(只能是主动释放)。
  • 请求和保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已被其他进程占有,此时请求进程被阻塞,但对自己已获得的资源保持不放。
  • 循环等待条件:存在一种进程资源的循环等待链,链中每一个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待状态的进程集合{Pl, P2, …, pn},其中Pi等待的资源被P(i+1)占有(i=0, 1, …, n-1),Pn等待的资源被P0占有,如图2-15所示。

2.18 死锁的处理策略

为使系统不发生死锁,必须设法破坏产生死锁的四个必要条件之一,或者允许死锁产生, 但当死锁发生时能检测出死锁,并有能力实现恢复。

预防死锁

设置某些限制条件,破坏产生死锁的四个必要条件中的一个或几个,以防止发生死锁。

避免死锁

在资源的动态分配过程中,用某种方法防止系统进入不安全状态,从而避免死锁。

死锁的检测及解除

无需釆取任何限制性措施,允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生,然后釆取某种措施解除死锁。

预防死锁和避免死锁都属于事先预防策略,但预防死锁的限制条件比较严格,实现起来较为简单,但往往导致系统的效率低,资源利用率低;避免死锁的限制条件相对宽松,资源分配后需要通过算法来判断是否进入不安全状态,实现起来较为复杂。

死锁的几种处理策略的比较见表2-14。

表2-14 死锁处理策略的比较
资源分配策略 各种可能模式 主要优点 主要缺点
死锁预防 保守,宁可资源闲置 一次请求所有资源,资 源剥夺,资源按序分配 适用于做突发式处理的进程,不必进行剥夺 效率低,进程初始化时间延长;剥夺次数过多;不便灵活申请新资源
死锁避免 是”预防“和”检测“ 的折中(在运行时判断是否可能死锁) 寻找可能的安全允许顺序 不必进行剥夺 必须知道将来的资源需求;进程不能被长时间阻塞
死锁检测 宽松,只要允许就分配资源 定期检查死锁是否已经发生 不延长进程初始化时间,允许对死锁进行现场处理 通过剥夺解除死锁,造成损失


2.19 死锁预防和死锁避免

死锁预防

防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。

1) 破坏互斥条件

如果允许系统资源都能共享使用,则系统不会进入死锁状态。但有些资源根本不能同时访问,如打印机等临界资源只能互斥使用。所以,破坏互斥条件而预防死锁的方法不太可行,而且在有的场合应该保护这种互斥性。

2) 破坏不剥夺条件

当一个已保持了某些不可剥夺资源的进程,请求新的资源而得不到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请。这意味着,一个进程已占有的资源会被暂时释放,或者说是被剥夺了,或从而破坏了不可剥夺条件。

该策略实现起来比较复杂,释放已获得的资源可能造成前一阶段工作的失效,反复地申请和释放资源会增加系统开销,降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源,如CPU的寄存器及内存资源,一般不能用于打印机之类的资源。

3) 破坏请求和保持条件

釆用预先静态分配方法,即进程在运行前一次申请完它所需要的全部资源,在它的资源未满足前,不把它投入运行。一旦投入运行后,这些资源就一直归它所有,也不再提出其他资源请求,这样就可以保证系统不会发生死锁。

这种方式实现简单,但缺点也显而易见,系统资源被严重浪费,其中有些资源可能仅在运行初期或运行快结束时才使用,甚至根本不使用。而且还会导致“饥饿”现象,当由于个别资源长期被其他进程占用时,将致使等待该资源的进程迟迟不能开始运行。

4) 破坏循环等待条件

为了破坏循环等待条件,可釆用顺序资源分配法。首先给系统中的资源编号,规定每个进程,必须按编号递增的顺序请求资源,同类资源一次申请完。也就是说,只要进程提出申请分配资源Ri,则该进程在以后的资源申请中,只能申请编号大于Ri的资源。

这种方法存在的问题是,编号必须相对稳定,这就限制了新类型设备的增加;尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序,但也经常会发生作业使甩资源的顺序与系统规定顺序不同的情况,造成资源的浪费;此外,这种按规定次序申请资源的方法,也必然会给用户的编程带来麻烦。

死锁避免

避免死锁同样是属于事先预防的策略,但并不是事先釆取某种限制措施破坏死锁的必要条件,而是在资源动态分配过程中,防止系统进入不安全状态,以避免发生死锁。这种方法所施加的限制条件较弱,可以获得较好的系统性能。

1. 系统安全状态

避免死锁的方法中,允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程; 否则,让进程等待。

所谓安全状态,是指系统能按某种进程推进顺序( P1, P2, …, Pn),为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺序地完成。此时称 P1, P2, …, Pn 为安全序列。如果系统无法找到一个安全序列,则称系统处于不安全状态。

假设系统中有三个进程P1、P2和P3,共有12 台磁带机。进程P1总共需要10台磁带机,P2和P3 分别需要4台和9台。假设在T0时刻,进程P1、P2 和P3已分别获得5合、2台和2台,尚有3台未分配,见表2-15。

表2-15 资源分配
进程 最大需求 已分配 可用
P1 10 5 3
P2 4 2
P3 9 2

则在T0时刻是安全的,因为存在一个安全序列P2、Pl、P3,即只要系统按此进程序列分配资源,则每个进程都能顺利完成。若在T0时刻后,系统分配1台磁带机给P3,则此时系统便进入不安全状态,因为此时已无法再找到一个安全序列。

并非所有的不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状态;反之,只要系统处于安全状态,系统便可以避免进入死锁状态。

2. 银行家算法

银行家算法是最著名的死锁避免算法。它提出的思想是:把操作系统看做是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。

1) 数据结构描述
可利用资源矢量Available:含有m个元素的歎组,其中的每一个元素代表一类可用的资源数目。Available[j]=K,则表示系统中现有Rj类资源K个。

最大需求矩阵Max:为n*m矩阵,定义了系统中n个进程中的每一个进程对m类资源的最大需求。Max[i, j]=K,则表示进程i需要Rj类资源的最大数目为K。

分配矩阵Allocation:为n*m矩阵,定义了系统中每一类资源当前已分配给每一进程的资源数。All0Cati0n[i, j]= K,则表示进程i当前已分得Rj类资源的数目为K。

需求矩阵Need:为n*m矩阵,表示每个进程尚需的各类资源数。Need[i, j]=K,则表示进程i还需要Rj类资源的数目为K。

上述三个矩阵间存在下述关系:
Need[i, j] = Max[i, j] - Allocation[i, j]

2) 银行家算法描述
设Requesti是进程Pi的请求矢量,如果Requesti[j]K,表示进程Pi需要Rj类资源K个。当Pi发出资源请求后,系统按下述步骤进行检查:

①如果Requesti[j] <= Need[i, j],便转向步骤②;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

②如果Requesti[j] <= Available[j],便转向步骤③;否则,表示尚无足够资源,Pi须等待。

③系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:
  1. Available[j] = Available[j] - Requesti[j];  
  2. Allocation[i, j] = Allocation[i, j] + Requesti[ j];  
  3. Need[i, j] = Need[i, j] - Requesti[j];  
Available[j] = Available[j] - Requesti[j];
Allocation[i, j] = Allocation[i, j] + Requesti[ j];
Need[i, j] = Need[i, j] - Requesti[j];
④系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

3) 安全性算法
①设置两个矢量。工作矢量Work;它表示系统可提供给进程继续运行所需的各类资源数目,它含有所个元素,在执行安全算法开始时,Work=Available; Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时 Finish[i]=false;当有足够资源分配给进程 Pi 时,再令 Finish[i]=true。

②从进程集合中找到一个能满足下述条件的进程:Finish[i]=false;    Need[i, j]<=Work[j]; 若找到,执行下一步骤,否则,执行步骤4。

③当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
  1. Work[j]=Work[j]+Allocation[i, j];  
  2. Finish[i]=true;  
  3. go to step <2>;  
Work[j]=Work[j]+Allocation[i, j];
Finish[i]=true;
go to step <2>;
④如果所有进程的Finish[i]=tme都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

3. 银行家算法举例

假定系统中有5个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况见表2-16。

1) T0时刻的安全性。
利用安全性算法对T0时刻的资源分配进行分析,由表2-17可知,在T0时刻存在着一个安全序列{P1, P3, P4, P2, P0},故系统是安全的。

表2-16 T0时刻的资源分配
进程 / 资源情况 Max
A  B  C
Allocation
A  B  C
Need
A  B  C
Available
A  B  C
P0 7  5  3 0  1  0 7  4  3 3  3  2
(2  3  0)
P1 3  2  2 2  0  0
(3  0  2)
1  2  2
(0  2  0)

P2 9  0  2 3  0  2 6  0  0
P3 2  2  2 2  1  1 0  1  1
P4 4  3  3 0  0  2 4  3  1

表2-17 T0时刻的安全序列
进程 / 资源情况 Work
A  B  C
Need
A  B  C
Allocation
A  B  C
Work+Allocation
A  B  C
Finish
P1 3  3  2 1  2  2 2  0  0 5  3  2 true
P3 5  3  2 0  1  1 2  1  1 7  4  3 true
P4 7  4  3 4  3  1 0  0  2 7  4  5 true
P2 7  4  5 6  0  0 3  0  2 10  4  7 true
P0 10  4  7 7  4  3 0  1  0 10  5  7 true

2) P1请求资源
P1发出请求矢量Request1(l,, 0, 2),系统按银行家算法进行检查:
  • Request1(1, 0, 2) <= Need1(l, 2, 2)。
  • Request1(1, 0, 2) <= Available1(3, 3, 2)。
  • 系统先假定可为P1分配资源,并修改Available、Allocation1和Need1矢量,由此形成的资源变化情况见表2-18。
  • 再利用安全性算法检查此时系统是否安全。

表2-18 P1申请资源时的安全性检测
进程 / 资源情况 Work
A  B  C
Need
A  B  C
Allocation
A  B  C
Work+ Allocation
A  B  C
Finish
P1 2  3  0 0  2  0 3  0  2 5  3  2 true
P3 5  3  2 0  1  1 2  1  1 7  4  3 true
P4 7  4  3 4  3  1 0  0  2 7  4  5 true
P0 7  4  5 7  4  3 0  1  0 7  5  5 true
P2 7  5  5 6  0  0 3  0  2 10  5  7 true

3) P4请求资源
P4发出请求矢量Request4(3, 3, 0),系统按银行家算法进行检查:
  • Request4(3, 3, 0) <= Need4(4, 3, 1)。
  • Request4(3, 3, 0) > Available(2, 3, 0),让 P4 等待。

4) P0请求资源
P0发出请求矢量Request0(0, 2, 0),系统按银行家算法进行检查:
  • Request0(0, 2, 0) <= Need0(7, 4, 3)。
  • Request0(0, 2, 0) <= Available(2, 3, 0)。
  • 系统暂时先假定可为P0分配资源,并修改有关数据,见表2-19。

表2-19 为P0分配资源后的有关资源数据
进程 / 资源情况 Allocation
A  B  C
Need
A  B  C
Available
A  B  C
P0 0  3  0 7  2  3 2  1  0
P1 3  0  2 0  2  0
P2 3  0  2 6  0  0
P3 2  1  1 0  1  1
P4 0  0  2 4  3  1

5) 进行安全性检测。
可用资源Available(2, 1, 0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源。

2.20 死锁的检测和解除

前面绍的死锁预防和避免算法,都是在为进程分配资源时施加限制条件或进行检测,若系统为进程分配资源时不釆取任何措施,则应该提供死锁检测和解除的手段。

资源分配图

系统死锁,可利用资源分配图来描述。如图2-17所示,用圆圈代表一个进程,用框代表一类资源。由于一种类型的资源可能有多个,用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边,表示该进程申请一个单位的该类资源;从资源到进程的边叫分配边,表示该类资源已经有一个资源被分配给了该进程。


图2-17  资源分配示例图


在图2-17所示的资源分配图中,进程P1已经分得了两个R1资源,并又请求一个R2 资源;进程P2分得了一个R1和一个R2资源,并又请求一个R1资源。

死锁定理

可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。简化方法如下:

1) 在资源分配图中,找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连,且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件,则这个进程能继续运行直至完成,然后释放它所占有的所有资源)。消去它所有的请求边和分配边,使之成为孤立的结点。在图2-18(a)中,P1是满足这一条件的进程结点,将P1的所有边消去,便得到图248(b)所示的情况。

2) 进程Pi所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程。在图2-17中,进程P2就满足这样的条件。根据第1) 条中的方法进行一系列简化后,若能消去图中所有的边,则称该图是可完全简化的,如图2-18(c)所示。

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

死锁的解除

一旦检测出死锁,就应立即釆取相应的措施,以解除死锁。死锁解除的主要方法有:

1) 资源剥夺法。挂起某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源,而处于资源匮乏的状态。

2) 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。



图2-18  资源分配图的化简


3) 进程回退法。让一(多)个进程回退到足以回避死锁的地步,进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息,设置还原点。


2.21 关于进程和线程的知识点汇总

进程与程序的区别与联系

1) 进程是程序及其数据在计算机上的一次运行活动,是一个动态的概念。进程的运行实体是程序,离开程序的进程没有存在的意义。从静态角度看,进程是由程序、数据和进程控制块(PCB)三部分组成的。而程序是一组有序的指令集合,是一种静态的概念。

2) 进程是程序的一次执行过程,它是动态地创建和消亡的,具有一定的生命周期,是暂时存在的;而程序则是一组代码的集合,它是永久存在的,可长期保存。

3) 一个进程可以执行一个或几个程序,一个程序也可以构成多个进程。进程可创建进程,而程序不可能形成新的程序

4) 进程与程序的组成不同。进程的组成包括程序、数据和PCB。

死锁与饥饿

具有等待队列的信号量的实现可能导致这样的情况:两个或多个进程无限地等待一个事件,而该事件只能由这些等待进程之一来产生。这里的事件是V操作的执行(即释放资源)。当出现这样的状态时,这些进程称为死锁(Dead locked)。

为了加以说明,考虑到一个系统由两个进程P0和P1组成,每个进程都访问两个信号量S和Q,这两个信号量的初值均为1。
  1. P0 () {  
  2.     While (1){  
  3.         P(S) ;  
  4.         P(Q);  
  5.         // …  
  6.         V(S) ;  
  7.         V(Q) ;  
  8.     }  
  9. }  
P0 () {
    While (1){
        P(S) ;
        P(Q);
        // …
        V(S) ;
        V(Q) ;
    }
}
  1. p1() {  
  2.     While(1){  
  3.         P(Q);  
  4.         P(S);  
  5.         // …  
  6.         V(Q);  
  7.         V(S);  
  8.     }  
  9. }  
p1() {
    While(1){
        P(Q);
        P(S);
        // …
        V(Q);
        V(S);
    }
}

假设进程P0执行P(S),接着进程P1执行P(Q)。当进程P0执行P(Q)时,它必须等待直到进程P1执行V(Q)。类似地,当进程P1执行P(S),它必须等待直到进程P0执行V(S)。由于这两个V操作都不能执行,那么进程P0和进程P1就死锁了。

说一组进程处于死锁状态是指:组内的每个进程都等待一个事件,而该事件只可能由组内的另一个进程产生。这里所关心的主要是事件是资源的获取和释放。

与死锁相关的另一个问题是无限期阻塞(Indefinite Blocking)或“饥饿” (Starvation),即进程在信号量内无穷等待的情况。

产生饥饿的主要原因是:在一个动态系统中,对于每类系统资源,操作系统需要确定一个分配策略,当多个进程同时申请某类资源时,由分配策略确定资源分配给进程的次序。有时资源分配策略可能是不公平的,即不能保证等待时间上界的存在。在这种情况下,即使系统没有发生死锁,某些进程也可能会长时间等待。当等待时间给进程推进和响应带来明显影响时,称发生了进程“饥饿”,当“饥饿”到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被“饿死”。

例如,当有多个进程需要打印文件时,如果系统分配打印机的策略是最短文件优先,那么长文件的打印任务将由于短文件的源源不断到来而被无限期推迟,导致最终的“饥饿”甚至“饿死”。

“饥饿”并不表示系统一定死锁,但至少有一个进程的执行被无限期推迟。“饥饿”与死锁的主要差别有:

  • 进入“饥饿”状态的进程可以只有一个,而由于循环等待条件而进入死锁状态的进程却必须大于或等于两个。
  • 处于“饥饿”状态的进程可以是一个就绪进程,如静态优先权调度算法时的低优先权进程,而处于死锁状态的进程则必定是阻塞进程。

银行家算法的工作原理

银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时,它首先检查系统是否有足够的资源满足要求,如果有,则先进行分配,并对分配后的新状态进行安全性检查。如果新状态安全,则正式分配上述资源,否则就拒绝分配上述资源。这样,它保证系统始终处于安全状态,从而避免死锁现象的发生。

进程同步、互斥的区别和联系

并发进程的执行会产生相互制约的关系:一种是进程之间竞争使用临界资源,只能让它们逐个使用,这种现象称为互斥,是一种竞争关系;另一种是进程之间协同完成任务,在关键点上等待另一个进程发来的消息,以便协同一致,是一种协作关系。

作业和进程的关系

进程是系统资源的使用者,系统的资源大部分都是以进程为单位分配的。而用户使用计算机是为了实现一串相关的任务,通常把用户要求计算机完成的这一串任务称为作业。

1) 批处理系统中作业与进程的关系(进程组织)

批处理系统中的可以通过磁记录设备或卡片机向系统提交批作业,由系统的SPOOLing 输入进程将作业放入磁盘的输入井中,作为后备作业。作业调度程序(一般也作为独立的进程运行)每当选择一道后备作业运行时,首先为该作业创建一个进程(称为该作业的根进程)。该进程将执行作业控制语言解释程序解释该作业的作业说明书。父进程在运行过程中可以动态地创建一个或多个子进程,执行说明书中的语句。

例如,对一条编译的语句,该进程可以创建一个子进程执行编译程序对用户源程序进行编译。类似地,子进程也可以继续创建子进程去完成指定的功能。因此,一个作业就动态地转换成了一组运行实体——进程族。当父进程遇到作业说明书中的“撤出作业”的语句时,将该作业从运行状态改变为完成状态,将作业及相关结果送入磁盘上的输出井。作业终止进程负责将输出井中的作业利用打印机输出,回收作业所占用的资源,删除作业有关数据结构,删除作业在磁盘输出井中的信息,等等。作业终止进程撤除一道作业后,可向作业调度进程请求进行新的作业调度。至此,一道进入系统运行的作业全部结束。

2) 分时系统中作业与进程的关系

在分时系统中,作业的提交方法、组织形式均与批处理作业有很大差异。分时系统的用户通过命令语言逐条地与系统应答式地输入命令,提交作业步。每输入一条(或一组)命令,便直接在系统内部对应一个(或若干个)进程。在系统启动时,系统为每个终端设备建立一个进程(称为终端进程),该进程执行命令解释程序,命令解释程序从终端设备读入命令解释执行用户输入的每一条命令。对于每一条终端命令,可以创建一个子进程去具体执行。若当前的终端命令是一条后台命令,则可以和下一条终端命令并行处理。各子进程在运行过程中完全可以根据需要创建子孙进程。终端命令所对应的进程结束后,命令的功能也相应处理完毕。用户本次上机完毕,用户通过一条登出命令即结束上机过程。

分时系统的作业就是用户的一次上机交互过程,可以认为终端进程的创建是一个交互作业的开始,登出命令运行结束代表用户交互作业的终止。

命令解释程序流程扮演着批处理系统中作业控制语言解释程序的角色,只不过命令解释程序是从用户终端接收命令。

3) 交互地提交批作业

在同时支持交互和批处理的操作系统中,人们可以用交互的方式准备好批作业的有关程序、数据及作业控制说明书。
比如,可用交互式系统提供的全屏幕编辑命令编辑好自编的一个天气预报程序,用编译及装配命令将程序变成可执行文件,用调试命令进行程序调试。在调试成功后,用户每天都要做如下工作:准备原始天气数据,运行天气预报执行文件处理原始数据,把结果打印出来等。这时,用交互系统提供的全屏幕编辑命令编辑好将要提交的作业控制说明书文件,如Windows系统的BAT文件和Linux系统的sh文件。然后用一条作业提交命令将作业提交给系统作业队列中。系统有专门的作业调度进程负责从作业队列中选择作业,为被选取的作业创建一个父进程运行命令解释程序,解释执行作业控制说明书文件中的命令。


2019-09-29 17:44:10 weixin_39506322 阅读数 106

目录

1. 死锁的概念以及产生死锁的原因

1.1 死锁的定义

1.2 死锁产生的原因

1) 系统资源的竞争

2) 进程推进顺序非法

3) 死锁产生的必要条件

 

2. 死锁的处理策略

预防死锁

避免死锁

死锁的检测及解除

3. 死锁预防和死锁避免

3.1 死锁预防

1) 破坏互斥条件

2) 破坏不剥夺条件

3) 破坏请求和保持条件

4) 破坏循环等待条件

3.2 死锁避免

3.2.1 系统安全状态

3.2.2  银行家算法

3.2.3  银行家算法举例

4. 死锁的检测和解除

资源分配图

死锁定理

死锁的解除

5. 关于进程和线程的知识点汇总

5.1 进程与程序的区别与联系

5.2 死锁与饥饿

5.3 银行家算法的工作原理

5.4 进程同步、互斥的区别和联系

5.5 作业和进程的关系


1. 死锁的概念以及产生死锁的原因

1.1 死锁的定义

在多道程序系统中,由于多个进程的并发执行,改善了系统资源的利用率并提高了系统 的处理能力。然而,多个进程的并发执行也带来了新的问题——死锁。所谓死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进。

下面我们通过一些实例来说明死锁现象。

先看生活中的一个实例,在一条河上有一座桥,桥面很窄,只能容纳一辆汽车通行。如果有两辆汽车分别从桥的左右两端驶上该桥,则会出现下述的冲突情况。此时,左边的汽车占有了桥面左边的一段,要想过桥还需等待右边的汽车让出桥面右边的一段;右边的汽车占有了桥面右边的一段,要想过桥还需等待左边的汽车让出桥面左边的一段。此时,若左右两边的汽车都只能向前行驶,则两辆汽车都无法过桥。

在计算机系统中也存在类似的情况。例如,某计算机系统中只有一台打印机和一台输入设备,进程P1正占用输入设备,同时又提出使用打印机的请求,但此时打印机正被进程P2 所占用,而P2在未释放打印机之前,又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去,均无法继续执行,此时两个进程陷入死锁状态。

 

1.2 死锁产生的原因

1) 系统资源的竞争

通常系统中拥有的不可剥夺资源,其数量不足以满足多个进程运行的需要,使得进程在运行过程中,会因争夺资源而陷入僵局,如磁带机、打印机等。只有对不可剥夺资源的竞争才可能产生死锁,对可剥夺资源的竞争是不会引起死锁的。

2) 进程推进顺序非法

进程在运行过程中,请求和释放资源的顺序不当,也同样会导致死锁。例如,并发进程 P1、P2分别保持了资源R1、R2,而进程P1申请资源R2,进程P2申请资源R1时,两者都会因为所需资源被占用而阻塞。

信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息,结果也会使得这些进程间无法继续向前推进。例如,进程A等待进程B发的消息,进程B又在等待进程A 发的消息,可以看出进程A和B不是因为竞争同一资源,而是在等待对方的资源导致死锁。

3) 死锁产生的必要条件

产生死锁必须同时满足以下四个条件,只要其中任一条件不成立,死锁就不会发生。

  • 互斥条件:进程要求对所分配的资源(如打印机)进行排他性控制,即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源,则请求进程只能等待。
  • 不剥夺条件:进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能由获得该资源的进程自己来释放(只能是主动释放)。
  • 请求和保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已被其他进程占有,此时请求进程被阻塞,但对自己已获得的资源保持不放。
  • 循环等待条件:存在一种进程资源的循环等待链,链中每一个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待状态的进程集合{Pl, P2, …, pn},其中Pi等待的资源被P(i+1)占有(i=0, 1, …, n-1),Pn等待的资源被P0占有,如图2-15所示。

2. 死锁的处理策略

为使系统不发生死锁,必须设法破坏产生死锁的四个必要条件之一,或者允许死锁产生, 但当死锁发生时能检测出死锁,并有能力实现恢复。

预防死锁

设置某些限制条件,破坏产生死锁的四个必要条件中的一个或几个,以防止发生死锁。

避免死锁

在资源的动态分配过程中,用某种方法防止系统进入不安全状态,从而避免死锁。

死锁的检测及解除

无需釆取任何限制性措施,允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生,然后釆取某种措施解除死锁。

预防死锁和避免死锁都属于事先预防策略,但预防死锁的限制条件比较严格,实现起来较为简单,但往往导致系统的效率低,资源利用率低;避免死锁的限制条件相对宽松,资源分配后需要通过算法来判断是否进入不安全状态,实现起来较为复杂。

死锁的几种处理策略的比较见表2-1。
 

表2-1  死锁处理策略的比较
资源分配策略 各种可能模式 主要优点 主要缺点
死锁预防 保守,宁可资源闲置 一次请求所有资源,资 源剥夺,资源按序分配 适用于做突发式处理的进程,不必进行剥夺 效率低,进程初始化时间延长;剥夺次数过多;不便灵活申请新资源
死锁避免 是”预防“和”检测“ 的折中(在运行时判断是否可能死锁) 寻找可能的安全允许顺序 不必进行剥夺 必须知道将来的资源需求;进程不能被长时间阻塞
死锁检测 宽松,只要允许就分配资源 定期检查死锁是否已经发生 不延长进程初始化时间,允许对死锁进行现场处理 通过剥夺解除死锁,造成损失
 

 

3. 死锁预防和死锁避免

3.1 死锁预防

防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。

1) 破坏互斥条件

如果允许系统资源都能共享使用,则系统不会进入死锁状态。但有些资源根本不能同时访问,如打印机等临界资源只能互斥使用。所以,破坏互斥条件而预防死锁的方法不太可行,而且在有的场合应该保护这种互斥性。

2) 破坏不剥夺条件

当一个已保持了某些不可剥夺资源的进程,请求新的资源而得不到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请。这意味着,一个进程已占有的资源会被暂时释放,或者说是被剥夺了,或从而破坏了不可剥夺条件。

该策略实现起来比较复杂,释放已获得的资源可能造成前一阶段工作的失效,反复地申请和释放资源会增加系统开销,降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源,如CPU的寄存器及内存资源,一般不能用于打印机之类的资源。

3) 破坏请求和保持条件

釆用预先静态分配方法,即进程在运行前一次申请完它所需要的全部资源,在它的资源未满足前,不把它投入运行。一旦投入运行后,这些资源就一直归它所有,也不再提出其他资源请求,这样就可以保证系统不会发生死锁。

这种方式实现简单,但缺点也显而易见,系统资源被严重浪费,其中有些资源可能仅在运行初期或运行快结束时才使用,甚至根本不使用。而且还会导致“饥饿”现象,当由于个别资源长期被其他进程占用时,将致使等待该资源的进程迟迟不能开始运行。

4) 破坏循环等待条件

为了破坏循环等待条件,可釆用顺序资源分配法。首先给系统中的资源编号,规定每个进程,必须按编号递增的顺序请求资源,同类资源一次申请完。也就是说,只要进程提出申请分配资源Ri,则该进程在以后的资源申请中,只能申请编号大于Ri的资源。

这种方法存在的问题是,编号必须相对稳定,这就限制了新类型设备的增加;尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序,但也经常会发生作业使甩资源的顺序与系统规定顺序不同的情况,造成资源的浪费;此外,这种按规定次序申请资源的方法,也必然会给用户的编程带来麻烦。

3.2 死锁避免

避免死锁同样是属于事先预防的策略,但并不是事先釆取某种限制措施破坏死锁的必要条件,而是在资源动态分配过程中,防止系统进入不安全状态,以避免发生死锁。这种方法所施加的限制条件较弱,可以获得较好的系统性能。

3.2.1 系统安全状态

避免死锁的方法中,允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程; 否则,让进程等待。

所谓安全状态,是指系统能按某种进程推进顺序( P1, P2, …, Pn),为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺序地完成。此时称 P1, P2, …, Pn 为安全序列。如果系统无法找到一个安全序列,则称系统处于不安全状态。

假设系统中有三个进程P1、P2和P3,共有12 台磁带机。进程P1总共需要10台磁带机,P2和P3 分别需要4台和9台。假设在T0时刻,进程P1、P2 和P3已分别获得5合、2台和2台,尚有3台未分配,见表3-1。
 

表3-1 资源分配
进程 最大需求 已分配 可用
P1 10 5 3
P2 4 2  
P3 9 2  


则在T0时刻是安全的,因为存在一个安全序列P2、Pl、P3,即只要系统按此进程序列分配资源,则每个进程都能顺利完成。若在T0时刻后,系统分配1台磁带机给P3,则此时系统便进入不安全状态,因为此时已无法再找到一个安全序列。

并非所有的不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状态;反之,只要系统处于安全状态,系统便可以避免进入死锁状态。

3.2.2  银行家算法

银行家算法是最著名的死锁避免算法。它提出的思想是:把操作系统看做是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。

1) 数据结构描述
可利用资源矢量Available:含有m个元素的歎组,其中的每一个元素代表一类可用的资源数目。Available[j]=K,则表示系统中现有Rj类资源K个。

最大需求矩阵Max:为n*m矩阵,定义了系统中n个进程中的每一个进程对m类资源的最大需求。Max[i, j]=K,则表示进程i需要Rj类资源的最大数目为K。

分配矩阵Allocation:为n*m矩阵,定义了系统中每一类资源当前已分配给每一进程的资源数。All0Cati0n[i, j]= K,则表示进程i当前已分得Rj类资源的数目为K。

需求矩阵Need:为n*m矩阵,表示每个进程尚需的各类资源数。Need[i, j]=K,则表示进程i还需要Rj类资源的数目为K。

上述三个矩阵间存在下述关系:
Need[i, j] = Max[i, j] - Allocation[i, j]

2) 银行家算法描述
设Requesti是进程Pi的请求矢量,如果Requesti[j]K,表示进程Pi需要Rj类资源K个。当Pi发出资源请求后,系统按下述步骤进行检查:

①如果Requesti[j] <= Need[i, j],便转向步骤②;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

②如果Requesti[j] <= Available[j],便转向步骤③;否则,表示尚无足够资源,Pi须等待。

③系统试探着把资源分配给进程Pi,并修改下面数据结构中的数:

Available[j] = Available[j] - Requesti[j];
Allocation[i, j] = Allocation[i, j] + Requesti[ j];
Need[i, j] = Need[i, j] - Requesti[j];

④系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

3) 安全性算法
①设置两个矢量。工作矢量Work;它表示系统可提供给进程继续运行所需的各类资源数目,它含有所个元素,在执行安全算法开始时,Work=Available; Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时 Finish[i]=false;当有足够资源分配给进程 Pi 时,再令 Finish[i]=true。

②从进程集合中找到一个能满足下述条件的进程:Finish[i]=false;    Need[i, j]<=Work[j]; 若找到,执行下一步骤,否则,执行步骤4。

③当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:

Work[j]=Work[j]+Allocation[i, j];
Finish[i]=true;
go to step <2>;

④如果所有进程的Finish[i]=tme都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

3.2.3  银行家算法举例

假定系统中有5个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况见表3-2。

1) T0时刻的安全性。
利用安全性算法对T0时刻的资源分配进行分析,由表3-3可知,在T0时刻存在着一个安全序列{P1, P3, P4, P2, P0},故系统是安全的。
 

表3-2 T0时刻的资源分配
进程 / 资源情况 Max
A  B  C
Allocation
A  B  C
Need
A  B  C
Available
A  B  C
P0 7  5  3 0  1  0 7  4  3 3  3  2
(2  3  0)
P1 3  2  2 2  0  0
(3  0  2)
1  2  2
(0  2  0)
 
P2 9  0  2 3  0  2 6  0  0  
P3 2  2  2 2  1  1 0  1  1  
P4 4  3  3 0  0  2 4  3  1  

 

表3-3 T0时刻的安全序列
进程 / 资源情况 Work
A  B  C
Need
A  B  C
Allocation
A  B  C
Work+Allocation
A  B  C
Finish
P1 3  3  2 1  2  2 2  0  0 5  3  2 true
P3 5  3  2 0  1  1 2  1  1 7  4  3 true
P4 7  4  3 4  3  1 0  0  2 7  4  5 true
P2 7  4  5 6  0  0 3  0  2 10  4  7 true
P0 10  4  7 7  4  3 0  1  0 10  5  7 true


2) P1请求资源
P1发出请求矢量Request1(l,, 0, 2),系统按银行家算法进行检查:

  • Request1(1, 0, 2) <= Need1(l, 2, 2)。
  • Request1(1, 0, 2) <= Available1(3, 3, 2)。
  • 系统先假定可为P1分配资源,并修改Available、Allocation1和Need1矢量,由此形成的资源变化情况见表3-4。
  • 再利用安全性算法检查此时系统是否安全。

 

表3-4 P1申请资源时的安全性检测
进程 / 资源情况 Work
A  B  C
Need
A  B  C
Allocation
A  B  C
Work+ Allocation
A  B  C
Finish
P1 2  3  0 0  2  0 3  0  2 5  3  2 true
P3 5  3  2 0  1  1 2  1  1 7  4  3 true
P4 7  4  3 4  3  1 0  0  2 7  4  5 true
P0 7  4  5 7  4  3 0  1  0 7  5  5 true
P2 7  5  5 6  0  0 3  0  2 10  5  7 true


3) P4请求资源
P4发出请求矢量Request4(3, 3, 0),系统按银行家算法进行检查:

  • Request4(3, 3, 0) <= Need4(4, 3, 1)。
  • Request4(3, 3, 0) > Available(2, 3, 0),让 P4 等待。


4) P0请求资源
P0发出请求矢量Request0(0, 2, 0),系统按银行家算法进行检查:

  • Request0(0, 2, 0) <= Need0(7, 4, 3)。
  • Request0(0, 2, 0) <= Available(2, 3, 0)。
  • 系统暂时先假定可为P0分配资源,并修改有关数据,见表3-5。
表3-5 为P0分配资源后的有关资源数据
进程 / 资源情况 Allocation
A  B  C
Need
A  B  C
Available
A  B  C
P0 0  3  0 7  2  3 2  1  0
P1 3  0  2 0  2  0  
P2 3  0  2 6  0  0  
P3 2  1  1 0  1  1  
P4 0  0  2 4  3  1  


5) 进行安全性检测。
可用资源Available(2, 1, 0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源。

 

4. 死锁的检测和解除

前面绍的死锁预防和避免算法,都是在为进程分配资源时施加限制条件或进行检测,若系统为进程分配资源时不釆取任何措施,则应该提供死锁检测和解除的手段。

资源分配图

系统死锁,可利用资源分配图来描述。如图4-1所示,用圆圈代表一个进程,用框代表一类资源。由于一种类型的资源可能有多个,用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边,表示该进程申请一个单位的该类资源;从资源到进程的边叫分配边,表示该类资源已经有一个资源被分配给了该进程。

                                                                                   图4-1  资源分配示例图


在图4-1所示的资源分配图中,进程P1已经分得了两个R1资源,并又请求一个R2 资源;进程P2分得了一个R1和一个R2资源,并又请求一个R1资源。

死锁定理

可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。简化方法如下:

1) 在资源分配图中,找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连,且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件,则这个进程能继续运行直至完成,然后释放它所占有的所有资源)。消去它所有的请求边和分配边,使之成为孤立的结点。在图4-2(a)中,P1是满足这一条件的进程结点,将P1的所有边消去,便得到图4-2(b)所示的情况。

2) 进程Pi所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程。在图2-17中,进程P2就满足这样的条件。根据第1) 条中的方法进行一系列简化后,若能消去图中所有的边,则称该图是可完全简化的,如图4-2(c)所示。

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

死锁的解除

一旦检测出死锁,就应立即釆取相应的措施,以解除死锁。死锁解除的主要方法有:

1) 资源剥夺法。挂起某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源,而处于资源匮乏的状态。

2) 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
 

 

                                                                               图4-2  资源分配图的化简


3) 进程回退法。让一(多)个进程回退到足以回避死锁的地步,进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息,设置还原点。

 

5. 关于进程和线程的知识点汇总

5.1 进程与程序的区别与联系

1) 进程是程序及其数据在计算机上的一次运行活动,是一个动态的概念。进程的运行实体是程序,离开程序的进程没有存在的意义。从静态角度看,进程是由程序、数据和进程控制块(PCB)三部分组成的。而程序是一组有序的指令集合,是一种静态的概念。

2) 进程是程序的一次执行过程,它是动态地创建和消亡的,具有一定的生命周期,是暂时存在的;而程序则是一组代码的集合,它是永久存在的,可长期保存。

3) 一个进程可以执行一个或几个程序,一个程序也可以构成多个进程。进程可创建进程,而程序不可能形成新的程序。

4) 进程与程序的组成不同。进程的组成包括程序、数据和PCB。

5.2 死锁与饥饿

具有等待队列的信号量的实现可能导致这样的情况:两个或多个进程无限地等待一个事件,而该事件只能由这些等待进程之一来产生。这里的事件是V操作的执行(即释放资源)。当出现这样的状态时,这些进程称为死锁(Dead locked)。

为了加以说明,考虑到一个系统由两个进程P0和P1组成,每个进程都访问两个信号量S和Q,这两个信号量的初值均为1。

P0 () {
    While (1){
        P(S) ;
        P(Q);
        // …
        V(S) ;
        V(Q) ;
    }
}
p1() {
    While(1){
        P(Q);
        P(S);
        // …
        V(Q);
        V(S);
    }
}

假设进程P0执行P(S),接着进程P1执行P(Q)。当进程P0执行P(Q)时,它必须等待直到进程P1执行V(Q)。类似地,当进程P1执行P(S),它必须等待直到进程P0执行V(S)。由于这两个V操作都不能执行,那么进程P0和进程P1就死锁了。

说一组进程处于死锁状态是指:组内的每个进程都等待一个事件,而该事件只可能由组内的另一个进程产生。这里所关心的主要是事件是资源的获取和释放。

与死锁相关的另一个问题是无限期阻塞(Indefinite Blocking)或“饥饿” (Starvation),即进程在信号量内无穷等待的情况。

产生饥饿的主要原因是:在一个动态系统中,对于每类系统资源,操作系统需要确定一个分配策略,当多个进程同时申请某类资源时,由分配策略确定资源分配给进程的次序。有时资源分配策略可能是不公平的,即不能保证等待时间上界的存在。在这种情况下,即使系统没有发生死锁,某些进程也可能会长时间等待。当等待时间给进程推进和响应带来明显影响时,称发生了进程“饥饿”,当“饥饿”到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被“饿死”。

例如,当有多个进程需要打印文件时,如果系统分配打印机的策略是最短文件优先,那么长文件的打印任务将由于短文件的源源不断到来而被无限期推迟,导致最终的“饥饿”甚至“饿死”。

“饥饿”并不表示系统一定死锁,但至少有一个进程的执行被无限期推迟。“饥饿”与死锁的主要差别有:

  • 进入“饥饿”状态的进程可以只有一个,而由于循环等待条件而进入死锁状态的进程却必须大于或等于两个。
  • 处于“饥饿”状态的进程可以是一个就绪进程,如静态优先权调度算法时的低优先权进程,而处于死锁状态的进程则必定是阻塞进程。

5.3 银行家算法的工作原理

银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时,它首先检查系统是否有足够的资源满足要求,如果有,则先进行分配,并对分配后的新状态进行安全性检查。如果新状态安全,则正式分配上述资源,否则就拒绝分配上述资源。这样,它保证系统始终处于安全状态,从而避免死锁现象的发生。

5.4 进程同步、互斥的区别和联系

并发进程的执行会产生相互制约的关系:一种是进程之间竞争使用临界资源,只能让它们逐个使用,这种现象称为互斥,是一种竞争关系;另一种是进程之间协同完成任务,在关键点上等待另一个进程发来的消息,以便协同一致,是一种协作关系。

5.5 作业和进程的关系

进程是系统资源的使用者,系统的资源大部分都是以进程为单位分配的。而用户使用计算机是为了实现一串相关的任务,通常把用户要求计算机完成的这一串任务称为作业。

1) 批处理系统中作业与进程的关系(进程组织)

批处理系统中的可以通过磁记录设备或卡片机向系统提交批作业,由系统的SPOOLing 输入进程将作业放入磁盘的输入井中,作为后备作业。作业调度程序(一般也作为独立的进程运行)每当选择一道后备作业运行时,首先为该作业创建一个进程(称为该作业的根进程)。该进程将执行作业控制语言解释程序解释该作业的作业说明书。父进程在运行过程中可以动态地创建一个或多个子进程,执行说明书中的语句。

例如,对一条编译的语句,该进程可以创建一个子进程执行编译程序对用户源程序进行编译。类似地,子进程也可以继续创建子进程去完成指定的功能。因此,一个作业就动态地转换成了一组运行实体——进程族。当父进程遇到作业说明书中的“撤出作业”的语句时,将该作业从运行状态改变为完成状态,将作业及相关结果送入磁盘上的输出井。作业终止进程负责将输出井中的作业利用打印机输出,回收作业所占用的资源,删除作业有关数据结构,删除作业在磁盘输出井中的信息,等等。作业终止进程撤除一道作业后,可向作业调度进程请求进行新的作业调度。至此,一道进入系统运行的作业全部结束。

2) 分时系统中作业与进程的关系

在分时系统中,作业的提交方法、组织形式均与批处理作业有很大差异。分时系统的用户通过命令语言逐条地与系统应答式地输入命令,提交作业步。每输入一条(或一组)命令,便直接在系统内部对应一个(或若干个)进程。在系统启动时,系统为每个终端设备建立一个进程(称为终端进程),该进程执行命令解释程序,命令解释程序从终端设备读入命令解释执行用户输入的每一条命令。对于每一条终端命令,可以创建一个子进程去具体执行。若当前的终端命令是一条后台命令,则可以和下一条终端命令并行处理。各子进程在运行过程中完全可以根据需要创建子孙进程。终端命令所对应的进程结束后,命令的功能也相应处理完毕。用户本次上机完毕,用户通过一条登出命令即结束上机过程。

分时系统的作业就是用户的一次上机交互过程,可以认为终端进程的创建是一个交互作业的开始,登出命令运行结束代表用户交互作业的终止。

命令解释程序流程扮演着批处理系统中作业控制语言解释程序的角色,只不过命令解释程序是从用户终端接收命令。

3) 交互地提交批作业

在同时支持交互和批处理的操作系统中,人们可以用交互的方式准备好批作业的有关程序、数据及作业控制说明书。

比如,可用交互式系统提供的全屏幕编辑命令编辑好自编的一个天气预报程序,用编译及装配命令将程序变成可执行文件,用调试命令进行程序调试。在调试成功后,用户每天都要做如下工作:准备原始天气数据,运行天气预报执行文件处理原始数据,把结果打印出来等。这时,用交互系统提供的全屏幕编辑命令编辑好将要提交的作业控制说明书文件,如Windows系统的BAT文件和Linux系统的sh文件。然后用一条作业提交命令将作业提交给系统作业队列中。系统有专门的作业调度进程负责从作业队列中选择作业,为被选取的作业创建一个父进程运行命令解释程序,解释执行作业控制说明书文件中的命令。

2016-10-30 12:11:24 ZJU_fish1996 阅读数 9643


       不知道做的对不对,仅供参考。


更新日志:


2016.11.12 更新版本:

解决了程序不能自动退出的bug(卡在死锁检测线程的while)
去掉main中最后一行:pthread_join(check,NULL) 主线程不等待死锁线程结束,程序可以自动退出。


1. 有两条道路双向两个车道,即每条路每个方向只有一个车道,两条道路十字交叉。假设车辆只能向前直行,而不允许转弯和后退。如果有4辆车几乎同时到达这个十字路口,如图(a)所示;相互交叉地停下来,如图(b),此时4辆车都将不能继续向前,这是一个典型的死锁问题。从操作系统原理的资源分配观点,如果4辆车都想驶过十字路口,那么对资源的要求如下:

        l 向北行驶的车1需要象限ab

        l 向西行驶的车2需要象限bc

        l 向南行驶的车3需要象限cd

        l 向东行驶的车4需要象限da

 

 

    我们要实现十字路口交通的车辆同步问题,防止汽车在经过十字路口时产生死锁和饥饿。在我们的系统中,东西南北各个方向不断地有车辆经过十字路口(注意:不只有4辆),同一个方向的车辆依次排队通过十字路口。按照交通规则是右边车辆优先通行,如图(a)中,若只有car1car2car3,那么车辆通过十字路口的顺序是car3->car2->car1。车辆通行总的规则:

        1) 来自同一个方向多个车辆到达十字路口时,车辆靠右行驶,依次顺序通过;

        2) 有多个方向的车辆同时到达十字路口时,按照右边车辆优先通行规则,除非该车在十字路口等待时收到一个立即通行的信号;

        3) 避免产生死锁;

        4) 避免产生饥饿;

        5) 任何一个线程(车辆)不得采用单点调度策略;

        6) 由于使用AND型信号量机制会使线程(车辆)并发度降低且引起不公平(部分线程饥饿),本题不得使用AND型信号量机制,即在上图中车辆不能要求同时满足两个象限才能顺利通过,如南方车辆不能同时判断ab是否有空。

 

编写程序实现避免产生死锁和饥饿的车辆通过十字路口方案并给出详细的设计方案,程序中要有详细的注释

        1) 每一辆车的行为设计为一个单独的线程。由于有4个不同方向的车辆,需要4种不同类型的线程。

        2) 使用pthread互斥锁和条件变量解决车辆的同步与互斥。

        3) 对4个不同方向的车辆,要设置车辆队列条件变量如: queueNorth、queueEastqueueSouthqueueWest。比如说,当一辆车从北方来的时候已经在过十字路口,从北方驶来的车就要等在queueNorth队列中每一个方向都需要一个计数器来跟踪等待排队的车辆数量。

        4) 按照右边车辆优先通行规则,当一辆车在等待通过路口而它右边不断有车辆到达时,这辆车及这个方向车辆队列会导致饥饿。为了防止饥饿,我们刚刚通过路口的A车辆发一个信号给它左边等待B车辆,接下去让B车辆通行需要设置下次通行车辆的条件变量firstNorth firstEast firstSouthfirstWest

        5) 每一车辆到达十字路口时,要检测是否有死锁发生,当发生死锁时,死锁检测线程必须发出一种信号,例如:从北方来的车辆先行。

        6) 假设我们设计的可执行程序文件名为p1-1,可以用'e'、'w'、's'、'n'来标识东西南北4个方向驶来的车辆,程序p1-1运行时有如下显示(你的程序不一定是这样相同的输出):

$ ./ p1-1 nsewwewn

car 4 from West arrives at crossing

car 2 from South arrives at crossing

car 1 from North arrives at crossing

car 3 from East arrives at crossing

DEADLOCK: car jam detected, signalling North to go

car 1 from North leaving crossing

car 3 from East leaving crossing

car 2 from South leaving crossing

car 4 from West leaving crossing

car 6 from East arrives at crossing

car 5 from West arrives at crossing

car 8 from North arrives at crossing

car 5 from West leaving crossing

car 6 from East leaving crossing

car 8 from North leaving crossing

car 7 from West arrives at crossing

car 7 from West leaving crossing


     

      


         

对于题目中要求的车辆优先权的理解:

      

 

        两车都希望占据路口a,由于西边的车(W1车)在北边车(N车)的右边,它具有优先权,将先行。

        W1车离开后,虽然对于N车来说,右边还有车,但是离开的车有必要告诉N车让其优先通行。

  实际上是这样处理的:设计了一个布尔量,每个方向各有一个,当车辆处在就绪状态(如左图的W1车),或者进入第一个路口时,标记布尔量为真,离开第一个路口时,标记布尔量为假。当车辆想要进入第二个路口时,需要检查它右边车的布尔量。如果为真,那么该车停等。

       该布尔量在小车进入就绪队列时就设为真,如果它当时还不为真,就认为这辆车还没有进入就绪状态,也就不是同时到达路口,所以不会出现不同步现象。


        N车过路口d(发现右边有车,等待)

        W1车过路口a

        W1车过路口b(唤醒N车)

        N车过路口a(接到信号,过第二个路口,发送一个信号唤醒W2车)

        W2车过路口a(接到信号,过路口a


新的车谁来唤醒:

 

        新的车有两种唤醒方式:

       1.如果当前方向的车离开后,左边没有车等待,那么它自己唤醒当前方向的一辆车。

       2.如果当前方向的车离开后,左边有车等待,那么它唤醒左边的车,并由左边的车来唤醒其方向的一辆车。

       由于左边要么有车等待,要么没有车等待,所以总会有一个结果被执行,因此我们保证了一定会有新的车被唤醒。


#include <pthread.h>  
#include <stdio.h>  
#include <unistd.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100

//mutex of the 4 cross
pthread_mutex_t mutex_a;
pthread_mutex_t mutex_b;
pthread_mutex_t mutex_c;
pthread_mutex_t mutex_d;

//mutex of deadlock thread
pthread_mutex_t mutex_e;

//mutex of car waiting(in ready queue)
pthread_mutex_t wait_east;
pthread_mutex_t wait_west;
pthread_mutex_t wait_north;
pthread_mutex_t wait_south;

//mutex of car waiting(in the first cross)
pthread_mutex_t block_east;
pthread_mutex_t block_west;
pthread_mutex_t block_north;
pthread_mutex_t block_south;

//cond of each direction(in the first cross)
pthread_cond_t cond_w;
pthread_cond_t cond_e;
pthread_cond_t cond_n;
pthread_cond_t cond_s;

//cond of each direction(in the ready queue)
pthread_cond_t firstEast;
pthread_cond_t firstWest;
pthread_cond_t firstSouth;
pthread_cond_t firstNorth;

//cond when deadlock happen(to wake up the deadlock thread)
pthread_cond_t cond_deadlock;
//cond when deadlock happen(to wake up the car on the right)
pthread_cond_t cond_lock;

typedef enum { west, north, south, east }dir_t;
dir_t dir;//indicate the direction of the new car that comes to the cross
int size = 0;//count the number of car
int empty;//record the number of empty cross

//indicate the current id of car in each direction
int current_north;
int current_south;
int current_east;
int current_west;

//save all the thread
pthread_t car[MAX];

//a data structure:queue, that descirbes the car in each direction
struct queue
{
	pthread_t thread[MAX];
	int num[MAX];//the id of the car
	int front;//front pointer
	int rear;//rear pointer
	int count;//the number of car in the queue
	queue() {
		front = rear = count = 0;
	}
	void push(int n) {//push a car at the back with id n
		count++;
		rear = (rear + 1) % MAX;
		num[rear] = n;
	}
	int pop() {//pop a car in the front,return the car id
		count--;
		front = (front + 1) % MAX;
		return num[front];
	}
};

//the queue of car
queue car_south;
queue car_east;
queue car_north;
queue car_west;

//if each direction has a car leaving the ready queue /or coming to the first cross
bool is_west;
bool is_south;
bool is_east;
bool is_north;
//if deadlock happens
bool is_deadlock = false;

//wake up all car in the front of the ready queue
void wakeupall()
{
	is_deadlock = false;
	if (car_south.count>0) {
		current_south = car_south.pop();
		//I think this variable has better be designed as a member variable of the class queue
		//but I am too lazy.
		pthread_cond_signal(&firstSouth);
	}
	if (car_north.count>0) {
		current_north = car_north.pop();
		pthread_cond_signal(&firstNorth);
	}
	if (car_west.count>0) {
		current_west = car_west.pop();
		pthread_cond_signal(&firstWest);
	}
	if (car_east.count>0) {
		current_east = car_east.pop();
		pthread_cond_signal(&firstEast);
	}
}
void *car_from_south(void *arg) {
	bool deadlock_flag = false;
	//add a wait lock
	pthread_mutex_lock(&wait_south);
	pthread_cond_wait(&firstSouth, &wait_south);
	pthread_mutex_unlock(&wait_south);

	//has come to the cross
	is_south = true;//set is_come to be true
					//add a lock to the cross
	pthread_mutex_lock(&mutex_a);
	printf("car %d from South arrives at crossing\n", current_south);
	//the resource minus 1
	empty--;
	//indicate current direction
	dir = south;

	bool flag = false;
	//if the resource is used up
	if (empty == 0) {
		//deadlock happened, send a signal to deadlock thread
		pthread_cond_signal(&cond_deadlock);
		//wait until the deadlock is solved
		pthread_cond_wait(&cond_lock, &mutex_a);

		usleep(2000);
		pthread_mutex_lock(&mutex_b);
		pthread_mutex_unlock(&mutex_a);
		printf("car %d from South leaves at crossing\n", current_south);
		is_south = false;
		//resource add 1.
		empty++;
		usleep(2000);
		pthread_mutex_unlock(&mutex_b);
		wakeupall();
		return NULL;
	}

	//if it find a car on its right
	else if (is_east) {
		//  printf("a car on south's right\n");
		flag = true;
		//it will wait for the car to go first
		pthread_cond_wait(&cond_s, &block_south);
		//the car is gone, remember to call the new car
		//and it is wake up, and find that deadlock happend
		//it has to wake up the left car
		if (is_deadlock) {
			usleep(2000);
			pthread_mutex_lock(&mutex_b);
			pthread_mutex_unlock(&mutex_a);
			printf("car %d from South leaves at crossing\n", current_south);
			if (dir == west)pthread_cond_signal(&cond_lock);
			else pthread_cond_signal(&cond_w);
			is_south = false;
			//resource add 1.
			empty++;
			usleep(2000);
			pthread_mutex_unlock(&mutex_b);
			return NULL;
		}
	}
	usleep(2000);

	//come to the second cross
	pthread_mutex_lock(&mutex_b);

	//if flag, remember to call
	if (car_east.count>0 && flag) {
		current_east = car_east.pop();
		pthread_cond_signal(&firstEast);
	}

	//release the lock
	pthread_mutex_unlock(&mutex_a);
	is_south = false;
	//resource add 1.
	empty++;
	printf("car %d from South leaves at crossing\n", current_south);

	//if a car is waiting on the left, let it go
	//and the waiting car in the queue is waked up by it
	if (is_west)pthread_cond_signal(&cond_w);
	//or it's waked up by itself
	else if (!is_south && car_south.count>0) {
		current_south = car_south.pop();
		pthread_cond_signal(&firstSouth);
	}
	usleep(2000);

	//unlock
	pthread_mutex_unlock(&mutex_b);
}
void *car_from_east(void *arg) {
	//add a wait lock
	pthread_mutex_lock(&wait_east);
	pthread_cond_wait(&firstEast, &wait_east);
	pthread_mutex_unlock(&wait_east);
	//has come to the cross
	is_east = true;//setis_come to be true
				   //add a lock to cross
	pthread_mutex_lock(&mutex_b);
	printf("car %d from East arrives at crossing\n", current_east);
	empty--;
	dir = east;
	bool flag = false;
	if (empty == 0) {
		pthread_cond_signal(&cond_deadlock);
		pthread_cond_wait(&cond_lock, &mutex_b);

		usleep(2000);
		pthread_mutex_lock(&mutex_c);
		pthread_mutex_unlock(&mutex_b);
		printf("car %d from East leaves at crossing\n", current_east);
		is_east = false;
		//resource add 1.
		empty++;
		usleep(2000);
		pthread_mutex_unlock(&mutex_c);
		wakeupall();
		return NULL;
	}
	// if it find a car on its right
	else if (is_north) {
		flag = true;
		//it will wait for the car to go first
		pthread_cond_wait(&cond_e, &block_east);
		//it will wait for the car to go first

		//the car is gone, remember to call the new car
		//and it is wake up, and find that deadlock happend
		//it has to wake up the left car
		if (is_deadlock) {
			usleep(2000);
			pthread_mutex_lock(&mutex_c);
			pthread_mutex_unlock(&mutex_b);
			printf("car %d from East leaves at crossing\n", current_east);
			//if it find a car on its left is the deadlock car,wake up it
			if (dir == south)pthread_cond_signal(&cond_lock);
			//otherwise wake up the one on the left
			else pthread_cond_signal(&cond_s);
			is_east = false;
			//resource add 1.
			empty++;
			usleep(2000);
			pthread_mutex_unlock(&mutex_c);
			return NULL;
		}
	}

	usleep(2000);
	//come to the second cross
	pthread_mutex_lock(&mutex_c);

	//if flag, remember to call
	if (!is_north && car_north.count>0 && flag) {
		current_north = car_north.pop();
		pthread_cond_signal(&firstNorth);
	}

	//release the lock
	empty++;
	pthread_mutex_unlock(&mutex_b);
	is_south = false;

	printf("car %d from East leaves at crossing\n", current_east);

	if (is_east)pthread_cond_signal(&cond_s);
	else if (!is_east && car_east.count>0) {
		current_east = car_east.pop();
		pthread_cond_signal(&firstEast);
	}

	usleep(2000);

	pthread_mutex_unlock(&mutex_c);
}
void *car_from_north(void *arg) {
	//  printf("create north\n");
	//add a wait lock
	pthread_mutex_lock(&wait_north);
	pthread_cond_wait(&firstNorth, &wait_north);
	pthread_mutex_unlock(&wait_north);
	is_north = true;
	pthread_mutex_lock(&mutex_c);
	printf("car %d from North arrives at crossing\n", current_north);
	empty--;
	dir = north;

	bool flag = false;
	if (empty == 0) {
		//deadlock happened, send a signal to deadlock thread
		pthread_cond_signal(&cond_deadlock);
		//wait until the deadlock is solved

		pthread_cond_wait(&cond_lock, &mutex_c);

		pthread_cond_signal(&cond_e);
		usleep(2000);
		pthread_mutex_lock(&mutex_d);
		pthread_mutex_unlock(&mutex_c);
		printf("car %d from West leaves at crossing\n", current_north);
		is_north = false;
		//resource add 1.
		empty++;
		usleep(2000);
		pthread_mutex_unlock(&mutex_d);

		wakeupall();
		return NULL;
	}
	//if it find a car on its right
	else if (is_west) {
		// printf("a car on north's right\n");
		flag = true;
		//it will wait for the car to go first
		pthread_cond_wait(&cond_n, &block_north);
		//the car is gone, remember to call the new car
		//and it is wake up, and find that deadlock happend
		//it has to wake up the left car
		if (is_deadlock) {
			usleep(2000);
			pthread_mutex_lock(&mutex_d);
			pthread_mutex_unlock(&mutex_c);
			printf("car %d from North leaves at crossing\n", current_north);
			if (dir == east)pthread_cond_signal(&cond_lock);
			else pthread_cond_signal(&cond_e);
			is_north = false;
			//resource add 1.
			empty++;
			usleep(2000);
			pthread_mutex_unlock(&mutex_d);
			return NULL;
		}
	}
	usleep(2000);

	pthread_mutex_lock(&mutex_d);
	//if flag, remember to call the right car
	if (car_west.count>0 && flag) {
		current_west = car_west.pop();
		pthread_cond_signal(&firstWest);
	}

	empty++;
	pthread_mutex_unlock(&mutex_c);
	is_north = false;
	printf("car %d from North leaves at crossing\n", current_north);

	if (is_east)pthread_cond_signal(&cond_e);
	//or it's waked up by itself
	else if (!is_north && car_north.count>0) {
		current_north = car_north.pop();
		pthread_cond_signal(&firstNorth);
	}

	usleep(2000);

	pthread_mutex_unlock(&mutex_d);


}

void *car_from_west(void *arg) {
	//add a wait lock
	pthread_mutex_lock(&wait_west);
	pthread_cond_wait(&firstWest, &wait_west);
	pthread_mutex_unlock(&wait_west);


	//has come to the cross
	is_west = true;//set is_come to be true
	pthread_mutex_lock(&mutex_d);
	printf("car %d from West arrives at crossing\n", current_west);

	//the resource minus 1
	empty--;
	//indicate current direction
	dir = west;

	bool flag = false;
	//if the resource is used up
	if (empty == 0) {
		//deadlock happened, send a signal to deadlock thread
		pthread_cond_signal(&cond_deadlock);
		//wait until the deadlock is solved

		pthread_cond_wait(&cond_lock, &mutex_d);
		usleep(2000);
		pthread_mutex_lock(&mutex_a);
		pthread_mutex_unlock(&mutex_d);
		printf("car %d from West leaves at crossing\n", current_west);
		is_south = false;
		//resource add 1.
		empty++;
		usleep(2000);
		pthread_mutex_unlock(&mutex_a);
		wakeupall();
		return NULL;
	}
	//if it find a car on its right
	else if (is_south) {
		flag = true;
		//it will wait for the car to go first

		pthread_cond_wait(&cond_w, &block_west);
		//the car is gone, remember to call the new car
		//and it is wake up, and find that deadlock happend
		//it has to wake up the left car
		if (is_deadlock) {
			usleep(2000);
			pthread_mutex_lock(&mutex_a);
			pthread_mutex_unlock(&mutex_d);
			printf("car %d from West leaves at crossing\n", current_west);
			if (dir == north)pthread_cond_signal(&cond_lock);
			else pthread_cond_signal(&cond_n);
			is_west = false;
			//resource add 1.
			empty++;
			usleep(2000);
			pthread_mutex_unlock(&mutex_a);
			return NULL;
		}
	}
	usleep(2000);
	//come to the second cross
	pthread_mutex_lock(&mutex_a);

	//if flag, remember to call
	if (!is_north && car_north.count>0 && flag) {
		current_north = car_north.pop();
		pthread_cond_signal(&firstNorth);
	}

	empty++;
	pthread_mutex_unlock(&mutex_d);
	is_west = false;

	printf("car %d from West leaves at crossing\n", current_west);
	if (is_north)pthread_cond_signal(&cond_n);
	else if (!is_west && car_west.count>0) {
		current_west = car_west.pop();
		pthread_cond_signal(&firstWest);
	}

	usleep(2000);
	pthread_mutex_unlock(&mutex_a);
}

void *check_dead_lock(void *arg) {
	//wait....
	usleep(4000);
	//at first wake up all the car;
	wakeupall();

	while (1) {
		pthread_mutex_lock(&mutex_e);
		//wait for deadlock
		pthread_cond_wait(&cond_deadlock, &mutex_e);
		//deadlock happen,set is_deadlock true
		is_deadlock = true;
		printf("DEADLOCK: car jam detected, signalling");
		//ask a car to go first,according to the latest car direction.
		switch (dir) {
		case north: {printf(" East "); pthread_cond_signal(&cond_e); break; }
		case east: {printf(" South "); pthread_cond_signal(&cond_s); break; }
		case west: {printf(" North "); pthread_cond_signal(&cond_n); break; }
		case south: {printf(" West "); pthread_cond_signal(&cond_w); break; }
		}
		printf("to go\n");

		pthread_mutex_unlock(&mutex_e);
	}
}

int main(int argc, char** argv) {

	int num[100];

	pthread_t check;//a thread for deadlock checking

	//initialize(it seems that it doesn't matter whether I intialize)
	pthread_cond_init(&cond_lock, NULL);
	pthread_cond_init(&cond_deadlock, NULL);
	pthread_cond_init(&cond_w, NULL);
	pthread_cond_init(&cond_s, NULL);
	pthread_cond_init(&cond_e, NULL);
	pthread_cond_init(&cond_n, NULL);
	pthread_cond_init(&firstEast, NULL);
	pthread_cond_init(&firstWest, NULL);
	pthread_cond_init(&firstSouth, NULL);
	pthread_cond_init(&firstNorth, NULL);

	pthread_mutex_init(&mutex_a, NULL);
	pthread_mutex_init(&mutex_b, NULL);
	pthread_mutex_init(&mutex_c, NULL);
	pthread_mutex_init(&mutex_d, NULL);
	pthread_mutex_init(&mutex_e, NULL);
	pthread_mutex_init(&wait_north, NULL);
	pthread_mutex_init(&wait_south, NULL);
	pthread_mutex_init(&wait_east, NULL);
	pthread_mutex_init(&wait_west, NULL);
	pthread_mutex_init(&block_north, NULL);
	pthread_mutex_init(&block_east, NULL);
	pthread_mutex_init(&block_west, NULL);
	pthread_mutex_init(&block_south, NULL);
	char s[100];
	scanf("%s", s);
	int len = strlen(s);
	empty = 4;
	//create the thread
	for (int i = 0; i<len; i++)num[i] = i + 1;
	for (int i = 0; i<len; i++) {
		switch (s[i]) {
		case 'w': {
			is_west = true;
			car_west.push(num[i]);
			car[size++] = car_west.thread[car_west.front];
			pthread_create(&car_west.thread[car_west.front],
				NULL, car_from_west, NULL);
			break;
		}
		case 'e': {
			is_east = true;
			car_east.push(num[i]);
			car[size++] = car_east.thread[car_east.front];
			pthread_create(&car_east.thread[car_east.rear],
				NULL, car_from_east, NULL);
			break;
		}
		case 's': {
			is_south = true;
			car_south.push(num[i]);
			car[size++] = car_south.thread[car_south.rear];
			pthread_create(&car_south.thread[car_south.rear],
				NULL, car_from_south, NULL);
			break;
		}
		case 'n': {
			is_north = true;
			car_north.push(num[i]);
			car[size++] = car_north.thread[car_north.rear];
			pthread_create(&car_north.thread[car_north.rear],
				NULL, car_from_north, NULL);
			break;
		}
		}
	}

	pthread_create(&check, NULL, check_dead_lock, NULL);
	//join the thread
	for (int i = 0; i<size; i++) {
		pthread_join(car[i], NULL);
	}
}