一. 虚拟内存基本概念
传统存储管理方式
传统内存管理策略都是为了将多个进程保存在内存中，以便允许进行多道程序设计。它们都有以下共同特征：
- 一次性：作业必须一次性全部装入内存后，才能开始运行。会导致以下两个问题：
- 作业过大而无法装入内存，导致无法运行。
- 大作业运行时，由于无法容纳所有作业，降低多道程序的并发性。
- 驻留性：作业装入内存后，一直驻留内存，任何部分都不会被换出，直到作业运行结束。
- 运行中的进程可能会因为等待 I/O 而被阻塞，可能处于长期等待状态。
- 可能只需要访问作业的一小部分数据就可以运行，大量用不到的数据驻留内存，浪费了内存资源。
局部性原理
- 时间局部性：程序中的某条指令短时间内被多次执行 或 某个数据短时间内被多次访问。
- 产生原因：代码中的循环指令。
- 空间局部性：程序访问某个存储单元后，短时间内其附近的存储单元也被访问。
- 原因：指令的顺序存放，顺序执行 / 数据以向量，数组，表等形式簇存储。
虚拟技术实际上建立“内存——外存”两级存储结构，利用局部性实现高速缓存。
虚拟存储器的定义和特征
- 定义：基于局部性原理，程序仅将少数页面（或段）装入内存，其余部分暂留外存。
【请求调用页/段功能：】程序执行时，OS 负责将所需要的在外存的访问信息调入内存，接着程序继续执行。
【页面/段置换功能】当内存空间不够，OS 负责将暂时用不到的信息换出内存，为外存信息调入腾出空间；
这样，OS 就好像提供了一个比实际内存容量大得多的存储器，称为虚拟存储器。
- 特征：
- 多次性。作业运行时无需全部调入内存，允许在运行时多次调入。
- 对换性。作业无需常驻内存。将暂时不用的程序和数据调出至外存的对换区（换出），需要时再从外存调入内存。（换入）
- 虚拟性。逻辑上扩充了内存容量，使用户看到的内存容量远大于实际容量。
虚拟内存技术的实现
虚拟内存技术采用多次调入方式，如果使用连续分配方式，会使得相当一部分内存空间暂时或 “永久”处于空闲状态，极大地浪费了内存空间。
因此，虚拟内存技术需要建立在离散分配的内存管理方式上。
实现方式：
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
一般需要的硬件支持方面：
实现方式：
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
一般需要的硬件支持方面：
建立在基本分页系统基础之上，增加请求调页和页面置换功能。需要有页表机制、缺页中断机构和地址变换机构等。
页表机制
新增四个字段：
- 状态位 P：标记是否调入内存
- 访问字段 A：标记本页近段时间的访问次数
- 修改位 M：表示调入内存后是否曾被修改
- 外存地址：记录该页在外存存放的地址。通常是物理块号。
缺页中断机构
缺页中断：当想要访问的页面不存在内存时，就会产生缺页中断，请求 OS 的缺页中断处理程序处理。此时缺页的进程阻塞，调页完成后唤醒。
- 若内存有空闲页框，直接为进程分配一个，然后将所需页面调入，并修改页表相应表项。
- 若内存没有空闲页框，使用页面置换算法淘汰一个页面。
- 若该淘汰页面被修改过，则需要写回外存。否则不需要。
地址变换机构
步骤：
- 检索快表
快表命中。从相应表项取出该页物理块号，修改页表项的访问位。【对于写指令，还需要将修改位置 1】
快表未命中。查询页表。
页表找到。从相应表项取出该页物理块号，将该页表项写入快表。若快表已满，需要采用替换算法进行对换，并删除换出快表的页表项。
页表未找到。进行缺页中断处理，请求系统将该页从外存换入内存，页面调入内存后，OS 更新页表和快表，并获得物理块号。
- 利用得到的物理块号与页内地址拼接形成物理地址，用该地址访存。
流程图如下：
三. 页框分配
驻留集大小
驻留集：OS 给一个进程分配的页框集合。
- 驻留集小：进程数量多，提高多道程序并发性；但分配给每个进程的页框数量太少，导致缺页概率提高，CPU 会花费大量时间处理缺页。
- 驻留集大：分配给进程的页框超过某个数量时，再增加页框对缺页率的改善不大，并且会浪费内存空间，导致多道程序并发度下降。
内存分配策略
请求分页系统中，两种内存分配策略：固定分配策略，可变分配策略；两种置换策略：全局置换，局部置换。
- 固定分配局部置换
- 进程分配固定数目的物理块；
- 进程缺页时，只能从分配给该进程再内存的页面中选出一页换出，然后调入一页，以保证分配给该进程的内存空间不变。
- 难以确定分配给进程的物理块数目。太少：频繁缺页中断；太多：降低 CPU 和其他资源的利用率。
- 可变分配全局置换
- 先为进程分配一定数量的物理块，进程运行期间动态增加或减少。
- 缺页时，系统从空闲物理块队列取出一块分配给该进程，并调入所缺页。
- 优点：比固定分配局部置换更灵活，动态增减进程物理块。
- 缺点：如果它盲目增加物理块，会降低系统多道程序的并发能力。
- 可变分配局部置换
物理块调入算法
采用固定分配策略时，空闲物理块分配给各个进程的算法：
- 平均分配算法：系统中所有空闲物理块平均分配给各个进程。
- 按比例分配算法：根据进程大小按比例分配物理块。
- 优先权分配算法：为重要紧迫的进程分配较多物理块。通常将物理块分成两部分，一部分按比例分配，另一部分根据优先权。分配
调入页面的时机
- 预调页策略：根据局部性原理，预测可能用到的页面，但目前成功率仅 50% ,因此主要用于进程首次调入，由程序员指出先调入哪些页。
- 请求调页策略：访问页面不存在，发出请求调入。易于实现，但通常每次仅仅调入一页，增加了磁盘 I/O 开销
何处调入页面
请求分页系统的外存分为两部分：
- 文件区：用于存放文件。采用离散分配方式。
- 对换区：用于存放对换页面，也称交换区。采用连续分配方式，因此磁盘 I/O 速度更快。
系统从何处将缺页调入内存：
- 系统拥有足够的对换空间
- 可以全部从对换区调入，以提高调页速度。
- 为此，进程运行之前，需要将与进程有关的文件从文件区复制到对换区。
- 系统缺少足够的对换空间
- 不会被修改的文件从文件区调入；当换出这些页面时，由于它们不会被修改而不必再换出；
- 对于可能被修改的部分，换出时必须放在对换区，以后需要再从对换区调入（由于 V读 > V写）
- UNIX 方式
- 与进程有关的文件都放在文件区。
- 运行过之后被换出的放在对换区。
进程请求的共享页面若被其他进程调入内存，则不必再次从对换区调入。
如何调入页面
- 内存未满
- 启动磁盘 I/O，缺页调入内存并修改页表。
- 内存已满
- 使用置换算法换出一页。
- 若换出页面被修改过：写回磁盘，缺页调入内存，修改页表项，置存在位为 1。
- 换出页码未被修改过：缺页调入内存，修改页表项，置存在位为 1
四. 页面置换算法
最佳（OPT）置换算法
- 原理：淘汰“以后永不使用”（或最长时间内不再访问）的页面。
- 缺点：由于人们无法预测进程会使用哪个页面，因此该算法无法实现。
先进先出（FIFO）置换算法
- 原理：将内存中页面按照调入顺序排为队列，发生对换时，淘汰队头（即最先调入内存的）页面。
最近最久未使用（LRU）置换算法
- 原理：淘汰最近最长时间未使用的页面。每个页面设置访问字段，记录从上次访问后经历的时间，将访问字段最大的页面对换出去。
时钟（CLOCK）置换算法
简单的 CLOCK 置换算法
- 原理：根据访问位 A，首次装入页面或被访问时，A=1；
- 算法将内存中页面链接成一个循环队列，并设置一个替换指针。
- 顺序查找替换页面，对 A=1 的页面将访问位置 0，给该类页面二次驻留内存的机会。 将 A=0 的页面被替换出来。
如果首次查找内存中所有页面访问位均为 1，则一次查找结束都为 0，第二轮查找指向页面即为替换页面。也称最近未使用（NRU）算法。
改进型 CLOCK 置换算法
- 原理：针对访问位 A 和修改位 M，产生以下四种页面。替换优先级从高到低依次排布：
A=0，M=0：最近未被访问，且未被修改，最佳淘汰页面。
A=0，M=1：最近未被访问，但已被修改，次佳淘汰页面。
A=1，M=0：最近已被访问，但未被修改，可能再次被访问。
A=1，M=1：最近已被访问，且已被修改，可能再次被访问。
原因：替换修改过的页面需要写回磁盘，置换代价更大。
算法总结对比
五. 抖动和工作集
- 抖动：页面置换过程中，发生刚换出的页面又被调入内存（需要访问）的现象，这种频繁的页面调入行为称为抖动或颠簸。
成因：分配给进程的物理块数量过少，不能满足进程基本运行的要求。
- 工作集：某段时间内，进程要访问的页面的集合。
六. 内存映射文件
- 定义：内存映射文件（Memory-Mapped Files）是 OS 向应用程序提供一个系统调用，在磁盘文件与进程的虚拟地址空间之间建立映射关系。
- 特点
类似大字符数组，避免直接文件I/O操作。
OS 负责磁盘文件读写，对进程透明。
映射时仅映射地址，实际内容按需读取。
修改内容在进程退出或关闭映射时写回文件。进程间可通过映射相同文件至虚拟地址空间实现共享内存通信。各进程虚拟地址独立，但操作系统通过页表映射至相同物理内存。一进程写操作后，另一进程读取即可见前者修改结果。
- 优点：
- 使程序员编程更简单。已建立映射的文件只需要按照访问内存的方式进行读写。
- 方便多个进程共享同一个磁盘文件。
