调度：引言

工作负载的简化假设

分析调度策略前，先对作业（有时也称任务）做出一组理想化假设：每项作业运行时长相同、全部同时到达、一旦开始就一直跑到结束、只占用CPU而不做I/O，并且调度器事先知道每项作业的精确运行时间。这些假设并不符合真实系统，但能让我们先看清每种策略的核心行为，再逐步放宽它们。

调度指标：周转时间

比较不同策略需要一个明确的度量。本章主要采用周转时间：作业完成时刻减去它到达系统的时刻。在目前所有作业同时到达的设定下，周转时间就等于完成时间。周转时间衡量性能；公平性是另一类关心点，二者常常互相冲突。

先进先出及其护航问题

最朴素的策略是先进先出（也称先来先服务）：作业按到达顺序依次运行完毕。当所有作业长度相同时它表现不错。一旦出现一个很长的作业排在前面，后面许多短作业就被迫长时间等待，平均周转时间急剧变差，这种现象称为护航效应。

最短作业优先

最短作业优先总是挑选当前剩余运行时间最短的作业来执行。在所有作业同时到达的前提下，它能把平均周转时间降到最低，并且在给定假设下是最优策略。一旦作业可以在任意时刻到达，纯最短作业优先就会暴露新的问题，需要后续章节继续放松假设。

常见误区

• 以为先进先出在作业长度不等时仍然高效
• 忽略长作业挡在短作业前面所造成的护航效应
• 误认为真实调度器总能预先获知每项作业的精确运行时间

最低标准 C11 · 完整程序 · 下载 .c

#include <stdio.h>

int main(void) {
    /* FIFO: A=100, B=10, C=10, order A then B then C */
    int fifo_a = 100;
    int fifo_b = 100 + 10;
    int fifo_c = 110 + 10;
    double fifo_avg = (fifo_a + fifo_b + fifo_c) / 3.0;
    printf("FIFO average turnaround: %.2f\n", fifo_avg);

    /* SJF: shortest first, B then C then A */
    int sjf_b = 10;
    int sjf_c = 10 + 10;
    int sjf_a = 20 + 100;
    double sjf_avg = (sjf_a + sjf_b + sjf_c) / 3.0;
    printf("SJF average turnaround: %.2f\n", sjf_avg);

    return 0;
}

在本地编译

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-07-cpu-scheduling.c -o example && ./example

预期结果

FIFO average turnaround: 110.00
SJF average turnaround: 50.00

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

三个作业A、B、C同时到达，运行时间分别为100秒、10秒、10秒。若FIFO按A-B-C顺序执行，SJF按最短优先执行，分别计算它们的平均周转时间。

继续查证

• OSTEP chapter PDF

标准草案与官方章节会更新；版本标记只说明示例最低要求。