【计算机操作系统】3-2-虚拟内存及页面置换

虚拟内存的基本概念

  • 内存空间的分配与回收
    • 连续分配
      • 单一连续分配
      • 固定分区分配
      • 动态分区分配
    • 非连续分配
      • 基本分页存储管理
      • 基本分段存储管理
      • 基本段页式存储管理
  • 内存空间的扩充
    • 覆盖技术
    • 交换技术
    • 虚拟内存技术
  • 地址转换
  • 存储保护

在传统存储管理方式的基础上引入了交换技术、覆盖技术,使得内存利用率有所提升,并且能从逻辑上扩充内存容量。

  • 传动存储管理方式的特征、缺点
  • 局部性原理
    • 时间局部性
    • 空间局部性
    • 高速缓存技术
  • 虚拟内存的定义和特征
  • 如何实现虚拟内存技术

传统存储管理方式的特征、缺点

  • 连续分配
    • 单一连续分配
    • 固定分区分配
    • 动态分区分配
  • 非连续分配
    • 基本分页存储管理
    • 基本分段存储管理
    • 基本段页式存储管理

很多暂时用不到的数据也会长期占用内存,导致内存利用率不高

一次性:作业必须一次性全部装入内存后才能开始运行。

  • 这会造成两个问题
    1. 作业很大时,不能全部装入内存,导致大作业无法运行
    2. 当大量作业要求运行时,由于内存无法容纳所有作业,因此只有少量作业能运行,导致多道程序并发度下降

驻留性:一旦作业被装入内存,就会一直驻留在内存中,直至作业运行结束。事实上,在一个时间段内,只需要访问作业的一小部分数据即可正常运行,这就导致了内存中会驻留大量的、暂时用不到的数据,浪费了宝贵的内存资源。

局部性原理

时间局部性:如果执行了程序中的某条指令,那么不久后这条指令很有可能再次执行;如果某个数据被访问过,不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)

空间局部性:一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的,并且程序的指令也是顺序地在内存中存放的)

高速缓冲技术的思想:将近期会频繁访问到的数据放到更高速的存储器中,暂时用不到的数据放在更低速的存储器中。

快表机构就是将近期常访问的页表项副本放到更高速的联想寄存器中。

虚拟内存的定义和特征

基于局部性原理,在程序装入时,可以将程序中很快会用到的部分装入内存,暂时不用的部分留在外存,就可以让程序开始执行。

在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存,然后继续执行程序。

若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存

在操作系统的管理下,在用户看来似乎有一个比实际内存大得多的内存,这就是虚拟内存

操作系统虚拟性的一个体现,实际物理内存大小没有变,只是在逻辑上进行了扩充。

  • 易混知识点

    • 虚拟内存的最大容量是由计算机的地址结构(CPU寻址范围)确定的
    • 虚拟内存的**实际容量=min(内存和外存容量的和,CPU寻址范围)
  • 虚拟内存的三个主要特征:

    • 多次性:无需再作业运行时一次性全部装入内存而是允许被分成多次调入内存
    • 对换性:在作业运行时无需一直常驻内存,而是允许在作业运行过程中,将作业换入、换出
    • 虚拟性:从逻辑上扩充了内存的容量,使用户看到的内存容量,远大于实际的容量

如何实现虚拟内存技术

虚拟内存技术,允许一个作业分多次调入内存。如果采用连续分配方式,会不方便实现。因此,虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

  • 传统的非连续分配存储管理
    • 基本分页存储管理
    • 基本分段存储管理
    • 基本段页式存储管理
  • 虚拟内存的实现
    • 请求分页存储管理
    • 请求分段存储管理
    • 请求段页式存储管理

主要区别:在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存,然后继续执行程序。若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存。

总结

  • 传统存储管理方式的特征、缺点
    • 一次性:作业数据必须一次全部调入内存
    • 驻留性:作业数据在整个运行期间都会常驻内存
  • 局部性原理
    • 时间局部性:现在访问的指令、数据在不久后可能会被再次访问
    • 空间局部性:现在访问的内存单元周围的内存空间,很可能在不久后会被访问
    • 高速缓存技术:使用频繁的数据放到更高速的存储器中
  • 虚拟内存的定义和特征
    • 程序不需全部装入如即可运行,运行时很具需要动态调入内存,若内存不够,还需换出一些数据
  • 特征
    • 多次性:无需再作业运行时一次性全部装入内存而是允许被分成多次调入内存
    • 对换性:在作业运行时无需一直常驻内存,而是允许在作业运行过程中,将作业换入、换出
    • 虚拟性:从逻辑上扩充了内存的容量,使用户看到的内存容量,远大于实际的容量
  • 如何实现虚拟内存技术
    • 访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存(请求调页功能)
    • 内存空间不够时,将内存中暂时用不到的信息换出到外存(页面置换功能)
    • 虚拟内存的实现
      • 请求分页存储管理
      • 请求分段存储管理
      • 请求段页式存储管理

请求分页管理方式

  • 页表机制
  • 缺页中断机构
  • 地址变换机构

页表机制

与基本分页管理相比,请求分页管理中,为了实现“请求调页”,操作系统需要知道每个页面是否已经调入内存,如果还没导入,那么也需要知道该页面在外存中存放的位置。

当内存空间不够时,要实现“页面置换”,操作系统需要通过某些指标来决定到底换出哪个页面;有的页面没有被修改过,就不用浪费时间写会外存。有的页面修改过,就需要将外存中的旧数据覆盖,因此,操作系统也需要记录各个页面是否被修改的信息。

页号 内存块号 状态位 访问字段 修改位 外存地址
0 a 0 0 0 x
1 b 1 10 0 y
2 c 1 6 4 z

缺页中断机构

在请求分页系统中,每当要访问的页面不在内存时,便产生一个缺页中断,然后由操作系统的缺页终端处理程序处理中断

此时缺页的进程阻塞,放入阻塞队里,调页完成后再将其唤醒,放回就绪队列。

如果内存中有空闲块,则为进程分配一个空闲块,将所缺页面装入该块,并修改页表中相应的页表项。

如果内存中没有空闲块,则由页面置换算法选择一个页面淘汰,若该页面在内存期间被修改过,则要将其写回外存。未修改过得页面不用写回外存。

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的,因此属于内中断

一条指令在执行期间,可能产生多次缺页中断。

  • 中断的分类
    • 内中断(内部异常)
      • 陷阱、陷入(trap)
      • 故障(fault)
      • 终止(abort)
    • 外中断
      • I/O中断请求
      • 人工干预

地址变换机构

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

  1. 在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存,然后继续执行程序。
  2. 若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存

快表中有的页面一定是在内存中的。若某个页面被换出外存,则快表中的相应表项也要删除,否则可能访问错误的页面。

  1. 只有“写指令”才需要修改“修改位”。并且,一般来说只需修改快表中的数据,只有要将快表项删除时才需要写会内存中的慢表。这样可以减少访存次数。
  2. 和普通的中断处理一样,缺页中断仍然需要保留CPU现场。
  3. 需要用某种“页面置换算法”来决定一个换出页面
  4. 换入/换出页面都需要启动慢速的I/O操作,可见,如果换入/换出太频繁,会有很大的开销。
  5. 页面调入内存后,需要修改慢表,同时也需要将表项复制到快表中

在具有快表机构的请求分页系统中,访问一个逻辑地址时,若发生缺页,则地址变换步骤是:

  1. 查快表(未命中)
  2. 查慢表(发现未调入内存)
  3. 调页(调入的页面对应的表项会直接加入快表)
  4. 查快表(命中)
  5. 访问目标内存单元

总结

  • 页表机制
    • 在基本分页的基础上增加了几个表项
    • 状态位:表示页面是否已在内存中
    • 访问字段:记录最近被访问过几次,或记录上次访问的时间,供置换算法选择换出页面时参考
    • 修改位:表示页面调入内存后是否被修改过,只有修改过的页面才需在置换时写回外存。
    • 外存地址:页面在外存中存放的位置
  • 缺页中断机构
    • 找到页表项后检查页面是否已在内存,若没在内存,产生缺页中断
    • 缺页中断处理中,需要将目标页面调入内存,有必要还要换出页面
    • 缺页中断属于内中断,属于内中断的“故障”,即可能被系统修复的异常
    • 一条指令在执行过程中可能产生多次缺页中断
  • 地址变换机构(重点灌注与基本分页不同的地方)
    • 找到页表项是需要检查页面是否在内存中
    • 若页面不再内存中,需要请求调页
    • 若内存空间不够,还需换出页面
    • 页面调入内存后,需要修改相应页表项

页面置换算法

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

    1. 在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外调入内存,然后继续执行程序。
    2. 若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存
  • 最佳置换算法(OPT)

  • 先进先出置换算法(FIFO)

  • 最近最久未使用置换算法(LRU)

  • 时钟置换算法(CLOCK)

  • 改进型的时钟置换算法

页面的换入、换出需要磁盘I/O,会有较大的开销,因此好的页面置换算法应该追求更少的缺页率

最佳置换算法(OPT)

最佳置换算法(Optimal):每次选择淘汰的页面将是以后永不使用,或者在最长时间内不再被访问的页面,这样可以保证最低的缺页率。

缺页时未必发生页面置换。若还有可用的空闲内存块,就不用进行页面置换。

最佳置换算法可以保证最低的缺页率,但实际上,只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列,因此最佳置换算法是无法实现的

先进先出置换算法(FIFO)

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

实现方法:把调入内存的页面根据调入的先后顺序排成一个队列,需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。

  • Belady异常——当为进程分配的物理块数增大时,缺页次数不减反增的异常现象。

只有FIFO算法会产生Belady异常。另外,FIFO算法虽然实现简单,但是该算法与进程实际运行时的规律不适应,因为先进入的页面也有可能最经常被访问。因此,算法性能差

最近最久未使用置换算法(LRU)

最近最久未使用置换算法(Least Recently Used):每次淘汰的页面最近最久未使用的页面

实现方法:赋予每个页面对应的页表项中,用访问字段记录该页面自上次被访问以来所经历的时间t

当需要淘汰一个页面时,选择现有页面中t值最大的,即最近最久未使用的页面。

|页面|内存块号|状态位|访问字段|修改位|外存地址|

在手动做题时,若需要淘汰页面,可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面

时钟置换算法(CLOCK)

最佳置换算法性能最好,但无法实现;先进先出置换算法实现简单,但算法性能差;最近最久未使用置换算法性能好,最接近OPT算法性能的,但是实现起来需要专门的硬件支持,算法开销大。

时钟置换算法是一种性能和开销较均衡的算法,又称CLOCK算法,或**最近未用算法(NRU,Not Recently Used)

简单的CLOCK算法实现方式:为每个页面设置一个访问位,再将内存中的页面都通过链接指针链接程一个循环队列。当某页被访问时,其访问位置为1。当需要淘汰一个页面时,只需检查页的访问位。如果是0,就选择该页换出;如果是1,则将它置为0,暂不换出,继续检查下一个页面,若第一轮扫描中所有页面都是1,则将这些页面的访问位依次置为0后,再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面,因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

|页号|内存块号|状态位|访问位|修改位|外存地址|

改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上,如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时,才需要写回外存

最多进行四轮扫描