跳转至

操作系统考前突击

Danger

这门课距离考试还有一坤天, 是时候开学了!

听别人说内容来自: 王道考研 + 最后一节课的超长超大PPT + 随机闪现模拟题

Chapter 1: 引论

(1) 操作系统的定义与作用:

  • 定义: 是一组控制和管理计算机系统中的各种软硬件资源, 合理地组织计算机系统的工作流程, 方便用户使用的程序的集合
  • 作用:
    1. 资源管理的观点: OS 是系统资源的管理者 (硬件和软件资源)
    2. 用户服务的观点: OS 是用户与裸机之间的接口

(2) 操作系统的四大特征:

  1. 并发
    • def: 指两个或多个事件在同一时间间隔内发生
    • 注意: 与并行 (Parallel) 的区别. 并行是指在同一时刻发生
  2. 共享
    • def: 系统中的资源, 可供内存中 "多个并发执行的进程" 共同使用
  3. 虚拟
    • def: 把一个物理实体映射为多个逻辑实体
    • eg: 通过"时分复用"把一个CPU虚拟成多个CPU, 通过"空分复用"把 物理内存 虚拟成更大的 逻辑内存
  4. 异步
    • def: 在"多道程序环境"下, 程序的执行进度是不确定的. "走走停停", 执行结果也可能不确定

(3) 操作系统的五大功能:

  1. 处理机管理
  2. 存储器管理
  3. 文件管理
  4. 设备管理
  5. 用户接口

(4) 操作系统的分类:

  1. 批处理操作系统
    • 细分: 单道/多道
    • 优点: 资源利用率高, 吞吐量大
    • 缺点: 无交互能力, 周转时间长
  2. 分时操作系统
    • 定义: 把CPU时间分成时间片, 轮流分配给各作业
    • 特征: 交互性强, 独占性
  3. 实时操作系统
    • 特征: 及时性, 可靠性
  4. 通用操作系统
    • def: 如果一个 OS 兼有 批处理, 分时处理, 实时处理 三者中的两者及以上, 这样的 OS 称为 通用操作系统
核心概念

多道程序设计:

  1. 定义: 内存中 同时存放多道作业, 使它们处于开始和结束之间
  2. 目的: 利用 CPU 和 I/O 设备 的并行工作能力来提高系统效率
  3. 特点: 宏观上并行, 微观上串行

接口:

  1. 作业级接口: 命令行, GUI, 批处理 (用户直接用的)
  2. 程序级接口: System Call (程序员用的, 是程序请求OS服务的唯一途径)

Chapter 2: 处理机管理

Part 1: 进程与线程 - 基础概念

  1. 进程 (Process):

    • 定义: 进程是程序的一次执行过程, 是系统进行资源分配和调度的一个基本单位
    • 特征: 动态性(有生命周期), 并发性, 独立性, 异步性, 结构性
    • 组成 (PCB)
      • PCB (进程控制块, Process Control Block) 是进程存在的唯一标志, 常驻内存
      • 包含: 进程ID, CPU现场(寄存器值), 调度信息(优先级/状态), 控制信息(资源清单)
    • 进程的三种基本状态
      • 运行 (Running): 占用 CPU 执行
      • 就绪 (Ready): 万事俱备, 只欠 CPU(资源都齐了, 就等调度)
      • 等待 (Waiting): 等待某个事件(如 I/O 完成, 信号量)发生
      • alt text

  2. 线程 (Thread):

    • 定义: 线程是进程内的一个可调度实体, 是处理机(CPU)调度的基本单位
    • 注意区分: 进程是资源分配单位, 线程是CPU调度单位
    • 引入目的: 减少并发执行时的时空开销(创建, 切换快), 提高并发性

  3. 进程 vs 线程的区别:

    • 调度: 线程是调度单位, 进程是资源分配单位
    • 并发性: 进程间可并发, 线程间也可并发
    • 拥有资源: 进程拥有资源, 线程只拥有必不可少的资源(如寄存器, 栈), 但共享进程资源
    • 开销: 线程切换开销远小于进程(不需要切页表等环境)

Part 2: 进程同步与互斥 - 信号量机制

(1) 什么是 PV 操作?

  1. 信号量 (S): 就是一个 "计数器", 代表资源的数量
  2. P 操作 (Wait): "申请/拿走"
    • 意思就是: 我要用一个资源
    • 动作: 把计数器 S 减 1 (\(S=S-1\))
    • 关键规则: 如果减完发现 \(S<0\) (也就是本来就没资源了), 那你就在门口排队等着(阻塞), 别进去捣乱
  3. V 操作 (Signal): "释放/归还"
    • 意思就是: 我用完了, 还回去
    • 动作: 把计数器 S 加 1 (\(S=S+1\))
    • 关键规则: 如果加完发现还有人在排队 (\(S \leq 0\)), 你就叫醒(唤醒)排队的那个人: "喂, 有空位了, 快进去!"

TLDR: P 是 减(拿钥匙), 减到负数就去睡; V 是 加(还钥匙), 加完喊人起来嗨

  • P(S): S--
  • V(S): S++

(2) 两大核心场景

  1. 互斥 (Mutex)
    • 问题: 只有一个厕所(临界资源), 一次只能进一个人. 如果A正在用, B就不能进
    • 解决方法:
      • 设置一个信号量 mutex = 1(代表只有 1 把钥匙)
      • 进去前 (P): 拿走钥匙 (P(mutex)). 如果没有钥匙了, 就在门口等
      • 出来后 (V): 还回钥匙 (V(mutex)). 让下一个人拿
    • 代码模式:
      C
      1
2
3
      P(mutex);  // 拿锁
[上厕所...] // 临界区代码
V(mutex);  // 开锁
  2. 同步 (Sync)
    • 问题: A 跑完第一棒, B 才能跑第二棒. B 必须等 A 的信号
    • 解决方法:
      • 设置一个信号量 S = 0(代表 A 还没跑完, B 手里没棒子)
      • B 的代码: P(S). 因为 S=0, 一减就是负数, B 只能死等
      • A 的代码: 跑完了, 执行 V(S). 把 S 变成 1, 相当于把棒子递给 B, 唤醒 B 接着

(3) 两类核心问题

[1] Producer-Consumer Problem:

alt text

[2] Readers-Writers Problem:

alt text

Part 3: CPU 调度 - 算法计算题

基础概念

(1) 三级调度

  1. 高级调度
    • aka. 作业调度
    • 地点: 磁盘 -> 内存
    • 频率: 最低
  2. 低级调度
    • aka. 进程调度
    • 地点: 内存 -> CPU
    • 频率: 最高
  3. 中级调度
    • aka. 交换调度
    • 地点: 内存 <-> 磁盘
    • 频率: 中等 [目的是 节省内存空间]

(2) 调度方式: 抢占式与非抢占式

别人正在吃饭(用CPU)时, 能不能把他赶下来?

抢占定义

指的是: "新来的 process" 能不能抢走 "正在运行的 process" 的 CPU

  1. Non-preemptive [非抢占式]
    • 不能赶走正在运行的进程
    • 只要我抢到了 CPU, 我就一直用, 直到我用完(任务完成)或者我自己主动放弃(比如我去等 I/O 了)
  2. Preemptive [抢占式]
    • 可以赶走正在运行的进程
    • 虽然我正在用 CPU, 但如果更有资格的人来了(优先级更高), 或者我的时间到了(时间片用完), 操作系统会强行把 CPU 收回, 分配给别人
    • 现代OS主要采用的方式!

(3) 调度时机

  1. 任务完成 or 出现异常
  2. 因某种原因由"运行"变成"等待"状态
  3. 时间片用完
  4. 采用"可抢占调度方式"时, 有更高优先级进程进入就绪队列

排队算法

(1) 三个核心概念

  1. 周转时间
    • def: 从你提交作业开始, 到你做完作业离开为止, 一共花了多少时间
    • 周转时间 = 运行时间 + 等待时间
  2. 等待时间
    • def: 在就绪队列里纯排队的时间
    • 等待时间 = 周转时间 - 运行时间
  3. 带权周转时间
    • def: 带权周转时间 = (周转时间 / 运行时间)

(2) 三种核心算法 (怎么排队)

  1. FCFS: 等价于 FIFO
    • 规则: 谁先到谁先用 CPU
    • 特点: 简单, 但对短作业极不公平
  2. SJF: 短作业优先, 先用 CPU 的是短作业
    • 规则: 贪心算法. 谁干活快(运行时间短), 谁先上
    • 特点: 平均等待时间最短
    • 注意: 分为"非抢占式"(一旦开始就不停)和"抢占式"(如果有更短的来了, 就把正在跑的挤下去, 也叫 SRTF). 默认情况通常指非抢占式
  3. Round-Robin, RR: 时间片轮询
    • 规则: 雨露均沾. 设定一个时间片 (Time Quantum)(比如 q=4). 每个进程只能跑这么久, 跑不完就滚回队尾重新排队

Part 4: Deadlock - 银行家算法

(1) 死锁的基础概念

  1. 定义: 多个进程因竞争资源而造成的一种僵局(互相等待), 若无外力作用, 它们都将无法推进
  2. 原因:
    • 系统资源不足
    • 进程推进顺序不合适

(2) 死锁的四个必要条件

这四个条件必须同时具备才会死锁! 只要破坏其中一个, 死锁就解除了

  1. 互斥使用
    • 资源是独占的, 我用你就不准用(如打印机)
  2. 不可剥夺
    • 我抢到的资源, 除非我自愿放弃, 否则你不能强行抢走
  3. 请求保持
    • 吃着碗里的, 看着锅里的. 我手里拿着资源(保持), 同时还要申请新资源(请求), 申请不到我就带着手里的资源一起等, 不肯放手
  4. 环路等待
    • 存在一个进程链: A 等 B, B 等 C ... C 等 A, 形成一个闭环

(3) 死锁的处理方式

  1. 预防死锁

    • 策略: 严格限制, 破坏四个必要条件之一
    • 特点: 即能够保证死锁绝对不会发生, 但系统效率低(管得太宽了)

  2. 避免死锁 (Avoidance)

    • 策略: 银行家算法
    • 特点: 允许进程动态申请, 但要防止系统进入不安全状态

  3. 检测与解除 (Detection & Recovery)

    • 策略: 不管它, 让死锁发生. 系统定时检测, 一旦发现死锁, 就通过撤销进程或剥夺资源来解除
预防死锁: 破坏条件

互斥条件通常改不了(硬件属性), 主要破坏后面三个:

  1. 破坏"请求保持"条件:
    • 方法: 资源的静态分配法
    • 解释: 进程运行前, 必须一次性申请全部资源. 要么全给, 要么一个都不给
  2. 破坏"环路等待"条件:
    • 方法: 资源的顺序分配法
    • 解释: 给系统所有资源编号. 规定进程只能按编号递增的顺序申请资源. (只能先拿1号, 再拿2号, 不能拿了2号回头要1号)
  3. 破坏"不可剥夺"条件:
    • 方法: 当一个进程申请新资源得不到满足时, 必须先放弃已占有的资源(被动释放)
避免死锁: 银行家算法

非常重要. 直接见B站考题讲解:

视频1

视频2

Chapter 3: 存储器管理

Part 1: 基础概念与连续分配

  1. 地址重定位:

    • 逻辑地址: 程序里写的地址(从0开始)
    • 物理地址: 内存条上真正的地址
    • 映射方式:
      • 静态重定位: 装入内存时一次性修改好, 运行期间不能动
      • 动态重定位: 运行时才转换. 需要硬件支持(重定位寄存器). 现代OS都用这个

  2. 动态分区分配算法: 当一个新的作业来了, 要在内存的一堆空闲洞(分区)里找一个塞进去

    • 首次适应 (First Fit): 从头开始找, 第一个能放下的就给它
      • 特点: 空闲分区按地址递增排列
    • 最佳适应 (Best Fit): 找大小最合适(最小能放下)的
      • 特点: 空闲分区按容量递增排列
    • 最坏适应 (Worst Fit): 找最大的那个切一块给它
      • 特点: 空闲分区按容量递减排列

  3. 紧凑技术:

    • 问题: 普通的可变分区分配会产生大量的外碎片(内存里有很多小空洞, 总和够大, 但分散着没法用)
    • 解决方式: 紧凑. 把所有作业挪到一起, 把小洞拼成大洞
      • 需要"动态重定位"支持
    • 硬件支持: 重定位寄存器
      • 因为作业在内存里被挪动了, 它的物理地址变了
      • 必须采用动态重定位, 在程序执行时, 通过硬件自动把逻辑地址加上重定位寄存器中的基址, 算出新的物理地址
内/外碎片
  1. 内碎片
    • 定义: 分配给作业的内存区域内部, 没被利用的空间
    • 出现场景: 固定分区, 分页存储(最后一页通常填不满)
  2. 外碎片
    • 定义: 内存中作业与作业之间, 太小而无法分配给新作业的空闲区
    • 出现场景: 动态分区分配(可变分区)
    • 解决: 紧凑技术

Part 2: 分页存储管理

"页"(Paging) + "块"(Block) + "地址变换"(PageTable + TLB)

  1. 基本原理:

    • 切分:
      • 进程逻辑空间切成 "页" (Page)
      • 内存物理空间切成 "块"/"页框" (Block/Frame)
      • 页大小 = 块大小
    • 页表 (Page Table): 记录 页号 -> 块号 的映射表
    • 快表 (TLB): 为了快, 把常用的页表项放在高速缓存里. 命中率是计算"有效访问时间"的关键

  2. 地址变换:

    • 逻辑地址结构: 前一部分是 页号 P, 后一部分是 页内偏移量 W
    • 物理地址结构: 前一部分是 块号 B, 后一部分是 块内偏移量 W
    • 转换步骤:
      1. 根据逻辑地址算出 P 和 W:
        • P = 逻辑地址 / 页大小
        • W = 逻辑地址 % 页大小
      2. 根据"页表"算出 B:
        • B = 页表[P]
        • 注意: 越界检查! 如果 P >= 页表长度, 报错
      3. 合并物理地址:
        • 物理地址 = B * 块大小 + W

  3. 页面置换算法: 当内存满了, 要调入新页, 必须踢走一个旧页. 踢谁?

    • 最佳置换 (OPT): 踢走以后最长时间不再访问的页
      • 理论算法, 不可实现, 用于评估
    • 先进先出 (FIFO): 踢走最早进来的页
    • 最近最久未使用 (LRU): 踢走过去最长时间没用过的页
      • 性能最好(最接近OPT), 但需要硬件支持(开销大)
    • Clock 算法 (NRU): 像时钟一样转圈扫描. 检查"访问位", 如果是1就清0给次机会, 如果是0就踢走

  4. 对换技术: Swapping

    • 目的: 内存不够时, 把暂时不运行的进程或页面调到外存(磁盘)的对换区, 腾出内存空间
    • 类型:
      • 整体对换: 以"整个进程"为单位(中级调度)
      • 页面对换: 以"页"为单位(部分对换)

  5. 抖动/颠簸: Thrashing

    • 现象: 频繁的缺页, 刚换进来又被换出去. CPU 忙着换页, 没空干活
    • 原因: 给进程分配的物理块太少, 不够它主要工作集用的
    • 解决:
      • 给进程提供足够的物理块
      • 采用局部置换: 若一个进程开始颠簸, 采用局部置换, 不会使其它进程也发生颠簸
      • 控制缺页频率

Part 3: 虚拟内存

  1. 理论基础

    • 局部性原理 (Locality): 程序在执行时, 访问的指令和数据倾向于聚簇(时间局部性, 空间局部性). 这是虚拟内存能跑通的根本原因
    • 请求分页 (Demand Paging): 不一次性全装入, 用到哪一页再调入哪一页

  2. 虚拟存储器必须建立在离散分配的基础上

    • 请求分页
    • 请求分段

  3. 硬件支持

    • 一定容量的内存
    • 较大容量的外存
    • "缺页(段)中断"机制
    • "地址变换"机制

整理一下workflow. 非常重要!

我们可以把这个过程看作 CPU 拿着一个逻辑地址去"寻宝"的过程.

第一阶段: 快速查找

一切始于 CPU 生成一个 逻辑地址 (Logical Address). 系统自动将这个地址拆分为 页号 (Page Number, P) 和 页内偏移量 (Offset, W)

Step 1: 查 TLB (快表)

CPU 首先拿着页号 P 去查 TLB (Translation Lookaside Buffer)

  • 情形 A: TLB 命中 (Hit)

    • 运气很好! TLB 直接给出了对应的 物理块号 (Frame Number, F)
    • 结果: 直接拼接物理地址 (F * 页大小 + W), 访问 Memory (内存). 流程结束(极速模式)

  • 情形 B: TLB 未命中 (Miss)

    • TLB 里没记录, 必须去查慢速的 Page Table (页表). 这通常需要多访问一次内存

第二阶段: Page Table Lookup

如果 TLB 没找到, CPU 就去访问内存中的 页表

Step 2: 查页表

根据页号, 找到对应的页表项. 此时要检查页表项中的 "状态位/存在位" (Valid/Present Bit)

  • 情形 A: 页在内存中 (Valid)

    • 页表项显示该页已经在内存里了(有对应的块号).
    • 动作:
      1. 读出物理块号.
      2. 更新 TLB(把这条记录写进快表, 下次就快了).
      3. 生成物理地址, 访问 Memory. 流程结束.

  • 情形 B: 页不在内存中 (Invalid) —— 触发缺页中断

    • 页表项显示该页在磁盘上(状态位为0)
    • 结果: 硬件产生一个 缺页中断 (Page Fault), 当前进程暂停, OS (操作系统) 接管控制权

第三阶段: 缺页处理

这是最耗时的阶段, 涉及 Disk (磁盘) I/O 和 Page Replacement (页面置换)

Step 3: 操作系统介入

  1. 保留现场: OS 保存当前进程的 CPU 寄存器状态
  2. 分析原因: 确认是合法的缺页(数据在磁盘), 而不是非法访问(越界)

Step 4: 磁盘寻址

OS 根据页表中的外存地址, 在 Disk (磁盘/对换区) 中找到那个丢失的页

Step 5: 内存分配 (关键分支)

OS 试图把这一页从磁盘搬到内存. 它检查 Memory 是否还有空闲的物理块?

  • 分支 A: 有空闲块
    • 直接分配一个空块
  • 分支 B: 内存已满 (无空闲块)
    • 执行页面置换算法 (如 LRU):
      1. 选出一个倒霉的"牺牲页" (Victim Page)
      2. 写回磁盘 (Swap Out): 如果该页被修改过(Dirty Bit = 1), 必须把它写回 Disk
    • 更新页表: 把牺牲页的状态改为"无效/不在内存"

Step 6: 数据调入 (Swap In)

  • 启动 I/O 操作, 把目标页从 Disk 读入刚才腾出来的 Memory 物理块中

第四阶段: 恢复执行

Step 7: 更新映射

  • OS 修改页表: 把目标页的状态改为"有效/在内存", 填入新的物理块号
  • (可选) 更新 TLB

Step 8: 重启指令

  • OS 恢复进程的上下文, 重新执行刚才那条导致缺页的指令
  • 这次执行时: TLB 或 页表 必定命中, 数据顺利拿到

总结: 四个组件的互动关系

  1. TLB (快表): 是 页表 的缓存(Cache). CPU 先问它, 它不知道再问页表
  2. Page Table (页表): 是 Memory 的地图. 它告诉 CPU 数据是在 Memory 里, 还是被踢到了 Disk 上
  3. Disk (磁盘): 是 Memory 的后备仓库(虚拟内存的实体). 当 Memory 满时, 用它来暂存数据(Swapping)
  4. Memory (内存): 是 CPU 唯一能直接读写数据的地方. 所有在 Disk 上的数据, 必须先搬到这里才能用

Chapter 4: 设备管理

(1) I/O 控制方式

原则: 尽量减少主机(CPU)对 I/O 控制的干预, 把主机从繁杂的 I/O 事务中解脱出来

  1. 程序 I/O (轮询):
    • 特点: CPU 必须不停地去问设备"好了没? 好了没?"
    • 缺点: CPU 利用率极低, 串行工作
  2. 中断驱动:
    • 特点: 设备准备好了就发一个中断信号给 CPU. CPU 可以去干别的, 收到中断再回来处理数据
    • 进步: 实现了 CPU 和 I/O 设备之间的并行工作
    • 缺点: 每次只能传一个字(Byte/Word), 数据量大时中断太频繁, CPU 还是累
  3. DMA (Direct Memory Access):
    • 特点: 直接内存存取. CPU 只需要告诉 DMA 控制器"传什么, 传多少, 送到哪", 剩下的搬运工作由 DMA 完成. 以数据块为单位传输
    • 进步: CPU 仅在开始和结束时参与, 干预更少了
  4. 通道 (Channel):
    • 特点: 通道是一个独立的处理机(弱智版的 CPU), 有自己的指令程序. CPU 只要发一条指令, 通道就能完成一整组复杂的 I/O 任务
    • 进步: CPU 干预最少

(2) 缓冲管理

  • 为什么要引入缓冲区:

    • 缓和 CPU 和 I/O 设备速度不匹配的矛盾
    • 降低对 CPU 的中断频率
    • 提高 CPU 和 I/O 设备之间的并行性

  • 缓冲类型:

    • 单缓冲
    • 双缓冲(乒乓缓冲)
    • 循环缓冲
    • 缓冲池(Buffer Pool, 公用缓冲)

(3) 设备分配与设备独立性

  1. 数据结构

    • SDT (系统设备表): 整个系统一张, 记录所有设备状态
    • DCT (设备控制表): 每个设备一张
    • COCT (控制器控制表): 每个控制器一张
    • CHCT (通道控制表): 每个通道一张

  2. 设备独立性

    • 定义: 应用程序独立于具体使用的物理设备
    • 核心实现:
      • 用户在程序里使用 "逻辑设备名" (e.g. /dev/printer)
      • 系统在实际执行时, 通过一张 LUT [逻辑设备表, LookUp Table], 把"逻辑设备名"映射到"物理设备名" (e.g. Printer_01)
    • 好处:
      • 灵活性: 物理设备坏了, 系统换一台分配就行, 用户程序不用改
      • 重定向: 输出可以方便地从打印机改到文件

(4) SPOOLing 技术 [假脱机]

  • 作用: 将一台独占的物理设备(如打印机), 虚拟为多台逻辑设备, 允许多个进程共享它
  • 系统组成:
    • 输入/输出井: 在磁盘上开辟的区域, 用来暂存数据
    • 输入/输出缓冲区: 在内存中, 用于数据中转
    • 输入/输出进程: 专门负责搬运数据的进程
  • 实例: 共享打印机原理
    • 当用户进程请求打印时, 系统并不是真的把打印机分配给它
    • 第一步: 系统在 "磁盘输出井" 中申请一个空闲区, 把要打印的数据填进去
    • 第二步: 系统申请一张"打印请求表", 挂到打印队列上
    • 结果: 用户进程觉得"打印好了", 继续执行. 实际上, 真正的打印机空闲时, 输出进程才会去磁盘捞数据打印

(5) 磁盘存储器管理 [Disk Management]

这部分考磁盘调度算法, 通常给一个磁道访问序列, 让你算平均寻道长度

磁盘访问时间

总时间 = 寻道时间 + 旋转延迟 + 传输时间

目标: 使磁盘的 "平均寻道时间" 最短

Note

寻道时间 (Seek Time): 磁头移动到指定磁道(柱面)的时间

这一部分最慢, 且占比最大, 所以优化的重点是它

调度算法

场景:

  • 磁盘 = 一栋 200 层的大楼 (楼层编号 0 - 199)
  • 磁头 = 送餐员 (当前他在 50 层)
  • 请求 = 有人点了外卖
    • 90 层 的住户点了
    • 10 层 的住户点了
    • 80 层 的住户点了

算法:

  1. FCFS: 先来先服务. first come, first serve
    • 原则: 完全按照订单进来的时间顺序跑, 不带脑子
    • 顺序: 50 -> 90 -> 10 -> 80
  2. SSTF: 最短寻道时间优先. shortest seek time first
    • 原则: "谁离我最近, 我就先送谁"
    • 顺序: 50 -> 80 -> 90 -> 10
  3. SCAN: 扫描. elevator
    • 原则: 即使离他最近的是楼下, 但如果电梯现在的设定是 "正在上行", 那它就必须一条道走到黑. 直到顶楼, 再回头
    • 顺序: 50 -> 80 -> 90 -> 199 -> 10 -> 0
  4. C-SCAN: 扫描. elevator + 瞬移
    • 原则: 单向移动. 到了头直接瞬间飞回起点(不反向服务), 重新开始扫描
    • 顺序: 50 -> 80 -> 90 -> 199 -> 0 -> 10

alt text