五、虚拟存储器

1，虚拟存储器概念

第四章讲的存储器都有一个共同的特点：要求将一个作业全部装入内存后才可以运行，于是出现了两种情况：

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

虚拟存储器的工作原理：

程序在运行时没有必要全部装入内存，仅将当前要运行的少数页面或段先装入内存就可以运行。在运行时，如果要访问的页（段）已经装入内存便可执行下去，如果要访问的页（段）尚未调入内存（称为缺页或缺段），便发出缺页（段）中断请求，此时OS利用请求调页（段）功能将他们调入内存，继续执行。

如果内存已满，OS会利用也（段）置换功能将内存中暂时不用的页（段）调出内存，腾出足够的空间，再将要访问的页（段）调入内存。这样，可以使大的程序在小内存空间中执行。

虚拟存储器的概念：

当用户看到自己程序正常运行时，他会认为该系统所具有的内存容量比自己的程序大，但用户看到的大容量只是一种错觉，是虚的，故吧这样的存储器称为虚拟存储器

虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的存储器系统

虚拟存储器的特征：

1. 多次性。作业中的程序无需一次装入内存，允许多次调入内存运行，只需要将当前要运行的那部分程序装入内存即可运行
2. 对换性。作业中的程序无需运行时一直常驻内存，允许将那些暂不使用的代码和数据从内存调至外存的对换区（换出），需要时再从外存调入内存（换进）。

虚拟存储器的实现方法：

1. 分页请求系统。在分页系统上增加了请求调页功能和页面置换功能
2. 分段请求系统。在分段系统的基础上增加了请求调段和分段置换功能。

2，请求分页存储管理方式

请求页表机制

页表的基本作用还会将逻辑地址映射为内存空间中国的物理地址。在请求页表中新增了四个字段，页表如下：

状态位P：在分页系统中只将一部分程序调入内存，一部分在外存，故用该字段表示该页是否调入内存

访问字段A：用来记录本页在一段时间被访问的次数，提供给页面置换算法参考

修改为M：标识该页在调入内存后是否被修改过。由于内存中的每一页在外存中都保存一份副本，在置换该页时，若未被修改，就不需要将该页写回外存，若被修改，则将该页重写到外存上，保证外存所保留的副本始终是最新的。

外存地址：用于之处改也在外存的地址，通常是物理块号。

页面调入策略

为了使进程能够正常运行，必须事先将要执行的程序所在页面调入内存。有一些问题：

1. 系统在何时调入所需页面

为了确定页面调入内存的时机，有两种策略：

1. 从何处调入所需页面

请求分页系统中将外存分为两部分：用于存放文件的文件区和用于存放兑换页面的对换区。对换区采用连续分配的方式，而文件区采用离散分配的方式，对换区的IO速度比文件区高。系统从何处将缺页调入内存，分成下面三种情况：

1. 系统拥有足够的对换区空间，这时可以全部从对换区调入页面
2. 系统缺少足够的对换区空间，这时凡是不会修改的文件都直接从文件区调入，对于那些可能被修改的部分，在将他们换出时调到对换区，需要时再从对换区调入
3. UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面都应该从文件区调入，对于运行过但又被换出的页面放在对换区，下次调入时从对换区调入。UNIX允许页面共享，因此，某进程所请求的页面有可能已被其他进程调入内存，此时无须从对换区调入

缺页率

在进程的运行过程中，访问页面成功的次数为S，失败次数为F，总访问次数A=S+F，缺页率f=F/A

缺页率受下面几个因素影响：

1. 页面大小，页面划分越大，缺页率越低
2. 进程所分配的物理块数目，物理块数目越多，缺页率越低
3. 页面置换算法，算法的优劣决定了进程执行过程中缺页的次数

3，页面置换算法（PBA）

在进程运行时，所访问的页面不在内村，需将其调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序送到对换区中。吧选择换出页面的算法叫做页面置换算法。

抖动：不适当的算法会导致进程发生抖动，即刚被换出的页很快又要被访问，需要重新调入。频繁的更换页面导致进程运行中吧大部分时间都花费在页面置换上。

常见置换算法

1. 最佳置换算法

其所选的淘汰页是在最长时间内不再被访问的页面。

优点：可保证缺页率是最低的

缺点：该算法无法实现，但可以用来去评价其他算法

假定系统为某进程分配了三个物理块，并有以下的页面号：

则置换图如下，共发生了6次页面置换

1. 先进先出置换算法

该算法总是选择在内存中驻留时间最久的页面淘汰

1. 最近最久未使用算法（LRU， Least Recently Used）

LRU算法选择最近最久未使用的页面淘汰，该算法赋予每个页面一个访问字段，用来记录一个页面自上次访问以来所经历的时间t，当淘汰页面时，会选择现有页面中t最大的进行淘汰

1. 最少使用算法（LFU， Frequently）

LRU算法为内存中每个页面设置一个移位寄存器，用来记录该页面访问的频率。该置换算法选择在最近使其使用最少的页面作为淘汰页。该算法使用了移位寄存器，每次访问某页时，便将该移位寄存器的最高位置1，LFU算法的访问图与LRU算法的访问图完全相同。

1. Clock置换算法

LRU是一种较好的算法，但由于它要求有较多的硬件支持，使得实现成本较高，在实际应用中，大多采用LRU的近似算法，clock就是其中一种

clock只需为每页设置一位访问位，再将内存中所有页面通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置为1。

置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，则选择该页换出；如果是1，则置为0，再按照FIFO、算法检查下一个页面。当检查到队列中最后一个页面时，若访问位还是1，则再返回到队首去检查第一个页面。

4，请求分段存储管理方式

​ 是在分段的基础上所建立的管理方式，以分段为基本单位进行换入换出的

1. 请求段表机制

该表中增加了存取方式字段和增补位

| 段名 | 段长 | 段基址 | 存取方式 | 访问字段A | 修改为M | 存在位P | 增补位 | 外存地址 |
| ---- | ---- | ------ | -------- | --------- | ------- | ------- | ------ | -------- |
| | | | | | | | | |

存取方式：如果该字段为两位，则存取属性是只执行，制度和允许读/写

增补位：表示本段在运行过程中是否做过动态增长

1. 缺段中断机构