跳到正文
WonderlandKnowledge Garden

操作系统

Operating System

精讲笔记 kaws-y 约 12 分钟 #学习资料

考点定位:综合知识选择题稳定考点,含 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. 考试重点

  1. PV 题:根据前驱图写出信号量初值与 P/V 位置(必考推理)。
  2. 给定页面访问序列与页框数,计算 FIFO/LRU 缺页次数。
  3. 判断死锁必要条件是否被破坏、银行家算法是否安全状态。
  4. 磁盘调度算法计算总寻道距离。
  5. 混合索引结构下文件最大长度计算(直接块 + 各级间接块 × 地址项数 × 块大小)。

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. 随堂测试

  1. 运行中的进程等待 I/O 完成后会进入什么状态?
  2. Belady 异常出现在哪种置换算法中?
  3. 破坏「循环等待」条件的常见方法是什么?
参考答案 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);同步信号量按前趋图边的约束设置。
0%