引入虚拟存储器的动机

传统存储器管理方式

无论是连续还是离散的存储器管理方式，统称为传统存储器管理方式，它们全都具有如下两个共同的特征。第一个是一次性，是指作业必须一次性地全部装入内存后方能开始运行。第二个是驻留性，是指作业被装入内存后，整个作业都一直驻留在内存中，其中任何部分都不会被换出，直至作业运行结束。尽管运行中的进程可能会被阻塞，或者有的程序模块在运行过一次后就不再需要(运行)了，它们都仍将继续占用的内存资源。部装入内存后方能运行。由于这 2 个性质，可能会导致两种情况：

1. 有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存使该作业无法运行；
2. 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存先运行，将其它大量的作业留在外存上等待。

出现上述两种情况的原因都是由于内存容量不够大，如果从物理上增加内存容量，往往会受到机器自身的限制而且要增加成本，另一种方法是从逻辑上扩充内存容量。

局部性原理

程序在执行时将呈现出局部性规律，即在一较短的时间内程序的执行仅局限于某个部分，相应地所访问的存储空间也局限于某个区域。局限性表现在下述两个方面：

虚拟存储器

虚拟存储器的定义

基于局部性原理可知，应用程序运行时仅须将当前要运行的少数页面或段先装入内存便可，其余部分暂留在盘上。在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。这样使一个大的用户程序在较小的内存空间中运行，也可在内存中同时装入更多的进程，使它们并发执行。

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。它的运行速度接近于内存速度，而每位的成本却又接近于外存。虚拟内存的最大容量是由计算机的 CPU 寻址范围确定的，实际容量是内存和外存容量之和和 CPU 寻址范围之间的最小值。例如某计算机地址结构为 32 位，按字节编址，内存大小为 512 MB，外存大小为 2 GB。则虚拟内存的最大容量为 2^32 B = 4 GB，虚拟内存的实际容量 = min(2^32 B, 512 MB + 2 GB) = 2 GB + 512 MB

虚拟存储器的特征

虚拟内存有一下三个主要特征：

虚拟存储器的实现

在虚拟存储器中，允许将一个作业分多次调入内存。如果采用连续分配方式，必须事先为作业一次性地申请一个足以容纳整个作业的内存空间，这样无法、也无意义再从逻辑上扩大内存容量。所以虚拟存储器的实现，都建立在离散分配存储管理方式的基础上。

分页请求系统

分页请求系统是在分页系统的基础上，增加请求调页功能和页面置换功能，形成页式虚拟存储系统。它允许用户程序只装入少数页面的程序(及数据)即可启动运行，再通过调页功能及页面置换功能陆续地把即将运行的页面调入内存，同时把暂不运行的页面换出到外存上。

请求分段系统

请求分段系统是在分段系统的基础上，增加了请求调段及分段置换功能，形成段式虚拟存储系统。它允许用户程序只要装入少数段（而非所有的段）的程序和数据即可启动运行，以后通过调段功能和段的置换功能将暂不运行的段调出，再调入即将运行的段。

请求分页存储的硬件支持

计算机系统除了要求一定容量的内存和外存外，还需要有请求页表机制、缺页中断机构以及地址变换机构。

请求页表机制

在请求分页系统中需要的主要数据结构是请求页表，作用仍然是将逻辑地址映射为物理地址。为了满足页面换进换出的需要，在请求页表中又增加了四个字段。

缺页中断机构

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒放回就绪队列。如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

缺页中断是一种特殊的中断，它是在指令执行期间产生和处理中断信号。一条指令在执行期间可能产生多次缺页中断，例如“copy A to B”将逻辑地址 A 中的数据复制到逻辑地址 B，而 A、B 属于不同的页面就有可能产生两次中断。

地址变换机构

请求分页系统中的地址变换机构是在分页系统地址变换机构的基础上，再增加了某些功能所形成的，如产生和处理缺页中断以及从内存中换出一页的功能等。在进行地址变换时，首先检索快表，试图从中找出所要访问的页。若找到便修改页表项中的访问位，对于写指令还须将修改位置成“1”，表示该页在调入内存后已被修改。然后利用页表项中给出的物理块号和页内地址形成物理地址，地址变换过程到此结束。如果在快表中未找到该页的页表项，则应到内存中去查找页表，再从找到的页表项中的状态位 P 来了解该页是否已调入内存。若该页已调入内存，这时应将该页的页表项写入快表。当快表已满时，则应先调出按某种算法所确定的页的页表项，然后再写入该页的页表项。若该页尚未调入内存，这时应产生缺页中断，请求 OS 从外存把该页调入内存。

分页管理的内存分配

在为进程分配内存时，将涉及到为保证进程能正常运行需要多少物理块数，以及在为每个进程分配物理块时应采取什么样的分配策略的问题。

驻留集

驻留集指请求分页存储管理中给进程分配的物理块的集合，在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少。驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

内存分配策略

在请求分页系统中分配内存时，可采取固定或可变分配两种策略。

在进行置换时，也可采取全局置换或局部置换两种策略。

通过分配策略和置换策略的组合，可组合出以下三种适用的策略。简单地说可变分配全局置换是只要缺页就给分配新物理块，可变分配局部置换是要根据发生缺页的频率来动态地增加或减少进程的物理块。

没有固定分配全局置换的原因是，全局置换意味着一个进程拥有的物理块数量必然会改变，因此不可能是固定分配。

物理块分配算法

在采用固定分配策略时，如何将系统中可供分配的所有物理块分配给各个进程，可采用下述几种算法：

1. 平均分配算法：即将系统中所有可供分配的物理块平均分配给各个进程；
2. 按比例分配算法：即根据进程的大小按比例分配物理块；

3. 考虑优先权的分配算法：为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。

   页面调入策略

   为使进程能够正常运行，必须事先将要执行的那部分程序和数据所在的页面调入内存。

   调入页面的时机

   为了确定系统将进程运行时所缺的页面调入内存的时机，可采取预调页策略或请求调页策略。预调页策略是采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存。如果预测较准确能有效改善性能，但目前预调页的成功率仅约 50%。
   请求调页策略是进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存便立即提出请求，由 OS 将其所需页面调入内存。由请求调页策略所确定调入的页是一定会被访问的，且请求调页策略比较易于实现，故在目前的虚拟存储器中大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘 I/O 的启动频率。

   调入页面的区域

   将请求分页系统中的外存分为两部分，一部分是用于存放文件的文件区，一部分是用于存放对换页面的对换区。通常由于对换区是采用连续分配方式，而文件区是采用离散分配方式，所以对换区的数据存取(磁盘 I/O)速度比文件区的高。每当发生缺页请求时，系统应从何处将缺页调入内存有以下情况：
   第一种情况，当系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。在进程运行前，便须将与该进程有关的文件从文件区拷贝到对换区。
   
   第二种情况，系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入，这些页面由于它们未被修改，不必再将它们重写到磁盘(换出)。以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时便须调到对换区，以后需要时再从对换区调入。
   
   第三种情况可以使用 UNIX 方式，凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时应从对换区调入。
   

   页面调入的过程

   每当程序所要访问的页面未在内存时(存在位为“0”)，便向 CPU 发出一缺页中断，中断处理程序首先保留 CPU 环境，分析中断原因后转入缺页中断处理程序。该程序通过查找
   页表得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘 I/O，将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法，从内存中选出一页准备换出。如果该页未被修改过(修改位为“0”)，可不必将该页写回磁盘；但如果此页已被修改(修改位为“1”)，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表形成所要访问数据的物理地址，再去访问内存数据。

   缺页率

   假设一个进程的逻辑空间为 n 页，系统为其分配的内存物理块数为 m(m ≤ n)。如果在进程的运行过程中，访问页面成功的次数为 S，访问页面失败的次数为 F，则该进程总的页面访问次数和缺页率 f 的计算公式为：
   Copy Highlighter-hljsA = S + F f = F / A
   通常缺页率受到以下几个因素的影响：

4. 页面大小：页面划分较大则缺页率较低，反之缺页率较高。

5. 进程所分配物理块的数目：所分配的物理块数目越多缺页率越低，反之则越高。
6. 页面置换算法：算法的优劣决定了进程执行过程中缺页中断的次数
7. 程序固有特性：程序编制的局部化程度越高，相应执行时的缺页程度越低。

事实情况下没有修改过的页面可以直接放弃，而修改过的页面则必须进行保存，所以处理这两种情况时的时间也是不同的。假设被置换的页面被修改的概率是 β，其缺页中断处理时间为 ta，被置换页面没有被修改的缺页中断时间为 ts，那么缺页中断处理时间的计算公式为：
Copy Highlighter-hljst = β × ta + (1 - β) × tb

抖动和工作集

抖动

由于虚拟存储器系统能从逻辑上扩大内存，这时只需装入一个进程的部分程序和数据便可开始运行。故人们希望在系统中能运行更多的进程以提高处理机的利用率，但处理机的实际利用率却如图的实线所示。随着进程数目的增加，处理机的利用率急剧增加，但到达 N1 时增速就减慢了，到达 Nmax 时处理机利用率达到最大。到达 N2 时若再继续增加进程数，利用率将加速下降趋于 0，这是因为发生了“抖动”现象。

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

工作集

进程发生缺页率的时间间隔与进程所获得的物理块数有关，缺页率会随着分配的物理块数的增加而明显地减少。当物理块增加到某个数目时，再增加物理块对缺页率的改善已经不明显，此时就没有继续增加的必要了。

工作集指在某段时间间隔里，进程实际访问页面的集合。操作系统会根据“窗口尺寸”来算出工作集，工作集大小可能小于窗口尺寸。实际应用中操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。
例如窗口尺寸为 5，经过一段时间的监测发现某进程的工作集最大为 3，那么可以给这个进程分配 3 个以上的内存块满足运行需要。一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。

防止抖动的方法

为了保证系统具有较大的吞吐量，必须防止“抖动”的发生，下面是几个较常用的预防“抖动”发生的方法。

页面置换算法

内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。应将哪个页面调出，须根据一定的算法来确定，选择换出页面的算法称为页面置换算法(Page-Replacement Algorithms)。置换算法的好坏将直接影响到系统的性能，不适当的算法可能会导致进程发生“抖动”，一个好的页面置换算法应具有较低的页面更换频率

最佳置换算法

最佳置换算法是一种理论上的算法，其所选择的被淘汰页面将是以后永不使用或在最长未来时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率，但由于无法预知哪一个页面是未来最长时间内不再被访问的，因而该算法无法实现，但可以利用该算法去评价其它算法。
假定系统为某进程分配了三个物理块，有以下的页面号引用串。
Copy Highlighter-hljs7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
进程运行时先将 7，0，1 三个页面装入内存，当进程要访问页面 2 时将会产生缺页中断。此时 OS 根据最佳置换算法将选择页面 7 淘汰，这是因为页面 0 将作为第 5 个被访问的页面，页面 1 是第 14 个被访问的页面，而页面 7 则要在第18次页面访问时才需调入。以此类推，得到采用最佳置换算法在各个页面引用时的状态。由表格可看出，采用最佳置换算法发生了 6 次页面置换。

先进先出页面置换算法

FIFO 算法总是淘汰最先进入内存的页面，也就是选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，但该算法与进程实际运行的规律不相适应，因为在进程中有些页面经常被访问，FIFO 算法并不能保证这些页面不被淘汰。
假定系统为某进程分配了三个物理块，有以下的页面号引用串。
Copy Highlighter-hljs7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
采用 FIFO 算法进，当进程第一次访问页面 2 时将把第 7 页换出，因为它是最先被调入内存的。在第一次访问页面 3 时，又将把第 0 页换出，因为它在现有的 2、0、1 三个页面中是最老的页。利用 FIFO 算法时，进行了 12 次页面置换，比最佳置换算法正好多一倍。

最近最久未使用置换算法

最近最久未使用 LRU(Least Recently Used)置换算法根据页面调入内存后的使用情况做出决策的，LRU 算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t。当需淘汰一个页面时，选择现有页面中其 t 值最大的页面淘汰。LRU 置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。可以为每个在内存中的页面配置一个移位寄存器记录未使用时间，也可以利用一个特殊的栈保存当前使用的各个页面的页面号。
假定系统为某进程分配了三个物理块，有以下的页面号引用串。
Copy Highlighter-hljs7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
当进程第一次对页面 2 进行访问时，由于页面 7 是最近最久未被访问的，故将它置换出去。当进程第一次对页面 3 进行访问时，第 1 页成为最近最久未使用的页，将它换出。利用 LRU 算法时，进行了 9 次页面置换。

Clock 置换算法

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

简单的 CLOCK 算法

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

改进的 CLOCK 算法

在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上。但如果该页未被修改过，则不必将它拷回磁盘。对于修改过的页面，在换出时所付出的开销比未修改过的页面大。在改进型 Clock 算法中，还须再增加一个置换代价的因素，这样选择页面换出时，未使用过和未被修改过的页面要综合考虑。由访问位 A 和修改位 M 可以组合成下面四种类型的页面：

1. A = 0，M = 0：该页最近既未被访问，又未被修改，是最佳淘汰页。
2. A = 0，M = 1：该页最近未被访问，但已被修改，并不是很好的淘汰页。
3. A = 1，M = 0：最近已被访问，但未被修改，该页有可能再被访问。
4. A = 1，M = 1：最近已被访问且被修改，该页可能再被访问。

在进行页面置换时，与简单 Clock 算法的差别在于该算法须同时检查访问位 A 与修改位 M。其执行过程可分成以下三步：

1. 从指针所指示的当前位置开始扫描循环队列，寻找第一类页面。将所遇到的第一个页面作为所选中的淘汰页，第一次扫描期间不改变访问位 A；
2. 如果第一步失败则开始第二轮扫描，寻找第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置 0；
3. 如果第二步也失败则将指针返回到开始的位置，并将所有的访问位复 0 然后重复第一步。如果仍失败就再重复第二步，此时就一定能找到被淘汰的页。

改进后的算法与简单 Clock 算法比较，可减少磁盘的 I/O 操作次数。但为了找到一个可置换的页，可能须经过几轮扫描。

页面缓冲算法

对于已经被修改过的页面，在将其换出时应当写回磁盘。如果每当有一个页面要被换出时就将它写回磁盘，这意味着每换出一个页面，便需要启动一次磁盘。页面缓冲算法 PBA在系统中建立了一个已修改换出页面的链表，对每一个要被换出的页面(已修改)，系统可暂不把它们写回磁盘，而是将它们挂在已修改换出页面的链表上。仅当被换出页面数目达到一定值时，再将它们一起写回到磁盘上，这样就显著地减少了磁盘 I/O 的操作次数。如果有进程在这批数据还未写回磁盘时需要再次访问这些页面时，就不需从外存上调入，而直接从已修改换出页面链表中获取，这样也可以减少将页面从磁盘读入内存的频率。

请求分段存储管理方式

请求分段存储的硬件支持

与请求分页系统相似，在请求分段系统中所需的硬件支持有段表机制、缺段中断机构，以及地址变换机构。

请求段表

在请求分段式管理中所需的主要数据结构是请求段表，除了具有请求分页机制中有的访问字段 A、修改位 M、存在位 P 和外存始址四个字段外，还增加了存取方式字段和增补位，这些字段供程序在调进、调出时参考。

缺段中断机构

在请求分段系统中采用的是请求调段策略，每当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生缺段中断信号，进入 OS 后由缺段中断处理程序将所需的段调入内存。与缺页中断机构类似，但由于分段是信息的逻辑单位，因而不可能出现一条指令被分割在两个分段中和一组信息被分割在两个分段中的情况。由于段不是定长的，这使对缺段中断的处理要比对缺页中断的处理复杂。

地址变换机构

因为被访问的段并非全在内存，所以在地址变换时若发现所要访问的段不在内存，必须先将所缺的段调入内存并修改段表，然后才能再利用段表进行地址变换。为此在地址变换机构中又增加了某些功能，如缺段中断的请求及处理等。

分段共享

分段存储管理方式的优点是便于实现分段的共享与保护，实现分段共享可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。在表项的上面记录了共享段的段号、段长、内存始址、状态(存在）位、外存始址以及共享计数等信息，接下去就是记录了共享此分段的每个进程的情况。

在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中。还须在共享段表中增加一表项，填写请求使用该共享段的进程名、段号和存取控制等有关数据，把 count 置为 1。当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中增加一表项，再执行 count = count + 1 操作表明有两个进程共享该段。
当共享此段的某进程不再需要该段时，应将该段释放，包括撤消在该进程段表中共享段所对应的表项，以及执行 count = count - 1 操作。若结果为 0 则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，否则只是取消调用者进程在共享段表中的有关记录。

分段保护

在分段系统中，由于每个分段在逻辑上是相对独立的，因而比较容易实现信息保护。目前常采用以下几种措施：