1 CPU调度的相关概念

1.1调度的基本概念

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

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

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

• 调度算法

• 调度时机

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

1.3 调度的层次

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

• 内存与辅存之间

• 就绪队列

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

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

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

• 分类
• 就绪挂起
• 阻塞挂起

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

• 内存里面

• 就绪队列 ——> 执行

(4)三级调度的联系

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

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

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

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

2 调度的实现

2.1 调度程序

(1)排队器

(2)分派器

(3)上下文切换器

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

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

典型的事件举例

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

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

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

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

CPU调度可能发生的情况

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

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

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

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

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

（1）进程切换

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

• 切换全局页目录以加载一个新的地址空间

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

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

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

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

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

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

（3）上下文切换的开销

• 间接开销：缓存失效
• 高速缓存(Cache)、缓冲区缓存(Buffer Cache)和TLB(Translation Look-aside Buffer)失效

• 直接开销：内核完成切换所用的CPU时间
• 保存和恢复寄存器
• 切换地址空间（相关指令比较昂贵）

2.4 闲逛进程

2.5 两种线程的调度

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

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

3 调度的一些讨论

3.1 进程优先级

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

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

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

3.2 进程就绪队列组织

3.3 抢占式与非抢占式

• 可抢占式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能力

• 进程的行为

4 调度算法的设计

调度算法的衡量指标

• 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）

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

• 非抢占式

• 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 多级反馈队列调度算法

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

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

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

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

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

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

• 由于阻塞而放弃CPU的进程进入相应的等待队列，一旦等待的事件发生，该进程回到原来一级就绪队列
• 若允许抢占：当有一个优先级更高的进程就绪时，可以抢占CPU。被抢占的进程回到原来一级就绪队列末尾

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

7.1 各种调度算法的比较

7.2 多处理器调度算法需要考虑的问题

1. 不仅要决定选择哪一个进程执行，还需要决定在哪一个CPU上执行

2. 要考虑进程在多个CPU之间迁移时的开销
• 高速缓存失效、TLB失效
• 尽可能使进程总是在同一个CPU上执行
• 如果每个进程可以调度到所有CPU上，假如进程上次在CPU1上执行，本次被调度到CPU2，则会增加高速缓存失效、TLB失效；如果每个进程尽量调度到指定的CPU上，各种失效就会减少

3. 考虑负载均衡问题

7.3 典型操作系统的调度算法

• UNIX：动态优先数法

• 5.3BSD：多级反馈队列法

• Linux：抢占式调度

• Windows：基于优先级的抢占式多任务调度

• Solaris：综合调度算法