第五章 虚拟存储器

虚拟存储器概述

普通存储器管理方式很难处理的两个问题

有些作业很大，其所要求的内存容量超过了物理内存的大小，所以该作业无法在机器上执行；

有大量作业要求进行，其内存所需容量之和超过了物理内存的大小，在普通存储器的管理方式下，只能让少量作业先运行，其他作业在外存上等待调度；

可以理解的是，普通存储器管理方式对这两个问题的处理都没有提高系统的吞吐量和资源的利用效率，而这是操作系统的重要目的之二；

常规存储器管理方式的两个特点

一次性：是指作业内容必须全部装入内存后，程序才能开始执行；这样的做法使得大作业无法在小内存中运行，即问题1，同时也限制了进一步提高程序的多道并发度，直接限制了对处理机的利用率和系统吞吐量的提高；

驻留性：是指，作业一旦进入内存，直至作业运行结束都不会调出，即便发生了IO阻塞事件，进程长期处于等待状态，或者某些模块运行过一次之后就不在需要运行了，它们都将留在内存中，占有宝贵的内存空间；

驻留性和一次性使得内存中存有不少用不到或者暂时用不到的程序或者数据，如果能将这些用不到的数据暂时换出，就能提高资源的利用率，提高系统的吞吐量。实际山，一次性和驻留性是可以解决的，而解决的理论就是：局部性原理；

局部性原理

程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分，相应的，它所需要访问的内存空间也会局限于某个区域，支持论点有：

程序执行时，处理少部分的转移和过程调用指令外，大多数情况下是顺序执行的；

过程调用将会使程序的执行轨迹有一个区域跳转到另一个区域，但是过程调用的深度一般情况下不超过5，这就是说，程序的执行仍然局限于这些过程的范围之内且该范围不会很大；

程序中存在大量循环结构，这些结构仅有少量指令构成，但是它们将被执行多次；

程序中还包括许多对数据结构的处理，如对数组的处理，这些处理往往都局限于很小的空间内；

实际上，局部性原理又分为：

时间局部性：如果程序中某条指令被执行过，那么在不久的将来该指令很有可能会被再次执行；如果某个数据被访问过，那么在不久的将来，该数据很有可能会被再次访问；这是因为论点3，即大量循环操作；

空间局部性：如果程序访问了某个存储单元，那么不久的将来程序将访问该程序单元附近的程序单元；这是因为论点1,2,4；

虚拟存储器的基本工作原理

虚拟存储器基于局部性原理，在不将所有程序内容装入内存的情况下，仅调入程序开始执行所需要的部分内容即启动程序，其余内容仍然驻留外存；当程序所需要的内容不在内存上时，就发出中断请求，由系统将其调入内存；如果此时内存已满，则由系统根据某种算法换出一部分内存空间上的内容，从而接纳新调入的指令和数据；这样就解决了常规存储器管理方式不易处理的两个问题；

虚拟存储器的定义、特征及其实现方式

虚拟存储器的定义

虚拟存储器使得有较大内存空间需求的程序可以运行在较小内存空间的机器上，使得用户可以所感觉到的内存容量比实际容量大的一种存储器管理方式，因为用户产生了这种“错觉”，是一种虚拟扩展内存容量的方法，故称为虚拟存储器技术；

实际上，虚拟存储器管理技术是指具有请求调入功能和置换功能，从而在逻辑上扩展内存容量的一种存储器系统，其逻辑容量由内存容量和外存容量共同决定，其运行速度接近内存的速度，而每位的平均成本接近于外存。是一种性能非常优越的存储器管理技术；

虚拟存储器的特征

与常规存储器管理方式相比，虚拟存储器技术有以下几个特点：

多次性：是指程序的内容是多次调入内存空间，在程序开始时仅调入当时所需要的部分代码和数据，其余驻留外存，当发生缺失中断时再从外存中调入 。

对换性：程序和代码无需常驻内存，当某一部分不再需要时就将其对换到外存中，从而释放其占有的内存空间，当再次需要时再从外存中调入即可，对换性也是多次性的基础，如果没有对换功能，那么再调入外存中的内容时就有可能因为内存空间使用完毕而失败，系统无法正常工作也就谈不上逻辑扩充内存容量了。

虚拟性：虚拟性则是说， 用户看到的内存容量远远大于实际的容量。虚拟性以多次性和对换性为基础；而多次性和对换性又以离散分配为基础

虚拟存储器的实现方法

虚拟存储器的实现常见方法有：

分页请求系统：在分页系统的基础上增加请求调入和页面置换功能所形成的虚拟存储系统。系统需要提供必要的硬件和软件来支持请求分页的实现；

分段请求系统：在分段系统的基础上增加请求调入和页面置换功能所形成的虚拟存储系统。系统同样需要提供必要的硬件和软件来支持请求分页的实现；

段页式虚拟存储器系统：在段页式系统的基础上通过增加请求调入和置换功能所形成的虚拟存储系统。

请求分页存储管理方式

请求分页存储管理方式在基础的分页基础上通过增加请求调页功能和页面置换功能而形成，由于每次调入和置换出的都是长度固定的页面，所以其实现比较简单，因此也是最为常用的一种虚拟存储器实现方式；

请求分页中的硬件支持

请求页表机制：

请求分页系统使用请求页表来建立页和物理块之间的关联；页表项的结构相比分页系统中的页表项结构也有变化，其增加了四个字段：状态位、访问字段、修改位、外存地址，原有的两个字段是页号和物理块地址；各字段的含义如下：

状态位标志该页面是否已调入内存；

访问字段用于记录置换算法所需要的信息，常记录在一段时间内的访问次数；

修改位表示该页面内容是否被修改，如果没有被修改，在换出的时候就不需要重写入磁盘啦；

外存地址表示该页面在外存中的地址，通常是物理块号，供调入页面时使用；

请求分页中的缺页中断机制：

在请求分页系统中，每当所要访问的页面不在内存中时，便产生一个缺页中断，请求OS将所缺页面调入内存。缺页中断作为中断中的一种，其处理过程也要经过：保护CPU环境、分析中断原因、转入中断处理程序、恢复CPU环境等步骤；但是缺页中断是一种特殊的中断，其与一般的中断有以下两个区别：

一般中断是在指令执行完毕后，才检查是否有中断请求到达，但是缺页中断信号却是在指令执行期间发生，当所需要的指令不在内存中时，便立即产生缺页中断信号，以便能及时调入所缺页面；

一条指令的执行过程中可能产生多次缺页中断；

地址转换方式：

首先检查快表，试图从中找出要访问的页，若找到，那么修改页表项中的访问位，对于写指令，还需要修改修改位，然后利用页表项中的物理块号和指令中的页内地址形成物理地址；如果没有在快表里找到，那么就根据页号从页表里找到对应的页表项，检查其状态位，如果其不在内存中，则将其调入内存，之后将其放入快表；如果快表已满，则根据一定算法置换出去一些缓冲项，之后从页表项中读出物理块号，配合指令中的页内地址得到数据的实际位置，如果是写指令，还需要修改修改位；同时更新页表项中的访问字段，为置换算法提供依据；

请求分页中的内存分配

在为进程分配内存时，将涉及三个问题：第一，为保证进程能正常运行，所需要的最少物理块数的确定；第二，在为每个进程分配物理块时，应该采取怎样的分配策略，即所分配的物理块是固定的还是可变的；第三，为不同进程所分配物理块数，是采取平均分配算法还是根据进程的大小比例分配；

最小物理块数的确定

最少物理块数是指能保证进程正常运行所需要的最少物理块数，当系统为进程分配的物理块数小于该值时，进程将无法正常工作；至于该值的确定，与计算机的硬件结构相关，取决于指令的格式、功能和寻址方式。比如指令本身的长度（存储指令时需要的空间）、指令的寻址方式（寻找指令时需要的空间）等因素；

内存分配策略

在请求分页系统中，可采取两种内存分配策略，即可变分配和固定分配；在进行置换时，可以采取两种策略，即全局置换和局部置换；于是可以组合出三种适用的策略：

固定分配局部置换

所谓固定分配是指，为每个进程分配一组固定数目的物理块，在程序运行期间不再改变；所谓局部置换是指，如果进程在运行中发生缺页，只能在分配给进程的物理块间选择一个物理块置换出去；这种策略实现的难点在于如何确定该为进程分配多少个物理块，如果太多，则浪费资源，如果太少，则频繁发生缺页，甚至系统难以工作；

可变分配局部置换

所谓可变分配是指，先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况适当增加或者减少进程拥有的物理块；局部置换是指，如果进程在运行期间发现缺页，则根据一定算法，从该进程所占有的物理块中置换出去一个物理块，然后将所缺少的页面调入；当进程在运行过程中频繁发生缺页时便再为该进程分配若干物理块，直至该进程的缺页率降低到合适程度为止；

可变分配全局置换

所谓可变分配是指，先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况适当增加或者减少进程拥有的物理块；全局置换是指，如果进程在运行期间发现缺页，则从OS保留的所有空闲物理块中取出一块分配给该进程，如果没有空闲物理块，那么根据一定算法置换出去一个物理块，然后将所缺少的页面调入；这是最容易实现的一种内存分配策略；这是最容易实现的一种内存分配策略；

物理块分配算法

平均分配算法：将物理块平均分配给所有进程，每个进程，无论其他属性，得到相同数量的物理块；

按比例分配：将物理块以进程的大小按比例分配给各个进程；

按优先权分配算法：将物理块以进程紧急程度（优先权的大小）为依据分配给各个进程

页面调入策略

关于页面调入，需要解决两个问题：什么时候调入以及从何处调入

什么时候调入

为了确定系统将进程所缺少页面调入内存的时机，可以采取预调页策略或者请求调页策略

预调页策略。如果进程的许多页存放在外存的一个连续区域里，那么一次性调入若干个相邻的页面将比一次调入一个页面更高效；但是如果调入的页面在将来没有被访问，那么就会被再次置换出去，反而降低了效率；所以需要一种以预测为基础的预调页策略，调入那些不久的将来就会访问的页面，那么效率提升就很明显了，然而遗憾的是，现在预调页的成功率仅有50%；

请求调页策略。在进程运行的过程中，如果发现需要的指令或者数据不在内存，便发出请求，由OS将其所需要的页面调入内存，由于请求调页策略所调入的页面一定会被访问，而且实现起来比较简单，所以大多虚拟存储器都会采用这种策略；但是很明显的是，这种策略并不高效，因为一次只调入一个页面；

从何处调入

分页系统的外分为两部分，一部分是用于存放文件的文件区，另一部分是存放对换页面的对换区；通常，对换区采用连续分配的方式，而文件区采用离散的空间分配方式，所以从外存中获得数据时，对换区要快于文件局。这样，每当系统发生缺页时，将有三种情况：

系统拥有足够对换区，在进程运行之前，将所有页面拷贝到对换区，这样就可以直接在对换区寻找所缺少的页面了；

系统没有足够的空间时，凡是不会被修改的文件，从文件区里获得，因为它们退出内存时不需要写回磁盘，所以会直接被抹去，下次需要的时候再从外从中调入就好；对于可能被修改的部分，需要将其调入的对换区，以后需要的时候就从对换区寻找；

Unix系统的方式：因为所有与进程相关的文件都放在文件区，所以凡是未运行过的页面，放在文件区，需要的时候也从文件区调入；对于从内存中返回的页面，将其放入对换区，下次调入时，从对换区寻找；因为UNIX系统允许共享页面，所以某个进程需要的页面可能已被其他进程调入内存；

缺页率：页面缺失的次数与页面访问次数的比值为缺页率；缺页率受以下几个因素影响

页面大小：页面越大，缺页率越低；反之越高；

进程所分配到的物理块数：物理块越多，缺页率越低；反之越高；

页面置换算法：算法优劣决定了进程执行过程中缺页中断的次数，所以缺页率也可以反映置换算法的优劣；

程序固有特性：程序的局部性特点越突出，缺页率越低；反之越高；

值得注意的是，在考虑置换算法时，还需要考虑置换的代价，比如检查页面是否被修改，如果没有被修改，那么就可以直接抹去，如果被修改，那么还需要写回到磁盘；

页面置换算法

页面置换算法是指当内存空间不足而又需要调入页面时，系统选择被置换出去页面的算法；

好的页面置换算法应具有较低的页面更换频率。不适合的置换算法将出现抖动情况：刚刚被置换出去的页面，很快又被调入，这样系统的一部分时间就在页面置换工作上，而没有进行业务处理，是一种资源的浪费；

实际上，好的页面置换算法应将那些再也用不到的页面置换出去，但是，如何识别未来的情况不是一件容易的事，常见的策略是站在过去看未来；

下面是几种常见的页面置换算法：

最佳置换算法：性能最好的置换算法，因为它对未来的判断达到了100%，同样，也决定了它无法实际应用，唯一的作用是作为衡量其他算法的标尺；该算法从已在内存中的页面中选择未来最长时间内不会使用的页面将其置换出去；但是现实中是无法预测未来的啊！

先进先出页面置换算法：该算法与通常页面的使用规律不符，往往是性能最差的算法，因为该算法使用调入时间这一因素来预测未来，与实际的访问情况没有很大关系，比如，最先调入的页面，可能最近一直被访问，把它置换出去，不久的将来还得找回来，何必呢？

最近最久未使用算法：该算法使用近期的访问情况作为预测未来的依据，即最近频繁使用的页面，那么将来也很有可能继续访问，所以找出最近最久未使用（使用频率最低）的页面置换出去，因为这些页面未来使用的可能性最低；该算法的实现，需要为每个页面使用一个寄存器来标识时间的流逝；如果访问某个页面，那么就对应的寄存器中的存储的数字的最高位置为1,；然后每隔一定时间，就将所有寄存器的数字右移一位，这样数字的大小就能表示使用频率啦；当然，也可使用栈的方式来管理各个页面的访问情况；

最少使用算法：该算法和最近最久未使用算法思路相同，都是使用最近的过去预测最近的未来；在该算法里，采取的依据是最近一段时间里的使用次数；其实和最近最久未使用算法基本相同；值得注意的是，因为移位操作是在一段时间间隔后进行的，所以在这段时间里，访问10000次某页面和访问1次页面是等效的；

Clock算法（最近未使用算法）：即便LRU(最近最久未使用)算法是一种不错的算法，但是需要系统提供较多的硬件支持，所以在实际运用过程中，大多采用该算法作为替代，故该算法也叫作最近未使用算法：该算法中将页面组织为循环队列，每个页面有一个访问位，如果访问过该页面，就将其访问位置为1，否则将其访问位置为0；当寻找置换出去的页面时，遇到第一个访问位为0的页面就将其置换出去，如果遇到访问位为1的页面，那么将其访问位置为1，然后继续寻找；由于该算法循环检查各个页面的使用情况，所以就叫做Clock算法了；

值得注意的是，因为没有修改过的页面不需要进行写回磁盘的操作，所以我们希望置换出去的页面是未修改的页面，这是考虑了置换代价的结果，此时称为改进版Clock算法；这样，最佳的置换页面是最近既未使用过的页面还要是未修改过的页面，这样，检查的时候就不能只检查访问位A，还需要组合修改位M。这样就会遇到四种页面；

A=0；M=0：最佳置换页；

A=0；M=1：不是很好的置换页；

A=1；M=0：表示该页面最近被访问，但是内容尚未被修改，该页面可能最近还会被访问；

A=1；M=1：该页面不但被访问过，而且还修改了，不好不好；

此时，寻找的过程为：首先寻找A=0；M=0的页面，遇到就置换出，第一次扫描时不改变访问位A；如果没找到，那么进行第二次寻找，此时寻找A=0；M=1的页面，遇到就置换出，同时遇到A=1的页面将其置为0；如果第二遍还没有找到，说明所有的页面都被访问过（没找到A=0,M=0的，也没找到A=0,M=1的，所以在寻找之前，所有的A=1），但是此时所有的A都会为0，因为被修改了呗，第三遍寻找的时候，我们希望A=0,M=0的页面，此时如果遇到，就置换出；但是如果第三遍还没有找到，那说明开始第一遍寻找之前，A=1,M=1啊，这样我们就需要开始第四遍寻找，目标A=0，M=1，这样一定会找到，遇到就置换出；

一个有意思的结论是，因为考虑了置换代价，所以产生了寻找代价：原来只需要遍历一遍的，现在有可能遍历四遍；这就是大自然的定律：你想要带走点什么，就必须留下点什么；这样道理还有很多：机械可以省力（意味着费距离），但是不能省功；改进算法时常常使用空间换时间或者时间换空间，很难既省空间有省时间——除非提出新的算法；得失之间，尽显智慧！跑远了，回来！

PBA算法：在请求分页系统中，由于系统经常发生页面换进换出的情况，所以置换代价会对系统性能产生重大影响，PBA准确的说不是一种置换算法，而是一种处理置换页面的方法：上述的算法只是提到了如何选择置换页面，但是没有说明怎么处理置换出去的页面，而PBA算法刚好补上这一空缺；不得不说，缓存的确是提高效率的一把利刃，存储器系统就是基于缓存思想而设计的，而PBA也是将修改过的页面缓存起来，从而避免频繁地执行中断和IO驱动程序（这和现实生活中的垃圾桶是一样的，缓存就像是垃圾桶，你可以扔一次垃圾而把一天的垃圾都处理掉，总比产生一些垃圾就扔一次好吧），以这样的方式来提高系统效率；下面看看该算法使用的数据结构以及算法思想；

该算法有以下几个特点：

显著降低页面换进换出的频率，使IO操作的次数大为减少，从而降低了置换开销；

因为置换开销的降低，所以支持系统使用较为简单的置换策略，避免复杂算法对系统的特殊硬件要求；

该算法使用两个链表：空闲页面链表和修改页面链表；

对于空闲页面链表，它所容纳的是空闲物理块，用于分配给频繁发生缺页的进程以降低该进程的缺页率；当进程需要读入一个页面时，首先从空闲链表上获取一个空闲物理块，这样就避免了置换出其他页面的开销；当有一个未修改的页面换出时，实际上将其挂入空闲链表的尾部而不必执行写入操作；需要注意的是，虽然进入了空闲链表，但是该物理块还是装有数据，以后如果还有进程需要这些页面的数据，可直接从空闲链表上取出，而不必从磁盘读入，这也降低了页面换进的开销；

对于修改页面链表，设置该链表的目的就是减少已修改页面换出的次数，当修改页面的数量达到一定数量后，系统再一次性将其写出，这样就降低了页面写入磁盘的频率，降低从磁盘读入数据进入内存的频率；

当然，额外的管理也是需要时空代价的，这时，需要做的就是取舍；

访问时间

访问时间需要考虑访问页表和访问实际物理地址数据的时间，还需要考虑缺页中断的时间，还有考虑快表的存在，下面分三种情况讨论：

被访问的页在内存中，而且其对应的页表项在快表中；这样访问时间T=访问快表的时间+访问实际物理地址的时间；

被访问的页在内存中，且其对应的页表项不在块表中；这样访问时间T=访问快表的时间+访问页表的时间+修改快表的时间+访问实际物理地址的时间；

综合1,2两种情况，可以用来快表的命中率来统一得到访问页面在内存中的情况下的平均访问时间T1；

被访问的页面不在内存；这样访问时间T=访问快表的时间+访问页表的时间+缺页中断时间+更新快表的时间+访问实际物理地址的时间；

可综合T1和3，引入页面的缺页率来统一得到页面的访问时间TF；

抖动与工作集

基本概念

所谓抖动是指，处理机的利用率趋于0的现象，即处理机没有进行业务处理，而是忙于中断响应；产生抖动的根本原因是同时运行在系统中的进程太多，而分配给每个进程的物理块太少，进程频繁发生缺页中断，这就使得每个进程的大部分时间都用于页面的换进换出，而不去做有效的工作；

所谓工作集就是指进程在某段时间里实际要访问的页面集合；这是基于程序的局部性原理来定义的，因为根据局部性原理，程序度页面的访问是不均匀的，所以一段时间里，对某些页面的访问要明显高于其他页面，这些被集中访问的页面就是进程当前的工作集；

抖动的解决方案

采取局部替换策略：这样，一个进程发生了“抖动”也不会影响到其他进程；于是可以控制抖动的影响范围，该方法虽然简单，但是效果并不是很好，因为一旦某个进程发生抖动，那么会让磁盘IO的等待队列增长，使得其他等待磁盘IO的进程的等待时间变长；

将工作集算法考虑到处理机调度中，当调度程序发现处理机效率较低时，不是简单的从外存中引入作业，而是先检查在内存中的每个进程是否有足够的空间，如果进程对物理块没有需求，那么就可以引入新的作业，如果内存使用紧张，则首先为那些缺页率高的作业增加新的物理块，即暂停调入新的作业；

利用L=S准则来调节多道程序度；L为缺页之间的平均时间，S为缺页服务时间，即置换一个页面的平均时间；如果L远远比S大，说明缺页较少发生，此时磁盘的能力尚未得到充分利用；反之，如果L小于S那么，这说明缺页频繁发生，缺页的速度已超过磁盘的处理能力；只有当L=S时，系统的资源利用率最为协调；实践检验后，发现L=S准则对于调节缺页率是十分有效的；

为防止发生抖动，系统必须减少多道程序的数量。此时应该基于某种选择策略暂停当前活动的某些进程以释放内存空间，将其分配给其他进程；通常采取和调度程序一致的策略；

总体来说，就是保证进程有充分的内存空间可以使用，从而降低缺页率；