进程调度

5.1 基本概念

对于单处理器系统，同一时间只有一个进程可以运行，其他进程都等待，直到CPU空闲并可调度为止。

多道程序的目的是，始终允许某个进程允许以最大化CPU利用率。

当一个进程等待时，操作系统就从该进程接管CPU控制，并将CPU交给另一个进程执行。

操作系统选择进程，并交给CPU执行。

5.1.1 CPU、IO执行周期

进程执行包括周期进程CPU执行和IO等待。进程在这两个状态之间不断交替。

下图是一个CPU执行和IO执行交替执行的例子

不过更多的情况可能IO执行并没有这么多，也不一定是一直与CPU执行交替的。

IO执行频繁的是IO密集型进程，CPU执行频繁的是CPU密集型进程。

通常IO密集型程序具有大量短CPU执行。CPU密集程序可能只有少量长CPU执行。

CPU密集型进程对CPU的利用率高，IO密集型进程由于要等待IO，对CPU的利用率没那么高。

5.1.2 CPU调度程序

每当CPU空闲时，操作系统就应该从就绪队列选择一个进程来执行。

进程选择采用短期调度程序或CPU调度程序。调度程序从内存中选择一个能够执行的进程，并为其分配CPU。如何选择进程是根据调度算法决定的。

就绪队列不一定是FIFO队列。

就绪队列中的所有进程都要排队以便等待在CPU上运行。队列内的记录通常为进程控制块PCB。

5.1.3 抢占调度

需要进行CPU调度的情况有四种： 当一个进程从运行状态切换到等待状态时（如IO请求）此时进程放弃CPU的使用权。

当一个进程从运行状态切换到就绪状态（如中断）进程的时间片结束，CPU执行下一个进程。

当一个进程从等待状态切换到就绪状态，此时CPU可以执行该进程

当一个进程终止时

如果调度只能发生在第一种和第四种情况下，调度方案就是非抢占的，只要给了进程CPU，CPU就会一直执行该进程，直到进程终止；否则就是抢占的。

例如一个优先级较高的进程可能会抢占一个正在被CPU执行的优先级低的进程的CPU执行权。

5.1.4 调度程序

调度程序是一个模块，用来讲CPU控制器交给短期调度程序选择的进程。功能包括

切换上下文

切换到用户模式

跳转到用户程序的合适位置，以便重启程序。

调度程序应尽可能快，因为在每次进程切换时都要使用。调度程序停止一个进程而启动另一个进程所需的时间就是调度延迟。

5.2 调度准则

不同的调度算法具有不同的特点，选择一个特定的算法对某些特定的进程更为有利。

为了比较CPU调度算法，可以采用许多比较准则。选择哪些特征来比较，对于确定那种算法是最好的有本质上的区别。这些准则包括：

CPU使用率：应使CPU尽可能忙碌。CPU使用率0-100%，范围应该从40%（轻负荷系统）到90%（重负荷系统）

吞吐量：在一个单位时间内进程完成的数量

周转数量：从进程提交到进程完成的时间段称为周转时间。周转时间为所有时间段之和，包括等待进程内存、在就绪队列等待、在CPU执行、IO执行等

等待时间：在就绪队列中等待所花时间之和

响应时间：从提交请求到产生第一响应所需的时间，是开始响应的时间，而非输出相应的时间。

总之就是需要最大化CPU使用率和吞吐量 最小化周转时间、等待时间和响应时间。

5.3 调度算法

CPU调度处理的问题是：从就绪队列中选择进程以便为其分配CPU。那么按照怎样的策略和方式选择进程，就是调度算法需要处理的问题。

5.3.1 先到先服务调度

最佳你的的CPU调度算法是先到先服务（FCFS）调度算法。采用这种方案，先请求CPU的进程先分配到CPU。可以通过FIFO（先进先出）队列容易地实现。

当一个进程进入就绪队列时，它的PCB会被链接到队列尾部。当CPU空闲时，它会分配给位于队列头部的进程，并且这个运行进程从队列中移除。

优点：算法非常简单

缺点：平均等待时间往往很长

假设有下面三个进程

如果采用FCFS调度算法，该算法是非抢占的。一旦CPU分配给了一个进程，改进程就会一直占用CPU直到释放CPU。如图p2和p3的等待时间特别长，p1等待时间为0，p2等待时间为24ms，p3等待时间为27ms，平均等待时间是17ms。但是如果按照p2，p3.p1的顺序执行，平均等待时间就是3ms。因此FCFS的平均等待时间通常不是最小，而且如果进程的CPU执行时间变化很大，平均等待时间的变化也会很大。

5.3.2 最短作业优先调度

最短作业优先（SJF）调度算法讲每个进程与其下一次CPU执行的长度关联起来。当CPU空闲时，它会被赋给最短CPU执行的进程。

SJF也叫最短下次CPU执行算法，因为调度取决于进程的下次CPU执行的长度，而不是其总的长度。

可以看出这样调度进程，进程的平均等待时间是最短的。

优点：SJF算法是最优的，因为平均等待时间是最短的，即CPU更忙碌。短进程等待时间减少，长进程等待时间增加，从而平均等待时间减少。

如何知道下次CPU执行长度？

对于批处理系统的长期调度，可以将用户提交作业时指定的进程时限作为长度。SJF调度经常用于长期调度。

SJF算法不能在短期CPU调度上加以实现，因为没法知道下次CPU执行的长度。一种方法是试图近似SJF调度，即预测下次CPU执行长度，可以认为下次CPU执行长度与之前的相似，例如进程执行到中断的时间可能会被下次执行作为预估的CPU执行长度。

SJF可以是抢占式的或非抢占式的。当一个进程到达就绪队列而以前的进程正在执行时，就需要选择。新进程的下次CPU执行与当前进程未完成的CPU执行相比，可能会更小。

抢占SJF算法会抢占当前运行进程，而非抢占SJF算法会运行当前运行进程先完成CPU执行。抢占SJF调度就是最短剩余时间优先调度。

抢占SJF调度：

5.3.3 优先级调度

每个进程都会有一个优先级和它关联，而具有最高优先级的进程会分配到CPU。而具有相同优先级的进程按FCFS顺序调度。

优先级的定义可以分为内部的和外部的，内部的优先级采用一些测量数据来计算进程优先级，看i如：时限、内存要求、打开文件数量和平均IO执行时间与平均CPU执行之比等。外部定义的优先级比如进程重要新、赞助部门、其他因素等。

SJF算法是优先级调度算法的一个特例。而优先级为下次CPU执行的倒数。CPU执行时间越长，则优先级越小。

优先级调度可以是抢占的，也可以是非抢占的。

优先级调度算法的一个主要问题是无穷阻塞或者饥饿问题。对于一个优先级特别低的进程，可能会一直处于阻塞状态。

低优先级进程的饥饿问题的解决方案之一是老化。老化是逐渐增加在系统中等待很长时间的进程的优先级。

5.3.4 轮转调度

轮转（RR）调度算法是专门为分时系统设计的。类似于FCFS调度，但增加了抢占以切换进程。也叫轮询调度。

将一个较小时间单元（通常为10ms-100ms）定义为时间片。就绪队列作为循环队列，CPU调度程序循环整个就绪队列，为每个进程分配不超过一个时间片的CPU执行。

时间片到，中断操作系统，进行上下文切换。类似于CPU被抢占，所以这是个抢占调度。

RR调度的平均等待时间通常较长

如果时间片为4ms，则

RR算法中，没有一个进程被连续分配超过一个时间片的CPU。如果进程的CPU执行超过一个时间片，这个进程就会被抢占，并被放回到就绪队列。因此，RR调度算法是抢占的。

RR算法的性能很大程序取决于时间片的大小。如果时间片很大，RR算法可能就和FCFS算法一样，如果时间片很小，会导致频繁的上下文切换，影响CPU使用率。

5.3.5 多级队列调度

多级队列调度算法将就绪队列分成多个单独队列，例如进程通常分为前台进程（交互进程）和后台进程（批处理进程）

根据进程属性，如内存大小、优先级、进程类型等一个进程永远分到一个队列。每个队列有自己的调度算法。

每个队列与更低层队列相比有绝对的优先。

优点：优先级高的进程优先执行

缺点：可能存在饥饿问题

5.3.6 多级队列反馈调度

使用多级队列算法时，进程进入系统时永久分配到某个队列。而在多级队列反馈调度算法允许进程在队列之间迁移。

这种算法根据不同的CPU执行的特定来区分进程。如果进程使用过多的CPU时间，那么它会被移到更低的优先级队列。

这种方案将IO密集型和交互进程放在更高优先级队列上。因为占用的CPU时间比较低，可以有更多的时间来执行优先级较低的队列进程。在较低优先级队列中等待时间过长的进程会被移动到更高优先级的队列，防止饥饿的发生。

5.4 线程调度

用户级线程是由线程库管理的，系统级线程是由操作系统调度的。因此用户线程为了在CPU上运行往往会映射到相关的内核级线程，不过这种映射可能不是直接的，而是采用轻量级进程（LWP）

5.4.1 竞争范围

用户级线程和内核级线程的一个区别就在于它们是如何调度的。

对于实现多对一和多对多模型的系统线程库会调度用户级线程，以便在可用LWP上运行。这种方案被称为进程竞争范围（PCS）因为竞争CPU是发生在同一进程的线程之间。

为了决定哪个内核级线程调度到一个处理器上，欸和采用系统竞争范围（SCS）采用SCS调度来竞争CPU，发生在系统内的所有线程之间，采用一对一的模型的系统只使用SCS调度。

PCS通常采用优先级调度。

5.5 多处理器调度

之前的都是单CPU调度问题，如果是多个CPU，负载分配就成为可能，但是调度问题就会更为复杂。

5.5.1 多处理器调度的方法

对于多处理器系统，CPU调度的一种方法是让一个处理器（主处理器）处理所有调度决定、IO处理以及其他系统活动，其他的处理器只执行用户代码。

这种非对称多处理很简单，因为只有一个处理器访问系统数据结构，减少了数据共享的需要。

第二种方法是多对称处理（SMP），每个处理器自我调度。所有进程都可能处于一个共同的就绪队列中，或处理器都要它自己的私有就绪进程队列。

调度这样进行：每个处理器的调度程序都检查共同的就绪队列，以便选择执行一个进程。

5.5.2 处理器亲和性

当一个进程运行在一个特定处理器上的时候会缓存。进程最近访问的数据更新了处理器的缓存。进程的后续内存访问通常通过缓存来满足。

如果进程移到其他处理器上。第一个处理器缓存的内容变为无效，第二个处理器缓存重新填充。大多数系统试图避免将进程从一个处理器移到另一个处理器，而是试图让一个进程运行在同一个处理器上。这就是处理器亲和性，即一个进程对它运行的处理器具有亲和性。

处理器的亲和性具有多种形式。当一个操作系统试图保持进程运行在同一个处理器上时（但不保证它会这么做，这个进程也可以迁移到其他处理器上）这种情况是软亲和性。

有的SMP系统提供系统调用以便支持硬亲和性，从而允许某个进程运行在某个处理器子集上。

许多系统提供软亲核性和硬亲和性。

5.5.3 负载均衡

对于SMP系统，重要的是保持所有处理器的负载平衡，以便充分利用多处理器的优点。否则一个或多个处理器会空闲，而其他处理器会处于高负载状态且有一系列进程处于等待状态。

负载平衡试图将负载平均分配到SMP系统的所有处理器。

负载平衡通常有两种方法：推迁移和拉迁移

对于推迁移，一个特定的任务周期性地检查每个处理器的负载，如果发现不平衡，那么通过从超载处理器（高负载处理器）推到（push）空闲或不太忙的处理器，从而实现平均分配负载。

当空闲处理器从一个忙的处理器上拉（pull）一个等待任务时，发生拉迁移。

推迁移和拉迁移不必相互排斥，事实上，在负载均衡系统中它们往往被并行实现。

负载平衡往往会抵消处理器亲和性的好处。

5.6 实时CPU调度

一般来说，我们可以区分软实时系统和硬实时系统。

软实时系统不保证调度关键实时进程。而保证这类进程会优先于关键进程。

硬实时系统有更严格的要求。一个任务应在它的截至期限之前完成，在截止期限之后完成与没有完成是完全一样的。

5.6.1 最小化延迟

从事件发生到事件得到服务的这段事件被称为事件延迟。

两种类型的延迟会影响实时系统的性能：中断延迟和调度延迟。

中断延时是从CPU收到中断到中断处理程序开始的事件。当应该中断发生时，操作系统应先完成正在执行的指令，在确定发生中断的类型。然后，应保存当前进程的状态，再采用特定的中断服务程序（ISR）来处理中断。执行这些任务需要的总时间为中断延迟。

对于实时操作系统至关重要的是：尽量减少中断延迟，以确保实时任务得到立即处理。ISR即中断服务程序

调度程序从停止一个进程到启动另一个进程所需的时间就是调度延迟。实时操作系统应最大限度的减少这种延迟。保持调度延迟尽可能低的有效技术是提供抢占式内核。

下图说明了调度延迟的组成部分。

调度延迟的冲突部分有两部分：

抢占在内核中运行的任何进程（CPU冲突）

释放高优先级进程所需的、低优先级进程占用的资源。（资源冲突）

5.6.2 优先权调度

实时操作系统最重要的功能是：当一个实时进程需要CPU是，立即响应。因此，用于实时操作系统的调度程序应支持抢占的、基于优先权的算法

基于优先级的调度算法根据进程的重要性分配优先级。进程越重要，它分配的优先级也越高。

如果调度程序支持抢占，并且有一个更高优先级的进程就绪，那么处于运行中的、优先级低的进程就被抢占。

提供抢占的、基于优先级的调度程序仅保证软实时功能，只保证能抢占到，但是不能保证能在规定时间内进程被执行。

硬实时系统应进一步保证实时任务应在截止期限内得到服务，做出这样的保证需要附加的调度特征。

在讨论各个调度程序的细节前，应当先分析需要调度的进程的特征。

这些进程是周期性的。它们定期的需要CPU。一旦周期性进程获得CPU，就具有固定的处理时间t，CPU应处理的截止期限d和周期（例如分时的时间片）p。

周期任务的速率为1/p。

处理时间t、截止期限d和周期p之间的关系为：0<=t<=d<=p

满足这个关系就满足硬实时系统，否则就是软实时。

下图描述了应该周期性进程随时间的执行情况，调度程序可以利用这些特性，根据进程的截止期限或速率要求来分配优先级

调度程序做两件事之一：它承认进程，保证进程完成；如果不能保证任务在截止期限之前得到服务，拒绝请求。

5.6.3 单调速率调度

单调速率算法采用抢占的、静态优先级（优先级是确定的，不能被动态的调整）的策略，调度周期性任务。

当较低优先级的进程正在运行并且较高优先级的进程可以运行时，较高优先级的进程就会抢占低优先级。

在进入系统时，每个周期性任务会分配应该优先级，它与其周期成反比。周期越短，优先级越高；周期越长优先级越低。

这种策略的利用是：更频繁的需要CPU的任务应该分配更高的优先级。此外，单调速率调度假定对于每次CPU执行，周期性进程的处理时间是相同的。也就是说在每次进程获取CPU时，它的CPU执行长度是相同的。

考虑一个例子：

进程p1的周期为p1=50，处理时间为t1=20，CPU利用率为p1/t1=0.4，进程p2=100，t2=35，p2/t2=0.35。如果这两个进程一起执行 其CPU利用率为0.75，我们似乎可以调度这些任务满足他们的截止期限并还能让CPU有多余时间。

假设为P2分配更高的优先级。执行情况如下：

p2先执行并且在35ms时完成，这时p1开始，它完成CPU执行时间为55但是截止期限是50，所以调度程序让p1错过了截止期限。这种调度无法实现硬实时系统。

如果使用单调速率调度，p1优先级更高，因为p1的周期更短。

此时这些进程的执行情况如下：

首先p1开始在20ms时完成CPU执行从而满足第一个截止期限。此时p2开始执行，运行到时间50，此时被p1抢占，尽管p2的CPU还有5ms的执行时间。p1在时间70完成CPU执行，调度器恢复p2.P2在75ms时完成CPU执行，也满足第一个截止期限。然后系统空闲到100ms进行下次调度。

单调速率调度可被认为是最优的，因为如果一组进程不能由此算法调度，它不能被其他任何分配静态优先级的算法来调度。接下来分析一组无法使用单调速率算法调度的进程。

假设进程P1具有p1=50，t1=25，p2=80，t2=35.此时p1优先级更高，此时总的CPU的利用率为0.94，逻辑上来讲这两个进程是可以被调度的。

下图显示了进程的调度：

图中显示了进程p1和p2的调度，首先p1运行，在25ms时完成CPU执行。p2开始执行运行到50，被p1抢占；这时p2在CPU执行时有10ms的剩余。进程p1运行到时间75，导致p2在85ms时结束，因此超过了在时间80完成CPU执行的截止期限。

尽管是最优的，单调速率调度仍然有一个限制：CPU的利用率是优先的，并不总是可能完全最大化CPU的资源。调度N给进程的最欢情况下CPU利用率为

对于具有一个进程的系统，CPU的利用率是100%；但是当进程数量接近无穷时，它大概只有69%。对于两个进程的系统，CPU利用率是83%。上面的调度利用率是75%。因此单调速率调度能调度它们。图5-18的利用率的94%，因此无法保证可以调度它们。

5.6.4 最早截止期限优先调度

最早截止期限调度（EDF）调度根据截止期限动态分配优先级。截止期限越早，优先级越高；截止期限越晚，优先级越低。

根据EDF策略，当一个进程可运行时，它应向系统公布截止期限要求。优先级可能需要进行调整，以便反映新可运行进程截止期限。

考虑5-18的调度p1=50，t1=25，p2=80，t2=35.EDF的调度如下图所示。

第一次调度失败原因是50ms时p2被p1抢占，但是EDF调度不会被抢占，原因是此时p1的截止期限是在第二个周期，也就是100，优先级是低于p2的。

与单调速率调度不同，EDF不要求进程是周期性的，也不要求进程的CPU执行时间固定，只要求进程在运行时公布截止期限。

EDF的优点是：理论上他是最佳的并且CPU的利用率可以达到100%，但是由于进程的上下文切换和中断的代价，这种级别的CPU利用率是不可能的。

5.6.5 比例分享调度

比例分享调度程序在所有应用之间分配T股。如果一个应用程序接收N股的时间，那么确保了它将有N/T的总的处理器时间。例如，假设总的T=100股要在三个进程ABC之间分配，A占50股，B为15股，C为20股。

这种方案确保A有50%的总处理器时间，B有15%，C有20%。这种调度程序采用准入控制策略，以确保每个进程得到分配时间。

准入控制策略是：只有客户请求的股数少于可用的股树，才能允许客户进入。