操作系统期末复习
按老师最新 PPT、往年卷和 Stallings 教材脉络整理的操作系统期末复习重点。
1. 第二章：操作系统概述
1.1 OS 的概念：OS 与一般程序的异同
定义：操作系统是控制应用程序执行的程序，是应用程序与计算机硬件之间的接口，同时也是系统资源管理器。
相同点：
- OS 和普通程序一样，都是处理器执行的指令序列。
- OS 也需要加载、执行，也会占用内存和 CPU。
不同点：
- OS 控制其他程序的执行时机。
- OS 管理 CPU、内存、I/O、文件等资源。
- OS 会主动释放 CPU 控制权，并依赖中断、异常、系统调用重新获得控制。
- OS 运行在特权模式，能执行普通程序不能执行的特权指令。
简答模板：
操作系统是控制应用程序执行、管理软硬件资源并向用户提供接口的系统软件。它与普通程序一样都是 CPU 执行的代码，但 OS 的特殊性在于它控制其他程序的运行，管理系统资源，提供抽象接口，并通过中断/异常/系统调用在用户态和内核态之间切换控制权。
1.2 OS 的目标和功能
三目标：
| 目标 | 含义 | 对应角色 |
|---|---|---|
| 方便 | 使计算机易用 | 用户/计算机接口 |
| 有效 | 高效使用系统资源 | 资源管理器 |
| 扩展能力 | 便于引入、测试、维护新功能 | 可扩展系统 |
功能：
- 进程/处理机管理：创建、撤销、调度、同步、通信、死锁处理。
- 内存管理：分配、回收、地址转换、虚拟内存。
- I/O 管理：设备驱动、中断、缓冲、磁盘调度。
- 文件管理：文件、目录、权限、外存分配。
- 用户接口：命令解释器、系统调用、图形界面。
- 错误检测和响应：发现硬件/软件错误并处理。
1.3 OS 的构成模块和各自功能
至少准备 3-4 个：
| 模块 | 功能 |
|---|---|
| 进程管理 | 进程/线程创建、切换、调度、同步、通信 |
| 存储管理 | 内存分配、保护、共享、地址转换、虚拟内存 |
| I/O 管理 | 设备抽象、驱动程序、中断处理、缓冲、调度 |
| 文件系统 | 文件组织、目录、权限、磁盘空间管理 |
1.4 OS 的发展：三个主线
老师 PPT 要求“从无到有，从简单到复杂，突出三个主线”。可这样答：
- 从处理方式看：无 OS/串行处理 -> 批处理 -> 多道批处理 -> 分时 -> 实时。
- 从资源利用看：人工独占硬件 -> 多道程序提高 CPU 利用率 -> 分时提高交互响应。
- 从抽象能力看：裸机接口 -> 系统调用/文件/进程/虚拟内存等高级抽象。
重点对比：
| 系统 | 产生背景 | 目标 | 关键技术 |
|---|---|---|---|
| 批处理 | 减少人工干预，提高吞吐 | CPU 利用率、吞吐量 | 作业成批、脱机 I/O |
| 多道批处理 | I/O 等待浪费 CPU | 多个作业交替执行 | 中断、调度、内存保护 |
| 分时系统 | 多用户交互需求 | 响应时间、公平性 | 时间片、时钟中断、抢占 |
| 实时系统 | 外部事件有时限 | 截止期、可预测性 | 优先级、实时调度 |
1.5 分时系统与批处理系统对比
| 项目 | 批处理系统 | 分时系统 |
|---|---|---|
| 用户交互 | 弱，提交作业后等待结果 | 强，通过终端交互 |
| 优化目标 | 吞吐量、CPU 利用率 | 响应时间、公平性 |
| 控制方式 | 作业控制语言/批作业 | 时间片轮转 |
| 关键机制 | 多道程序、I/O 中断 | 时钟中断、抢占调度 |
| 共同点 | 都可使用多道程序设计 | 都需要 OS 调度资源 |
1.6 中断/异常在批处理和分时系统中的作用
- 批处理中：I/O 操作启动后，CPU 可执行其他作业；I/O 完成后通过中断通知 OS。
- 分时中：时钟周期性中断，使 OS 重新获得控制权并切换用户进程。
- 异常：处理程序错误、缺页、非法访问等，使系统可保护自身并恢复或终止进程。
值得注意的是，中断是异步的，它和当前程序执行到哪条指令没有直接关系，也就是说中断随时都可能发生。
异常是同步的，它和当前执行的指令有关。
系统调用也被看作一种特殊异常，也叫陷入 trap。
关于异常
**异常（exception）**通常指 CPU 执行当前指令时发生的特殊事件。常见分类一般有三类
- Fault 是执行某条指令时发现问题，但问题可能可以被修复。
- Trap 通常是程序主动触发的异常。
- Abort 是严重错误，通常无法恢复。
2. 第三章：进程管理
2.1 实现进程需要 CPU 的硬件支持
老师 PPT 强调：CPU 的 Mode + 中断/异常。
CPU的Mode:用户态 内核态
必写点：
- 用户态/内核态：限制普通程序执行特权指令，保护 OS。
- 中断机制：I/O 完成、时钟等外部事件使 OS 获得控制。
- 异常机制：缺页、越界、非法指令等内部事件使 OS 介入。
- 定时器：实现时间片和抢占。
- 寄存器/PC/栈指针：上下文切换时保存和恢复。
- MMU（内存管理单元）：支持地址转换、内存保护和虚拟内存。
2.2 进程概念、进程与程序
进程：正在执行的程序实例，是由指令序列、当前执行状态和相关系统资源组成的活动实体。
| 比较 | 程序 | 进程 |
|---|---|---|
| 性质 | 静态 | 动态 |
| 存放 | 文件/外存 | 内存和系统数据结构 |
| 内容 | 指令和数据 | 程序、数据、栈、堆、寄存器状态、PCB |
| 数量关系 | 一个程序可多次运行 | 一个程序可对应多个进程 |
2.3 PCB 的概念、重要性和构成
PCB：Process Control Block，进程控制块。它是 OS 为每个进程维护的数据结构，保存进程当前状态和管理信息。
重要性：
- OS 通过 PCB 感知和管理进程。
- PCB 保存上下文，使进程被中断后可恢复。
- PCB 是调度、同步、资源管理、内存管理的基础。
构成答题口径：
| 类别 | 例子 |
|---|---|
| 标识信息 | PID、父进程 PID、用户 ID |
| 状态信息 | 运行态、就绪态、阻塞态、优先级 |
| 处理器状态 | PC、通用寄存器、PSW、栈指针 |
| 控制信息 | 调度队列指针、内存信息、打开文件、IPC、资源清单 |
2.4 图题：HelloWorld 程序变为 HelloWorld 进程
老师要求：四个阶段、进程 Image 要素和 PCB。
四阶段：
- 编译/链接：源程序变成可执行文件。
- 装入：OS 将程序代码和初始数据装入内存，建立地址空间。
- 创建进程：分配 PID，创建 PCB，初始化寄存器、PC、栈、页表/段表。
- 就绪/运行：进程进入就绪队列，调度后开始执行 HelloWorld。
进程 Image 要素：
- 用户程序代码。
- 用户数据。
- 用户栈。
- 堆。
- 共享库/系统栈等运行支持区。
- PCB 和页表等内核维护结构。
可画简图：
可执行文件
|
v
装入内存: 代码区 + 数据区 + 堆 + 栈
|
v
创建 PCB: PID + 状态 + PC/寄存器 + 优先级 + 内存映射
|
v
就绪队列 -> CPU 调度 -> 运行 HelloWorld3. 第四章：线程
3.1 线程概念、产生背景、进程与线程关系
线程：进程中的一个执行流，是 CPU 调度的基本单位。
产生背景：
- 进程创建/切换开销较大。
- 同一应用内需要多个并发执行流。
- 多核处理器需要更细粒度的并行单位。
- I/O 阻塞时可让同进程其他线程继续执行。
进程与线程：
| 比较 | 进程 | 线程 |
|---|---|---|
| 基本角色 | 资源分配单位 | CPU 调度单位 |
| 地址空间 | 进程间相互隔离 | 同进程线程共享 |
| 开销 | 创建/切换开销大 | 创建/切换开销小 |
| 通信 | IPC 成本较高 | 共享内存，通信方便 |
| 保护 | 进程间保护强 | 同进程线程相互影响 |
挂起状态就是：进程/线程被系统暂时暂停，不参与 CPU 调度，通常需要经过“激活/恢复”后才能重新进入普通的就绪或阻塞状态。
阻塞挂起 —事件完成—> 就绪挂起
就绪挂起 —激活—> 就绪态
3.2 线程实现方法：三类
- 用户级线程 ULT：线程管理由用户态线程库完成，内核不知道线程存在。
- 内核级线程 KLT：线程由内核管理，内核能调度每个线程。
- 组合模型：用户线程映射到若干内核线程，兼顾灵活性和并行性。
3.3 ULT 和 KLT 优缺点
| 类型 | 优点 | 缺点 |
|---|---|---|
| ULT | 切换无需陷入内核；调度可由应用定制；移植性好 | 阻塞式系统调用可能阻塞整个进程；不能真正利用多处理器并行 |
| KLT | 一个线程阻塞不影响其他线程；可多核并行；内核可统一调度 | 线程操作需要内核参与，模式切换开销大 |
| 组合 | 既可用户态管理，又可多核并行 | 实现复杂，需要映射和调度协调 |
线程的状态及其切换：
| 转换 | 原因 |
|---|---|
| 新建态 → 就绪态 | 线程被创建并启动 |
| 就绪态 → 运行态 | 被 CPU 调度 |
| 运行态 → 就绪态 | 时间片用完，或被更高优先级线程抢占 |
| 运行态 → 阻塞态 | 等待 I/O、锁、信号量、sleep 等 |
| 阻塞态 → 就绪态 | 等待事件完成，条件满足 |
| 运行态 → 终止态 | 线程执行完毕或被终止 |
4. 第五章：并发、同步互斥
| 术语 | 英文定义与解析 |
|---|---|
| 原子操作 | 一种函数或动作，实现为由一条或多条指令组成的序列，在外部看来是不可分割的。也就是说，没有其他进程能看到其实施的中间状态或中断该操作。该指令序列要么作为一个整体确保全部执行，要么根本不执行，对系统状态不产生任何可见影响。原子性保证了与并发进程之间的隔离。 |
| 临界区 | 进程中的一段代码区域，该区域需要访问共享资源，并且当另一个进程正在对应的代码区域中执行时，当前进程绝不能执行这段代码。 |
| 死锁 | 两个或多个进程由于都在等待其他进程做出某种行为，导致所有相关进程都无法向前推进的僵持状态。 |
| 活锁 | 两个或多个进程为了响应其他进程的状态变化，而持续不断地改变自身状态，但结果却没有做任何有用功的现象。 |
| 互斥 | 一种强制性要求：当一个进程正处于访问共享资源的临界区时，其他任何进程都不得进入访问该相同共享资源的临界区。 |
| 条件竞争 | 多个线程或进程同时对某项共享数据进行读写操作，导致**最终结果取决于它们执行的相对时间顺序（时序）**的一种情况。 |
| 饥饿 | 一个处于就绪状态（Runnable）的进程，被调度程序无限期地忽略；虽然它完全具备执行条件，但却永远不会被选中执行。 |
4.1 Concurrency 需要解决的四个问题
| 问题 | 含义 |
|---|---|
| 同步 | 多个执行流之间存在先后约束 |
| 互斥 | 对临界资源的访问一次只允许一个执行流 |
| 死锁 | 一组进程永久等待彼此持有的资源或事件 |
| 饥饿 | 可运行进程长期得不到资源或 CPU |
注意：第五章主要同步互斥，第六章主要死锁/饥饿。
4.2 Race Condition 与原子操作
Race Condition：多个进程/线程并发访问共享数据，最终结果依赖它们执行的相对时序。
原子操作：一个操作要么全部执行成功，要么全部不执行（不保留中间状态），并且在执行过程中绝对不会被其他线程或硬件中断打断。
4.3 临界区由几个部分组成
常见四部分：
| 部分 | 作用 |
|---|---|
| Entry Section | 进入区，申请进入临界区的许可，如加锁 |
| Critical Section | 临界区，访问共享资源的代码 |
| Exit Section | 退出区，释放许可，如解锁 |
| Remainder Section | 剩余区，与共享资源无关的代码 |
简图：
while (true) {
entry_section();
critical_section();
exit_section();
remainder_section();
}互斥实现必须保证临界区同一时刻最多一个进程进入。
4.4 同步互斥实现方法对比
| 方法 | 思路 | 优点 | 缺点 |
|---|---|---|---|
| 软件方法 | 用共享变量和协议控制进入，如 Dekker/Peterson | 不依赖特殊硬件 | 复杂，适用范围有限，忙等待 |
| 硬件方法 | 关中断或原子指令 test-and-set/CAS/exchange | 简单，原子性强 | 忙等待，关中断不适合多处理器，可能饥饿 |
| 信号量 | 整数计数 + 等待队列，P/V 原子操作 | 表达能力强，可同步可互斥 | 分散在程序中，顺序错易死锁 |
| 管程 | 共享数据和操作封装，内部自动互斥 | 结构清晰，易验证 | 语言/系统支持要求高 |
| 消息传递 | send/receive 同步或传递数据 | 适合分布式或无共享内存 | 通信开销和阻塞语义需处理 |
早期方法分类可简答为：软件方法、硬件方法、系统/OS 提供的机制。
4.5 进程间关系
| 关系 | 原因 | 典型问题 |
|---|---|---|
| 互不知道对方存在 | 竞争同类资源 | 互斥、死锁、饥饿 |
| 间接知道对方存在 | 共享数据或缓冲区合作 | 数据一致性、同步、互斥 |
| 直接知道对方存在 | 通过消息通信合作 | 发送/接收同步、消息丢失 |
互斥锁 Mutex：
如果锁是空闲的，该线程成功加锁，进入临界区。
如果锁已经被其他线程占用，当前线程不会死等，而是会被操作系统挂起（阻塞，进入等待队列），让出 CPU 资源给其他就绪的线程执行。
当持有锁的线程释放锁时，操作系统会唤醒等待队列中的一个线程，使其重新变为就绪状态，等待 CPU 调度去获取锁。
自旋锁 Spinlock：
如果锁是空闲的，该线程成功加锁。
如果锁已经被占用，当前线程绝对不睡觉，也不释放 CPU，而是在那里执行一个死循环（While loop），疯狂地、不断地去检查锁的状态是否已经变为空闲。
这种“在原地转圈死等”的行为，就叫做“自旋”。其底层通常是一条高频执行的 CAS 原子指令。
4.6 管程组成和必要性
管程将共享变量和对这些变量的同步操作直接封装在一个专门的结构体内，从而把并发控制的复杂度对开发者屏蔽掉。
组成：
- 局部共享数据。
- 对共享数据的操作过程/函数。
- 初始化代码。
- 条件变量和等待队列。
必要性：
- 信号量太底层，P/V 分散在程序中，容易顺序错误。
- 管程把共享资源和操作封装起来，由结构保证互斥。
- 条件变量可表达“等待某个条件成立”。
4.7 信号量与管程条件变量：联系与区别
| 比较 | 信号量 | 条件变量 |
|---|---|---|
| 使用范围 | 可在任意并发程序中使用 | 通常在管程内部使用 |
| 本质 | 带计数的同步对象 | 等待某条件成立的等待队列 |
| 是否保存资源数 | 保存，S>0 表示资源数 | 不保存资源数，只表示等待队列 |
| wait 含义 | 申请资源，可能阻塞 | 释放管程锁并等待条件 |
| signal 含义 | 增加资源/唤醒等待者 | 唤醒某个等待该条件的进程 |
| 风险 | 顺序错误可死锁 | 结构化，较易验证 |
联系：二者都用于阻塞和唤醒并发执行流，都可表达同步关系。
4.8 信号量应用与分析
生产者-消费者
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
producer() {
while (true) {
produce();
wait(empty);
wait(mutex);
put();
signal(mutex);
signal(full);
}
}
consumer() {
while (true) {
wait(full);
wait(mutex);
get();
signal(mutex);
signal(empty);
consume();
}
}分析：
mutex解决互斥访问缓冲区。empty保证有空位才能生产。full保证有产品才能消费。
读者-写者：读者优先
int readCount = 0;
semaphore x = 1;
semaphore wsem = 1;
reader() {
wait(x);
readCount++;
if (readCount == 1) wait(wsem);
signal(x);
read();
wait(x);
readCount--;
if (readCount == 0) signal(wsem);
signal(x);
}
writer() {
wait(wsem);
write();
signal(wsem);
}分析：
- 多个读者可同时读。
- 写者需要独占。
- 第一个读者阻止写者，最后一个读者释放写者。
哲学家进餐
问题：五个哲学家共用五支筷子，每人需左右两支筷子才能吃饭。若每人先拿左筷子再等右筷子，会死锁。
常见解决：
- 最多允许 4 个哲学家同时进入餐厅。
- 规定奇偶哲学家拿筷子顺序不同。
- 用服务员/管程集中分配。
5. 第六章：死锁/饥饿
5.1 死锁概念和例子
死锁：两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象。
5.2 死锁条件
可重用资源的概念:资源被某个进程使用完后，可以供其他进程使用。
老师 PPT 写法：“充分条件 3 个，充要条件 4 个”。考试建议按以下口径：
前三个资源条件：
- 互斥：资源不能共享。
- 占有且等待：持有资源时继续等待其他资源。
- 不可抢占：资源只能主动释放。
四个条件完整口径：
- 循环等待：存在进程等待环。
常规教材中四条件通常是死锁必要条件；在单实例资源分配图中，循环等待也可作为死锁判定。答题时按老师口径写“四个条件同时出现构成死锁判定依据”。
5.3 解决死锁方法
| 方法 | 思路 | 例子 |
|---|---|---|
| 预防 | 静态破坏死锁条件 | 一次性申请、资源排序、允许抢占 |
| 避免 | 动态判断是否会进入不安全状态 | 银行家算法 |
| 检测 | 允许死锁发生，周期性检测 | 死锁检测算法 |
| 综合 | 不同资源类别使用不同策略 | 内存可抢占，内部资源排序 |
恢复方法：
- 取消所有死锁进程。
- 逐个取消进程直到解除死锁。
- 回滚到检查点。
- 抢占资源。
牺牲进程选择标准：
- 优先级低。
- 已运行时间短或剩余时间长。
- 占用资源少或回滚代价小。
- 对系统影响小。
5.4 银行家算法思想和现实局限
思想：进程请求资源时，系统先试探分配，再检查分配后系统是否仍处于安全状态。若安全则分配，否则拒绝或等待。
为什么能避免死锁：
- 它不让系统进入不安全状态。
- 安全状态表示至少存在一个进程序列，使所有进程最终都能完成。
现实局限：
- 需要预先知道每个进程最大资源需求。
- 假设进程数量和资源类型较稳定。
- 运行时维护和检测成本高。
- 实际系统资源请求复杂，很多需求难以提前声明。
因此银行家算法在教学中重要，但实际通用 OS 中不常直接使用完整形式。
5.5 银行家算法步骤
数据：
Available: 当前可用资源
Max: 每个进程最大需求
Allocation: 当前已分配
Need = Max - Allocation安全性检测：
Work = Available，所有Finish=false。- 找一个
Finish=false且Need <= Work的进程。 - 假设它完成，
Work += Allocation，Finish=true。 - 重复直到不能继续。
- 全部
Finish=true则安全，否则不安全。
请求处理：
- 检查
Request <= Need。 - 检查
Request <= Available。 - 试分配。
- 做安全性检测。
- 安全则正式分配，不安全则回滚。
6. 第七章：内存管理
6.1 内存管理方法关系：从简单到复杂
| 方法 | 是否全部装入 | 是否连续 | 特点 |
|---|---|---|---|
| 固定分区 | 是 | 是 | 分区大小固定，内部碎片 |
| 动态分区 | 是 | 是 | 按需分配，外部碎片 |
| 简单分页 | 是 | 否 | 进程分页，内存页框 |
| 简单分段 | 是 | 否 | 按逻辑模块分段，段长不等 |
| 虚拟分页 | 否 | 否 | 请求调页 |
| 虚拟分段 | 否 | 否 | 请求调段 |
| 段页式/虚拟段页式 | 否 | 否 | 先分段，段内分页 |
6.2 内存管理功能需求
Stallings 常见五项：
| 需求 | 含义 |
|---|---|
| 重定位 | 程序装入位置可变，逻辑地址能映射到物理地址 |
| 保护 | 防止进程访问未授权内存 |
| 共享 | 支持多个进程共享代码或数据 |
| 逻辑组织 | 按模块、段、过程等组织程序 |
| 物理组织 | 管理主存和外存之间的数据移动 |
6.3 常见术语
| 术语 | 含义 |
|---|---|
| 覆盖 Overlay | 程序不同部分分时装入同一内存区域，早期解决内存不足 |
| 交换 Swapping | 将整个进程或部分内容在内存和外存之间换入换出 |
| 重定位 Relocation | 把逻辑地址转换为物理地址 |
| 逻辑地址/虚拟地址 | 程序生成的地址 |
| 物理地址 | 主存中的实际地址 |
| 相对地址 | 相对于某个基址的偏移 |
| 内部碎片 | 分配块内部未被使用的空间 |
| 外部碎片 | 空闲空间分散，虽总量够但无法满足连续分配 |
| 页 Page | 进程地址空间固定大小块 |
| 页框 Frame | 物理内存固定大小块 |
| 段 Segment | 程序逻辑单元，长度可变 |
6.4 固定分区、动态分区、分页、分段对比
固定分区 vs 分页：
- 相同：分配单位大小固定，都可能有内部碎片。
- 不同：固定分区要求每个进程装入一个连续分区；分页把进程拆成页，可不连续装入多个页框。
动态分区 vs 分段：
- 相同：分配单位大小可变，可能有外部碎片。
- 不同：动态分区通常按整个进程分配；分段按程序逻辑模块划分。
分页 vs 分段：
| 项目 | 分页 | 分段 |
|---|---|---|
| 划分依据 | 固定大小 | 逻辑模块 |
| 大小 | 等长 | 不等长 |
| 程序员可见性 | 通常不可见 | 通常可见 |
| 碎片 | 内部碎片 | 外部碎片 |
| 表项 | 页号 -> 页框号 | 段号 -> 基址 + 长度 |
6.5 段表项和页表项一般格式
页表项常见字段：
- 存在位/有效位：指示该页是否已加载到物理内存中
- 页框号：存储该虚拟页对应的物理内存块起始地址
- 访问位/使用位：记录该页最近是否被访问过（读或写），区域性原理的调度算法
- 修改位/脏位：记录该页的内容在换入内存后是否被修改过，是否写回磁盘
- 保护位：控制对该页的访问权限，保障系统安全
段表项常见字段：
- 存在位：指示该整个逻辑段是否已加载到物理内存中
- 段基址：该逻辑段在物理内存中的起始绝对地址
- 段长度/界限：规定该逻辑段的合法最大长度（ Segmentation Fault ）
- 保护位：定义该逻辑段的访问权限
- 修改位/访问位：用于记录该段的访问与修改状态
6.6 图题：简单分页/分段大局观
7. 第八章：虚拟内存管理
简单管理和虚拟管理最本质的区别在于：是否要求将程序“一次性、全部”读入物理内存才能运行。
系统抖动 (Thrashing)：当操作系统试图运行过多的并发进程，或者分配给某个进程的物理内存（页框）严重不足时，就会发生抖动。
局部性原理：程序在执行时，对数据和指令的访问呈现出高度的“聚集倾向”，而不是随机、均匀地访问整个内存空间。
7.1 如何理解虚拟内存 VM
软件和硬件两个层次：
- CPU/MMU 支持：CPU 产生虚拟地址，MMU 进行地址转换，TLB 加速转换。
- OS 支持：维护页表/段表，处理缺页，进行置换、装入、保护和共享。
从不同角度理解：
- 进程 P：看到独立、连续、私有的大地址空间，好像独占内存。
- CPU：执行指令产生虚拟地址，不直接感知物理内存布局。
- OS：维护虚拟页到物理页框的映射，决定哪些页在内存。
- 内存 M：只保存虚拟地址空间中当前活跃的一部分页。
CSAPP 角度：
- 虚拟内存是缓存工具：主存缓存磁盘上的虚拟页。
- 虚拟内存是内存管理工具：每个进程有一致的虚拟地址空间。
- 虚拟内存是内存保护工具：通过页表权限隔离进程。
7.2 虚拟内存要考虑的三个因素
- 是否使用虚拟内存。
- 使用分页、分段，还是段页式。
- 采用哪些管理策略：读取、放置、置换、驻留集、清除、加载控制。
7.3 实现方法及特点
| 方法 | 特点 |
|---|---|
| 虚拟分页 | 页固定大小，按需调入，管理简单 |
| 虚拟分段 | 段按逻辑模块，便于共享和保护 |
| 段页式 | 程序员视角分段，系统视角分页，兼顾逻辑组织和物理管理 |
倒排页表：以物理页框为基准来建表 ，查询方式：哈希映射和锚点表
7.4 图题：页面故障处理流程
段页式中：每个进程维护一个段表，而每一个段又对应一个页表。
7.5 常见术语
| 术语 | 含义 |
|---|---|
| Page Fault | 访问页不在内存，触发缺页异常 |
| Thrashing | 抖动，系统大量时间用于换页，实际执行很少 |
| Address Space | 地址空间，一个进程可使用的虚拟地址范围 |
| Cleaning Policy | 清除策略，决定脏页何时写回外存 |
| Load Control | 加载控制，控制内存中进程数量 |
| Resident Set | 驻留集，某进程当前驻留在内存的页集合 |
| Working Set | 工作集，进程在一段时间内活跃访问的页集合 |
7.6 页调度算法
| 算法 | 规则 | 特点 |
|---|---|---|
| OPT | 淘汰未来最久不用的页 | 理论最优，不能实际实现 |
| LRU | 淘汰最久未访问的页 | 接近 OPT，实现成本高 |
| FIFO | 淘汰最早进入内存的页 | 简单，可能 Belady 异常 |
| Clock | 用访问位近似 LRU | 实用、低成本 |
Clock：
- 页面装入或被访问时使用位置 1。
- 置换时从指针开始扫描。
- 遇 1 改 0 并跳过。
- 遇 0 替换。
8. 第九/十章：进程调度
8.1 图题：长/中/短调度类型和特点
| 调度 | 别名 | 作用 | 方向 |
|---|---|---|---|
| 长程调度 | 作业调度 | 决定哪些作业进入系统，控制多道程度 | 外存 -> 内存 |
| 中程调度 | 交换调度 | 决定哪些挂起进程调回内存 | 外存 <-> 内存 |
| 短程调度 | CPU 调度 | 决定就绪进程中谁获得 CPU | 内存 -> CPU |
答图时要画：
后备队列 --长程调度--> 就绪队列 --短程调度--> CPU
阻塞/就绪挂起 <--中程调度/交换--> 内存中的阻塞/就绪队列长程调度：控制并发度
中程调度：挂起进程回内存
短程调度：谁占用CPU （时钟中断，IO中断，系统调用，信号）
8.2 调度选择影响因素
决策模式：
- 非抢占：进程运行到阻塞或结束才释放 CPU。
- 抢占：OS 可在时间片到或更高优先级到达时打断当前进程。
性能指标：
- 响应时间:从任务提交到任务开始相应
- 周转时间:从任务提交到任务执行最终完成
- 等待时间。
- 吞吐量:单位时间完成的任务数量
- 资源利用率:单位时间内处于工作状态的时间比例
- 截止期满足率。
公平性：
- 防止进程饥饿（一个进程被准入后一直没得到执行，因此永远无法完成）
- 避免某类进程长期得不到服务。
场景目标：
- 批处理：吞吐量、周转时间。
- 交互系统：响应时间、公平性。
- 实时系统：截止期、可预测性。
8.3 常见调度算法特点
| 算法 | 抢占 | 特点 | 饥饿风险 |
|---|---|---|---|
| FCFS | 否 | 先到先服务，简单公平 | 短作业等待长，护航效应 |
| SPN/SJF | 否 | 服务时间短者优先，平均等待低 | 长作业可能饥饿 |
| HRRN | 否 | 响应比最高，兼顾等待时间 | 较低 |
| RR | 是 | 时间片轮转，适合交互 | 时间片不当影响性能 |
| SRT | 是 | 剩余时间最短，SPN 抢占版 | 长作业可能饥饿 |
| MLFQ/Feedback | 是 | 多级队列，用完时间片降级 | 低优先级可能饥饿 |
| EDF | 是/可抢占 | 最早截止期优先 | 过载时任务会错过截止期 |
| RM | 是/静态优先级 | 周期越短优先级越高 | 低优先级任务可能受影响 |
8.4 调度计算公式
周转时间 Tr = 完成时间 - 到达时间
等待时间 Tw = 周转时间 - 服务时间
归一化周转时间 = Tr / 服务时间
HRRN 响应比 R = (等待时间 + 服务时间) / 服务时间8.5 实时调度 EDF 和 RM
EDF：Earliest Deadline First，最早截止期优先。
- 动态优先级。
- 截止期越早，优先级越高。
- 单处理器可抢占任务模型下，EDF 在理论上有很强的可调度性。
- 适合截止期不同、动态变化的实时任务。
RM：Rate Monotonic，速率单调调度。
- 静态优先级。
- 周期越短，速率越高，优先级越高。
- 适合周期性实时任务。
- 经典利用率上界：
U <= n(2^(1/n)-1)可保证可调度；当n很大时约为 0.693。
场景选择：
- 要求动态截止期：EDF。
- 周期任务、优先级固定：RM。
- 普通交互系统：RR/MLFQ。
- 批处理短作业优化：SPN/SRT/HRRN。
9. 第十章：I/O 管理
老师 PPT 中写“第十章 IO管理”，对应教材常见 I/O 管理和磁盘调度内容。
9.1 OS 中 I/O 系统设计目标
| 目标 | 含义 |
|---|---|
| 效率 | I/O 慢，OS 应减少等待和中断开销 |
| 通用性 | 用统一方式管理不同设备 |
| 设备独立性 | 程序不依赖具体设备细节 |
| 统一命名 | 设备可用文件或统一接口访问 |
| 错误处理 | 屏蔽和恢复设备错误 |
| 缓冲与缓存 | 缓和速度差异，提高并行性 |
| 调度 | 合理安排请求顺序，减少寻道/等待 |
9.2 系统缓冲区组成与功能
缓冲区功能：
- 缓和 CPU/内存与设备速度差异。
- 减少进程阻塞时间。
- 降低中断频率。
- 支持预读和延迟写。
- 提高 CPU 和 I/O 设备并行度。
- 支持进程换出，减少 I/O 与换入换出之间的耦合。
9.3 图题：缓冲区组织类型
单缓冲：
设备 -> [Buffer] -> 进程双缓冲：
设备 -> [Buffer A] -> 进程
设备 -> [Buffer B] -> 进程
两个缓冲交替使用循环缓冲：
[B1] -> [B2] -> [B3] -> ... -> [Bn] -> 回到 [B1]适用：
- 单缓冲：简单预读。
- 双缓冲：输入/处理可重叠。
- 循环缓冲：生产者和消费者速度波动较大时。
9.4 磁盘访问时间组成
磁盘访问时间通常包括：
总访问时间 = 寻道时间 + 旋转延迟 + 传输时间 + 控制器/排队开销| 部分 | 含义 | 影响因素 |
|---|---|---|
| 寻道时间 Seek Time | 磁头移动到目标磁道 | 当前磁道与目标磁道距离 |
| 旋转延迟 Rotational Latency | 等待目标扇区转到磁头下 | 磁盘转速 |
| 传输时间 Transfer Time | 数据实际读写时间 | 数据量、转速、接口带宽 |
| 排队/控制器开销 | 等待设备和控制器处理 | 请求队列、控制器性能 |
磁盘调度主要优化寻道时间。
9.5 磁盘调度策略
磁盘调度都是非抢占式
| 算法 | 规则 | 优点 | 缺点 |
|---|---|---|---|
| FIFO | 按请求到达顺序服务 | 公平、简单 | 平均寻道可能大 |
| LIFO | 最近请求先服务 | 可能利用局部性 | 老请求可能饥饿 |
| SSTF | 选距离当前磁头最近请求 | 平均寻道短 | 远处请求可能饥饿 |
| SCAN | 电梯算法，沿一个方向服务，到端点反向 | 等待较均衡 | 端点附近等待模式特殊 |
| C-SCAN | 单方向扫描，到端点后回到另一端 | 等待更均匀 | 回扫成本 |
| FSCAN | 两个队列，一个按 SCAN 服务，新请求进另一个队列 | 避免磁臂黏着，响应更稳定 | 实现更复杂 |
执行过程答题：
- 写出初始磁道和移动方向。
- 根据算法列服务序列。
- 累加相邻服务磁道距离。
- 说明公平性/饥饿风险。
10.文件系统
文件抽象结构：
[域 Field] ➔ [记录 Record] ➔ [文件 File] ➔ [虚拟/逻辑块 Logical Block] ➔ [物理数据块 Data Block]
(数据项) (行/实体) (抽象集合) (文件系统单位) (磁盘扇区聚合)10.1 文件系统层次
应用/用户
-> 逻辑 I/O
-> 基本文件系统
-> 基本 I/O 管理
-> 设备驱动
-> 硬件10.2 文件逻辑组织
- 堆。
- 顺序文件。
- 索引顺序文件。
- 索引文件。
- 散列文件。
10.3 文件物理分配
| 方式 | 优点 | 缺点 |
|---|---|---|
| 连续分配 | 顺序/随机访问快 | 外部碎片，增长困难 |
| 链式分配 | 无外部碎片，增长方便 | 随机访问差，指针开销 |
| 索引分配 | 支持随机访问，无外部碎片 | 索引块开销 |
评论