📚 课程目录第4章进程控制与调度

4. 进程控制与调度：进程的创建与终止、调度算法与性能指标

进程是操作系统资源分配与独立运行的基本单位。本章深入剖析进程的完整生命周期——从创建（fork/exec）到终止（exit），并系统讲解操作系统如何通过调度算法在多个就绪进程间高效、公平地分配CPU资源。我们将结合xv6与Linux内核的实现，揭示这些核心机制背后的设计哲学。

核心要点：进程管理是操作系统的中枢神经。理解fork/exec的写时复制（COW）机制、进程状态转换模型以及调度算法的权衡（吞吐量 vs 响应时间），是掌握操作系统内核的关键。

4.1 进程的创建与终止：fork/exec/exit 系统调用

在Unix/Linux及xv6中，进程的创建与执行是分离的：fork() 复制当前进程，exec() 加载新程序替换当前进程映像，exit() 终止进程并释放资源。

4.1.1 fork()：进程复制的艺术

fork() 创建一个与父进程几乎完全相同的子进程。子进程获得父进程数据段、堆、栈的副本，但拥有独立的地址空间和PID。xv6的 fork() 实现会复制页表与内存内容；而现代Linux采用写时复制（Copy-on-Write, COW）技术，仅在写入时复制页面，大幅提升性能。

// xv6 fork() 核心逻辑（简化）
int fork(void) {
    struct proc *np;
    // 1. 分配新的进程结构体
    if ((np = allocproc()) == 0) return -1;
    // 2. 复制父进程的内存（xv6 直接复制）
    if (uvmcopy(p->pagetable, np->pagetable, p->sz) < 0) {
        freeproc(np);
        return -1;
    }
    np->sz = p->sz;
    // 3. 复制 trapframe 和 context
    *np->tf = *(p->tf);
    // 4. 设置返回值：子进程返回 0，父进程返回子进程 PID
    np->tf->a0 = 0;  // 子进程返回值
    p->tf->a0 = np->pid; // 父进程返回值
    return np->pid;
}

面试高频题：为什么 fork() 在父进程返回子进程PID，在子进程返回0？答：父进程需要PID来管理子进程（如wait）；子进程通过返回值0知道自己是被创建出来的，从而执行不同的代码路径。

4.1.2 exec()：加载新程序

exec() 系统调用将当前进程的地址空间完全替换为指定可执行文件的新映像。它解析ELF文件格式，分配新页表，加载代码段、数据段，并设置栈和入口点。成功后不返回，直接开始执行新程序。

// xv6 exec() 核心流程（简化）
int exec(char *path, char **argv) {
    struct inode *ip;
    struct elfhdr elf;
    // 1. 打开文件并读取 ELF 头部
    if ((ip = namei(path)) == 0) return -1;
    readi(ip, 0, (uint64)&elf, 0, sizeof(elf));
    // 2. 为新程序分配页表
    pagetable_t pagetable = proc_pagetable(p);
    // 3. 逐段加载 ELF 段到内存
    for (int i = 0; i < elf.phnum; i++) {
        readi(ip, 0, (uint64)&ph, elf.phoff + i*sizeof(ph), sizeof(ph));
        if (ph.type == ELF_PROG_LOAD) {
            // 分配内存并加载数据
            uvmalloc(pagetable, ph.vaddr, ph.vaddr + ph.memsz);
            loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz);
        }
    }
    // 4. 设置用户栈和参数
    // 5. 切换到新页表，释放旧页表
    // 6. 返回，开始执行新程序（不返回原调用处）
}

4.1.3 exit()：进程的善后

进程调用 exit(int status) 终止自身。内核会释放其内存、关闭打开的文件描述符、唤醒等待的父进程，并将进程状态置为 ZOMBIE，直到父进程调用 wait() 回收其PID和退出状态。

注意：僵尸进程（Zombie）是已终止但未被父进程回收的进程。如果父进程不调用 wait()，僵尸进程会一直占用进程表项。孤儿进程（父进程先于子进程退出）会被init进程（PID=1）收养并自动回收。

4.2 进程调度算法

调度算法决定就绪队列中哪个进程获得CPU使用权。不同算法在公平性、吞吐量、响应时间和开销之间做出不同权衡。

4.2.1 先来先服务（FCFS）

最简单的非抢占式算法。进程按到达顺序排队，CPU分配给队首进程直到其完成（或阻塞）。

优点：实现简单，公平（按到达顺序）。
缺点：平均周转时间长，护航效应（Convoy Effect）——一个长CPU突发进程阻塞所有后续短进程。

4.2.2 短作业优先（SJF）

选择预计CPU突发时间最短的进程执行。可以是抢占式（SRTF，最短剩余时间优先）或非抢占式。

优点：理论上平均周转时间最小（最优）。
缺点：难以准确预估进程运行时间；长进程可能饥饿（Starvation）。

4.2.3 轮转调度（RR）

时间片轮转，每个进程获得一个固定长度的时间片（Time Quantum）。时间片耗尽则进程被剥夺CPU，放回就绪队列尾部。

优点：响应时间短，公平，适合分时系统。
缺点：时间片选择是关键——太短导致频繁上下文切换，开销大；太长退化为FCFS。

4.2.4 优先级调度

每个进程关联一个优先级，调度器选择优先级最高的进程执行。可以是抢占式或非抢占式。

静态优先级：创建时确定，简单但可能导致低优先级进程饥饿。
动态优先级：随时间调整（如老化技术 Aging），防止饥饿。

xv6 调度策略：xv6 采用简单的轮转调度（RR），每个时间片约10ms。它在 scheduler() 函数中循环遍历进程表，找到第一个 RUNNABLE 状态的进程并切换执行。Linux 则使用完全公平调度器（CFS），基于虚拟运行时间（vruntime）选择最需要CPU的进程，实现近似完美的公平性。

4.3 调度性能指标

调度算法的优劣通过以下关键指标衡量。理解这些指标是设计、分析和选择调度策略的基础。

指标	定义	计算公式	优化目标
周转时间 (Turnaround Time)	从进程提交到完成的总时间	T_turnaround = T_completion - T_arrival	最小化（提高吞吐量）
响应时间 (Response Time)	从进程提交到首次获得CPU的时间	T_response = T_{first_run} - T_arrival	最小化（提高交互性）
等待时间 (Waiting Time)	进程在就绪队列中等待的总时间	T_waiting = T_turnaround - T_burst	最小化
吞吐量 (Throughput)	单位时间内完成的进程数	Throughput = N_completed / ΔT	最大化
CPU利用率 (CPU Utilization)	CPU处于忙碌状态的时间百分比	Utilization = T_busy / T_total	最大化（避免空闲）

指标权衡：没有完美的调度算法。例如，RR通过频繁切换获得低响应时间，但增加了上下文切换开销，可能降低吞吐量。SJF最小化平均周转时间，但可能导致长进程响应时间极差。设计者必须根据系统目标（批处理、分时、实时）做出取舍。

4.3.1 案例分析：FCFS vs. RR 的响应时间对比

假设三个进程P1（CPU突发24ms）、P2（3ms）、P3（3ms）同时到达。

FCFS：顺序P1→P2→P3。平均周转时间 = (24 + 27 + 30) / 3 = 27ms。P2和P3的响应时间分别为24ms和27ms，交互性差。
RR（时间片=4ms）：P1运行4ms→P2运行3ms→P3运行3ms→P1继续... 平均周转时间 = (30 + 7 + 10) / 3 ≈ 15.7ms。P2和P3的响应时间分别为4ms和7ms，交互性显著提升。

4.4 多级队列与多级反馈队列调度

现代操作系统（如Linux、Windows）通常使用更复杂的调度框架，将进程分类到不同优先级队列，并允许进程在不同队列间移动。

多级队列（MLQ）：进程永久属于一个队列（如系统进程、交互进程、批处理进程），每个队列有自己的调度算法（如RR、FCFS）。队列间有优先级调度。
多级反馈队列（MLFQ）：进程可以在队列间移动。新进程进入最高优先级队列（时间片短），用完时间片后降级到下一级（时间片更长）。这既保证了交互进程的快速响应，又避免了长进程饥饿。

Linux CFS 核心思想：Linux 的完全公平调度器（CFS）不直接使用时间片或优先级队列。它维护一个红黑树，键值为进程的虚拟运行时间（vruntime）。调度器总是选择 vruntime 最小的进程执行，确保所有进程获得近似相等的CPU时间比例。nice值用于调整进程的权重，影响其 vruntime 的增长速度。

4.5 本章小结

进程控制与调度是操作系统最核心的职能之一。通过 fork/exec/exit 系统调用，进程得以创建、执行新程序并有序终止。调度算法决定了系统资源的分配策略：FCFS简单但护航效应严重；SJF理论最优但难以实现；RR提供良好的交互响应；优先级调度灵活但需防饥饿。性能指标（周转时间、响应时间、吞吐量）为评估和选择调度算法提供了量化依据。从xv6的简单轮转到Linux的CFS，调度器的演进体现了对公平性、效率和交互性的不断追求。