操作系统
Operating System
考点定位:综合知识选择题稳定考点,含 PV 题、页面置换、磁盘调度等计算/推理题。 优先级:中。芝士架构公开课程大纲中「操作系统」子模块:进程模型、PV 操作、死锁判断、内存管理、文件系统。
1. 知识地图
| 子模块 | 核心考点 | 考查形式 | 优先级 |
|---|---|---|---|
| 进程与线程 | 进程状态、PCB、进程通信、线程与进程区别 | 选择题 | ★★★★ |
| 同步与互斥 | 临界区、信号量、PV 操作、前驱图 | 选择题(推理/填空) | ★★★★★ |
| 死锁 | 四个必要条件、预防/避免/检测解除、银行家算法 | 选择题 | ★★★★ |
| 内存管理 | 分页、分段、段页式、页面置换算法、抖动 | 选择题 + 计算 | ★★★★★ |
| 文件系统 | 文件索引结构(直接/间接)、目录、空闲空间管理 | 选择题 + 计算 | ★★★ |
| 磁盘与 I/O | 磁盘调度算法、磁盘管理、I/O 控制方式 | 计算题 | ★★★ |
2. 核心知识
2.1 进程与线程
- 进程:程序的一次执行,是资源分配的基本单位;线程:CPU 调度的基本单位,共享进程资源。
- 进程状态:新建、就绪、运行、阻塞、终止。只有「就绪 → 运行」由调度触发;「运行 → 阻塞」是主动等待;「阻塞 → 就绪」是等待事件发生。
- PCB(进程控制块):进程存在的唯一标志,保存状态、优先级、现场信息等。
- 进程通信:共享存储、消息传递、管道。
2.2 同步与互斥:PV 操作
- 临界资源:一次只允许一个进程访问的资源;临界区:访问临界资源的代码段。
- 信号量 S:
- P(S)(wait):S = S - 1;若 S < 0 则阻塞。(申请资源)
- V(S)(signal):S = S + 1;若 S ≤ 0 则唤醒一个等待进程。(释放资源)
- S > 0 表示可用资源数;S = 0 表示刚好无资源无等待;S < 0 的绝对值为等待进程数。
- 互斥信号量初值 1;同步信号量初值通常为 0 或资源数量。
- 前驱图:用信号量实现前驱约束——每条边一个信号量,前驱节点完成后 V,后继节点开始前 P。
2.3 死锁
- 四个必要条件(缺一不可):互斥、请求和保持(占有且等待)、不可剥夺、循环等待。
- 处理策略:
- 预防:破坏四个条件之一(如一次性分配破坏请求保持、资源有序分配破坏循环等待)。
- 避免:银行家算法(安全序列检测)。
- 检测与解除:资源分配图化简;终止进程或剥夺资源。
- 关键辨析:死锁是「都等待对方释放资源」;饥饿是「长期得不到调度」;活锁是「不断改变状态但都无法推进」。
2.4 内存管理
| 方式 | 特点 | 碎片 |
|---|---|---|
| 连续分配 | 单一/分区分配 | 内部碎片 / 外部碎片 |
| 分页 | 固定大小页框,地址 = 页号 + 页内偏移 | 仅有最后一页内部碎片 |
| 分段 | 按逻辑段划分,段长不等 | 外部碎片 |
| 段页式 | 先分段再分页 | 内部碎片(页级) |
- 地址转换:逻辑地址 →(页表)→ 物理地址;快表(TLB)缓存常用页表项。
- 页面置换算法:
- 最佳(OPT):淘汰未来最长时间不用的(理论最优,无法实现,用于评价基准)。
- 先进先出(FIFO):淘汰最早进入的;可能产生Belady 异常(分配页框增多缺页反而增加)。
- 最近最久未用(LRU):淘汰最近最久未使用的。
- 时钟(Clock/NRU):近似 LRU,低开销。
- 抖动(颠簸):频繁换入换出,CPU 利用率骤降;原因:进程太多、 frames 不足。
2.5 文件系统与磁盘
- 文件物理结构:连续分配(顺序访问快、有外部碎片)、链接分配(无碎片、随机访问慢)、索引分配(支持随机访问,索引块开销;大文件用多级/混合索引——直接块 + 一级/二级/三级间接块)。
- 空闲空间管理:空闲表、空闲链表、位示图、成组链接法。
- 磁盘调度算法:
- FCFS(先来先服务,公平但效率低)
- SSTF(最短寻道时间优先,可能饥饿)
- SCAN(电梯算法,双向扫描)
- C-SCAN(单向循环扫描,响应更均匀)
- LOOK / C-LOOK(只到最远请求即返回,SCAN 的改进)
3. 易混淆概念对比
| 对比项 | 关键区别 |
|---|---|
| 进程 vs 线程 | 进程是资源分配单位、地址空间独立;线程是调度单位、共享进程资源 |
| 互斥 vs 同步 | 互斥解决「不能同时用」;同步解决「按什么先后顺序」 |
| 死锁 vs 饥饿 | 死锁是相互等待永远阻塞;饥饿是调度策略长期忽略 |
| FIFO vs LRU | FIFO 按进入时间淘汰(可能 Belady 异常);LRU 按最近使用时间淘汰 |
| 分页 vs 分段 | 分页是物理单位、大小固定、对用户透明;分段是逻辑单位、大小不等、用户可见 |
| SCAN vs C-SCAN | SCAN 双向来回扫描;C-SCAN 单向扫描到头后直接回到起点 |
4. 考试重点
- PV 题:根据前驱图写出信号量初值与 P/V 位置(必考推理)。
- 给定页面访问序列与页框数,计算 FIFO/LRU 缺页次数。
- 判断死锁必要条件是否被破坏、银行家算法是否安全状态。
- 磁盘调度算法计算总寻道距离。
- 混合索引结构下文件最大长度计算(直接块 + 各级间接块 × 地址项数 × 块大小)。
5. 典型例题(原创模拟题)
例题 1:某系统有 3 个页框,页面访问序列为 1,2,3,1,4,5,分别用 FIFO 与 LRU 计算缺页次数(初始为空)。
解析:
- FIFO:1(缺)、2(缺)、3(缺)、1(命中)、4(缺,淘汰1)、5(缺,淘汰2) → 共 5 次缺页。
- LRU:1(缺)、2(缺)、3(缺)、1(命中,1 最近使用)、4(缺,淘汰2)、5(缺,淘汰3) → 共 5 次缺页。
该题演示标准解题思路:逐项模拟队列/栈状态,标注每次命中与淘汰,避免凭直觉估算。
例题 2:若信号量 S 初值为 2,某时刻 S = -1,则表示( )。 A. 还有 1 个资源可用 B. 有 1 个进程在等待 C. 有 2 个进程在等待 D. 无进程等待
| 答案:B。解析:S < 0 时, | S | 为等待队列中的进程数。S = -1 表示 1 个进程阻塞等待。 |
6. 记忆技巧
- 死锁四条件:互请不循(互斥、请求保持、不可剥夺、循环等待)。
- 页面置换:OPT 理论最优,FIFO 会异常,LRU 最常用,Clock 近似 LRU。
- 磁盘调度:先来先服务 → 最短寻道 → 电梯 → 循环电梯,公平性与效率逐步权衡。
- PV 口诀:P 减 V 加,负为等待数;互斥初 1,同步看先后。
7. 随堂测试
- 运行中的进程等待 I/O 完成后会进入什么状态?
- Belady 异常出现在哪种置换算法中?
- 破坏「循环等待」条件的常见方法是什么?
参考答案
1. 阻塞态(等待完成后转入就绪态,再由调度进入运行态)。 2. FIFO(先进先出),即分配更多页框时缺页次数反而可能增加。 3. 资源有序分配法:为资源编号,进程必须按递增顺序申请资源。7. 芝士架构资料补充
来源:《公共知识红宝书》第 11 章。
7.1 进程状态模型(★★★☆☆)
- 三态模型:就绪(已获取除 CPU 外所有资源,在就绪队列等待调度)、运行(占用 CPU,单 CPU 同一时刻只有一个)、阻塞(又称等待/睡眠态,等待某事件而暂停,即便有空闲 CPU 也不能运行,事件完成后转就绪)。口诀:舅(就绪)运(运行)祖(阻塞)宗。
- 五态模型增加:新建态(分配资源、初始化,未入就绪队列)、终止态(执行完毕/异常终止,保留部分内核数据善后)。口诀:新舅运祖宗。
- 辨析:就绪态是”在队列等待调度”,阻塞态是”进程暂停运行”。
7.2 前趋图(★★★★★)
- 是一个有向无环图,结点表示进程/程序段/语句,有向边表示偏序或前驱关系。
- 关键规则:前趋图的每一对结点必须是相邻关系(直接联系),不能凭传递性写成间接关系(如 P1→P2、P2→P5,不能写 P1→P5)。
7.3 同步与互斥(★★★★★)
| 概念 | 定义 | 关键 | 举例 |
|---|---|---|---|
| 进程同步(按顺序) | 协调多进程执行顺序以共享资源 | 注重先后顺序 | 读进程等写进程写满管道才读 |
| 进程互斥(独占) | 关键资源同一时刻只允许一个进程访问 | 注重独占性 | 打印机等临界资源 |
7.4 PV 操作细节(★★★★★)
| 操作 | 步骤 | 条件判断 | 本质 |
|---|---|---|---|
| P(wait) | 信号量 S 减 1 | S-1 后 S≥0 继续执行;S<0 则阻塞并插入阻塞队列 | 申请资源 |
| V(signal) | 信号量 S 加 1 | S+1 后 S>0 继续执行;S≤0 则唤醒一个阻塞进程入就绪队列 | 释放资源并唤醒 |
- 词源:荷兰语 Proberen(测试)、Verhogen(增加),对应 Wait、Signal。
-
考法:给定临界资源数量,问有多少进程在等待(S<0 时 S 即等待数)。 - 互斥信号量初值为资源数(通常 1);同步信号量按前趋图边的约束设置。
