第5章：虚拟内存

操作系统

• 起因
• 覆盖技术
• 交换技术
• 虚存技术
  
  • 目标
  • 程序局部性原理
  • 基本概念
  • 基本特征
  • 虚拟页式内存管理

5.1 虚拟内存的起因

• 理想中的存储器
  
  • 更大、更快、更便宜的非易失性存储器
• OS支持的存储器
  
  • 更大、更快、更便宜好用的易失性存储器
• 内存不够用
  
  • 程序太大，手动的覆盖（overlay）技术，只把需要的指令和数据保存在内存当中
  • 程序太多，自动的交换（swapping）技术，把暂时不能执行的程序送到外存
  • 想在有限的内存中，以更小的页粒度为单位装入更多更大的程序，采用自动的虚拟存储技术

5.2 覆盖技术

• 目标：是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用
• 原理：把程序按照自身逻辑结构，划分为若干个功能上相对独立的程序模块，那些不会同时执行的模块共享同一块内存区域，按时间先后来运行
  
  • 必要部分（常用功能）的代码和数据常驻内存
  • 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中，在需要用到时才装入内存
  • 不存在调用关系的模块不必同时装入内存，从而可以相互覆盖，即这些模块共用一个分区
• 缺点：
  
  • 由程序员来把一个大的程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，费时费力，增加了编程的复杂度
  • 覆盖模块从外存装入内存，实际上是以时间延长来换取空间节省

5.3 交换技术

• 目标：多道程序在内存中时，让正在运行的程序或需要运行的程序获得更多的内存资源
• 方法：
  
  • 可将暂时不能运行的程序送到外存，从而获得空闲内存空间
  • 操作系统把一个进程的整个地址空间的内容保存到外存中（换出swap out），而将外存中的某个进程的地址空间读入到内存中（换入swap in）。换入换出内容 的大小为整个程序的地址空间

几个问题

• 交换时机的确定：只有当内存空间不够或有不够的危险时换出
• 交换区的大小：必须足够大以存放所有用户进程的所有内存映像的拷贝；必须能对这些内存映像进行直接存取
• 程序换入时的重定位：换出后再换入内存位置一定要在原来的位置上吗？最好采用动态地址映射的方法

覆盖与交换的比较

• 覆盖只能发生在那些相互之间没有调用关系的程序模块之间，因此程序员必须给出程序内各个模块之间的逻辑覆盖结构
• 交换技术是以在内存中的程序大小为单位进行的，它不需要程序员给出各个模块之间的逻辑覆盖结构。换言之，交换发生在内存中程序与管理程序或操作系统之间，而覆盖发生在运行程序的内部。

5.4.1 虚存技术（上）

• 目标：在内存不够用的情形下，可以采用覆盖技术和交换技术，但是

  • 覆盖技术：需要程序员自己把整个程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，增加了程序员的负担。
  • 交换技术：以进程为交换的单位，需要把进程的整个地址空间都换进换出，增加了处理器的开销。

• 像覆盖技术一样，不是把程序的所有内容都放在内存中，因而能够运行比当前空闲内存空间还要大的程序。但做得更好，由操作系统自动来完成，无需程序员的干涉

• 像交换技术那样，能够实现进程在内存与外存之间的交换，因而获得更多的空闲内存空间。但做得更好，只对进程的部分内容在内存和外存之间进行交换

程序的局部性原理

• 指程序在执行的过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域，可以表现为：

  • 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问，都集中在一个较短时期内
  • 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在较小的区域内。

• 基本概念：

  • 可以在页式或段式内存管理的基础上实现
  • 在装入程序时，不必将其全部装入到内存，而只需将当前执行的部分页面或段装入到内存，就可以让程序开始执行
  • 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存中（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序
  • 另一方面，操作系统将内存中暂时不使用的页面或段调出保存在外存上，从而腾出更多的空闲空间存放将要装入的程序以及将要调入的页面或段
• 基本特征：
  
  • 大的用户空间：通过把物理内存与外存相结合，提供给用户的虚拟内存空间通常大于实际的物理内存，即实现了这两者的分离
  • 部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的
  • 不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续

5.4.2 虚存技术（下）

虚存技术 - 虚拟页式内存管理

• 大部分虚拟存储系统都采用虚拟页式存储管理技术，即在页式存储管理的基础上，增加请求调页和页面置换功能

• 基本思路：

  • 当一个用户程序要调入内存运行时，不是将该程序的所有页面都装入内存，而是只装入部分的页面，就可启动程序运行
  • 在运行过程中，如果发现要运行的程序或要访问数据不再内存，则向系统发出缺页中断请求，系统在处理这个中断时，将外存中相应的页面调入内存，使得该程序能够继续运行

• 页表表项：

  • 逻辑页号i | 访问位 | 修改位 | 保护位 | 驻留位 | 物理页帧号 |
  • 驻留位：表示该页是在内存还是在外存，如果该位为1，表示该页位于内存当中，即该页表项是有效的，可以使用；如果该位为0，表示该页当前还在外存当中，如果访问该页表项，将导致缺页中断
  • 保护位：表示允许对该页做何种类型的访问，如只读、可读写、可执行等
  • 修改位：表明此页在内存中是否被修改过。当系统回收该物理页面时，根据此位来决定是否把它的内容写回外存
  • 访问位：如果该页面被访问过（包括读操作或写操作），则设置此位。用于页面置换算法
• 缺页中断处理过程：
  
  1. 如果在内存中有空闲的物理页面，则分配一物理页帧f，然后转第4步；
  2. 采用某种页面置换算法，选择一个将被替换的物理页帧f，它所对应的逻辑页为q。如果该页在内存期间被修改过，则需把它写回外存；
  3. 对q所对应的页表项进行修改，把驻留位置为0；
  4. 将需要访问的页p装入到物理页面f当中；
  5. 修改p所对应的页表项的内容，把驻留位置为1，把物理页帧号置为f；
  6. 重新运行被中断的指令；

后备存储（Backing store）

• 在何处保存未被映射的页？
• 能够简单的识别在二级存储器中的页
• 交换空间（磁盘或文件）：特殊格式，用于存储未被映射的页面
• 概念：
  
  • 一个虚拟地址空间的页面可以被映射到文件（在二级存储中）中的某个位置
  • 代码段：映射到可执行二进制文件
  • 动态加载的共享库程序段：映射到动态调用的库文件
  • 其他段：可能被映射到交换文件（swap file）

虚拟内存性能

• 为了便于理解分页的开销，使用有效存储器访问时间（EAT）
• EAT = 访存时间 * 页表命中几率 + page fault 处理时间 * page fault 几率

例
- 访存时间：10 ns
- 磁盘访问：5 ms
- 参数p = page fault 几率
- 参数q = dirty page 几率
- EAT = 10(1-p) + 5,000,000 p(1*q)