1.3 - 进程（线程）调度

一篇围绕进程与线程调度展开的学习笔记。

在 进程基础 中已介绍进程状态、就绪队列、调度器和上下文切换；线程基础 补充了线程模型及用户线程与内核线程的区别。本篇将这些概念收拢到调度主题下：谁先运行、运行多久、什么时候切换，以及在多线程、多核和实时系统中如何变化。

• 机制与策略：dispatcher 与 CPU 调度算法（CPU scheduler）
• 调度边界：抢占与非抢占、常见调度指标
• 经典算法：FCFS、SJF/SRTF、优先级调度、RR、多级队列、多级反馈队列
• 线程层调度：PCS、SCS 与 Pthreads 竞争范围
• 多处理器调度：SMP、亲和性、NUMA、负载均衡与硬件多线程
• 实时系统：软实时、硬实时与 POSIX 实时调度 API

经典算法通常以进程为叙述对象；在支持线程的现代系统中，内核真正调度的是内核可见的线程。

调度机制 ​

CPU 是有限资源，多个进程通过调度轮流共享。对进程而言，调度过程透明，每个进程看似连续执行；从操作系统视角看，则是多个进程轮流占用 CPU——调度因此常被视为”CPU 的虚拟化”。

1. 抢占与非抢占 ​

需要做 CPU 调度的典型时机可以压缩成四种：

如果调度只发生在“任务主动让出 CPU”或“任务结束”这类场景，那么这种调度方案就是非抢占式（nonpreemptive），也常被称为协作式（ cooperative）。

如果系统允许一个正在运行的任务在还没完成时被强行切走，例如时间片耗尽或有更高优先级任务到达，那么这种方案就是抢占式（ preemptive）。

两者的差别可以压缩如下：

抢占式调度是现代通用操作系统的主流，因为它更适合交互系统、多任务环境和实时场景；代价则是调度逻辑更复杂，而且共享数据时更容易出现竞争问题。

2. 调度队列 ​

为了完成调度，操作系统通常会维护几类队列。

这里要区分“等待队列”和“设备队列”：

• 等待队列是从 CPU 调度视角看，表示进程暂时不能运行
• 设备队列是从具体设备调度视角看，例如磁盘请求自身也可能排队

如果把队列和状态结合起来，一个进程在生命周期里通常这样迁移：

3. 调度器 ​

调度器（scheduler）负责从队列中选择进程运行，按作用分三类：

短期调度器即 CPU 调度器，是最频繁参与运行时决策的那一个。

4. 上下文切换 ​

进程的上下文是恢复执行所需的状态信息集合。上下文切换的本质是将当前进程 PCB 中的运行信息从 CPU/寄存器保存到内存，再将新进程 PCB 中的信息从内存加载到 CPU/寄存器。

进程上下文通常包括：

一个典型的进程切换过程大致如下：

1. 时钟中断或其他事件发生
2. 硬件先自动保存中断所需的最基本上下文
3. 内核进入中断处理程序或调度路径
4. 内核把当前进程的关键上下文保存到它的 PCB 中
5. 调度器从就绪队列中选出新的进程
6. 内核把新进程 PCB 中的关键上下文重新加载到 CPU
7. 返回后，CPU 从新进程原先停止的位置继续执行

上下文切换本身是有开销的，因此调度策略总是在“响应更快”和“切换次数更少”之间做折中。

5. 中断上下文与进程上下文 ​

中断上下文和进程上下文是两类不同的上下文切换：

时钟中断发生时，两种切换依次发生：硬件先保存中断上下文 → 中断服务程序（调度程序）决定切换进程时处理进程上下文 → 中断退出时硬件恢复中断上下文。

经典调度策略 ​

调度指标 ​

评价一个调度算法时，常见指标有下面几项：

若用 $X_i$ 表示第 i 个任务在某个指标上的取值，那么平均值与方差通常写成：

批处理系统更在意吞吐量和平均周转时间，交互系统更在意响应时间均值或方差，实时系统更在意最坏情况。因此，调度算法讨论的不只是平均值，还包括波动和尾部表现。

1. 先来先服务 ​

先来先服务（FCFS, First-Come First-Served）按进入就绪队列的先后顺序分配 CPU。

FCFS 通常是非抢占式的。它最大的问题是护航效应（convoy effect）：一个 CPU 密集型长任务排在前面时，只有主动放弃CPU时，其他任务才可执行。这也是非抢占式调度的通病。

2. SJF 与 SRTF ​

最短作业优先（SJF, Shortest Job First）优先选择预计 CPU 执行时间最短的任务；它的抢占式版本通常称为最短剩余时间优先（ SRTF, Shortest Remaining Time First）。

SJF 的重要性质是：如果已知每个任务的下一次 CPU 执行时间，它能够把平均等待时间压到最优。

但实际系统很难事先精确知道“未来还要跑多久”，因此通常只能根据历史 burst 长度做预测，而不能真正精确实现教材里的理想 SJF。

3. 优先级调度 ​

优先级调度会先运行优先级最高的任务。SJF 其实可以视为它的一个特例，只不过这里的“优先级”由预计 CPU 执行时间导出而已。

老化的思路很直接：一个任务等得越久，就逐渐提高它的优先级，避免饥饿。

4. 时间片轮转 ​

时间片轮转（RR, Round-Robin）给每个任务一个固定时间片（time quantum）；时间片用完但任务还没结束，就把它放回就绪队列尾部。

RR 的效果很大程度上取决于时间片长度：时间片太短，切换开销高；时间片太长，则会退化成 FCFS。它的核心价值是用可控的时间片换取交互响应。

5. 多级队列 ​

多级队列（multilevel queue）适合就绪任务天然可以分组的场景，例如前台交互任务与后台批处理任务。

它的关键点有两个：

这种方法的优点是结构清晰，可以针对不同类型任务使用不同策略；缺点是灵活性不高，因为任务通常一进入某个队列后，就不会再迁移。

6. 多级反馈队列 ​

多级反馈队列（MLFQ, Multilevel Feedback Queue）允许任务在不同优先级队列之间迁移，因此比多级队列更灵活。

它的基本规则可以压缩成下面这张表：

MLFQ 没有单一固定版本，它更像一类可配置框架。要真正定义一个 MLFQ，通常还要说明：

正因为它足够灵活，MLFQ 很适合通用操作系统；但也正因为参数多，它比前面几种算法更难调试。

线程调度 ​

1. 操作系统真正调度谁 ​

在线程语境下，内核直接调度的是内核可见的执行实体（内核线程或 LWP），不是用户态线程库里的抽象线程。

如果系统采用多对一或多对多模型，用户线程必须先映射到某种内核可见实体上，例如内核线程或 LWP；只有映射后的实体，才会真正被内核分派到 CPU 上运行。

2. PCS 与 SCS ​

线程调度里有两个关键术语：

在 Linux、macOS、Windows 这类主流系统上，用户常见到的 Pthreads 实现通常采用一对一模型，因此实际看到的主要是 SCS。

3. Pthreads 竞争范围 API ​

Pthreads 提供了竞争范围相关的属性接口：

int pthread_attr_setscope(pthread_attr_t *attr, int contentionscope);
int pthread_attr_getscope(const pthread_attr_t *attr, int *contentionscope);

可用的竞争范围值主要有两个：

最小示例如下：

#include <pthread.h>

pthread_attr_t attr;
int scope;

pthread_attr_init(&attr);
pthread_attr_getscope(&attr, &scope);
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);

这里要特别注意一个现实约束：虽然 POSIX 标准定义了两种 scope，但在很多主流 Unix-like 系统上，实际只支持 PTHREAD_SCOPE_SYSTEM。因此，setscope 是否成功，最终还要看平台实现。

多处理器调度 ​

1. 硬件概念 ​

多处理器调度中的硬件概念主要包含多处理器与多核、多线程核与单线程核、多线程核上的硬件线程以及硬件整体暴露给软件的逻辑处理器。

处理器与核：

多处理器与多核：

传统的单线程核上，只能执行一个线程，当此线程访问内存时，若缓存未命中，将消耗大量时间，因此，多线程核支持多个硬件线程，以在耗时等待发生时切换其他线程。

硬件线程与逻辑处理器：

单线程核通常只对应一个逻辑处理器；多线程核可以暴露多个逻辑处理器。

2. 非对称与对称多处理 ​

多处理器系统里，调度方式大体可以分成两类：

SMP 下有两种常见组织方式：

• 多个处理器共享一个就绪队列
• 每个处理器维护自己的本地就绪队列

共享队列更直观，但并发访问队列时同步开销较大；私有队列更适合扩展，但又需要额外的负载均衡机制。

3. 处理器亲和性与 NUMA ​

一个任务如果持续运行在同一个处理器上，它最近访问的数据更可能还留在该处理器的缓存里。因此，随意把任务迁到别的处理器，会导致缓存重新填充，代价并不低。

这就是处理器亲和性（processor affinity）的背景。

NUMA, Non-Uniform Memory Access 会让这个问题更明显。NUMA 机器上，不同处理器访问不同内存区域的延迟并不一样，因此“任务在哪个 CPU 跑”和“它的数据主要放在哪块内存上”往往需要一起考虑。

换句话说，亲和性不只是缓存问题，也常常与内存拓扑绑在一起。

4. 负载均衡 ​

如果某些处理器很忙，而另一些处理器长期空闲，多处理器的好处就发挥不出来。因此 SMP 系统通常需要负载均衡（load balancing）。

两种常见方法如下：

负载均衡与亲和性之间天然有张力：

• 频繁迁移任务，有利于把负载摊平
• 尽量不迁移任务，有利于缓存和局部性

因此实际系统通常会在“处理器不要太闲”和“任务不要乱跑”之间折中。

5. 多核与硬件多线程 ​

现代处理器不仅有多个核，一个核里还可能有多个硬件线程。引入硬件多线程的一个重要动机，是隐藏内存停顿（memory stall）。

当一个线程因为缓存未命中而长时间等数据时，核心并不一定非得空转；如果它还能快速切到另一个硬件线程继续执行，就能提高执行单元利用率。

这意味着多核加硬件多线程的系统，实际存在两个层面的“调度”：

因此，“线程很多就一定能线性加速”并不成立。一个物理核心上的多个逻辑处理器，往往共享部分执行资源，它更像是在提高资源利用率，而不是简单地把核心数翻倍。

6. 小结 ​

线程模型、PCS/SCS 和多核硬件三个层次总结如下：

因此，用户线程并不会直接在“物理核心”上执行；中间至少还隔着一层内核可见执行实体，而在多线程核的机器上， 内核可见执行实体最后分配到逻辑处理器上，还需要由处理器核结经过硬件调度后才能实际执行。

实时调度 ​

1. 软实时与硬实时 ​

实时系统的重点不是“平均速度快”，而是“能否在需要的时候及时完成”。

因此，软实时更像“尽量优先”，硬实时则是“必须按时”。通用桌面系统和服务器系统通常只提供软实时能力；工业控制、飞控、刹车控制这类系统才会严格关注硬实时。

2. 事件延迟、中断延迟与调度延迟 ​

实时系统通常是事件驱动的。一个事件从发生到被真正处理，中间经历的总时间称为事件延迟（event latency）。

影响事件延迟的两个关键部分如下：

对实时系统来说，两者都越小越好，而且对硬实时系统而言，往往还要求它们是可界定的，而不只是“平均很小”。

3. 抢占的优先级调度与软实时 ​

实时任务希望一旦变为就绪，就能尽快拿到 CPU。因此实时系统通常至少要支持抢占式、基于优先级的调度。

这个要求可以概括成一句话：高优先级实时任务一旦到达，低优先级普通任务就应该立刻让位。

不过，这种能力本身只够构成软实时，而不是硬实时。要做到硬实时，系统还需要对任务的处理时间、周期、截止期限和准入控制做更严格的建模。

4. 硬实时中的几种典型算法 ​

教材中常见的硬实时调度方法有三类：

RM 的一个重要性质是：它是静态优先级算法里的经典方案，但并不能总把 CPU 利用率压到 100%。对于 n 个周期任务，它的一个常见可调度性上界是：

当 n 很大时，这个上界大约收敛到 0.69；也就是说，RM 很稳健，但并不是把 CPU “榨干”的算法。

EDF 的优先级是动态变化的。只要新就绪任务的截止期限更早，它就可以抢占当前任务。理论上，EDF 在忽略切换和中断开销时，可以把可利用率逼近 100%。

比例分享调度则强调“谁拿多少股”，例如某个任务拿到总份额中的 20%，系统就应尽量保证它长期获得大约 20% 的 CPU 时间。它通常还要配合准入控制：若新任务请求的总份额超过系统可提供能力，就不应再接纳。

POSIX 调度 API ​

1. 调度策略 ​

POSIX 扩展定义了几类常见调度策略：

SCHED_FIFO 和 SCHED_RR 的差别主要在同优先级线程之间是否分时：

• SCHED_FIFO 下，一个可运行线程一旦拿到 CPU，通常会一直运行到阻塞、主动让出或被更高优先级线程抢占
• SCHED_RR 下，同优先级线程会轮流获得时间片

Pthreads 提供了线程属性上的策略接口：

int pthread_attr_getschedpolicy(const pthread_attr_t *attr, int *policy);
int pthread_attr_setschedpolicy(pthread_attr_t *attr, int policy);

它们的核心含义很直接：

这里要注意两点：

• 这些函数操作的是线程属性对象 pthread_attr_t，不是“已经运行中的线程”
• policy 只是“采用哪类调度规则”，还不等于完整调度配置

2. 调度优先级 ​

实际使用调度策略时，通常还要配合优先级参数一起看。常见写法是通过 struct sched_param 指定 sched_priority。

int pthread_attr_getschedparam(const pthread_attr_t *attr,
                               struct sched_param *param);
int pthread_attr_setschedparam(pthread_attr_t *attr,
                               const struct sched_param *param);

很多 Unix-like 系统对实时策略和较高优先级还有权限限制。因此，设置这些属性时即使代码写得对，也可能因为权限或平台实现差异而失败。

3. 调度竞争范围 ​

参见Pthreads 竞争范围 API

4. 示例 ​

下面给出一个示例，演示如何在线程属性对象上设置实时调度策略与优先级：

#include <pthread.h>
#include <sched.h>
#include <stdio.h>

void *worker(void *arg) {
    (void)arg;
    return NULL;
}

int main(void) {
    int ret;
    pthread_t tid;
    pthread_attr_t attr;
    struct sched_param param;

    pthread_attr_init(&attr);

    /* 让新线程使用显式指定的调度属性，而不是继承创建者线程的设置 */
    pthread_attr_setinheritsched(&attr, PTHREAD_EXPLICIT_SCHED);

    pthread_attr_setschedpolicy(&attr, SCHED_RR);

    param.sched_priority = 10;
    pthread_attr_setschedparam(&attr, &param);

    ret = pthread_create(&tid, &attr, worker, NULL);
    if (ret != 0) {
        fprintf(stderr, "pthread_create failed: %d\n", ret);
        pthread_attr_destroy(&attr);
        return 1;
    }

    pthread_join(tid, NULL);
    pthread_attr_destroy(&attr);
    return 0;
}

这个例子一般的配置思路如下：

1. 初始化 pthread_attr_t
2. 决定线程应采用显式调度属性还是继承已有属性
3. 设置策略，例如 SCHED_FIFO 或 SCHED_RR
4. 设置优先级参数
5. 用这组属性创建线程

如果平台不支持该策略，或者当前进程没有足够权限，相关函数会返回非零错误码。

小结 ​

调度问题的核心，是在“谁先运行、运行多久、什么时候切换”之间做取舍。

在单处理器语境下，重点是经典 CPU 调度算法及其指标权衡；进入线程语境后，要先分清用户线程、内核线程和 PCS/SCS；进入多核机器后，又要考虑亲和性、NUMA、负载均衡和硬件多线程；到了实时系统，问题则进一步变成“能否在时限前完成”，这已经不只是平均性能问题。

因此，调度并不是一套单独的算法清单，而是贯穿单核、多核、线程模型和实时约束的一整组决策机制。后面继续讨论同步、锁和并发控制时，会看到这些机制又会和“什么时候阻塞、什么时候唤醒”进一步交织在一起。