死锁问题

  • 如果集合中的每个进程正在等待只有集合中的另一个进程可能导致的事件，则会导致一组进程死锁。
  • Kansas立法机构通过的一个法律：当两列列车在十字路口逼近时，它们要完全停下来，且在一列列车开走之前，另一列列车不能启动。
  • 只有一个方向的交通：桥的每个部分都可以被视为一个资源。如果发生死锁，则可以解决一辆车是否备份（抢占资源并回滚），可能需要“备份几辆汽车。 饥饿是可能的。

#####系统模型

  • 一个系统由有限数量的资源组成，分配给多个竞争过程。
  • 资源被分成几种类型：资源类型R1，R2，…，Rm，例如CPU周期，内存空间和 I/O 设备。
  • 每个资源类型Ri都有Wi实例操作来使用资源
  1. 申请：如果不能立即授予请求，则请求进程必须等待直到它获得该资源为止。
  2. 使用：进程正在使用该资源。
  3. 释放：进程释放资源。

死锁特征

  • 如果以下4个条件同时满足，则会出现死锁：
  1. 互斥：至少有一个资源必须处于非共享模式，即一次只有一个进程可以使用该资源。
  2. 占有并等待：一个进程必须占有至少一个资源，并等待另一个资源，而该资源为其它资源所占有。
  3. 非抢占：资源不能抢占，即资源只能在进程完成任务后自动释放。
  4. 循环等待：有一组等待进程{P0，P1，… ，Pn}，P0等待的资源由P1占有，P1等待的资源由P2占有，… ，Pn-1等待的资源由Pn占有，并且Pn等待的资源由P0占有。

所有4个条件必须同时满足才会出现死锁。循环等待条件意味着占有并等待条件，这样的4个条件并不完全独立。

资源分配图

  • 死锁问题可用称为系统资源分配图的有向图进行更精确地描述。
  • 该图由一组顶点集合V和一组边集合E组成。
  • V被分成两种类型：
  • P = {P0，P1，…，Pn}，系统中的所有进程的集合。
  • R = {R0，R1，…，Rm}，系统中所有资源类型的集合。
  • 申请边：Pi → Rj
  • 分配边：Rj → Pi
  • 如果资源分配图不包含环，则系统中的任何进程都不会死锁;
  • 如果资源分配图包含环，则可能存在死锁。

死锁处理方法

  • 可以设计一个协议来预防或避免死锁，确保系统永远不会进入死锁状态。
  • 可以允许系统进入死锁状态，检测并从中恢复。
  • 可以完全忽略这个问题，并假设系统中永远不会发生死锁。(鸵鸟算法)
  • 大多数操作系统都使用该解决方案，包括Windows和Unix。
  • 由于死锁很少发生，并且死锁预防、死锁避免或死锁检测和恢复算法成本很高。
  • 这是便利性和正确性之间的权衡。