操作系统导论笔记虚拟化

Category： forJobs

写在前面

这部分内容可以成为资源虚拟化, 主要包括 CPU 虚拟化(CPU 调度策略) 和内存虚拟化(虚拟内存, 分段分页技术, 缓存策略等), 从一些很容易思考的点引入, 一点一点来分析不同策略的优劣和权衡, 十分引人入胜.

引入

正在运行的程序

执行指令: 处理器从内存中获取一条指令, 对其进行解码(decode), 然后执行(execute), 完成这条指令之后, 处理器继续执行下一条指令, 直到程序完成.

操作系统

一类让程序在计算机上运行变得容易的程序, 例如允许程序共享内存, 让程序与设备交互等.

虚拟化资源

操作系统通过虚拟化的方法使得计算机更加易用.

操作系统将物理资源(处理器, 内存, 磁盘等) 转换为更加通用, 强大, 易用的虚拟化形式. 为用户提供一些接口, 即系统调用, 或者称为标准库.

操作系统扮演的主要角色就是各种计算机资源的管理器.

进程(抽象)

介绍

操作系统为正在运行的程序提供的抽象, 就是进程(process).

一个进程就是一个正在运行的程序.

程序本身没有生命周期, 只是存在磁盘上的一些指令(静态数据), 是操作系统让这些字节运行起来, 并发挥作用.

进程包括以下的一些部分:

内存: 指令在内存中, 正在运行的程序读取和写入的数据也在内存中,

进程可以访问的内存(地址空间)
寄存器: 许多指令明确地读取或更新寄存器.

程序计数器(Program Counter, PC, 或者称指令指针, IP, Instruction Pointer): 程序当前正在执行哪个指令

栈指针(stack pointer): 管理函数参数栈, 局部变量和返回地址.
可持久化存储设备(硬盘): 此类 I/O 信息可能包含当前打开的文件列表.

创建

将代码和所有静态数据(例如初始化变量) 加载到内存中, 加载到进程的地址空间中.

需要操作系统从磁盘读取这些字节, 并将它们放在内存中的某处.
必须为程序的运行时栈分配一些内存.
可能为程序的堆分配一些内存(动态内存).
执行一些其他的初始化任务(I/O)

状态

      运行 <----->  就绪
I/O 发起 \         / I/O 完成
         \       /
            阻塞

运行(running): 正在执行指令
就绪(ready): 已准备好运行
阻塞(blocked): 直到发生其他事件时才会准备运行.

受限直接执行机制(LDE)

操作系统需要以某种方式让许多任务共享物理 CPU, 让这些程序看起来像是在同时运行, 基本思想就是轮换执行(时分共享 CPU).

在这种共享机制中, 还要保证 CPU 保持高性能且状态可控, 一个技巧就是受限直接执行(LDE, Limited Direct Execution), 引入新的硬件执行模式: 用户态和内核态.

内核态和用户态

在用户态下: 应用程序不能完全访问硬件资源.
在内核态下: 操作系统可以访问机器的全部资源.

与此同时, 还提供陷入指令(用户态->内核态)以及从陷入状态返回(内核态->用户态)操作, 以及系统调用(Syscall).

系统调用允许内核小心地向用户暴露某些关键功能, 要执行这些 Syscall, 程序必须执行特殊的陷阱指令(trap, 陷入), 该指令同时跳入内核并将特权级别提升到内核模式, 一旦进入内核, 系统就可以执行任何需要的特权操作, 从而为调用进程执行所需的工作. 完成之后, 操作系统调用一个特殊的从陷阱返回的指令, 该指令返回到发起调用的用户程序中, 同时将特权级别降低, 回到用户态.

这是通过指令寄存器/程序计数器等协同完成的

trap 寻找 OS 内指令的过程: 陷阱表

内核通过在启动时设置 trap-table 实现, 机器启动时, 在内核态下执行, 因此可以自由配置硬件, 例如配置在发生异常事件时运行哪些代码, 硬件于是记录下这些程序的位置, 记录在陷阱表中, 这类似于注册回调函数.

进程间切换

主动交出控制权(yield)

或者当 OS 发现异常行为自动终止进程并回收资源

被动控制: 时钟中断

中断到期, 执行中断处理程序, 此时 CPU 控制权重新由 OS 获得, OS 可以终止当前进程, 启动新的进程.

上下文切换(保存和恢复)

OS 需要决定: 继续运行当前的程序还是切换到另一个进程, 这个过程由调度程序完成

上下文切换: 为当前正在执行的进程保存寄存器的值(从内核栈中), 并为即将执行的进程恢复一些寄存器的值(从内核栈)

寄存器情况

发生时钟中断: 运行进程的用户寄存器由硬件隐式保存, 使用该进程的内核栈
OS 决定进程切换: 内核寄存器被 OS 明确保存, 存储在该进程的进程结构的内存中(PCB).

进程调度

传统调度

先来先服务(先进先出FIFO): FCFS

最短作业优先: SJF

抢占式最短作业优先(最短完成时间优先STCF): PSJF

时间片轮转: RR

比例份额调度(公平调度)

多级反馈队列调度(MLFQ)

有多级队列来反映工作的优先级, 并且利用反馈信息决定某个工作的优先级.

基本原理

基于许多独立的队列实现, 任何时刻, 一个工作只能存在于一个队列中, MLFQ 总是优先执行优先级较高的工作(较高级别队列中的工作)

每个队列中的多个工作具有同样的优先级, 这种情况下采用轮转调度.

优先级的设置: 根据观察到的行为调整其优先级.

规则

优先级: A>B, 运行 A 而不运行 B
优先级: A=B, 轮转运行 A 和 B
工作进入系统时, 放入最高优先级队列(最上层)
一旦工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次 CPU), 就降低其优先级(移入下一层队列)

原始规则: 工作用完整个时间片之后, 降低其优先级, 如果在其时间片内主动释放了 CPU, 则优先级保持不变

这会导致 CPU 被欺骗(一直有一个程序主动在时间片内释放CPU, 则一直保持高优先级), 采用时间配额方式解决.
经过一段时间, 将系统中所有的工作重新加入最高优先级队列

彩票调度机制

多处理器调度

单队列调度

多队列调度

完全公平调度

地址空间的虚拟化

进程的物理内存抽象, 是运行中的程序”看到的”系统中的内存.

一个进程的地址空间包括运行的程序的所有内存状态:

程序的代码(指令)
函数调用栈信息(局部变量, 传递参数和返回值)
动态内存分配(堆, 由用户管理的内存)

虚拟内存

问题: OS 如何在单一物理内存中为多个运行的进程构建一个私有的, 可能很大的地址空间抽象?

隔离原则: 建立可靠系统的关键原则.

相互隔离的两个实体, 保证了一个实体的失败不会影响到另一个实体

操作系统力求让进程彼此隔离, 防止相互造成伤害

通过内存隔离, 操作系统进一步确保了进程不会影响底层操作系统的操作.

一些现代操作系统通过将某些部分与操作系统的其他部分分离, 实现了进一步的隔离: 称为微内核.

主要目标

透明: 使得运行的程序”看不见”, 即程序不应该感知到内存被虚拟化的事实, 程序的行为就好像其拥有了自己的私有物理内存一样.

在幕后, 操作系统和硬件完成了所有的工作, 让不同反工作复用内存, 从而实现了这一假象.
效率: 追求虚拟化尽可能高效
- 时间上: 不会降低程序运行速度
- 空间上: 不会占用太多额外内存
保护: 操作系统应确保进程受到保护, 不会受到其他进程的影响. (提供隔离的特性)

虚拟地址

程序打印出的地址都是虚拟地址, 虚拟地址只是提供地址如何在内存中分布的假象, 只有操作系统和硬件才知道物理地址.

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    printf("main addr: %p\n", (void *)main);

    int a = 1;
    printf("stack addr: %p\n", &a);

    int *p = (int *)malloc(sizeof(int));
    printf("heap addr: %p\n", p);
    free(p);
    /* g++ on Mac
    main addr: 0x102257ee4
    stack addr: 0x16dbaab24
    heap addr: 0x600002c28050
    */
    return 0;
}

内存操作 API

使用 C 库函数:

#include <stdlib.h>

// man malloc on Ubuntu
void *malloc(size_t size); // 分配未初始化的动态内存
void *calloc(size_t nmemb, size_t size); // 分配初始化的(初始化为 0)动态内存
void *realloc(void *ptr, size_t size); // 重新指定分配的动态内存大小
// 返回的指针指向分配好的且已对齐的内存

void free(void *ptr); // 释放由上述三个函数分配的动态内存

测试

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
void t1() {                              // for test malloc
    int* pi = (int*)malloc(sizeof(int)); // assign one int number
    *pi = 10;                            // Assignment
    printf("%d\n", *pi);
    free(pi);
}
void t2() {                                  // for test calloc
    int* pi = (int*)calloc(10, sizeof(int)); // 第二参数为每一个元素的大小

    for (int i = 0; i < 10; ++i)
        assert(pi[i] == 0);

    free(pi);
}

void t3() { // test realloc
    int* pi = (int*)calloc(5, sizeof(int));
    // printf("%d\n", pi[5]); // heap buffer overflow
    int* new_pi = (int*)realloc(pi, sizeof(int) * 10);
    printf("%d\n", new_pi[5]); // 此时并未初始化
    for (int i = 5; i < 10; ++i)
        assert(new_pi[i] == 0); //
    // free(pi); // double free
    free(new_pi);
}

int main(void) {
    // t1();
    // t2();
    t3();
    return 0;
}

常见错误

可以用 Google 的 Address Sanitizer检测内存问题(力扣常用) AddressSanitizer · google/sanitizers Wiki;

忘记分配内存

多见于常量字符串(char*)赋值
没分配足够的内存(见上面的例子)
忘记初始化分配的内存(见上面的例子)
忘记释放内存
用完之前释放了内存(使用了释放掉的内存)
反复释放内存(double free, 见上面的例子)
错误调用 free, 例如释放栈空间的指针

…

底层系统调用支持

brk 和 sbrk以及 mmap 和 munmap

地址转换

15 章

为了高效灵活使用虚拟内存, 需要使用一种(基于硬件的)地址转换技术, 可以看成受限直接执行(LDE, Limited Direct Execution)这种一般方法的补充

利用地址转换, 硬件对每次内存访问进行处理(指令获取, 数据读取或写入), 将指令中的虚拟地址转换为数据实际存储的物理地址.

程序在每次内存引用时, 都会进行地址转换, 将应用程序的内存引用重定位到内存中实际的位置.

具体

操作系统需要在关键位置介入(Interposition), 设置好硬件, 以便完成正确的地址转换.

因此地址转换必须管理内存, 记录被占用和空闲的内存位置, 并小心介入, 保持对内存使用的控制.

目标

使程序认为自己都拥有私有的内存, 那里存放着自己的代码和数据, 事实上不同程序都在同一时间共享(物理)内存.

一种虚拟化抽象的实现

动态(基于硬件的)重定位

基址寄存器(base): 基地址
界限寄存器(Bound): 偏移量

作用: 可以将地址空间放在物理内存的任何位置, 同时又能确保进程只能访问自己的地址空间.

假设: 在编写程序和编译程序时, 地址空间从零开始.

实际: 真正执行程序时, 操作系统会决定其在物理内存中的实际加载位置, 并将起始地址记录在基址寄存器中.

\[物理地址=虚拟地址+基址\]

操作系统的职责

内存管理:
- 新进程分配内存
- 回收终止进程的内存
- 通过空闲列表管理内存
基址/界限管理: 必须在上下文切换时正确设置基址/界限寄存器
异常处理: 异常发生时终止错误的进程, 并且保持原有状态.

硬件支持

MMU: 内存管理单元, Memory Management Unit.

操作系统层面:

内核态
用户态

硬件层面:

基址/界限寄存器: 每个 CPU 都需要一对这样的寄存器来支持地址转换和界限检查(防止内存访问越界).
转换虚拟地址并检查越界情况
修改基址/界限寄存器
注册异常处理
触发异常

分段(segment)

虚拟化, 第 16 章内容.

引入

程序分为:

同一方向增长(低地址向高地址增长)

代码段: 包含指令计数器
堆段: 动态内存分配

反向增长(高地址向低地址增长)

栈段: 局部变量, 函数参数

分段机制的本质就是: 基址/界限的泛化, 在 MMU 中引入的不只是一个基址/界限寄存器对, 而是给地址空间内的每一个逻辑段都加入一对基址界限寄存器.

用途

使得操作系统能够将不同的段放到不同的物理内存区域, 从而避免了虚拟地址空间中的未使用部分占用物理内存.

分段机制保证了只有已使用的内存才在物理内存中分配空间, 提高内存利用率.

空闲内存管理

本质就是内存块的分割与合并, 目标是避免小块内存产生的内存碎片(降低系统性能).

底层机制

分割合并
追踪已分配的空间的大小
嵌入空闲列表
重新分配更大的堆

基本策略

最优匹配: 找大小最合适的块
最差匹配: 找最大的空闲块
首次匹配: 找第一个足够大能容纳请求大小的块, 每次都从头开始遍历查找可用内存
下次匹配: 使用指针指向上一次分配的控价

分离空闲列表: 有点像 C++的内存管理, 采用池方式
伙伴系统(类似二分查找)

伙伴系统$\bigstar$

二分伙伴分配程序(binary buddy allocator)

原理

空闲空间从概念上看成大小为 $2^N$ 的大空间.

例如:(一开始有一个 64KB 的空闲空间)

|<-      64 KB     ->|
     |           |
   32 KB   |   32 KB
  |     |
16KB | 16KB
 |  |     
8KB|8KB

如果要分配 7KB, 则选择上图左下角的块, 下面分析

分配时: 当有一个内存分配请求时, 空闲空间被递归的一分为二, 直到刚好可以满足请求的大小(无法继续细分), 这时候请求的块返回给用户.
$\bigstar$ 释放时: 如果这个 8KB 的块不再使用, 归还给空闲列表, 分配程序会检查伙伴8KB 是否空闲, 如果是, 则合二为一, 变成 16KB. 然后检查 16KB 的伙伴是否空闲, 如果是, 则合并, 递归合并过程一直上溯, 直到合并整个内存区域, 或者某一块的伙伴还未被释放.

分页(page)

虚拟内存: 虚拟页

物理内存: 物理页帧

页表: 打通虚拟内存和物理内存的桥梁, 主要作用是为地址空间的每一个虚拟页面保存地址转换, 从而让程序知道每个页在物理内存中的位置.

页表

是一个每进程的数据结构, 也就是说每次创建进程都会生成页表.

用于将虚拟地址(虚拟页号, VPN, Virtual Page Number)映射到物理地址(物理帧号, PFN, Physical Frame Number)

最简单的实现形式是: 线性页表(数组, 线性表)

页表项(PTE, Page Table Entry): 页表中的条目.

具体操作

对于每一个具体的内存引用(取指令/显式加载/存储), 分页都需要执行额外的内存引用, 以便首先从页表中获取地址转换.

导致了额外的内存引用开销很大.

与分段相比的优势

不会导致外部碎片: 分页按设计将内存划分为固定大小的单元
灵活: 支持稀疏虚拟地址空间

自身的问题

性能下降: 有许多额外的内存访问来访问页表
内存浪费: 内存被页表塞满而不是有用的应用程序数据.

快速地址转换: TLB

Translation-Lookaside Buffer: 地址转换旁路缓冲存储器

本质就是通过缓存技术提高地址转换的访问命中率, 有了这项技术, 使得虚拟内存成为可能.

TLB 大致流程

从虚拟地址中提取页号(VPN)
检查 TLB 中是否有该 VPN 的转换映射
- 有: 有了 TLB 命中(Hit), 意味着 TLB 有该页的转换映射 -> 成功
  1. 取出页帧号
  2. 保护检查通过 -> 与原来的虚拟地址中的偏移量组合形成期望的物理地址(PA, Physical Address)
  3. 访问内存
- 没有: 需要访问页表, 花费额外的内存引用, 因此耗时较长
  1. 硬件访问页表来寻找转换映射
  2. 地址有效且有对应权限 -> 用找到的转换映射更新TLB
  3. 重试指令.

缓存技术

计算机系统中最基本的性能改进技术之一, 一次又一次用于让常见的情况更快.

背后思想是指令和数据引用的局部性(locality).

时间局部性: 最近访问过的指令或数据项可能很快会再次访问

空间局部性: 当程序访问内存地址 X 时, 可能很快会访问邻近 X 的内存.

利用了局部性, 在小而快的 CPU 内存储器中保存一份内存副本, 这样处理器就可以先检查缓存中是否存在就近的副本, 而不是必须访问内存来满足请求, 如果存在, 处理器就可以很快地访问它, 避免花很多时间来访问内存.

TLB 硬件

全相联(fully-associative, 硬件语言)缓存, 即一条地址映射可能出现在 TLB 的任意位置.

TLB 有效位和页表的有效位

页表中, 页表项(PTE)标记为无效, 则该页并没有被进程申请使用, 正常运行的程序不应该访问该地址, 如果访问了, 就会陷入 trap 内核态, OS 沙雕对应的进程.

TLB 有效位:只是指出 TLB 的条目不是有效的地址映射, 例如当机器启动时, 所有的 TLB 都初始化位无效状态, 之后系统慢慢运行, TLB 逐渐填满, 有效的项逐渐充满 TLB.

分页: 较小的表

简单策略

如果分页太多, 就会导致表变大, 占用很大的内存, 于是可以采用更大的分页大小, 以减小页表.

但是更大的页也会导致每页内的浪费, 又称为内存碎片(所以只能找一个折中的选择)

内存碎片: 浪费的内存存在于页中(分配单元中), 由此得名.

实际上: 大多数系统在常见的情况下使用较小的页大小:

x86_64: 4KB

杂合: 分页和分段

优点:

实现了显著的内存节省: 栈和堆之间未分配的页不再占用页表中的空间(通过标记为无效实现)

缺点:

仍然要求使用分段, 而分段并不灵活, 会导致页表的浪费(产生外部碎片)

折中: 多级页表$\bigstar$

问题: 如何去掉页表中的所有无效区域, 而不是全部保存在内存中?

构建数据结构时候, 应该始终考虑时空的折中(time-space tradeoff)

将线性的页表变成树形.

思路

将页表分成页大小的单元
如果整页的 PTE 无效, 就完全不分配该页的页表
为了追踪页表的页是否有效, 使用页目录(数据结构)追踪页表的位置.

页目录项: PDE

优势

多级页表分配的页表空间, 与正在使用的地址空间爱你内存呢量成比例, 所以其通常很紧凑, 并且支持系数的地址空间.
页表的每一个部分都可以整齐地放入一页中, 从而更容易管理内存

成本

当 TLB 未命中时候, 需要从内存加载两次, 才能从业表中获取正确的地址转换信息(页目录和 PTE 本身)

放入磁盘(换出)

之前一直假设页表位于内核拥有的物理内存中, 但是如果无论怎么优化都还是很大的话就需要换出到磁盘中了, 即:

将页表放入内核虚拟内存
将这些页表的一部分交换到磁盘

机制: 物理内存之外

问题: 使用磁盘(大而慢的设备)透明地提供巨大虚拟地址空间的假象?

SRAM(Static Random Access Memory): (CPU 与内存之间的) L1,L2,L3三级缓存

DRAM(Dynamic Random Access Memory): 内存中缓存的虚拟页(比 SRAM 慢 10 倍) , 采用写回策略

磁盘: 比 DRAM 慢 10w 倍

交换空间(swap space)

交换空间不是唯一的硬盘交换目的地

存在位

硬件通过PTE 中的存在位标记, 查看页是否在内存中.

存在位=0: 页在磁盘上, 而非内存中
存在位=1: 页在物理内存中

页错误

只是一个术语, 其实应该理解为页未命中.

访问不在物理内存中的页: 页错误(page fault)

处理方法: OS需要将发生错误的页交换到(换入)内存中.

OS 如何找到要换入的页?

通过页表, 即 PTE 的某些位存储磁盘地址, 这些位通常用来存储像页的 PFN(物理页帧号)类似的数据.

当 OS 收到 page fault 时, 会在 PTE 中查找地址, 并将请求发送到磁盘, 将页换入内存.

内存满了之后

换出(page out)一些页, 以便为 OS 即将交换入的新页留出空间. (但是不是直接进行替换)

为了保证有少量的空闲内存, OS 会设置高(HW, High Watermark)低(LW)水位线, 以决定何时从内存中清除页.

页替换策略: 选择哪些页被换入或者替换的过程

原理:

当 OS 发现有少于 LW 个页可用的时候, 后台负责释放内存的线程开始运行, 直到有 HW 个可用的物理页, 这个后台线程称为交换守护进程(swap daemon), 之后这个线程会进入休眠状态.

上面的操作也会进行 聚集(cluster)或者分组(group)同时写入 等优化.

具体地, OS 先检查是否有空闲页, 而不是直接执行替换, 如果没有空闲页, 会通知后台分页线程按需要释放页(换出到磁盘), 当后台线程释放了一定数目的页, 会重新唤醒原来的执行线程, 然后把需要的页换入内存, 继续工作.

内存溢出怎么办

内存的超额请求, 这种情况下是否进程的内存需求真的超出了物理内存?

遇到这个问题, OS 会不断进行换入换出操作, 这就导致了抖动(thrashing)现象

解决:

早期系统: 准入控制
Linux: 杀掉内存占用大的进程

TLB缓存替换策略(缓存管理)

这部分单独说了, 面试常考缓存策略(事实上缓存作为一种中间层, 遍布计算机领域).

引入

当内存足够大时候, 不会考虑这个问题, 但是现实往往并不完美.

当内存不足时, 由于内存压力迫使操作系统换出一些页, 位常用的页腾出空间, 确定要逐出(evict)哪个(些)页的方法就是 OS 的替换策略, 封装在 OS 中.

目标

内存只包含系统中所有页的子集, 因此可以将其视为系统中虚拟内存页的缓存, 因此,在为这个缓存选择替换策略的时候, 目标是让缓存未命中尽可能少, 即使得从磁盘获得的页的次数最少. 或者, 将目标看成让缓存命中次数尽可能多, 即在内存中找到待访问的页的次数最多

最优替换策略: OPT

仅用于比较策略的好坏, 因为预测未来中不存在真正的完美

这种方法能达到总体未命中数量最少.

方法

替换内存中在最远的将来才会被访问到的页, 可以达到缓存未命中率最低.

简单策略: FIFO

无状态的策略

方法

先入先出, 队列实现

简单策略: 随机 Random

无状态的策略

方法

随机替换, 平均来说比较好, 但是没有用到局部性原则和历史页面状态信息.

最近最少使用: LRU

利用历史数据(状态)

局部性

时间局部性: 当前页面被访问, 则该页面在不久的某个时间还有可能被访问
空间局部性: 当前页面被访问, 则在该页面的前面或后面几个页面也有可能被访问

近似的 LRU 策略

实现完美的 LRU 需要记录很多信息, 代价比较高, 于是可以通过近似来实现.

通过硬件的标志位支持, 以及时钟算法实现.

类似时间轮, 遍历时钟指针指向的页, 判断标志位, 1 则最近使用过, 0 则可以替换.

加入脏页判断

如果某个页被写入(修改), 变为脏页, 此时进行 evict 就需要写回磁盘, 成本较高, 而 clean 的页写磁盘不会占用过多资源.

这个实现可以通过新的标志位支持完成.

最不经常使用: LFU

先判断使用频率, 如果使用频率相同再判断使用时间的先后, 用到了更多的历史信息.

实例: VAX/VMS 虚拟内存系统

VAX: 硬件

VMS: 操作系统

空指针访问异常

通过

int *p = NULL; // set p = 0
*p = 10;       // 尝试在虚拟地址 0 处装载 int 10

导致段错误: segment fault.

硬件试图在 TLB 中查找 VPN(虚拟页号), 此时 VPN=0, 遇到 TLB 未命中, 查询页表, 发现 VPN=0 的条目标记为无效, 对于这种访问, 会由操作系统决定(陷入内核态), 会导致进程终止.

设计无法被访问的零页, 其目的是提供调试支持, 用于检测空指针访问等问题.

页替换

分段 FIFO 策略

每个进程都有一个可以保存在内存中的最大页数, 称为驻留集大小(RSS, Resident Set Size), 每个页都保存在 FIFO 列表中, 当一个进程超过其 RSS 时, 先入的页被驱逐 (evict), 此过程不需要硬件支持.

原理:

引入二次机会列表(second-chance list), 页在被从内存中逐出之前放在这里, 即全局的干净页空闲列表和脏页列表.

当进程 P 超过其 RSS 时, 将从它的 FIFO 中移除一个页: (每进程 FIFO)

如果干净, 则将其放在全局干净页列表尾
如果被写入/修改, 则将其放在脏页列表尾

此时, 如果另一个进程 Q 需要一个空闲页, 先从全局干净页列表中取出第一个空闲页, 如果原来的 P 进程在回收之前出现了页错误, 则 P 会从空闲列表中回收, 从而避免昂贵的磁盘访问.

页聚集

就是小页的合并, 合并后写入磁盘, 提高性能.

其他技巧: 惰性存取

按需置零

情景: 当用户向 OS 申请一份堆区内存, OS 首先响应这个请求, 在物理内存中找到页, 将该页添加到用户空间的堆区(物理内存), 并将其置零(否则会出现别的进程的内存数据), 然后将其映射到用户地址空间(设置页表以根据需要引用该物理页).

通过按需置零的方法, 当页添加到用户地址空间时, OS 工作变少, OS 首先在页表中放入一个标记页不可访问的条目, 如果进程读取或写入页(访问), 会陷入 OS. 在处理陷入时, OS 发现(通过查看PTE 中的某标志位实现)这是一个按需置零页, 于是 OS 继续完成寻找物理页的必要工作, 将其置零然后映射到进程的地址空间. 如果进程从不访问该页, 则所有的这些工作都可以避免, 降低资源占用和性能损耗.

写时复制: COW

如果 OS 需要将一个页面从某一地址空间复制到另一个地址空间, 不是实际复制, 而是将其映射到目标地址空间, 并在两个地址空间中将其标记为只读.

如果两个地址空间都只读取页面,则不会采取进一步的操作, 因此 OS 已经实现了快速复制而不实际移动任何数据.

当一个地址空间确实尝试写入页面, 就会陷入内核态, OS 会注意到该页面是一个 COW 页面, 因此惰性分配一个新页, 填充数据, 并将这个新页映射到错误处理的地址空间, 此时该页面就有了私人副本.

实际应用:

fork/vfork(): 创建调用者地址空间的精确副本

上篇C++容器存放引用的小坑与分析

下篇多路归并的一些题目总结