1.1 进程抽象#

• 进程 = 运行中的程序，包含地址空间、寄存器状态、打开的文件等
• 状态机：Running ↔ Ready ↔ Blocked
• OS 用 PCB（Process Control Block） 记录每个进程的状态

1.2 Limited Direct Execution（怎么安全地把 CPU 交给进程）#

• 直接让进程跑在硬件上性能最好，但进程可以为所欲为
• 解法：硬件提供两种模式
  • user mode：进程跑，权限受限
  • kernel mode：OS 跑，可以做任何事
• 进程做特权操作（IO、申请内存）必须通过 syscall 陷入内核
• OS 通过 timer interrupt 强制夺回 CPU，进程无法赖着不走

1.3 Context Switch（怎么切换进程）#

• CPU 只有一套寄存器，切换时要保存当前进程的全部寄存器状态
• 保存到该进程的 PCB，下次恢复时读回来
• 切换本身有开销，不能切太频繁

1.4 调度算法（切换给谁）#

按历史演进顺序：

MLFQ 核心思想：

• 新进程先放高优先级队列（当短任务对待）
• 用完时间片还没结束，降到低优先级队列
• 自动区分 IO 密集型（经常主动放弃 CPU）和 CPU 密集型进程
• 定期 boost 所有进程到最高优先级，防止饿死

演进脉络#

1
base+bounds → 分段 → 分页 → TLB → 多级页表 → swap
2
     ↓            ↓       ↓
3
  外部碎片    碎片改善   彻底解决碎片，但引入新问题

2.1 base + bounds（最朴素的做法）#

• 给每个进程分配一段连续物理内存
• 两个寄存器：base（起始地址）+ bounds（大小），硬件自动检查越界
• 问题：必须连续，产生大量外部碎片

2.2 分段（Segmentation）#

• 把进程内部按逻辑切成几段：代码段、堆、栈
• 每段单独分配物理内存，各有自己的 base + bounds
• 虚拟地址高位 = 段号，低位 = 段内偏移
• 改善了碎片，但每段本身仍要求连续，外部碎片没有根本解决

2.3 分页（Paging）#

• 把内存切成固定大小的块：物理内存每块叫 frame，虚拟内存每块叫 page（典型 4KB）
• 虚拟地址结构：[ VPN（页号） | offset（页内偏移） ]
• OS 维护页表（page table）：VPN → PFN（物理帧号）的映射
• 外部碎片彻底消失（固定大小，随时可用）
• 新问题：
  • 页表太大：32位地址空间 + 4KB页 = 每进程 100万条页表项
  • 访问慢：每次内存访问要先查页表（一次额外内存访问）

2.4 TLB（解决”慢”的问题）#

• Translation Lookaside Buffer，页表的硬件缓存
• 把最近用过的 VPN→PFN 翻译缓存在 CPU 里
• 命中时不需要访问内存，大多数情况下命中率很高（局部性原理）
• context switch 时需要处理 TLB（flush 或打标记区分不同进程）

2.5 多级页表（解决”页表太大”的问题）#

• 只给实际用到的地址空间建页表，没用的部分不分配
• 页表本身也分页，形成树状结构（二级、三级页表）
• 用空间换时间的反向操作：牺牲一点查询速度，换来页表本身更小
• 64位系统典型用四级页表

2.6 Swap（内存不够用怎么办）#

• 把暂时不用的 page 换出到磁盘（swap 空间），腾出物理 frame
• 访问被换出的 page 触发 page fault，OS 从磁盘读回来
• 关键：页面置换算法决定换出谁
  • OPT（最优，理论上最好但不可实现）
  • LRU（最近最少使用，实际常用近似实现）
  • Clock 算法（LRU 的近似，硬件支持）

3.1 线程是什么（vs 进程）#

• 线程 = 进程内部的执行单元
• 同进程的线程共享：地址空间（代码、堆、全局变量）
• 每个线程独有：栈、寄存器状态
• 类比：进程是房子，线程是房子里的人，共用客厅（堆），各有自己房间（栈）

3.2 Race Condition（为什么会出问题）#

• 多线程同时执行 counter++，实际是三步：读 → 加 → 写
• 线程可以在任意步骤之间被切换，导致结果不可预测
• 临界区（critical section）：访问共享数据的那段代码，必须保护

3.3 锁（互斥）#

• 进临界区前加锁，出来解锁，同一时间只有一个线程能进
• 实现需要硬件支持的原子指令：test-and-set、compare-and-swap
• 自旋锁：没抢到就循环等，简单但浪费 CPU
• 阻塞锁：没抢到就睡眠，OS 调度其他线程，抢到时再唤醒

3.4 条件变量（等待条件）#

• 锁只能解决互斥，线程还需要等某个条件成立再继续
• 典型：生产者消费者问题
  • 消费者发现队列空，wait 主动睡眠并释放锁
  • 生产者放完东西，signal 唤醒消费者
• 注意：wait 必须在循环里检查条件（防止虚假唤醒）

3.5 信号量（通用原语）#

• 一个整数计数器 + PV 操作（wait/post）
• 初始值 = 1：等价于锁
• 初始值 = N：允许最多 N 个线程同时进入
• 初始值 = 0：线程间同步（一个等另一个完成）
• 锁和条件变量都可以用信号量实现，反之亦然

3.6 死锁#

• 多个线程互相等对方持有的锁，永远卡住
• 成立需要同时满足 Coffman 四条件：
  1. 互斥（资源不可共享）
  2. 持有并等待（拿着锁再等另一个）
  3. 不可抢占（锁不能被强制拿走）
  4. 循环等待
• 破掉任意一个即可避免
• 最常用：破循环等待——规定所有线程按固定顺序加锁

4.1 IO 设备基础#

• CPU 通过内存映射 IO 或 in/out 指令与设备通信
• 中断 vs 轮询：等设备完成时，中断让 CPU 去做别的事；轮询简单但浪费
• DMA：让设备直接读写内存，不占用 CPU

4.2 磁盘结构#

• 盘片、磁道、扇区，读写头要寻道 + 旋转等待，延迟大
• 磁盘调度算法决定 IO 请求顺序，减少寻道时间：
  • SSTF（最短寻道时间优先）
  • SCAN / C-SCAN（电梯算法）

4.3 文件系统基础#

• 文件系统要解决：怎么在磁盘上组织数据，让 OS 能找到文件
• inode：存储文件元数据（大小、权限、数据块位置），每个文件一个
• 目录：本质是文件名 → inode 号的映射表
• 数据块：实际存文件内容
• 位图：记录哪些 inode / 数据块是空闲的

4.4 文件系统实现（以 vsfs 为例）#

磁盘布局：

1
| superblock | inode bitmap | data bitmap | inode table | data blocks |

• 读一个文件：查目录 → 找 inode → 找数据块（多次磁盘访问）
• 缓存（page cache）：把热数据缓存在内存里，减少磁盘访问

4.5 崩溃一致性（核心难点）#

• 写文件需要多次磁盘写（更新 inode、bitmap、数据块），断电可能只写了一部分
• 导致文件系统状态不一致

两种解法：

fsck（文件系统检查工具）

• 崩溃后启动时扫描整个磁盘，找并修复不一致
• 慢，大磁盘要扫很久

Journaling（日志）

• 写数据前先把”打算做什么”写到日志区
• 崩溃重启后看日志，重放未完成的操作
• 分两种：
  • data journaling：数据和元数据都记日志，安全但慢
  • metadata journaling：只记元数据日志，数据直接写，性能好（ext4 默认）

4.6 其他文件系统话题#

• LFS（Log-structured File System）：把磁盘当日志用，所有写操作追加到末尾，对 SSD 友好
• SSD vs HDD：SSD 没有寻道延迟，但有写放大、磨损均衡等问题
• 分布式文件系统：NFS、AFS，跨网络访问文件，一致性更复杂