OS：CPU调度 | Koreyoshi

type

status

date

slug

summary

1 CPU调度的相关概念

1.1调度的基本概念

CPU调度——其任务是控制、协调进程对CPU的竞争。

即按一定的调度算法从就绪队列中选择一个进程，把CPU的使用权交给被选中的进程

如果没有就绪进程，系统会安排一个系统空闲进程或idle（闲逛）进程。

1.2 CPU调度要解决的三个问题

WHAT:按什么原则选择下一个要执行的进程。

调度算法

WHEN：何时选择。

调度时机

HOW：如何让被选中的进程上CPU运行。

调度过程（进程的上下文切换）

1.3 调度的层次

一个作业从提交开始知道完成，往往要历经以下三级调度。

(1)高级调度——作业调度

从外存中处于后备状态的作业挑选一个（多个）作业，给它分配内存，输入输出设备等资源，并建立相应的进程、分配必要的资源，并将其放入就绪队列。

内存与辅存之间

就绪队列

(2)中级调度——内存调度

为将那些暂时不能运行的进程调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。（中级调度实际上是存储器管理中的对换功能）

目的：提高内存利用率和系统吞吐量。

对比：内存调度和作业调度看起来都是内存与外存，但内存调度不会撤销其PCB，只是将进程映像放入外存，【也就是挂起】，因此并不影响作业调度对每个作业只调入一次，调出一次挂起。

分类

就绪挂起
阻塞挂起

(3)低级调度——进程调度

按照某种算法从就绪队列中选取一个进程，将CPU分配给它。

内存里面

就绪队列 ——> 执行

(4)三级调度的联系

作业调度从外村的后备队列选择一批作业进入内存，为他们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选择一个，将其状态改为运行态，把CPU分配给它。中级调度则是为了提高内存利用率，将那些暂时不能运行的进程挂起来。

作业调度为进程活动做准备，进程调度使进程正常活动起来。

中级调度将暂时不能运行的进程挂起，处于作业调度和进程调度之间。

作业调度次数最少，进程调度次数最多。

进程调度是最基本的，不可或缺的。

ㅤ	要做什么	任务流向	发生频率	进程状态变化
高级调度（作业调度）	按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程	外存 —> 内存（面向作业）	最低	无→创建态→就绪态
中级调度（内存调度）	按照某种规则，从挂起队列中选择合适的进程将其数据调回内存	外存 —> 内存（面向进程）	中等	挂起态→就绪态（阻塞挂起阻塞态）
低级调度（进程调度）	按照某种规则，从就绪队列中选择一个进程为其分配处理机	内存 —> CPU	最高	就绪态→运行态

2 调度的实现

2.1 调度程序

用于调度和分派CPU的组件称为调度程序，它通常由三部分组成。

(1)排队器

将系统中的所有就绪进程按照一定的策略排成一个或者多个队列，以便调度程序选择。每当有一个进程转变为就绪态时，排队器便将它插入相应的就绪队列。

(2)分派器

依据调度程序所选的进程，将其从就绪队列中取出，将CPU分配给新进程。

(3)上下文切换器

在对CPU进行切换时，会发生两对上下文的切换操作：

第一队，将当前进程的上下文保存到其PCB中，再装入分派程序的上下文，以便分配程序运行。

第二队，移出分派程序的上下文，将新选进程的CPU现场信息装入CPU的各个相应寄存器。

在上下文切换的时，需要大量的load和store指令，以保存寄存器的内容，因此会花费较多的时间。现在已有硬件方法来减少上下文切换时间。通常采用两组寄存器，其中一组供内核使用，一组供用户使用。这样，上下文切换时，只需要改变指针，让其指向当前寄存器组。

2.2 调度的时机、切换与过程

事件发生 → 当前运行的进程暂停运行 → 硬件机制响应后 → 进入操作系统，处理相应的事件 → 结束处理后：某些进程的状态会发生变化，也可能又创建了一些新的进程 → 就绪队列有调整 → 需要进程调度根据预设的调度算法从就绪队列选一个进程

典型的事件举例

创建、唤醒、退出等进程控制操作

进程等待I/O、I/O中断

时钟中断，如：时间片用完、计时器到时

进程执行过程中出现abort异常

CPU调度可能发生的情况

进程正常终止或由于某种错误而终止

新进程创建或一个等待进程变成就绪

当一个进程从运行态进入阻塞态

当一个进程从运行态变为就绪态

其本质是：内核对中断/异常/系统调用处理后返回到用户态时。

2.3 进程切换（调度的实现）

（1）进程切换

定义：是指一个进程让出处理器，由另一个进程占用处理器的过程。

进程切换主要包括两部分工作：

切换内核栈和硬件上下文，其中硬件上下文包括了内核执行新进程需要的全部信息，如CPU相关寄存器

切换过程包括了对原来运行进程各种状态的保存和对新的进程各种状态的恢复

（2）上下文切换的具体步骤

（进程A下CPU，进程B上CPU）

从进程B的PCB中恢复上下文（程序计数器、程序状态字、其他寄存器…）

将进程B的状态设置为运行态

把进程A移至合适的队列（就绪、阻塞…）

用新状态和其他相关信息更新进程A的PCB

保存进程A的上下文环境（程序计数器、程序状态字、其他寄存器…）

（3）上下文切换的开销

（上下文切换通常是计算密集型的，即它需要相当可观的CPU时间。）

间接开销：缓存失效

高速缓存(Cache)、缓冲区缓存(Buffer Cache)和TLB(Translation Look-aside Buffer)失效

直接开销：内核完成切换所用的CPU时间

保存和恢复寄存器
切换地址空间（相关指令比较昂贵）

2.4 闲逛进程

在进程切换时，如果系统中没有就绪进程，就会调用闲逛进程，如果没有其他进程就绪，该进程就会一直运行。闲逛进程优先级最低，没有就绪进程时才会调用闲逛进程。

它不需要CPU以外的资源，所以不会被阻塞

2.5 两种线程的调度

用户级线程。由于内核不知道线程的存在，所以内核还是和以前一样，选择一个进程并给予时间控制。由进程中的调度程序决定哪个线程运行

内核级线程调度。内核选择一个特定的线程运行，通常不考虑该线程属于哪个进程。对被选择的线程赋予一个时间片，如果超过了时间片，就强制挂起。

3 调度的一些讨论

3.1 进程优先级

静态优先级：

进程创建时指定，运行过程中不再改变

动态优先级：

进程创建时指定了一个优先级，运行过程中可以动态变化

如：等待时间较长的进程可提升其优先级

3.2 进程就绪队列组织

3.3 抢占式与非抢占式

抢占与非抢占指占用CPU的方式：

可抢占式Preemptive（可剥夺式）：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用

不可抢占式Non-preemptive（不可剥夺式）：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去

3.4 I/0密集型与CPU密集型进程

按进程执行过程中的行为划分：

I/O密集型或I/O型(I/O-bound)：频繁的进行I/O，通常会花费很多时间等待I/O操作的完成

CPU密集型或CPU型或计算密集型(CPU-bound)：需要大量的CPU时间进行计算

3.5 时间片

时间片：一个时间段，分配给调度上CPU的进程，确定了允许该进程运行的时间长度

设计时间片大小时，考虑因素：

进程切换的开销

对响应时间的要求

就绪进程个数

CPU能力

进程的行为

4 调度算法的设计

调度算法的衡量指标

CPU利用率

尽可能使CPU处于“忙”状态，使这一资源利用率最高。CPU利用率计算方法如下：

吞吐量

单位时间内CPU完成作业的数量

周转时间

指从作业提交到作业完成所经历的时间总和，是作业等待，在就绪队列中排队，在处理机上运行以及输入输出所花费时间的总和

等待时间

作业处于等待处理机的时间总和，等待时间越长，用户满意度越低。处理机调度算法实际上并不影响作业执行或输入输出时间。

响应时间

指从用户提交作业到系统首次产生响应所用的时间。

5 批处理系统的调度算法

批处理系统中可用的调度算法有

先来先服务（FCFS-First Come First Serve）

最短作业优先（SJF-Shortest Job First）

最短剩余时间优先（SRTN-Shortest Remaining Time Next）

最高响应比优先（HRRN-Highest Response Ratio Next）

5.1 先来先服务（FCFS）

特点：

先进先出 First In First Out (FIFO)

按照进程就绪的先后顺序使用CPU

非抢占

优缺点：

公平

实现简单

长进程后面的短进程需要等很长时间，不利于用户体验

5.2 短作业有限（SJF）

短作业优先的特点：

具有最短完成时间的进程优先执行

非抢占式

最短剩余时间优先(Shortest Remaining Time Next(SRTN))的特点：

SJF抢占式版本，即当一个新就绪的进程比当前运行进程具有更短的完成时间时，系统抢占当前进程，选择新就绪的进程执行

优缺点：

最短的平均周转时间

不公平，源源不断的短任务到来，可能使长的任务长时间得不到运行 → 产生 “饥饿”现象(starvation)

5.3 最高响应比有限（HRRN）

特点：

是一个综合的算法

调度时，首先计算每个进程的响应比R；之后，总是选择R最高的进程执行

6 交互式系统的调度算法

交互式系统中可用的调度算法有

轮转调度（RR-Round Robin）

最高优先级调度（HPF—Highest Priority First）

多级反馈队列（Multiple feedback queue）

最短进程优先（Shortest Process Next）

6.1 时间片轮转调度算法

目标：为短任务改善平均响应时间

特点：

周期性切换

每个进程分配一个时间片

时钟中断 → 轮换

如何选择合适的时间片?

太长 --大于典型的交互时间

降级为先来先服务算法
延长短进程的响应时间

太短 --小于典型的交互时间

进程切换浪费CPU时间

优缺点：

公平

有利于交互式计算，响应时间快

由于进程切换，时间片轮转算法要花费较高的开销

RR对不同大小的进程是有利的，但是对于相同大小的进程，会增加平均响应时间（因为几乎都在最后一些时间片中所有进程才完成）

6.2 虚拟轮转法（VIRTUAL RR）

6.3 最高优先级调度算法

优先级调度算法既可用于作业调度，又可用于进程调度。

根据更高优先级进程能否抢占当前正在执行的进程，可将调度算法分为两种：

非抢占式优先级调度算法。

抢占式优先级调度算法。

根据优先级是否可以改变，可以将优先级分为以下两种：

静态优先级。优先级在创建进程时确定，主要依据有进程类型，对资源的要求，用户要求等。

动态优先级。在运行过程中，可以动态调整优先级，主要依据有CPU时间长短，就绪进程等待CPU时间等。

6.4 多级反馈队列调度算法

Multilevel Feedback是UNIX的一个分支BSD（加州大学伯克利分校开发和发布的）5.3版所采用的调度算法，是一个综合调度算法

算法详细描述

设置多个就绪队列，第一级队列优先级最高

给不同就绪队列中的进程分配长度不同的时间片，第一级队列时间片最小；随着队列优先级别的降低，时间片增大

当第一级队列为空时，在第二级队列调度，以此类推

各级队列按照时间片轮转方式进行调度

当一个新创建进程就绪后，进入第一级队列

进程用完时间片而放弃CPU，进入下一级就绪队列

由于阻塞而放弃CPU的进程进入相应的等待队列，一旦等待的事件发生，该进程回到原来一级就绪队列

若允许抢占：当有一个优先级更高的进程就绪时，可以抢占CPU。被抢占的进程回到原来一级就绪队列末尾

7 各种调度算法的比较与应用

7.1 各种调度算法的比较

调度算法	占用CPU方式	吞吐量	响应时间	开销	对进程的影响	饥饿问题
FCFS	非抢占	不强调	可能很慢，特别是当进程的执行时间差别很大时	最小	对短进程不利；对I/O型的进程不利	无
Round Robin	抢占(时间片用完时)	若时间片小，吞吐量会很低	为短进程提供好的响应时间	最小	公平对待	无
SJF	非抢占	高	为短进程提供好的响应时间	可能较大	对长进程不利	可能
SRTN	抢占(到达时)	高	提供好的响应时间	可能较大	对长进程不利	可能
HRRN	非抢占	高	提供好的响应时间	可能较大	很好的平衡	无
Feedback	抢占(时间片用完时)	不强调	不强调	可能较大	对I/O型进程有利	可能