7 虚拟内存

7.1 虚拟内存的定义

1. 早期，整个程序装入内存执行，内存不够不能运行

2. 后来，内存不足时以进程为单位在内外存之间交换

3. 对内存采用分页/分段管理后：
• 进程中所有内存访问都是逻辑地址，运行时动态转换为物理地址，使重定位成为可能。
• 进程被划分成许多块（页或段），不需要连续地位于内存中。

4. 进程不需要所有的页/段都在内存中（局部性原理）
• 时间局部性：某条指令被执行后，不久可能被再次执行，某数据被访问后，不久之后可能再次访问  （Cache）
• 空间局部性：一段时间内所访问的地址集中在一定范围内（虚存）

• 在页/段表项中，加入一个标志位，使处理器知悉该页/段是否在内存中。

• 调页时机：预调页（×）；请求调页（√）

• 处理器需要访问一个不在内存中的逻辑地址时，会产生缺页中断。

• 进程被阻塞，操作系统发出磁盘I/O请求。

• 当块被载入内存后，修改页表，并通过I/O中断，唤醒该进程。

• 如果内存已满，先进行置换，置换是在缺页中断期间发生的。

• 在一条指令的执行过程中，可能多次发生缺页中断。

• 给一个进程分配的物理页框的集合被称之为驻留集。

• 支持更有效的系统并发度：在内存中保留更多的进程

• 解除用户与内存之间没必要的紧密约束：进程可以比内存全部空间都大

7.2 支持虚拟内存地硬件和控制结构

分页存储管理

单级页表

多级页表

倒排页表

快表 TLB

高速缓存 Cache

分段存储管理

段页式存储管理

• 页越小，内碎片总量越少

• 页越小，页表越大，可用内存减少，可能导致一次内存访问两次缺页中断。

• 页非常小，页数多，最近访问的部分都被包含在内存中，则缺页率低

• 页越大，页数减少，代码（数据）越集中，局部性原理的影响被削弱，缺页中断有增加的可能

• 页尺寸接近整个进程大小时，缺页率下降，最后为零

7.3 支持虚拟内存的操作系统机制

驻留集分配策略

• 分配给一个进程的物理内存越小，驻留在主存中的进程数就越多，从而可以提高处理器的利用率

• 如果一个进程分配的物理内存（页框）过少，尽管有局部性原理，页错误率仍然会相对较高

• 如驻留集较大，由于局部性原理，当给特定进程分配更多的主存空间时，对进程的缺页错误率没有明显的影响。

1. 固定分配(fixed-allocation)：驻留集大小固定，可以：
• 各进程平均分配；
• 根据程序大小按比例分配；
• 按优先权分配。

2. 可变分配(variable-allocation)：驻留集大小可动态变化，
• 按照缺页率动态调整（高或低→增大或减小常驻集）
• 性能较好，增加算法运行的开销。

页面置换策略

1. 全局置换：
• 从所有进程的页面中选择需要置换的页面；
• 当内存紧张且多个进程频繁缺页时，系统会选择未被频繁访问的页面进行置换。

2. 局部置换：
• 在该进程的驻留集内部进行置换。
• 能减少进程间干扰，简化页面分配策略
• 最优算法（理想化模型）、先进先出算法（FIFO）、最近最久未使用算法（LRU）、CLOCK算法

• 解决方法1：维护一个时间戳(time stamp)，即计数器。每次页引用时，计数器加1，并将该值复制到相应页表项中。当需要置换页时，选则计数值最小的页。
存在的问题：每次地址访问都需要修改时间戳，需维护一个全局时钟（该时钟溢出怎么办？），需要找到最小值，这样的实现代价较大。

• 解决方法2：建立一个容量为有效页框数的页码栈。每当引用一个页时，该页号就从栈中上升到栈的顶部，栈底为LRU页。当需要置换页时，直接置换栈底页即可
存在的问题：每次地址访问都需要修改栈，实现代价仍然较大

• 结构初始化
• 所有可用页框按顺序组成一个环形队列。
• 每个页框都有一个“使用位（use bit）”，初始值为 0。
• 一个指针（类似时钟指针）指向当前检查的位置。

• 页面访问时
• 当某页被访问（读或写）时，将该页的“使用位”设为 1（表示该页最近被使用过。）

• 缺页时的替换过程
• 当发生缺页中断，需要腾出页框时：
• 从当前指针位置开始，检查页框的使用位：
• 若为 1 → 将其清零（表示“刚刚用过，但下次可以考虑换出”），并移动指针到下一项；
• 若为 0 → 表示该页最近没被用过，选它进行替换。
• 将被替换页框装入新页，并把它的使用位设为 1。
• 指针移到下一页框位置。

页面调入与放置策略

• 文件区：存放（可执行）文件（原始存放位置）

• 交换区：存放交换页面

• 基于文件系统：Windows中pagefile.sys文件

• 独立的磁盘分区：生磁盘（RAW），不需要文件系统和目录结构，如Linux中的swap分区

• 系统拥有足够的交换区空间：可以全部从交换区调入所需页面，以提髙调页速度。在进程运行前，需将与该进程有关的文件从文件区复制到交换区。

• 系统缺少足够的交换区空间：凡不会被修改的文件都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出。对于可能被修改的部分，将它们换出时须放到交换区，需要时再从交换区调入。

• UNIX方式：未运行过的页面，都应从文件区调入。曾经运行过但又被换出的页面，被放在交换区，下次调入时从交换区调入。

课堂练习

B

B

D

C

C

ABCD

0000 0000 0000 0000 0110 1111 0001 0010

0000 0000 00|00 0000 0110| 1111 0001 0010

页表项大小4B，小端序

0000 0000 0100 0000 0110 0111 1111 1010

0000 0000 01|00 0000 0110| 0111 1111 1010

一级页表里第第0x1 + 1个4B，二级页表里第0x110 + 1个4B

一级页表起始地址0x00000000，找第1 + 1个4B（0x00000004）

小端序，只有高20位有效

00 00 2|0 07 ←控制位，清零 下级页表起始地址：0x00 00 20 00，找第6 + 1个4B（0x00002018）

00 40 6|0 07 ←控制位，清零 块号：0x00 40 6 物理地址：0x00 40 67 FA

期末真题

2024秋

• 内部碎片（Internal Fragmentation）：
已分配的内存块内部未被充分利用的部分，即分配给进程的内存大于实际需要。
产生原因：内存以固定大小的分区（或页框）分配，进程实际需求与分区大小不完全匹配，导致块内空间浪费。

• 外部碎片（External Fragmentation）：
未分配的空闲内存被分散成多个小块，虽然空闲总量足够，但无法满足一个连续分配请求。
产生原因：进程不断装入、撤出，造成内存中空闲区间分散、不连续。

1. 产生缺页（或缺段）中断，CPU转入内核态；

2. 操作系统根据中断信息查找该页（或段）在外存中的位置；

3. 从外存（通常是磁盘）调入所需页（或段）到内存；

4. 更新页表或段表，标记该页已在内存；

5. 恢复进程并重新执行被中断的指令。

2020春

• 虚拟内存（Virtual Memory）：
是一种让每个进程拥有连续、独立的逻辑地址空间的技术，它将进程的地址空间与实际物理内存空间分离，通过在需要时才将部分程序或数据装入内存来实现“假象的大内存”。

• 引入原因：
1. 允许程序比物理内存更大，提高内存利用率；
2. 支持多道程序并发运行；
3. 提供地址空间隔离，增强系统安全与稳定性。

2014