1. 虚拟存储管理
1.1 传统存储管理方式的特征、缺点
一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：①作业很大时，不能全部装入内存，导致大作业无法运行；②当大量作业要求运行时，由于内存无法容纳所有作业，因此只 有少量作业能运行，导致多道程序并发度下降。
驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段 内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的
数据，浪费了宝贵的内存资源。
1.2 虚拟内存的定义和特征
基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存， 就可以让程序开始执行。 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续 执行程序。
若内存空间不够，由操作系统负责将内存中暂时用不 到的信息换出到外存。 在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存
虚拟内存有一下三个主要特征：
- 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
- 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换 入、换出。
- 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
1.3 虚拟内存技术的实现
虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在传统的非连续分配内存管理方式基础上。
主要区别：
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
1.4 小结
2. 请求分页存储管理
2.1 概念
请求分页系统是建立在基本分页的基础上的，为了能支持虚拟存储器功能而增加了请求调页功能和页面置换功能。
相应地，每次调入和换出的基本单位都是长度固定的页面，这使得请求分页系统在实现上要比请求分段系统简单（请求分段系统在换进和换出时是可变长度的段）。因此，请求分页便成为目前最常用的一种实现虚拟存储器的方式。
为了实现请求分页，系统必须提供一定的硬件支持。除了需要一台具有一定容量的内存及外存的计算机系统外，还需要有页表机制、缺页中断机构以及地址变换机构。
2.2 页表机制
在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将用户空间中的逻辑地址变换为内存空间中的物理地址。由于只将应用程序的一部分调入内存，还有一部分仍在外存上，故需在页表中再增加若干项，供程序（数据）在换进、换出时参考。
在请求分页系统中的每个页表项如下所示：
各字段的说明如下：
- 状态位P：用于指示该页是否已调入内存，供程序访问时参考。
- 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。
- 修改位M：表示该页在调入内存后是否被修改过。供置换页面时参考。
由于内存中的每一页都在外存上有一份副本，因此，若未被修改，在置换该页时就不需要将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。 - 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。
2.3 缺页中断机构
在请求分页系统中，每当访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。 此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则“将其写回外存。未修改过的页面不用写回外存。
缺页中断作为中断，同样需要经历诸如保护CPU现场、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU现场等几个步骤。
但缺页中断又是一种特殊的中断，它与一般的中断相比，有着明显的区别，主要表现在下面两个方面：
- 在指令执行期间产生和处理中断信号。通常，CPU都是在一条指令执行完成后，才检查是否有中断请求到达。若有，便去响应，否则，继续执行下一条指令。然而，缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时所产生和处理的。
- 一条指令在执行期间，可能产生多次缺页中断。所以，系统中的硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处继续执行。
2.4 地址变换机构
请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，为实现虚拟存储器而增加了某些功能而形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。
在进行地址变换时，首先去检索快表，试图从中找出所要访问的页。若找到，便修改页表项中的访问位。对于写指令，还需将修改位置成“1”，然后利用页表项中给出的物理块号和页内地址形成物理地址。地址变换过程到此结束。
如果在快表中未找到该页的页表项时，应到内存中去查找页表，再根据找到的页表项中的状态位P，了解该页是否已调入内存。
若该页已调入内存，这时应将此页的页表项写入快表，当快表已满时，应先调出按某种算法所确定的页的页表项；然后再写入该页的页表项。
若该页尚未调入内存，这时应产生缺页中断，请求OS从外存把该页调入内存。
细节：
①只有“写指令”才需要修改 “修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
②和普通的中断处理一样，缺页中断处理依然需要保留CPU现场。
③需要用某种“页面置换算法” 来决定一个换出页面
④换入/换出页面都需要启动慢速的I/O操作，可见，如果换入/ 换出太频繁，会有很大的开销。
⑤页面调入内存后，需要修改慢表，同时也需“将表项复制到快表中
2.5 小结
3.页面置换算法
3.1 最佳置换算法
最佳置换算法（OPT）（理想置换算法）：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。
最佳置换算法可以用来评价其他算法。假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
进程运行时，先将7, 0, 1三个页面依次装入内存。进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰。然后，访问页面0时，因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面1淘汰……依此类推，如图3-26所示。从图中可以看出釆用最佳置换算法时的情况。
可以看到，发生缺页中断的次数为9，页面置换的次数为6。
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 7 | |||||||||||
| 物理块2 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | ||||||||||||
| 物理块3 | 1 | 1 | 3 | 3 | 3 | 1 | 1 | |||||||||||||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ |
3.2 先进先出置换算法
先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块1 | 7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 7 | 7 | 7 | |||||
| 物理块2 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | 0 | 0 | ||||||
| 物理块3 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | |||||||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
这里仍用上面的实例，釆用FIFO算法进行页面置换。进程访问页面2时，把最早进入内存的页面7换出。然后访问页面3时，再把2, 0, 1中最先进入内存的页换出。由图 3-27可以看出，利用FIFO算法时进行了 12次页面置换，比最佳置换算法正好多一倍。
FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由 Belady于1969年发现，故称为Belady异常。只有FIFO算法可能出现Belady 异常，而LRU和OPT算法永远不会出现Belady异常。
3.3 最近最久未使用（LRU）算法
这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。
所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。
再对上面的实例釆用LRU算法进行页面置换。进程第一次对页面2访问时，将最近最久未被访问的页面7置换出去。然后访问页面3时，将最近最久未使用的页面1换出。
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块1 | 7 | 7 | 7 | 2 | 2 | 4 | 4 | 4 | 0 | 1 | 1 | 1 | ||||||||
| 物理块2 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 0 | 0 | |||||||||
| 物理块3 | 1 | 1 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 7 | ||||||||||
| 缺页否 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
实际上，LRU算法根据各页以前的情况，是“向前看”的，而最佳置换算法则根据各页以后的使用情况，是“向后看”的。
LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法。
3.4. 时钟(CLOCK)置换算法
LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。
简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。
3.5 改进型时钟置换算法
CLOCK算法的性能比较接近LRU，而通过增加访问的位数目，可以使得CLOCK算法更加高效。在访问位的基础上再增加一个修改位，用(访问位，修改位)方式表示，则得到改进型的CLOCK置换算法。这样，每一帧都处于以下四种情况之一：
- 最近未被访问，也未被修改(u=0, m=0)。
- 最近被访问，但未被修改(u=1, m=0)。
- 最近未被访问，但被修改(u=0, m=1)。
- 最近被访问，被修改(u=1, m=1)。
算法执行如下操作步骤：
- 从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对访问位不做任何修改。选择遇到的第一个帧(u=0, m=0)用于替换。(寻找最近未被访问，也未被修改的页面)
- 如果第1)步失败，则重新扫描，查找(u=0,m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的访问位设置成0。(寻找最近未被访问，但被修改的页面)
- 如果第2)步失败，指针将回到它的最初位置，并且集合中所有帧的访问位均为0。重复第1步(寻找最近被访问，但未被修改的页面)
- 如果第3)步失败，重复第2步(寻找最近被访问，被修改的页面)
改进型的CLOCK算法优于简单CLOCK算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回，因而这样做会节省时间。
3.6 小结
| 算法规则 | 优缺点 | |
|---|---|---|
| OPT | 优先淘汰最长时间内不会被访问的页面 | 缺页率最小，性能最好 但无法实现 |
| FIFO | 优先淘汰最先进入内存的页面 | 实现简单；但性能很差 可能出现Belady异常 |
| LRU | 优先淘汰最近最久没访问的页面 | 性能很好；但需要硬件 支持，算法开销大 |
| CLOCK（NRU） | 循环扫描各页面第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。若第一轮没选中则进行第二轮扫描。 | 实现简单，算法开销小但未考虑页面是否被修改过。 |
| 改进型CLOCK（改进型NRU） | 若用（访问位, 修改位）的形式表述，则 第一轮：淘汰（0, 0） 第二轮：淘汰（0, 1），并将扫描过的页面访问位都置为0 第三轮：淘汰（0, 0） 第四轮：淘汰（0, 1） |
算法开销较小，性能也不错 |
4. 页面分配
4.1 驻留集大小
对于分页式的虚拟内存，在准备执行时，不需要也不可能把一个进程的所有页都读取到主存，因此，操作系统必须决定读取多少页。也就是说，给特定的进程分配多大的主存空间，这需要考虑以下几点：
- 分配给一个进程的存储量越小，在任何时候驻留在主存中的进程数就越多，从而可以提高处理机的时间利用效率。
- 如果一个进程在主存中的页数过少，尽管有局部性原理，页错误率仍然会相对较高。
- 如果页数过多，由于局部性原理，给特定的进程分配更多的主存空间对该进程的错误率没有明显的影响。
4.2 三种策略
基于这些因素，现代操作系统通常釆用三种策略：
- 固定分配局部置换
它为每个进程分配一定数目的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。
实现这种策略难以确定为每个进程应分配的物理块数目：太少会频繁出现缺页中断，太多又会使CPU和其他资源利用率下降。 - 可变分配全局置换
这是最易于实现的物理块分配和置换策略，为系统中的每个进程分配一定数目的物理块,操作系统自身也保持一个空闲物理块队列。当某进程发生缺页时，系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的页装入其中。 - 可变分配局部置换
它为每个进程分配一定数目的物理块，当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其他进程的运行。如果进程在运行中频繁地缺页，系统再为该进程分配若干物理块，直至该进程缺页率趋于适当程度； 反之，若进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。
4.3 调入页面的时机
为确定系统将进程运行时所缺的页面调入内存的时机，可釆取以下两种调页策略：
- 预调页策略
根据局部性原理，一次调入若干个相邻的页可能会比一次调入一页更高效。但如果调入的一批页面中大多数都未被访问，则又是低效的。所以就需要釆用以预测为基础的预调页策略，将预计在不久之后便会被访问的页面预先调入内存。但目前预调页的成功率仅约50%。故这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。 - 请求调页策略
进程在运行中需要访问的页面不在内存而提出请求，由系统将所需页面调入内存。由这种策略调入的页一定会被访问，且这种策略比较易于实现，故在目前的虚拟存储器中大多釆用此策略。它的缺点在于每次只调入一页，调入调出页面数多时会花费过多的I/O开销。
4.4 从何处调入页面
请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区通常是釆用连续分配方式，而文件区釆用离散分配方式，故对换区的磁盘I/O速度比文件区的更快。这样从何处调入页面有三种情况：
- 系统拥有足够的对换区空间：可以全部从对换区调入所需页面，以提髙调页速度。为此，在进程运行前，需将与该进程有关的文件从文件区复制到对换区。
- 系统缺少足够的对换区空间：凡不会被修改的文件都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出。但对于那些可能被修改的部分，在将它们换出时须调到对换区，以后需要时再从对换区调入。
- UNIX方式：与进程有关的文件都放在文件区，故未运行过的页面，都应从文件区调入。曾经运行过但又被换出的页面，由于是被放在对换区，因此下次调入时应从对换区调入。进程请求的共享页面若被其他进程调入内存，则无需再从对换区调入。