操作系统6：处理机的任务调度和进程调度

拼搏现实的明天。 2024-03-16 20:58 71阅读 0赞

**目录**

1、处理机调度的层次

（1）高级调度(High Level Scheduling)

（2）低级调度(Low Level Scheduling)

（3）中级调度(Intermediate Scheduling)

2、处理机调度算法的目标

批处理系统的目标

3、作业与作业调度

（1）批处理系统中作业

（2）先来先服务（first-comefirst-served，FCFS）调度算法

（3）短作业优先（shortjob first，SJF）的调度算法

（4）优先级调度算法（priority-scheduling algorithm，PSA）

（5）高响应比优先调度算法（Highest Response Ratio Next，HRRN）

4、进程调度

（1）进程调度的任务和机制

（2）进程调度的方式

（3）轮转调度算法

（4）优先级调度算法

（5）多队列调度算法

（6）多级反馈队列（multileved feedback queue）调度算法

（7）基于公平原则的调度算法

--------------------

在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。// 资源分配

### 1、处理机调度的层次 ###

#### （1）高级调度(High Level Scheduling) ####

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

#### （2）低级调度(Low Level Scheduling) ####

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

#### （3）中级调度(Intermediate Scheduling) ####

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

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

### 2、处理机调度算法的目标 ###

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

![f7c1fd571d494008a5f46f593b6475f7.png][]

（2）公平性：公平性是指应使诸进程都获得合理的 CPU 时间，不会发生进程饥饿现象。公平性是相对的，对相同类型的进程应获得相同的服务；但对于不同类型的进程，由于其紧急程度或重要性的不同，则应提供不同的服务。

（3）平衡性。由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于 I/O 型。为使系统中的 CPU 和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。// 平衡 CPU 和 外部设备的使用

（4）策略强制执行。对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

#### 批处理系统的目标 ####

1.  **平均周转时间短**。所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔（作业周转时间）。它包括四部分时间：作业在外存后备队列上等待作业调度的时间，进程在就绪队列上等待进程调度的时间，进程在 CPU 上执行的时间以及进程等待 I/O 操作完成的时间。其中的后三项在一个作业的整个处理过程中，可能发生多次。
2.  **系统吞吐量高**。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度有关。事实上，如果单纯是为了获得高的系统吞吐量，就应尽量多地选择短作业运行。
3.  **处理机利用率高**。对于大、中型计算机，CPU 价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标；而调度方式和算法又对处理机的利用率起着十分重要的作用。如果单纯是为使处理机利用率高，应尽量多地选择计算量大的作业运行。

由上所述可以看出，这些要求之间是存在着一定矛盾的。

### 3、作业与作业调度 ###

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

#### （1）批处理系统中作业 ####

**1 - 作业和作业步**

作业（Job）：作业不仅包含了通常的程序和数据而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。// 作业是一个比程序更为广泛的概念

作业步（Job Step）：通常，在作业运行期间，每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果。我们把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，往往是上一个作业步的输出作为下一个作业步的输入。例如，一个典型的作业可分成：“编译” 作业步，“链接装配” 作业步和 “运行” 作业步。// 编译 -> 装配 -> 运行

**2 - 作业控制块（Job Control Block，JCB）**

为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块 JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。

通常在 JCB 中包含的内容有：作业标识、用户名称、用户账号、作业类型（CPU 繁忙型、I/O 繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、要求内存大小等）、资源使用情况等。

每当一个作业进入系统时，便由 “作业注册” 程序为该作业建立一个作业控制块 JCB 。再根据作业类型，将它放到相应的作业后备队列中等待调度。调度程序依据一定的调度算法来调度它们，被调度到的作业将被装入内存。在作业运行期间，系统就按照 JCB 中的信息和作业说明书对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收已分配给它的资源，撤销该作业控制块。// JCB 的调度过程，类似于进程

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

作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有 “后备状态”、“运行状态” 和 “完成状态”。

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

在批处理系统中，作业进入系统后，总是先驻留在外存的作业后备队列上，因此需要有作业调度，以便将它们分批地装入内存。// 外存 -> 内存

在分时系统中，为了做到及时响应，用户通过键盘输入的命令或数据等都被直接送入内存，因而无需配置上述的作业调度机制，但也需要有某种接纳控制措施来限制进入系统的用户数目。即如果系统尚有能力处理更多的任务，将会接纳授权用户的请求，否则，便拒绝接纳。// 键入

在实时系统中，也不需要作业调度，而必需具有接纳控制措施。

#### （2）先来先服务（first-comefirst-served，FCFS）调度算法 ####

FCFS 是最简单的调度算法，该算法既可用于作业调度，也可用于进程度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。

当在进程调度中采用 FCFS 算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其它进程。// 先进先出

顺便说明，FCFS 算法在单处理机系统中已很少作为主调度算法，但经常把它与其它调度算法相结合使用，形成一种更为有效的调度算法。例如，可以在系统中按进程的优先级设置多个队列，每个优先级一个队列，其中每一个队列的调度都基于 FCFS 算法。

#### （3）短作业优先（shortjob first，SJF）的调度算法 ####

由于在实际情况中，短作业（进程）占有很大比例，为了能使它们能比长作业优先执行而产生了短作业优先调度算法。// 减少作业的平均等待时间

**1 - 短作业优先算法**

SJF 算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF 算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。// 最主要的问题是作业的时间无法准确计算

**2 - 短作业优先算法的缺点**

SJF 调度算法较之 FCFS 算法有了明显的改进，但仍然存在不容忽视的缺点：

*  必须预知作业的运行时间。在采用这种算法时，要先知道每个作业的运行时间。即使是程序员也很难准确估计作业的运行时间，如果估计过低，系统就可能按估计的时间终止作业的运行，但此时作业并未完成，故一般都会偏长估计。// 这一点非常麻烦
 *  对长作业非常不利，长作业的周转时间会明显地增长。更严重的是，该算法完全忽视作业的等待时间，可能使作业等待时间过长，出现饥饿现象。
 *  在采用 FCFS 算法时，人机无法实现交互。
 *  该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。

#### （4）优先级调度算法（priority-scheduling algorithm，PSA） ####

先来先服务调度算法和短作业优先调度算法的两种优先级都不能反映作业的紧迫程度。

在优先级调度算法中，基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法根据该优先级进行调度。

优先级调度算法可以保证紧迫性作业优先运行，它可作为作业调度算法，也可作为进程调度算法。当把该算法用于作业调度时，系统是从后备队列中选择若干个优先级最高的作业装入内存。

#### （5）高响应比优先调度算法（Highest Response Ratio Next，HRRN） ####

在批处理系统中，FCFS 算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。而 SJF 算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。

高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法。因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。// 等待+运行

**高响应比优先算法是如何实现的呢?**

如果为每个作业引入一个动态优先级，使它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可描述为：

![ee9661152b284e48878c2faae9208c54.png][]

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

![a444db10dfd346cba735ebfb89bca54a.png][]

由上式可以看出：

*  如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而类似于 SJF 算法，有利于短作业。
 *  当要求服务的时间相同时，作业的优先权又决定于其等待时间，因而该算法又类似于 FCFS 算法。
 *  对于长作业的优先级，可以随等待时间的增加而提高，当其等待时间足够长时，也可获得处理机。

因此该算法实现了较好的折中。不过在利用该算法时，每次要进行调度之前，都需要先做响应比的计算，显然会增加系统开销。// 计算机系统中的折中思想无处不在

### 4、进程调度 ###

进程调度是 OS 中必不可少的一种调度。它也是对系统性能影响最大的一种 CPU 调度。

#### （1）进程调度的任务和机制 ####

**1 - 进程调度的任务**

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

**2 - 进程调度机制**

为了实现进程调度，在进程调度机制中，应具有如下三个基本部分：

![a2356c3ee56e486e9c2e473908a4c2e8.png][]

排队器。为了提高进程调度的效率，应事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便调度程序能最快地找到它。以后每当有一个进程转变为就绪状态时，排队器便将它插入到相应的就绪队列。

分派器。分派器依据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程。

上下文切换器。在对处理机进行换时，会发生两对上下文的切换操作：

*  第一对上下文切换时，OS 将保存当前进程的上下文，即把当前进程的处理机寄存器内容保存到该进程的进程控制块内的相应单元，再装入分派程序的上下文，以便分派程序运行。// 卸载
 *  第二对上下文切换是移出分派程序的上下文，而把新选进程的 CPU 现场信息装入到处理机的各个相应寄存器中，以便新选进程运行。// 装配

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

#### （2）进程调度的方式 ####

非抢占方式存在着很大的局限性，很难满足交互性作业和实时任务的需求。所以，在进程调度中又引入了抢占方式。

**1 - 非抢占方式（Nonpreemptive Mode）**

在采用这种调度方式时，一旦把处理机分配给某进程后，就一直让它运行下去，绝不会因为时钟中断或任何其它原因去抢占当前正在运行进程的 CPU，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程。

在采用非抢占调度方式时，可能引起进程调度的因素可归结为：

*  正在执行的进程运行完毕，或因发生某事件而使其无法再继续运行
 *  正在执行中的进程因提出 I/O 请求而暂停执行
 *  在进程通信或同步过程中，执行了某种原语操作，如 Block 原语。

这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统。但它不能用于分时系统和大多数实时系统。

**2 - 抢占方式（PreemptiveMode）**

这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。

在现代 OS 中广泛采用抢占方式，这是因为：

*  对于批处理机系统，可以防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更为公平的服务。
 *  在分时系统中，只有采用抢占方式才有可能实现人机交互。
 *  在实时系统中，抢占方式能满足实时任务的需求。

抢占方式比较复杂，所需付出的系统开销也较大。“抢占”不是一种任意性行为，必须遵循一定的原则。主要原则有:

*  优先权原则，指允许优先级高的新到进程抢占当前进程的处理机。
 *  短进程优先原则，指允许新到的短进程可以抢占当前长进程的处理机。
 *  时间片原则，即各进程按时间片轮转运行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度。

#### （3）轮转调度算法 ####

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

**1 - 轮转法的基本原理**

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

**2 - 进程切换时机**

在 RR 调度算法中，应在何时进行进程的切换，可分为两种情况：

*  若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。
 *  在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

**3 - 时间片大小的确定**

在轮转算法中，时间片的大小对系统性能有很大的影响。若选择很小的时间片，将有利于短作业，因为它能在该时间片内完成。但时间片小，意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销。反之，若时间片选择得太长，且为使每个进程都能在一个时间片内完成，RR 算法便退化为 FCFS 算法，无法满足短作业和交互式用户的需求。

一个较为可取的时间片大小是略大于一次典型的交互所需要的时间，使大多数交互式进程能在一个时间片内完成，从而可以获得很小的响应时间。

![56af6a8b3bf148b99fcc6060ffe370be.png][]

下图给出了时间片分别为 q=1 和 q=4 时对平均周转时间的影响。

![460eaebd35df429294f46abf87e4e36e.png][]

// 上例中，当 q=4 时，每个作业都能够在一个时间片内执行完。所以会比 q=1 要好

#### **（4）优先级调度算法** ####

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

**1 - 优先级调度算法的类型**

优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。该算法可分成如下两种：

*  非抢占式优先级调度算法。一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，系统方可将处理机重新分配给另一优先级最高的进程。// 进程不会被抢占
 *  抢占式优先级调度算法。把处理机分配给优先级最高的进程，使之执行。但在其执行期间，只要出现了另一个其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。因此，在采用这种调度算法时，每当系统中出现一个新的就绪进程 i 时，就将其优先级 P(i) 与正在执行的进程 j 的优先级 P(j) 进行比较，如果 P(j) >= P(i)，原进程 j 便继续执行；但如果是 P(j) < P(i)，则立即停止 j 的执行，进行进程切换，使 i 进程投入执行。// 抢占式，当有新进程时，每次都会要进行比较

**2 - 优先级的类型**

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

*  静态优先级：静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的，例如 0~255 中的某一整数，又把该整数称为优先数。确定进程优先级大小的依据有三个：进程类型、进程对资源的需求、用户要求(紧迫程度)。静态优先级法简单易行，系统开销小，但不够精确，可能会出现优先级低的进程长期没有被调度的情况。// 有可能出现进程不被调度或线程饥饿
 *  动态优先级：在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。例如，可以规定在就绪队列中的进程随其等待时间的增长，使其优先级相应提高。若所有的进程都具有相同优先级初值，则最先进入就绪队列的进程会因其优先级变得最高，而优先获得处理机，这相当千 FCFS 算法若所有的就绪进程具有各不相同的优先级初值，那么对于优先级初值低的进程，在等待了足够的时间后，也可以获得处理机。当采用抢占式调度方式时，若再规定当前进程的优先级随运行时间的推移而下降，则可防止一个长作业长期地垄断处理机。

#### （5）多队列调度算法 ####

系统中仅设置一个进程的就绪队列，那么低级调度算法就是固定的、单一的，无法满足系统中不同用户对进程调度策略的不同要求，在多处理机系统中，这种单一调度策略实现机制的缺点更显突出。而多级队列调度算法能够在一定程度上弥补这一缺点。

该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。// 拆分多个对列

多队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。

#### （6）多级反馈队列（multileved feedback queue）调度算法 ####

多级反馈队列调度算法不必事先知道各种进程所需的执行时间，可以较好地满足各种类型进程的需要，所以它是目前公认的一种较好的进程调度算法。

**1 - 调度机制**

多级反馈队列调度算法的调度机制可描述如下：

（1）设置多个就绪队列。在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。该算法为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。例如第二个队列的时间片要比第一个的时间片长一倍，第 i+1个队列的时间片要比第 i 个的时间片长一倍。

下图是多级反馈队列算法的示意图：

![3f6f0acecb094682b009df5ced98b6a9.png][]

（2）每个队列都采用 FCFS 算法。当新进程进入内存后，首先将它放入第一队列的末尾按 FCFS 原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，依此类推。当进程最后被降到第 n 队列后，在第 n 队列中便采取按 RR 方式(时间片轮转)运行。// 进程不断进行队列降级

（3）按队列优先级调度。调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行：换言之，仅当第 1~(i-1) 所有队列均空时，才会调度第 i 队列中的进程运行。如果处理机正在第 i 队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第 i 队列的末尾，而把处理机分配给新到的高优先级进程。

#### （7）基于公平原则的调度算法 ####

**1 - 保证调度算法**

保证调度算法向用户所做出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。

一种比较容易实现的性能保证是处理机分配的公平性。如果在系统中有 n 个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时间 1/n。在实施公平调度算法时系统中必须具有这样一些功能：// 保证每个进程都能公平得分配到 CPU

*  跟踪计算每个进程自创建以来已经执行的处理时间。
 *  计算每个进程应获得的处理机时间，即自创建以来的时间除以 n。
 *  计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比。
 *  比较各进程获得处理机时间的比率。如进程 A 的比率最低，为 0.5，而进程 B 的比率为 0.8，进程 C 的比率为 1.2 等。
 *  调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。

**2 - 公平分享调度算法**

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

[f7c1fd571d494008a5f46f593b6475f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/323c68e513cc44699fca66386cf98ce1.png
[ee9661152b284e48878c2faae9208c54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d9514144aeba4817be2255f358b96a31.png
[a444db10dfd346cba735ebfb89bca54a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7719cda84c0f425089d5f0c5d1736e22.png
[a2356c3ee56e486e9c2e473908a4c2e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0d13c4c0a05c461497af6505651f82f6.png
[56af6a8b3bf148b99fcc6060ffe370be.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/121eb443858c450ca3bf79ab7a9f3e84.png
[460eaebd35df429294f46abf87e4e36e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e8069fbabc0943ff80c50d7f1db10df9.png
[3f6f0acecb094682b009df5ced98b6a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/15cc2de9055b47af9af9d6cf9cf55745.png