资源问题

在系统中有许多不同类型的资源，其中可以引起死锁的主要是，需要采用互补访问方式的、不可以被抢占的资源，即临界资源。

• 可重用性资源和消耗性资源
  • 可重用性资源：对资源的请求和释放通常都是利用系统调用来实现的。
    可重用性资源是一种可供用户重复使用多次的资源，它具有如下性质：
    • 每一个可重用性资源中的单元只能分配给一个进程使用，不允许多个进程共享。
    • 进程在使用可重用性资源时，须按照这样的顺序：
      • 请求资源：如果请求资源失败，请求进程将会被阻塞或循环等待。
      • 使用资源：进程对资源进行操作。
      • 释放资源：当进程使用完后自己释放资源。
    • 系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它。
  • 可消耗性资源
    可消耗性资源通常是有由生产者进程创建，由消费者进程消耗。
    最典型的可消耗性资源就是用于进程间通信的消息等。
    可消耗性资源又称为临时性资源，它是在进程运行期间，由进程动态地创建和消耗的，它具有如下性质：
    • 每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的。
    • 进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓存区中，以增加该资源类的单元数目。
    • 进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中。
• 可抢占性资源和不可抢占性资源
  • 可抢占性资源：进程在获得这类资源后，该资源可以再被其他进程或系统抢占。
  • 不可抢占性资源：一旦系统把某类资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。

死锁的类别

• 竞争不可抢占性资源引起死锁
  通常系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。
• 竞争可消耗资源引起死锁
  n个进程构成循环通信，每一个进程先能够接收到从上个进程发来的消息，才将消息发送给下一个进程，则这n个进程就会永远阻塞在它们接收消息的操作上，等待一条永远不会发出的消息，于是发生了死锁。
• 进程推进顺序不当引起死锁
  进程在运行过程中，对资源进行申请和释放的顺序是否合法，也是在系统中是否会产生死锁的一个重要因素。

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

• 死锁：如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的（Deadlock）。
• 产生死锁的必要条件
  产生死锁必须同时具备下面四个必要条件，只要其中任一个条件不成立，死锁就不会发生。
  • 互斥条件：进程对所分配的资源进行排他性使用，即在一段时间内，某资源只能被一个进程占用。如果此时还有其他进程请求该资源，则请求进程只能等待，直至占有该资源的进程用毕释放。
  • 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
  • 不可抢占条件：进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放。
  • 循环等待条件：在发送死锁时，必然存在一个进程一资源的循环链，即进程集合中的各进程彼此等待其他进程占有的资源。
• 处理死锁的方式
  • 预防死锁
  • 避免死锁
  • 检测死锁
  • 解除死锁

预防死锁

预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个，以避免发生死锁，由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此主要是破坏产生死锁的后三个条件。

• 破坏“请求和保持”条件
  为了破坏“请求和保持”条件，系统必须保证做到：当一个进程在请求资源时，它不能持有不可抢占资源。该保证可通过如下两个不同的协议实现：
  • 第一种协议
    该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。此时若系统有足够的资源分配给某进程，便可把其需要的所有资源分配给它。这样，该进程在整个运行期间，便不会再提出资源要求，从而破坏了“请求”条件。系统在分配资源时，只要有一种资源不能满足进程的要求，即使其它所需的各资源都空闲也不分配给该进程，而让该进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件，从而可以预防死锁的发生。
    第一种协议的优点是简单、易行且安全，但缺点也极其明显：
    • 资源被严重浪费，严重地恶化了资源的利用率。进程在开始运行时就一次性地占有了整个运行过程所需的全部资源，其中有些资源可能仅在运行初期或运行快结束时才能使用，甚至根本不使用。
    • 使进程经常会发生饥饿现象。因为仅当进程在获得了其所需的全部后才能开始运行，这样就可能由于个别资源长期被其他进程占有，而致使等待该进程迟迟不能开始运行，而个别资源有可能仅在进程运行到最后才需要。
  • 第二种协议
    该协议是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。
• 破坏“不可抢占”条件
  为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已占有的资源会被暂时地释放，或者说是被抢占了，从而破坏了“不可抢占”条件。
  该方法实现起来比较复杂，且需付出很大的代价。这种策略还可能因为反复地申请和释放资源致使进程的执行被无限地推迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。
• 破坏“循环等待”条件
  一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号。在对系统所有资源类型进行线性排序后，便可采用这样的预防协议：规定每个进程必须按序号递增的顺序请求资源。
  在采用这种策略时，应如何来规定每种资源的序号是十分重要的。通常应根据大多数进程需要资源的先后顺序来确定。
  这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量都有较明显的改善。但存在下述问题：
  • 首先，为系统中各类资源所规定的序号必须相对稳定，这就限制了新类型设备的增加；
  • 其次，尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况：作用使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。
  • 最后，为方便用户，系统对用户在编程时所施加的限制条件应尽量少，然而这种按规定次序申请资源的方法必然会限制用户简单、自主地编程。

避免死锁

避免死锁同样是属于事先预防的策略，但并不是事先采取某种限制措施，破坏产生死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。
在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。
安全状态：是指系统能按某种进程推进顺序为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称这个序列为安全状态。
避免死锁的基本思想：就是确保系统始终处于安全状态。一个系统开始是处于安全状态的。当有进程请求一个可用资源时，系统需对该进程的请求进行计算，若将资源分配给进程后系统仍处于安全状态，才将该资源分配给进程。
银行家算法：每一个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总数。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。

死锁的检测

• 死锁的检测
  • 资源分配图
  • 死锁定理
    系统状态为死锁的充分条件是：当且仅当系统状态的资源分配图是不可完全简化的。
  • 死锁检测中的数据结构

死锁的解除

常采用解除死锁的两种方法：

• 抢占资源。
• 终止（或撤销）进程。

终止进程的方法：

• 终止所有死锁进程
• 逐个终止进程