1.虚拟存储器的基本概念

1）常规存储器管理不足的原因：

常规存储器管理方式的特征:

一次性：作业在运行前一次性地全部装入内存

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

2）局部性原理

时间局部性：被引用过一次的存储器位置很可能在不远的将来再被多次引用

空间局部性：如果一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器功能。

基于局部性原理

程序运行前，不需全部装入内存（打破一次性）

    仅装入当前要运行的部分页面或段即可运行，其余部分暂留在外存上。

   缺页/段的情况：要访问的页(段) 尚未调入内存。程序应利用OS所提供的请求调页(段)功能，       将它们调入内存，使程序继续执行。

调入需要的页/段时，如果内存已满，无法再装入新页(段)，通过置换功能将内存中暂时不用的页(段)调至外存，腾出足够的内存空间。（不总驻留）

3）虚拟存储器的定义：

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

虚拟存储管理下

内存逻辑容量由内存容量和外存容量之和所决定

运行速度接近于内存速度

每位的成本却接近于外存。

4）虚拟存储器的实现

若采用连续分配方式，需申请足够空间，再分多次装入，造成内存资源浪费，并不能从逻辑上扩大内存容量。

虚拟的实现建立在离散分配存储管理基础上

方式：请求分页/请求分段系统

细节：分页/段机构、中断机构、地址变换机构、软件支持

5）虚拟存储器的特征

离散分配方式是基础

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

对换性：允许在作业的运行过程中进行换进、换出。（进程整体对换不算虚拟）

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

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

基本分页 + “请求调页”和“页面置换”功能。

换入和换出基本单位都是长度固定的页面

1）硬件支持

一台具有一定容量的内/外存的计算机+ 页表机制+ 缺页中断机构+ 地址转换机构

（1）页表基本功能不变：逻辑地址映射为物理地址

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

② 访问字段A ：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问。(置换时考量的参数)

③修改位M ：该页在调入内存后是否被修改过。(关系到置换时调出的具体操作)

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

（2）缺页中断机构

每当要访问的页面不在内存时，便产生一缺页中断通知OS，OS则将所缺之页调入内存。作为中断，需经历几个步骤：

“保护CPU环境”

“分析中断原因”

“转入缺页中断处理程序”

“恢复CPU环境”等。

作为一种特殊中断，与一般中断有明显区别：

①在指令执行期间产生和处理中断信号。

② 一条指令在执行期间，可能产生多次缺页中断。

（3）地址变换机构

2）内存分配

（1）最小物理块数的确定

少于此数量进程将不能运行

与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式

（2）物理块的分配策略

固定分配、局部置换

可变分配、全局置换

可变分配、局部置换

（3）物理块的分配算法

①平均分配算法

将所有可供分配的物理块平均分配给各进程。

缺点：未考虑各进程本身的大小，利用率不均。

②按比例分配算法

根据进程的大小按比例分配物理块。

设系统中共有n个进程

则，每个进程能分到的物理块数：

Si：进程i页面数为；S：n个进程页面数总和；m：可用物理块总数

③考虑优先权的分配算法

所有可用物理块分两部分：

一部分按比例分配给各进程；

另一部分根据各进程优先权，适当地为其增加份额，分配给各进程。

3）调页策略

（1）何时调入页面

预调页策略

请求调页策略

（2）从何处调入页面

在请求分页系统中的外存分为：

对换区：连续存放数据，读写速度较快

文件区：离散分配方式，I/O速度相对慢

发生缺页时，系统应从何处将缺页调入内存，分成三种情况：

①系统拥有足够的对换区空间：

进程运行前所有页面由文件区拷贝到对换区；

运行需要的页面全部从对换区调入内存，提高调页速度。

②系统缺少足够的对换区空间：

不会被修改的部分，在文件区操作（即：直接从文件区调入，换出时不用写入文件，再调入时仍从文件区调入）

可能被修改的部分，在对换区操作。

③UNIX方式：（随运行数据逐渐从文件区转到对换区）

未运行的页面从文件区调入；

曾经运行，但又被换出的页面放在对换区，下次调入应从对换区调入。

进程请求的共享页面可能已被其他进程调入，无需再从对换区调入。

（3）页面调入过程

程序运行前需要装入内存：上述的②步策略处理何处调入；

开始运行：先预调入一部分页面；

运行中：需要的页面不在内存时，

向CPU发出一缺页中断，“中断处理程序”开始工作：

    ①首先保留CPU环境

   ②分析中断原因后，转入缺页中断处理程序。

   ③处理：判断是否置换、页表信息更新

   ④恢复现场，重新操作页面。

3.页面置换算法

1）最佳Optimal置换算法

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

不足：无法实现，因为无法预知一进程将来的运行情况

作用：作为参照标准，评价其他算法。

2）先进先出FIFO置换算法

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

优点：实现简单，把一进程已调入内存的页面按先后次序组织成一个队列，并设置一个指针(替换指针)，使它总是指向队首最老的页面。

不足：与进程实际运行规律不相适应（较早调入的页往往是经常被访问的页，频繁被对换造成运行性能降低）

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

不足：有时页面过去和未来的走向之间并无必然的联系。

相应的需较多的硬件支持：记录每个页面自上次被访问以来所经历的时间t，淘汰时选择页面t值最大的；以及需要快速地知道哪一页是最近最久未使用的页面，用寄存器或栈。

4）CLOCK置换算法

每个页设一个使用标志位(use bit)，若该页被访问则将其置为1。

设置一个指针，从当前指针位置开始按地址先后检查各页，寻找use bit=0的页面作为被置换页。

若指针经过的页use bit=1，修改use bit=0（暂不凋出，给被用过的页面驻留的机会 ），指针继续向下。到所有页面末尾后再返回队首检查。

说明：

增加了一个使用位

当一页首次加载入内存时，该位为1，当该页被访问时，使用位也置1

当需要进行页替换时

第一个使用位为0的帧被替换，指针指向缓冲区的下一帧

循环扫描，遇到使用位为1的，变成0

改进CLOCK：

改进：主要考虑对没访问过的页面再细分是否修改过的不同情况，减少因修改造成的频繁I/O操作。

每页除记录是否用过A，还记录是否修改的标志M。置换时根据两个标志的值有4种不同情况的处理。

5）其他

（1）最少使用 (LFU, Least Frequently Used)

关键在次数记录上

每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；缺页中断时，淘汰计数值最小的页面，并将所有计数清零；

计数的实现类似LRU，用移位寄存器，但比较时不是简单比较寄存器的值，而是比较寄存器每位的和∑Ri。

（2）页面缓冲算法PBA(page buffering algorithm)

对FIFO算法的发展，弥补了FIFO可能造成的I/O开销，又不需要LRU等算法的硬件支持。

仍用FIFO算法选择被置换页

但并不将其马上换入外存。

系统将页面放入两个链表之一：如果页面未被修改，就将其归入到空闲页面链表的末尾；否则将其归入到已修改页面链表。

需要调入新的物理页面时，将新页面内容读入到空闲页面链表的第一项所指的页面，然后将第一项删除（从空闲链表摘下）。

空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，而被访问的页面可以返还作为进程的内存页。

当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表，这样能大大减少I/O操作的次数。

6）虚拟存储管理下访问内存的有效时间

7）影响缺页率的主要因素

(1)分配给作业的主存块数:

多则缺页率低，反之则高。

(2)页面大小：

大则缺页率低；反之则高。

(3)页面调度算法：

对缺页中断率影响很大，但不可能找到一种最佳算法。

(4)程序编制方法：

以数组运算为例，如果每一行元素存放在一页中，则按行处理各元素缺页中断率低；反之，按列处理各元素，则缺页中断率高。

8）抖动

（1）系统抖动：

为了提高处理机利用率，可增加多道程序并发度；

但进程数目增加过多，每个进程分配得到的物理块太少，在某个临界点上，会出现刚被淘汰的页很快又需重新调入；而调入不久又被淘汰出去；出现频繁缺页

大部分处理器时间都用在来回的页面调度上，这种局面称为系统抖动或颠簸（thrashing)

（2）抖动的后果：

缺页率急剧增加

内存有效存取时间加长，

系统吞吐量骤减；系统已基本不能完成什么任务，而是忙于页面对换操作，cpu虽然忙，但效率急剧下降。

（3）根本原因：

页面淘汰算法不合理；分配给进程的物理页面数(驻留集)太少。

（4）常用防抖动方法：

局部置换策略；

页面调入内存前检查各进程工作集，为缺页率高的增加有限物理块；

L缺页间的平均时间=S置换一个页面所需时间，可使磁盘和cpu达到最大利用率；

抖动发生时选择暂停一些进程，调节多道程序度。

（5）工作集模型的原理：

操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。

如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。

如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。

（6）驻留集

驻留(常驻)集是指在当前时刻，进程实际驻留在内存当中的页面集合。

工作集是进程在运行过程中固有的性质，而驻留集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法；

如果一个进程的整个工作集都在内存当中，即驻留集 <=工作集，那么进程将很顺利地运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）；

当驻留集达到某个数目之后，再给它分配更多的物理页面，缺页率也不会明显下降。

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

1）请求分段中的硬件支持

(1)段表机制

(2)缺段中断机构

(3)地址变换机构

2)分段的共享和保护

(1)实现共享：共享段表

(2)共享段如何分享与回收

①共享段的分配

②共享段的回收

③分段保护

a.越界检查

b.存取控制检查

c.环保护机构