操作系统四块知识一套账：状态迁移边界与自检框架

简介：面向西北工业大学801考研的操作系统复习资料，以单份PDF形式梳理课程核心知识，适合基础阶段搭建知识框架，也便于冲刺阶段查漏补缺。内容按操作系统概述、进程管理、内存管理、文件管理、设备管理与作业调度六部分展开，覆盖进程状态与PCB、先来先服务与短作业优先等调度算法、同步互斥与PV操作、固定分区与分页分段、虚拟内存与内外碎片、文件逻辑与物理结构、I/O控制方式及作业周转时间等高频考点，并对易混概念和算法差异作出归纳，便于对照教材建立复习索引。压缩包内共1个PDF文件，大小约19.05MB，内容集中，适合按章节检索、在平板或电脑上阅读标注并反复翻阅。已有167人学习，可作为801专业课复习中的提纲式笔记与考前速览材料，帮助快速定位重点章节和薄弱环节。

1. 四块知识其实是一套账：操作系统考的从来不是概念，而是状态迁移的边界

翻过一份把操作系统压成几十页的手写扫描笔记，最反直觉的地方在于：进程、内存、文件、设备看上去是四套独立知识，实际上却对应同一套记账逻辑——资源有状态，状态只能沿合法边界迁移，考题和真实内核出问题的地方都集中在边界上。801 这类自命题科目真正爱考的是“进程在等 I/O 时被调度走，谁保存了它当时的现场”这类问题；而“什么是 PCB”这种表层问题并非重点。把这套账理顺之后，需要背诵的内容会减少一大半，剩下的内容基本都能自己推导出来。

2. 进程与 PCB：为什么“状态”必须落进一个结构体里

大多数人对进程的理解停留在“程序的一次执行”，这句话没错，但几乎不解决问题。真正让人算错题、也真正让内核写出 bug 的，是状态机的边和 PCB 的字段；笔记如果只画了五个方框和箭头，却没有说明哪条边是谁触发的，后面调度、同步、死锁就会全部只能靠背。这一章把这三样拆开看：状态机的约束、PCB 的字段动机、调度算法的选择函数。

2.1 进程状态机：五条边里只有两条是进程自己走的

从一个刚提交的作业到进程终止，中间的状态是新建、就绪、运行、等待、终止。就绪到运行由调度器决定；运行到就绪是时间片用完或被更高优先级抢占；运行到等待由进程自己触发，典型场景是读文件、等锁、等 I/O 完成，这类阻塞叫自愿阻塞；等待到就绪由外部事件完成后唤醒；运行到终止则是进程退出。

最容易被画错的一条边是“等待直接到运行”。这条边不存在，原因很直白：被唤醒的进程只是重新具备了运行资格，能不能拿到 CPU 得由调度器按策略决定。如果允许等待直接跳到运行，等于事件完成的一瞬间强行抢占 CPU，所有调度策略都会立刻失效，优先级、时间片、多级队列全部作废。内核里唤醒的正确动作是“把 PCB 从等待队列摘下、挂到就绪队列”，仅此而已。

还有一个高频混淆点：阻塞和挂起不是一回事。阻塞是进程在内存里等事件，挂起是把进程映像换到外存、腾出内存给别的进程用，这才有了七状态模型里的“就绪挂起”和“等待挂起”。做题时如果题目出现“内存紧张”“换出”，那考的是挂起；只说“等待 I/O”，那是阻塞。

2.2 PCB：内核里唯一信得过的现场记录

进程切换的本质是“把一套 CPU 寄存器换掉，再把另一套装进来”。CPU 只有一套物理寄存器，被切走的进程的所有现场必须有个地方存，这个地方就是 PCB；它也是内核态数据，用户态代码碰不到。

/* 极度简化的 PCB 模型，字段取自教科书常见划分，不代表任何真实内核实现 */ struct pcb { int pid; /* 进程标识，队列和表里的主键 */ int state; /* NEW/READY/RUNNING/WAITING/TERMINATED */ uint64_t pc; /* 程序计数器：切走时下一条要执行的指令地址 */ uint64_t regs[32]; /* 通用寄存器现场，切换时整组保存/恢复 */ uint64_t pgtbl; /* 页表基址：这个进程地址空间的身份 */ int priority; /* 调度优先级，多级反馈队列里会被动态改写 */ struct pcb *next; /* 就绪/等待队列指针，决定入队是 O(1) 还是 O(n) */ int exit_code; /* 退出码，留给父进程收尸 */ };

逐个字段看动机。pc和regs是进程切换时的核心现场：没有它们，进程被切走后回来就不知道执行到哪了，这就是操作系统的“后悔药”。pgtbl决定了切换的代价量级：同一地址空间内的线程切换不用换它，进程切换要换，而换页表往往伴随 TLB 失效。next指针是纯粹的数据结构选择：用链表就是 O(1) 入队但调度时要遍历找优先级最高的，用优先级数组或多级队列则是 O(1) 选人但可能浪费内存。priority是唯一一个“策略会反过来改数据结构”的字段，老化机制就是不停给它减分。

为什么 PCB 必须放在内核态、用户不可写，道理和虚拟内存是同一个：如果进程能改自己的state或pgtbl，隔离就彻底不存在了。PCB 就是内核记录进程状态的唯一可信位置，所有系统调用最终都会修改它。

2.3 调度算法：同一个循环，换一个 pick 函数

把教材里那一堆 FCFS、SJF、优先级、多级反馈队列摊开看，它们的骨架完全一样：一个循环，每次从就绪集合里挑一个进程，让它跑，跑完或被打断再挑。区别只在“怎么挑”以及“能不能打断”。

from dataclasses import dataclass @dataclass class Proc: pid: str arrive: int # 到达时刻（进入就绪队列的时间） burst: int # 需要占用 CPU 的时间 def schedule(procs, pick): """ pick: 从当前就绪集合里选出下一个执行的进程 非抢占模型：选中后一次跑完整个 burst 返回 [(pid, 周转时间, 带权周转时间), ...] """ t, ready, rest, out = 0, [], sorted(procs, key=lambda p: p.arrive), [] while rest or ready: while rest and rest[0].arrive <= t: # 把已到达的放进就绪队列 ready.append(rest.pop(0)) if not ready: # CPU 空转，时间跳到下一个到达点 t = rest[0].arrive continue p = pick(ready) ready.remove(p) t += p.burst # 非抢占：一次跑完 turnaround = t - p.arrive out.append((p.pid, turnaround, turnaround / p.burst)) return out # FCFS：谁先来谁先跑，pick 只看到达时间 fcfs = lambda q: min(q, key=lambda p: p.arrive) # SJF：谁短谁先跑，pick 只看服务时间 sjf = lambda q: min(q, key=lambda p: p.burst)

参数含义需要说清：arrive决定就绪队列的入队时机，burst是服务时间，周转时间是“完成时刻减到达时刻”，带权周转时间是“周转时间除以服务时间”，分母弄错是考场上最常见的失分点。把pick换成max就是优先级调度，换成“剩余时间最短”并允许打断就是 SRTF。

三种策略的设计动机值得逐条说。FCFS 最简单、天然公平，但有护航效应：一个长作业排在队首，后面所有短作业都要干等，平均周转时间会大幅增加。SJF 能证明平均周转时间最小，代价是它要求预知burst，而现实中没人知道下一个进程要跑多久；工程上的做法是用指数平滑预测，把上一次的预测值和这次的实际值加权混合，权重越小越保守。就算预测准了，SJF 还会饿死长作业，所以优先级调度必须配老化，等待越久优先级越高，用一点最优性换无饥饿。

多级反馈队列是这三种思路的折中方案，也是我认为最值得琢磨的设计：新进程进最高优先级队列，给一个很短的第一个时间片；用完没结束就降到下一级，时间片变长；一直降到最低级。它不需要预测运行时间，却能用“降级”近似出 SJF 的效果，因为短作业在第一级就跑完了，长作业自动沉底。代价是两个参数没法从理论上定：队列级数和每级时间片长度，都是靠测量调出来的，这也是它经常被吐槽为“玄学”的原因。

2.4 上下文切换：真正贵的是冷却，不是保存

很多人默认进程切换昂贵、线程切换廉价，然后拿这句话去解释所有性能问题。这句话只在特定前提下成立。直接开销是保存恢复寄存器、切换内核栈、更新 PCB 状态，这部分对进程和线程差不多，量级很小。真正的差距在地址空间：进程切换要换页表基址，TLB 里缓存的地址翻译全部作废，Cache 里的数据也大面积失效，回到用户态后要重新预热。

我一般会这么理解：切换成本由“换不换地址空间”决定，不由“是不是线程”决定。同一个进程里两个线程如果跑在不同核上、访问的数据八竿子打不着，Cache 该失效还是失效；反过来，如果两个进程共享大量内存页，切换后的预热代价也没那么夸张。看到“多开线程更快”这种结论，先问一句：快在哪，是切换省了，还是并发度上去了。

3. 虚拟内存：为什么逻辑地址必须和物理地址解耦

分页这件事，教材上一句话就能说完：把逻辑地址空间切成固定大小的页，映射到物理页框。但真正理解了以后，你会发现虚拟内存解决的从来不是“内存不够”，而是三个更棘手的问题：进程之间不能互相踩内存、程序不能依赖自己被加载到哪个物理位置、内存可以比物理内存小。这一章沿着一次地址翻译的全过程走，把页表项、缺页、置换算法串起来。

3.1 一次地址翻译的完整旅程

CPU 执行一条访存指令，发出的是逻辑地址。MMU 把它切成两部分：低位是页内偏移，高位是页号。先查 TLB，命中就直接拼出物理地址发到总线上；没命中就去查页表，多级页表要一级一级往下走，每一级都取一次内存；如果最后拿到的页表项有效位是 0，触发缺页异常，控制权交给内核。

举一个能落地的例子：32 位地址、页大小 4KB。4KB 等于 2 的 12 次方，所以低 12 位是页内偏移，剩下 20 位是页号。要是用两级页表，每级 10 位，一个地址0x00403A20拆出来就是一级索引0x001、二级索引0x003、偏移0xA20。十六进制下这个拆分特别好做：页大小 4KB 时，最后三位十六进制数字就是偏移，前面全是页号，考场上不用换算成二进制。

多级页表的设计动机常被讲成“节省空间”，其实更准确的说法是应对稀疏地址空间。单级页表要给 20 位页号建 2 的 20 次方个表项，每项 4 字节就是 4MB，每个进程一份，而且这 4MB 必须常驻；可一个进程实际用到的地址往往只集中在几个区域，中间大片是空的。两级页表把一级页表压到 4KB，二级页表按需创建，没用到的那段地址连二级页表都不用建。

注意：多级页表省的是空间，代价是时间。一次 TLB 未命中可能要访存两次甚至四次，这也是 TLB 命中率对性能影响这么大的原因。

3.2 页表项里每一位在干什么

页表项不是只存一个物理页框号，它是一组标志位加一个编号。有效位表示这一页是否在内存里，为 0 就触发缺页；保护位标记这一页可读、可写还是可执行，写一个只读页会触发保护异常而不是缺页，这两类异常的处理路径完全不同；修改位（脏位）表示这一页被写过没有，它决定了换出时要不要写回磁盘，这是纯性能优化，没写过就不用写回；访问位表示这一页最近被访问过，它是 Clock 置换算法的唯一输入。

这几位里，脏位的性价比最高。操作系统在页面换出时，如果脏位是 0，直接把页框回收就行；脏位是 1，就得先写磁盘再回收，一次 I/O 的时间够 CPU 跑几十万条指令。所以“读多写少”的映射文件、代码段，换出成本远低于被频繁写的堆内存。

3.3 LRU 为什么在硬件里做不出来，Clock 怎么近似

理论上最优的置换算法是换掉未来最久不会被访问的那一页，这显然无法实现；退一步，换掉过去最久没被访问的那页，就是 LRU。LRU 在软件里好写，在硬件里几乎做不了：它要求每次访存都更新时间戳或调整链表，这个开销比访存本身还大，而且要在 MMU 里实现，没法靠编译器优化。

硬件只能提供一个访问位。Clock 算法就把所有页框串成一个环，配一个指针：需要换页时看指针指向的页，访问位是 1 就清成 0 并跳过，是 0 就选它换出。这个“给一次免死机会”的动作，本质是用一个 bit 近似“最近有没有被访问”，工程上够用。

from collections import OrderedDict def fifo(refs, frames): q, faults = [], 0 for r in refs: if r not in q: faults += 1 if len(q) == frames: q.pop(0) # 淘汰最早进来的页 q.append(r) return faults def lru(refs, frames): q, faults = OrderedDict(), 0 for r in refs: if r in q: q.move_to_end(r) # 命中：刷新为“最近使用” else: faults += 1 if len(q) == frames: q.popitem(last=False) # 淘汰最久未使用 q[q.__len__()] = r if False else None q[r] = None return faults refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] print(fifo(refs, 3), fifo(refs, 4)) # 9 10：帧数变多，缺页反而增加 print(lru(refs, 3), lru(refs, 4)) # 10 8：栈式算法，不会反常

这段代码里，refs是页面访问序列，frames是可用页框数，返回值是缺页次数。fifo用一个普通列表模拟先进先出队列；lru用OrderedDict维护访问顺序，命中就move_to_end挪到队尾，淘汰时弹队头。

第三行输出就是著名的 Belady 异常：FIFO 在 4 个页框时缺页次数比 3 个页框还多。原因是 FIFO 不满足“栈式算法”性质，增加页框会改变整个淘汰历史，可能刚好把后面要用的页提前踢掉。LRU 和最优算法都是栈式的，小容量的驻留集永远是大容量的子集，所以不会出现这种反常。这也是为什么教材强调这个反例，它说明“加内存一定变快”这种直觉在置换策略上是站不住的。

3.4 内碎片和外碎片：分页为什么没有外碎片

分页的代价是内部碎片：进程最后一页大概率装不满，平均浪费半页。但分页完全没有外部碎片，因为所有页框大小一致，任意空闲页框都能装任意页，不存在“洞太小塞不进去”的情况。

分段正好相反，段是逻辑单位，长度由程序决定，一段代码、一段数据、一个栈，大小参差不齐。分配久了就会在内存里留下大量小空洞，总量够但拼不出一个连续的大段，这就是外部碎片，解决办法是紧凑，把进程整体挪动，把空洞挤到一起，代价是搬运开销。

段页式是两者的组合：先按逻辑分成段，每段再分页，逻辑结构保住了，物理分配也整齐了，代价是一次访存要查段表再查页表，地址翻译路径更长。页大小 4KB 是一个经典的折中：页太小则页表项数量爆炸、TLB 能覆盖的范围变小；页太大则内碎片浪费加剧、一次缺页要读的数据变多。这个数值不是理论最优，而是几十年工程实践调出来的平衡点。

4. 文件与设备：索引、缓存、调度，其实是同一套思路换了对象

文件管理和设备管理常被当成两块边缘内容，其实它们是前面两章的复用：文件就是“用索引结构管理外存块”，设备管理就是“用队列和调度管理独占资源”。把 inode 看懂，把 DMA 和磁盘调度的动机搞清，这部分几乎不用背。

4.1 inode：文件就是一张索引表加一个编号

目录里存的不是文件内容，而是“文件名到 inode 号”的映射。inode 里放元数据（大小、所有者、权限、时间戳）和块地址。关键是块地址的组织方式：前若干个是直接块，后面跟一级间接、二级间接、三级间接。间接块本身不存数据，只存下一层块的编号。

def max_file_bytes(block=4096, ptr=4, n_direct=12): """ block : 磁盘块大小（字节） ptr : 一个块地址占多少字节，决定每个间接块能装多少指针 n_direct: 直接块数量 返回最大文件字节数与各级间接的容量明细 """ per_block = block // ptr # 每个间接块能放 1024 个指针 detail = {"direct": n_direct * block} total = detail["direct"] cap = per_block for level in (1, 2, 3): cap *= per_block if level == 1 else per_block ... return total, detail print(max_file_bytes())

按 4KB 块、4 字节指针算，每个间接块能放 1024 个指针。12 个直接块覆盖 48KB；一级间接再覆盖 1024 个块，也就是 4MB；二级间接 1024 的平方个块，4GB；三级间接 4TB。这组数字解释了 inode 设计的取舍：绝大多数文件很小，直接块命中，一次寻址就拿到数据，路径最短；少数大文件靠多级间接撑住容量，代价是访问最后一个块要多读几次间接块，每一次都是实打实的 I/O。这本质上是“小文件快、大文件能装”的折中，而不是追求两种都最优。

4.2 三种物理结构的取舍

顺序结构把文件放在连续块上，寻道最少、支持随机访问，缺点是两个：外部碎片，以及文件增长时后面可能没位置了，只能整体搬家。链接结构把文件切成块用指针串起来，没有碎片、随便增长，但只能顺序访问，想读最后一块得从头走一遍，而且指针占空间，中间一个块坏了整条链就断。索引结构给每个文件配索引块，索引块里存所有块的地址，随机访问和增长都支持，代价是多了一层索引块开销，小文件可能为了几百字节专门占一个索引块。

FAT 是链接结构的一个变体，把整条链的指针集中到内存里的一张表，寻道时查表就行，本质上是用内存换访问速度。这三种结构没有绝对优劣，选哪个取决于“这个文件系统主要跑什么负载”：日志类顺序写多用链接变体，数据库类随机读多用索引。

4.3 空闲空间管理：位图与成组链接

位图用 1 bit 标记一个块是否被占用，查找连续的空闲块特别快，因为连续的 bit 可以一次扫描一大片。代价是占空间：1TB 磁盘、4KB 块，一共 2 亿多个块，位图就是 32MB 左右，这部分通常常驻内存。

空闲链表把空闲块本身串成链，几乎不额外占空间，但想找一段连续空间就得遍历。成组链接是折中方案，把空闲块按组串起来，每组的第一块记录下一组的块号和数量，分配时一次能拿到一批，既省空间又不用全程遍历。这几种方案的取舍都能用一句话概括：拿空间换查找速度，还是拿查找速度换空间。

4.4 DMA 到底省了什么，磁盘调度又在省什么

I/O 控制方式有三种。程序查询是 CPU 死等设备就绪，全程占用处理器；中断驱动是设备准备好一个字节就中断一次，CPU 每次都参与数据搬运，好处是不用空转；DMA 是 CPU 只发一条命令，把内存地址、传输长度告诉控制器，剩下的搬运由控制器直接和内存打交道，全部传完才中断一次。

这里的常见误解是把 DMA 当成“让磁盘变快”。DMA 省的是 CPU 搬运数据的时间，磁盘本身的机械寻道一点没变快。区分这两件事很重要：I/O 响应时间由磁盘决定，CPU 占用率由控制方式决定，题目问哪个就答哪个。

磁盘调度才是真正在减少寻道。FCFS 按请求顺序服务，公平但平均寻道距离大；SSTF 每次选离当前磁头最近的请求，平均寻道最短，但远端请求可能永远等不到；SCAN 像电梯一样单向扫到端点再折返，牺牲一点平均寻道换无饥饿。

拿一组真实可算的数字对比：磁头当前在 100 磁道，请求序列是 55、58、39、18、90、160、150、38、184。SSTF 的走法是 100→90→58→55→39→38→18→150→160→184，总移动 248 个磁道。SCAN 假设向大号方向扫，走法是 100→150→160→184→199→90→58→55→39→38→18，总移动 280 个磁道。

有意思的是这里 SCAN 反而更差。这不是算错，而是它揭示了 SCAN 的真实定位：它优化的是“最大等待时间”和“响应方差”，不是总移动距离。回程那 109 个磁道是白跑的，但正因为扫到端点，远处的请求有一个可预期的等待上界。题目如果问“平均寻道长度最短”，答案是 SSTF；问“不会饥饿”，答案才轮到 SCAN。

5. 排查清单：五类“看着会、一做就错”的翻车现场

复习到后期，卡住人的往往不是不懂，而是懂了个大概然后在细节上翻车。下面五条是这类笔记里反复出现、也最容易在考场上丢分的地方，每条按现象、原因、解决三段写。

5.1 同步与互斥：PV 写反与初值给错

第一条，现象是 PV 操作能默写出来，但推出执行序列时发现两个进程互相等待。原因几乎都是 P 操作的顺序问题：一个进程先 P 互斥量再 P 资源量，另一个进程占着资源等互斥量，双方各持一把锁不放手。解决办法是记住固定顺序：先 P 资源信号量、再 P 互斥信号量，V 操作顺序反过来。互斥量只保护临界区，资源量才代表“有没有东西可用”，先拿资源再进临界区，逻辑上就不可能死锁。

第二条，现象是生产者消费者写出来以后，两个进程变成完全串行，一点并发都没有。原因是把缓冲区计数当成了互斥量，empty和full的初值给成了 1。互斥信号量初值必须是 1，表示临界区只有一个入口；empty的初值是缓冲区容量，full的初值是 0，它们代表的是资源数量而不是锁。初值给错，整个同步关系就退化成了互斥。

5.2 计算题：地址、时间、磁道三个易错位

第三条，现象是页号页内偏移算出来跟答案差一位。原因是页大小和位数的换算没做熟：4KB 就是 2 的 12 次方，偏移 12 位，十六进制下正好是末三位。解决办法是养成习惯，见到十六进制地址先数末三位当偏移，前面的当页号；见到十进制就先除以页大小取整得页号，余数就是偏移，别在脑子里做二进制拆分。

第四条，现象是带权周转时间算出来比 1 还小。原因是分母写成了等待时间或周转时间。带权周转时间的定义是周转时间除以服务时间，服务时间是进程真正占用 CPU 的时长，任何进程的这个比值都不会小于 1，一旦算出小于 1，立刻回头检查分母。

第五条，现象是磁盘调度总移动道数比标准答案少一截。原因是从 0 号磁道或者第一个请求开始算的。磁头有一个初始位置，所有移动都必须从当前位置起算；用 SCAN 还要记得算到端点（比如 199 号磁道）的那一段，这段路虽然不服务任何请求，但它真实发生了。做题时先把磁头位置和请求序列抄在草稿纸最上面，画一条数轴标出来，比在脑子里空想靠谱得多。

6. 从“记住结论”到“能自己推”：一套可验证的自检模型

这份笔记真正有用的地方，不在于它把五章内容压成了几十页，而在于它给出了一套可以反复自检的框架。我在看这类材料时，习惯把每一章都压缩成三个问题：这个资源有哪几个状态，谁有权改这些状态，改一次的代价是什么。进程那一章，状态是就绪、运行、等待，改状态的是调度器和进程自己，代价是上下文切换；内存那一章，状态是页在不在内存、脏不脏，改状态的是缺页处理和置换算法，代价是一次磁盘 I/O；文件那一章，状态是块分配了没有、索引到不到位，改状态的是文件系统和缓存，代价是寻道加传输。

这三个问题的价值在于，它把“背结论”变成了“推结论”。比如页大小为什么是 4KB，按这个框架推：页小则页表项多、TLB 覆盖范围小、缺页频繁；页大则内碎片多、一次缺页搬运的数据多。两边都有代价，所以只能取中间值，具体数字是工程调出来的，但“为什么必须折中”是可以推的。同理，索引结构为什么要有直接块和三级间接，也是同一个推法。

验证方法也很朴素：拿一个具体例子手算一遍，再和笔记对照。算一道 SJF 的周转时间，算一次两级页表的地址拆分，算一遍 SCAN 的磁道总数，手算过的东西和看过的东西，在考场上完全是两个状态。我吃过这个亏，笔记看得滚瓜烂熟，一到手算地址翻译就卡在十六进制换位上，那道题的分丢得毫无技术含量。

从那以后，我每次看这类知识点梳理，都会强迫自己先合上笔记，把状态迁移图画一遍、把关键参数算一遍，再翻回去对答案，对不上的地方才是真正要补的洞。希望帮到你。

本文还有配套的精品资源，点击获取