OS-虚拟存储器

第五章虚拟存储器

虚拟存储器在逻辑上实现了对内存容量的扩充

概述

常规存储管理方式的特征

一次性：作业必须一次性的全部装入内存后方能开始运行
驻留性：作业被装入内存后，将一直驻留到作业运行结束

局部性原理

程序运行时存在局部性现象，由于大多是顺序执行，循环结构，以及对数据结构的处理也是局限于一个小范围
局限性分为两个方面
- 时间局限性
  - 若某指令被执行，则不久可能再被执行
  - 若某数据被访问，则不久可能再被访问
- 空间局限性
  - 程序在一定时间所访问的地址可能集中在一定的范围之内

虚拟存储器的工作情况

由于局部性原理，程序在运行时没必要一次性装入内存，只需要当前运行的少数页面或段先装入即可
当访问的页/段未调入内存，称为缺页/缺段，便发出中断请求，利用调页/调段功能调入内存
若内存已满，则需要置换暂时不用的页/段，腾出空间

定义

虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器
其逻辑容量由内存容量和外存容量之和决定

特征

多次性：一个作业中的程序和数据允许被分为多次调入
对换性：一个作业中的程序和数据无须一直驻留，允许进行换出换入
虚拟性：能够从逻辑上扩充内存容量，虚拟存储器最重要的特征

实现方法

二者分别是在分页/分段系统基础上添加了请求调页和页面置换功能所形成的页式/段式虚拟存储系统

分页请求系统
请求分段系统

请求分页存储管理方式

硬件支持

请求页表机制
- 请求分页系统中需要的主要数据结构是请求页表
- 每个页表需含有
- 状态位：指示该页是否已调入内存
- 访问字段：用于记录本页在一段时间被访问的此时或多久未被访问，提供于置换算法参考
- 修改位：标识调入内存后是否被修改，供置换时参考
缺页中断机构
- CPU通常在一条指令执行完后才检查是否有中断请求到达；而缺页中断是在指令执行期间，若发现访问的指令或数据步在内存，则立即产生和处理缺页中断信号
- 一条指令在执行期间可能产生多次缺页中断，机构应保存多次中断时的状态，确保中断恢复顺利
地址变换机构
- 地址变换过程

内存分配

最小物理块数的决定

最小物理块数是指能保证进程正常运行所需的最小物理块数
取决于指令格式，功能，寻址方式
如单地址指令且直接寻址，则最少2块，一块存放指令页面，一块存放数据页面

内存分配策略

固定分配局部置换
- 固定分配，即位每个进分配一组固定数目的物理块，运行期间不再改变
- 局部置换，即若运行中发现缺页，则只能从分配给该进程的n个页面中选出一页换出，再调入一页，确保分配的内存空间不变
可变分配全局置换
- 可变分配，即先为每个进程分配一定数目的物理块，在运行期间，根据情况适当增加或减少
- 全局置换，即如果进程运行中发现缺页，则将OS所保留的空闲物理块取出一块分配给该进程，或者以所有进程的全部物理块为标的，选择一块换出，调入所缺之页
可变分配局部置换

物理块分配算法

平均分配算法
- 将系统中所有可供分配的物理块平均分配给各个进程
按比例分配算法
- 根据进程大小按比例分配物理块
考虑优先权的分配算法
- 把内存中可供分配的所有物理块分成两部分
  - 一部分按比例分配
  - 一部分按优先权分配

页面调入策略

何时调入页面
- 预调页策略
  - 以预测为基础的策略，将预计会不久被访问的页面预先调入内存
  - 第一次调入可由程序员指定哪些页先调入
  - 在采用工作集的系统。每个进程有个表，表中记录运行时的工作集。每当程序被调度运行，就把工作集中所有页调入
- 请求调页策略
  - 当进程运行时发现所需页面不在内存，则立即提出请求
何处调入页面

请求分页系统的外存分为两部分

存放文件的文件区，离散分配，存取速度慢

存放对换页面的对换区，连续分配，存取速度块

有三种情况
- 系统拥有足够对换区空间，此时可全部从对换区调入所需页面
- 系统缺少足够对换区空间，凡是不会被修改的文件，都从文件区调入；对于可能被修改的部分，换出时调到对换区
- UNIX方式，凡是为运行过的页面，都从文件区调入
调入页面过程
- 发出缺页中断请求
- 中断处理程序保留CPU环境，分析原因
- 缺页中断处理程序查找页表，得到该页在外存的物理块
  - 若内存可容纳新页，直接调入内存，修改页表
  - 若内存已满，采用置换算法，选择一页换出
    - 若该页未被修改，则不必写回硬盘
    - 若该页已被修改，则须写回硬盘
    - 调入所缺页
缺页率
- 假设进程逻辑空间为n页，系统分配内存物理块数位m，若运行过程中，访问页面成功(该页面在内存中)的次数S，访问失败次数为F，则总访问次数A=S+F
  [缺页率f=frac{F}{A}=frac{F}{F+S}=frac{访问成功次数}{总访问次数} ]
页面大小，页面越大，缺页率越低
进程所分配的物理块数，越多缺页率越低
页面置换算法
程序固有特性
假设被置换的页面被修改改了为b，缺页中断处理时间为Ta，被置换页面没有被修改的缺页中断事件为Tb，

[缺页中断处理时间t=b imes{Ta}+(1-b) imes{Tb} ]

页面置换算法

当一个进程运行中的大部分时间花在页面置换工作上，称该进程发生了抖动，不适当的页面置换算法会导致抖动

最佳置换算法

所选择的被淘汰的页面将是以后永不使用，或最长时间内不再被访问的页面
可保证最低缺页率，但无法实现该算法
序号列为引用顺序，7，0，1先装入内存，当还要访问页面2时，将选择页面7淘汰，因为7比0和1更晚被再次访问，以此类推
在该序列号共发生了六次页面置换

先进先出置换算法FIFO

总是淘汰最先进入内存的页面，即选择驻留时间最久的页面淘汰
实现方式：把一个进程已经调入内存的页面按先后次序链接成队列，并设置替换指针，总是指向最老的页面
同样的引用顺序序列号，发生了12次页面置换

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

选择最近最久未使用的页面予以淘汰
实现方式：赋予每个页面一个访问字段，用于记录一个页面自上次被访问以来所经历的时间t，每次需要淘汰页面时，选择t最大的
硬件支持
- 寄存器，记录某进程在内存中各页的使用情况，设置了一个移位寄存器
- 栈，每当进程访问某页面，则压入栈顶，栈顶始终未最新访问页面编号，栈底是最近最久未使用页面

最少使用置换算法LFU

每个页面设置一个移位寄存器，用于记录该页面被访问的频率，每访问某页，便将最高位置1，再每隔一定时间右移一次
该算法选择最佳时期使用最少的页面作为淘汰页

Clock置换算法

简单的Clock置换算法（NRU，Not Recently Used）

实现方式：每页设置一位访问位，内存中所有页面通过链接指针链接成一个循环队列，当某页被访问时，其访问位置1
执行过程：选择淘汰页时，只需检查页的访问位，若为0，则换出，若为1，则置0；若检查到最后一个页面访问位仍为1，则再返回队首重新检查

改进型Clock置换算法

对于修改过的页面，换出时所付出的开销比未修改的大，又称置换代价
由访问位A和修改位M可用组成四种页面，分别为1，2，3，4类
- A=0,M=0：该页最近既未被访问，又为被修改，最佳淘汰页
- A=0,M=1：该页最近未被访问，但已被修改
- A=1,M=0：该页最近已被访问，但未被修改，可能再被访问
- A=1,M=1：该页最近已被访问，也已被修改，可能再被访问
执行过程：
- 先寻找第一类页面，将所遇到的第一个页面作为淘汰页，第一次扫描不改变访问位
- 若第一步失败，第二轮扫描第二类页面，将所遇到的第一个页面作为淘汰页，将所有扫描过的页面访问位置0
- 若第二步失败，重复循环第1，2步，但将所有扫描过的页面访问位置0

页面缓冲算法

页面换出换进所付出的开销对系统性能影响重大

影响页面换出换进效率的因素

页面置换算法
写回磁盘的频率
读入内存的频率

页面缓冲算法PBA

系统为每个进程分配一定数目的物理块，自己保留一部分空闲物理块，为了显著降低页面换进换出频率，在内存中设置两个链表
- 空闲页面链表
  - 实际上是空闲物理块链表，用于分配给频繁缺页的进程
  - 当这样的进程需要读入一个页面时，便将空闲物理块链表中第一个物理块装入该页
  - 当有一个未被修改的页要换出时，把它们所在的物理块挂在空闲链表末尾，而不是换出
- 修改页面链表
  - 当有一个已被修改的页要换出时，把它们所在的物理块挂在修改页面链表末尾，而不是换出

访问内存的有效时间EAT

被访问页在内存，对应的页表项在快表中
- EAT=查找快表时间+访问实际物理地址所需时间
被访问页在内存，对应的页表项不在快表中
- 需两次访问内存，一次读取页表，一次读取数据，还要修改快表
- EAT=(查找快表时间+访问实际物理地址所需时间)x2
被访问页不在内存
- 访问实际物理地址所需时间a，缺页率f，缺页中断处理时间b
- EAT=a+f x (a+b)+(1-f) x t