【操作系统复习之路】虚拟存储器（第五章）

本文主要是介绍【操作系统复习之路】虚拟存储器（第五章），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章专栏：操作系统复习之路

一、虚拟存储器概述

1.1 局部性原理

1.2 虚拟存储器的定义

1.2 虚拟存储器的特征

二、请求分页存储管理方式

2.1 请求分页中的硬件支持

2.1.1 页表机制

2.1.2 缺页中断机构

2.1.3 地址变换机构

2.2 请求分页中的内存分配

2.2.1 固定分配+局部置换

2.2.2 可变分配+全局置换

2.2.3 可变分配+局部置换

2.3 页面调入策略

2.3.1 何时调入页面

2.3.2 从何处调入页面

2.3.3 页面调入过程

三、页面置换算法

3.1 最佳置换算法（OPT）

3.2 先进先出置换算法（FIFO）

3.3 最近最久未使用置换算法(LRU）

3.4 Clock置换算法

四、“ 抖动 ”与工作集

五、结尾

一、虚拟存储器概述

前面介绍的传统存储器管理方式的特征：

一次性：作业在运行前一次性地全部装入内存
驻留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束

很显然，一次性及驻留性在程序运行时是没有必要的，这会浪费宝贵的内存资源和降低多道程序并发度。

上述问题可以用虚拟存储技术解决。

1.1 局部性原理

程序在运行时存在局部性现象，主要表现在下述两个方面：

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)

空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的)

1.2 虚拟存储器的定义

基于局部性原理，应用程序在运行前，没有必要全部装入内存，仅将当前要运行的部分页面或段先装入内存即可运行，其余部分暂留在外存上。程序运行时，如果要访问的页(段)已调入内存，便可继续执行；如果尚未调入内存(称为缺页或缺段)，此时程序应利用OS所提供的请求调页(段)功能，将它们调入内存，使程序继续执行。如果内存已满，无法再装入新的页(段)，还必须利用页(段)的置换功能，将内存中暂时不用的页(段)调至外存，腾出足够的内存空间后，再将要访问的页(段)调入内存，使程序继续执行。

（注意：解答虚拟存储器的定义时，要写上面这段话，下面这段话只是其特点）

基于上述定义，可以看出虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却接近于外存。

1.2 虚拟存储器的特征

多次性：一个作业被分成多次调入内存运行

对换性：允许在作业的运行过程中进行换进、换出。

虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

虚拟性以多次性和对换性为基础；

多次性和对换性又必须建立在离散分配的基础上。

在虚拟存储器中，允许将一个作业分多次调入内存。如果采用连续分配方式，不仅造成内存资源的浪费，而且无法从逻辑上扩大内存容量。因此，虚拟存储器的实现都是建立在离散分配的存储管理方式的基础上。

二、请求分页存储管理方式

2.1 请求分页中的硬件支持

2.1.1 页表机制

在请求分页系统中所需要的主要数据结构是页表。基本作用仍是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。由于只将程序的一部分装入内存，还有一部分在外存中，因此须在页表中增加若干项，供程序或数据在换进、换出时参考。

请求分页系统中的页表项：

状态位：指示该页是否已调入内存。

访问字段：可记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考。

修改位：页面调入内存后是否被修改。

外存地址：用于指出该页在外存上的地址。

2.1.2 缺页中断机构

在请求分页系统中，每当要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断作为中断，同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。但缺页中断是一种特殊的中断，与一般中断有明显区别：

在指令执行期间产生和处理中断信号。
一条指令在执行期间，可能产生多次缺页中断。

2.1.3 地址变换机构

很重要，建议一定要深刻理解变换过程，不然根本不会做习题！

请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能而形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。

在进行地址变换时，首先检索快表，试图从中找出所要访问的页。若找到，便修改页表项中的访问位，供置换算法选换出页面时参考。对于写指令，还须将修改位置成“1”，表示该页在调入内存后已被修改。然后利用页表项中给出的物理块号和页内地址形成物理地址。地址变换过程到此结束。

如果在快表中未找到该页的页表项，则应到内存中去查找页表，再从找到的页表项中的状态位P来了解该页是否已调入内存。若该页已调入内存，这时应将该页的页表项写入快表。（如果当快表已满时，则应先调出按某种算法所确定的页的页表项，然后再写入该页的页表项）；若该页尚未调入内存，这时应产生缺页中断，请求OS从外存把该页调入内存。后续的页面调入过程，可以跳转到下面的：页面调入策略。

注意：将页面换入内存后，需要修改页表和块表。

2.2 请求分页中的内存分配

驻留集：指请求分页存储管理中给进程分配的物理块的集合。

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；
若驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

固定分配：

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

可变分配：

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

局部置换：

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

全局置换：

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

对于分配和置换两两组合，可以搭配出3种方案，但有一种不行。

因为固定分配+全局置换：其中全局置换意味着一个进程拥有的物理块数量必然会改变，因此不可能是固定分配！

2.2.1 固定分配+局部置换

系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。

这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。(采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)

2.2.2 可变分配+全局置换

刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。

采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。

2.2.3 可变分配+局部置换

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

考点：
可变分配全局置换：只要缺页就给分配新物理块

可变分配局部置换：要根据发生缺页的频率来动态地增加或减少进程的物理块

2.3 页面调入策略

2.3.1 何时调入页面

【1】预调页策略

采用以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。

主要用于进程的首次调入时，由程序员指出应该先调入哪些页。

【2】请求调页策略

当程序在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需要的页面调入内存。

优点：由请求调页策略所确定调入的页，一定会被访问；请求调页策略比较容易实现。

缺点：每次仅调入一页，需花费较大的系统开销，增加了磁盘I/O的启动频率。

2.3.2 从何处调入页面

【1】系统拥有足够的对换区空间：

页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。

【2】系统缺少足够的对换区空间：

凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。

3.UNIX方式：运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。

2.3.3 页面调入过程

【1】每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保护CPU环境，分析中断原因后，转入缺页中断处理程序。

【2】该程序通过查找页表，得到该页在外存上的物理块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。

【3】如果内存已满，则需按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表。

【4】在缺页调入内存后，利用修改后的页表，形成所要访问的物理地址，再去访问内存数据。

三、页面置换算法

在进程运行过程中，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，需从内存中调出一页程序或数据，送入磁盘的对换区。但应将哪个页面调出，需根据一定的算法来确定。把选择换出页面的算法称为页面置换算法，其好坏直接影响系统的性能。

因为页面的换入、换出需要磁盘I/O，会有较大的开销，因此一个好的置换算法应具有较低的页面更换频率。从理论上讲，应将那些以后不会再访问的页面换出，或者把那些在较长时间内不会再访问的页面换出。

3.1 最佳置换算法（OPT）

其所选择的被淘汰页面，将是以后永不再用的，或许是在最长(未来)时间内不再被访问的页面。

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

整个过程缺页中断发生了9次，页面置换发生了6次。
注意：缺页时未必发生页面置换。若还有可用的空闲内存块，就不用进行页面置换。

因此：缺页率 = 9/20 = 45%

优点：保证获得最低的缺页率

缺点：无法预知一个进程在内存的若干个页面，哪个在未来最长时间内不再被访问。（因此该算法是无法实现的，但是可以用它评价其他算法）

3.2 先进先出置换算法（FIFO）

算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针(替换指针)，使它总是指向最老的页面。

注意：队列的最大长度取决于系统为进程分配了多少个内存块！

例：假设系统为某进程分配了三个内存块，并考虑到有以下页面号引用串：
3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4

如上图所示，整个过程发生了9次缺页中断，所以缺页率为：9 / 12

下述还要一个例子，可以练练手！

当然，观察我们练习的这两个例子，可以发现当为进程分配的物理块数增大时，缺页次数不减反增的异常现象（又叫Belady异常）。

只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差。

3.3 最近最久未使用置换算法(LRU）

LRU( least recently used) : 每次淘汰的页面是最近最久未使用的页面。

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

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

发生了6次缺页中断，所以缺页率为：6 / 20

该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大。

3.4 Clock置换算法

最佳置换算法性能最好，但无法实现；先进先出置换算法实现简单，但算法性能差；最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU，NotRecently Used)

简单的CLOCK 算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位应被置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

例：假设系统为某进程分配了5个内存块，并考虑到有以下页面号引用串：

1、3、4、2、5、6、3、4、7

【1】分析当访问到6号页面时：

前面的5个页面恰好可以依次被分配给这5个内存块(并将其访问位改成1)，然后当访问6号页面时，此时指针在1号页，那么还是像时钟一样顺时针转动，依次检查各内存块(当需要淘汰一个页面时，如果是1，则将它置为0，暂不换出，继续检查下一个页面)，显然6号页面是缺页的。最后指针转完一圈后又回到1号页，并且各内存块访问位又改为0，因此在第2轮扫描时，由于1号页的访问位为0，因此可以作为被淘汰页面(将其置换为6号页面)，然后指针指向下一位 (即3号页)。

【2】分析当访问3、4号页面时：

当访问3号页时，命中，然后将其访问位改为1，然后指针不动（只发生缺页中断时，指针才转 ）。
当访问4号页时，命中，然后将其访问位改为1，然后指针不动。

【3】分析当访问7号页面时：

显然7号页会发生缺页中断，指针顺时针依次检查【如果是访问位0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面】，最后会淘汰2号页面，指针指向下一位（即5号页面）。

书上P179还有改进型Clock置换算法，有需要的可以去看看，当然如果看不懂，可以直接去看王道的视频：

3.2_3_页面置换算法_哔哩哔哩_bilibili

四、“ 抖动 ”与工作集

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够)

为了研究应该为每个进程分配多少个物理块, Denning 提出了进程“工作集”的概念。

驻留集：指请求分页存储管理中给进程分配的内存块的集合。
工作集：指在某段时间间隔里，进程实际访问页面的集合。

操作系统会根据“窗口尺寸”来算出工作集。例：
某进程的页面访问序列如下，窗口尺寸为4，各时刻的工作集为?

这里列出当访问到23和17时，对应的工作集：

工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。如：窗口尺寸为5，经过一段时间的监测发现某进程的工作集最大为3，那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。
一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。

最后，请求分段存储管理方式就不讲了，考试基本不考，有需要的可以去看书上P185。