操作系统之 虚拟存储概念

为什么需要虚拟存储?

计算机系统常出现内存空间不够用

如何解决内存空间不够用?

  • 覆盖(Overlay)

应用程序 手动 把需要的指令和数据保存在内存中 (将代码分成若干模块 彼此无调用关系的 将其附庸到一块区域 需要用户自己来确定何时将其模块加入程序 开发难度高)

  • 交换(对换 Swapping)

操作系统 自动 把暂时不能执行的程序保存到外存中 (因为对换的是一个进程的整个地址空间 所以开销会比较大)

  • 虚拟存储

在有限容量的内存中 以页为单位自动装入更多更大的程序

覆盖和交换技术

覆盖技术目标

在较小的可用内存中运行较大的程序 (一个程序的运行内存空间都不够)

覆盖技术实现方法

依据程序的逻辑结构 将程序模块划分为若干功能相对独立的模块
将不会同时执行的模块共享同一块内存区域

  • 必要部分(常用功能)的代码和数据常驻内存
  • 可选部分(非常用功能)放在其他程序模块中 只在需要的时候装入内存
  • 不存在调用关系的模块可相互覆盖 共用同一块内存区域

overlay

覆盖技术的不足
  • 增加编程难度
    1
    需要程序员 划分功能模块 并确定模块间的覆盖关系
  • 增加执行时间
    1
    从外存 装入覆盖 模块 时间换空间

交换技术目标

增加正在运行或需要运行的程序的内存 (一个程序的运行内存空间足够了 但是想要运行更多的进程)

交换技术实现方法

  • 将暂时不能运行的程序放到外存
  • 换入换出基本单位 整个进程的地址空间
  • 换出(Swap out) 把一个进程的整个地址空间保存到外存
  • 换入(Swap in) 把外存中的某进程的地址空间读入到内存

swapping

交换技术有什么问题?

  • 交换时机
    1
    当内存不够 或 有不够的可能时换出
  • 交换区大小
    1
    存放所有用户进程的所有内存映像的拷贝
  • 程序换入时的重定位 换出时再换入时要放在原处吗?
    1
    采用动态地址映射的方法

覆盖与交换的比较

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

虚拟存储 使用的就是 交换的思路 只不过它是以页来做单位 且 是操作系统来完成的交换

局部性原理 (Principle of locality)

程序在执行过程中的一个较短时期 所执行的指令地址和指令的操作数地址 分别局限于一定区域

  • 时间局部性
    • 一条指令的一次执行和下一次执行 一个数据的一次访问和下次访问 都集中在一个较短时期
  • 空间局部性
    • 当前指令和邻近的几条指令 当前访问的数据和邻近的几个数据 都集中在一个较小的区域
  • 分支局部性
    • 一条跳转指令的两次执行 很可能跳转到相同的内存位置
  • 局部性原理意义
    • 从理论上来说 虚拟存储是能够实现的 并且可以取得满意的成果

不同程序编写方法的局部性特征

例子:页面大小为4K,分配给每个进程的物理页面数为1。在一个进程中,定义了如下的二维数组int A[1024][1024],该数组按行存放在内存,每一行放在一个页面中

1
2
3
4
程序编写方法1
for (j = 0; j < 1024; j++)
for (i = 0; i < 1024; i++)
A[i][j] = 0; // 按行 清 0
1
2
3
4
程序编写方法2
for (i = 0; i < 1024; i++)
for (j = 0; j < 1024; j++)
A[i][j] = 0; // 按列 清 0

principle_of_locality

第一种编程方法 按行 清 0 按照题目所说 分配给每个进程的物理页面数为 1 就会产生 1024 x 1024 次缺页异常 因为 不断的在换页

第二种编程方法 按列 清 0 从 0 ~ 1023 都是在同一页 只有换行的时候 才会换页 故会 产生 1024 次 缺页异常

如果物理内存小 这两种编程方法的性能差距是巨大的

虚拟存储

将不常用的部分内存暂存到外存

虚拟存储的目标

  • 只把部分程序放到内存中 从而运行比物理内存大的程序
  • 由操作系统自动完成
  • 在内存与外存之间只交换进程的部分内容

虚拟存储思路

  • 加载程序时 只将当前执行所需要的部分页面或段装入内存
  • 指令执行时中需要的指令或数据不在内存中时 处理器通知操作系统将相应的页面或段调入内存
  • 操作系统将内存中暂时不用的页面或段保存到外存

虚拟存储实现方式

  • 虚拟段式存储
  • 虚拟页式存储

虚拟存储基本特征

  • 不连续性
    • 物理内存分配非连续
    • 虚拟地址空间使用非连续
  • 大用户空间
    • 提供给用户的虚拟内存可大于实际的物理内存
  • 部分交换
    • 虚拟存储只对部分虚拟地址空间的换入和换出

虚拟存储的支持技术

  • 硬件
    • 页式或短时存储中的地址转换机制 (硬件要知道它在内存里还是在外存里)
  • 操作系统
    • 管理内存和外存间页面或段的换入换出 (操作系统要知道它要换的页面或段是哪些)

虚拟页式存储

在页式存储管理的基础上 增加请求调页和页面置换

  • 思路
    • 当用户进程要加载到内存运行时 只装入部分页面 就启动程序运行
    • 进程在运行中发现有需要的代码或数据不在内存中 则向系统发起缺页异常请求 然后就进入了 中断服务例程
    • 操作系统在处理缺页异常时 将外存的页面调入内存 使进程能够继续运行

虚拟页式存储地址转换

其实和之前 非虚拟页式存储地址转换 是一样的 只不过页表项里会有一个 P 位 表示这个页是否存在 若不存在 就会发起缺页异常中断

logaddr2phyaddr0

x86pagetable

1
2
3
地址转换依然是 逻辑地址的 前 10 位 加上 cr3 寄存器里面的 页目录表基址 找到 PDE 
读出 PDE 找到 页表项基址 加上 逻辑地址的中间 10位 找到 PTE
再将 从 PTE 读出的 物理页面帧号 + 逻辑地址的 低 12 位 找到 物理地址

页表项 结构和之前说的一样
pagetable_entries

  • AVL CPU 不理会这个属性 可以不管 (有可能在32位系统使用大过 4G内存的时候 用到这几位)
  • G Global 全局位 表示是否将虚拟地址与物理地址的转换结果缓存到 TLB 中
  • D Dirty 脏页位 当 CPU 对这个页进行写操作时 会置 1
  • PAT Page Attribute Table 页属性表位 置 0
  • A Accessed 访问位 若为 1 则 说明 CPU 访问过了 CPU 会定时清 0 记录被置 1 的频率 当内存不足时 会将 使用频率较低的页面换出到外存 同时将 P位 置 0 下次访问 该页时 会引起 Pagefault 异常 中断处理程序再将此页换上
  • PCD Page-level Cache Disable 页级高速缓存位 置 0 即可 读的时候 高速缓存是否有效 若有效则直接从高速缓存中读出 若无效的话 则必须实实在在的从 I/O 端口去读数据
  • PWT Page-level Write-Through 页级通写位 控制是先写到高速缓存里再慢慢回写到内存里 还是 直接慢慢写到内存里
  • US User/Superviosr 普通用户/超级用户位
  • RW Read/Write 读写位
  • P Present 存在位 (虚拟页式存储的关键位 若为 0 则发起缺页异常)

缺页异常的处理例程

1
2
3
4
5
6
7
8
CPU 执行 Load M
这条指令会去找 M 对应的 页表项 若 这个页表项有效(P 位 为 1) 则直接访问
若无效 就会产生缺页异常 导致操作系统的缺页异常的服务例程会执行
缺页异常服务例程 会去找外存中的那个页面 若找到 就将其读入内存
读入内存之前 还要先判断物理内存中是否有空闲页 若找到空闲页 就将这页读进来 并修改页表项 最后重新执行 一开始的那条指令
若找不到空闲页 依据页面置换算法 找一页不常用的页 若这一页被修改过 则将其写到外存
若未修改过 则将其丢弃 且 修改 这一页的 P 位 为 0 使其失效
将需要访问的页装入被替换掉的页 且 修改 页表项的 P 位 为 1

pagefault

虚拟页式存储中的外存管理

在何处保存未被映射的页?

  • 应能方便地找到在外存中的页面内容 (直接做一个分区做对换区 Linux Unix)
  • 交换空间 (磁盘或者文件)
    • 采用特殊格式存储未被映射的页面 (用一个文件来存)

虚拟页式存储中的外存怎么选择?

  • 代码段 它就是可执行的二进制文件 没必要复制
  • 代码加载的共享库程序段 也是不会变的 没必要复制
  • 其他段 可以放到交换空间里去

虚拟页式存储管理的性能

有效存储访问时间 (Effective memory access time EAT)

1
2
EAT = 访存时间 * (1 - p) + 缺页异常处理时间 * 缺页率p * (1 + 页修改概率q) (若不开启虚拟页式存储 则 EAT = 访存时间)
加多一个 页修改概率q 是因为被替换的页被修改过的话 还要写到外存里保存起来