408操作系统第三章内存管理 虚拟内存管理

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，即为虚拟内存。虚拟内存管理，详细的总结了虚拟内存的基本概念，请求分页管理方式。页面置换算法，页面分配策略，抖动，工作集。

第三章 内存管理 3.2虚拟内存管理

• 虚拟内存的基本概念
  • 传统存储管理方式的特征、缺点
    • 一次性：作业必须一次性全部装入内存后才能开始运行。会造成大作业无法运行和多道程序并发度下降的问题
    • 驻留性：作业数据在整个运行期间都会常驻内存
  • 局部性原理
    • 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
    • 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的）
    • 高速缓存技术：使用频繁的数据放到更高速的存储器中
  • 虚拟内存的定义和特征
    • 定义
      • 程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
      • 程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
      • 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
      • 在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，即为虚拟内存。
    • 三个主要特征
      • 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
      • 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
      • 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
  • 虚拟内存的实现
    • 虚拟内存的实现需要建立在离散分配的内存管理方式基础上。
    • 请求分页存储管理
    • 请求分段存储管理
    • 基本段页式存储管理
• 请求分页管理方式
  • 与基本分页存储管理的区别
    • 操作系统要提供请求调页功能，将缺失页面从外存调入内存
    • 操作系统要提供页面置换功能，将暂时用不到的页面换出外存（用页面置换算法决定应该换出哪个页面）
  • 页表机制
    • 在基本分页基础上增加了几个表项
    • 状态位：表示页面是否已在内存中
    • 访问字段：记录最近被访问几次，或上次访问的时间，供置换算法选择换出页面时参考
    • 修改位：表示页面调入内存后是否被修改过，只有修改过的页面才需在置换时写回内存
    • 外存地址：页面在外存中存放的位置
  • 缺页中断机构
    • 找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断
    • 缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面
    • 缺页中断属于内中断，属于内中断中的“故障”，即可能被系统修复的异常
    • 一条指令在执行的过程中可能产生多次缺页中断
  • 地址变换机构（重点关注与基本分页不同的地方）
    • 找到页表项是需要检查页面是否在内存中
    • 若页面不在内存中，需要请求调页
    • 若内存空间不够，还需换出页面
    • 页面调入内存后，需要修改相应页表项
• 页面置换算法
  • 页面的换入、换出需要磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率
  • 最佳置换算法（OPT，Optimal）
    • 算法规则：优先淘汰最长时间内不会被访问的页面
    • 优缺点：缺页率最小，性能最好；但无法实现
  • 先进先出置换算法（FIFO）
    • 算法规则：优先淘汰最先进入内存的页面
    • 优缺点：实现简单；但性能很差，可能出现Belady异常
  • 最近最久未使用置换算法（LRU）
    • 算法规则：优先淘汰最近最久没访问的页面
    • 优缺点：性能很好；但需要硬件支持，算法开销大
  • 时钟置换算法（CLOCK，NRU）
    • 算法规则：循环扫描各页面。第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。若第一轮没选中，则进行第二轮扫描。
    • 优缺点：实现简单，算法开销小；但未考虑页面是否被修改过。
  • 改进型的时钟置换算法（改进型NRU）
    • 算法规则：将所有可能被置换的页面排成一个循环队列
      • 第一轮：淘汰（0,0） 从当前位置开始扫描到第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位（第一优先级：最近没访问，且没修改的页面）
      • 第二轮：淘汰（0,1），并将扫描过的页面访问位都置为0 若第一轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。本轮将所有扫描过的帧访问位设为0（第二优先级：最近没访问，但修改过的页面）
      • 第三轮：淘汰（0,0） 若第二轮扫描失败，则重新扫描，查找第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位（第三优先级：最近访问过，但没修改的页面）
      • 第四轮：淘汰（0,1） 若第三轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换（第四优先级：最近访问过，且修改过的页面）
    • 优缺点：算法开销较小，性能也不错
• 页面分配策略、抖动、工作集
  • 驻留集
    • 指请求分页存储管理中给进程分配的物理块的集合。
    • 在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。
    • 若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少: 驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。
  • 页面分配、置换策略
    • 固定分配：操作系统为每个进程分配- -组固定 数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
    • 可变分配：先为每个进程分配一-定 数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变
    • 局部置换：发生缺页时只能选进程自己的物理块进行置换。
    • 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
    • 固定分配局部置换：进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页
    • 可变分配全局置换：只要缺页就分配新物理块，可能来自空闲物理块，也可能需换出别的进程页面
    • 可变分配局部置换：频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块。 直到缺页率合适
  • 何时调入页面
    • 预调页策略:一般用于进程运行前
    • 请求调页策略:进程运行时，发现缺页再调页
  • 从何处调页
    • 对换区——采用连续存储方式，速度更快；文件区——采用离收存储方式，速度更慢。
    • 对换区足够大：运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行
    • 对换区不够大:不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入
    • UNIX方式：第一次使用的页面都从文件区调入；调出的页面都写回对换区，再次使用时从对换区调入
  • 抖动（颠簸）现象
    • 页面频繁换入换出的现象。主要原因是分配给进程的物理块不够
  • 工作集
    • 在某段时间间隔里， 进程实际访问页面的集合。驻留集大小一般不能小于工作集大小