MHuiG

CPU 调度

基本概念

CPU－I/O 区间周期

进程执行由 CPU 和 I／O 等待周期组成。进程在这两个状态之间切换。

CPU 调度程序

所谓 CPU 调度程序，其实就是：当 CPU 空闲时，操作系统如何从就绪队列中选择一个进程来执行的策略。

抢占调度

非抢占调度，一旦 CPU 分配给一个进程，那么该进程会一直使用 CPU 直到进程终止或切换到等待状态。
抢占调度，可能一个进程正在运行时，另一个新的进程也到来。而依据调度策略与当前各进程状态，新进程应该先执行。那么，新进程会抢占 CPU 进行执行，原进程切换到就绪状态。

分派程序

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

切换上下文
切换到用户模式
跳转到用户程序的合适位置，以重新启动程序

调度准则

CPU 使用率
吞吐量：一个时间单元内所完成进程的数量
周转时间：从进程提交到进程完成的时间段称为周转时间。
等待时间：为在就绪队列中等待所花费时间之和
响应时间：开始响应所需要的时间，响应时间指从进程提交到被运行第一段代码的时间

调度算法

1. 先到先服务调度（FCFS）

非抢占。补充概念：护航效果：所有其他进程等待一个大进程释放 CPU 的状态

2. 最短作业优先调度（SJF）

这一算法将每个进程与其下一个 CPU 区间段相关联。当 CPU 为空闲时，它会赋给具有最短 CPU 区间的进程。如果两个进程具有同样长度，那可以使用 FCFS 调度来处理。

SJF 调度算法的平均等待时间最小。

SJF 的难点就是如何得知下一个 CPU 区间的长度。书上采用，预测下一个 CPU 区间为以前 CPU 区间的测量长度的指数平均。

T（n＋1）＝åt（n）＋（1-å）T（n）

抢占 SJF 调度：最短剩余时间优先调度也存在非抢占 SJF

3. 优先级调度

SJF 可作为通用优先级调度算法的一个特例

（书上默认）优先级越高，数值越小即优先级 1 比优先级 2 的优先级要高优先级调度可以是抢占的或者非抢占的。

主要问题：无穷阻塞或饥饿＝》它可能会导致某个低优先级进程无线等待 CPU

解决：使用老化技术，以逐渐增加在系统中等待很长时间的进程的优先级

4. 轮转法调度（RR）

定义一个较小时间单元，称为时间片。

将就绪队列保存为进程的 FIFO 队列。新进程增加到就绪队列的尾部。CPU 调度程序就从就绪队列中选择第一个进程，设置定时器在一个时间片之后中断，再分排该进程。（1 进程在时间片中运行完，进程自动释放 CPU，下一个进程开始执行 2. 进程未在时间片内执行完，定时器产生中断并产生操作系统中断，然后进行上下文切换，将进程加入到就绪队列的尾部，就绪队列中下一个进程开始执行）

该策略的平均等待时间通常较长具体效率和时间片大小有关适合分时（交互系统）