虚拟存储概念

虚拟存储

  • 概念：基于非连续存储内存分配的基础上，可以把一部分内训放在外存里
  • 需求
    • 计算机系统时常出现内存空间不够用
      • 覆盖( overlay )
        应用程序手动把需要的指令和数据保存在内存中
      • 交换( swapping )
        操作系统自动把暂时不能执行的程序保存到外存中
      • 虚拟存储
        在有限容量的内存中，以页为单位自动装入更多更大的程序

覆盖技术

  • 目标：在较小的可用内存中运行较大的程序
  • 方法：依据程序逻辑结构，将程序划分为若干功能相对独立的模块；将不会同时执行的模块共享同一块内存区域
    • 必要部分(常用功能)的代码和数据常驻内存
    • 可选部分(不常用功能)放在其他程序模块中，只在要用到时装入内存
    • 不存在调用关系的模块可相互覆盖，共用同一内存区域
  • 不足
    • 增加编程困难
      • 需程序员划分功能模块，并确定模块间的覆盖关系
      • 增加了编程的复杂度
    • 增加执行时间
      • 从外存装入覆盖模块
      • 时间换空间

交换技术

  • 目标：增加正在运行或需要运行的程序的内存
  • 实现方法
    • 可将暂时不能运行的程序放到外存
    • 换入换出的基本单位
      • 整个进程的地址空间
    • 换出( swap out )
      • 把一个进程的整个地址空间保存到外存
    • 换入( swap in )
      • 将外存中某进程的地址空间读入到内存
  • 交换技术面临的问题
    • 交换时机：何时需要发生交换？
      • 只当内存空间不够或有不够的可能时换出
    • 交换区大小
      • 存放所有用户进程的所有内存映像的拷贝
    • 程序换入时的重定向：换出后再换入时要放在原处吗？
      • 采用动态地址映射的方法

覆盖和交换的比较

  • 覆盖
    • 只能发生在没有调用关系的模块间
    • 程序员须给出模块间的逻辑覆盖结构
    • 发生在运行程序的内部模块间
  • 交换
    • 以进程为单位
    • 不需要模块间的逻辑覆盖结构
    • 发生在内存进程间

虚拟存储技术的目标

  • 只把部分程序放到内存中，从而运行比物理内存大的程序
    • 由操作系统自动完成，无需程序员的干涉
  • 实现进程在内存与外存之间的交换，从而获得更多的空闲内存空间
    • 在内存与外存之间只交换进程的部分内容

局部性原理( principle of locality )

  • 程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。
    • 时间局部性
      • 一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内
    • 空间局部性
      • 当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小区域内
    • 分支局部性
      • 一条跳转指令的两次执行，很可能跳到相同的内存位置
    • 局部性原理的意义
      • 从理论上来说，虚拟存储技术是能够实现的，而且可取得满意的效果

虚拟存储的基本概念

  • 思路：将不常用的部分内存块暂存到外存
  • 原理
    • 装载程序时
      • 只将当前指令执行需要的部分页面或段装入内存
    • 指令执行中需要的指令或数据不在内存(称为缺页或缺段)时
      • 处理器通知操作系统将相应的页面或段调入内存
    • 操作系统将内存中暂时不用的页面或段保存到外存
  • 实现方式
    • 虚拟页式存储
    • 虚拟段式存储
  • 基本特征
    • 不连续性
      • 物理内存分配非连续
      • 虚拟地址空间使用非连续
    • 大用户空间
      • 提供给用户的虚拟内存可大于实际的物理内存
    • 部分交换
      • 虚拟存储只对部分虚拟地址空间进行调入和调出
  • 支持技术
    • 硬件：页式或段式存储中的地址转换机制
    • 操作系统：管理内存和外存间页面或段的换入和换出

虚拟页式存储管理

  • 在页式存储管理的基础上，增加请求调页和页面置换
  • 思路
    • 当用户程序要装载到内存运行时，只装入部分页面，就启动程序运行
    • 进程在运行中发现有需要的代码或数据不在内存时，则向系统发出缺页异常请求
    • 操作系统在处理缺页异常时，将外存中相应的页面调入内存，使得进程能继续运行
  • 虚拟页式存储中的页表项结构
    • 驻留位：表示该页是否在内存
      • 1表示该页位于内存中，该页表项是有效的，可以使用
      • 0表示该页当前在外存中，访问该页表项将导致缺页异常
    • 修改位：表示在内存中的该页是否被修改过
      • 回收该物理页面时，据此判断是否要把它的内容写回外存
    • 访问位：表示该页面是否被访问过(读或写)
      • 用于页面置换算法
    • 保护位：表示该页的允许访问方式
      • 只读，可写，可执行等
  • 虚拟页式存储中的外存管理
    • 在何处保存未被映射的页？
      • 应能方便地找到在外存中的页面内容
      • 交换空间(磁盘或者文件)
        • 采用特殊格式存储未被映射的页面
    • 虚拟页式存储中的外存选择
      • 代码段：可执行二进制文件
      • 动态加载的共享库程序段：动态调用的库文件
      • 其他段：交换空间
  • 虚拟页式存储管理的性能
    • 有效存储访问时间( effective memory access time EAT )
      • EAT = 访存时间 (1-p) + 缺页异常处理时间 缺页率 p
    • 例子：
      • 访存时间：10 ns；磁盘访问时间：5 ms；缺页率 p；页修改概率 q；
      • EAT = 10(1-p) + 5,000,000p(1+q)

缺页异常(缺页中断)的处理流程

  1. 在内存中有空闲物理页面时，分配一物理页帧 f，转第 5 步
  2. 依据页面置换算法选择将被替换的物理页帧 f，对应逻辑页 q
  3. 如 q 被修改过，则把它写回外存
  4. 修改 q 的页表项中驻留位置为 0
  5. 将需要访问的页 p 装入到物理页面 f
  6. 重新执行产生缺页的指令

页面置换算法

置换算法的功能和目标

  • 功能
    • 当出现缺页异常，需调入新页面而内存已满时，置换算法选择被置换的物理页面
  • 设计目标
    • 尽可能减少页面的调入调出次数
    • 把未来不再访问或短期内不访问的页面调出
  • 页面锁定( frame locking )
    • 描述必须常驻内存的逻辑页面
    • 操作系统的关键部分
    • 要求响应速度的代码和数据
    • 页表中的锁定标志位( lock bit )
  • 置换算法的评价方法
    • 记录进程访问内存的页面轨迹
      • 举例：虚拟地址访问用(页号，位移)表示
        (3,0), (1,9), (4,1), (2,1), (5,3), (2,0), (1,9), (2,4), (3,1), (4,8)
      • 对应的页面轨迹
        3，1，4，2，5，2，1，2，3，4
        替换c，a，d，b，e，b，a，b，c，d
    • 评价方法
      • 模拟页面置换行为，记录产生缺页的次数
      • 更少的缺页，更好的性能
  • 页面置换算法分类
    • 局部页面置换算法
      • 置换页面的选择范围仅限于当前进程占用的物理页面内
      • 最优算法，先进先出算法，最近最久未使用算法
      • 时钟算法，最不常用算法
    • 全局页面置换算法
      • 置换页面的选择范围是所有可换出的物理页面
      • 工作集算法，缺页率算法

最优页面置换算法( OPT，optional )

  • 基本思路：置换在未来最长时间不访问的页面
  • 算法实现
    • 缺页时，计算内存中每个逻辑页面的下一次访问时间
    • 选择未来最长时间不访问的页面
  • 算法特征
    • 缺页最少，是理想情况
    • 实际系统中无法实现
    • 无法预知每个页面在下次访问前的等待时间
    • 作为置换算法的性能评价依据
      • 在模拟器上运行某个程序，并记录每一次的页面访问情况
      • 第二遍运行时使用最优算法

先进先出算法( First-In First-Out，FIFO )

  • 思路：选择在内存驻留时间最长的页面进行置换
  • 实现
    • 维护一个记录所有位于内存中的逻辑页面链表
    • 链表元素按驻留内存的时间排序，链首最长，链尾最短
    • 出现缺页时，选择链首页面进行置换，新页面加到链尾
  • 特征
    • 实现简单
    • 性能较差，调出的页面可能是进场访问的
    • 进程分配物理页面数增加时，缺页并不一定减少(Belady现象)
    • 很少单独使用

最近最久未使用算法( Least Recently Used，LRU )

  • 思路
    • 选择最长时间没有被引用的页面进行置换
    • 如某些页面长时间未被访问，则它们在将来还可能会长时间不会访问
  • 实现
    • 缺页时，计算内存中每个逻辑页面的上一次访问时间
    • 选择上一次使用到当前时间最长的页面
  • 特征
    • 最优置换算法的一种近似
  • LRU 算法的可能实现方法
    • 页面链表
      • 系统维护一个按最近一次访问时间排序的页面链表
        • 链表首节点是最近刚刚使用过的页面
        • 链表尾节点是最久未使用的页面
      • 访问内存时，找到相应页面，并把它移到链表之首
      • 缺页时，置换链表尾节点的页面
    • 活动页面栈
      • 访问页面时，将此页号压入栈顶，并栈内相同的页号抽出
      • 缺页时，置换栈底的页面
    • LRU 算法特征：开销比较大

时钟置换算法( Clock )

  • 思路：仅对页面的访问情况进行大致统计
  • 数据结构
    • 在页表项中增加访问位，描述页面在过去一段时间的内访问情况
    • 各页面组织成环型链表
    • 指针指向最先调入的页面
  • 算法
    • 访问页面时，在页表项记录页面访问情况
    • 缺页时，从指针处开始顺序查找未被访问的页面进行置换
  • 特征：时钟算法是 LRU 和 FIFO 的折中
  • 实现
    • 页面装入内存时，访问位初始化为0
    • 访问页面(读/写)时，访问位置1
    • 缺页时，从指针当前位置顺序检查环形链表
      • 访问位为0，则置换该页
      • 访问位为1，则访问位置0，并指针移动到下一个页面，直到找到可置换的页面
  • 改进的 Clock 算法
    • 思路：减少修改页的缺页处理开销
    • 算法
      • 在页面中增加修改位，并在访问时进行相应修改
      • 缺页时，修改页面标志位，以跳过有修改的页面

最不常用算法( Least Frequently Used，LFU )

  • 思路：缺页时，置换访问次数最少的页面
  • 实现
    • 每个页面设置一个访问计数
    • 访问页面时，访问计数加1
    • 缺页时，置换计数最小的页面
  • 特征
    • 算法开销大
    • 开始时频繁使用，但以后不使用的页面很难置换
      • 解决方法：计数定期右移
  • LRU 和 LFU 的区别
    • LRU 关注多久未访问，时间越短越好
    • LFU 关注访问次数，次数越多越好

Belady现象

  • 现象：采用 FIFO 等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象
  • 原因
    • FIFO 算法的置换特征与进程访问内存的动态特征矛盾
    • 被它置换出去的页面并不一定是进程近期不会访问的
  • FIFO 算法有 Belady 现象
  • LRU 算法没有 Belady 现象

LRU，FIFO 和 Clock 的比较

  • LRU 算法和 FIFO 本质上都是先进先出的思路
    • LRU 依据页面的最近访问时间排序
    • LRU 需要动态地调整顺序
    • FIFO 依据页面进入内存的时间排序
    • FIFO 的页面进入时间是固定不变的
  • LRU 可退化成 FIFO
    • 如页面进入内存后没有被访问，最近访问时间与进入内存的时间相同
    • 例如：给进程分配3个物理页面，逻辑页面的访问顺序为1，2，3，4，5，6，1，2，3…
  • LRU 算法性能较好，但系统开销较大
  • FIFO 算法系统开销较小，会发生 Belady 现象
  • Clock 算法是它们的折中
    • 页面访问时，不动态调整页面在链表中的顺序，仅做标记
    • 缺页时，再把它移动到链表末尾
  • 对于未被访问的页面，Clock 和 LRU 算法的表现一样好
  • 对于被访问过的页面，Clock 算法不能记录准确访问顺序，而 LRU 算法可以

全局页面置换算法

  • 背景：局部置换算法没有考虑进程访存差异
  • 思路：全局置换算法为进程分配可变数目的物理页面
  • 全局置换算法要解决的问题
    • 进程在不同阶段的内存需求是变化的
    • 分配给进程的内存也需要在不同阶段有所变化
    • 全局置换算法需要确定分配给进程的物理页面数

CPU 利用率和并发进程数的关系

  • CPU 利用率与并发进程数存在相互促进和制约的关系
    • 进程数少时，提高并发进程数，可提高 CPU 利用率
    • 并发进程导致内存访问增加
    • 并发进程的内存访问会降低了访存的局部性特征
    • 局部性特征的下降会导致缺页率上升和 CPU 利用率下降

工作集

  • 一个进程当前正在使用的逻辑页面集合，可表示为二元函数 W(t,△)
    • t 是当前的执行时刻
    • △ 称为工作集窗口 ( working-set window )，即一个定长的页面访问时间窗口
    • W(t,△) 是指在当前时刻 t 前的 △ 时间窗口中的所有访问页面所组成的集合
    • |W(t,△)| 指工作集的大小，即页面数目
  • 工作集的变化
    • 进程开始执行后，随着访问新页面逐步建立较稳定的工作集
    • 当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定
    • 局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值

常驻集

  • 在当前时刻，进程实际驻留在内存当中的页面集合
    • 工作集和常驻集的关系
      • 工作集是进程在运行过程中固有的性质
      • 常驻集取决于系统分配给进程的物理页面数目和页面置换算法
    • 缺页率和常驻集的关系
      • 常驻集 ⊇ 工作集时，缺页较少
      • 工作集发生剧烈变动(过渡)时，缺页较多
      • 进程常驻集大小达到一定数目后，缺页率也不会明显下降

工作集置换算法

  • 思路：换出不在工作集中的页面
  • 窗口大小 τ
    • 当前时刻前 τ 个内存访问的页引用是工作集，τ 被称为窗口大小
  • 实现方法
    • 访存链表：维护窗口内的访存页面链表
    • 访存时，换出不在工作集的页面；更新访存链表
    • 缺页时，换入页面；更新访存链表

缺页率( page fault rate )

缺页次数 / 内存访问次数 或 缺页平均时间间隔的倒数

  • 影响缺页率的因素
    • 页面置换算法
    • 分配给进程的物理页面数目
    • 页面大小
    • 程序的编写方法

缺页率置换算法( PFF，Page-Fault-Frequency )

  • 原理
    • 通过调节常驻集大小，使每个进程的缺页率保持在一个合理的范围内
      • 若进程缺页率过高，则增加常驻集以分配更多的物理页面
      • 若进程缺页率过低，则减少常驻集以减少它的物理页面
  • 实现
    • 访存时，设置引用位标志
    • 缺页时，计算从上次缺页时间 tlast 到现在 tcurrent 的时间间隔
      • 如果 tcurrent - tlast > T，则置换所有在 [ tlast , tcurrent ] 时间内没有被引用的页
      • 如果 tcurrent - tlast <= T，则增加缺失页到常驻集中

抖动问题

  • 抖动
    • 进程物理页面太少，不能包含工作集
    • 造成大量缺页，频繁置换
    • 进程运行速度变慢
  • 产生抖动的原因
    • 随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减少，缺页率不断上升。
  • 操作系统需在并发水平和缺页率之间达到一个平衡
    • 选择一个适当的进程数目和进程需要的物理页面数

负载控制

  • 通过调节并发进程数 ( MPL ) 来进行系统负载控制
    • ∑WSi = 内存大小
    • 平均缺页间隔时间 ( MTBF ) = 缺页异常处理时间( PFST )