AHA'S BOOK

在文章 操作系统之 chapter5.1 虚拟内存管理之覆盖技术与交换技术 中，介绍了内存管理的覆盖技术和交换技术；这篇文章将介绍虚拟内存管理技术（虚存技术），它结合了覆盖技术和交换技术中的优点。

虚拟内存管理技术

如果想要在有限容量的内存中，以 更小的页粒度为单位 装入更多、更大的程序，可以采用自动的虚拟存储技术。

目标

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

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

操作系统内存管理

程序局部性原理

程序的局部性原理（principle of locality）：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定的区域。

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

程序的局部性原理表明，从理论上来说，虚拟存储技术是能够实现的。而且在实现了以后应该是能够取得一个满意的效果。

经典实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
题目描述：
页面大小为 4KB，分配给每个进程的物理页面是 1。 
在一个进程中，定义了如下的二维数组 int arr[1024][1024]，该数组按行存放在内存，每一行放在一个页面中。

考虑一下程序的编写方法对缺页率的影响？
*/

// 程序编写方法 1：（发生了 1024*1024 次缺页中断）
for (j = 0; j < 1024; j++) {
    for (i = 0; i < 1024; i++) {
        arr[i][j] = 0;
    }
}
    

// 程序编写方法 2：（发生了 1024 次缺页中断）
for (i = 0; i < 1024; i++) {
    for (j = 0; j < 1024; j++) {
        arr[i][j] = 0;
    }
}

因为数组是「按行」存放在一块连续的内存中的，上面的二维数组每行有 1024 个元素（类型为 int 型），所以该数组的一行数据，占用 4K 字节，正好为一个物理页面的空间。

  • 方法一是按列访问的，即访问完第 0 列，再访问第 1 列，每列的不同行处在不同的物理页面中，因此会发生 102421024^{2} 次缺页中断；
  • 方法二是按行访问的，即访问完第 0 行，再访问第 1 行，访问的每行都是在同一个物理页面中，因此只会发生 10241024 次缺页中断。

实例耗时测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <time.h>

int main(int argc, char *argv[]) {
    int arr[1024][1024];
    clock_t start, end;
    double cpu_time_used;

    start = clock();
    for (int j = 0; j < 1024; j++) {
        for (int i = 0; i < 1024; i++) {
            arr[i][j] = 0;
        }
    }
    end = clock();
    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf(" 代码执行耗时：%f 秒 \n", cpu_time_used);

    start = clock();
    for (int i = 0; i < 1024; i++) {
        for (int j = 0; j < 1024; j++) {
            arr[i][j] = 0;
        }
    }
    end = clock();
    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf(" 代码执行耗时：%f 秒 \n", cpu_time_used);

    return 0;
}

连续运行三次的结果：

1
2
3
4
5
6
7
8
9
[root@localhost xxx]# ./a.out
代码执行耗时：0.008293 秒 
 代码执行耗时：0.002611 秒 
[root@localhost xxx]# ./a.out
 代码执行耗时：0.008260 秒 
 代码执行耗时：0.002613 秒 
[root@localhost xxx]# ./a.out
 代码执行耗时：0.008252 秒 
 代码执行耗时：0.002575 秒

基本概念

可以在页式或段式内存管理的基础上实现虚拟内存管理技术。

  • 在装入程序时，不必将其全部装入内存，而只需将当前需要执行的部分页面（或段）装入到内存中，就可以让程序开始执行；
  • 一方面，在程序执行过程中，如果需执行的指令或访问的数据尚未在内存中（称为缺页或缺段），则由 CPU 通知操作系统将相应的页面（或段）调入到内存，然后继续执行程序；
  • 另一方面，操作系统将内存中暂时不使用的页面（或段）调出保存在外存上，从而腾出更多空闲内存空间，存放将要装入的程序以及将要调入的页面（或段）。

基本特征

  • 大的用户空间：通过把物理内存和外存相结合，提供给用户的虚拟内存空间通常大于实际的物理内存，即实现了这两者的分离。
    • 如 32 位的虚拟地址理论上可以访问 4GB，而可能计算机上仅有 256M 的物理内存，但硬盘容量大于 4GB。
  • 部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的（交换粒度更小，效率更高）。
  • 不连续性：物理内存分配的不连续性，虚拟地址空间使用的不连续性。

页式内存管理

页表：完成逻辑页到物理页帧的映射。首先，根据页号查找页表对应的索引项；然后，查看该表项对应的 resident bit 的状态，1 表示映射关系存在，确定页帧号；最后，页帧号加上原来的页内偏移，即可获得物理地址。

resident bit 的值为 0 表示虚拟地址对应的逻辑页当前不在内存中，而是在外存（磁盘）中存储。

虚拟页式内存管理

实现

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

基本思路

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

页面置换功能实现的好坏决定了整体的效率，后面专门讲这些设计有效的置换算法。

页表表项

为了实现「请求调页」和「页面置换」功能，我们需要在页表表项中增加一些位 bit 来辅助实现。

页表表项示意图：

1
逻辑页号 | 访问位 | 修改位 |   保护位   | 驻留位 | 物理页帧号
  • 驻留位：表示该页是在内存中还是在外存中。
    • 值为 1 表示该页位于内存中，该页表表项有效，物理页帧可以被使用；
    • 值为 0 表示当前页在外存中，访问该页表表项将导致缺页异常。
  • 保护位：表示允许对该页做何种类型的访问，如只读，可读写，可执行等。
  • 修改位：表示此页在内存中是否被修改过。
    • 当系统回收该物理页面时，根据此位来决定是否把物理页面的内容写回外存。
  • 访问位：如果该页被访问过（包括读写操作），则设置此位。
    • 用于页面置换算法。

缺页中断

缺页中断处理过程：

  1. 产生缺页中断；
  2. 如果在内存中有空闲的物理页面，则分配一物理页帧 f，然后转第 4 步；否则转到第 2 步；
  3. 采用某种页面置换算法，选择一个将被替换的物理页帧 f，它所对应的逻辑页为 q。如果该页在内存期间被修改过，则需要把它写回外存；
  4. 对 q 所对应的页表项修改，把驻留位置为 0；
  5. 将需要访问的页 p 装入到物理页面 f 当中；
  6. 修改 p 所对应的页表项的内容，把驻留位置为 1，把物理页帧号置为 f；
  7. 重新运行被中断的指令。

缺页中断操作系统处理流程：
缺页中断操作系统处理

后备存储（backing store）

系统在何处保存未被映射到物理内存中的页呢？

  • 能够简单地识别在二级存储器中的页
  • 交换空间（磁盘或者文件）：特殊格式，用于存储未被映射的页面

后背存储（二级存储）：一个虚拟地址空间的页面，可以被映射到一个文件（在二级存储中）的某个位置，以便在需要时重新加载到主存储器中。

在操作系统中，不同段可以被映射到不同的文件：

  • 代码段：映射到可执行二进制文件；
  • 动态加载的共享库程序段：映射到动态调用的库文件；
  • 其他段：可能被映射到交换文件（swap file）。

操作系统中一般会有主存储器（也称为一级存储器或内存）和辅助存储器（如硬盘、SSD 等）两种类型的存储设备。主存储器用于存储当前正在运行的进程和其所需的数据，而辅助存储器用于存储暂时不需要的进程或数据，辅助存储器也称为后背存储或二级存储。

虚拟内存性能分析

为了便于理解分页的开销，使用有效存储器访问时间（effective memory access time, EAT）来衡量。

EAT = 访存时间 * 页表命中几率 + page fault 处理时间 * page fault 几率

实例：

  • 访问物理内存时间：10 ns
  • 磁盘访问时间：5 ms
  • 参数 p = page fault 几率
  • 参数 q = dirty page 几率

则 EAT=10×(1−p)+5⋅106×p×(1+q)EAT = 10 \times (1-p) + 5 \cdot 10^{6} \times p \times (1+q)

其中，1+q1 + q 的 qq 表示发生 dirty page 后需要将页面写回外存的耗时。

dirty page 是指在计算机系统中的内存中的一个页面，其中的数据已经被修改，与磁盘上的对应页面的数据不同步。当进程对内存中的页面进行写操作时，该页面会被标记为“脏页”，表示该页面的数据已经被修改但尚未写回到磁盘。在后续的页面调度或内存回写操作中，操作系统会将脏页的数据写回到磁盘，以确保内存中的数据与磁盘上的数据保持一致性。这样可以防止数据丢失或不一致的情况发生。

参考资料：
1：https://github.com/OXygenMoon/OperatingSystemInDepth
2：https://blog.csdn.net/weixin_53407527/article/details/124983180

aha
2023-11-27
操作系统 内存管理技术
Expand all Back to top Go to bottom Search in blogs
银河白
豆沙绿
杏仁黄
青草绿
秋叶褐