Version: Next

虚拟存储技术

属于 内存空间扩充 技术

  • 覆盖
  • 交换
  • 虚拟存储技术

传统存储方式的特征与缺点

  • 一次性：作业必须一次性全部装入内存后才能开始运行
    • 问题：
      1. 作业很大时，不能全部装入内存，导致大作业无法运行
      2. 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降
  • 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束
    • 问题：
      1. 事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，驻留性导致内存中驻留大量、暂时用不到的数据，浪费了宝贵的内存空间

局部性原理

时间局部性

  • 如果执行了程序中的某条指令，那么很有可能在不久之后再次执行这些指令；对于数据同理

空间局部性

  • 一旦程序访问了某个存储单元，不久之后，其附近的存储单元也很可能被访问

高速缓存技术

  • 将近期频繁访问的数据放到更高速的存储器中，暂时用不到的数据存放到低速存储器中
  • 对应 CPU 内部寄存器 -> L1、2、3 级 Cache 缓存 -> 物理内存 （内存条）-> 外存机械硬盘/SSD

虚拟内存的定义与特征

定义

  • 基于局部性原理，在程序装入时，可以将程序中 很快会用到的部分装入内存，暂时不用的部分留到外存，就可以让程序开始执行
  • 在程序执行过程中，当所访问的信息不在内存时，由 操作系统负责将所需的信息从外存调入内存，然后继续执行程序
  • 若内存空间不够，由 操作系统负责 将内存中 暂时不用的信息换出到外存
  • 在操作系统的管理下，在用户看来似乎有一个远比实际物理内存大的 “内存”，这就是 虚拟内存
易混淆知识点
  • 虚拟内存的 最大容量 是由计算机的地质结构（CPU 寻址范围）确定的
    • 32位计算机 4GB
    • 64位计算机 128GB
  • 虚拟内存的 实际容量 = min(物理内外存容量之和, CPU 寻址范围)
  • 例：某计算机地址结构 32位，按字节寻址，内存大小 512MB，外存大小 2GB
    • 虚拟内存最大容量为 2^32 = 4GB
    • 虚拟内存实际容量= min(2^32, 512MB + 2GB) = 2GB + 512MB

虚拟内存的三个主要特征

  1. 多次性：无需作业运行时一次全部转入内存，而是允许被分成多次调入内存（与 一次性 对立）
  2. 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出 （与 驻留性 对立）
  3. 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际物理内存容量

虚拟内存技术的实现

需要建立在 离散分配 内存管理方式上

  • 请求分页存储管理
  • 请求分段存储管理
  • 请求段页式存储管理

与传统非连续分配存储管理的主要区别

  1. 由操作系统负责，将不常用的信息换出到外存
  2. 由操作系统负责，将即将用到的信息从外存调入内存

结论：操作系统需要提供 请求调页 （请求调段）功能；页面置换（段置换）功能

请求分页管理方式

请求分页 存储管理与 基本分页 存储管理的主要区别

  • 添加 调入、换出 功能

页表机制

与基本分页管理相比

  • 为了实现 请求调页 ，需要知道 每个页面是否已经调入内存
    • 如果没调入：需要知道页面存储在外存中的位置
  • 为了实现 页面置换，需要通过某些指标决定换出哪个页面
    • 未被修改过的页面：不用浪费时间写回外存
    • 被修改过的页面：需要将外存中的旧数据覆盖
    • 因此：操作系统需要几率各个页面是否被修改过的信息
  • 请求分页管理方式下的 页表结构，一般称为 请求页表
    • 状态位：标记页面是否已调入内存 （对应下文 缺页）
    • 访问字段：记录最近被 访问过几次，或记录 上次访问时间，供置换算法选择换出页面时参考（对应 LRU 置换算法）
    • 修改位：标记页面调入内存后是否被修改过
页号（隐含）内存块号状态位（是否已调入内存）访问字段修改位外存地址
0b1100y

缺页中断机构

  • 缺页：当要访问一个页面时，发现它当前不在内存中（没调入）
  • 这种情况下，会产生一个 缺页中断，接着操作系统的 缺页中断处理程序 处理中断
  • 此时 缺页进程阻塞，加入阻塞队列，调页完成后将其唤醒，放回就绪队列
  • 调入：如果此时内存中 有空闲块，则为进程 分配一个空闲块，将所缺页面装入该块，并修改也表中响应的页表项
  • 置换：如果此时内存中 没有空闲块，则 由页面置换算法选择一个页面淘汰，若该页面在内存期间 被修改过，则要将其写会外存；若未曾修改过，则不用写会外存，直接淘汰即可

地址变换机构

新增步骤

  1. 请求调页：需要先根据页表项的 状态位 判断页面是否已经被调入内存
  2. 页面置换：当需要将页面从外存调入内存时，没有空闲的内存块时进行
  3. 需要维护页表中的数据

快表

  • 如果快表 命中，说明对应页面一定已经调入内存
  • 若某个页面要被置换出内存，则相应的快表记录必须删除

页置换算法 *

用于决定被置换到外存的具体内存块的算法——追求最低缺页率

  • 最佳置换算法 OPT
  • 先进先出置换算法 FIFO
  • 最近最久未使用置换算法 LRU
  • 时钟置换算法 CLOCK
  • 改进型时钟置换算法

最佳置换算法 OPT

OPT：Optimal

  • 每次选择 淘汰的页面 将是 以后永不使用 或 在最长时间内不会再被访问的页面，这样可以保证最低的缺页率

例：假设系统为某进程分配了 3 个内存块，考虑到有以下页面号访问串：7 0 1 2 0 3 4 2 3 0 3 2 1 2 0 1 7 0 1

  • 访问完 7 0 1，内存已经满了，需要置换，那么 7 0 1 置换谁出去，根据 OPT 的思想，要求计算机 未卜先知，看一下后面的调用串，显然 最远 会被调用的是 下一个7，所以把 7 换出去，把 7 的位置给调入的 2
  • 根据下表可知：整个过程 缺页中断 9 次，页面置换 6 次，缺页率 = 9 / 20 = 45%
  • 缺页中断未必发生页面置换，只有分配给进程的内存块已经全部满了，才会进行页面置换
访问页面7012030423032120170
内存块1777222227
内存块200004000
内存块31133311
是否缺页是是是是是是是是是
  • 优点：理论最低缺页率
  • 缺点：要未卜先知，根本没法实现

先进先出置换算法 FIFO

每次选择 淘汰的页面 是 最早进入内存的页面

  • 实现：把调入内存的页面根据调入顺序弄成一个队列，需要换出时，把队头页面弹出即可；队列的最大长度取决于系统为进程分配了多少个内存块

  • 3个内存块：3 2 1 0 3 2 4 3 2 1 0 4

访问页面321032432104
内存块1333000444
内存块222233311
内存块31112220
是否缺页是是是是是是是是是
  • 缺页 9 次，置换 6 次，缺页率 = 9 / 12 = 75%
  • 4 个内存块，相同序列
访问页面321032432104
内存块13330444400
内存块2222233334
内存块311112222
内存块40000111
是否缺页是是是是是是是是是是
  • 缺页 10 次，置换 6 次，缺页率 10 / 12 = 83.3%
  • 增加了内存块，缺页次数却增加了：Belady 异常，只有 FIFO 算法会产生 Belady 异常
  • FIFO 算法虽然 实现简单，但是该算法与进程实际运行规律不适应，因为先进入的页面通常是最可能被经常访问的（局部性原理），因此 FIFO 算法性能差

最近最久未使用置换算法 LRU *

Least Recently Used：每次淘汰的页面是最近最久未使用的页面

  • 实现：哈希表 + 双向量表 （看算法笔记）
  • 在 页表 的 访问字段 中几率上次访问时间
  • 4 个内存块，序列 1 8 1 7 8 2 7 2 1 8 3 8 2 1 3 1 7 1 3 7
访问页面1817827218382131713
内存块11131111
内存块288887
内存块37733
内存块4222
是否缺页是是是是是是
  • 缺页 6 次，置换 2 次，缺页率 6 / 20 = 30%
  • 实际实现需要专门硬件支持，虽然算法 性能好，但是 实现比较困难，开销大
  • 性能最接近最佳置换算法的算法

时钟置换算法 CLOCK （NRU）

一种性能、开销较均衡的算法，又称 CLOCK 算法，或最近未用算法 NRU Not Recently Used

  • 根 CPU 时钟没关系

  • 为 页表 中的 页表项 设置 访问位

    • 访问位：1 表示最近访问过、0 表示最近未被访问过

  • 再将内存中的页面通过 链接指针链接成一个 循环队列，当某页面被访问时，将其 访问位 设置为 1

  • 当需要淘汰一个页面时，只需 检查 页的 访问位

    • 0：就选择该页换出
    • 1：不换出，但将其设置为 0

  • 继续检查下一个页面，若第一轮扫描中所有页面都是 1，则将这些页面访问后依次置 0，在进行第二轮扫描

    • 第二轮扫描中，一定有 访问位 = 0 的页面
    • 因此：简单 CLOCK 算法选择淘汰的页面最多会经过 2 轮扫描
    • 在循环队列上循环的过程，就像一个 时钟

改进型时钟置换算法

优化思路

  • 如果置换的页面 未被修改过，则不需要写会外存进行更新，可以减少 I/O 操作
  • 想办法实现：优先淘汰未被修改过的页面
  • 实现：为各个页面增加 修改位，和 访问位 进行配合
    • 修改位 = 0 ： 页面没被修改
    • 修改位 = 1 ： 页面被修改过
  • 以 (访问位，修改位) 的格式表示这两个位上的数值，如 (1, 1) 表示一个页面最近被访问过，且最近被修改过
    • 算法规则：所有可能被置换的页面排列成一个 循环队列，
    • 第一轮：从当前位置开始扫描到第一个 (0, 0) 的页面用于替换，本轮扫描不修改任何标志 （试图置换 最近没访问，也没修改过的页面）
    • 第二轮：若第一轮扫描没找到 (0, 0)，则重新扫描，查找第一个 (0, 1) 页面用于替换，本轮将所有扫描的页面 访问位 设为 0 （试图置换 最近没访问，但修改过的页面）
    • 第三轮：如果第二轮没找到 (0, 1)，则重新扫描，查找第一个 (0, 0) 的页面用于替换，本轮扫描不修改任何标志位 （试图置换 最近访问过，但没修改的页面）
    • 第四轮：若第三轮扫描没找到 (0, 0)，则重新扫描，查找第一个 (0, 1) 的页面用于替换；由于第二轮扫描已经将所以页面的访问位修改为 0，因此第三、四轮扫描中一定会有页面被选中，因此 改进型 CLOCK 置换算法选择一个淘汰页面最多会进行 4 轮扫描 （试图置换 最近访问过，且修改过的页面）
  • 心法：以访问位为主，修改位为辅
  • 心法：总是试图先找一个 (0, 0) 置换，是在找不到就找 (0, 1)
算法规则优缺点
OPT优先淘汰最长时间不会被访问的页面缺页率最小，性能最好；无法实现
FIFO优先淘汰最先进入内存的页面实现简单；性能差，可能出现 Belady 异常
LRU优先淘汰最近最久没访问的页面性能很好；需要硬件支持，算法开销大
CLOCK (NRU)循环扫描各页面
第一轮淘汰 访问位=0，并将扫描过的页面 访问位=1；若第一轮没选中，则进行第二轮扫描		实现简单，算法开销小；未考虑页面是否被修改过
改进型 CLOCK用 (访问位, 修改位) 表示
第一轮：尝试淘汰（0, 0）
第二轮：尝试淘汰（0, 1），并将访问过的页面的设置为 (0, X)
第三轮：尝试淘汰（0, 0），（原本是 (1, 0) 上一轮被置成 (0,0) 了）
第四轮：尝试淘汰（0, 1） （原本是 (1,1) 第二轮被置成 (0, 1) 了）		算法开销较小，性能较好

页面分配策略

驻留集

  • 请求分页存储管理中，给 进程 分配的 内存块 的 集合

页面分配、置换策略

在采用虚拟存储技术的系统中，驻留集大小一般小于进程的总大小

  • 驻留集太小：导致频繁缺页，处理缺页耗费资源
  • 驻留集太大：导致并发度下降

页面分配：需要选择合适的驻留集大小

  • 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变，即 侏罗纪大小不变
  • 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少，即 驻留集大小可变

置换策略：页面置换的范围

  • 局部置换：发生缺页时，只能选进程自己的物理块进行之魂啊
  • 全局置换：可以将操作系统保留的空间物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程
局部置换全局置换
固定分配√不存在
全局置换意味着一个进程拥有的物理块必然会改变，因此不可能固定分配
可变分配√√

固定分配局部置换

  • 系统为每个进程分配一定数目的物理块，在整个运行期间不变 （固定分配）
  • 若进程在运行中 缺页，则只能从该进程在内存中的页面中选出一页换出，再调入新页面 （局部替换）
  • 缺点：很难在刚开始就确定应为每个进程分配多少个物理块才合理
    • 采用这种策略的系统可以根据进程大小、优先级、或程序员经验给出的参数确定一个进程分配的内存块数

可变分配全局置换

  • 刚开始会为每个进程分配一定数量的物理块
  • 操作系统会保持一个 空闲物理块队列，当某进程发生 缺页，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个 未锁定 的页面换出 （可变分配）
  • 只要某进程发生了缺页，都能获得新的物理块，仅当空闲物理块用完时，系统才会选择一个 未锁定 的页面调出
    • 锁定：系统会锁定一些页面，这些页面中的内容 不能被置换出外存（如重要的内核数据等）
  • 被选择调出的页面可能是系统中任何一个进程中的页，因此这个 被选中的进程拥有的物理块会减少，缺页率会增加 （全局置换）

可变分配局部置换

  • 开始时，为每个进程分配一定数目的物理块，如果进程频繁 缺页，则系统会为该进程对分配几个物理块，直至该进程缺页率趋于适当程度；反之如果进程在运行中缺页率很低，可以适当缩减分配给该进程的物理块 （可变分配）
  • 当某进程发生 缺页 时，只允许从该进程自己的物理块中选出一个进行换出外存 （局部置换）
对比
  • 可变分配 全局 置换：只要缺页就分配新物理块
  • 可变分配 局部 置换：要根据发生 缺页的频率 来动态的增加、减少进程的物理块

调入页面的时机

预调页策略

  • 根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效
  • 但，如果提前调入的页面中大多数没有被访问过，又是低效的
  • 可以预测不久之后可能访问到的页面，将他们预先调入内存，但目前预测成功率只有 50% 左右
  • 这种策略 主要用于进程首次调入，由程序员指出应先调入哪些部分 （因为不好预测，所以用在那些可以准确预测的场景）（运行前调入）

请求调页策略

  • 进程 在运行期间发现缺页时才将所缺页面调入内存 （运行时调入）
  • 这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而且每次都要进行 IO 操作，因此 IO 开销大

从何处调页

  1. 优先使用磁盘 对换区，因为对换区比较快
  2. 对换区空间不足：凡是不会被修改的数据都从 文件区 调入，因为它们不会被修改，因此不需要写回磁盘；如果需要修改，则会涉及后续写回磁盘 对换区
  3. UNIX 方式： 运行前，全部放在 文件区，第一次调入内存后，写回时写回到 对换区 下次使用时从 对换区 换入

抖动（颠簸）现象

  • 刚换出的页面，立马又要换入内存；刚换入的页面，立马又要换出外存，这种频繁的页面调度行为成为 抖动、颠簸
  • 产生抖动的 主要原因 是进程频繁的访问的页面数目高于可用的物理块数 （分配给进程的物理块不够）
  • 通过 工作集 解决

工作集

  • 驻留集：指请求分页存储管理中给进程分配的内存块的集合
  • 工作集：指在某段时间间隔内，进程实际访问的页面的集合

操作系统会根据 窗口尺寸 来算出工作集

例：某进程的页面访问序列如下，窗口尺寸4，各时刻的工作集为？

24 15 18 23 24 17 18 24 18 17 17 15

  • 若当前访问 23 则看之前的 4 个家伙（包括自己），就是 24 15 18 23
  • 若当前访问的 倒数第三个 17，则工作集为 18 24 17
  • 工作集大小 可能小于窗口尺寸，实际中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块
  • 如：窗口尺寸为 5，经过一段时间监控发现某进程的工作集最大为 3，那么说明该进程具有很好的局部性，可以给这个进程分配 3 个以上的内存块即可满足进程的运行需要
  • 一般来说，驻留集大小不能小于工作集大小，否则进程运行该过程中将频繁缺页
拓展

基于局部性原理可知，进程在一段时间内访问的页面与不久之后会访问的页面时相关的，因此可以根据进程近期访问的页面集合（工作集）来设计一种页面置换算法——选择一个不再工作集中的页面进行淘汰