简介面向西北工业大学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, keylambda 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, keylambda p: p.arrive) # SJF谁短谁先跑pick 只看服务时间 sjf lambda q: min(q, keylambda 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(lastFalse) # 淘汰最久未使用 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(block4096, ptr4, n_direct12): 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 的磁道总数手算过的东西和看过的东西在考场上完全是两个状态。我吃过这个亏笔记看得滚瓜烂熟一到手算地址翻译就卡在十六进制换位上那道题的分丢得毫无技术含量。从那以后我每次看这类知识点梳理都会强迫自己先合上笔记把状态迁移图画一遍、把关键参数算一遍再翻回去对答案对不上的地方才是真正要补的洞。希望帮到你。本文还有配套的精品资源点击获取
简介面向西北工业大学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, keylambda 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, keylambda p: p.arrive) # SJF谁短谁先跑pick 只看服务时间 sjf lambda q: min(q, keylambda 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(lastFalse) # 淘汰最久未使用 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(block4096, ptr4, n_direct12): 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 的磁道总数手算过的东西和看过的东西在考场上完全是两个状态。我吃过这个亏笔记看得滚瓜烂熟一到手算地址翻译就卡在十六进制换位上那道题的分丢得毫无技术含量。从那以后我每次看这类知识点梳理都会强迫自己先合上笔记把状态迁移图画一遍、把关键参数算一遍再翻回去对答案对不上的地方才是真正要补的洞。希望帮到你。本文还有配套的精品资源点击获取
