第2章 · 播客 第4集
操作系统 · 存储管理
🎙️ 本集播客：第4集：从内存与虚存的容量口径讲起，页式、段式、段页式三种虚地址结构逐一对照（第6题），页式与段式的地址变换一步步走完；四种页面调度算法与抖动，并用一个访问串把 FIFO 的 Belady 异常从 9 次缺页算到 10 次缺页（第5题）。 语音由微软 Edge 神经网络语音预生成（女声·晓伊，男声·云希）。点击下方任意对话可直接从该句开始播，当前句朗读时下一句已预先加载，无缝衔接。
明
阿明
上集把 P、V 操作和死锁的四个必要条件都啃下来了，也搞清了银行家算法属于死锁避免。这集该进内存了吧？
雅
小雅
对，进 2.2.2 存储管理。先给你定位：存储器是计算机系统中最重要的资源之一，因为任何程序和数据以及各种控制用的数据结构都必须占有一定的存储空间，因此存储管理直接影响系统性能。存储器由内存和外存组成。内存是由系统实际提供的存储单元、常指字节，组成的一个连续地址空间，处理器可直接存取；外存也叫辅存，是指软盘、硬盘、光盘和磁带等一些外部存储部件，常用来存放暂不执行的程序和数据。
明
阿明
外存处理器能直接读吗？
雅
小雅
不能，这句原话要背：处理器不能直接访问外存，需通过启动 I/O 设备才能进行内存、外存交换，其访问速度慢，但价格便宜，常用作内存的后援设备。紧接着还有一组容量口径的对照，特别爱考：内存大小由系统硬件决定，存储容量受到实际存储单元的限制；而虚拟存储器简称虚存，不考虑实际内存的大小和数据存取的实际地址，只考虑相互有关的数据之间的相对位置，它的容量由计算机地址的位数决定。
明
阿明
虚存容量由地址位数决定，不是由内存条大小决定。这两个一对比就清楚了。
雅
小雅
就是要考这个对比。再补一条内存布局：系统中内存的使用一般分成两部分，一部分为系统空间，存放操作系统本身及相关的系统程序；另一部分为用户空间，存放用户的程序和数据。
明
阿明
那存储管理具体管哪几件事？
雅
小雅
四件，一件都别漏：存储管理主要是指对内存储器的管理，负责对内存的分配和回收、内存的保护和内存的扩充；存储管理的目的是尽量提高内存的使用效率。注意主语是「内存储器」，外存不在这儿管——外存空闲块怎么组织是文件管理那一节的事，别串台。
明
阿明
教材说这套机制变迁过好几轮？
雅
小雅
这句话本身就是考点：存储管理的机制经历了多次变迁，由以前的单一连续区管理到分区存储管理，再发展为段页式管理；目前前两种技术已逐步被淘汰。所以「已逐步被淘汰」的是单一连续区管理和分区存储管理这两种，别把段式或者页式也算进去。教材后面只详细解读段页式这条线，我们就按页式、段式、段页式的顺序走。
明
阿明
先来页式。分页到底按什么分？
雅
小雅
分页的基本思想是把程序的逻辑空间和内存的物理空间按照同样的大小划分成若干页面，并以页面为单位进行分配。关键词是「同样的大小」，逻辑页和物理页一样大，所以页内位移根本不用换算。在页式存储管理中，系统中虚地址是一个有序对，前一项是页号、后一项是位移；系统为每一个进程建立一个页表，其内容包括进程的逻辑页号与物理页号的对应关系、状态等。
明
阿明
一个进程一张页表。那地址变换的过程，能一步一步念一遍吗？
雅
小雅
能，页式系统的动态地址转换分五步。第一步，当进程运行时，其页表的首地址已在系统的动态地址转换机构中的基本地址寄存器中。第二步，执行的指令访问虚存地址 p、d 时，首先根据页号 p 查页表。第三步，由状态可知，这个页是否已经调入内存。第四步，若已调入内存，则得到该页的内存位置，教材记作 p 撇，然后与页内相对位移 d 组合，得到物理地址 r。第五步，如果该页尚未调入内存，则产生缺页中断，以装入所需的页。
明
阿明
第四步那个「组合」，是相加还是拼起来？
雅
小雅
问到点子上了，这是页式和段式最容易被拿来出题的一处差别。页式这里教材用的词是「组合」，因为页的大小固定，位移的位数也就固定，物理块号往高位拼、位移往低位拼就行。等下讲段式你会看到，教材换了个词叫「相加」：段内偏移量要和段的内存起始地址做加法。一个是拼接、一个是加法，选项里改一个字你就得认出来。
明
阿明
记住了。那页式虚拟存储管理又多了什么？
雅
小雅
页式虚拟存储管理是在页式存储管理的基础上实现虚拟存储器的。首先把作业信息作为副本存放在磁盘上，作业执行时，把作业信息的部分页面装入内存储器；若所访问的页面已在内存中，则按页式存储管理方式进行地址转换，得到欲访问的内存绝对地址；若欲访问的页面不在内存中，则产生一个「缺页中断」，由操作系统把当前所需的页面装入内存储器中。
明
阿明
那页表怎么知道哪些页在内存里？
雅
小雅
靠标志位，数值别记反：在装入作业时，就应在该作业的页表中指出哪些页已在内存储器中、哪些页还没有装入内存，可用一个标志位指示，假设标志位为 1 表示该页在内存，标志位为 0 表示该页尚未装入内存。另外，为了能方便地从磁盘上找到作业信息的副本，页表中还可指出每一页副本在磁盘上的位置。
明
阿明
内存满了要腾地方，被换出去的页是不是每次都得写回磁盘？
雅
小雅
不是，这句最爱出判断题：当要装入一个当前需要的页面时，如果内存储器中无空闲块，则可选择一个已在内存储器中的页面，把它暂时调出内存；若在执行中该页面被修改过，则把该页信息重新写回到磁盘上，否则不必重新写回磁盘。没改过就不用写——磁盘上那份副本还是对的。另外，页面被调出或装入之后都要对页表中的相应表目做修改。
明
阿明
「选一页调出」这个动作，教材有专门叫法吗？
雅
小雅
叫页面调度，定义是：当内存中无空闲块时，为了装入一个页面而必须按某种算法从已在内存的页中选择一页，将它暂时调出内存，让出内存空间以存放所需装入的页面，这个工作称为「页面调度」。
明
阿明
要是算法选得不好呢？
雅
小雅
就会抖动。原文写得很形象：如果采用了一个不合适的算法，就会出现这样的现象——刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久又被装入，如此反复，使调度非常频繁，这种现象称为「抖动」。一个好的调度算法应减少或避免抖动现象。
明
阿明
常用的调度算法有哪几种？
雅
小雅
四种，按原文编号来，一个都别少。第一，最优 OPT 算法，选择不再使用或最远的将来才被使用的页，这是理想的算法，但是难以实现，常用于淘汰算法的比较。第二，随机 RAND 算法，随机地选择被淘汰的页，开销小，但是可能选中立即就要访问的页。
雅
小雅
第三，先进先出 FIFO 算法，选择在内存驻留时间最长的页，似乎合理，但可能淘汰掉频繁使用的页；实现上把装入内存储器的那些页的页号按进入的先后顺序排成队列，每次总是调出队首的页，当装入一个新页后，把新页的页号排到队尾，所以它简单、易实现。第四，最近最少使用 LRU 算法，选择离当前时间最近的一段时间内使用得最少的页。
明
阿明
LRU 凭什么认为这样选是对的？
雅
小雅
原文给了出发点：如果某个页被访问了，则它可能马上就要被访问；反之，如果某个页长时间未被访问，则它在最近一段时间也不会被访问。把四个的判据串一遍就不会混——OPT 看未来，RAND 不看，FIFO 看进入时间，LRU 看最近使用情况。只有 OPT 要预知未来，所以它难以实现、只能当尺子。
明
阿明
那有道题问「可能出现页面数增多、缺页次数反而增加的异常现象」的算法，选项给了 LRU、OPT、FIFO、RAND，答案是哪个？
雅
小雅
FIFO，而且原文就写在 FIFO 那一条里，原话是：使用 FIFO 算法时，在未给予进程分配足够的页面数时，有时会出现给予进程的页面数增多、缺页次数反而增加的异常现象。这个现象有个名字叫 Belady 异常。注意两个限定语——「未给予足够页面数时」和「有时」，它不是必然发生，是可能发生。
明
阿明
多给内存反而更慢，这也太反直觉了。能举个具体的串算算吗？
雅
小雅
教材没配例题，但这个反例你得会自己搭，考场上心里有底。访问串取 1、2、3、4、1、2、5、1、2、3、4、5，一共十二次访问，先给三个页面。前三次访问 1、2、3 都缺页，内存装满，队列顺序就是 1、2、3。第四次访问 4，缺页，淘汰队首 1，内存变成 2、3、4。第五次访问 1，缺页，淘汰 2，内存 3、4、1。第六次访问 2，缺页，淘汰 3，内存 4、1、2。第七次访问 5，缺页，淘汰 4，内存 1、2、5。
雅
小雅
接着第八次访问 1，命中；第九次访问 2，命中。第十次访问 3，缺页，淘汰队首 1，内存 2、5、3。第十一次访问 4，缺页，淘汰 2，内存 5、3、4。第十二次访问 5，命中。数一下缺页：前七次全缺，加上第十、第十一次，一共 9 次缺页。
明
阿明
那给四个页面呢？按常理应该少于 9 次。
雅
小雅
同一个串，四个页面。前四次访问 1、2、3、4 全缺页，内存装满，队列 1、2、3、4。第五次访问 1，命中；第六次访问 2，命中。第七次访问 5，缺页，淘汰队首 1，内存 2、3、4、5。第八次访问 1，缺页，淘汰 2。第九次访问 2，缺页，淘汰 3。第十次访问 3，缺页，淘汰 4。第十一次访问 4，缺页，淘汰 5。第十二次访问 5，缺页，淘汰 1。缺页 4 加 6，一共 10 次。
明
阿明
9 次变 10 次，页面多了一个，缺页真多了一次。
雅
小雅
这就是 Belady 异常。为什么只有 FIFO 会？看判据就明白：FIFO 淘汰谁只看「进入时间」，跟这页最近有没有被用过完全无关，所以你加一个页框，整个队列的出队节奏全变了，原本刚好留在内存里的页可能反而被排到队首挤掉。而 LRU 和 OPT 的判据都盯着访问情况——页框多的时候留下来的页，一定包含页框少时留下来的那些，所以缺页只会不增不减，绝不会反增。
明
阿明
那 RAND 呢？它也不看访问情况。
雅
小雅
RAND 是随机的，结果不确定，教材根本没把这个异常挂在它名下——考场上认原文的挂靠关系：这句话原文只写在 FIFO 条目里，所以答 FIFO，其余三个全是干扰项。反过来问「哪种算法不会出现该异常」，就排除 FIFO 选 LRU 或 OPT。