xv6(16) 进程二:调度算法

进程二:调度算法

调度是操作系统里面一个很重要的概念，进程中有调度，页面置换有调度，磁盘访问也有调度，本文讲述的是进程之间的调度，以及多处理器之间的调度策略。废话不多时直接来看，先来简单了解各种概念：

各种概念简析

各种时间

到达时间：进程到达等待队列的时间

开始时间：CPU 开始执行进程的时间

完成时间：进程执行完成的时间

服务时间：进程在 CPU 上总共执行的时间

等待时间/响应时间：进程在队列中等待的时间，即$开始时间-到达时间$

周转时间：进程被提交给系统到完成的这段时间，即$完成时间-到达时间=等待时间+服务时间$

平均周转时间：多个进程周转时间的平均值

带权周转时间：周转时间与服务时间之比

平均带权周转时间：多个进程的带权周转时间的平均值

作业进程

作业是用户需要计算机完成的某项任务，而进程是完成这个任务的执行实体，是资源分配的基本单位。作业的层级比进程高，一个作业至少由一个进程组成。

类型：

• CPU 繁忙型：需要大量 CPU 时间而很少请求 I/O。
• I/O 繁忙型：作业/进程执行期间频繁请求 I/O，这类进程对用户交互影响较大，所以通常赋予较高的优先级以达到交互的实时性。

系统类型

批处理系统：作业成批装入计算机由计算机管理，作业执行的过程中用户不能干预交互。

分时系统：多个用户可以通过各自的终端共用一台计算机，同计算机进行交互操作，计算机以“分时”(划分时间片)的方法轮流为每个用户服务。

实时系统：要求及时响应且高可靠的一类系统。

抢占非抢占

非抢占方式

进程分配到 CPU 之后，进程一直运行到完成或异常才终止。

• 简单，开销小
• 适用批处理系统

抢占方式

系统会根据某种策略(抢占原则)收回正在运行当前进程的 CPU，转而去调度其他的就绪进程。

• 能够及时响应进程的需求
• 适用于分时/实时系统

抢占方式采用的策略：

• 时间片，当前进程的时间片用完后调度其他就绪进程
• 优先级，有更高优先级的进程出现后，抢占当前正运行的进程
• 短进程，有更短进程出现后，抢占当前正运行的进程

调度算法

先来先服务

维护一个队列，按照进程/作业进入队列的先后次序调度，先进入先调度，后进入后调度。

特点：

• 简单，公平，不可抢占，不会饥饿
• 对长作业有利，对短作业不利
• 对 CPU 繁忙型有利，对 I/O 繁忙型不利
• 适用于批处理，不适用于分时系统

最短进程优先

同样维护一个队列，每次调度时从队列中选一个运行时间最短的作业/进程调度。这里的运行时间是用户自己估计的。

特点：

• 不可抢占
• 对长作业不利，可能导致长作业长期不被调度——饥饿现象，如果一直不被调度，则饿死
• 平均等待时间，平均周转时间最短
• 作业长短具主观因素，不一定真的最短作业优先。

最短剩余时间优先

最短进程/作业的抢占形式，从就绪队列中挑选出估计运行时间最小的作业/进程，然后为其分配 CPU。

特点：

• 可抢占，当来了一个新进程，如果这个新进程比正在运行的当前进程需要更少的时间，则抢占当前进程的 CPU。
• 相比短进程优先性能更好，短进程只要就绪就可以抢占 CPU 开始执行。
• 需计算记录剩余的时间，增加系统开销

最高优先级

维护一个队列，将队列中优先级最高的进程/作业分配给处理器

非抢占式：处理器一旦分配给队列中某优先级最高的进程后，除了因为一些事件比如阻塞，该进程会让出处理器，否则将一直执行下去直到完成。

抢占式：处理器分配给队列中某优先级最高的进程后，在执行的过程中如果来了一个优先级更高的进程，调度程序则停止当前进程的执行转去调度新来的那个优先级更高的进程。

优先级类型：

静态优先级：在创建进程的时候确定，在整个运行过程中保持不变。可能会产生饥饿乃至饿死

动态优先级：随着进程的执行时间或等待时间而动态的改变其优先级

高相应比优先

$响应比=(等待时间+要求服务时间)/要求服务时间$

每次调度时计算各个作业或进程的相应比，选择响应比最高的调度

特点：

• 不可抢占，不会饥饿
• 综合了等待时间和服务时间两个因素
• 要进行计算，增加开销

时间片轮转法

将所有就绪的进程按 FCFS 的原则排成一个队列，每次调度时，将 CPU 分配给队首进程，但只执行一个时间片。时间片结束后将其放在队尾，然后将 CPU 分配给新的队首执行一个时间片。而如果在时间片用完之前该进程就结束或阻塞，那么 CPU 立即进行进程的切换。

特点：

• 简单公平，不会饥饿
• 时间片的选取太小会频繁的发生上下文切换，增加系统开销，但利于短作业
• 时间片选取太大，增加了短作业的响应时间可能退化成 FCFS，有利于长作业。

多级反馈队列

设置多个就绪队列，每个队列的优先级和时间片不同。第一个队列的优先级最高，时间片最短。各个队列的优先级依次降低，时间片依次增长。

一个新进程会被先放入第一个就绪队列，按照 FCFS 的原则等待调度。当这个进程被分配到 CPU 执行时，如果能在相应的时间片内执行完，则可准备撤离系统，如果不能执行完成，则将该进程放入第二个就绪队列的末尾，按照 FCFS 的原则等待调度。如此依次进行下去直到执行完成。

只有当高优先级的队列为空时，才会调度较低优先级队列中的进程。如果 CPU 正在执行某较低优先级队列中的进程时，较高优先级队列中来了一个新进程，则这个新进程抢占当前进程的 CPU，即 CPU 将当前进程放在原队列的队尾，转而去为那个较高优先级的进程服务。

特点：

• 综合时间片轮转法和优先级两种调度算法
• 兼顾长作业和短作业，短作业可以在第一个就绪队列很快的执行完成，长作业在第一个就绪队列中没有执行完，移到下一个就绪队列等待执行，等待时间边长但执行时间也变长了。
• 可抢占

多处理器调度

单队列

这种形式不需要在单处理器的框架下做太多改动，同样的是维护一个进程的全局就绪队列，为所有 CPU 共享。运行在 CPU 上的调度程序从这个队列中挑选合适的进程执行。

特点：

• 实现较简单，对所有的 CPU 来说很公平。
• 这个队列是全局共享的，所以当一个 CPU 挑选进程时需要加锁，不然多个 CPU 就可能选取同一个进程。但是锁机制不可避免带来额外的开销使得性能降低，可扩展性降低。
• 处理器亲和性(Processor Affinity)不容易实现，处理器亲和性是系统提供给用户的一种选择，用户可以指定特定的处理器来执行进程。
• 每个处理器都有自己的缓存，处理器亲和性不好，一个进程可能在多个处理器之间来回运行，使得处理器的缓存无效，所以缓存亲和性也不好，性能较为低下。

多队列

如上图所示：每个 CPU 都有自己单独的调度队列。每个 CPU 只在自己本地的队列中挑选合适的进程，速度很快。

队列之间的调度相互独立，可不再使用锁机制，可扩展性增强，比如每个队列可使用不同的调度算法。

所有的任务工作都能在固定的 CPU 上执行，能够很好的利用缓存数据。

但是也有明显缺点：各个 CPU 的负载不均衡，从上图就可以看出 CPU2 负载较大，而 CPU3 负载较小

解决负载均衡的办法叫做迁移(Migration)，从繁忙 CPU 的队列中迁移一些进程到空闲 CPU 中去。

好了本节就这样吧，有什么问题还请批评指正，也欢迎大家来同我讨论交流学习进步。