Untitled

背景

虚拟内存（virtual memory）将用户逻辑内存与物理内存分开

不需要将整个程序置于内存中

在现有物理内存有限的情况下，为程序员提供了更大的虚拟内存

虚拟内存大于物理内存

虚拟内存大于物理内存

虚拟地址空间

虚拟地址空间

随着动态内存分配，允许堆向上生长，也允许栈向下生长，只有在堆与栈生长时才需要实际的物理页

包括空白的虚拟地址空间称为稀疏（sparse）地址空间

虚拟内存允许文件和内存通过共享页为多个进程所共享

通过将共享对象映射到虚拟地址空间中，系统库可以为多个进程所共享

Untitled

虚拟内存允许进程共享内存

当通过系统调用fork()创建进程时，可以共享页面，从而加快进程创建

  • 虚拟内存可以通过两种方式实现：
    • 请求调页（Demand Paging）
    • 请求调段（Demand Segmentation）

请求调页（Demand Paging）

仅在需要时才加载页面

当进程需要执行时，它被交换到内存中，但不是整个进程交换到内存中，而是采用惰性交换器（lazy swapper）

惰性交换器除非需要某个页面，否则从不将它交换到内存中

调页程序（pager）只涉及进程的页面

基本概念

  • 有效-无效位可用于区分内存的页面和磁盘的页面：
    • 有效：相关联的页面是合法的，并且在内存中
    • 无效：页面不在进程的逻辑地址空间中，或有效但只在磁盘上

有些页面不在内存的页表

有些页面不在内存的页表

对标记为无效的页面访问会产生缺页错误（page fault）

  • 处理缺页错误的程序：
    1. 检查这个进程的内部表（通常与 PCB 一起保存），以确定该引用是有效的还是无效的内存访问
    2. 如果引用有效但是尚未调入页面则现在就应调入；如果引用无效则通过 trap 中断进程
    3. 找到一个空闲帧
    4. 调度一个磁盘操作，以将所需页面读到刚分配的帧
    5. 当磁盘读取完成时，修改进程的内部表和页表，以指示该页现在处于内存中
    6. 重新启动被 trap 中断的指令。该进程现在能访问所需的页面，就好像它总是在内存中

Untitled

请求调页的性能

设 pp 为缺页错误的概率（0≤p≤10\leq p\leq1），则有效访问时间为：

EAT=(1−p)×memory access+p×缺页错误时间EAT=(1-p)\times memory\,access+p\times缺页错误时间

  • 缺页错误导致发生一系列动作：
    • 陷入操作系统
    • 保存用户寄存器和进程状态
    • 确定中断是否为缺页错误
    • 检查页面引用是否合法，并确定页面的磁盘位置
    • 从磁盘读入页面到空闲帧
      1. 在该磁盘队列中等待，直到读请求被处理
      2. 等待磁盘的寻道或延迟时间
      3. 开始传输磁盘页面到空闲帧
    • 在等待时，将 CPU 分配给其它用户（CPU 调度，可选）
    • 收到来自 I/O 子系统的中断（I/O 完成）
    • 保存其他用户的寄存器和进程状态
    • 确认中断时来自上述磁盘的
    • 修正页表的其他表，以表示所需页面现在已在内存中
    • 等待 CPU 再次分配给本进程
    • 恢复用户寄存器、进程状态和新页表，再重新执行中断的指令
  • 缺页错误的处理时间有三个主要组成部分
    • 处理缺页错误的中断
    • 读入页面
    • 重新启动进程

写时复制（Copy-on-Write）

通过允许父进程和子进程最初共享相同的页面来工作

如果任何一个进程写入共享页面，就创建共享页面的副本

进程 1 修改页面 C 之前

进程 1 修改页面 C 之前

进程 1 修改页面 C 之后

进程 1 修改页面 C 之后

复制页面是，空闲页面从操作系统提供的一个空闲页面池（page pool）来分配

操作系统分配这些页面通常采用按需填零（zero-fill-on-demand）技术，按需填零页面在需要分配内存之前先添零，因此清除了以前的内容。

页面置换（Page Replacement）

需要页面置换的情况

需要页面置换的情况

基本页面置换

  • 基本过程：
    1. 找到所需页面的磁盘位置
    2. 找到一个空闲帧：
      • 如果有空闲帧，那么就使用它
      • 如果没有空闲帧，那么就使用页面置换算法来选择一个牺牲帧（victim frame）
      • 将牺牲帧的内容写到磁盘上，修改对应的页表和帧表
    3. 将所需页面读入（新的）空闲帧，修改页表和帧表
    4. 从发生缺页错误位置，继续用户进程

Untitled

希望一个缺页错误率最低的页面置换算法

评估算法的方法：针对特定内存引用串，运行某个置换算法，并计算缺页错误的数量

缺页错误与帧数量图

缺页错误与帧数量图

即使帧数量无限大，缺页错误也不为 0，因为初始化的时候使用惰性交换器，必然会有缺页错误

FIFO 页面置换

为每个页面记录调到内存的时间，当必须置换页面时，将选择最旧的页面

Belady 异常（Belady’s anomaly）：对于有些页面置换算法，随着分配帧数量的增加，缺页错误率可能会增加

最优页面置换

置换最长时间不会使用的页面

具有最低的缺页错误率，且不会遭受 Belady 异常

最优置换算法难以实现，因为需要引用串的未来知识（与 SJF 调度的问题类似），主要用于比较研究

LRU 页面置换

最近最少使用算法（Least-Recent-Used algorithm, LRU algorithm）

将每个页面与它上次使用的时间关联起来，当需要置换页面时，LRU 选择最长时间没有使用的页面

  • 确定由上次使用时间定义的帧的顺序的两种实现：
    • 计数器：每当进行页面引用时，时钟寄存器的内容会复制到相应页面的页表条目的使用时间域。需要搜索页表以查找 LRU 页面，而且每次内存访问都要写到内存（到页表的使用时间域）
    • 堆栈：每当页面被引用时，它就从堆栈中移除并放在顶部。最近最少使用的页面总是在堆栈底部。因为需要从堆栈中间删除条目，所以最好通过使用具有首指针和尾指针的双向链表来实现

很少有计算机系统能够提供足够的硬件来支持真正的 LRU 页面置换算法

近似 LRU 页面置换

每个页表的引用位由操作系统初始化为 0

每当引用一个页面时（无论是对页面的字节进行读或写），它的页面引用位就被硬件置位

额外引用位算法

可以为内存中的页表的每个页面保留一个 8 位的字节，包含着最近 8 个时间周期内的页表使用情况，全0说明没用过，全1说明每个周期至少都用过1次，值越大越最近使用。

具有最小编号的页面是 LRU 页面，可以被置换

被访问时左边最高位置 1，定期右移并且最高位补 0

第二次机会算法

  • 当选择一个页面时检查其引用位：
    • 如果为 0 就直接置换此页面
    • 如果为 1 就将引用位置为 0，即给此页面第二次机会

实现方式是采用循环队列

Untitled

一旦找到牺牲页面就置换该页面，并在循环队列的这个位置上插入新页面

如果所有位都为 1，则退化为 FIFO 置换

增强型第二次机会算法

  • 通过将引用位和修改位作为有序对修改第二次机会算法，有四种可能的类型：
    • (0,0) 无引用无修改，置换的最佳页
    • (0,1) 无引用有修改，置换前需要写回脏页
    • (1,0) 有引用无修改，很可能会继续用
    • (1,1) 有引用有修改，很可能会继续用且置换前须要写回脏页

淘汰次序 (0,0) > (0,1) > (1,0) > (1,1)

替换非空的最低类型中的第一个页面

可能需要多次扫描循环队列才会找到要置换的页面

为已修改的页面赋予更高级别，从而降低了所需 I/O 数量

基于计数的页面置换

为每个页面的引用次数保存一个计数器

最不经常使用（Least Freuently Used, LFU）页面置换算法：置换具有最小计数的页面，因为积极使用的页面应当具有大的引用次数

最经常使用（Most Frequently Used, MFU）页面置换算法：基于具有最小计数的页面可能刚刚被引入尚未使用的论点

LFU 和 MFU 都不常用，不能很好地近似 OPT 置换

页面缓冲

通过被置换页面的缓冲，有机会找回刚被置换的页

被置换页面的选择和处理：用 FIFO 选择置换页，如果页面无修改，将其归入空闲页链表，否则归入已修改页面链表。

需要调入新页面时，将新页面内容读入空闲页面链表的第一项所指的页面，然后将其删除

帧分配

每个进程的最小帧数由体系结构决定

固定分配（Fixed Allocation）

平均分配（equal allocation）：给每个进程一个平均值

比例分配（proportional allocation）：根据每个进程大小分配可用内存

优先级分配（Priority Allocation）

采用的比例分配的策略不是根据进程的相对大小，而是根据进程的优先级或大小和优先级的组合

给予高优先级的进程更多内存以加速执行，同时损害低优先级进程

全局分配与局部分配

全局置换（global replacement）：允许一个进程从所有帧的集合中选择一个置换帧，而不管该帧是否已分配给其他进程

局部置换（local replacement）：要求每个进程只从它自己分配的帧中进行选择

在全局置换算法中进程不能控制自己的缺页错误率

对于局部置换算法，进程的内存页面的集合仅受该进程本身的调页行为所影响

局部置换由于不能额使用其他进程的较少使用的内存页面，可能会阻碍一个进程

全局置换通常由更好的系统吞吐量，因此更常用

系统抖动（Thrashing）

如果进程没有需要支持活动使用页面的帧数，那么它会很快产生缺页错误。此时，必须置换某个页面，但由于它的所有页面都在使用中，所以必须立即置换需要再次使用的页面，因此会再次快速产生缺页错误，再一次置换必须立即返回的页面，如此快速进行。

抖动：一个进程高度的页面调度活动。如果一个进程的调页时间多于它的执行时间，则这个进程就在抖动

系统抖动的原因

Untitled

局部性模型（locality model）：随着进程的执行，它从一个局部移向另一个局部

局部性是最近使用的页面的一个集合

发生抖动主要原因是内存不足，不足以容纳下一段时间内的局部性之和

通过局部置换算法可以限制系统抖动，一个进程不能从另一个进程中获取帧，也不能导致后者抖动

通过分配足够的内存来容纳下一个进程的局部性可以避免系统抖动

工作集模型（Working-Set Model）

基于局部性假设

采用参数 Δ\Delta 定义工作集窗口，思想是检查最近 Δ\Delta 个页面引用

最近 Δ\Delta 个页面引用的页面集合称为工作集，其大小为 WSSiWSS_i

D=∑WSSiD=\sum WSS_i 为系统中所有进程的帧的总需求量，如果大于可用帧总数则将发生抖动

通过定期时钟中断和引用位，可以近似工作集模型

假设 Δ\Delta 为 10000 个引用，每 5000 个引用引起定时器中断。当得到一个定时器中断时，复制并清除所有页面的引用位。如果发生缺页错误，检查当前的引用位和位于内存中断两个位，至少有一位打开的页面被视为在工作集中

缺页错误频率（Page-Fault Frequency）

当缺页错误率太高时，该进程需要更多的帧

当缺页错误率太低时，该进程可能具有太多的帧

可以为所期望的页错误设置一个上限和下限，如果页错误率超过上限，那么分配更多的帧，如果低于下限，那么可以从进程中移走帧。

Untitled

内存映射文件

采用虚拟内存技术来将文件 I/O 作为常规内存访问

将每个磁盘块映射到一个或多个内存页面

开始的文件访问按照普通按需请求调度，会出现缺页错误。这样，一页大小的部分文件从文件系统中读入物理页，以后的文件访问就可以按照通常的内存访问来处理，这样就可以用内存操作文件，而非read()和write()等系统调用，简化了文件访问和使用。

多个进程可以允许将同一文件映射到各自的虚存中，达到数据共享的目的

分配内核内存

  • 用于分配内核内存的空闲内存池通常不同于用于普通用户模式进程的列表，有两个主要原因：
    • 内核需要为不同大小的数据结构请求内存
    • 有的硬件设备与物理内存直接交互，可能要求内存常驻在连续物理内存中

伙伴系统（Buddy System）

从物理连续的大小固定的段上进行分配

采用 2 的幂分配器来满足请求分配单员的大小为 2 的幂

请求大小如不适当就圆整到下一个更大的 2 的幂

Untitled

通过合并可以将相邻的伙伴快速组合形成更大的分段

Untitled

由于圆整到下一个 2 的幂，很可能造成分配段内的碎片

slab 分配

每个内核数据结构都有一个 cache，每个 cache 含有内核数据结构的对象实例

每个 cache 由一个或多个 slab 组成

每个 slab 由一个或多个物理连续的页面组成

Untitled

在创建 cache 时，cache 内所有对象都标记为 free

当需要内核数据结构新对象时，从 cache 上分配空闲对象，标记为 used

slab 分配器首先从部分为空的 slab 中用空闲对象满足请求，如果没有则从全空的 slab 中分配空闲对象。如果没有全空的 slab ，从物理连续页上分配新的 slab 并分配给 cache，再从 slab 分配空间。

  • slab 分配器的两个主要优点：
    • 没有因碎片而引起的内存浪费
    • 可以快速满足内存请求