1. 调度的三个层次
1.1 作业调度
作业调度决定是否为作业
创建相应的进程
（建立PCB），并将其加入将要执行的进程集合中。
作业调度是
外存与内存
之间的调度。每个作业只会被调入一次、调出一次，作业调度主要关注
调入
问题，因为只有调入的时机需要操作系统决定。
1.2 内存调度
引入虚存技术后，可以将暂时不能运行的进程移至外存等待，即变为
挂起状态
。处于挂起状态的进程的PCB会
常驻内存
，被放入
挂起队列
中。
内存调度调度就是决定是否将一个挂起进程载入内存。
一个进程可能被多次调入、调出内存，因此内存调度的发生频率比作业调度高。
1.3 进程调度
进程调度决定哪个就绪进程将被处理机执行。
进程调度的频率很高，一般几十毫秒一次。
1.4 三层调度的对比
2. 进程调度
2.1 进程调度的时机
需要进行进程调度、切换的情况：
-
当前进程
主动
放弃处理机：- 进程正常终止
- 运行过程中发生异常而终止
- 进程主动请求阻塞（如I/O请求）
-
当前进程
被动
放弃处理机：- 时间片用完
- 有更紧急的事需要处理（I/O中断）
- 有更高优先级的进程进入就绪队列
不能进行进程调度、切换的情况：
- 在处理中断的过程中
-
进程在
操作系统内核程序临界区
- 在原子操作过程中
2.2 进程调度的方式
被抢占方式：只允许进程主动放弃处理机。这种方式实现简单，但无法处理紧急任务，适合早期的批处理系统。
抢占方式：允许进程被动放弃处理机。
2.3 进程的切换与过程
进程切换的过程主要完成了：
- 对原来运行进程的各种数据的保存。
- 对将要运行进程的各种数据的恢复。
各种数据包括：程序计数器、程序状态字、数据寄存器等，这些信息一般保存在进程控制块中。
由此可见，进程切换是
有代价
的，过于频繁的切换可能会导致系统效率的降低。
3 调度算法的评价指标
3.1 CPU利用率
CPU“忙碌”的时间占总时间的比例。
3.2 系统吞吐量
单位时间内完成作业的数量。
3.3 周转时间
从作业被
提交
给系统开始，到作业
完成
为止的这段时间间隔。它包括4个部分：
- 作业在外存上等待作业调度的时间。
- 进程在就绪队列上等待调度的时间。
- 进程等待I/O操作完成的时间。
作业周转时间 = 作业完成时间 – 作业提交时间
平均周转时间 = 各作业周转时间之和 / 作业数
带权周转时间 = 作业周转时间 / 作业实际运行的时间
平均带权周转时间 = 各带权周转时间 / 作业数
3.4 等待时间
指进程/作业处于
等待处理机状态
的时间之和。
对进程来说，等待时间是指进程
建立
后，
等待
被服务的时间之和。注意：在等待I/O完成的期间，其实也是在被I/O设备服务的，所以不计入等待时间。
对作业来说，相比进程还要额外考虑作业在
外存后备队列
中的等待时间。
等待时间 = 周转时间 – 运行时间 – I/O操作时间
一般而言，一个作业/进程需要CPU、I/O设备服务多久都是固定的，因此调度算法只会影响作业/进程的等待时间。
3.5 响应时间
用户提交请求到首次产生响应的时间。
响应时间 = 进程第一次被CPU执行的时刻 – 提交时间（不确定）
4 调度算法
4.1 先来先服务
从“公平”的角度考虑，按照作业/进程
到达
的
先后顺序
进行服务。
从另一个角度说，优先为等待时间最长的作业/进程服务。
对于作业调度，考虑的是哪个作业先到达后备队列；对于进程调度，考虑的是哪个进程先到达
就绪队列
。
非抢占式算法。
优点：公平、实现简单，不会导致饥饿。
缺点：对长作业不利、对短作业不利。
4.2 短作业优先
为了追求最少的平均等待时间、最少的平均周转时间、最少的平均带权周转时间，让
服务时间最短
的作业优先得到服务。
短作业优先算法默认是
非抢占式
的，每次调度时选择当前
已到达
且
运行时间最短
的作业。
抢占式的短作业优先算法又称“最短剩余时间优先算法”，每当
有进程加入就绪队列
或
进程完成
时就需要进行调度，选择
剩余执行时间
最短的作业。
优点：“最短的”平均等待时间、平均周转时间
缺点：不公平；对短作业有利，对长作业不利；可能导致饥饿，甚至“饿死”；作业的运行时间
由用户提供
，不一定真实。
4.3 高响应比优先
综合考虑作业/进程的等待时间和要求服务的时间，在每次调度时选择
响应比最高
的作业/进程为其服务。
响应比 = （等待时间+要求服务时间）/ 要求服务时间
非抢占式
算法。
优点：综合考虑了等待时间和运行时间，不会导致饥饿。
4.4 时间片轮转调度算法
按照各进程到达就绪队列的顺序，轮流让各个进程执行一个
时间片
（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将该进程放到就绪队列的
队尾
重新排队。
如果一个进程时间片到的时刻，一个新进程恰好进入就绪队列，则默认新进程排在
前面
。
该算法适用于进程调度，属于
抢占式
算法，由时钟装置发出
时钟中断
来通知CPU时间片到。
若时间片过长，则时间片轮转调度算法
退化
为先来先服务算法，大大增加进程
响应
时间；若时间片过短，则会导致进程调度过于频繁，进程切换的开销过大。
优点：公平；响应快；不会导致饥饿。
缺点：不区分任务的紧急程度。
4.5 优先级调度算法
调度时选择
优先级最高
的作业/进程。
非抢占式、抢占式均有。非抢占式的进程调度只发生在
进程主动放弃
处理机时，而抢占式的进程调度还会发生在
就绪队列变化
时。
优先级有
静态优先级
和
动态优先级
两种：
-
静态优先级：进程
创建
时决定，之后一直不变。 - 动态优先级：进程创建时有一个初始值，之后根据情况动态调整优先级。
通常：
- 系统进程优先级高于用户进程
- 前台进程高于后台进程
-
I/O型
进程高于
计算型
进程解释：如果让I/O型进程优先运行，则I/O设备可以尽早投入使用，以实现I/O设备和CPU的并行工作，提高资源利用率、系统吞吐量。
处于公平、资源利用率等角度考虑：
- 如果某进程在就绪队列中等待时间过长，则适当提升其优先级。
- 如果某进程占用处理机时间过长，则适当降低其优先级。
优点：可以区分进程的重要程度、紧急程度；灵活。
缺点：可能导致饥饿。
4.6 多级反馈队列调度算法
设置多级就绪队列，各级队列
优先级从高到低
，
时间片从小到大
。新进程到达时，先进入第1级队列，按照先来先服务原则排队等待时间片，若
时间片到
进程还未结束，则进程进入
下一级队列队尾
，如果此时已经在最下级队列，则重新放回
该队列队尾
。只有
前k级
队列为空时，才会为第k+1级
队头
的进程分配时间片。
抢占式算法
。在k级队列的进程运行过程中，若
上级队列
进入了一个新进程，则此新进程会抢占处理机，原来运行的进程放回
k级队列
的
队尾
。
优点：综合上述算法的特点。
缺点：可能导致饥饿。