跳转至

8 Virtual Memory

8.1 Background

虚拟内存（Virtual Memory）是一种内存管理技术，它允许运行程序的只有部分被加载到内存中即可执行，从而提高了内存使用效率。

虚拟内存将用户的逻辑地址空间与物理内存分离，使得逻辑地址空间可以大于实际的物理地址空间，并支持多个进程共享物理地址空间，同时加快了进程的创建速度。

虚拟内存可以通过两种主要方式实现：

  • 按需调页（Demand Paging），即请求页式管理，仅在需要时将页面调入内存；
  • 请求段式管理（Demand Segmentation），根据程序的逻辑分段进行内存分配和管理。

局部性原理

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

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

虚拟存储器是具有请求调入功能和置换功能，仅把进程的一部分装入内存便可运行进程的存储管理系统，它能从逻辑上对内存容量进行扩充的一种虚拟的存储管理系统

8.2 Demand Paging

按需调页是一种虚拟内存管理技术，它只在某一页被实际访问时才将其从外存调入内存，而不是在进程开始执行前就将所有页面加载进来。这种方式具有多个优点：减少了 I/O 操作、降低了内存占用、加快了系统响应速度，并支持更多用户并发运行。

在按需调页机制中，页表的每个表项包含一个有效-无效位（valid–invalid bit）：

  • v（valid） 表示该页当前在内存中；
  • i（invalid） 表示该页尚未调入内存。

当 CPU 访问某个虚拟地址时，若对应页表项的有效位为 i，则触发缺页中断（page fault）。操作系统随后执行以下缺页处理步骤：

  1. 检查该地址引用是否合法（即是否属于进程的合法地址空间）；
  2. 若非法，终止进程；若合法但页未在内存中，则准备调入该页；
  3. 从空闲帧链表中分配一个物理帧；
  4. 启动磁盘 I/O 操作，将所需页面从外存读入该帧；
  5. 更新进程的页表及相关数据结构，标记该页已在内存中；
  6. 重新执行因缺页而中断的指令。

若内存中没有空闲帧，则需进行页面置换（page replacement）：选择一个不再使用或近期较少使用的页面换出到磁盘，腾出空间给新页。

按需调页的性能由有效内存访问时间（EAT）衡量，其公式为：

\[ \text{EAT}=(1−p)×\text{内存访问时间}+p×\text{缺页服务时间} \]

其中 \(p\) 为缺页率。由于缺页服务涉及磁盘 I/O，耗时远高于内存访问（例如内存访问为 200 纳秒，而缺页服务可能达 8 毫秒），即使缺页率很低（如 0.001），也会显著降低系统性能（如 EAT 增至 8200 纳秒，慢约 40 倍）。

8.3 Process Creation

写时拷贝（COW）是一种优化进程创建（尤其是通过 fork() 系统调用）的虚拟内存技术。在传统方式中，fork() 会为子进程复制父进程的整个地址空间，开销较大。而 COW 允许父进程和子进程在创建初期共享相同的物理内存页，从而显著提高效率。

当某一个进程要修改共享的内存页的时候，这个时候才进行页的复制。下图就是当进程1修改 page C 时发生的变化。

8.4 Page Replacement

在进程运行过程中，如果发生缺页，此时内存中又无空闲块时，为了保证进程能正常运行，就必须从内存中调出一页程序或数据送磁盘的交换区。将哪个页面调出，则须根据一定的页面置换算法来确定。

从理论上讲，应将那些以后不再被访问的页换出，或把那些在较长时间内不会再被访问的页换出。

利用“修改位”（dirty bit）可以来减少页面传输的开销，仅将被修改过的页面写回磁盘，提高效率。

此外，页面置换机制完成了逻辑内存与物理内存之间的完全分离，使得在较小的物理内存上可以提供较大的虚拟内存空间，增强了系统的内存使用灵活性和性能。

以上内容无论是在计算机体系结构还是计算机组成都有涉及

一些常用的页面置换算法，在这里也不再具体赘述

  • First-In-First-Out Algorithm (FIFO，先进先出算法)

  • Optimal Algorithm （OPT 最佳页面置换算法）

  • Least Recently Used (LRU) Algorithm (最近最久使用算法)

  • LRU Approximation Algorithms （近似LRU算法） ：

  • Additional-Reference-Bits Algorithm

  • Second-Chance（clock） Algorithm

  • Enhanced Second-Chance Algorithm

  • Counting-Base Page Replacement：

  • Least Frequently Used Algorithm (LFU最不经常使用算法）

  • Most Frequently Used Algorithm (MFU引用最多算法)

  • Page Buffering Algorithm（页面缓冲算法）

页面缓冲算法

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

被置换页面的选择和处理：用FIFO算法选择被置换页，把被置换的页面放入两个链表之一。

  • 如果页面未被修改，就将其归入到空闲页面链表的末尾，否则将其归入到已修改页面链表。

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

空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，这些页面还在内存中。

当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表。

8.5 Allocation of Frames

在虚拟内存系统中，帧分配策略决定了每个进程能获得多少物理内存帧。为确保进程正常运行，必须为其分配最少数量的页面，以容纳关键代码和数据。

常见的帧分配方案包括

  • 固定分配：每个进程获得固定数量的帧，实现简单但内存利用率低
  • 优先级分配：根据进程优先级动态分配帧，高优先级进程可抢占低优先级进程的帧，灵活性强但实现复杂。

关于固定分配也有两个算法

  • 平均分配算法（Equal Allocation）：所有进程获得相同数量的帧。例如，若有 100 个帧和 5 个进程，则每个进程分得 \(\frac{100}{5} = 20\) 个帧。这种方案实现简单，但未考虑进程大小差异，可能导致内存利用率不高。

  • 按比例分配算法（Proportional Allocation）：根据进程的大小（页数）按比例分配帧，以提高公平性和资源利用率。

优先级分配（Priority Allocation）采用类似按比例分配的思想，但将“进程大小”替换为“优先级”，即高优先级的进程可以获得更多的物理帧资源。当进程 \(P_i\) 发生缺页中断时，系统会优先考虑从该进程自身的帧中选择一个进行替换；如果需要更多帧，则会从优先级较低的进程的帧中挑选一个进行置换，从而确保高优先级进程获得更好的内存支持和响应性能。

Global vs. Local Allocation

置换策略：

Global replacement（全局置换） – process selects a replacement frame from the set of all frames; one process can take a frame from another

Local replacement （局部置换）– each process selects from only its own set of allocated frames

分配策略和置换策略可以组合成三种策略

  • 固定分配局部置换策略
  • 可变分配全局置换策略
  • 可变分配局部置换

8.6 Thrashing

当一个进程所分配的页面数量不足时，其缺页率会变得非常高，导致系统频繁进行页面置换。这种情况下，进程大部分时间都忙于将页面换入换出，而无法执行有效的工作，从而造成利用率低下。

操作系统可能误认为系统性能不佳是由于并发度不够，因而试图通过增加多道程序设计的道数或引入新的进程来提升效率，但实际上这会进一步加剧内存压力。这种现象被称为颠簸（Thrashing），即进程持续不断地在交换页面，导致CPU利用率下降、系统响应变慢，整体性能严重恶化。

为应对颠簸，操作系统可采取多种策略：

一是采用局部置换算法，限制进程只能替换自身页面，避免相互干扰；

二是依据 L=S 准则（缺页间隔时间 L 与缺页处理时间 S 相等时即为颠簸临界点）动态调整负载；

三是结合工作集模型，根据进程近期实际访问的页面集合为其分配足够帧数；

四是主动挂起部分低优先级或非活跃进程，减少并发度，释放内存资源。

介绍一下工作集模型

  • Δ：工作集窗口（working-set window）：表示最近 Δ 个页面引用。

  • 工作集 WS（Working Set）：最近 Δ 个引用的页集合。

  • \(WSS_i\)：进程 \(P_i\) 的工作集大小 = 最近 Δ 时间内引用的不同页面总数（随时间变化）

  • 若 Δ 过小 → 无法覆盖完整局部性区域
  • 若 Δ 过大 → 可能包含多个局部性区域

  • 若 Δ = ∞ → 包含整个程序

  • D = \(\Sigma \text{ WSS}_i\)：系统总需求帧数 \(m\)：系统可用帧总数

  • 若 D > m，则部分进程得不到足够帧，导致颠簸（Thrashing）解决方法为挂起部分进程，减少并发度，缓解内存压力

8.7 Memory-Mapped Files

内存映射文件（Memory-Mapped Files）是一种将磁盘文件直接映射到进程虚拟地址空间的技术，使得文件 I/O 操作可以像访问普通内存一样进行。

系统通过需求分页机制将文件的页面按需从磁盘加载到物理内存中：首次访问某部分文件时，操作系统会自动将其对应的数据块读入一个物理页框；之后对该区域的读写操作就直接作为内存访问处理，无需调用传统的 read() 或 write() 系统调用，从而简化了文件访问过程。

此外，多个进程可以映射同一个文件，实现对共享内存页的协同访问，支持高效的数据共享与同步。

如图所示，一开始加载的时候是加载如虚拟内存中，并没有加载到物理内存中。当多个进程（如进程A和B）映射同一文件时，操作系统按需将文件页（如页1、2、5等）加载到物理内存中，并让各进程的虚拟页指向对应的物理页框；若多个进程访问同一文件页（如文件页5）

8.8 Allocating Kernel Memory

内核内存的分配与用户内存不同，通常从一个专门的空闲内存池中进行管理。操作系统内核需要为各种数据结构（如进程控制块、页表、缓冲区等）动态申请大小不一的内存块，因此其分配机制需支持可变大小的请求。

某些内核操作（如DMA传输或硬件设备驱动）要求内存必须是连续的物理地址，这使得内核内存分配面临更高的约束。

因此，内核常采用专用的内存管理算法（如slab分配器、伙伴系统等），以高效满足不同大小和连续性要求的内存需求，确保系统稳定性和性能。

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！