虚拟内存的基本概念

虚拟内存的基本概念从四个部分来介绍，分别是：

传统存储管理方式的特点
局部性原理
虚拟内存的定义和特征
如何实现虚拟内存技术

传统存储管理方式的特征

传统存储管理方式可以分为两种：

连续分配方式：单一连续、固定分区、动态分区
非连续分配方式：基本分页、基本分段、基本段页

然而，传统存储管理方式存在下面的问题：

一次性：作业必须一次性装入内存才能运行。这就导致了大作业无法运行，以及大量的作业要求运行超出总容量的话并发性差。
驻留性：作业被装入内存后会一直驻留内存。浪费。

虚拟内存的特征和定义

描述：虚拟存储，就是要做到在用户看上来似乎有一个用不完的内存。具体来说，装入时只将很快要用到的部分装入到内存（局部性原理）；运行中，如果访问的信息不在，OS负责从外存调入内存；如果空间不足：OS负责将用不到的换出到外存。
特点：
- 多次性：无需一次装入内存，可以分为多次调入内存
- 对换性：无需一直在内存中。
- 虚拟性：逻辑上扩充了容量。

如何实现虚拟内存

虚拟内存建立在离散分配的基础上。传统的离散分配包括基本分页、基本分段、基本段页式。而虚拟内存的实现主要有三种方式：

请求分页
请求分段
请求段页式

区别：

请求调页：访问的信息不在内存时，操作系统负责将所需信息从外存调入内存。
页面置换：如果内存不够，OS负责将用不到的内存调到外存（页面置换功能）。

请求分页管理方式

请求分页和基本分页的区别：找不到就换入，不够就换出。
- 新增步骤1：请求调页
- 新增步骤2：页面置换
- 新增步骤3：需要修改页表项
硬件支持：页表机制、缺页中断机构、地址变换机构

页表机制

请求分页的页表和基本分页的页表是不同的。请求分页的页表项字段如下：

页号：都有。
内存块号：都有。
状态位：这个块是否在内存中，用于判断是否需要调入。
访问位：最近这个块访问的次数或者时间，用于判断哪些块适合换出。
修改位：脏位。页面调入是否被修改过。
外存地址：去哪里将这个块换入到内存。

缺页中断机构

流程

用户访问逻辑地址（页号 + 页内偏移）
查页表，判断页面是否存在（状态位）
1. 存在：直接返回。
2. 不存在：产生缺页中断。此时进程阻塞：加入阻塞队列，调页成功后唤醒，加入就绪队列。判断内存中是否有空闲块
  1. 有空闲块：分配一个空闲块，将页面装入该块，修改页表项。
  2. 没有空闲块：由页表置换算法选择一个页面淘汰，如果这个页面被修改过，还要将这个页面写会外存。

注意：

缺页中断是在指令执行期间发生的，所以属于内中断，也就是异常，并且是属于故障。
一条指令可能发生多次中断。

复习一下中断的类型

中断：

内中断（异常）
1. trap：系统调用
2. 故障：缺页中断
3. 终止：除法等
外中断
1. IO中断请求
2. 人工干预

机构

检查页号是否越界：如果越界产生越界中断。
查快表：
1. 命中：返回物理地址，修改访问位和修改位。
2. 页面被换出内存：要删除快表的页表项，否则会导致数据不一致。
查页表：
1. 页面不存在：
  1. 产生缺页中断，调入页面-->是否空闲-->淘汰页面
2. 页面存在：返回得到物理地址，将页表项写入到快表。

增加的步骤：

拿到物理地址后要修改访问位和修改位（写指令）。
需要使用某种【页面置换算法】
需要换入换出

问题：

换入换出都需要慢速IO，太频繁的话开销很大

页面置换算法

好的页面置换算法追求更少的缺页率，下面是五种常见的页面置换算法。

OPT
FIFO
LRU
CLOCK
改进CLOCK

最佳置换算法（OPT）

描述：每次选择淘汰的页面是以后最长时间不会使用的页面。（就是提前预知未来）
做题：既要往前看有没有空闲页面，又要往后看哪些页面最长时间不会被使用。
实际：无法实现

FIFO

描述：每次淘汰最早进入内存的页面，即每次淘汰队头页面。队列最大长度取决于系统为进程分配的内存块。
问题：会产生Belady异常。
- 何为Belady异常？按理说，为进程分配的内存块越多，缺页率应该下降。如果说分配的物理块增大时，缺页次数不减反增，就是出现了Belady异常。
- 只有FIFO会有Belady异常。

LRU

描述：最近最久未使用置换算法，淘汰最近最久未使用的页面。
做题：从这个内存块开始逆向扫描，最后一个出现的页号就是要淘汰的。
问题：性能最接近最佳置换算法。需要硬件支持。比较难实现。
软件实现：双向链表+哈希表，哈希表存储key和Node，双向链表维护Node的访问顺序。每次访问这块内存，都将这块Node移动到链表头。每次淘汰一个内存块，就是删除链表尾部。

CLOCK：时钟置换算法（NRU）

简单的CLOCK算法

CLOCK算法也叫做NRU算法，意思是最近未用算法。

思路：

设置访问位：每个页面设置一个访问位，将内存中的页面通过指针链接为一个循环队列。当一个页面被访问时，就设置访问位=1。
淘汰策略：指针扫一遍的时候会检查访问位，如果访问位=0，就换出这个页面。如果访问位=1：将访问位设置为0，暂时不换出，继续检查下一个页面。**淘汰一个页面最多经过两轮扫描**

改进的CLOCK算法

简单CLOCK的问题：

仅仅考虑到一个页面最近是否被访问过。
没有考虑到页面是否被修改过，实际上应该优先淘汰没有被修改过的页面

算法：

状态表示：用(访问位,修改位)表示各个页的状态。
- (0,0)：最近没被访问，也没被修改。最佳淘汰页面。
- (0,1)：最近没被访问，但是被修改了。不是很好的淘汰页。
- (1,0)：最近被访问了，没被修改。
- (1,1)：最近被访问了，也被修改了。
扫描算法：
- 第一轮扫描：扫描到第一个(0,0)，如果遇到了就淘汰，不修改标志位。
- 第二轮扫描：扫描到第一个(0,1)，如果遇到就淘汰，同时将所有访问过的访问位设为0
- 第三轮扫描：扫描到第一个(0,0)，不修改任何标志位。
- 第四轮扫描：扫描到第一个(0,1)，一定能找到需要淘汰的页面。
可见，淘汰一个页面，最多扫描四轮。

页面分配和置换策略

驻留集

驻留集：请求分页中给进程分配的物理块的集合。

一般驻留集<进程总大小
太小：缺页频繁
太大：并发度下降，资源利用率低。

分配策略：

固定分配：驻留集大小不变
可变分配：驻留集大小可变

置换策略：

全局置换：缺页时选择自己进程的物理块。
局部置换：缺页时可以选择其它进程持有的物理块。

没有固定分配局部置换这个组合。

页面分配、置换策略

固定分配局部置换：
- 描述：系统开始为进程分配物理块，运行期间都不变。如果缺页只能在物理块中选一个换出。
- 缺点：很难开始就确定分配多少物理块合理。
可变分配全局置换：
- 描述：系统开始分配一定数量物理块，维护空闲物理块队列，缺页的时候从空闲队列中选出块分配到进程；如果没有空闲物理块，选择一个未锁定的页面换出外存，然后将这个物理块分配给进程。
- 特点：只要进程发生缺页，都将能够得到新的物理块。被选中的物理块可能是系统中任意一个进程的物理块，它的缺页率会增加。
可变分配局部置换：
- 描述：开始分配一定物理块，缺页时只能从自身的物理块选一个换出。如果进程频繁缺页，系统会为该进程多分配几个物理块，直到缺页率达到适当的程度。反之，系统缺页率特别低的话，会适当减小分配给进程的物理块
- 特点：动态调整。

何时调入页面

预调页策略：空间局部性原理，一次调入若干个相邻的页面。
1. 缺点：如果调入的页面大多数没访问，就很低效。
2. 应用：主要用于进程首次访问（运行前调入）
请求调页策略：
1. 运行时调入：运行期间发现缺页时才将所缺页面调入内存。
2. 缺点：IO开销比较大。

何处调入页面

对换区：读写速度更快，连续分配方式。
文件区：读写速度慢，离散分配方式。

对换区足够：

描述：如下图所示，页面调入和调出都是和对换区之间进行，速度很快。
注意：进程运行前，需要将相关的数据从文件区复制到对换区。

对换区不足：

不会被修改的数据：直接从文件区调入。
可能会被修改的数据：换出时写入对换区，下次从对换区调入。

Unix的方式：

运行之前，进程有关的数据都放在文件区。第一次调入从文件区调入。
若被使用过的页面需要换出，则写回对换区，下次从对换区调入。

抖动

工作集：某段时间间隔内，进程实际访问的页面集合。

概念：频繁页面调度，即刚换出的页面马上又要换入内存，刚换入马上又要换出内存。
主要原因：进程频繁访问的页面数量 > 可用的物理块数，即为进程分配的物理块太少
解决：一般来说，驻留集应该大于工作集，否则会频繁缺页。

内存映射文件

什么是内存映射文件

文件可能被离散存放在磁盘的各个角落。

传统的文件访问方式：

open：打开文件
seek：将读写指针移动到某个位置
read：从读写指针所指位置读取多少字节。
write：将内存中的指定数据写回磁盘

内存映射文件：

open：打开文件
mmap：将文件映射到进程虚拟地址空间，返回指向映射内存区域的起始地址
- 使用访问内存的方式访问文件数据
- 访问内存过程中发生缺页异常，OS会自动将某块数据读入到内存中。但是不需要程序员手动调用read函数
文件的读入写出由OS自动完成
进程关闭文件后，OS自动将文件被修改的数据写回磁盘

多个进程可以映射同一个文件，实现共享。