第 3 周星期二第 2 大节

视频：screen_操作系统与分布式计算_第3周_星期二_第2大节.mp4
字幕：transcripts/第3周_星期二_第2大节.srt

时间轴

[00:37]~[06:21] 上节回顾：PCB、进程内存映像（代码区/数据区/栈区）
[06:21] 三状态模型：就绪态/运行态/阻塞态及转换
[09:09] 五状态模型：+ 新建 (New)/结束 (Terminate)
[10:14] 七状态模型：+ 挂起 (Suspend) — 挂起就绪/挂起等待
[12:22] Linux 进程状态：TASK_RUNNING, TASK_STOPPED, TASK_ZOMBIE, TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE
[16:47] 进程组织方式：线性表/链表/索引表，按状态分队列
[27:47] 原语 (Primitive) 概念——原子操作，不可打断
[30:27] 创建原语流程：分配 PCB→分配内存映像→初始化 PCB 字段→插入就绪队列
[33:12] 进程创建时机（提问王佳）
[38:33] fork() 系统调用详解 + C 代码示例
[43:30] 父子进程关系：浅拷贝 (代码/数据/栈相同)，通过 fork 返回值区分
[56:53] 进程树：root 根进程，树形结构管理
[57:42] 撤销原语：正常结束/异常退出/外界干预，回收资源
[01:01:57] 子孙进程处理：终止或移交给其他进程
[01:02:51] 阻塞原语：运行态→阻塞态，保存现场，插入阻塞队列
[01:04:57] 唤醒原语：中断处理程序调用，阻塞态→就绪态
[01:06:39] 挂起原语：内存→外存；解挂原语：外存→内存
[01:07:37] 模式切换 (用户态/核心态) vs 进程切换 (CPU 在不同进程间切换)
[01:11:43] CPU 调度（低级调度）：选择哪个进程占用 CPU
[01:13:28] 三种调度级别：高级 (作业调度)→中级 (内存调度)→低级 (进程调度)
[01:14:49] 进程调度时机：CPU 空闲/进程主动放弃/中断发生
[01:16:47] 上下文切换：保存/恢复 PCB 中的寄存器、程序计数器、栈指针等现场信息
[01:17:22] 非剥夺式 (Non-preemptive) vs 剥夺式 (Preemptive) 调度
[01:21:04] 引发调度因素：主动放弃 (运行完/I/O 阻塞/等资源) / 被动剥夺 (中断/高优先级/时间片到)
[01:25:51] 调度算法评价指标：CPU 利用率、吞吐量、周转时间、响应时间、公平性
[01:29:37] 周转时间定义：作业提交到完成的时间差
[01:30:29] FCFS 先来先服务：队列实现，非抢占，简单可靠但不利于短作业
[01:33:37] FCFS 实例计算：P1(2h)/P2(1min)/P3(1min)，平均周转时间>>2h
[01:39:37] 银行排队类比：短业务被长业务阻塞，需按业务分窗口优化
[01:43:03] SJF/SPF 短作业优先：理论最优 (平均等待时间最短)，对长作业不公平/饥饿/难以预估运行时间
[01:46:44] 非剥夺式 SPF vs 可剥夺式 SPF 实例计算：P1(7)/P2(4)/P3(1)/P4(4) 不同到达时间
[01:53:06] 可剥夺 SPF 等待时间更短 (3 vs 4) 但频繁切换消耗大
[01:55:01] 优先级调度：静态优先级/动态优先级，可剥夺
[02:00:22] 时间片轮转 (Round Robin)：分时系统，时间片过小→切换开销大，过大→退化为 FCFS
[02:05:51] 多级反馈队列调度：集多种策略优点，动态升降优先级（等待时间升优先/I/O 完成升优先/时间片用完降优先）
[02:14:36] 作业调度方法：FIFO/FCFS, SJF/SPF, 最高响应比优先 (HRRN)
[02:14:47] 作业 vs 进程关系：一个作业涉及多个进程，作业调度=高级调度
[02:17:27] 线程概念引入：轻量级进程，并行粒度更细，同一进程内线程共享地址空间/代码/数据
[02:21:31] 进程内涵改变：进程→资源分配单位，线程→CPU 调度单位
[02:22:32] 进程与线程关系：一个进程含多个线程，各有 TCB/栈/寄存器，共享代码和数据
[02:25:08] 线程状态继承：就绪/运行/阻塞等状态迁移到线程
[02:25:22] Linux 不严格区分进程和线程，统一作 task 调度

关键点

考勤/签到/小测

课堂互动：提问 ” 陈一磊 ” 数组 vs 链表区别
提问 ” 王佳 ” 什么情况下创建进程

作业

PPT 内容自行学习，未布置具体作业
课后任务：了解 Linux 内核采用的调度策略

考试/复习重点

三/五/七状态模型及转换
原语概念（原子操作）
fork() 返回值区分父子进程（父进程>0=子进程 PID，子进程=0，失败<0）
浅拷贝：子进程复制父进程代码段/数据段/栈
进程调度三大级别含义
FCFS、SJF/SPF 调度算法计算（非剥夺与可剥夺）
模式切换 vs 进程切换的区别
线程与进程关系
优先级调度、时间片轮转、多级反馈队列基本思想

其他需要回看的片段

[38:33] fork() C 代码讲解
[43:30] 浅拷贝与 fork 返回值区分逻辑
[01:46:44] P1(7)/P2(4)/P3(1)/P4(4) 非剥夺 vs 可剥夺 SPF 计算

知识点详解

进程状态模型

三状态模型（核心）

进程在生命周期中处于三种基本状态：

就绪态 (Ready)：进程已具备所有运行条件，只等 CPU 调度
运行态 (Running)：进程获得 CPU 正在执行
阻塞态 (Blocked/Waiting)：进程因等待 I/O 或事件而暂停，即使有 CPU 也无法执行

状态转换：

就绪→运行：调度程序分配 CPU
运行→就绪：时间片用完（分时系统）
运行→阻塞：请求 I/O 或等待事件
阻塞→就绪：I/O 完成或事件到达（通过中断唤醒）

五状态模型（+ 新建/结束）

在三状态基础上增加：

新建态 (New)：进程刚创建，尚未放入就绪队列
- 新建→就绪：创建完成后放入就绪队列
结束态 (Terminated)：进程已执行完毕或异常终止，正在回收资源
- 运行→结束：执行 exit 或正常结束

七状态模型（+ 挂起）

早期操作系统内存资源有限，需将进程从内存移到外存：

挂起就绪 (Suspend Ready)：就绪态进程被换出到外存
挂起等待 (Suspend Blocked)：阻塞态进程被换出到外存

挂起目的：内存空间不足时，将暂时不运行的进程移到外存，释放内存给活跃进程。挂起相关细节在存储管理章节深入。

Linux 进程状态

Linux 对状态进行重新组织，区别于原理模型的实现：

Linux 状态	说明	对应原理
TASK_RUNNING	就绪态或运行态	就绪 + 运行
TASK_STOPPED	暂停态（调试断点）	—
TASK_ZOMBIE	将死态（已 exit 但资源未回收）	结束过渡态
TASK_INTERRUPTIBLE	浅度睡眠（可被信号唤醒）	阻塞（可唤醒）
TASK_UNINTERRUPTIBLE	深度睡眠（不可被打断）	阻塞（硬等待）

浅度睡眠 (TASK_INTERRUPTIBLE)：进程等待资源/信号，可被唤醒转入就绪
深度睡眠 (TASK_UNINTERRUPTIBLE)：不可被信号打断，需等待特定条件满足（如 I/O 完成）
唤醒机制不同：interruptible 用 wake_up_interruptible，uninterruptible 用 wake_up

进程组织方式

PCB 组织方式：

线性表：按创建顺序存放，简单但搜索效率低
链表队列：按状态分队列（就绪队列/阻塞队列/优先级队列），调度时取队首，效率高
索引表：按状态建立索引表，通过索引指针访问 PCB

就绪队列：按调度规则排序，每次调度取队首。 阻塞队列：按阻塞原因分类，事件到达时到对应队列查找。 current 指针：系统维护一个 current 指针指向当前运行进程的 PCB。

原语（Primitive）

定义：一系列指令组成的程序段，用于完成特定功能，特点是原子性——要么不执行，要么一次性执行完，中途不允许被打断（不允许中断插入）。

进程控制原语：

创建原语 (Create) — 创建新进程
撤销原语 (Destroy) — 终止进程
阻塞原语 (Block) — 运行态→阻塞态
唤醒原语 (Wakeup) — 阻塞态→就绪态
挂起原语 (Suspend) — 内存→外存
激活原语 (Activate) — 外存→内存

创建原语

创建时机（王佳回答）：

系统初始化（开机启动时创建系统进程）
用户登录（为用户创建用户进程）
运行应用程序（每次执行程序→创建进程）
进程主动调用创建新进程（如 fork）

创建流程：

在系统空间申请空白 PCB
分配进程内存映像（代码区、数据区、栈区）
初始化 PCB 字段：进程名、优先级、内存映像起始地址、资源清单、打开文件等
将新进程插入就绪队列

fork() 系统调用（Unix/Linux）

fork() 是 Unix/Linux 中创建进程的系统调用。

返回值：

fork() 返回 pid_t 类型
父进程收到返回值 = 子进程的 PID（>0）
子进程收到返回值 = 0
创建失败返回 -1

代码逻辑：

pid_t pid = fork();
if (pid < 0)    // 创建失败
    exit(1);
else if (pid == 0) {
    // 子进程代码（通过execlp执行具体任务）
    execlp(...);
} else {
    // 父进程代码（通过wait等待子进程完成）
    wait(NULL);
    printf("Child complete");
}

父子进程关系（浅拷贝）

浅拷贝机制：

fork 创建子进程时，子进程的代码段 (code)、数据段 (data)、栈 (stack) 完全复制父进程
父子进程看到的代码完全相同

任务区分：

通过 fork 的返回值不同，父子进程进入不同的分支执行
子进程执行 pid==0 的分支
父进程执行 pid>0 的分支（值为子进程 PID）
父子进程可以并行推进

子进程执行流程：fork() 创建后→执行 execlp 加载新程序→执行完毕调用 exit()→向父进程发送信号 父进程执行流程：调用 wait() 挂起等待→收到子进程完成信号→打印 “Child complete”→结束

进程树

系统启动时创建根进程 (root)
根进程是所有进程的祖先
进程间形成树形关系：父进程创建子进程，子进程再创建孙进程，以此类推
树结构是表达进程代际关系最清晰的数据结构

撤销原语

撤销时机：

正常结束：进程执行完毕
异常退出：访问越界、算术逻辑错误、I/O 设备故障
外界干预：用户在任务管理器中终止进程

撤销流程：

根据 PID 找到 PCB，读取进程当前状态
若进程正在运行（执行态），立即停止，从 CPU 上移除，调度标志置为终止
处理子孙进程：要么全部终止，要么移交给其他进程（不能处于无人监管的游离态）
回收全部资源：打开的文件、占用的内存等，归还给父进程或系统
从 PCB 集合中移除该 PCB

系统调用：

Unix/Linux：exit()
Windows：ExitProcess()

阻塞原语

引发事件：请求系统服务无法立即满足（键盘输入、磁盘读写）、等待其他进程发送消息等

流程（由当前运行进程自己调用）：

将 PCB 状态从运行态改为阻塞态
保存 CPU 运行现场（寄存器、程序计数器等）到 PCB
将 PCB 插入对应阻塞原因的分类队列
转进程调度，选择就绪队列中下一个进程占用 CPU

唤醒原语

由中断处理程序调用（不同于阻塞原语由进程自己调用）
I/O 操作完成→产生中断→中断处理程序调用唤醒原语
将阻塞态进程重新置为就绪态，放入就绪队列

Unix 系统调用：sleep(), pause(), wakeup() 等

挂起原语与解挂原语

挂起：将进程从内存移到外存（释放内存空间），用于内存不足时
解挂：将进程从外存移回内存
应用场景：实时操作系统（内存空间有限）、分时操作系统（暂时不运行的进程换出）

模式切换 vs 进程切换

	模式切换	进程切换
含义	同一进程从用户态切换到核心态（或反之）	CPU 从 A 进程切换到 B 进程
是否涉及 PCB 更换	否	是
典型场景	系统调用、中断处理	时间片用完、I/O 阻塞、高优先级抢占

进程切换流程：

保存当前进程 (P0) 的 PCB 现场（寄存器、程序计数器等）
恢复目标进程 (P1) 的 PCB 现场
开始执行 P1
P1 执行完毕后，保存 P1 现场，恢复 P0 现场
P0 继续执行

CPU 调度级别

高级调度（作业调度）：从外存作业队列中选择作业调入内存，创建进程
中级调度（内存调度）：将进程在内存和外存之间换入换出（与挂起相关）
低级调度（进程调度/CPU 调度）：从就绪队列中选择进程分配 CPU——本课重点

进程调度

调度目的：合理分配有限的 CPU 资源，提高利用率，兼顾公平。

调度时机：

主动放弃：进程运行完毕、进程进入阻塞态 (I/O/等待资源)
被动剥夺：高优先级进程到达、时间片用完、中断处理程序完成唤醒高优先级进程

上下文切换：保存当前进程的 PCB 现场（程序计数器、栈指针、寄存器等），恢复新进程的 PCB 现场。

非剥夺式 vs 剥夺式调度

	非剥夺式 (Non-preemptive)	剥夺式 (Preemptive)
原理	进程主动让出 CPU 后才调度	OS 可强制将 CPU 从运行进程拿走
优点	实现简单，无频繁切换开销	响应及时，适合分时/实时系统
适用	批处理系统	分时系统、实时系统
示例	FCFS、非剥夺 SPF	时间片轮转、可剥夺 SPF、优先级

调度算法评价指标

CPU 利用率：越高越好
吞吐量：单位时间内完成的任务数
周转时间：作业从提交到完成的总时间差
平均周转时间：所有作业周转时间的平均值
响应时间：从提交到首次响应的时间（分时系统关注）
公平性：所有进程都应有机会运行

FCFS（先来先服务）

原理：按到达顺序排队，先到先服务。

数据结构：队列（先进先出）。

特点：

非抢占式
简单、可靠、易于实现
不利于短作业（短作业可能被长作业阻塞很久）
平均等待时间长

计算实例：P1(2h), P2(1min), P3(1min) 按序到达

P1 周转时间=2h
P2 周转时间=2h1min
P3 周转时间=2h2min
平均周转时间 >> 2h
短作业用户不满意，如同银行排队办业务（换号一分钟，排队两小时）

优化思路：将短作业前置可大幅降低平均等待时间。

SJF/SPF（短作业/进程优先）

原理：每次选择预计运行时间最短的进程调度。

特点：

理论最优：平均等待时间最短
对长作业不公平：持续有短进程到达会导致长作业饥饿
实际中难以评估进程运行时间（分支判断导致路径不同）
理论价值：作为一把 ” 尺子 “，衡量其他算法的最优基准

非剥夺式 SPF

P1(7) 到达时间 0, P2(4) 到达时间 2, P3(1) 到达时间 4, P4(4) 到达时间 5：

0 时刻：仅 P1→调度 P1
P1 运行完 (时刻 7)→就绪队列 P2(4), P3(1), P4(4)→选最短 P3
P3 运行完 (时刻 8)→选 P2(4) 或 P4(4)→按 FCFS 先 P2
P2 运行完 (时刻 12)→P4
P4 运行完 (时刻 16)
平均等待时间 = ((0) + (7-2) + (7-4) + (12-5)) / 4 = (0+5+3+7)/4 = 15/4 = 3.75

可剥夺式 SPF（最短剩余时间优先）

P1(7) 到达时间 0, P2(4) 到达时间 2, P3(1) 到达时间 4, P4(4) 到达时间 5：

0 时刻：仅 P1→调度 P1
时刻 2：P2 到达，P1 剩余 5 > P2 需要 4→P1 被剥夺，P2 运行
时刻 4：P3 到达，P2 剩余 2 > P3 需要 1→P2 被剥夺，P3 运行
时刻 5：P3 运行完，P4 到达→就绪队列 P2(2), P1(5), P4(4)→选 P2 运行
时刻 7：P2 运行完→P4(4), P1(5)→选 P4
时刻 11：P4 运行完→P1(5)
时刻 16：P1 运行完
平均等待时间 = ((11-2) + (2-2) + (4-4) + (5-5)) / 4 = (11+0+0+0)/4 = 2.75

比较：可剥夺 SPF 平均等待时间 (2.75) < 非剥夺 SPF(3.75)，但 CPU 切换次数更多，开销更大。

优先级调度

思想：给每个进程赋予优先级，优先级高的先运行。

类型：

静态优先级：创建时确定，运行中不变
动态优先级：根据等待时间、运行时间等动态调整（如等待时间过长则提升优先级）

特点：

必须是可剥夺的，否则优先级失去意义
静态优先级可能导致低优先级进程饥饿
动态优先级更灵活

时间片轮转（Round Robin）

原理：就绪队列按 FCFS 排队，每个进程运行一个时间片后强制让出，下一个进程执行。

时间片设定至关重要：

时间片过大 → 退化为 FCFS
时间片过小 → 频繁上下文切换，开销大
需要有测算依据，平衡切换开销和响应速度

适用：分时操作系统，保证每个用户都感到系统在 ” 为自己服务 “。

多级反馈队列调度

集大成者：综合 FCFS、时间片轮转、优先级调度的优点，为现代通用操作系统（如 Linux）采用。

核心机制：

设置多个优先级队列（优先级从高到低）
同一队列内按 FCFS+ 时间片轮转
CPU 每次从最高优先级非空队列取进程
动态反馈调整优先级：
- 等待 CPU 时间越长 → 升优先级（保证每个进程都有机会运行）
- I/O 完成后回就绪队列 → 升优先级（I/O 密集型进程占用 CPU 短，放行快）
- 时间片运行完 → 降优先级（已获得 CPU 机会，往下放）

特点：实现逻辑复杂，但适应性强、效率高。

作业调度方法

FIFO/FCFS：先来先服务
SJF/SPF：短作业优先
HRRN（最高响应比优先）：响应比 = (等待时间 + 运行时间) / 运行时间 = 1 + 等待时间/运行时间

→ 等待时间越长，响应比越高，越优先运行（动态升优先思想）

线程概念

线程引入原因：

进程是独立资源分配单位，进程间数据共享困难（需开辟公共内存）
多 CPU/多核发展：希望一个进程内部的不同子任务能真正并行
线程使并行粒度更细，提高并行度
上下文切换信息更少，切换效率更高

线程定义：轻量级进程（Light Weight Process），是 CPU 调度的基本单位。

进程与线程关系：

进程→资源分配单位（内存、文件等）
线程→CPU 调度单位
一个进程包含多个线程
同一进程内的线程共享：代码段、公共数据、进程工作区
每个线程独立拥有：TCB（线程控制块）、栈、寄存器

Linux 中的线程：Linux 不严格区分进程和线程，统一作为 task 调度。

Windows 中的线程：通过 CreateProcess 创建进程。

例子：Word 进程包含多个线程——键盘输入接收线程、拼写错误检查线程等。

Notes@Tsukino

探索

第3周_星期二_第2大节

第 3 周 星期二 第 2 大节

时间轴

关键点