CPU调度：三级调度与经典算法

本篇对应王道第二章下半（原 09 篇）。两个问题贯穿：为什么要进行处理机调度（进程比 CPU 多，不抢不行）、调度算法有哪些、适用什么情况。

一、调度的概念与层次

调度就是资源怎么公平高效地分配，处理机调度就是 CPU 怎么公平高效地分配。多道程序系统中进程数量往往多于处理机个数，争用在所难免——从就绪队列中按一定算法选一个进程，把处理机分配给它，就是处理机调度。

一个作业从提交到完成，要经历三级调度：

层次	又名	干什么	备注
高级调度	作业调度	从外存后备队列挑作业，分配内存等资源、建立进程	内存与辅存之间的调度；每个作业只调入一次调出一次
中级调度	内存调度	暂时不运行的进程调到外存（挂起态），条件好了再调回	提高内存利用率和吞吐量；本质是存储器管理的对换功能
低级调度	进程调度	从就绪队列选一个进程，分配 CPU	最基本、所有 OS 必须配置；频率最高，几十毫秒一次

我自己梳理的三层画面感：外存里有 n 个程序同时要运行——要执行就得读入内存，所以第一层调度决定让哪些程序先进内存建立进程；但不需要整个程序都读进来，用一部分换一部分（虚拟内存那套），有些进程暂时执行不了还占着内存就是浪费空间，挂到外存去，能用了再调回来排队，这是第二层；第三层就发生在 CPU 和就绪队列之间——进程 PCB 里记着优先级，说明就绪队列不一定是先进先出，谁先上 CPU 是第三层要考虑的事。

几条关系：

作业调度为进程活动做准备，进程调度使进程正常活动起来
中级调度夹在两者之间，负责挂起/激活
频率：作业调度最少 < 中级调度 < 进程调度最高
进程调度是最基本的，不可或缺

二、调度算法好不好，看什么指标

指标	定义	备注
CPU 利用率	忙碌时间 / 总时间	CPU 是最贵资源之一，要让它保持忙
系统吞吐量	单位时间内完成的作业数量	长作业拉低、短作业拉高
周转时间	提交到完成的全过程时间（等待+排队+运行+IO）	带权周转时间 = 周转时间 / 实际运行时间
等待时间	处于等待处理机状态的时间之和	调度算法只影响它（执行和 IO 的时间它管不着），所以衡量优劣主要看等待时间
响应时间	提交请求到首次产生响应的时间	交互式系统用这个衡量，周转时间不是好准则

周转时间公式：

想让一个算法满足所有用户和系统要求几乎不可能：既要照顾特定进程的快速响应（实时/交互），又要整体效率（平均周转时间短），还要考虑调度本身的开销。

三、调度的实现

调度程序三部件

排队器：把就绪进程按策略排成队列；进程变就绪时由它插入相应队列
分派器：按调度程序的选择，把进程从就绪队列取出、分配 CPU
上下文切换器：切换时要两对上下文切换——第一对：旧进程上下文存回 PCB → 装入分派程序上下文（让分派程序跑起来）；第二对：移出分派程序上下文 → 装入新进程的 CPU 现场

上下文切换要执行大量 load/store 指令保存寄存器，很费时间。硬件优化思路：两组寄存器（内核一组用户一组），切换时只需改变指针指向当前寄存器组。

调度时机：什么时候能换人

想象 OS 是个忙碌的办公室经理，决定哪位员工（进程）用电脑（CPU）。请求调度的事件：时间片到期、进程阻塞、进程终止、更高优先级进程就绪……

三种情况不能调度和切换：

处理中断的过程中——紧急事件要快速响应，不属于任何进程的运行范畴
进程在操作系统内核临界区中——加锁独占访问，切走会访问冲突
执行原子操作时（加锁、解锁、中断现场保护）——必须完全屏蔽中断，不能停

可以调度的情况：当前进程无法继续执行时（阻塞/终止）立即调度；中断/自陷处理完成后、返回用户态之前，若设了请求调度标志则调度。

盲点辨析：进程处于临界区≠不能调度。进程在临界区说明它正占着处理机，只要不破坏临界资源的使用规则就不影响调度——比如进程访问打印机这种慢速外设时，若不能调度，系统性能会非常差。不能调度的是内核临界区，不是普通临界区。

抢占与非抢占

进程在 CPU 上跑着，来了个更重要的进程，给不给？

非抢占（非剥夺）：让当前进程跑完或阻塞，才轮到别人。像在优先队列里操作——新事件优先级再高也只能排队，等当前的做完取队头。实现简单、开销小，适合批处理系统；不能用于分时和实时系统
抢占（剥夺）：允许暂停当前进程，把 CPU 给更重要的。对吞吐量和响应效率好处明显，但抢占要有原则：优先权、短进程优先、时间片

闲逛进程

就绪队列空了怎么办？调度闲逛进程（idle）运行：优先级最低，没有就绪进程时才跑；不需要 CPU 之外的资源，所以不会被阻塞；一直在跑、顺便测试中断，只要有进程就绪立刻让位。

线程的调度

用户级线程：内核不知道线程存在，照旧选进程、给时间，进程自己的调度程序决定跑哪个线程；同进程内线程切换只需少量机器指令
内核级线程：内核直接选线程（通常不考虑它属于哪个进程），给时间片，超时强制挂起；切换需要完整上下文切换、修改内存映像、高速缓存失效——若干数量级的延迟

四、经典调度算法

FCFS：先来先服务

最简单直观，作业调度和进程调度都可用：按到达顺序排队，谁先来谁先跑，跑到完成或阻塞才释放 CPU。

表面公平，实际有坑——购物结账：前面的人买了两车东西，你只买一盒口香糖，明明一眨眼的事，却要等两车加一件的时间。这不是欺负人吗。

特点：算法简单但效率低；对长作业有利、对短作业不利（长作业先来就拖死后面一堆短作业）；有利于 CPU 繁忙型作业（跑起来不被打断），不利于 IO 繁忙型作业（等 IO 期间 CPU 干等着别人也用不上）。不能作为分时/实时系统的主策略，但常被结合使用——优先级调度里，同优先级的进程往往按 FCFS 处理。

SJF：短作业优先

从后备/就绪队列里选估计运行时间最短的，立即执行直到完成或阻塞。

还是超市的例子：买了两车的人看你只有一件让你先扫，后面又来一群一两件的，让一个两个可以，数量一多，买两车的人也会不情愿——根本让不完，这就是饥饿现象。

三个缺点：

对长作业不利 → 饥饿
完全未考虑紧迫程度，紧急作业可能被晾着
运行时间靠用户估计，用户会有意无意报短——不一定真短

但它是平均等待时间、平均周转时间最短的算法（证明见盲点）。

自己写过一个 SPF 的 C 实现，链表 + 每次找当前时间已到达的最短作业：

#include<stdio.h>
#include<stdlib.h>

typedef struct pro {
    int num;
    int arriveTime;
    int burst;
    struct pro *next;
} process;

process* create_process(int num, int arriveTime, int burst) {
    process *new_process = (process*)malloc(sizeof(process));
    if(new_process) {
        new_process->num = num;
        new_process->arriveTime = arriveTime;
        new_process->burst = burst;
        new_process->next = NULL;
    }
    return new_process;
}

process* find_shortest_job(process *head, int currentTime) {
    process *prev = head;
    process *selected_prev = NULL;
    int shortest_burst = __INT_MAX__;
    while(prev->next != NULL) {
        if(prev->next->arriveTime <= currentTime && prev->next->burst < shortest_burst) {
            shortest_burst = prev->next->burst;
            selected_prev = prev;
        }
        prev = prev->next;
    }
    return selected_prev;
}

void delete_process(process *prev) {
    if(prev != NULL && prev->next != NULL) {
        process *to_delete = prev->next;
        prev->next = to_delete->next;
        free(to_delete);
    }
}

int getCount(process *head, int currentTime) {
    int count = 0;
    process *current = head->next;
    while (current != NULL) {
        if (current->arriveTime <= currentTime) count++;
        current = current->next;
    }
    return count;
}

void spf(process *head) {
    int currentTime = 0;
    while(head->next != NULL) {
        if(getCount(head, currentTime) == 0) {
            currentTime++;
        } else {
            process *selected_prev = find_shortest_job(head, currentTime);
            if(selected_prev != NULL) {
                process *selected = selected_prev->next;
                printf("进程名：%d 到达：%d 响应时间：%d\n",
                       selected->num, selected->arriveTime,
                       currentTime - selected->arriveTime);
                printf("开始：%d", currentTime);
                currentTime += selected->burst;
                printf(" 结束：%d 周转时间：%d\n",
                       currentTime, currentTime - selected->arriveTime);
                delete_process(selected_prev);
            }
        }
    }
}

int main() {
    process *head = create_process(-1, -1, -1);
    process *tail = head;
    int num, arrive, burst;
    printf("请输入进程名、到达时间、运行时间，用逗号隔开，输入-1结束：\n");
    while(scanf("%d,%d,%d", &num, &arrive, &burst) == 3 && num != -1) {
        tail->next = create_process(num, arrive, burst);
        tail = tail->next;
    }
    spf(head);
    process *curr = head;
    while(curr != NULL) {
        process *temp = curr;
        curr = curr->next;
        free(temp);
    }
    return 0;
}

优先级调度

既可用于作业调度又可用于进程调度：选优先级最高的。按能否抢占分：

非抢占式：正在跑的进程不受后来高优先级影响，直到自己让出
抢占式：更高优先级一来，立即暂停当前进程

按创建后能否改变分：静态优先级（创建时定死，依据进程类型、资源要求、用户要求）和动态优先级（运行中调整，依据占 CPU 长短、等待 CPU 时长）。

设置优先级的经验原则：

系统进程 > 用户进程——管理者理应优先
交互型 > 非交互型（前台 > 后台）——正在跟你交互的当然要快响应
IO 型 > 计算型——IO 设备比 CPU 慢得多，让 IO 型进程先跑，IO 设备能尽早开工，整体效率反而更高

高响应比优先

主要用于作业调度，是 FCFS 和 SJF 的折中。每次调度先算响应比，选最高的：

R = \frac{等待时间 + 要求服务时间}{要求服务时间}

三条推论：

等待时间相同 → 服务时间越短响应比越高 → 照顾短作业（像 SJF）
服务时间相同 → 等得越久响应比越高 → 先来先服务（像 FCFS）
长作业等得足够久，响应比也能涨上去 → 克服饥饿

（小声 bb：之前都是估算确定，现在还得额外计算每个任务的响应比，不凭空多了 n 条进程吗……）

时间片轮转

主要用于分时系统：所有就绪进程按 FCFS 排队，队头进程跑一个时间片（如 5ms），用完必须让出 CPU 回队尾重新排队，下一个上。

（我一开始觉得这队列用 FCFS 还是优先级都无所谓，反正执行时间固定——哦不对，如果是优先队列，再次排队就不是去末尾了，那就不平均了。所以就用普通 FIFO 队列，有先进先出的性质就行。）

时间片大小是命门：

足够大（人人一个时间片内跑完）→ 退化成 FCFS
太小 → 进程间切换过于频繁，开销吃掉有效运行时间

选时间片要考虑：系统响应时间、就绪进程数目、系统处理能力。

多级队列

系统里只设一个就绪队列、用单一算法，满足不了不同用户的口味。多级队列：设多个就绪队列，不同类型进程固定分到不同队列，每队列可用不同算法，队列之间也有优先级。多处理机系统还能给每个处理机配独立队列、各自策略。

多级反馈队列：统筹兼顾

时间片轮转和优先级调度的综合与发展，动态调整优先级和时间片，兼顾多方面目标——照顾短进程（吞吐量、周转时间）、照顾 IO 型进程（设备利用率、响应时间），还不用事先估计执行时间。

规则：

设多个就绪队列，优先级第 1 级最高、依次递减；优先级越高的队列时间片越小（第 i+1 级时间片一般是第 i 级的 2 倍）
新进程先进第 1 级队列末尾，按 FCFS 等待；轮到时能在时间片内完成就撤离，完不成 → 降到第 2 级队列末尾，以此类推
降到第 n 级（最低级）后，在第 n 级里用时间片轮转跑
按队列优先级调度：第 1 级空了才跑第 2 级……第 i 级空了才跑第 i+1 级
处理机在跑第 i 级进程时，只要有任何更高优先级队列来了新进程 → 立即把当前进程放回第 i 级队尾，CPU 给新的

很巧妙。效果：

终端型作业用户（短作业）：高优先级队列里几个时间片就跑完 → 短作业优先
短批处理作业用户：周转时间较短
长批处理作业用户：在前面队列里已得到部分执行，不会长期得不到处理

统筹兼顾，而不是像前面那些算法一样"if 什么就执行什么"。

各算法总览：

五、进程切换：上下文切换

任何进程都是在操作系统内核支持下运行的，进程切换也一样。

上下文 = 某一时刻 CPU 寄存器和程序计数器的内容。上下文切换 = 内核把旧进程状态存进它的 PCB，再加载新进程的上下文。流程：

挂起当前进程，保存 CPU 上下文（PC + 各寄存器）
更新 PCB 信息，把 PCB 移入相应队列（就绪/某事件阻塞队列）
选择另一个进程执行，更新其 PCB
跳到新进程 PCB 中 PC 指向的位置，恢复处理机上下文

上下文切换是计算密集型的，每秒几十上百次切换、每次纳秒级——所以才有"线程内切换省开销"和"硬件多寄存器组切换"这些优化。

上下文切换 vs 模式切换（容易混）：

模式切换：用户态 ↔ 核心态，CPU 逻辑上还在执行同一个进程（进内核处理完中断又回到该进程），不算上下文切换
上下文切换：换了进程，只能发生在内核态

六、盲点总复习

CPU 繁忙型作业类似长作业，占 CPU 久、很少请求 IO，用 FCFS 可从容完成；IO 繁忙型作业频繁放弃 CPU、占用时间不长，一放弃就得重新排队，用 SJF 合适
为什么 SJF 平均周转时间最短：j1、j2、j3 同时到达，执行时间 t1、t2、t3，按 j1j2j3 顺序跑，周转时间分别是 t1、t1+t2、t1+t2+t3，平均 = (3t1+2t2+t3)/3——先执行的权重更大，要平均最小就把小的数乘大权重，所以短作业先跑
中断向量本身是中断服务程序的入口地址，所以中断向量地址是该入口地址的地址
高响应比不会饥饿：长作业等待时间增加，响应比变大，执行机会增大
调度时机三禁（处理中断、内核临界区、原子操作）≠ 进程在（普通）临界区时不能调度——普通临界区访问慢速外设时若禁止调度，系统性能会非常差
计算题画甘特图：横轴时间、纵轴进程，按算法规则一格格画出来，周转时间和等待时间直接从图上数

CPU 分完了，但多个进程要同时碰一份资源怎么办？下一章讲同步与互斥 → 04-同步与互斥

⬅️ 🏠 00-操作系统总览 ➡️ 04-同步与互斥

03-CPU调度：三级调度与经典算法