虚拟内存管理

请求式分页管理方式

前面我们介绍了虚拟内存，并且介绍了请求式管理的由来，那么接下来就详细介绍一下请求式分页管理方式。请求分页存储管理与基本分页存储管理的主要区别是在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息调入内存（这里操作系统要提供请求调页功能把缺失页面从外存调入内存）后继续执行程序。如果内存空间不足，由操作系统负责将内存中暂时用不到的信息换出到外存。（操作系统要提供页面置换的功能，将暂时用不到的页面换出外存).这里会涉及到页面机制，缺页中断机构和地址变换机构，我们在下面一一进行介绍。

页表机构

与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是够已经掉入内存，如果还没有调入内存，那么也需要知道该页面在外存中存放的位置。并且当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面（页面置换算法），有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，需要将外存中的旧数据覆盖，因此操作系统需要记录各个页面是否被修改的信息。如下：

从上图我们可以看出请求分页存储管理的页表中存储了所有的页表，即使没有放入到内存中页记录在一个页表项。例如x现在就没有在内存中。

缺页中断机构

假设现在某进程要使访问的逻辑地址为（页号，页内偏移量）=（0，1024），那么经过查表发现此时0号页不在页表中，所以产生一个缺页中断，然后然后由操作系统对缺页中断进行处理。首先是将缺页的进程阻塞，然后放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。如果内存中还有空闲块，那么就为进程分配一个空闲块，将所缺页面装入该快，并修改页表中相应的页表项。

如上图就是将0号页表项内存块号修改为a并且状态为1，并且还要将x号块内的页面装入内存中去：

思考：如果内存块此时是满的怎么办？

那么就会调用页面置换算法将一些符合调出条件的页面写回外存，所以只有内存满的时候才会触发调换算法（其实很容易理解，写回外存肯定是有时间开销的，所以只有满的时候迫不得已了才会增加时间开销为新来的页腾地儿），类似的实际上TLB等快表也有这个调出暂时长时间不命中的页表项的算法。并且如果内存满了，调出某个页面时，如果这个页面在内存期间被修改过，那么需要将其写回外存覆盖旧数据，否则未修改过的页面就不用了写回外存了，直接淘汰掉就好。毕竟外存块x处还存有旧数据的页，所以我们也可以看出调入是从外存快复制一份页面进入内存块，调出的意思是从内存淘汰的意思，当修改过的时候，这个被淘汰的页面还肩负着通知外存块更新数据的使命所以还需要写回外存（当然肯定是有额外的时间开销的），当没有被修改过（不意味着没被使用，可能在内存期间一直在在被读也发挥作用了）那么就直接扔出内存即可。

思考：缺页中断属于内中断的哪一类？

我们知道缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断。一条指令在执行期间，可能会产生多次缺页中断（如copy A to B,即将逻辑地址A的数据复制到逻辑地址B，而A,B属于不同的页面，就可能产生两次中断，即A的页不在内存中，B的页也不再内存中，可能会产生两次中断）。

我们可以看出缺页中断属于内中断中的故障，但是是可以被程序处理恢复的。

地址变换机构

因为不能保证逻辑地址访问的页在内存中，所以我们首先是需要确定页是否在页表中，如果不在还需要调入页面并修改表项，当然如果内存满了，那么还需要页面置换。所以新增的步骤有：

当然后面的步骤就是根据页号找到内存块号了，然后拼接物理地址最后再访问目标内存单元。

这里我们尤其要注意TLB的机制，他只存放现在在内存中的刚刚被访问过得页表项，所以TLB里的页一定是存在的。

这里面的一些小细节直接用图片给出，这里我们一定要注意绿框中的提示要点。我们可以看出当产生缺页中断时换出旧页面并调入新的页面到内存块后发生了几个重要的事件：

快表直接加上新的表项
不是直接通过慢表拼接出了物理地址然后访存，而是又重新来了一遍这次快表命中了，然后通过快表拼接出了物理地址进行访存。

思考：为什么没有查慢表和查快表一起进行？

可以，但是没必要，因为此时慢表大概率会慢于快表（如果不是还要TLB作甚）并且查慢表还会出现缺页中断，并行查询也快不了多少。

思考：为什么当有缺页中断时会通过快表命中？

这就是进程中断的原理了，当在某一个指令处中断时如果进程阻塞了PCB会记录上次停止的位置，然后当进程再次执行时PCB会恢复到上一次停止的指令处然后重新执行中断的指令（大部分情况下），所以此时还会再执行一遍这个指令的逻辑地址但是此时就会通过快表命中了。

总结

页面置换算法

这部分超级重要，我会做适当的扩充，毕竟王道讲的实在是太少了。一定要透彻了解并且会计算。首先我们明确一个目的，由于页面的换入换出需要磁盘I/O，会有较大的开销，因此优秀的页面置换算法应该追求更少的缺页率。

最佳置换算法（OPT）

也叫作最优置换算法（OPT,Optimal):每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样就可以保证最低的缺页率。这里我们知道肯定是最理想的情况，因为这个算法要求我们需要提前知道未来这个所要被调出的页面就是最长时间或者永久不可能再被使用的页面，但是未来不可预测，所以这个算法实际中不可能实现，但是我们需要学习算法思想（毕竟万一未来我们量子预测到未来这个算法那不就可以实现了吗😝）

例题：假设系统为某进程分配了三个内存块，并考虑有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

那么最终的过程如下：

首先不用想，第一次填入时肯定都是缺页的（这个很重要容易被忽视）所以内存块填入7,0,1就先缺页3次，然后接下来到2，我们需要调出一个页面，此时我们看一下未来的访页顺序发现7最长时间不会被访问了，所以调出7接入2又缺页1次，继续执行到3发现又该调出了，还是看未来的顺序，调出1,…一直这样看未来顺序调出页面最终缺页率还是可观的才45%。这里我们可以看出缺页率的计算公式：

缺页率=缺页中断次数/页面引用次数

最近未使用页面置换算法（NRU）

最近未使用页面置换算法（Not Recently Used)和OPT很相似，既然我不能知道未来的顺序，那么我就往回看，根据经验分析和局部性原理我们知道如果一个页面很久没有被是用来，那么大概率他就会很长时间或者不会再被使用了（根据历史经验推测未来），所以我们每次都选择调出最近未使用的页面。这里我们的做法如下：

当一个页面被访问(读)时设置R(read)位，页面被写入(修改)时设置M(modificate)位。

当启动一个进程时，它的所有页面的两个位都由操作系统初始化为0，R会被定期地（比如在每次时钟中断时）清零以区别最近没有被访问和被访问的页面。

那么当发生缺页中段时就会检查页面，其中页面可以分为4类：

第0类：没有被访问也没有被修改过的页面（R=M=0)
第1类：没有被访问但是已被修改过的页面（R=0,M=1）
第2类：已被访问过但是没有被修改过的页面（R=1,M=0）
第3类：已经被访问过并且也被修改过的页面（R=M=1）

每次都是从类编号小的非空类中随机挑选一个页面淘汰。

思考：问什么第2类比第3类优先被淘汰？

首先请读一下算法名字，他强调的就是最近未使用，所以重在根据是否最近被访问过来决定页面的重要性，所以2类先被淘汰，毕竟在一个时间嘀嗒中（大约20ms）淘汰一个没有被访问过的已被修改过的页面比淘汰一个被频繁使用的“干净”（没被修改过）的页面好，所以是否“干净”（即是够被修改过）只是一个次级判断条件。其实NRU这种算法优点就是易于理解和有效实现并且虽然性能不是最好的但是已经够用了。

先进先出页面置换算法（FIFO）

同样借鉴了NRU的思路，既然每次都淘汰最近未被使用的页面，那么大多数情况先来的一般会在内存中待较长的时间，根据时间局部性原理，一般他就是那个最近未被使用的页面。所以FIFO算法就是每次选择淘汰的页面是最早进入内存的页面。

实现方法：把调入内存的页面根据调入的先后顺序排成一个队列（FIFO队列），需要换出页面时就选择队头页面即可。所以队列的最大长度取决于操作系统为进程分配了多少个内存块。

例题：

缺页率=9/12=75%,说实话优点小高。那么你一定想到了如果多分几个内存块是不是缺页次数会变得更少，答案是未必，如下：

缺页率=10/12=83%缺页率反而更大了。只有FIFO会产生这种Belady异常现象，所以FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律是不适应的，因为先进入的页面也有可能经常被访问，所以算法性能差，不推荐使用。

第二次机会页面置换算法（SC）

第二次机会页面置换算法（Second Chance)是对FIFO算法进行的一种优化改进。修改的思路其实很简单，就是避免将最先进来的页面却被访问的页面优先调出，所以只需要设置一位R位，如果是0那么这个页面就是既老还没有被使用，可以直接置换掉。如果是1那么就说明这个页面虽然老但是被访问过，所以将R为置为0然后把这个页面放到队尾修改装入的时间就好像它刚被装入一样（即拥有了第二次机会），然后继续搜索队头直至R=0的页面换出。

第二次机会算法就是在寻找一个最近的时钟间隔内没有被访问过的页面。如果所有的页面都被访问过了，即队列中所有的页面R都是1了，那么这个算法就是纯FIFO算法了，所以为了避免这种情况此时操作系统会一个接一个地将每一个页面都移动到队尾并将R设置为0。最后又回到原来的表头页面并且此时R位都是0，因此这个页面会被淘汰，所以这个算法总是可以结束不会出现死循环的。

思考：NRU和SC都有R位有什么区别？

NRU和SC的R位都是被访问的意思，但是NRU的R位是最近被访问的概念，而SC的R为只是表示被访问过的意思，所以NRU需要一个时间嘀嗒来设置R在一个时间段后清零，而SC就不需要只是当队列全是1时所有页面都在绕一圈然后R都变为0。

时钟页面置换算法（CLOCK）

对第二次机会算法的改进，我们发现第二次机会算法总是需要在链表中移动页面，这很低效没必要。所以更好的做法是把所有的页面都保存在一个类似钟面的环形链表中，一个表指针指向最老的页面（即最先进入内存的页面）。当发生缺页中断时，首先检查指针指向的页面，如果R位是0，那么就淘汰该页面，并把新的页面插入到这个位置，然后把表指针移到下一个页面，如果R位是1就将R位置为0然后检验下一个位置，重复这个过程一直到找到一个R位为0的页面为止。当所有的R位都是1时，则指针转一圈将所有的页面的R位都清为0。

我们发现实际上CLOCK算法和SC算法思想一模一样，只不过是换了一个数据结构来减少操作的开销。并且我们发现简单的CLOCK算法选择淘汰一个页面最多经过两轮扫描。

思考：能否进一步优化CLOCK算法？

我们发现NRU不止讨论了是否最近被访问过的问题，还加了一个是否被修改过的判断指标，当都没有被访问时优先会淘汰没有被修改过的页面，这是因为毕竟修改过的页面被淘汰时还需要写回外存有更大的开销不如再等一等万一他一会被访问了不就不用写回外存了嘛。所以优先淘汰的是R=M=0的，那么CLOCK算法也可以借鉴这种思想。

改进型的时钟置换算法（CLOCK v2.0)

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件均相同时，应该优先淘汰没有被修改过得页面，避免I/O操作。这就是改进型的时钟置换算法的思想。所以也是有下面这四类：

第0类：没有被访问也没有被修改过的页面（R=M=0)
第1类：没有被访问但是已被修改过的页面（R=0,M=1）
第2类：已被访问过但是没有被修改过的页面（R=1,M=0）
第3类：已经被访问过并且也被修改过的页面（R=M=1）

页面的状态用（R,M）表示，所以（1,1）表示最近被访问过且被修改过。

算法规则：将所有可能被置换的页面排成一个钟面型的循环队列。

第一轮：从当前位置开始扫描到第一个（0,0)的帧用于替换，本轮扫描结束。

第二轮：前提是第一轮扫描失败（即没有(0,0)），那么重新扫描，查找第一个（0,1)的帧用于替换。本轮会将所有扫描过得帧访问位设置为0（即第二轮扫描后（1,0)->(0,0),(1,1)->(0,1)。

第三轮：前提是第二轮扫描失败（即没有(0,0)和（0,1)），那么重新扫描，查找第一个（0,0）（此时的(0,0)是原先的(1,0)）的帧用于替换。本轮不修改任何标志位。

第四轮：前提是第三轮扫描失败（即没有(0,0),(0,1)和(1,0)），那么重新扫描，查找第一个（0,1)（此时的(0,1)是原先的(1,1)）的帧用于替换。并且此轮一定会扫描成功。

由于第二轮已经将所有的访问位设置为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK算法选择一个淘汰页面最多会进行四轮扫描。

思考：改进型CLOCK和CLOCK最大的区别是什么？

我们仔细对比一下两者的算法思想，我们发现虽然都是使用类似钟的循环队列数据结构，但是算法思想却截然不同，对于简单的CLOCK使用的是SC的思想，而改进型的时钟页面置换算法使用的是NRU+CS的算法思想但是更贴向NRU。

最近最少使用页面置换算法（LRU）

最近最少使用页面置换算法（LRU，Least Recently Used）：每次淘汰的页面是最近最久未使用的页面。

实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t，当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。很明显这个非常的科学。

我们以一道例题讲解，假设某系统为某进程分配了4个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,1,8,3,8,2,1,3,1,7,1,3,7

缺页率=6/20=33%很小。在手动做题时，若需要淘汰页面，可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。我们发现这个方法太好啦，就用这个吧，但是实际上这个算法不常见，因为需要专门的硬件支持且实现困难，开销极大。

最不常用页面置换算法（NFU）

最不常用页面置换算法（NFU,Not Frequently Used）:用一个软件模拟LRU，该算法将每个页面与一个软件计数器相关联，计数器的初始值为0，每次时钟中断时，由操作系统扫描内存中的所有页面，将每个页面的R位（他是0或1）加到计数器上。这个计数器大体上跟踪了各个页面被访问的频繁程度。当发生缺页中断时，则置换计数器上数值最小的页面。

我们发现NFU不忘记任何事情，比如一个页面之前被频繁访问，导致这个计数器很大，但是后来不访问他了，但是由于计数器的值太大，他也一直不会被置换出去，这个缺点太严重，所以也不推荐。

老化算法

老化算法是对NFU算法的修改，其修改包括两个部分，首先，在R位被加进之前将计数器（二进制数）右移一位（相当于除以2）然后将新来的R位的数加在计数器的最左端的位（即次数最大最优决定权）。这样老化算法的计数器中只有有限位数，如果时钟滴答是20ms,8位一般足够了，加入一个页面160ms都没有被访问过，那么他很有可能就不重要了。

工作集页面置换算法(WS)

在讲解算法的实现之前，我们先了解一下几个概念：

思考：什么是工作集？

工作集：一个进程当前正在使用的页面的集合称为工作集

思考：什么是颠簸现象？

颠簸现象：程序每执行几条指令就产生一次缺页中断

思考：什么是请求调页？颠簸现象什么时候频繁出现？

请求调页：在单纯的分页系统中，刚启动进程时，在内存中是没有页面的，所以当cpu尝试读取第一条指令时就会产生一次缺页中断，使操作系统装入含有第一条指令的页面，其他由访问全局数据和堆栈引起的缺页中断通常会紧接着发生。一段时间后，该进程需要的大部分页面都已经在内存中了，进程开始在较少缺页中断的情况下运行

思考：怎么解决程序初期运行的颠簸现象？

有不少分页系统会设法跟踪进程的工作集，以确保进程运行以前，他的工作集就已经在内存中了，这样运行初期就不会频繁发生颠簸了。这种方法就叫做工作集模型，大大减少了缺页中断率。在进程前装入其工作集页面也称为预先调页。所以工作集随着时间变化的。

实际上大多数的程序会任意访问一小部分页面，工作集缓慢变化。当程序重新开始时，就有可能根据它上次结束时的工作集对要用到的页面作一个合理的推测，预先调页就是在程序IXUS运行之前预先装入推测的工作集的页面。

思考：纯分页式管理的工作集和请求式分页管理的工作集的区别？

那么按照以前的方法定义工作集为前1000万次内存访问所使用过的页面的集合，那么现在在请求式分页管理中就应该定义为过去10ms中的内存访问所用到的页面的集合。这样的模型更合适和容易实现。并且要注意每个进程都只会计算自己执行的时间，所以当一个进程在T时刻开始然后在T+100ms的时间段内使用了40ms的CPU，那么对于工作集来说就是40ms。一个程序从他开始执行到当前所实际使用处理机的时间总数就是当前实际运行时间。我们通过这个近似的方法定义进程的工作集就是在过去的t秒实际运行时间中他所访问过的页面的集合。

那么现在我们再来探讨下基于工作集的页面置换算法：就是找出一个不在进程工作集中的页面淘汰他。

每个表项至少要包含两条信息：

上次使用该页面的近似时间
最近是否访问过的R位

过程如下：

扫描所有的页面检查R位。

如果R==1：那么设置上次使用时间为当前实际时间，以表示缺页中断时该页面正在被使用
如果R==0&&生存时间>t:那么表示最近没有被访问过且已经不再工作集了，那么就移除这个页面，用新的页面置换它。扫描会继续进行以更新剩余的表项。所以这次扫描后所有不在工作集的页面都会被淘汰掉。
如果R==0&&生存时间<=t:那么表示这个页面没有被访问过但是却还在工作集中，那么就记录下最长生存时间（就是当前时间-最早被使用时间即已经在呆工作集中的时间）。如果最后没有找到任何一个可以淘汰的即所有页面都是1情况除了现在被扫描的这个页面那么就淘汰这个页面，如果有多个3这种情况的即（1,3都有的情况）那么就淘汰生存时间最长的。如果最终所有页面都是1的情况（包括现在被扫描的这个也是1的情况）那么虽然都满足无需淘汰的条件，但是总是得出去一个，那么就尽可能随机淘汰一个“干净”（没有被修改过的）页面这样就无需进行I/O操作了节省开销。

总结

以上涵盖了大部分置换算法，这里列表总结

页面置换算法	算法规则	优点	缺点
最佳置换算法（OPT）	优先淘汰最长时间内不会被访问到的页面	缺页率小，性能最好	预测未来，无法实现
最近未使用置换算法（NRU）	优先淘汰最近未被访问且干净的页面（需要R,M）	性能优秀，实现简便	————
先进先出置换算法（FIFO）	优先淘汰最先进入内存的页面	实现简单	性能差，与规律相悖，可能出现Belady异常
第二次机会置换算法（SC)	FIFO改良版，对于最近被访问过得放到队尾获得第二次机会	合理，性能适中	链表操作复杂
时钟置换算法（CLOCK）	SC的时钟循环链表形式，规则同上	合理，性能适中	未考虑干净页面的I/O开销
改进型的时钟置换算法（CLOCK v2.0)	和NRU思路规则相似使用的是时钟循环链表形式	合理，性能适中，考虑了I/O开销	有时候扫描次数有点多
最近最少使用页面置换算法（LRU）	每次都淘汰上一次被访问时间最早的页	性能好，科学合理	实现复杂，需要特殊地硬件支持，开销大
最不常用页面置换算法（NFU）	计数器记录R的和来表示被访问频率，每次淘汰访问频率小的页面	实现简单	之前访问频率大但是最近不怎么访问的页面迟迟不能被置换
老化算法	NFU改良版	实现适中，性能适中	————
工作集算法（WS）	每次都淘汰不在工作集的或者在工作集时间最长的干净的页面	实现适中，性能适中	————

页面分配策略

页面分配、置换策略

驻留集

指请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。如果驻留集太大，就失去了虚拟存储技术的应用意义，导致多道程序并发度下降，资源利用率降低。如果驻留集太小，会导致缺页颠簸，系统需要花费大量时间处理缺页。所以驻留集的大小要合适。

我们考虑一个极端的情况，如果一个进程共有100个页，那么如果驻留集大小为100，那么进程可以全部放入内存运行期间也就不会再发生缺页了，如果驻留集为1，则进程运行期间必定会频繁的缺页。

页面分配策略

固定分配：操作系统为每个进程分配一组固定数目的物理块，在运行期间各个进程的驻留集大小不变。

可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即驻留集大小动态变化。

页面置换策略

局部置换：发生缺页时只能选进程自己的物理块进行置换。

全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

思考：分配策略和置换策略的关系？

固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略缺点是很难在刚开始就确定应该为每个进程分配多少个物理块才算合理。（采用这种策略的系统可以根据进程大小，优先级，或是根据程序猿给出的参数来确定为一个进程分配的内存块数）

可变分配全局置换：刚开始为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某个进程发生缺页时，从空闲物理块中取出一块分配给该进程，如果已经没有空闲物理块了，则可以选择一个未锁定的页面换出外存（注意，并不是所有的页面都可以换出外存，比如系统会锁定一些页面，这些页面中的内容不能置出外存比如重要的内核数据等），再将物理块分配给缺页的进程。如果采取这种策略，那么只要进程发生缺页，都将先获得空闲的物理块，只有空闲物理块也没有的时候系统会调出一些其他进程未锁定的页面（这个页可能是任何一个进程的页），然后将腾出的物理块分配给这个缺页的进程。因此这个被选中的进程拥有的物理块会减少，缺页率会增加。

可变分配局部置换：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

思考：可变分配全局置换和可变分配局部置换的区别？

可变分配全局置换是只要缺页系统就会给他分配新的物理块。

可变分配局部置换是根据发生缺页的频率动态增加或减少进程的物理块直至频率趋于稳定。

调入页面的时机

预调页策略

根据局部性原理（主要是空间局部性原理），一次调入若干个相邻的页面可能比一次调入一个页面更加高效。但是如果预先调入的页面大多数没有被访问，那么就会低效。因此可以预测不久之后可能访问到的页面，将他们预先调入内存，但是目前预测成功概率为50%。所以这种策略主要用于进程的首次调入，由程序猿指出应该调入那些部分。