处理机调度与死锁

  在多道程序环境下，内存中存在着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地将处理机分配给处于就绪状态的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。对于大型系统运行时的性能，如系统吞吐量、资源利用率、作业周转时间或响应的及时性等，在很大程度上都取决于处理机调度性能的好坏。因而，处理机调度便成为OS中至关重要的部分。

处理机调度的层次和调度算法的目标

  在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。在多道批处理系统中，一个作业从提交到获得处理机执行，直至作业运行完毕，可能需要经历多级处理机调度，下面先来了解处理机调度的层次。

处理机调度的层次

高级调度(High Level Scheduling)

  高级调度又称长程调度或作业调度，它的调度对象是作业。其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。

低级调度(Low Level Scheduling)

  低级调度又称为进程调度或短程调度，其所调度的对象是进程（或内核级线程）。其主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。

中级调度(Intermediate Scheduling)

  中级调度又称为内存调度。引入中级调度的主要目的是，提高内存利用率和系统吞吐量。为此，应把那些暂时不能运行的进程，调至外存等待，此时进程的状态称为就绪驻外存状态（或挂起状态）。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。中级调度实际上就是存储器管理中的对换功能。

  在上述三种调度中，进程调度的运行频率最高，在分时系统中通常仅10〜 \(100 \text{ms}\) 便进行一次进程调度，因此把它称为短程调度。为避免调度本身占用太多的CPU时间，不宜使进程调度算法太复杂。作业调度往往是发生在一批作业已运行完毕并退出系统，又需要重新调入一批作业进入内存时，作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。中级调度的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。

处理机调度算法的目标

  一般而言，在一个操作系统的设计中，应如何选择调度方式和算法，在很大程度上取决于操作系统的类型及其设计目标，例如，在批处理系统、分时系统和实时系统中，通常都采用不同的调度方式和算法。

处理机调度算法的共同目标

  (1)资源利用率。为提高系统的资源利用率，应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态，其中最重要的处理机利用率可用以下方法计算：

\[ \text{CPU的利用率}=\frac{\text{CPU有效工作时间}}{\text{CPU有效工作时间}+\text{CPU空闲等待时间}} \tag{1} \]

  (2)公平性。公平性是指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。公平性是相对的，对相同类型的进程应获得相同的服务；但对于不同类型的进程，由于其紧急程度或重要性的不同，则应提供不同的服务。
  (3)平衡性。由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。
  (4)策略强制执行。对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

批处理系统的目标

  (1)平均周转时间短。所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔（称为作业周转时间）。它包括四部分时间：作业在外存后备队列上等待（作业）调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间。其中的后三项在一个作业的整个处理过程中，可能发生多次。
  对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望能使平均周转时间最短，这不仅会有效地提高系统资源的利用率，而且还可使大多数用户都感到满意。应使作业周转时间和作业的平均周转时间尽可能短。否则，会使许多用户的等待时间过长，这将会引起用户特别是短作业用户的不满。可把平均周转时间描述为

\[ T=\frac{1}{n}\left(\sum_{i=1}^{n}T_i\right) \tag{2} \]

  为了进一步反映调度的性能，更清晰地描述各进程在其周转时间中，等待和执行时间的具体分配状况，往往使用带权周转时间，即作业的周转时间 \(T\) 与系统为它提供服务的时间 \(T_s\) 之比，即 \(\displaystyle W=\frac{T}{T_s}\) 。而平均带权周转时间则可表示为：

\[ W=\frac{1}{n}\sum_{i=1}^{n}\frac{T_i}{T_s} \tag{3} \]

  (2)系统吞吐量高。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度有关。事实上，如果单纯是为了获得高的系统吞吐量，就应尽量多地选择短作业运行。
  (3)处理机利用率高。对于大、中型计算机，CPU价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标：而调度方式和算法又对处理机的利用率起着十分重要的作用。如果单纯是为使处理机利用率高，应尽量多地选择计算量大的作业运行。由上所述可以看出，这些要求之间是存在着一定矛盾的。

分时系统的目标

  (1)响应时间快。响应时间快是选择分时系统中进程调度算法的重要准则。所谓响应时间，是从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔。它包括三部分时间：一是请求信息从键盘输入开始，直至将其传送到处理机的时间；二是处理机对请求信息进行处理的时间；三是将所形成的响应信息回送到终端显示器的时间。
  (2)均衡性。用户对响应时间的要求并非完全相同。通常用户对较复杂任务的响应时间允许较长，而对较简单任务的响应时间则要短。所谓均衡性，是指系统响应时间的快慢应与用户所请求服务的复杂性相适应。

实时系统的目标

  (1)截止时间的保证。所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须能保证这一点，否则将可能造成难以预料的后果。对于实时系统而言，调度算法的一个主要目标是保证实时任务对截止时间的要求。对于HRT任务，其调度方式和调度算法必须确保对截止时间的要求，否则将可能造成难以预料的后果；而对于SRT任务，其调度方式和调度算法也应基本上能保证对截止时间的要求。
  (2)可预测性。在实时系统中，可预测性显得非常重要。例如，在多媒体系统中，无论是电影还是电视剧都应是连续播放的，这就提供了请求的可预测性。如果系统中采用了双缓冲，则因为可实现第 \(i\) 帧的播放和第 \(i+1\) 帧的读取并行处理，进而可提高其实时性。

作业与作业调度

  在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。操作员把用户 提交的作业通过相应的输入设备输入到磁盘存储器，并保存在一个后备作业队列中。再由作业调度程序将其从外存调入内存。

批处理系统中的作业

作业和作业步

  (1)作业(Job)。作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。
  (2)作业步(Job Step)。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。我们把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，往往是上一个作业步的输出作为下一个作业步的输入。例如，一个典型的作业可分成：“编译”作业步，“链接装配”作业步和“运行”作业步。

作业控制块(Job Control Block,JCB)

  为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。通常在JCB中包含的内容有：作业标识、用户名称、用户账号、作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、要求内存大小等）、资源使用情况等。
  每当一个作业进入系统时，便由“作业注册”程序为该作业建立一个作业控制块JCB。再根据作业类型，将它放到相应的作业后备队列中等待调度。调度程序依据一定的调度算法来调度它们，被调度到的作业将被装入内存。在作业运行期间，系统就按照JCB中的信息和作业说明书对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收已分配给它的资源，撤销该作业控制块。

作业运行的三个阶段和三种状态

  作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有“后备状态”、“运行状态”和“完成状态”。
  (1)收容阶段。操作员把用户提交的作业通过某种输入方式或SPOOLing系统输入到硬盘上，再为该作业建立JCB，并把它放入作业后备队列中。相应地，此时作业的状态为“后备状态”。
  (2)运行阶段。当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从第一次进入就绪状态开始，直到它运行结束前，在此期间都处于“运行状态”。
  (3)完成阶段。当作业运行完成、或发生异常情况而提前结束时，作业便进入完成阶段，相应的作业状态为“完成状态”。此时系统中的“终止作业”程序将会回收己分配给该作业的作业控制块和所有资源，并将作业运行结果信息形成输出文件后输出。

作业调度的主要任务

  作业调度的主要任务是，根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。因此，也把作业调度称为接纳调度(Admission Scheduling)。在每次执行作业调度时，都需做出以下两个决定。

接纳多少个作业

  在每一次进行作业调度时，应当从后备队列中选取多少作业调入内存，取决于多道程序度(Degree of Multiprogramming)，即允许多少个作业同时在内存中运行。对系统来说，希望装入较多的作业，有利于提高CPU的利用率和系统的吞吐量。但如果内存中同时运行的作业太多时，进程在运行时因内存不足所发生的中断就会急剧增加。这将会使平均周转时间显著延长，影响到系统的服务质量。因此，多道程序度的确定是根据计算机的系统规模、运行速度、作业大小，以及能否获得较好的系统性能等情况作出适当的抉择的。

接纳哪些作业

  应选择后备队列中的哪些作业调入内存，取决于所采用的调度算法。最简单的是先来先服务调度算法，它是将最早进入外存的作业优先调入内存。较常用的一种算法是短作业优先调度算法，是将外存上所需执行时间最短的作业优先调入内存。另一种较常用的是基于作业优先级的调度算法，该算法是将外存上作业优先级最高的作业优先调入内存。比较好的一种算法是“响应比高者优先”的调度算法。我们将在后面对上述的几种算法作较详细的介绍。
  在批处理系统中，作业进入系统后，总是先驻留在外存的作业后备队列上，因此需要有作业调度，以便将它们分批地装入内存。然而在分时系统中，为了做到及时响应，用户通过键盘输入的命令或数据等都被直接送入内存，因而无需配置上述的作业调度机制，但也需要有某种接纳控制措施来限制进入系统的用户数目。即如果系统尚有能力处理更多的任务，将会接纳授权用户的请求，否则，便拒绝接纳。类似地，在实时系统中也不需要作业调度，而必需具有接纳控制措施。

先来先服务(FCFS)和短作业优先(SJF)调度算法

先来先服务(first-come first-served,FCFS)调度算法

  FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。
  当在进程调度中采用FCFS算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其它进程。
  顺便说明，FCFS算法在单处理机系统中已很少作为主调度算法，但经常把它与其它调度算法相结合使用，形成一种更为有效的调度算法。例如，可以在系统中按进程的优先级设置多个队列，每个优先级一个队列，其中每一个队列的调度都基于FCFS算法。

短作业优先(short job first,SJF)的调度算法

  由于在实际情况中，短作业(进程)占有很大比例，为了能使它们能比长作业优先执行，而产生了短作业优先调度算法。
  SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。
  SJF调度算法较之FCFS算法有了明显的改进，但仍然存在不容忽视的缺点：
  (1)必须预知作业的运行时间。在采用这种算法时，要先知道每个作业的运行时间。即使是程序员也很难准确估计作业的运行时间，如果估计过低，系统就可能按估计的时间终止作业的运行，但此时作业并未完成，故一般都会偏长估计。
  (2)对长作业非常不利，长作业的周转时间会明显地增长。更严重的是，该算法完全忽视作业的等待时间，可能使作业等待时间过长，出现饥饿现象。
  (3)在采用FCFS算法时，人—机无法实现交互。
  (4)该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。

优先级调度算法和高响应比优先调度算法

优先级调度算法(prioilty-scheduling algorithm,PSA)

  我们可以这样来看作业的优先级，对于先来先服务调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级越高。对于短作业优先调度算法，作业的长短就是作业的优先级，作业所需运行的时间越短，其优先级越高。但上述两种优先级都不能反映作业的紧迫程度。而在优先级调度算法中，则是基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的。这样就可以保证紧迫性作业优先运行。优先级调度算法可作为作业调度算法，也可作为进程调度算法。当把该算法用于作业调度时，系统是从后备队列中选择若干个优先级最高的作业装入内存。

高响应比优先调度算法(Highest Response Ratio Next,HRRN)

  在批处理系统中，FCFS算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。而SJF算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。
  高响应比优先算法是如何实现的呢？如果我们能为每个作业引入一个动态优先级，即优先级是可以改变的，令它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可描述为：

\[ \text{优先权}=\frac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}} \tag{4} \]

  由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比 \(R_p\) 。据此，优先又可表示为：

\[ R_p=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间} \tag{5} \]

  由上式可以看出：①如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而类似于SJF算法，有利于短作业。②当要求服务的时间相同时，作业的优先权又决定于其等待时间，因而该算法又类似于FCFS算法。③对于长作业的优先级，可以随等待时间的增加而提高，当其等待时间足够长时，也可获得处理机。因此该算法实现了较好的折中。当然在利用该算法时，每次要进行调度之前，都需要先做响应比的计算，显然会增加系统开销。

进程调度

  进程调度是OS中必不可少的一种调度。因此在三种类型的OS中，都无一例外地配置了进程调度。此外它也是对系统性能影响最大的一种处理机调度，相应的，有关进程调度的算法也较多。

进程调度的任务、机制和方式

进程调度的任务

  进程调度的任务主要有三：
  (1)保存处理机的现场信息。在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。
  (2)按某种算法选取进程。调度程序按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分配给它。
  (3)把处理器分配给进程。由分派程序把处理器分配给该进程，此时需要将选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。

进程调度机制

  为了实现进程调度，在进程调度机制中，应具有如下三个基本部分。
  (1)排队器。为了提高进程调度的效率，应事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便调度程序能最快地找到它。以后每当有一个进程转变为就绪状态时，排队器便将它插入到相应的就绪队列。
  (2)分派器。分派器依据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程。
  (3)上下文切换器。在对处理机进行切换时，会发生两对上下文的切换操作：①第一对上下文切换时，OS将保存当前进程的上下文，即把当前进程的处理机寄存器内容保存到该进程的进程控制块内的相应单元，再装入分派程序的上下文，以便分派程序运行；②第二对上下文切换是移出分派程序的上下文，而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中，以便新选进程运行。

图1 进程调度机制

  在进行上下文切换时，需要执行大量的load和store等操作指令，以保存寄存器的内容。即使是现代计算机，每一次上下文切换所花费的时间大约可执行上千条指令。为此，现在已有靠硬件实现的方法来减少上下文切换时间。一般采用两组（或多组）寄存器，其中的一组寄存器供处理机在系统态时使用，而另一组寄存器供应用程序使用。在这样条件下的上下文切换，只需改变指针，使其指向当前寄存器组即可。

进程调度方式

  早期所采用的非抢占方式存在着很大的局限性，很难满足交互性作业和实时任务的需求。为此，在进程调度中又引入了抢占方式。我们先了解一下非抢占方式时的情况。

1. 非抢占方式(Nonpreemptive Mode)

  在采用这种调度方式时，一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程。
  在采用非抢占调度方式时，可能引起进程调度的因素可归结为：①正在执行的进程运行完毕，或因发生某事件而使其无法再继续运行；②正在执行中的进程因提出I/O请求而暂停执行；③在进程通信或同步过程中，执行了某种原语操作，如Block原语。这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统。但它不能用于分时系统和大多数实时系统。

2. 抢占方式(Preemptive Mode)

  这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。在现代OS中广泛采用抢占方式，这是因为：对于批处理机系统，可以防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更为公平的服务。在分时系统中，只有采用抢占方式才有可能实现人—机交互。在实时系统中，抢占方式能满足实时任务的需求。但抢占方式比较复杂，所需付出的系统开销也较大。
  “抢占”不是一种任意性行为，必须遵循一定的原则。主要原则有：
  ①优先权原则，指允许优先级高的新到进程抢占当前进程的处理机，即当有新进程到达时，如果它的优先级比正在执行进程的优先级高，则调度程序将剥夺当前进程的运行，将处理机分配给新到的优先权高的进程。
  ②短进程优先原则，指允许新到的短进程可以抢占当前长进程的处理机，即当新到达的进程比正在执行的进程（尚须运行的时间）明显短时，将处理机分配给新到的短进程。
  ③时间片原则，即各进程按时间片轮转运行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度。

轮转调度算法

  在分时系统中，最简单也是较常用的是基于时间片的轮转(round robin,RR)调度算法。该算法采取了非常公平的处理机分配方式，即让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有 \(n\) 个进程，则每个进程每次大约都可获得 \(\cfrac{1}{n}\) 的处理机时间。

轮转法的基本原理

  在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间（如 \(30 \text{ms}\) ）便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。

进程切换时机

  在RR调度算法中，应在何时进行进程的切换，可分为两种情况：①若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。②在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

时间片大小的确定

  在轮转算法中，时间片的大小对系统性能有很大的影响。若选择很小的时间片，将有利于短作业，因为它能在该时间片内完成。但时间片小，意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销。反之，若时间片选择得太长，且为使每个进程都能在一个时间片内完成，RR算法便退化为FCFS算法，无法满足短作业和交互式用户的需求。一个较为可取的时间片大小是略大于一次典型的交互所需要的时间，使大多数交互式进程能在一个时间片内完成，从而可以获得很小的响应时间。图2示出了时间片大小对响应时间的影响，其中图2(a)是时间片略大于典型交互的时间，而图2(b)是时间片小于典型交互的时间。表1示出了时间片分别为 \(q=1\) 和 \(q=4\) 时对平均周转时间的影响。

图2 时间片大小对响应时间的影响

表1 q=1和q=4时进程的周转时间

优先级调度算法

  在时间片轮转调度算法中，做了一个隐含的假设，即系统中所有进程的紧迫性是相同的。但实际情况并非如此。为了能满足实际情况的需要，在进程调度算法中引入优先级，而形成优先级调度算法。

优先级调度算法的类型

  优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。这时，又可进一步把该算法分成如下两种。
  (1)非抢占式优先级调度算法。该算法规定，一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，系统方可将处理机重新分配给另一优先级最高的进程。
  (2)抢占式优先级调度算法。把处理机分配给优先级最高的进程，使之执行。但在其执行期间，只要出现了另一个其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。因此，在采用这种调度算法时，每当系统中出现一个新的就绪进程 \(i\) 时，就将其优先级 \(P_i\) 与正在执行的进程 \(j\) 的优先级 \(P_j\) 进行比较，如果 \(P_i \le P_j\) ，原进程 \(P_j\) 便继续执行；但如果是 \(P_i > P_j\) ，则立即停止 \(P_j\) 的执行，进行进程切换，使 \(i\) 进程投入执行。抢占式的优先级调度算法常用于对实时性要求较高的系统中。

优先级的类型

  优先级调度算法的关键在于：应如何确定进程的优先级，以及确定是使用静态优先级还是动态优先级。

1. 静态优先级

  静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的，例如10〜255中的某一整数，又把该整数称为优先数。确定进程优先级大小的依据有如下三个：
  (1)进程类型。通常系统进程（如接收进程、对换进程）的优先级高于一般用户进程的优先级。
  (2)进程对资源的需求。对资源要求少的进程应赋予较高的优先级。
  (3)用户要求。根据进程的紧迫程度及用户所付费用的多少确定优先级。
  静态优先级法简单易行，系统开销小，但不够精确，可能会出现优先级低的进程长期没有被调度的情况。

2. 动态优先级

  动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。例如，可以规定在就绪队列中的进程随其等待时间的增长，使其优先级相应提高。若所有的进程都具有相同优先级初值，则最先进入就绪队列的进程会因其优先级变得最高，而优先获得处理机，这相当于FCFS算法。若所有的就绪进程具有各不相同的优先级初值，那么对于优先级初值低的进程，在等待了足够的时间后，也可以获得处理机。当采用抢占式调度方式时，若再规定当前进程的优先级随运行时间的推移而下降，则可防止一个长作业长期地垄断处理机。

多队列调度算法

  如前所述的各种调度算法，尤其在应用于进程调度时，由于系统中仅设置一个进程的就绪队列，即低级调度算法是固定的、单一的，无法满足系统中不同用户对进程调度策略的不同要求，在多处理机系统中，这种单一调度策略实现机制的缺点更显突出，由此，多级队列调度算法能够在一定程度上弥补这一缺点。
  该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。
  多队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。
  在多处理机系统中，该算法由于安排了多个就绪队列，因此，很方便为每个处理机设置一个单独的就绪队列。这样，不仅对每个处理机的调度可以实施各自不同的调度策略，而且对于一个含有多个线程的进程而言，可以根据其要求将其所有线程分配在一个就绪队列，全部在一个处理机上运行。再者，对于一组需要相互合作的进程或线程而言，也可以将它们分配到一组处理机所对应的多个就绪队列，使得它们能同时获得处理机并行执行。

多级反馈队列(multilevel feedback queue)调度算法

  前面介绍的各种用于进程调度的算法都有一定的局限性。如果未指明进程长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而下述的多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，还可以较好地满足各种类型进程的需要，因而它是目前公认的一种较好的进程调度算法。

调度机制

  多级反馈队列调度算法的调度机制可描述如下：
  (1)设置多个就绪队列。在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。该算法为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。例如第二个队列的时间片要比第一个的时间片长一倍，···，第i+1个队列的时间片要比第i个的时间片长一倍。图3是多级反馈队列算法的示意图。

图3 多级反馈队列调度算法

  (2)每个队列都采用FCFS算法。当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，···，依此类推。当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。
  (3)按队列优先级调度。调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行；换言之，仅当第1~(i-1)所有队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。

调度算法的性能

  在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能较好地满足各种类型用户的需要。
  (1)终端型用户。由于终端型用户提交的作业多属于交互型作业，通常较小，系统只要能使这些作业在第一队列规定的时间片内完成，便可使终端型用户感到满意。
  (2)短批处理作业用户。对于这类作业，如果可在第一队列中执行完成，便获得与终端型作业一样的响应时间。对于稍长的短作业，也只需在第二和第三队列各执行一时间片完成，其周转时间仍然较短。
  (3)长批处理作业用户。对于长作业，它将依次在第1,2,···,n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。

基于公平原则的调度算法

  以上介绍的几种调度算法所保证的只是优先运行，如优先级算法是优先级最高的作业优先运行，但并不保证作业占用了多少处理机时间。另外也未考虑到调度的公平性。本小节将介绍两种相对公平的调度算法。

保证调度算法

  保证调度算法是另外一种类型的调度算法，它向用户所做出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。一种比较容易实现的性能保证是处理机分配的公平性。如果在系统中有 \(n\) 个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时间 \(\displaystyle\frac{1}{n}\) 。在实施公平调度算法时系统中必须具有这样一些功能：
  (1)跟踪计算每个进程自创建以来已经执行的处理时间。
  (2)计算每个进程应获得的处理机时间，即自创建以来的时间除以 \(n\) 。
  (3)计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比。
  (4)比较各进程获得处理机时间的比率。如进程A的比率最低，为0.5；而进程B的比率为0.8；进程C的比率为1.2等。
  (5)调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。

公平分享调度算法

  分配给每个进程相同的处理机时间，显然，这对诸进程而言，是体现了一定程度的公平，但如果各个用户所拥有的进程数不同，就会发生对用户的不公平问题。假如系统中仅有两个用户，用户1启动了4个进程，用户2只启动1个进程，采用轮转法让每个进程轮流运行一个时间片时间，对进程而言很公平，但用户1和用户2得到的处理机时间分别为80%和20%，显然对用户2而言就有失公平。在该调度算法中，调度的公平性主要是针对 用户而言，使所有用户能获得相同的处理机时间，或所要求的时间比例。然而调度又是以进程为基本单位，为此，必须考虑到每一个用户所拥有的进程数目。例如系统中有两个用 户，用户1有4个进程A、B、C、D，用户2只有1个进程E。为保证两个用户能获得相 同的处理机时间，则必须执行如下所示的强制调度序列：

  A E B E C E D E A E B E C E D E ···

  如果希望用户1所获得的处理机时间是用户2的两倍，则必须执行如下所示的强制调度序列：

  A B E C D E A B E C D E A B E C D E ···

实时调度

  在实时系统中，可能存在着两类不同性质的实时任务，即HRT任务和SRT任务，它们都联系着一个截止时间。为保证系统能正常工作，实时调度必须能满足实时任务对截止时间的要求。为此，实现实时调度应具备一定的条件。

实现实时调度的基本条件

提供必要的信息

  为了实现实时调度，系统应向调度程序提供有关任务的信息：
  (1)就绪时间，是指某任务成为就绪状态的起始时间，在周期任务的情况下，它是事先预知的一串时间序列。
  (2)开始截止时间和完成截止时间，对于典型的实时应用，只须知道开始截止时间，或者完成截止时间。
  (3)处理时间，一个任务从开始执行，直至完成时所需的时间。
  (4)资源要求，任务执行时所需的一组资源。
  (5)优先级，如果某任务的开始截止时间错过，势必引起故障，则应为该任务赋予“绝对”优先级；如果其开始截止时间的错过，对任务的继续运行无重大影响，则可为其赋予“相对”优先级，供调度程序参考。

系统处理能力强

  在实时系统中，若处理机的处理能力不够强，则有可能因处理机忙不过，而致使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有 \(m\) 个周期性的硬实时任务HRT，它们的处理时间可表示为 \(C_i\) ，周期时间表示为 \(P_i\) ，则在单处理机情况下，必须满足下面的限制条件系统才是可调度的：

\[ \sum_{i=1}^{m}\frac{C_i}{P_i} \le 1 \tag{6} \]

  顺便说明一下，上述的限制条件并未考虑到任务切换所花费的时间，因此，当利用上述限制条件时，还应适当地留有余地。
  提高系统处理能力的途径有二：一是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；二是采用多处理机系统。假定系统中的处理机数为 \(N\) ，则应将上述的限制条件改为：

\[ \sum_{i=1}^{m}\frac{C_i}{P_i} \le N \tag{7} \]

采用抢占式调度机制

  在含有HRT任务的实时系统中，广泛采用抢占机制。这样便可满足HRT任务对截止时间的要求。但这种调度机制比较复杂。对于一些小的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和在任务调度时所花费的系统开销。在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机，供调度程序去调度那个开始截止时间即将到达的任务。

具有快速切换机制

  为保证硬实时任务能及时运行，在系统中还应具有快速切换机制，使之能进行任务的快速切换。该机制应具有加下两方面的能力：
  (1)对中断的快速响应能力。对紧迫的外部事件请求中断能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机（其它紧迫任务）。
  (2)快速的任务分派能力。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。

实时调度算法的分类

  可以按不同方式对实时调度算法加以分类：①根据实时任务性质，可将实时调度的算法分为硬实时调度算法和软实时调度算法；②按调度方式，则可分为非抢占调度算法和抢占调度算法。

非抢占式调度算法

  (1)非抢占式轮转调度算法。由一台计算机控制若干个相同的（或类似的）对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾等待，调度程序再选择下一个队首任务运行。这种调度算法可获得数秒至数十秒的响应时间，可用于要求不太严格的实时控制系统中。
  (2)非抢占式优先调度算法。如果在系统中还含有少数具有一定要求的实时任务，则可采用非抢占式优先调度算法，系统为这些任务赋予了较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后，便可去调度执行队首的高优先进程。这种调度算法在做了精心的处理后有可能使其响应时间减少到数秒至数百毫秒，因而可用于有一定要求的实时控制系统中。

抢占式调度算法

  可根据抢占发生时间的不同而进一步分成以下两种调度算法：
  (1)基于时钟中断的抢占式优先级调度算法。在某实时任务到达后，如果它的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断发生时，调度程序才剥夺当前任务的执行，将处理机分配给新到的高优先级任务。该算法能获得较好的响应效果，其调度延迟可降为几十至几毫秒，可用于大多数的实时系统中。
  (2)立即抢占(Immediate Preemption)的优先级调度算法。在这种调度策略中，要求操作系统具有快速响应外部事件中断的能力。一旦出现外部中断，只要当前任务未处于临界区，便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。这种算法能获得非常快的响应，可把调度延迟降低到几毫秒至100微秒，甚至更低。图4中的(a)、(b)、(c)、(d)分别示出了四种情况的调度时间。

图4 实时进程调度

最早截止时间优先EDF(Earliest Deadline First)算法

  该算法是根据任务的截止时间确定任务的优先级，任务的截止时间愈早，其优先级愈高，具有最早截止时间的任务排在队列的队首。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机。最早截止时间优先算法既可用于抢占式调度方式中，也可用于非抢占式调度方式中。

非抢占式调度方式用于非周期实时任务

  图5示出了将该算法用于非抢占调度方式之例。该例中具有四个非周期任务，它们先后到达。系统先调度任务1执行，在任务1执行期间，任务2、3又先后到达。由于任务3的开始截止时间早于任务2的，故系统在任务1后将先调度任务3执行。在此期间又到达作业4,其开始截止时间仍是早于任务2的，故在任务3执行完后，系统又先调度任务4执行，最后才调度任务2执行。

图5 EDF算法用于非抢占调度方式

抢占式调度方式用于周期实时任务

  图6示出了将该算法用于抢占调度方式之例。在该例中有两个周期任务，任务A和任务B的周期时间分别为 \(20 \text{ms}\) 和 \(50 \text{ms}\) ，每个周期的处理时间分别为 \(10 \text{ms}\) 和 \(25 \text{ms}\) 。
  图6示出了将最早截止时间（最后期限）优先算法用于抢占调度的示意图。图中的第一行示出了两个任务的到达时间、截止时间和执行时间图。其中任务A的到达时间为 \(0\) 、 \(20 \text{ms}\) 、 \(40 \text{ms}\) ···，任务A的最后期限为 \(20 \text{ms}\) 、 \(40 \text{ms}\) 、 \(60 \text{ms}\) ···，任务B的到达时间为 \(0\) 、 \(50 \text{ms}\) 、 \(100 \text{ms}\) ···，任务B的最后期限为 \(50 \text{ms}\) 、 \(100 \text{ms}\) ···。

图6 最早截止时间优先算法用于抢占调度方式之例

  为了说明通常的优先级调度不能适用于实时系统，该图特增加了第二和第三行。在第二行中，假定任务A具有较高的优先级，所以在t= \(0 \text{ms}\) 时，先调度 \(A_1\) 执行，在 \(A_`\) 完成后(t= \(10 \text{ms}\) )才调度 \(B_1\) 执行。在t= \(20 \text{ms}\) 时，又重新调度 \(A_2\) 执行，在t= \(30 \text{ms}\) 时， \(A_2\) 完成，又调度 \(B_1\) 执行。在t= \(40 \text{ms}\) 时，又调度 \(A_3\) 执行，在t= \(50 \text{ms}\) 时，虽然 \(A_3\) 已完成，但 \(B_1\) 已错过了它的最后期限。这说明利用通常的优先级调度已经失败。第三行与第二行类似，只是假定任务B具有较高的优先级。
  第四行是采用最早截止时间优先算法的时间图。在 \(t=0\) 时， \(A_1\) 和 \(B_1\) 同时到达，由于 \(A_1\) 的截止时间比 \(B_1\) 早，故调度 \(A_1\) 执行。在 \(t=10\) 时， \(A_1\) 完成又调度 \(B_1\) 执行。在 \(t=20\) 时， \(A_2\) 到达，由于 \(A_2\) 的截止时间比 \(B_2\) 早， \(B_1\) 被中断而调度 \(A_2\) 执行。在 \(t=30\) 时， \(A_2\) 完成，又重新调度 \(B_1\) 执行。在 \(t=40\) 时， \(A_3\) 又到达，但 \(B_1\) 的截止时间要比 \(A_3\) 早，仍应让 \(B_1\) 继续执行直到完成( \(t=45\) )，然后再调度 \(A_3\) 执行。在 \(t=55\) 时， \(A_3\) 完成又调度 \(B_2\) 执行。在该例中，利用最早截止时间优先算法可以满足系统的要求。

最低松弛度优先LLF(Least Laxity First)算法

  该算法在确定任务的优先级时，根据的是任务的紧急(或松弛)程度。任务紧急程度愈高，赋予该任务的优先级就愈高，以使之优先执行。例如，一个任务在 \(200 \text{ms}\) 时必须完成，而它本身所需的运行时间是 \(100 \text{ms}\) ,因此调度程序必须在 \(100 \text{ms}\) 之前调度执行，该任务的紧急程度(松弛程度)为 \(100 \text{ms}\) 。又如另一任务在 \(400 \text{ms}\) 时必须完成，它本身需要运行 \(150 \text{ms}\) ,则其松弛程度为 \(250 \text{ms}\) 。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在最前面，调度程序选择队列中的队首任务执行。
  该算法主要用于可抢占调度方式中。假如在一个实时系统中有两个周期性实时任务A和B,任务A要求每 \(20 \text{ms}\) 执行一次，执行时间为 \(10 \text{ms}\) ，任务B要求每 \(50 \text{ms}\) 执行一次，执行时间为 \(25 \text{ms}\) 。由此可知，任务A和B每次必须完成的时间分别为： \(A_1\) 、 \(A_2\) 、 \(A_3\) 、···和 \(B_1\) 、 \(B_2\) 、 \(B_3\) 、···，见图7。为保证不遗漏任何一次截止时间，应采用最低松弛度优先的抢占调度策略。

图7 A和B任务每次必须完成的时间

  在刚开始时( \(t_1=0\) )， \(A_1\) 必须在 \(20 \text{ms}\) 时完成，而它本身运行又需 \(10 \text{ms}\) ，可算出A1的松弛度为 \(10 \text{ms}\) 。 \(B_1\) 必须在 \(50 \text{ms}\) 时完成，而它本身运行就需 \(25 \text{ms}\) ，可算出 \(B_1\) 的松弛度为为 \(25 \text{ms}\) ，故调度程序应先调度 \(A_1\) 执行。在 \(t_2=10 \text{ms}\) 时， \(A_2\) 的松弛度可按下式算出：

\[ \begin{aligned} A2的松弛度=&必须完成时间-其本身的运行时间-当前时间\\ =&40 \text{ms} - 10 \text{ms} - 10 \text{ms} = 20 \text{ms} \end{aligned} \tag{8} \]

  类似地，可算出 \(B_1\) 的松弛度为 \(15 \text{ms}\) ,故调度程序应选择 \(B_1\) 运行。在 \(t_3 = 30 \text{ms}\) 时， \(A_2\) 的松弛度已减为 \(0\) （即 \(40-10-30\) ），而 \(B_1\) 的松弛度为 \(15 \text{ms}\) （即 \(50-5-30\) ），于是调度程序应抢占 \(B_1\) 的处理机而调度 \(A_2\) 运行。在 \(Q = 40 \text{ms}\) 时， \(A_3\) 的松弛度为 \(10 \text{ms}\) （即 \(60-10-40\) ），而 \(B_1\) 的松弛度仅为 \(5 \text{ms}\) （即 \(50-5-40\) ），故又应重新调度为执行。在\(t_5 = 45 \text{ms}\) 时， \(B_1\) 执行完成，而此时 \(A_3\) 的松弛度已减为 \(5 \text{ms}\) （即 \(60-10-45\) ），而 \(B_2\) 的松弛度为 \(30 \text{ms}\) （即 \(100-25-45\) ），于是又应调度 \(A_3\) 执行。在\(t_6 = 55 \text{ms}\) 时，任务A尚未进入第4周期，而任务B已进入第2周期，故再调度 \(B_2\) 执行。在 \(t_7 = 70 \text{ms}\) 时， \(A_4\) 的松弛度已减至 \(0 \text{ms}\) （即 \(80-10-70\) ），而 \(B_2\) 的松弛度为 \(20 \text{ms}\) （即 \(100-10-70\) ），故此时调度程序又应抢占 \(B_2\) 的处理机而调度 \(A_4\) 执行。图8示出了具有两个周期性实时任务的调度情况。

图8 利用LLF算法进行调度的情况

优先级倒置(priority inversion problem)

优先级倒置的形成

  当前OS广泛采用优先级调度算法和抢占方式，然而在系统中存在着影响进程运行的资源而可能产生“优先级倒置”的现象，即高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞。我们通过一个例子来说明该问题。假如有三个完全独立的进程 \(P_1\) 、 \(P_2\) 和 \(P_3\) ， \(P_1\) 的优先级最高， \(P_2\) 次之， \(P_3\) 最低。 \(P_1\) 和 \(P_3\) 通过共享的一个临界资源进行交互。下面是一段代码：
   \(P_1\) ：... P(mutex); CS-1; V(mutex); ...
   \(P_2\) ：... program2 ...
   \(P_3\) ：... P(mutex); CS-3; V(mutex); ...
  假如 \(P_3\) 最先执行，在执行了P(mutex)操作后，进入到临界区CS-3。在时刻 \(a\) ， \(P_2\) 就绪，因为它比 \(P_3\) 的优先级高， \(P_2\) 抢占了 \(P_3\) 的处理机而运行，如图3-10所示。在时刻 \(b\) ， \(P_1\) 就绪，因为它又比 \(P_2\) 的优先级高， \(P_1\) 抢占了 \(P_2\) 的处理机而运行。在时刻 \(c\) ， \(P_1\) 执行P(mutex)操作，试图进入临界区CS-1，但因为相应的临界资源已被 \(P_3\) 占用，故 \(P_1\) 将被阻塞。由 \(P_2\) 继续运行，直到时刻 \(d\) 运行结束。然后由 \(P_3\) 接着运行，到时刻 \(e\) 时 \(P_3\) 退出临界区，并唤醒 \(P_1\) 。因为它比 \(P_3\) 的优先级高，故它抢占了 \(P_3\) 的处理机而运行。
  根据优先级原则，高优先级进程应当能优先执行，但在此例中， \(P_1\) 和 \(P_3\) 共享着“临界资源”，而出现了不合常理的现象，高优先级进程 \(P_1\) 因 \(P_3\) 进程被阻塞了，又因为 \(P_2\) 进程的存在而延长了 \(P_1\) 被阻塞的时间，而且被延长的时间是不可预知和无法限定的。由此所产生的“优先级倒置”的现象是非常有害的，它不应出现在实时系统中。

图9 优先级倒置示意图

优先级倒置的解决办法

  一种简单的解决方法是规定：假如进程 \(P_3\) 在进入临界区后 \(P_3\) 所占用的处理机就不允许被抢占。由图9可以看出， \(P_2\) 即使优先级高于 \(P_3\) 也不能执行。于是 \(P_3\) 就有可能会较快地退出临界区，不会出现上述情况。如果系统中的临界区都较短且不多，该方法是可行的。反之，如果 \(P_3\) 临界区非常长，则高优先级进程 \(P_1\) 仍会等待很长的时间，其效果是无法令人满意的。
  一个比较实用的方法是建立在动态优先级继承基础上的。该方法规定，当高优先级进程 \(P_1\) 要进入临界区，去使用临界资源 \(R\) ，如果已有一个低优先级进程 \(P_3\) 正在使用该资源，此时一方面 \(P_1\) 被阻塞，另一方面由 \(P_3\) 继承 \(P_1\) 的优先级，并一直保持到 \(P_3\) 退出临界区。这样做的目的在于不让比 \(P_3\) 优先级稍高，但比 \(P_1\) 优先级低的进程如 \(P_2\) 进程插进来，导致延缓 \(P_3\) 退出临界区。图10示出了采用动态优先级继承方法后， \(P_1\) 、 \(P_2\) 、 \(P_3\) 三个进程的运行情况。由图可以看出，在时刻 \(c\) ， \(P_1\) 被阻塞，但由于 \(P_3\) 已继承了 \(P_1\) 的优先级，它比 \(P_2\) 优先级高，这样就避免了 \(P_2\) 的插入，使 \(P_1\) 在时刻 \(d\) 进入临界区。该方法已在一些操作系统中得到应用，而在实时操作系统中是必须的。

图10 采用了动态优先级继承方法的运行情况

死锁概述

  在第二章中，我们已经涉及到死锁的概念。例如，系统中只有一台扫描仪 \(R_1\) 和一台刻录机 \(R_2\) 。有两个进程 \(P_1\) 和 \(P_2\) ，它们都准备将扫描的文挡刻录到CD光盘上，进程 \(P_1\) 先请求扫描仪 \(R_1\) 并获得成功，进程 \(P_2\) 先请求CD刻录机 \(R_2\) 也获得成功。后来 \(P_1\) 又请求CD刻录机，因它已被分配给了 \(P_2\) 而阻塞。 \(P_2\) 又请求扫描仪，也因被分配给了 \(P_1\) 而阻塞，此时两个进程都被阻塞，双方都希望对方能释放出自己所需要的资源，但它们谁都因不能获得自己所需的资源去继续运行，从而无法释放出自己占有的资源，并且一直处于这样的僵持状态而形成死锁。又如，在哲学家进餐问题中，如果每一个哲学家因饥饿都拿起了他们左边的筷子，当每一个哲学家又试图去拿起他们右边的筷子时，将会因无筷子可拿而无限期地等待，从而产生死锁问题。在本篇的后半部分，我们将对死锁发生的原因、如何预防和避免死锁等问题作较详细的介绍。

资源问题

  在系统中有许多不同类型的资源，其中可以引起死锁的主要是，需要采用互斥访问方法的、不可以被抢占的资源，即在前面介绍的临界资源。系统中这类资源有很多，如打印机、数据文件、队列、信号量等。

可重用性资源和消耗性资源

1. 可重用性资源

  可重用性资源是一种可供用户重复使用多次的资源，它具有如下性质：
  (1)每一个可重用性资源中的单元只能分配给一个进程使用，不允许多个进程共享。
  (2)进程在使用可重用性资源时，须按照这样的顺序：①请求资源。如果请求资源失败，请求进程将会被阻塞或循环等待。②使用资源。进程对资源进行操作，如用打印机进行打印；③释放资源。当进程使用完后自己释放资源。
  (3)系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能 创建也不能删除它。
  对资源的请求和释放通常都是利用系统调用来实现的，例如对于设备，一般用request/release；对于文件，可用open/close。对于需要互斥访问的资源，进程可以用信号量的wait/signal操作来完成。进程在每次提出资源请求后，系统在执行时都需要做一系列的工作。计算机系统中大多数资源都属于可重用性资源。

2. 可消耗性资源

  可消耗性资源又称为临时性资源，它是在进程运行期间，由进程动态地创建和消耗的，它具有如下性质：①每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，有时它可以有许多，有时可能为0。②进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目。③进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中。可消耗性资源通常是由生产者进程创建，由消费者进程消耗。最典型的可消耗性资源就是用于进程间通信的消息等。

可抢占性资源和不可抢占性资源

1. 可抢占性资源

  可把系统中的资源分成两类，一类是可抢占性资源，是指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占。例如优先级高的进程可以抢占优先级低的进程的处理机。又如可把一个进程从一个存储区转移到另一个存储区，在内存紧张时，还可将一个进程从内存调出到外存上，即抢占该进程在内存的空间。可见，CPU和主存均属于可抢占性资源。对于这类资源是不会引起死锁的。

2. 不可抢占性资源

  另一类资源是不可抢占性资源，即一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。例如，当一个进程已开始刻录光盘时，如果突然将刻录机分配给另一个进程，其结果必然会损坏正在刻录的光盘，因此只能等刻好光盘后由进程自己释放刻录机。另外磁带机、打印机等也都属于不可抢占性资源。

计算机系统中的死锁

  死锁的起因，通常是源于多个进程对资源的争夺，不仅对不可抢占资源进行争夺时会引起死锁，而且对可消耗资源进行争夺时，也会引起死锁。

竞争不可抢占性资源引起死锁

  通常系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。例如，系统中有两个进程 \(P_1\) 和 \(P_2\) ，它们都准备写两个文件 \(F_1\) 和 \(F_2\) ，而这两者都属于可重用和不可抢占性资源。进程 \(P_1\) 先打开 \(F_1\) ，然后再打开文件 \(F_2\) ；进程 \(P_2\) 先打开文件 \(F_2\) ，后打开 \(F_1\) ，下面示出了这段代码。
   \(P_1\) ：···Open(f1,w); Open(f2,w);···
   \(P_2\) ：···Open(f2.w); Open(f1,w);···
  两个进程 \(P_1\) 和 \(P_2\) 在并发执行时，如果 \(P_1\) 先打开 \(F_1\) 和 \(F_2\) ，然后 \(P_2\) 才去打开 \(F_1\) （或 \(F_2\) ）,由于文件 \(F_1\) （ \(F_2\) ）已被 \(P_1\) 打开，故 \(P_2\) 会被阻塞。当 \(P_1\) 写完文件 \(F_1\) （或 \(F_2\) ）而关闭 \(F_1\) （ \(F_2\) ）时， \(P_2\) 会由阻塞状态转为就绪状态，被调度执行后重新打开文件 \(F_1\) （或 \(F_2\) ）。在这种情况下， \(P_1\) 和 \(P_2\) 都能正常运行下去。若 \(P_2\) 先打开 \(F_1\) 和 \(F_2\) ，然后 \(P_1\) 才去打开 \(F_1\) （或 \(F_2\) ）， \(P_1\) 和 \(P_2\) 同样也可以正常运行下去。
  但如果在 \(P_1\) 打开 \(F_1\) 的同时， \(P_2\) 去打开 \(F_2\) ，每个进程都占有一个打开的文件，此时就可能出现问题。因为当 \(P_1\) 试图去打开 \(F_2\) ，而 \(P_2\) 试图去打开 \(F_1\) 时，这两个进程都会因文件 已被打开而阻塞，它们希望对方关闭自己所需要的文件，但谁也无法运行，因此这两个进程将会无限期地等待下去，而形成死锁。
  我们可将上面的问题利用资源分配图进行描述，用方块代表可重用的资源（文件），用圆圈代表进程，见图11所示。当箭头从进程指向文件时，表示进程请求资源（打开文件）；当箭头从资源指向进程时，表示该资源已被分配给该进程（已被进程打开）。从中可以看出，这时在 \(P_1\) 、 \(P_2\) 及 \(F_1\) 和 \(F_2\) 之间，已经形成了一个环路，说明已进入死锁状态。

图11 共享文件时的死锁情况

竞争可消耗资源引起死锁

  现在进一步介绍竞争可消耗资源所引起的死锁。图12示出了在三个进程之间，在利用消息通信机制进行通信时所形成的死锁情况。图中， \(m_1\) 、 \(m_2\) 和 \(m_3\) 是可消耗资源。进程 \(P_1\) 一方面产生消息 \(m_1\) ，利用send(p2,m1)原语将它发送给 \(P_2\) ；另一方面，它又要求从 \(P_3\) 接收消息。而进程 \(P_2\) 一方面产生消息 \(m_2\) ，利用send(p3,m2)原语将它发送给 \(P_3\) ；另一方面，它又需要接收进程 \(P_1\) 所产生的消息 \(m_1\) 。类似地，进程 \(P_3\) 也产生消息 \(m_3\) ，利用send(P1,m3)原语将它发送给 \(P_1\) ，而它又要求从进程 \(P_2\) 接收其所产生的消息 \(m_2\) 。如果三个进程间的消息通信，则按下述顺序进行：
   \(P_1\) ：···send(p2,m1);receive(p3,m3);···
   \(P_2\) ：···send(p3,m2);receive(p1,m1);···
   \(P_3\) ：···send(p1,m3);receive(p2,m2);···
  这三个进程都可以先将消息发送给下一个进程，相应地它们也都能够接收到从上一个进程发来的消息，因此三个进程可以顺利地运行下去，而不会发生死锁。但若改成三个进程都先执行receive操作，后执行send操作，即按下述的运行顺序：
   \(P_1\) ：···receive(p3,m3);send(p2,m1);···
   \(P_2\) ：···receive(p1,m1);send(p3,m2);···
   \(P_3\) ：···receive(p2,m2);send(p1,m3);···
  则这三个进程就会永远阻塞在它们的receive操作上，等待一条永远不会发出的消息，于是发生了死锁。

图12 进程之间通信时的死锁

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

  除了系统中多个进程对资源的竞争会引发死锁外，进程在运行过程中，对资源进行申请和释放的顺序是否合法，也是在系统中是否会产生死锁的一个重要因素。例如，系统中只有一台打印机 \(R_1\) 和一台磁带机 \(R_2\) ，可供进程 \(P_1\) 和 \(P_2\) 共享，由于进程在运行中具有异步性特征，这就可能使 \(P_1\) 和 \(P_2\) 两个进程按下述两种顺序向前推进。

1. 进程推进顺序合法

  在进程 \(P_1\) 和 \(P_2\) 并发执行时，如果按图13中的曲线①所示的顺序推进:：P1:Request(R1)→P1:Request(R2)→P1:Release(R2)→P1:Release(R2)→P2:Request(R2)→P2:Request(R1)→P2:Release(R2)→P2:Release(R1)，两个进程可顺利完成。类似地，若按图中曲线②和③所示的顺序推进，两进程也可以顺利完成。我们称这种不会引起进程死锁的推进顺序是合法的。

2. 进程推进顺序非法

  若并发进程 \(P_1\) 和 \(P_2\) 按图13中曲线④所示的顺序推进，它们将进入不安全区 \(D\) 内。此时 \(P_1\) 保持了资源 \(R_1\) ， \(P_2\) 保持了资源 \(R_2\) ，系统处于不安全状态。此刻，如果两个进程继续向前推进，就可能发生死锁。例如，当 \(P_1\) 运行到P1:Request(R2)时，将因 \(R_2\) 已被 \(P_2\) 占用而阻塞：当 \(P_2\) 运行到P2:Request(R1)时，也将因 \(R_1\) 已被 \(P_1\) 占用而阻塞，于是发生了进程死锁，这样的进程推进顺序就是非法的。

图13 进程推进顺序对死锁的影响

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

死锁的定义

  在一组进程发生死锁的情况下，这组死锁进程中的每一个进程，都在等待另一个死锁进程所占有的资源。或者说每个进程所等待的事件是该组中其它进程释放所占有的资源。但由于所有这些进程己都无法运行，因此它们谁也不能释放资源，致使没有任何一个进程可被唤醒。这样这组进程只能无限期地等待下去。由此可以给死锁做出如下的定义：
  如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的(Deadlock)。

产生死锁的必要条件

  虽然进程在运行过程中可能会发生死锁，但产生进程死锁是必须具备一定条件的。综上所述不难看出，产生死锁必须同时具备下面四个必要条件，只要其中任一个条件不成立, 死锁就不会发生：
  (1)互斥条件。进程对所分配到的资源进行排它性使用，即在一段时间内，某资源只能被一个进程占用。如果此时还有其它进程请求该资源，则请求进程只能等待，直至占有该资源的进程用毕释放。
  (2)请求和保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
  (3)不可抢占条件。进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放。
  (4)循环等待条件。在发生死锁时，必然存在一个进程一资源的循环链，即进程集合 \(\set{P_0,P_1,P_2,\cdots,P_n}\) 中的 \(P_0\) 正在等待一个 \(P_1\) 占用的资源， \(P_1\) 正在等待 \(P_2\) 占用的资源，···， \(P_n\) 正在等待已被 \(P_0\) 占用的资源。

处理死锁的方法

  目前处理死锁的方法可归结为四种：
  (1)预防死锁。这是一种较简单和直观的事先预防方法。该方法是通过设置某些限制条件，去破坏产生死锁四个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较 易实现的方法，已被广泛使用。
  (2)避免死锁。同样是属于事先预防策略，但它并不是事先采取各种限制措施，去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。
  (3)检测死锁。这种方法无须事先采取任何限制性措施，允许进程在运行过程中发生死锁。但可通过检测机构及时地检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来。
  (4)解除死锁。当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用的方法是撤消一些进程，回收它们的资源，将它们分配给己处于阻塞状态的进程，使其能继续运行。
  上述的四种方法，从(1)到(4)对死锁的防范程度逐渐减弱，但对应的是资源利用率的提高，以及进程因资源因素而阻塞的频度下降（即并发程度提高）。

预防死锁

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

破坏“请求和保持”条件

  为了能破坏“请求和保持”条件，系统必须保证做到：当一个进程在请求资源时，它不能持有不可抢占资源。该保证可通过如下两个不同的协议实现：

第一种协议

  该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。此时若系统有足够的资源分配给某进程，便可把其需要的所有资源分配给它。这样，该进程在整个运行期间，便不会再提出资源要求，从而破坏了“请求”条件。系统在分配资源时，只要有一种资源不能满足进程的要求，即使其它所需的各资源都空闲也不分配给该进程，而让该进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件，从而可以预防死锁的发生。
  第一种协议的优点是简单、易行且安全。但缺点也极其明显：
  (1)资源被严重浪费，严重地恶化了资源的利用率。进程在开始运行时就一次性地占用了整个运行过程所需的全部资源，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。
  (2)使进程经常会发生饥饿现象。因为仅当进程在获得了其所需的全部资源后才能开始运行，这样就可能由于个别资源长期被其它进程占用，而致使等待该资源的进程迟迟不能开始运行，而个别资源有可能仅在进程运行到最后才需要，如打印机往往就是如此。

第二种协议

  该协议是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。我们可以通过一个具体例子来说明，第二种协议比第一种协议要好。例如有一个进程，它所要完成的任务是，先将数据从磁带上复制到磁盘文件上，然后对磁盘文件进行排序，最后把结果打印出来。在采用第一种协议时，进程必须在开始时就请求磁带机、磁盘文件和打印机。然而打印机仅在最后才会用到，既影响到其利用率，还会影响到其它进程的运行。此外，又如磁带机和磁盘文件虽然空闲，但因打印机已分配给其它进程，因而进程还需要等待。
  在采用第二种协议时，进程在开始时只需请求磁带机、磁盘文件，然后就可运行。等到全部磁带上的数据已复制到磁盘文件中并已排序好后，便可将磁带机和磁盘文件释放掉，再去请求磁盘文件和打印机。这不仅能使进程更快地完成任务，提高设备的利用率，还可减少进程发生饥饿的机率。

破坏“不可抢占”条件

  为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已占有的资源会被暂时地释放，或者说是被抢占了，从而破坏了“不可抢占”条件。
  该方法实现起来比较复杂，且需付出很大的代价。因为一个不可抢占的资源如打印机、CD刻录机等在使用一段时间后被抢占，可能会造成进程前一阶段工作的失效，即使是采取了某些防范措施，也还会使进程前后两次运行的信息不连续。这种策略还可能因为反复地申请和释放资源致使进程的执行被无限地推迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。

破坏“循环等待”条件

  一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号。设 \(R=(R_1,R_2,R_3,\cdots,R_m)\) 为资源类型的集合，为每个资源类型赋予唯一的序号。如果系统中有磁带驱动器、硬盘驱动器、打印机，则函数 \(F\) 可按如下形式来定义：
   \(F(\text{tape drive})=1\) ；
   \(F(\text{disk drive})=5\) ；
   \(F(\text{printer})=12\) ；
  在对系统所有资源类型进行线性排序后，便可采用这样的预防协议：规定每个进程必须按序号递增的顺序请求资源。一个进程在开始时，可以请求某类资源 \(R_i\) 的单元。以后，当且仅当 \(F(R_j)>F(R_i)\) 时，进程才可以请求资源 \(R_j\) 的单元。如果需要多个同类资源单元，则必须一起请求。例如，当某进程需要同时使用打印机和磁带机时，由于磁带机序号低，而打印机序号高，故必须先请求磁带机，再请求打印机。假如某进程已请求到一些序号较高的资源，后来它又想请求一个序号低的资源时，它必须先释放所有具有相同和更高序号的资源后，才能申请序号低的资源。在采用这种策略后所形成的资源分配图中，不可能再出现环路，因而破坏了“循环等待”条件。事实上，总有一个进程占据了较高序号的资源，此后它继续申请的资源必然是空闲的，因而进程可以一直向前推进。
  在采用这种策略时，应如何来规定每种资源的序号是十分重要的。通常应根据大多数进程需要资源的先后顺序来确定。一般情况下，进程总是先输入程序和数据，继而进行运算，最后将计算结果输出。故可以为输入设备规定较低的序号，如前面是将磁带机定为 \(1\) ；为输出设备规定较高的序号，如把打印机定为 \(12\) 。
  这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量都有较明显的改善。但也存在下述问题：首先，为系统中各类资源所规定的序号必须相对稳定，这就限制了新类型设备的增加；其次，尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况：作业使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。第三，为方便用户，系统对用户在编程时所施加的限制条件应尽量少，然而这种按规定次序申请资源的方法必然会限制用户简单、自主地编程。

避免死锁

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

系统安全状态

  在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。

安全状态

  在该方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，才可将资源分配给进程，否则，令进程等待。所谓安全状态，是指系统能按某种进程推进顺序 \((P_1,P_2,\cdots,P_n)\) 为每个进程 \(P_i\) 分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称 \((P_1,P_2,\cdots,P_n)\) 为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。虽然并非所有不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，就有可能进入死锁状态。反之，只要系统处于安全状态，系统便不会进入死锁状态。因此，避免死锁的实质在于，系统在进行资源分配时，，应使系统不进入不安全状态。

安全状态之例

  假定系统中有三个进程 \(P_1\) 、 \(P_2\) 和 \(P_3\) ，共有 \(12\) 台磁带机。进程 \(P_1\) 总共要求 \(10\) 台磁带机， \(P_2\) 和 \(P_3\) 分别要求 \(4\) 台和 \(9\) 台。假设在 \(T_0\) 时刻，进程 \(P_1\) 、 \(P_2\) 和 \(P_3\) 已分别获得 \(5\) 台、 \(2\) 台和 \(2\) 台磁带机，尚有 \(3\) 台空闲未分配，如下表所示：

表2

  经分析发现，在 \(T_0\) 时刻系统是安全的，因为这时存在一个安全序列 \((P_2,P_1,P_3)\) ，即只要系统按此进程序列分配资源，就能使每个进程都顺利完成。例如将剩余的磁带机取 \(2\) 台分配给 \(P_2\) ，使之继续运行，待 \(P_2\) 完成便可释放出 \(4\) 台磁带机，于是可用资源增至 \(5\) 台；以后再将这些全部分配给进程 \(P_1\) 使之运行，待 \(P_1\) 完成后，将释放出 \(10\) 台磁带机， \(P_3\) 便能获得足够的资源，从而使 \(P_1\) 、 \(P_2\) 、 \(P_3\) 每个进程都能顺利完成。

由安全状态向不安全状态的转换

  如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如在 \(T_0\) 时刻以后 \(P_3\) 又请求 \(1\) 台磁带机，若此时系统把剩余 \(3\) 台中的 \(1\) 台分配给 \(P_3\) ,则系统便进入不安全状态。因为此时也无法再找到一个安全序列。例如把其余的 \(2\) 台分配给 \(P_2\) ,这样在 \(P_2\) 完成后，只能释放出 \(4\) 台，既不能满足 \(P_1\) 尚需 \(5\) 台的要求，也不能满足 \(P_3\) 需要 \(6\) 台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，结果导致死锁。类似地，如果我们将剩余的 \(2\) 台磁带机先分配给 \(P_1\) 或 \(P_3\) ,也同样都无法使它们推进到完成，因此从 给 \(P_3\) 分配了第3台磁带机开始，系统便又进入了不安全状态。
  在建立了系统安全状态的概念后，便可知道避免死锁的基本思想，就是确保系统始终处于安全状态。一个系统开始是处于安全状态的。当有进程请求一个可用资源时，系统需对该进程的请求进行计算，若将资源分配给进程后系统仍处于安全状态，才将该资源分配给进程。在上面的例子中，在 \(P_3\) 请求 \(1\) 台磁带机时，尽管系统中有可用的磁带机，但却不 能分配给它。必须等待到P1和 \(P_2\) 完成并释放出资源后再将足够的资源分配给 \(P_3\) 。

利用银行家算法避免死锁

  最有代表性的避免死锁的算法是Dijkstra的银行家算法。起这样的名字是由于该算法原本是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS中也可用它来实现避免死锁。
  为实现银行家算法，每一个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。

银行家算法中的数据结构

  为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
  (1)可利用资源向量 \(\text{Available}\) 。这是一个含有 \(m\) 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 \(\text{Available}[j]=K\) ，则表示系统中现有 \(R_j\) 类资源 \(K\) 个。
  (2)最大需求矩阵 \(\text{Max}\) 。这是一个 \(n \times m\) 的矩阵，它定义了系统中 \(n\) 个进程中的每一个进程对 \(m\) 类资源的最大需求。如果 \(\text{Max}[i,j]=K\) ，则表示进程 \(i\) 需要 \(R_j\) 类资源的最大数目为 \(K\) 。
  (3)分配矩阵 \(\text{Allocation}\) 。这也是一个 \(n \times m\) 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 \(\text{Allocation}[i,j]=K\) ，则表示进程 \(i\) 当前已分得 \(R_j\) 类资源的数目为 \(K\) 。
  (4)需求矩阵 \(\text{Need}\) 。这也是一个 \(n \times m\) 的矩阵，用以表示每一个进程尚需的各类资源数。如果 \(\text{Need}[i,j]=K\) ，则表示进程 \(i\) 还需要 \(R_j\) 类资源 \(K\) 个方能完成其任务。
  上述三个矩阵间存在下述关系：

\[ \text{Need}[i,j] = \text{Max}[i,j] - \text{Allocation}[i,j] \tag{9} \]

银行家算法

  设 \(\text{Request}_i\) 是进程 \(P_i\) 的请求向量，如果 \(\text{Request}_i[j]=K\) ，表示进程 \(P_i\) 需要 \(K\) 个 \(R_j\) 类型的资源。当 \(P_i\) 发出资源请求后，系统按下述步骤进行检查：
  (1)如果 \(\text{Request}_i[j] \le \text{Need}[i,j]\) ，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
  (2)如果 \(\text{Request}_i[j] \le \text{Available}[i,j]\) ，便转向步骤(3)；否则，表示尚无足够资源， \(P_i\) 须等待。
  (3)系统试探着把资源分配给进程 \(P_i\) ，并修改下面数据结构中的数值：
   \(\text{Available}[j]=\text{Available}[j]-Request_i[j];\)
   \(\text{Allocation}[i,j]=\text{Allocation}[i,j]+\text{Request}_i[j];\)
   \(\text{Need}[i,j]=\text{Need}[i,j]-\text{Request}_i[j];\)
  (4)系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 \(P_i\) ，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 \(P_i\) 等待。

安全性算法

  系统所执行的安全性算法可描述如下：
  (1)设置两个向量：①工作向量 \(\text{Work}\) ，它表示系统可提供给进程继续运行所需的各类资源数目，它含有 \(m\) 个元素，在执行安全算法开始时， \(\text{Work}=\text{Available}\) ；② \(\text{Finish}\) ：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 \(\text{Finish}[i]=\text{false}\) ；当有足够资源分配给进程时，再令 \(\text{Finish}[i]=\text{true}\) 。
  (2)从进程集合中找到一个能满足下述条件的进程：
  ① \(\text{Finish}[i]=\text{false}\)
  ② \(\text{Need}[i,j]\le \text{Work}[i,j]\)
  若找到，执行步骤(3)；否则，执行步骤(4)。
  (3)当进程 \(P_i\) 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
   \(\text{Work}[j]=\text{Work}[j]+\text{Allocation}[i,j];\)
   \(\text{Finish}[i]=\text{true}\) 。
   \(\text{go to step 2}\) 。
  (4)如果所有进程的 \(\text{Finish}[i]=\text{true}\) 都满足，则表示系统处于安全状态；否则，系统处于不安全状态。