虚拟存储管理

1.虚拟存储器概述

1.1常规存储管理方式的特征和局部性原理

1.常规存储器管理方式的特征：(1)一次性 (2)驻留性

2.局部性原理:
①定义：指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域中
②分类：
时间局部性(被访问过一次的存储器位置很可能在不远的将来再被多次访问，循环结构)
空间局部性(如果一个存储器位置被访问了一次，那么程序很可能在不远的将来访问附近的一个存储器位置，顺序结构/大数组)

3.虚拟存储器的基本工作情况
- 所谓虚拟存储技术是指：当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作

- 虚拟地址空间 即为 分配给进程的虚拟内存

- 虚拟地址 是 在虚拟内存中指令或数据的位置，该位置可以被访问，仿佛它是内存的一部分

1.2虚拟存储器的定义与特征

以 CPU 时间和磁盘空间换取昂贵内存空间，这是操作系统中的资源转换技术

1.虚拟存储器的定义

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

• 其容量接近于外存，其运行速度接近于内存速度，而每位的成本却又接近于外存

在虚存管理中:
①虚拟地址空间是指逻辑地址空间，实地址空间是指物理地址空间
② 前者的大小受 CPU 可寻址范围(机器地址长度)的限制，而后者的大小受物理内存大小的限制

2.虚拟存储器的特征

• 离散性：在分配内存时采用离散分配方式

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

• 对换性：允许在作业的运行过程中进行换进、换出

• 虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量(虚拟性以多次性和对换性为基础；多次性和对换性以离散分配为基础。)

1.3虚拟存储器的实现方法

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

2.1请求分页存储管理方式基本思想

基本思想：请求分页=分页+请求

逻辑空间分页 物理空间分块

页与块同样大 页连续块离散

用页号查页表 硬件做重定位

请求分页的基本思想:

（1）作业部分装入内存
（2）作业所占的内存块不连续
（3）硬件通过页表生成访问内存的地址
（4）若发生缺页，则进行缺页中断处理，将该页调入内存
（5）利用快表可以加速地址转换

请求分页式虚拟存储
硬件支撑：硬件（主存管理单元 MMU）
主要任务：将逻辑地址转换为物理地址

功能:

管理硬件页表基址寄存器

分解逻辑地址

管理快表

访问页表

发出缺页中断或越界中断，并将控制权交给内核存储管理处理

• 设置和检查页表中各个特征位

2.2请求分页中的硬件支持

1.页表机制

2.缺页中断(异常)

• 是一种 Page Fault；

• 在地址映射过程中，硬件检查页表时发现所要访问的页面不在内存，则产生该异常——缺页异常；

• 操作系统执行缺页异常处理程序，获得磁盘地址，启动磁盘，将该页调入内存：

  ①如果内存中有空闲页框，则将新页调入，并修改页表项的有效位、访问位及页框号

  ②若内存中没有空闲页框，则要置换内存中某一页框；若该页框内容被修改过，则要将其写回磁盘。

• 缺页中断与一般中断的区别：
  （1）缺页中断是在执行一条指令中间时产生的中断，并立即转去处理。而一般中断则是在一条指令执行完毕后，当发现有中断请求时才去响应和处理
  （2）缺页中断处理完成后，仍返回到原指令去重新执行，因为那条指令并未执行。而一般中断则是返回到下一条指令去执行，因为上一条指令已经执行完毕了

3.缺页中断处理过程

①根据当前执行指令中的虚拟地址，形成数对：（页号，页内位移）。用页号去查页表，判断该页是否在内存

②若该页的状态位为“0”，表示当前该页不在内存，于是产生缺页中断，让操作系统的中断处理程序进行中断处理

③中断处理程序去查存储分块表，寻找一个空闲的内存块；查页表，得到该页在辅助存储器上的位置，并启动磁盘读信息

④把从磁盘上读出的信息装入到分配的内存块中

⑤根据分配存储块的信息，修改页表中相应的表目内容，另外，还要修改存储分块表里相应表目的状态

⑥由于产生缺页中断的那条指令并没有执行，所以在完成所需页面的装入工作后，应该返回原指令重新执行。这时再执行时，由于所需页面已在内存，因此可以顺利执行下去

4.地址变换机构

5.地址转换过程

6.请求分页存储管理优缺点
优点:
①按页分散存放在内存中，减少移动开销
②有利于改进主存利用率
③部分装入，有利于多道程序运行
缺点:
①需要硬件支持进行缺页中断处理，成本增加，开销加大
②存在页内碎片

2.3内存分配策略和分配算法

2.4调页策略

3.页面置换算法

用途:用于页淘汰、段淘汰、块表淘汰

3.1最佳置换算法和先进先出置换算法

1.最佳置换算法—理想化

最佳置换算法是由 Belady 于 1966 年提出的一种理论上的算法。其所选择的
被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的
页面。采用最佳置换算法，通常可保证获得最低的缺页率

2.先进先出页面置换算法

①该算法的出发点是最早调入内存的页面，其不再被访问的可能性会大一些

②该算法实现比较简单(队列)，对具有线性顺序访问的程序比较合适，而对其他情况效率不高。因为经常被访问的页面，
往往在内存中停留最久，结果这些常用的页面却因变老而被淘汰

③先进先出算法存在一种异常现象，即在某些情况下会出现分配给的进程物理块数增多，缺页次数有时增加，有时减少
的奇怪现象，这种现象称为 Belady 现象

Belady 异常：随着物理块数的增多缺页率可能增大

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

3.3Clock置换算法-LRU的近似算法

3.4其他置换算法

4."抖动"与工作集

4.1"抖动"与工作集的基本认知

抖动 thrashing：刚刚被换出的页面很快又要用到，CPU 忙于调出和调入页面。
根本原因：页面淘汰算法不合理；分配给进程的物理页面数(驻留集)太少。

防止抖动发生的方法：

(1)挂起某些进程-调节多道程序度。

(2)采用局部置换策略。

(3)L=S 准则(产生缺页的平均时间等于系统处理缺页的平均时间。

(4)利用工作集策略防止抖动。

工作集概念：
工作集：一个进程当前正在使用的逻辑页面集合，可以用一个二元函数 W(t, Δ)来表示：

①t是当前的执行时刻；

②Δ称为工作集窗口（working-set window ），即一个定长的页面访问窗口

③W(t, Δ)＝在当前时刻 t 之前的Δ窗口当中的所有页面所组成的集合（随着 t 的变化，该集合也在不断地变化）

④| W(t, Δ) | 指工作集的大小，即页面数目

驻留集概念:

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

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

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

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

缺页率与驻留集的关系：

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

5.1请求分段中的硬件支持

1.段表机制

2.缺段中断机构

3.地址变换机构

5.2分段的共享与保护

1.共享段表

2.共享段的分配和回收
(1)分配:
第一次访问：分配内存 ①增加共享段 ②修改进程段表
第二次访问：①修改共享段表 ②修改进程段表

(2)回收: ①count=0 ②count< >0

5.3环保护机构