进程调度
进程调度（Scheduling）
- 短程调度（STS, Short Term Scheduling）：从就绪队列中选择进程送到CPU执行。
- 中程调度（MTS, Medium Term Scheduling）：从外存中挂起的进程中选择进程调入内存；仍在等待事件的进程继续处于阻塞状态。
- 长程调度（LTS, Long Term Scheduling）：从外存中选择一个作业送到内存中，为其创建进程，并加入就绪队列。
调度准则（Scheduling Criteria）
调度的基本准则分为面向用户和面向系统两方面。
面向用户准则包括：
- 响应时间（response time）快：一般采用响应时间作为衡量调度算法的重要准则之一。从用户角度看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。
- 周转时间（turnaround time）短：周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。通常把周转时间的长短作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。
- 截止时间（deadline）的保证：截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间。截止时间是用于评价实时系统性能的重要指标。
- 优先权（priority）准则：让某些紧急的作业能得到及时处理，在要求较严格的场合，往往还须选择抢占式调度方式（preemptive），才能保证紧急作业得到及时处理。
面向系统准则包括：
- 系统吞吐量（throughput）高：吞吐量是指在单位时间内系统所完成的作业数。
- 处理机利用率高：处理机利用率是衡量系统性能的重要指标。
- 各类资源的平衡利用：有效地利用其他各类资源，如内存、外存和I/O设备等。
- 公平性（fairness）：不能让某一些进程遭受饥饿。
知识测验
决策模式（Decision Mode）
OS调度算法的决策模式分为非抢占式（nonpreemptive）和抢占式（preemptive）。
- 非抢占式：一个进程一旦开始执行就会占用处理机，直到进程结束、发生阻塞或主动让出CPU。非抢占式主要用于批处理系统。
- 抢占式：当前正在运行的进程可以被打断，并转移到就绪态，可防止单一进程长时间独占CPU。抢占式主要用于实时系统以及性能要求较高的批处理系统和分时系统。
先来先服务（FCFS, First Come First Served）
最简单的CPU调度算法是FCFS算法，FCFS策略可以通过FIFO队列容易地实现。当一个进程进入就绪队列时，它的PCB会被链接到队列尾部。当CPU空闲时，它会分配给位于队列头部的进程，并且将这个进程从队列中移去。
FCFS策略的缺点是平均等待时间往往很长。
假设有一组进程，它们在时间0到达：
| 进程 | 执行时间（ms） |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
如果按P1、P2、P3的顺序进入队列，执行时间线为P1 [0,24) → P2 [24,27) → P3 [27,30)。
进程P1的等待时间为0，进程P2的等待时间为24，而进程P3的等待时间为27。因此，平均等待时间为 ms。
不过，如果按P2、P3、P1的顺序进入队列，执行时间线为P2 [0,3) → P3 [3,6) → P1 [6,30)。
现在平均等待时间为 ms，这个减少是相当大的。
FCFS算法特点如下：
- 算法思想：主要从排队顺序的公平性考虑。
- 算法规则：按照进程到达的先后顺序进行服务。
- 决策模式：非抢占式。
- 优点：按队列顺序服务、算法实现简单。
- 缺点：排在长作业后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。
先来先服务：从队首进入CPU
解锁完整互动实验、进阶解析与精选参考答案。
先来先服务：画出新队列的执行时间线
所有进程在0时刻到达，按P1、P2、P3顺序入队。单CPU，无I/O，忽略切换开销。
| 进程 | 到达A（ms） | 执行B（ms） |
|---|---|---|
| P1 | 0 | 12 |
| P2 | 0 | 4 |
| P3 | 0 | 2 |
- 画出FCFS甘特图，标注每段的开始与完成时刻。
- 计算各进程等待时间及平均等待时间。
最短作业优先（SJF, Shortest Job First）
在执行长度已知、进程同时到达且不计切换开销时，SJF算法使平均等待时间最小。通过将短进程移到长进程之前，短进程的等待时间减少大于长进程的等待时间增加，因而平均等待时间减少。
SJF算法的真正困难是如何知道下次CPU执行的长度。一种方法是预测下一个CPU执行的长度，可以认为下一个CPU执行的长度与以前的相似。因此，通过计算下一个CPU执行长度的近似值，可以选择具有预测最短CPU执行的进程来运行。
SJF算法可以是抢占或非抢占的。当一个新进程到达就绪队列而以前进程正在执行时，就需要选择了。新进程的下次CPU执行，与当前运行进程的尚未完成的CPU执行相比，可能还要小。抢占SJF算法会抢占当前运行进程，而非抢占SJF算法会允许当前运行进程先完成CPU执行。抢占SJF调度称为最短剩余时间优先调度（Shortest Remaining Time First）。
假设有一组进程：
| 进程 | 到达 | 执行长度 |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
使用抢占SJF调度，执行时间线为P1 [0,1) → P2 [1,5) → P4 [5,10) → P1 [10,17) → P3 [17,26)。
进程P1在时间0开始，因为这时只有进程P1。进程P2在时间1到达。进程P1剩余时间（7 ms）大于进程P2需要的时间（4 ms），因此进程P1被抢占，而进程P2被调度。
抢占SJF调度的平均等待时间为 ms。
如果使用非抢占SJF调度，平均等待时间为7.75 ms。
最短作业优先：新进程到达时比较长度
解锁完整互动实验、进阶解析与精选参考答案。
最短作业优先：新进程到达时要不要抢占？
单CPU，无I/O，忽略切换开销；同长度优先选择先到者，再按P1、P2、P3、P4顺序选择。
| 进程 | 到达A（ms） | 执行B（ms） |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 1 | 3 |
| P3 | 2 | 6 |
| P4 | 3 | 2 |
- 为这组进程分别画出非抢占SJF与抢占SRTF甘特图。
- 分别计算各进程等待时间及平均等待时间，说明t=1时的决策。
知识测验
优先级调度（Priority Scheduling）
优先级调度算法的原理是给每个进程赋予一个优先级，每次需要进程切换时，找一个优先级最高的进程进行调度。给长进程较高优先级可以减少它被短进程持续推迟的情况，但低优先级进程仍可能饥饿（starvation）。
优先级调度的优点是可以赋予重要的进程高优先级以确保重要任务能够得到CPU时间。其缺点是低优先级的进程可能会饥饿。可以动态地调节优先级，例如，在一个进程执行特定CPU时间后降低其优先级，或者提高等待进程的优先级。这样，等待时间很长的进程可以因优先级持续提升而得到CPU时间。
假设有一组进程，均在时间0到达，数值越小优先级越高：
| 进程 | 执行时间（ms） | 优先级 |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 1 | 5 |
| P5 | 5 | 2 |
执行时间线为P2 [0,1) → P5 [1,6) → P1 [6,16) → P3 [16,18) → P4 [18,19)；由于全部同时到达，抢占与非抢占策略在此例中的结果相同。
平均等待时间为 ms。
优先级调度：最高优先级先进入CPU
解锁完整互动实验、进阶解析与精选参考答案。
优先级调度：安排四个就绪进程
所有进程在0时刻到达，采用非抢占优先级调度，数字越小优先级越高。忽略I/O与切换开销。
| 进程 | 到达A（ms） | 执行B（ms） | 优先级 |
|---|---|---|---|
| P1 | 0 | 6 | 3 |
| P2 | 0 | 2 | 1 |
| P3 | 0 | 4 | 4 |
| P4 | 0 | 3 | 2 |
- 确定执行顺序，画出标注区间边界的甘特图。
- 计算各进程等待时间及平均等待时间。
轮转调度（RR, Round Robin）
RR调度算法是专门为分时系统设计的，它类似于FCFS调度，但是增加了抢占以切换进程。RR算法中，将一个较小时间单元定义为时间量（time quantum）或时间片（time slice）。时间片大小取决于系统，10至100 ms是传统示例范围。
就绪队列作为循环队列，CPU调度程序循环整个就绪队列，为每个进程分配不超过一个时间片的CPU。
有两种情况可能发生：
- 进程可能只需少于时间片的CPU执行：进程本身会释放CPU，调度程序接着处理就绪队列的下一个进程。
- 当前运行进程的CPU执行大于一个时间片：时间片用完，进行上下文切换，再将进程加到就绪队列的尾部，接着CPU调度程序会选择就绪队列内的下一个进程。
采用RR策略的平均等待时间可能较长，具体取决于工作负载和时间片大小。
假设有一组进程，它们在时间0到达：
| 进程 | 执行时间（ms） |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
如果使用4 ms的时间片，那么P1会执行最初的4 ms。由于它还需要20 ms，所以在第一个时间片之后它会被抢占，而CPU就交给队列中的下一个进程。由于P2不需要4 ms，所以在其时间片用完之前就会退出。CPU接着交给下一个进程P3。在每个进程都得到了一个时间片之后，CPU又交给进程P1继续执行。
执行时间线为P1 [0,4) → P2 [4,7) → P3 [7,10) → P1 [10,14) → P1 [14,18) → P1 [18,22) → P1 [22,26) → P1 [26,30)。
平均等待时间为 ms。
RR算法的性能很大程度取决于时间片的大小。如果时间片很大，那么RR算法与FCFS算法一样。相反，如果时间片很小，那么RR算法会导致大量的上下文切换。
轮转调度：时间片用完，回到队尾
解锁完整互动实验、进阶解析与精选参考答案。
轮转调度：追踪3 ms时间片
所有进程在0时刻按P1、P2、P3顺序入队。时间片3 ms，单CPU，无I/O，忽略切换开销。
| 进程 | 到达A（ms） | 执行B（ms） |
|---|---|---|
| P1 | 0 | 9 |
| P2 | 0 | 4 |
| P3 | 0 | 2 |
- 画出甘特图，保留每个时间片边界，包括提前完成的短片段。
- 求出各完成时刻，再计算各进程等待时间及平均等待时间。