3.5　产生死锁的原因和必要条件

3.5.1产生死锁的原因

  (1)竞争资源。

   当系统中供多个进程共享的资源数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。

(2) 进程间推进顺序非法。

   进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。

1．竞争资源引起进程死锁

  1) 资源分类 

2) 竞争非剥夺性资源

　　在系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷入僵局。例如，系统中只有一台打印机R1和一台磁带机R2，可供进程P1和P2共享。两个进程都在等待对方释放出自己所需的资源。但它们又都因不能继续获得自己所需的资源而不能继续推进，从而也不能释放出自己已占有的资源，以致进入死锁状态。

 

如：P1已占用打印机R1，P2已占用了磁带机R2。P2继续要求打印机R1，P2将阻塞；P1要求磁带机R2，P1也阻塞。于是，在P1与P2之间便形成了僵局，即闭合环路。

3) 竞争临时性资源

S1、S2和S3是临时性资源。

P1产生消息S1，要求接收消息S3；

P2产生消息S2，要接收消息S1；

P3产生消息S3，要求接收消息S2；

 

若按下述的运行顺序：

P1： …Request(S3)；

    Release(S1)； …

P2： …Request(S1)；

    Release(S2)； …

P3： …Request(S2)；

     Release(S3)； …

则发生死锁。

2．进程推进顺序不当引起死锁

　由于进程在运行中具有异步性特征，因此P1和P2两个进程按多种顺序向前推进。

1)     进程推进顺序合法

 

 

2) 进程推进顺序非法

  若并发进程P1和P2按曲线④所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1，P2保持了资源R2，系统处于不安全状态。

  此时两进程再向前推进，便可能发生死锁。

  在D内若向右推进:运行到P1:Request(R2)将阻塞；  

  在D内若向上推进:运行到P2:Request(R1)将阻塞， 

  于是发生了进程死锁。

3.5.2产生死锁的必要条件

  死锁的发生必须具备下列四个必要条件。

  (1)互斥条件：指进程对所分配到的资源进行排它性使用。

    (2)请求和保持条件：进程保持至少一个资源，同时又提出了新的资源请求。

  (3)不剥夺条件：进程已获得的资源在未使用完之前不能被剥夺。

  (4)环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链。

 

3.5.3处理死锁的基本方法

  (1) 预防死锁。——事先预防

  通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。 

(2) 避免死锁。——事先预防。

  不须事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。 

  目前较完善的系统中常用此方法避免发生死锁。

(3) 检测死锁。——事后补救。

  不须事先采取任何限制性措施，也不检查系统是否进入不安全区，而是允许系统运行过程中发生死锁。 

  再通过系统所设置的检测机构，及时地检测出死锁，并精确地确定与死锁有关的进程和资源；然后，采取适当措施清除死锁。

(4) 解除死锁。——与检测死锁相配套。

   当检测到系统中已发生死锁时，须靠外力将进程从死锁状态中解脱出来。

   常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。

   死锁的检测和解除措施可使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

3.6　预防死锁的方法

3.6.1预防死锁

  1．摒弃“请求和保持”条件——静态分配资源。

   进程在开始运行之前必须一次性地申请其在整个运行过程所需的全部资源，从而摒弃了请求条件。

   在进程的等待期间并未占有任何资源，从而也摒弃了保持条件。

优点：简单、易于实现且很安全。

  缺点：1)资源严重浪费，资源中有些很少使用甚至运行结束时才使用严重降低系统资源的利用率；

2)使进程延迟运行:可能因有些资源已长期被其它进程占用而致使等待该资源的进程迟迟不能运行。

2．摒弃“不剥夺”条件——只适用于CPU和内存

   实现：当申请新资源不能满足时要释放所有已占有的可剥夺性资源，待资源充足后再申请新资源及释放的资源。

    此方法实现起来比较复杂且要付出很大的代价：资源被迫释放可能会造成前段工作的失效，会使进程前后两次运行的信息不连续，如打印机。

  为了保持运行信息的连续性，对于临资而言此法不合适（CPU、内存除外)。

    这种策略可能因为反复地申请和释放资源，致使进程的执行被无限地推迟，增加了系统开销，降低了系统吞吐量。

3．摒弃“环路等待”条件

  实现：系统将所有资源按类型进行线性排队，并赋予不同的序号。在所形成的资源分配图中，不可能再出现环路，因而摒弃了“环路等待”条件。

该方法存在问题：

1)系统各类资源序号必须相对稳定，因而限制新类型设备的增加。

2)可能造成某些资源长时间闲置。

3)按规定次序申请资源增加了用户编程时的限制条件，必然会限制用户简单、自主地编程。