死锁
前言
- 在多道程序环境中，多个进程可以竞争有限数量的资源。当一个进程申请资源时，如果这时没有可用资源，那么这个进程进入等待状态。有时，如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变状态。这种情况称为死锁（deadlock)。
系统模型
有一个系统拥有有限数量的资源，需要分配到若干竞争进程。这些资源可以分成多种类型，每种类型有一定数量的实例。资源类型有很多，如CPU周期、文件、I/O设备(打印机和DVD驱动器）等。
如果一个进程申请某个资源类型的一个实例，那么分配这种类型的任何实例都可满足申请。
各种同步工具，如互斥锁和信号量。这些工具也应作为系统资源，它们是常见的死锁源。然而，一个锁通常与保护某个特定的数据结构相关联，即一个锁可用于保护队列的访问，另一个锁保护访问链接列表的访问，等等。由于这个原因，每个锁通常有自己的资源类型，并且这种定义不是一个问题。
进程在使用资源前应申请资源，在使用资源之后应释放资源。一个进程可能要申请许多资源，以便完成指定任务。显然，申请的资源数量不能超过系统所有资源的总和。
在正常操作模式下，进程只能按如下顺序使用资源:
- 申请:进程请求资源。如果申请不能立即被允许（例如，申请的资源正在被其他进程使用)，那么申请进程应等待，直到它能获得该资源为止。
- 使用:进程对资源进行操作（例如，如果资源是打印机，那么进程就可以在打印机上打印了)。
- 释放:进程释放资源。
当进程或线程每次使用内核管理的资源时，操作系统会检查以确保该进程或线程已经请求并获得了资源。系统表记录每个资源是否是空闲的或分配的。对于每个已分配的资源，该表还记录了它被分配的进程。如果进程申请的资源正在为其他进程所使用，那么该进程会添加到该资源的等待队列上。
当一组进程内的每个进程都在等待一个事件，而这一事件只能由这一组进程的另一个进程引起，那么这组进程就处于死锁状态。这里所关心的主要事件是资源的获取和释放。资源可能是物理资源（例如，打印机、磁带驱动器、内存空间和CPU周期)或逻辑资源（例如，信号量、互斥锁和文件)。
死锁也可能涉及不同资源类型。例如，假设一个系统有一台打印机和一台DVD驱动器。假如进程P0占有DVD驱动器而进程P1占有打印机。如果P0申请打印机而P1申请DVD驱动器，那么就会出现死锁。
死锁特征
前言
当死锁时，进程永远不能完成，系统资源被阻碍使用，以致于阻止了其他作业开始执行。
必要条件
如果在一个系统中以下四个条件同时成立，那么就能引起死锁:
- 互斥( mutual exclusion):至少有一个资源必须处于非共享模式，即一次只有一个进程可使用。如果另一进程申请该资源，那么申请进程应等到该资源释放为止。
- 占有并等待(hold and wait):一个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有。
- 非抢占(no preemption):资源不能被抢占，即资源只能被进程在完成任务后自愿释放。
- 循环等待（(circular wait):有一组等待进程{P0,P1,…,Pn.}) ,P0等待的资源为P1占有，P1等待的资源为P2占有，……，Pn-1等待的资源为Pn占有,Pn等待的资源为P0占有。我们强调所有四个条件必须同时成立才会出现死锁。循环等待条件意味着占有并等待条件，这样四个条件并不完全独立。
资源分配图
- 通过称为系统资源分配图( system resource-allocation graph)的有向图可以更精确地描述死锁。该图包括一个节点集合V和一个边集合E。节点集合V可分成两种类型:P={P1,P2，…,Pn}(系统所有活动进程的集合）和R= {R1,R2，…，Rm}（系统所有资源类型的集合)。
- 从进程Pi,到资源类型Rj 的有向边记为Pi→Rj，它表示进程Pi已经申请了资源类型Rj的一个实例，并且正在等待这个资源。从资源类型Rj到进程Pi的有向边记为Rj→Pi，它表示资源类型Rj的一个实例已经分配给了进程Pi。有向边Pi→Rj称为申请边（ request edge),有向边Rj→Pi称为分配边( assignment edge)。
- 在图形上，用圆表示进程Pi，用矩形表示资源类型Rj。由于资源类型Rj,可能有多个实例，所以矩形内的点的数量表示实例数量。注意申请边只指向矩形Rj，而分配边应指定矩形内的某个圆点。
- 当进程Pi申请资源类型Rj的一个实例时，就在资源分配图中加入一条申请边。当该申请可以得到满足时，那么申请边就立即转换成分配边。当进程不再需要访问资源时，它就释放资源，因此就删除了分配边。如图
- 根据资源分配图的定义，可以证明:如果分配图没有环，那么系统就没有进程死锁。如果分配图有环,那么可能存在死锁。
- 如果每个资源类型刚好有一个实例，那么有环就意味着已经出现死锁。如果环上的每个类型只有一个实例，那么就出现了死锁。环上的进程就死锁。在这种情况下，图中的环就是死锁存在的充分且必要条件。
- 如果每个资源类型有多个实例，那么有环并不意味着已经出现了死锁。在这种情况下，图中的环就是死锁存在的必要条件而不是充分条件。
- 总而言之，如果资源分配图没有环，那么系统就不处于死锁状态。如果有环，那么系统可能会也可能不会处于死锁状态。在处理死锁问题时，这点是很重要的。
死锁处理方法
一般来说,处理死锁问题有三种方法:
- 通过协议来预防或避免死锁,确保系统不会进入死锁状态。
- 可以允许系统进入死锁状态，然后检测它，并加以恢复。
- 可以忽视这个问题,认为死锁不可能在系统内发生。
第三种解决方案为大多数操作系统所采用，包括Linux和 Windows。因此，应用程序开发人员需要自己编写程序,以便处理死锁。
为了确保死锁不会发生，系统可以采用死锁预防或死锁避免方案。
死锁预防( deadlock prevention)方法确保至少有一个必要条件不成立。这些方法通过限制如何申请资源的方法来预防死锁。
死锁避免（ deadlock avoidance)要求，操作系统事先得到有关进程申请资源和使用资源的额外信息。有了这些额外信息，系统可以确定:对于每个申请，进程是否应等待。为了确定当前申请是允许还是延迟，系统应考虑:现有的可用资源、已分配给每个进程的资源及每个进程将来申请和释放的资源。
如果系统不使用死锁预防或死锁避免算法，那么死锁情况可能发生。在这种情况下，系统可以提供一个算法来检查系统状态以确定死锁是否发生，提供另一个算法来从死锁中恢复(如果死锁确实已经发生)。
当没有算法用于检测和恢复死锁时，可能出现这样的情况:系统处于死锁，而又没有方法检测到底发生了什么。在这种情况下，未被发现的死锁会导致系统性能下降，因为资源被不能运行的进程占有，而越来越多的进程会因申请资源而进入死锁。最后，整个系统会停止工作,且需要人工重新启动。
对于许多系统，死锁很少发生(如一年一次)，因此，与使用频繁的并且开销昂贵的死锁预防、死锁避免和死锁检测与恢复相比，这种方法更为便宜。
死锁预防
前言
- 发生死锁有4个必要条件。只要确保至少一个必要条件不成立，就能预防死锁发生。下面，通过详细讨论这4个必要条件来研究这种方法。
互斥
- 互斥条件必须成立。也就是说，至少有一个资源应是非共享的。相反，可共享资源不要求互斥访问，因此不会参与死锁。只读文件是一个很好的共享资源例子。如果有多个进程试图同时打开一个只读文件，那么它们可以同时访问文件。进程决不需要等待共享资源。然而，通常不能通过否定互斥条件来预防死锁，因为有的资源本身就是非共享的。例如，一个互斥锁不能同时被多个进程所共享。
占有并等待
- 为了确保持有并等待条件不会出现在系统中，应保证:当每个进程申请一个资源时，它不能占有其他资源。一种可以采用的协议是，每个进程在执行前申请并获得所有资源。这可以这样实现:要求进程申请资源的系统调用在所有其他系统调用之前进行。
- 另外一种协议允许进程仅在有资源时才可申请资源。一个进程可申请一些资源并使用它们。然而，在它申请更多其他资源之前，它应释放现已分配的所有资源。
- 这两种协议有两个主要缺点。第一，资源利用率可能比较低，因为许多资源可能已分配，但是很长时间没有被使用。
- 第二，可能发生饥饿。一个进程如需要多个常用资源，可能必须永久等待，因为在它所需要的资源中至少有一个已分配给其他进程。
无抢占
- 第三个必要条件是，不能抢占已分配的资源。为了确保这一条件不成立，可以采用如下协议:如果一个进程持有资源并申请另一个不能立即分配的资源（也就是说，这个进程应等待)，那么它现在分配的资源都可被抢占。换句话说，这些资源都被隐式释放了。被抢占资源添加到进程等待的资源列表上。只有当进程获得其原有资源和申请的新资源时，它才可以重新执行。
- 换句话说，如果一个进程申请一些资源，那么首先检查它们是否可用。如果可用，那么就分配它们。如果不可用，那么检查这些资源是否已分配给等待额外资源的其他进程。如果是，那么从等待进程中抢占这些资源，并分配给申请进程。如果资源不可用且也不被其他等待进程持有，那么申请进程应等待。当一个进程处于等待时，如果其他进程申请其拥有资源，那么该进程的部分资源可以被抢占。只有当一个进程分配到申请的资源，并且恢复在等待时被抢占的资源时,它才能重新执行。
- 这个协议通常用于状态可以保存和恢复的资源，如CPU寄存器和内存。它一般不适用于其他资源，如互斥锁和信号量。
循环等待
死锁的第四个也是最后一个条件是循环等待。确保这个条件不成立的一个方法是:对所有资源类型进行完全排序，而且要求每个进程按递增顺序来申请资源。
为了说明起见，假设资源类型的集合为R= {R1，R2，…，Rm}。为每个资源类型分配一个唯一整数，这样可以比较两个资源以确定它们的先后顺序。形式地，我们可以定义一个函数F:R→N，其中N是自然数的集合。例如，如果资源类型R的集合包括磁带驱动器、磁盘驱动器和打印机，那么函数F可以定义成:
F(磁带驱动器)=1
F(磁盘驱动器)=5
F(打印机)=12
我们可以采用如下协议来预防死锁:每个进程只能按递增顺序申请资源。即一个进程开始可申请任何数量的资源类型Ri的实例。之后，当且仅当F(Rj)>F(Ri)时，该进程才可以申请资源类型Rj的实例。例如，采用上面定义的函数，一个进程如要同时使用磁带驱动器和打印机时，应首先请求磁带驱动器，然后请求打印机。换句话说，要求当一个进程申请资源类型R时，它应先释放所有资源Ri(F(Ri)≥ F(Rj))。请注意，如果需要同一资源类型的多个实例,那么应一起申请它们。
如果使用这两个协议，那么循环等待就不可能成立。通过反证法可以证明这一点。假定存在一个循环等待。设循环等待的进程集合为{P0，P1，…，Pn}，其中Pi等待一个资源Ri，而Ri又为进程Pi+1所占有。(对于索引采用取模运算，因此Pn等待由P0所占有的资源Rn)。因此，由于进程Pi+1占有资源Ri而同时申请资源Ri+1，所以对所有i，我们有F(Ri)<F(Ri+i)。而这意味着F(R0)<F(R1)<…<F(Rn)<F(R0)。根据传递规则，F(Ro)<F(R0)，这显然是不可能的。因此，不可能有循环等待。
死锁避免
前言
- 死锁预防算法中，通过限制如何申请资源来预防死锁。这种限制确保,至少有一个死锁的必要条件不会发生。然而，通过这种方法预防死锁有副作用:设备使用率低和系统吞吐率低。
- 避免死锁的另一种方法需要额外信息，即如何申请资源。例如，有一台磁带驱动器和一台打印机的系统可能需要知道:进程Р将会先申请磁带驱动器，再申请打印机，最后释放这些资源;而进程Q将会先申请打印机，再申请磁带驱动器。在获悉每个进程的请求与释放的完整顺序之后，系统可以决定，在每次请求时进程是否应该等待以避免未来可能的死锁。针对每次申请要求，系统在做决定时考虑现有可用资源、现已分配给每个进程的资源和每个进程将来申请与释放的资源。
- 采用这种方法的算法有许多，它们在所要求的信息类型和数量上有差异。最简单且最有用的模型要求，每个进程都应声明可能需要的每种类型资源的最大数量。鉴于这个先验信息，有可能构造一个算法，以便确保系统不会进入死锁状态。死锁避免算法动态检查资源分配状态，以便确保循环等待条件不能成立。资源分配状态包括可用的资源、已分配的资源及进程的最大需求。下面，我们讨论两个死锁避免算法。
安全状态
- 如果系统能按一定顺序为每个进程分配资源(不超过它的最大需求)，仍然避免死锁，那么系统的状态就是安全的( safe)。更为正式地说，只有存在一个安全序列( safesequence)，系统才处于安全状态。进程序列〈P1，P2，…，Pn〉在当前分配状态下为安全序列是指:对于每个Pi，Pi仍然可以申请的资源数小于当前可用资源加上所有进程Pj(其中j<i)所占有的资源。在这种情况下，进程Pi需要的资源即使不能立即可用，那么Pi可以等待直到所有Pj释放资源。当它们完成时，Pi可得到需要的所有资源，完成给定任务，返回分配的资源，最后终止。当Pi终止时，Pi+1可得到它需要的资源，如此进行。如果没有这样的序列存在，那么系统状态就是非安全的(unsafe )。
- 安全状态不是死锁状态。相反，死锁状态是非安全状态。然而，不是所有的非安全状态都能导致死锁状态。非安全状态可能导致死锁。只要在安全状态下，操作系统就能避免非安全（和死锁)状态。在非安全状态下,操作系统不能阻止进程申请资源,因而可能死锁。进程行为控制了非安全状态。
- 通过安全状态的概念，我们可以定义避免算法，以便确保系统不会死锁。这个想法简单，即确保系统始终处于安全状态。最初，系统处于安全状态。当有进程申请一个可用资源时，系统应确定:这一资源申请是可以立即分配，还是应让进程等待。只有在分配后系统仍处于安全状态，才能允许申请。
- 采用这种方案，如果进程申请一个现已可用的资源，那么它可能仍然必须等待。因此，与没有采用死锁避免算法相比,这种情况下的资源使用率可能更低。
资源分配图算法
除了申请边和分配边外，我们引入一新类型的边，称为需求边(claim edge)。需求边Pi→Rj,表示，进程Pi可能在将来某个时候申请资源Rj。这种边类似于同一方向的申请边，但是用虚线表示。当进程Pi申请资源Rj时，需求边Pi→Rj,变成了申请边。类似地，当进程Pi释放Rj时，分配边Rj→Pi,变成了需求边Pi→Rjo
请注意，系统资源的需求应事先说明。即当进程Pi开始执行时，所有需求边应先处于资源分配图内。
现在，假设进程Pi申请资源Rj。只有在将申请边Pi→Rj变成分配边Rj→Pi;并且不会导致资源分配图形成环时，才能允许申请。通过采用环检测算法，检查安全性。检测图中是否有环的算法需要n^2数量级的操作，其中n^2是系统的进程数量。
如果没有环存在，那么资源的分配会使得系统处于安全状态。如果有环存在，那么分配会导致系统处于非安全状态。在这种情况下，进程Pi应等待资源申请。注意需求边也应在环的考虑范围
比如这个图中，就不能把R2分配给P2。
银行家算法-----死锁避免算法
概念
对于每种资源类型有多个实例的资源分配系统，资源分配图算法就不适用了。这一算法通常称为银行家算法( banker's algorithm)。
当一个新的进程进入系统时，它应声明可能需要的每种类型资源实例的最大数量，这一数量不能超过系统资源的总和。当用户申请一组资源时，系统应确定这些资源的分配是否仍会使系统处于安全状态。如果会，就可分配资源;否则，进程应等待，直到某个其他进程释放足够多的资源为止。
为了实现银行家算法，需要有几个数据结构。这些数据结构对资源分配系统的状态进行了记录。我们需要以下数据结构，这里n为系统进程的数量,m为资源类型的种类:
- Available :长度为m的向量，表示每种资源的可用实例数量。如果 Available[j]=k,那么资源类型Rj有k个可用实例。
- Max : nxm矩阵，定义每个进程的最大需求。如果Max[i][j]= k，那么进程Pi最多可申请资源类型Rj的k个实例。
- Allocation : n×m矩阵，定义每个进程现在分配的每种资源类型的实例数量。如果Allocation[i][j]=k，那么进程Pi现在已分配了资源类型Rj的k个实例。
- Need : nxm矩阵，表示每个进程还需要的剩余资源。如果 Need[i][j]= k，那么进程Pi还可能申请k个资源类型Rj的实例。注意Need[i][j]=Max[i][j]-Allocation[i][j]。这些数据结构的大小和值会随着时间而改变。
为了简化银行家算法的描述，下面采用一些符号。设X和Y为长度为n的向量。我们说:X≤Y当且仅当对所有i= 1，2，…，n，X[i]≤Y[i]。此外，如果Y≤X且Y≠X，那么Y<X。
可以将矩阵 Allocation和 Need 的每行作为向量，并分别用Allocationi和 Needi来表示。向量Allocationi表示分配给进程Pi的资源;向量 Needi表示进程为完成任务可能仍然需要申请的额外资源。
安全算法
现在我们介绍这个算法，以求出系统是否处于安全状态。该算法可以描述如下:
1.令 Work和Finish分别为长度m和n的向量。对于i=0，1，…， n-1，初始化 Work =Available和 Finish[i] = false。
2.查找这样的i使其满足
- a.Finish[i]== false
- b. Needi≤Work
- 如果没有这样的i存在,那么就转到第4步。
\3. Work = Work +Allocationi
- Finish[i] = true
- 返回到第2步。
4.如果对所有i，Finish[i]= true，那么系统处于安全状态。
这个算法可能需要m×n^2数量级的操作，以确定系统状态是否安全。
资源请求算法
现在,我们描述判断是否安全允许请求的算法。
设Requesti为进程Pi的请求向量。如果Requesti[j]== k，那么进程Pi需要资源类型Rj的实例数量为k。当进程Pi作出这一资源请求时，就采取如下动作:
1.如果Requcsti≤ Needi，转到第2步。否则，生成出错条件，这是因为进程Pi已超过了其最大需求。
2.如果Requesti≤ Available，转到第3步。否则，Pi应等待，这是因为没有资源可用。
3.假定系统可以分配给进程Pi请求的资源，并按如下方式修改状态:
- Available = Available-Requesti
- Allocationi = Allocationi+ Requesti
- Needi = Needi-Requesti
如果新的资源分配状态是安全的，那么交易完成且进程Pi可分配到需要的资源。然而,如果新状态不安全，那么进程Pi应等待Requesti并恢复到原来的资源分配状态。
死锁检测
如果一个系统既不采用死锁预防算法也不采用死锁避免算法，那么死锁可能出现。在这种环境下，系统可以提供:
- 一个用来检查系统状态从而确定是否出现死锁的算法;
- 一个用来从死锁状态中恢复的算法。
不过，这里需要注意，检测并恢复的方案会有额外开销，这些不但包括维护所需信息和执行检测算法的运行开销，而且也包括死锁恢复引起的损失。
每种资源只有单个实例
如果所有资源类型只有单个实例，我们可以定义这样一个死锁检测算法，该算法使用了资源分配图的一个变形，称为等待( wait-for)图。从资源分配图中，删除所有资源类型节点，合并适当边，就可以得到等待图。
更确切地说，等待图的从Pi到Pj的边意味着:进程Pi等待进程Pj释放一个Pi所需的资源。等待图有一条由Pi→Pj的边，当且仅当相应资源分配图包含两条边Pi→Rq和Rq→Pj，其中Rq为资源。例如，图7-9为一个资源分配图及其对应的等待图。
与以前一样，当且仅当在等待图中有一个环，系统死锁。为了检测死锁，系统需要维护等待图，并周期调用用于搜索图中环的算法。从图中检测环的算法需要n^2数量级的操作，其中n为图的节点数。
每种资源类型可有多个实例
等待图方案不适用于每种资源类型可有多个实例的资源分配系统。下面描述的死锁检测算法适用于这样的系统。该算法使用了一些随时间而变化的数据结构，类似于银行家算法:
- Available:长度为m的向量,表示各种资源的可用实例数量。
- Allocation: n×m矩阵,表示每个进程的每种资源的当前分配数量。
- Request:n×m矩阵，表示当前每个进程的每种资源的当前请求。如果Request[i][j]=k，那么Pi现在正在请求资源类型Rj的k个实例。
两向量的≤关系与银行家定义的一样。为了简化起见，将Allocation和 Request的行作为向量，并分别称为Allocationi和Requesti。
1.设Work 和 Finish分别为长度为m和n的向量。初始化 Work = Available。对i= 0,l，…，n-1，如果Allocationi不为0，则 Finish[i] = false;否则，Finish[i] = true。
2.找这样的i，同时满足
- a. Finish[i]== false
- b.Requesti≤ Work
- 如果没有这样的i,则转到第4步
\3. Work = Work +Allocationi
- Finish[i] = true
- 转到第2步。
4.如果对某个i(0≤ i <n)，Finish[i]== false，则系统死锁。而且，如果Finish[i] ==false，则进程Pi死锁。
该算法需要m×n^2数量级的操作，来检测系统是否处于死锁状态。
应用检测算法
何时应该调用检测算法?答案取决于两个因素
- 死锁可能发生的频率是多少?
- 当死锁发生时,有多少进程会受影响?
如果经常发生死锁，就应经常调用检测算法。分配给死锁进程的资源会一直空着，直到死锁被打破。另外，参与死锁等待环的进程数量可能不断增加。
只有当某个进程提出请求且得不到满足时，才会出现死锁。在极端情况下，即每次分配请求不能立即允许时，就调用死锁检测算法。在这种情况下，不仅能确定哪些进程死锁，而且能确定哪个特定进程“造成”了死锁。
当然，对于每个请求都调用死锁检测算法将会引起相当的计算开销。另一个不太昂贵的方法只是每隔一定时间调用检测算法，如每小时一次，或当CPU使用率低于40%时。(死锁最终会使系统性能下降，并造成CPU使用率下降。)如果在任一时间点调用检测算法，那么资源图可能有多个环。通常不能确定哪个死锁进程“造成”了死锁。
死锁恢复
前言
- 当检测算法确定已有死锁时，存在多种可选方案。一种可能是，通知操作员死锁已发生，并且让操作员人工处理死锁。另一种可能是，让系统从死锁状态中自动恢复(recover)过来。打破死锁有两个选择。一个是，简单地中止一个或多个进程来打破循环等待。另一个是，从一个或多个死锁进程那里抢占一个或多个资源。
进程终止
通过中止进程来消除死锁，有两种方法。这两种方法都允许系统收回终止进程的所有分配资源。
- 中止所有死锁进程。这种方法显然会打破死锁环，但是代价也大。这些死锁进程可能已计算了较长时间;这些部分计算的结果也要放弃，并且以后可能还要重新计算。
- 一次中止一个进程，直到消除死锁循环为止。这种方法的开销会相当大，这是因为每次中止一个进程，都应调用死锁检测算法，以确定是否仍有进程处于死锁。
终止一个进程并不简单。如果进程正在更新文件，那么终止它会使文件处于不正确的状态。类似地，如果进程正在打印数据，那么系统在打印下一个文件之前应将打印机重置到正确的状态。
如果采用了部分终止，那么我们应确定哪个(或哪些)死锁进程应该终止。这个确定，类似于CPU调度决策，是策略决策。这个问题基本上是经济问题;我们应该中止造成最小代价的进程。(minimum cost)
资源抢占
通过资源抢占来消除死锁，我们不断地抢占一些进程的资源以便给其他进程使用，直到死锁循环被打破为止。
如果要求采用抢占来处理死锁,那么需要处理三个问题:
选择牺牲进程:抢占哪些资源和哪些进程?与进程终止一样，应确定抢占的顺序，使得代价最小。代价因素可包括这样的参数，如死锁进程拥有的资源数量、死锁进程到现在为止所消耗的时间等。
回滚:如果从一个进程那里抢占了一个资源，那么应对该进程做些什么安排?显然，该进程不能继续正常执行;它缺少所需的某些资源。我们应将该进程回滚到某个安全状态，以便从该状态重启进程。
因为一般来说，很难确定什么是安全状态，最简单的解决方案是完全回滚:中止进程并重新执行。然而，更为有效的方法是回滚进程直到足够打破死锁，但是这种方法要求系统维护有关运行进程的更多状态信息。
饥饿:如何确保不会发生饥饿?即如何保证资源不会总是从同一个进程中被抢占。
如果一个系统是基于代价来选择牺牲进程，那么同一进程可能总是被选为牺牲的。结果，这个进程永远不能完成指定任务，任何实际系统都需要处理这种饥饿情况。显然应确保一个进程只能有限次数地被选为牺牲进程。最为常用的方法是在代价因素中加上回滚次数。