操作系统
全书精读
按考研 408 操作系统大纲编排：运行环境、进程与线程、调度、同步与死锁、内存与虚拟内存、文件系统、设备与 I/O。可以少讲，不写错；边界条件写全。
概述与运行环境
LEVEL 1操作系统是管理硬件、向上提供服务的系统软件。本章先钉死四个特征和三种陷入路径，后面各章都站在这张图上。
1.1定义、目标与特征
操作系统管理处理机、内存、设备和文件等资源，为应用程序提供一组接口（命令、系统调用、图形界面等）。教材常用四个特征描述它：
| 特征 | 含义 | 不要写成 |
|---|---|---|
| 并发 | 宏观上多个任务推进；单核交替即可，不要求同一时刻同时执行 | 并发 = 并行。并行是同一时刻实际同时执行；并发不要求并行，二者不是同义词 |
| 共享 | 资源可被多个进程按互斥或同时方式使用 | 共享 = 不需要互斥 |
| 虚拟 | 把一份物理资源表现为多份逻辑资源（虚存、虚处理机、SPOOLing） | 虚拟 = 一定用了虚拟化硬件（VT-x 等） |
| 异步 | 进程推进速度不可预知，靠状态切换与同步协调 | 异步 = 结果不确定（正确程序结果应可预期） |
1.2内核结构
- 大内核 / 单体内核：进程管理、内存、文件、驱动等多在内核态，模块间以函数调用通信，切换开销小；一个模块缺陷可能牵连整个内核。
- 微内核：内核态通常只保留处理机调度、进程间通信、中断处理、基本地址空间等；文件、驱动等作为用户态服务，靠 IPC 交互。隔离较好，跨地址空间通信次数增加。
1.3中断 · 异常 · 系统调用
三者的处理程序均在内核态运行；系统调用由用户态主动陷入，中断/异常则可能在用户态或内核态发生。来源不同：
| 来源 | 与当前指令的关系 | 例子 | |
|---|---|---|---|
| 中断 | 外设等异步事件 | 通常与当前指令无关 | 时钟、磁盘完成、网卡 |
| 异常（内中断） | 执行当前指令引起 | 同步于该指令 | 除零、非法指令、缺页、越界 |
| 系统调用 | 用户程序主动请求服务 | 由 trap / syscall 等指令陷入 | fork、read、mmap |
1.4用户态与内核态
特权指令（关中断、置页表基址、I/O 等）只能在内核态执行。用户态执行特权指令会触发异常。进入内核态的合法路径就是上一节三种，不能「随便跳进内核」。
printf）可能封装系统调用，也可能纯用户态。系统调用要切换特权级、走内核入口；开销和失败语义都不同。不要把「调用了 libc」写成「一定陷入内核」。进程
LEVEL 2进程是资源分配的基本单位。它的存在标志是 PCB；它的可执行实体在引入线程后，通常不再独自充当调度单位。
2.1PCB 与进程映像
PCB（进程控制块）是内核描述进程的数据结构，是进程存在的唯一标志。典型字段：进程标识、状态、程序计数器与寄存器副本、调度信息、内存映像（页表/段表指针）、打开文件、记账与亲缘关系。
进程映像通常包括：程序代码、数据、运行时栈、堆、以及内核中的 PCB。逻辑地址空间对其他进程隔离（共享内存段是显式约定的例外）。
2.2状态转换
三态：运行、就绪、阻塞。五态再加创建、终止。需要时还可扩展挂起（就绪挂起 / 阻塞挂起），把映像换到外存。
2.3进程控制
创建
分配 PID 与 PCB，建立地址空间，装入程序，加入就绪队列。Unix 上常见路径是 fork 复制后再 exec 换映像。
撤销 / 退出
回收用户空间与大部分内核对象，把退出状态留给父进程；在父进程 wait 之前，子进程以僵尸形式保留最小 PCB。
阻塞 / 唤醒
等待 I/O、锁、子进程等时进入阻塞队列；事件到达后移入就绪队列。
切换
保存当前内核上下文（寄存器、内核栈指针），选中下一进程后恢复；若地址空间不同还要切换页表/ASID。详见 图谱 · 上下文切换。
2.4进程通信
- 共享存储：双方映射同一段物理页，自己用锁或信号量协调；内核只建立映射。
- 消息传递：send/receive，直接或经信箱；同步或异步由接口定义。
- 管道：半双工字节流，通常有亲缘关系；容量有限，写满或读空会阻塞（具体语义依实现/标志）。
线程
LEVEL 2408 标准表述：进程是资源分配的基本单位，线程是处理机调度的基本单位。线程共享本进程地址空间，自有栈、寄存器与线程控制块。
3.1资源单位与调度单位
| 进程 | 同进程内的线程 | |
|---|---|---|
| 地址空间 | 独立 | 共享本进程空间 |
| 栈 / PC / 寄存器 | 各有一份 | 各有一份 |
| 打开文件、堆、全局数据 | 每进程一份 | 共享 |
| 切换代价 | 常含地址空间切换 | 同进程内通常更轻 |
3.2用户级 / 内核级
- 用户级线程：内核只看见进程。线程库在用户态调度。一线程阻塞型系统调用，可能卡住同进程其他用户线程（除非库用非阻塞或内核提供额外机制）。
- 内核级线程：内核为每个线程建 TCB，可独立调度。一线程阻塞，同进程其他就绪线程仍可运行。
- 多对一 / 一对一 / 多对多：描述用户线程与内核线程的映射，不是第三种「特权级」。
3.3实现要点
线程切换要保存/恢复该线程的用户寄存器与栈指针。同进程内通常不必换页表；跨进程才换地址空间。同步见 05：共享地址空间让数据竞争成为默认风险。
处理机调度
LEVEL 3调度从就绪队列选出下一个占用 CPU 的进程或线程。它不负责把缺页调入内存，也不等于 I/O 设备调度。
4.1三级调度与抢占
- 高级（作业）调度：选作业进入内存成为进程，控制多道程度。
- 中级（交换）调度：在内存与外存之间挂起/激活，缓解内存压力。
- 低级（进程/线程）调度：分配 CPU。这是分时系统里最频繁的一级。
非抢占：运行进程主动放弃（完成、阻塞、让出）才切换。抢占：时钟中断或更高优先级就绪时，调度器可剥夺当前 CPU。
4.2常用算法
| 算法 | 规则 | 须记住的边界 |
|---|---|---|
| FCFS | 按到达顺序 | 对短作业不友好；非抢占 |
| SJF / SPF | 非抢占，选估计运行时间最短 | 在「同时就绪、服务时间已知」等条件下平均等待最优；可能饥饿；真实系统只能估计 |
| SRTN / SRTF | 抢占式最短剩余时间 | 新的更短作业可抢占；同样依赖估计 |
| 优先级 | 静态或动态优先数 | 可抢占或非抢占；低优先可能饥饿，常用老化缓解 |
| 时间片轮转 RR | 就绪队列轮转，用完时间片到队尾 | 用于分时。时间片过小切换开销大，过大接近 FCFS。不宜写成「最公平」 |
| 多级反馈队列 | 新进程进最高队列；用完本层时间片降级 | 兼顾短作业响应与长作业推进；具体级数与时间片是设计参数 |
4.3指标
带权周转 = 周转 / 实际运行时间
等待时间：无 I/O/阻塞的典型调度题中 = 周转 − CPU 服务；一般情形还须扣除阻塞/I/O 时间，以题面定义为准
吞吐量 = 单位时间完成的作业数。CPU 利用率 = CPU 忙时间 / 总时间。响应时间常指提交到首次运行的间隔（分时语境）。
4.4调度与缺页的边界
缺页异常由内存管理处理：合法页不在内存时陷入内核；有空闲页框则直接调入，无空闲页框才走页面置换。缺页进程常因磁盘 I/O 进入阻塞；此时系统仍可能调度其他就绪进程。处理机调度算法（FCFS/RR/…）并不选择牺牲页。
同步与互斥
LEVEL 3临界资源一次只允许一个进程进入其临界区。同步还要约定执行次序。本节准则不要和死锁四条件混记。
5.1临界区进入准则
- 空闲让进：临界区空闲时，请求者应能进入。
- 忙则等待：已有进程在临界区，其他进程必须等。
- 有限等待：从请求到进入，等待应有上界，避免饥饿。
- 让权等待：等不到时应放弃 CPU，避免忙等浪费（有的实现用自旋，是性能权衡，不满足本条）。
关中断只能约束本 CPU，多处理机不够。测试并置位（TSL）等指令可实现互斥，若循环测试则是忙等。
5.2信号量与管程
信号量上的 P（wait）与 V（signal）必须是原子操作。整型信号量只提供计数；记录型信号量把等待进程链入队列，P 发现值将小于 0 时阻塞，V 时唤醒一个。
V(S): S.value++; 若 S.value ≤ 0 则从 S.queue 唤醒一个
管程把共享数据和操作封装在一起，同时只允许一个进程进入。条件变量上 wait 会释放管程并等待；signal/notify 唤醒等待者。Hoare 与 Mesa 的唤醒语义不同：前者立即把管程交给被唤醒者，后者被唤醒者还要重新竞争——答题注明所用约定。
5.3经典问题
有界缓冲区生产者—消费者常用三个信号量：empty（空槽数）、full（满槽数）、mutex（对缓冲区的互斥）。生产者先 P(empty) 再 P(mutex)；消费者先 P(full) 再 P(mutex)。P 的次序不能对调成先锁再等空槽，否则可能死锁。
读者—写者：多个读者可同时读；写者互斥。哲学家就餐：拿叉顺序或最多允许四人同时拿叉等，用于避免环路。
死锁
LEVEL 4死锁：一组进程中每个都在等待该组内另一进程占有的资源，以至于谁都无法推进。
6.1四个必要条件
- 互斥：资源一次只能分给一个进程。
- 占有并等待：已占有资源的进程还在申请新资源。
- 不可抢占：已分配资源不能被强行收回，只能进程自行释放。
- 循环等待：存在进程—资源循环链。
四条同时成立才可能发生死锁；它们是必要不充分条件。拆掉任意一条，死锁不能成立。四条都在，仍可能只是「有风险」而尚未死锁。
6.2预防 · 避免 · 检测 · 解除
| 策略 | 做法 | 典型手段 |
|---|---|---|
| 预防 | 破坏四个必要条件之一 | 一次性分配、资源有序申请、允许抢占等 |
| 避免 | 分配前检查是否进入不安全状态 | 银行家算法 |
| 检测 | 允许死锁发生，事后发现 | 化简资源分配图；检测算法 |
| 解除 | 打破死锁 | 撤销进程、剥夺资源、回滚 |
6.3银行家算法
每个进程声明最大需求。系统维护：Available、Max、Allocation、Need = Max − Allocation。一次请求若 Need 与 Available 都允许，先试分配，再找安全序列：反复挑选 Need ≤ Work 的进程，把它的 Allocation 加回 Work。找不到含所有未完成进程的序列，则撤回试分配并让该进程等待。
安全状态：存在一个完成序列使每个进程的剩余需求都能被满足。不安全不是已经死锁，只是无法保证一定不死锁。
内存管理
LEVEL 3把逻辑地址变成物理地址，并在多个进程间分配有限的物理内存。固定分区典型产生内碎片，动态分区典型产生外碎片；分页的最后一页可能产生页内碎片。
7.1连续分配
- 单一连续：除操作系统外一次只装一个用户程序。
- 固定分区：分区大小预先划定，内碎片明显。
- 动态分区：按请求切空闲区。首次适应、最佳适应、最坏适应是放置策略。外碎片靠紧凑（移动已分配区）合并。
7.2分页 · 分段 · 段页
| 划分 | 地址 | 碎片 | |
|---|---|---|---|
| 分页 | 等长页 / 页框 | 页号 + 页内偏移 | 内碎片（最后一页） |
| 分段 | 按逻辑段，变长 | 段号 + 段内偏移 | 外碎片 |
| 段页 | 段内再分页 | 段号 + 页号 + 偏移 | 主要是页内碎片 |
页表把页号映射到页框号。多级页表降低连续占用；快表 TLB 缓存近期页表项。段表登记基址与限长，越界则异常。
7.3地址变换
CPU 发出逻辑地址
分页下拆成虚拟页号 VPN 与页内偏移。
查 TLB
命中则直接得页框号；未命中再查页表（可能多级）。
检查页表项
存在（Present）位为 1：页已驻留，拼接物理地址。为 0：只表示未驻留；若本次访问的是合法页，才触发缺页异常。非法地址走保护异常，不是缺页。
虚拟内存
LEVEL 4程序不必全部装入内存即可运行。局部性使请求调页可行；置换只在没有空闲页框时发生。
8.1请求调页
只装入当前需要的页。访问未驻留的合法页产生缺页异常。有效访问时间要计入：TLB 命中、页表命中、缺页（含磁盘）三种路径的加权。
缺页处理代价是否含换出，取决于有没有空闲页框、牺牲页是否为脏
8.2缺页处理的边界
陷入缺页异常
P=0 且访问合法页。P=0 本身只是状态，不是事件。
合法性检查
越界或无权限：错误处理（常终止进程），不是调页。
找页框
有空闲页框则直接分配并调入，不调用置换算法。
无空闲才置换
按 OPT/FIFO/LRU/Clock 等选牺牲页；脏页先写回。
阻塞与调度
等磁盘期间缺页进程通常阻塞。系统仍可能调度其他就绪进程。置换算法 ≠ 处理机调度算法。
8.3置换算法
| 算法 | 选择 | Belady 异常 |
|---|---|---|
| OPT | 未来最久不用 | 无（理论对照） |
| FIFO | 在内存中驻留最久 | 可能有 |
| LRU | 过去最久未用 | 无（栈类算法） |
| Clock / 时钟 | 扫使用位，近似 LRU | 实现相关；不要断言「一定没有」除非题面指定 |
Belady 异常：页框数增加，缺页次数反而增加。FIFO 可能出现；OPT、LRU 作为栈算法不会。
8.4抖动与工作集
分配的物理页框少于进程的工作集时，会频繁缺页，CPU 大量时间花在换页上，称为抖动。工作集是最近 Δ 时间内访问过的页的集合。缓解：降多道、挂起某些进程、增大工作集窗口或给足页框——这是中级调度与内存分配的交界，不是换一个 RR 时间片就能解决。
文件系统
LEVEL 3文件系统用目录和分配算法组织字节流与磁盘块。它不是磁盘控制器，也不等于整块磁盘硬件。
9.1文件、目录与 FCB
FCB / inode 记录文件的元数据：权限、大小、时间、数据块指针等。目录是「名字 → FCB/inode 号」的映射。逻辑结构（流式 / 记录式）与物理结构（盘上怎么放）要分开说。
9.2物理分配
| 方式 | 做法 | 顺序访问 | 随机访问 | 碎片 |
|---|---|---|---|---|
| 连续 | 一块连续盘区 | 好 | 好 | 外碎片；文件难增长 |
| 链接 | 块内指针串起来 | 尚可 | 差 | 几乎无外碎片；指针占空间 |
| 索引 | 索引块登记所有盘块号 | 好 | 好 | 索引块本身开销；Unix inode 多用直接+间接混合 |
9.3空闲管理
空闲盘块可用位图、空闲链表或 Unix 的成组链接。位图适合随机找连续空闲区；成组链接把一组空闲号存在一个块里，减少超级块更新次数。
9.4打开文件
进程打开文件表里是文件描述符，指向系统打开文件表项（偏移、引用计数、指向 inode）。两个 fd 可以指向同一系统表项（dup）或不同表项（两次 open）。close 减引用，到 0 才释放表项。
设备与 I/O
LEVEL 3I/O 子系统连接内核与设备控制器。控制方式决定 CPU 介入的粒度；SPOOLing 用磁盘模拟独占设备。
10.1控制方式
| 方式 | CPU 角色 | 适用 |
|---|---|---|
| 程序直接控制（轮询） | 循环查状态，传送每个字 | 极简单设备；浪费 CPU |
| 中断驱动 | 启动后可做别的事，完成后中断再传 | 低速字符设备 |
| DMA | CPU 只设内存地址与长度，块传送由 DMA 控制器完成，结束再中断 | 磁盘、网卡等成块设备 |
| 通道 | 通道执行通道程序，组织更复杂的 I/O | 大型机教材模型；可看成更强的 DMA |
10.2缓冲与 SPOOLing
单缓冲、双缓冲、循环缓冲缓和 CPU 与设备的速度差。缓冲在内存；缓存还强调保留近期数据以减少重复 I/O。
SPOOLing（假脱机）：用磁盘上的输入井/输出井，加上预输入、缓输出进程，把独占设备改造为共享的虚拟设备。它不是「完全脱机的人工磁带交换」——名字来自历史，现代实现是联机的。
10.3磁盘调度
一次磁盘服务时间 ≈ 寻道 + 旋转延迟 + 传送。调度主要减寻道：
- FCFS：公平，寻道可能很长。
- SSTF：最近优先，平均寻道短，远端请求可能饥饿。
- SCAN / LOOK：电梯算法，扫到一端再折返；LOOK 只扫到最远请求。
- C-SCAN / C-LOOK：单向服务，回程不服务，两端等待更均匀。
章末自测
复查点开看答案。表述按 408 口径写了边界；全站题库见 quiz.html。