操作系统存储器管理：从分页分段到页面置换算法全解析

我学《计算机操作系统》第四章的时候一度怀疑自己是不是脑子转不过来。书上从程序的装入和链接一路讲到虚拟存储器页表、分段、段式、段页式、局部性、抖动几个概念轮番上阵我明明每个名词都眼熟做题却总是卡壳。后来才想明白问题出在我把存储器管理当成了一堆需要背的考点而没有把它当成操作系统在资源紧缺时的一条“分配方案链”。这篇就围绕第四章-存储器管理把这条链是怎么一环扣一环的讲清楚从物理内存怎么切、地址怎么映射到虚拟内存怎么换页再到我亲手写的一个C语言模拟实验以及复习时最容易翻车的细节。如果你正在啃这个章节或者在准备操作系统课设、考研复试这篇文章应该能给你一条更容易走通的路。1. 别急着背概念先想想“内存为什么需要管”1.1 程序员和操作系统眼中的内存不是同一个东西写程序的时候我们觉得内存是理所当然的定义一个变量malloc一块空间指针随便指来指去。可在操作系统的视角里内存是一个又贵又小的资源而且同一时刻可能有好几个进程都在抢它。每个进程都以为自己拥有一整块连续的地址空间实际上物理内存被切得七零八落由操作系统负责把这些“假地址”映射到真正的内存条上。所以存储器管理要回答的问题其实很朴素谁住哪块内存、怎么让它们不打架、放不下怎么办、换进换出怎么换。教材第一页经常提到的“内存利用率、程序运行效率、系统可靠性”这三个词本质就是这些问题的目标。学习这一章前先把这句话刻在脑子里逻辑地址是进程视角物理地址是机器视角中间的翻译工作就是存储器管理。1.2 从单道到多道内存管理是被逼出来的在最早的单道程序环境下一个程序独占整个内存CPU遇到I/O操作只能傻等内存再大也用不满。后来有了多道程序设计内存里同时驻留几个程序CPU在它们之间切换利用率才上来。可多道程序带来的第一个问题就是“这些程序怎么塞进内存”。早期方案是连续分配一个进程必须占一整块连续的空间。连续分配已经发展出了好几种策略固定分区是提前把内存切成固定大小的区一个区装一个进程简单但内部碎片严重动态分区是等进程来了再切一块正好大小的区又细分为首次适应找到第一个够大的空闲区就用、最佳适应找最小的足够空间、最坏适应找最大的空闲区。这三个算法是第四章前几节的必考内容但考试只考选择的话很多人容易把“最佳适应”为什么会产生小碎片搞混——因为它宁可找最小的够用空隙结果是剩下一个更小的碎片很难再被利用。动态分区还有一个绕不过去的问题外部碎片。进程换进换出内存里会出现一些散落的、彼此不相邻的小空闲区总和可能很大却没有一块能连续装下新进程。比如两个空闲区分别是30KB和40KB来了一个需要50KB的进程就算总空闲70KB也分配不出去。经典办法是“紧凑”compaction把所有进程挪到一起合并出大块空闲区但挪动进程的代价很高后来基本被分页方案取代。1.3 覆盖和交换的教训管理粒度决定一切在分页方案成熟之前人们也尝试过两种“硬凑”的办法。覆盖overlay程序员自己把程序拆成若干模块同一时间只让一部分模块驻留内存其他模块用到时再从磁盘调入。这个方案把内存管理的负担完全甩给了程序员你得自己分析模块间的依赖关系程序规模一大就是灾难。交换swapping操作系统把暂时不运行的进程整体换到磁盘等需要时再换入内存。交换的粒度是整个进程换入换出一次就是几MB甚至几十MB的I/O非常耗时。这两个方案失败的原因本质上都是管理粒度过粗。覆盖要由人来决定粒度交换以进程为粒度都缺乏灵活度。分页方案出现后把粒度细化为固定大小的小块页才真正解决了碎片和调度的两难。学到这里你会看到一个清晰的递进逻辑管理粒度越细内存利用越灵活操作系统要做的事情也越多。第四章后面所有内容都是在这个逻辑上展开的。2. 分页、分段、段页式三种方案到底在解决什么2.1 分页用离散空间消灭外部碎片分页的核心思想一句话就能说清把进程的逻辑地址空间切成等大小的块叫页面page把物理内存也切成等大小的块叫页框frame。页面大小通常是4KB也可以是2KB、8KB。进程页面可以离散地放在任意空闲页框里不再要求连续所以外部碎片直接被消灭了。实现这个离散映射的关键数据结构是页表页表记录“逻辑页号 - 物理页框号”的对应关系。地址格式是逻辑地址 页号 页内偏移物理地址 页框号 页内偏移。页内偏移在页面大小是2的n次幂时就是逻辑地址的低n位前面剩下的高位就是页号非常方便硬件拼接。分页不是没有碎片它只是把外部碎片变成了很小的内部碎片进程最后一个页面往往装不满平均浪费半页。但这在工程上完全可以接受4KB页面最多浪费2KB比连续分配随时可能出现的几十KB外部碎片温和多了。2.2 分段让内存也跟着程序逻辑走分页是从内存利用角度出发的是机器视角分段则站在程序员视角按程序的逻辑结构切分。一个程序天然就是由代码段、数据段、堆栈段等组成的段内是连续的逻辑空间各段大小不一样。分段地址 段号 段内偏移段表里记录每个段的基址和段长。访问时要先查段表再检查偏移是否超过段长超出就触发越界中断这是分页没有的“逻辑保护”。分段还有个分页难以替代的好处共享方便。两个进程想共享同一个代码库只需要让它们的段表项指向同一个段基址而不像分页那样要逐页共享。所以分页和分段的区别经常被拿来当简答题分页是系统自动完成、对程序员透明、解决物理碎片分段是用户可见、按逻辑单位划分、方便共享和保护。2.3 段页式先分段后分页逻辑和物理都要既然分段有逻辑优势分页有物理优势那就合体先按逻辑分段每段内部再分页。地址结构变成“段号 段内页号 页内偏移”三层段表项里存的不是段基址而是该段的页表始址和页表长度。访问一次数据需要查段表、查页表、读内存共三次访存性能代价比单纯分页高但换来的是逻辑保护和物理离散双重收益。段页式是第四章的难点最容易被问倒的点是别把段表和页表的层次搞反。段表放在全局根据段号找到对应页表页表是每段一个根据段内页号找到页框号最后一层偏移直接和页框号拼接得到物理地址。可以把它想象成查书目录先按章查段号再按节查页号最后定位到具体行偏移。2.4 三张分配方案的对比角度考前如果把这三张方案放在一张表里对比会清晰很多方案分配单位地址结构访存次数主要碎片共享/保护连续分配整个进程基址长度1次外部碎片为主困难分页定长页面页号偏移2次内部碎片共享不便分段变长逻辑段段号偏移2次外部碎片天然支持段页式分段拆分页段号页号偏移3次内部碎片支持注意分段因为段长可变依然可能出现外部碎片分页因为等宽外部碎片清零但会有少量内部碎片。考试答“分页消除了外部碎片”时记得补一句“没有消除内部碎片”这就是得分点。3. 地址变换是考点也是理解门从公式到TLB3.1 一个典型计算逻辑地址怎么变成物理地址地址变换是这一章的“动手题”。基础公式只有两条页号 p 逻辑地址 / 页面大小页内偏移 d 逻辑地址 % 页面大小物理地址 页框号 f × 页面大小 页内偏移 d。页面大小是2的幂时其实不用乘除直接移位和拼接更直观。假定页面大小4KB2^12逻辑地址是十六进制0x1123低12位是页内偏移也就是0x123高位的0x1是页号。如果页表里页号1对应的页框号是7物理地址就是偏移0x123前面接上页框号7的二进制11位表示结果为0x7123。这里有个坑很多人踩题目如果给物理内存大小是4GB页面4KB那页框号要有20位才够表示2^20个页框。计算物理地址时要把页框号左移12位再和偏移相或不能直接写成“页框号乘以4096”就完事这个乘法和左移本质上是一样的但能帮你保持位数直观。3.2 页表多大、多级页表为什么省32位逻辑地址4KB页面则页号占20位。如果页表项占4字节一张页表的大小就是 2^20 × 4B 4MB。每个进程一张页表100个进程就是400MB光页表就吃掉了大量物理内存这显然不划算。多级页表的思路很简单只给实际用到的虚拟页面建立二级页表。32位地址分两级一级页表有 2^10 项每项指向一个二级页表二级页表同样 2^10 项。一个进程如果只用了很少的地址空间就不需要为未使用的区域分配二级页表页表总占用从4MB降到了几十KB级别。代价是地址变换时多查一次页表访存次数从2次变成3次。所以多级页表不是免费的午餐它是用时间换空间。3.3 快表TLB和有效访问时间页表放在内存里意味着CPU每次取数据都要先查内存中的页表访存次数翻倍。为了解决这个性能问题硬件在CPU里加了一个很小的快表TLB保存最近访问的页表项。CPU生成逻辑地址后先查TLB命中就直接得到页框号只需再访问一次内存取数据未命中才去查内存中的页表查完顺便把页表项装进TLB。有效访问时间EAT是常考计算题。设访存时间为 t查快表时间为 λ命中率为 α则EAT α × (λ t) (1 - α) × (λ 2t)这里第二项未命中时是 λ t(查页表) t(取数据)共两次访存。举个例子t 100nsλ 20ns命中率98%则 EAT 0.98×120 0.02×220 117.6 4.4 122ns。如果命中率掉到90%EAT 108 22 130ns性能下降不大但如果没有TLBEAT 200ns立刻翻倍。这就是为什么现代CPU会把TLB命中率当作重要性能指标。3.4 页表项里藏着哪些标志位页表项不只是“页号-页框号”的映射表每个页表项里还有几个关键标志位存在位有效位页是否在物理内存中。为0时访问该页会触发缺页中断。修改位页在内存期间是否被写改。换出时如果修改位为1必须把页写回磁盘为0则可以直接丢弃省一次磁盘I/O。访问位页最近是否被访问过。页面置换算法里的CLOCK算法主要靠它打分。这几位在做模拟实验时非常重要许多人写置换算法时只盯着页号忘了维护修改位和访问位实验效果就差很多。4. 虚拟存储器放不下就换关键在置换算法4.1 局部性原理是虚拟内存的物理基础虚拟内存能成立靠的不是魔法而是局部性原理。程序运行时的指令和数据访问不是均匀分布的循环体内的代码会被反复执行这是时间局部性访问过某个地址后它附近的地址很快也会被访问这是空间局部性。因为局部性操作系统只需要把当前要用的页面放在内存里其他页面留在磁盘。对进程来说它拥有一个比物理内存大得多的地址空间这就是“虚拟”的来源。第四章后面讲请求调页、预调页基础都是局部性原理。很多人不理解虚拟内存为什么不是“一次性把程序全部调入再运行”就是没想明白局部性。4.2 缺页中断的完整流程当CPU访问的页面不在内存时会发生缺页中断。流程分几步CPU查页表如果TLB没命中发现存在位为0。缺页中断触发操作系统被叫起来。在内存里找空闲页框如果没有空闲页框就要选一个受害者页面换出。换出时看修改位如果页被修改过就写回磁盘否则直接丢弃。从磁盘把需要的页面读入空闲页框。更新页表把存在位置1填上页框号。重新执行导致缺页的那条指令。注意最后一步缺页是在一条指令执行到一半时发生的处理完缺页后CPU必须重新执行那条指令而不是从下一条继续。这个细节经常被忽略但在简答题里是送分别丢掉的分。4.3 页面置换算法谁走谁留各有门道到了内存满了还要继续调入新页时就必须置换。四个算法是本章核心中的核心OPT最佳置换淘汰以后最长时间不会被访问的页。它是理想情况实际没法实现因为操作系统没法预测未来。但它是衡量其他算法优劣的标尺。FIFO先进先出淘汰最早进入内存的页。实现简单用一个队列就行。但它不看访问频率容易把正在被高频使用的页换走甚至出现Belady异常分配到的物理页框增多缺页次数反而增加。LRU最近最久未使用淘汰最长时间没被访问的页。它比较符合局部性直觉但实现需要每次访问都记录时间戳硬件开销大。Clock时钟LRU的近似实现。每个页有一个使用位缺页时指针沿着环形队列走使用位为1就清零并继续走碰到0就换出。开销小被工业界用得最多。Belady异常是FIFO的标志性现象。经典引用串1 2 3 4 1 2 5 1 2 3 4 5物理块数从3增加到4FIFO的缺页次数反而从9次变成10次。LRU和OPT则不会出现这种反常——块数增加只可能缺页减少或不变。这个点经常被拿来出选择题务必记住FIFO是唯一闹这个脾气的算法。4.4 颠簸thrashing和工作集如果分配给一个进程的物理页框数太少或者置换策略不对进程会频繁缺页CPU大量时间花在等待磁盘I/O上系统吞吐量暴跌这种现象叫颠簸。理解颠簸要引入工作集概念工作集是一个进程在某段时间内实际访问到的页面集合。如果进程的驻留集实际占用的页框数小于工作集就会一直缺页反过来驻留集足够大缺页率就会降低。解决颠簸的常见手段是调整驻留集大小、采用局部置换进程只能替换自己的页面。这个知识点把虚拟内存和进程调度连起来了很多学生学到这章期末才发现前面没学扎实原因就是没把工作集当作“动态的访问集合”来理解。5. 用C语言写一个页面置换模拟器实测FIFO和LRU5.1 为什么值得写这个模拟器纸上得来终觉浅这句话在操作系统身上尤其对。你能很轻松地背出“FIFO淘汰最早进入的页”但真让你模拟一个引用串很多人在第一步就卡住页表怎么表示空闲页框怎么找内存里的页面要不要顺序记录这些细节不亲手写一遍永远只是模糊的印象。写一个最小模拟器还有一个好处它能帮你做实验。你可以在同一段引用串上对比FIFO和LRU观察Belady异常什么时候出现然后把算法扩展成Clock再跑一遍。比起看十遍教材自己改代码跑数据印象深得多。5.2 数据结构与两个算法的实现思路我用C语言写了一个精简模拟器。数据结构很简单一个frames[]数组表示物理页框中现在装的页号初始化为-1表示空闲一个loaded[]数组记录每个页框里那个页是第几次调入的用来实现FIFO一个last_access[]数组记录每个页最近一次被访问的时间用来实现LRU。FIFO的思路是用“装入时间”代替队列每次缺页时扫描loaded找到值最小的页框就是最早装入的把它替换掉。LRU每次命中时刷新last_access缺页时找last_access最小的页框替换。这样两份逻辑对称对比起来特别直观。5.3 核心代码与运行结果直接看关键函数#include stdio.h #define MAX_FRAMES 32 #define MAX_REF 128 int my_fifo(int ref[], int n, int fc) { int frames[MAX_FRAMES]; int loaded[MAX_FRAMES]; int time 0, faults 0; for (int i 0; i fc; i) { frames[i] -1; loaded[i] -1; } for (int i 0; i n; i) { int hit 0; for (int j 0; j fc; j) { if (frames[j] ref[i]) { hit 1; break; } } if (hit) continue; faults; int free_slot -1; for (int j 0; j fc; j) { if (frames[j] -1) { free_slot j; break; } } if (free_slot 0) { frames[free_slot] ref[i]; loaded[free_slot] time; } else { int victim 0; for (int j 1; j fc; j) { if (loaded[j] loaded[victim]) victim j; } frames[victim] ref[i]; loaded[victim] time; } time; } return faults; } int my_lru(int ref[], int n, int fc) { int frames[MAX_FRAMES]; int last_access[MAX_FRAMES]; int time 0, faults 0; for (int i 0; i fc; i) { frames[i] -1; last_access[i] -1; } for (int i 0; i n; i) { int hit 0; for (int j 0; j fc; j) { if (frames[j] ref[i]) { hit 1; last_access[j] time; break; } } if (hit) { time; continue; } faults; int free_slot -1; for (int j 0; j fc; j) { if (frames[j] -1) { free_slot j; break; } } if (free_slot 0) { frames[free_slot] ref[i]; last_access[free_slot] time; } else { int victim 0; for (int j 1; j fc; j) { if (last_access[j] last_access[victim]) victim j; } frames[victim] ref[i]; last_access[victim] time; } time; } return faults; }跑一组简单引用串1 2 3 1 4 1 2 3物理块3个FIFO缺页7次LRU缺页6次。你还会在该代码上复现经典FIFO的Belady异常引用串1 2 3 4 1 2 5 1 2 3 4 5物理块3时缺页9次块4时反而缺页10次。这两个实验做完比背十遍书本有用。5.4 踩过的坑和扩展方向写模拟器时最容易在这几个地方翻车初始装载也是缺页很多新手从第1次缺页开始算但首次调入页面同样要走缺页中断流程必须计入。页面编号和数组下标引用串如果从1开始内存数组的索引又是从0开始初始化时容易有一串“段错误”。FIFO的队列不要自己去实现“搬移”除非你愿意写散列表否则用装入时间戳代替队列又简单又稳。LRU时间戳溢出模拟数据规模小不致命但如果你把引用串拉长到几万条int时间戳可能溢出换成long或者定期重排。扩展方向很多加入Clock算法给每个页加访问位和修改位比较两种Clock版本的缺页数或者把模拟器升级成“分配器”接收一个虚拟地址按照页表计算出物理地址并打印整个过程。这就是一个相当完整的操作系统课设雏形了。6. 把第四章织成一张网复习路线与答题要点6.1 四个问题自查比抄十遍笔记有效复习到后期我会用四个问题检验自己是否真的理解这一章而不是背概念外部碎片是怎么产生的分页为什么能消除它分段为什么又会引入外部碎片一次地址变换到底要访存几次单级页表几次多级页表几次段页式几次为什么TLB能减少这些访问缺页中断的完整流程从CPU访存到重新执行指令能面不改色讲三分钟吗什么是颠簸工作集和驻留集的关系是什么调整哪个参数能缓解颠簸这四个问题每个都能串起一组知识点。比如第一个问题的答案里其实就包含了连续分配、动态分区算法、紧凑、分页、分段全部内容。能讲清楚说明你已经把“分配方案链”打通了。6.2 三类高频考题的“坑位”提醒我见过太多人复习时栽在同样的坑里计算物理地址题目给页面大小和页表求某逻辑地址的物理地址。坑在页大小不是2的幂次或页号从0/1开始的约定先统一再算别直接乘。页表大小页表项不是只有页框号还有标志位。算页表占多少字节时要注意页表项是几个字节算多级页表时要保证每一级页表恰好能放进一个页面。置换算法缺页次数初始装载算缺页FIFO可能出现Belady异常OPT不能实现只能分析。遇到给引用串算缺页的题别紧张到把“命中”也记成缺页。还有个更容易忽略的角度为什么页面大小不能无限大页面太大内部碎片多页数少页面太小页表太大TLB能覆盖的范围也小。现代操作系统选4KB是一个折中理解这个权衡面试时比死背“4KB是经典选择”生动得多。6.3 结合Linux和实验平台加深理解如果电脑装了Linux强烈建议花10分钟做个小实验用free -m查看物理内存和交换分区用ulimit -v限制一个进程的虚拟地址空间再运行大程序你会亲眼看到缺页和换页对程序运行速度的影响。不要只看数字带上“局部性原理”去感受。在学校常用的实验平台比如头歌这类在线操作系统实验上也会配一些存储管理题目补全分配算法、模拟页面置换、实现地址变换。虽然题目很小但和教材习题完全是两种体验——教材告诉你“页表项有存在位”实验里你才能真正意识到如果存在位0还傻乎乎去取页框号程序就跑飞了。我自己复习这一章时还有一个笨办法每天抽10分钟在白纸上画一遍“逻辑地址 - TLB - 页表 - 物理内存”的流程。一开始卡壳画了几天之后缺页中断该在哪一步触发、修改位该在哪一步更新就都长在肌肉记忆里了。这个习惯帮我打通的不只是第四章后来的文件系统、进程调度复习也一直在用。如果你现在正被存储器管理绕晕不妨试试这套方法大概率能少走很多弯路。