5. 存储器管理

# 存储器管理概述

# 存储管理的挑战与起因

现代处理器能以很高的速度执行指令，因此处理器必须连接一个容量大、速度快的存储器。然而，设计一个足够大、足够快又足够便宜的单一存储器是不可能的。

• 容量问题：如果存储器容量太小，就不能装载足够的程序以保持处理器全力处理。
• 速度问题：如果存储器太慢，就不能像处理器执行指令那样快地提供指令和数据，导致处理器空等。
• 成本问题：大容量、高速度的存储器成本极其高昂。

# 存储器访问的局部性原理

操作系统和计算机体系结构通过利用“存储器访问的局部性原理”来解决上述挑战。该原理指出：处理器访问存储器时，无论取指令还是取数据，所访问的存储单元都趋向于聚集在一个较小的连续单元区域中。

• 时间局部性：最近的将来要用到的信息很可能就是现在正在使用的信息。这主要由程序中的循环造成。
• 空间局部性：最近的将来要用到的信息很可能与现在正在使用的信息在空间上是邻近的。这主要由代码的顺序执行和数据的聚集存放造成。

# 存储系统的层次结构

基于局部性原理，现代计算机大多采用多层次的存储结构，从上到下速度递减、容量递增、成本递减。典型结构为：寄存器 -> 高速缓存（Cache） -> 主存储器（内存） -> 辅助存储器（外存）。

• 工作方式：
  • 当前正在使用的指令或数据应存放在最高速的存储层（如高速缓存）。
  • 未来一段时间才会用到的指令或数据可以放在主存储器中。
  • 暂时用不到的程序或数据则存放在磁盘等辅助存储器中。
• 效果：如果大部分访问都能在高速缓存中命中，系统就能提供接近高速缓存的访问速度和接近辅助存储器的存储容量，给用户的感觉就像拥有一个又大又快的存储器。
• 常用存储介质：
  • 高速缓存：SRAM（常分为数据缓存、指令缓存）、TLB（Translation Lookaside Buffer，用于地址转换缓存）。
  • 内存：DRAM、SDRAM 等。
  • 外存：硬盘、固态硬盘（SSD）、光盘、磁带等。

# 存储管理的核心功能

操作系统的存储管理功能主要针对内存（主存储器）。外存属于设备管理范畴，而高速缓存（Cache）的管理通常由硬件直接完成，对操作系统软件是透明的。

内存管理的核心功能包括：

• 内存分配和回收
• 地址变换与重定位
• 内存保护
• 内存扩充

# 内存分配与回收

操作系统负责管理内存资源，需要设计高效的策略和数据结构来完成内存的分配与回收。

• 分配和回收时机：
  • 进程创建和结束时。
  • 进程运行过程中，如动态申请内存或栈空间变化。
  • 进程在内存与外存之间进行交换（中级调度）时。
  • 系统为优化空间利用率而进行内存整理时。
• 相关策略：
  • 调入策略：决定程序在何时调入内存，如请调（demand-paging）和预调（pre-paging）。
  • 放置策略：决定程序调入内存时，具体放置在哪个位置。
  • 置换策略：当内存空间不足时，决定将哪个程序或数据块从内存中移出。
• 分配数据结构：用于记录内存使用情况的数据结构，如空闲分区表、空闲分区链表、位图等。

# 地址变换与重定位

程序中使用的地址（逻辑地址）与内存中的物理地址通常是不同的，操作系统和硬件需要协同完成地址的转换。

• 地址空间：

  • 物理地址空间：内存中每个存储单元的唯一编号（物理地址或绝对地址）的集合。
  • 逻辑地址空间：用户程序中使用的地址（逻辑地址、相对地址或虚拟地址）的集合。其地址从 0 开始，相对于程序的起始位置编址。CPU 不能直接使用逻辑地址访问内存。

• 地址的生成过程：

  1. 名空间：程序员在代码中使用变量名、函数名等标识符，构成程序的名空间。此阶段没有地址概念。
  2. 相对地址空间：编译器将源代码编译成目标模块，每个模块的地址都从 0 开始，形成相对地址。
  3. 逻辑地址空间：链接器将多个目标模块和库函数链接成一个可执行文件，形成统一的逻辑地址空间。

• 地址变换与重定位：

  • 定义：将程序中的逻辑地址转换为内存中的物理地址的过程。
  • 原因：程序装入内存时，操作系统为其分配的物理地址与程序的逻辑地址（从0开始）不一致，CPU 访问内存必须使用物理地址，因此需要进行转换。

  

# 内存保护

在多道程序环境下，必须确保各个程序只能在自身被分配的内存区域内活动，互不干扰。

• 实现机制：

  • 通常在 CPU 中设置一对基址寄存器和限长寄存器。基址寄存器存放程序在内存中的起始地址，限长寄存器存放程序的长度。
  • 也可以使用上限寄存器和下限寄存器来界定程序的内存范围。

• 工作流程：

  • CPU 每次访问内存时，硬件会自动检查目标物理地址是否在界限寄存器规定的范围内。
  • 若地址合法（未越界），则正常访问。
  • 若地址非法（越界），硬件会产生一个陷阱（Trap），触发操作系统的越界中断处理程序，通常会终止该进程。

  

• 共享：内存保护机制的扩展功能。在确保安全的前提下，允许多个进程访问同一块内存区域，以实现代码或数据的共享，提高内存利用率。

# 内存扩充

内存扩充技术旨在让用户程序感觉拥有比实际物理内存更大的存储空间，使得大程序也能在小内存上运行。

• 由应用程序控制：覆盖技术（Overlay）

  • 思想：将程序手动分割成若干功能上相对独立的程序段（覆盖块）。程序运行时，只将需要的覆盖块调入内存。当一个覆盖块执行完毕后，再调入后续的覆盖块，覆盖掉前一个。
  • 实现：程序员必须明确程序的逻辑结构，并组织覆盖关系。操作系统仅提供调入/换出服务。

  

• 由操作系统控制：交换与虚拟存储

  • 交换技术（Swapping）

    • 思想：将内存中暂时不能运行的进程（如阻塞态）的整个地址空间保存到外存的交换区，从而释放内存空间给其他具备运行条件的进程。之后，被换出的进程可被再次换入内存继续执行。这是一种进程级别的内存-外存动态调度（中级调度）。
    • 特点：主要用于早期的分时系统，需要一个高速的磁盘交换区。

    

  • 虚拟存储技术（Virtual Memory）

    • 思想：利用局部性原理，程序装入时只将当前需要运行的部分页面或段装入内存，其余部分留在外存。当需要访问尚未在内存中的部分时，由操作系统负责将其调入内存。
    • 效果：为用户提供一个远大于物理内存的虚拟地址空间，程序员编程时无需关心物理内存的大小限制。地址转换由操作系统和硬件（MMU）自动完成。

    

# 程序的链接与装入

一个用户源程序从代码到最终在内存中执行，需要经历编译、链接和装入三个步骤。

• 编译（Compilation）：由编译器将用户源代码（如 C++ 文件）转换成若干个目标模块（如 .o 文件）。
• 链接（Linking）：由链接器将多个目标模块以及它们所需的库函数组合起来，解决符号引用，形成一个完整的、统一逻辑地址空间的可执行文件（装入模块）。
• 装入（Loading）：由装入程序将可执行文件从外存装入内存。

# 程序链接方式

• 静态链接：在程序运行前，链接器将所有目标模块一次性链接成一个完整的可执行文件。
• 装入时动态链接：在程序被装入内存时，边装入边完成链接。便于模块的修改和更新，也便于实现共享。
• 运行时动态链接：在程序执行过程中，当需要某个模块时才对其进行链接。可以节省内存空间，但实现更复杂。

# 程序装入方式

• 绝对装入（Absolute Loading）

  • 方式：在编译时就确定程序在内存中的物理地址。装入时直接将程序放置到该指定地址。
  • 缺点：灵活性差，只适用于单道程序环境。

• 可重定位装入（Relocatable Loading）

  • 方式：程序装入内存时，根据分配到的起始地址，对程序中的所有逻辑地址进行一次性的地址转换（重定位），将其变为物理地址。程序运行期间地址不再改变。
  • 缺点：要求为程序分配连续的内存空间；程序一旦装入内存后不能再移动。

  

• 动态运行时装入（Dynamic Run-time Loading）

  • 方式：程序装入内存后，其地址仍然是逻辑地址。真正的地址转换推迟到程序运行时，每当访问内存时由硬件（MMU）进行动态转换。
  • 优点：程序可以被放置在内存的任何位置，也可以在内存中移动；可以离散地存放在不连续的内存区域；是实现虚拟存储的基础。
  • 缺点：需要硬件地址变换机构的支持。

  

# 连续分配存储管理

连续分配是指为一个用户程序分配一个连续完整的物理内存空间。

# 单一连续区存储管理

这是最简单的存储管理方式，将内存划分为两个区域：系统区和用户区。

• 特点：

  • 应用程序装入到唯一的用户区，并可使用该区的全部空间。
  • 适用于单用户、单任务的操作系统（如 MS-DOS）。

• 内存布局：

  

• 优点：实现简单，开销小。

• 缺点：内存利用率低，若程序小于用户区空间，会造成浪费；不支持多道程序。

# 分区存储管理

为了在内存中同时运行多道程序，将用户区内存划分为若干个分区，每个进程占用一个分区。

# 基本思想与碎片问题

• 内碎片：分配给进程的分区大于进程的实际需求，分区内部未被利用的空间。
• 外碎片：分区之间存在的一些过小的、难以利用的空闲分区。

分区存储管理可分为固定分区和动态分区两种。

# 固定分区

系统预先把内存划分为若干个大小固定的分区。

• 分区方式：

  • 分区大小相等：适用于多个相同大小的程序并发执行。分配简单，但空间浪费严重。
  • 分区大小不等：划分出多个小分区、适量的中等分区和少量的大分区，根据程序大小分配最合适的空闲分区。

• 管理方式：系统通过分区表来记录每个分区的起始地址、大小和状态（是否空闲）。

  

  

• 特点：

  • 优点：实现简单，开销小。
  • 缺点：存在严重的内碎片，无法消除；分区总数固定，限制了并发执行的程序数目。

# 动态分区

不预先划分分区，而是在进程需要装入时，根据其大小动态地从空闲内存中分割出一个分区。

• 特点：
  • 分区的大小和数量是可变的。
  • 消除了内碎片，但会产生外碎片。
• 空闲空间管理方法：

  • 位图（Bitmap）：将内存划分为小的分配单元，用一位（bit）来表示一个单元的状态（0表示空闲，1表示占用）。分配时需要查找连续的k个0。

    

  • 空闲链表（Free List）：将所有空闲分区通过链表连接起来，每个链表节点记录一个空闲区的起始地址、长度和指向下一个节点的指针。

    

# 动态分区分配算法

当一个进程请求内存时，系统需要从空闲分区链表中选择一个合适的分区进行分配。

• 首次适配算法（First-Fit）：从链表头开始查找，选择第一个大小足够的空闲分区分割。
  • 优点：算法简单，速度快，倾向于在内存低地址保留大空闲区。
  • 缺点：低地址空间容易产生大量外碎片。
• 下次适配算法（Next-Fit）：从上次分配位置的下一个空闲分区开始查找。
  • 优点：空闲分区分布更均匀，查找开销小。
  • 缺点：不容易保留大的空闲分区。
• 最佳适配算法（Best-Fit）：遍历整个链表，选择大小与请求最接近（最小且足够）的空闲分区。
  • 优点：外碎片较小。
  • 缺点：容易产生许多极小的、难以利用的碎片。
• 最坏适配算法（Worst-Fit）：遍历整个链表，选择最大的空闲分区进行分配。
  • 优点：剩余的空闲区较大，不易产生小碎片。
  • 缺点：大分区被快速消耗，不利于后续大进程的分配。

# 内存紧缩（Memory Compaction）

为解决外碎片问题，系统可以移动内存中的所有进程，使它们都紧凑地排列在一端，从而将所有小的空闲分区合并成一个大的空闲区。

• 缺点：非常耗时，且要求程序支持动态重定位。

# 分区管理的地址变换

分区管理采用动态运行时装入，需要硬件支持。

• 重定位寄存器（基址寄存器）：存放进程在内存中的起始物理地址。
• 地址变换过程：CPU 产生的逻辑地址 + 重定位寄存器的值 = 物理地址。

# 伙伴系统（Buddy System）

这是一种介于固定分区和动态分区之间的技术，试图综合两者的优点。

• 基本思想：

  • 内存空间的大小必须是 $2$ 的幂次，如 $2^m$。
  • 当需要为进程分配空间时，系统将一个大分区递归地对半分割，直到产生一个大小刚好满足（大于等于并最接近）请求的分区。
  • 两个大小相同、地址连续且由同一个大分区对半分割而来的分区互为伙伴。
  • 当一个分区被释放时，系统会检查其伙伴是否也空闲，如果是，则将两者合并成一个更大的分区，并递归此过程。

• 管理方式：系统维护多个空闲链表，每个链表负责一种大小为 $2^k$ 的空闲分区。

  

• 伙伴地址计算：对于大小为 $2^k$，地址为 x 的内存块，其伙伴块的地址为：

  $$buddy_k(x)=\begin{cases}x+2^k, & \text{if } x \pmod{2^{k+1}} = 0 \\ x-2^k, & \text{if } x \pmod{2^{k+1}} = 2^k \end{cases}$$

• 优缺点：

  • 优点：分配和回收速度快，能有效减少外碎片。
  • 缺点：由于分配大小必须是 $2$ 的幂次，会产生内碎片。

# 非连续分配存储管理

允许将一个进程的程序和数据离散地存储在多个不相邻的内存区域中，以克服连续分配的缺点。

# 基本思想

非连续分配技术主要包括：

• 页式存储管理（Paging）：将进程的逻辑地址空间和物理内存都划分为大小固定的块（页和页框），以页为单位进行分配。
• 段式存储管理（Segmentation）：按程序的逻辑结构（如代码段、数据段）划分，每段的长度可变。
• 段页式存储管理（Segmentation with Paging）：结合上述两种方式，先分段，再对每段分页。

# 页式存储管理

# 基本原理

• 页（Page）：进程的逻辑地址空间被划分为大小相等的块。
• 页框（Page Frame）：物理内存被划分为与页大小相等的块。
• 分配方式：以页为单位进行内存分配，进程的各个页可以离散地存放在物理内存的任意可用页框中。
• 页表（Page Table）：系统为每个进程维护一个页表，记录逻辑页号到物理页框号的映射关系。
• 地址结构：
  • 逻辑地址分为两部分：逻辑页号 (p) 和 页内偏移 (d)。
  • 物理地址分为两部分：物理页框号 (f) 和 页内偏移 (d)。
  • 地址转换的核心就是通过页表找到 p 对应的 f。页内偏移在转换过程中保持不变。

# 实存页式存储管理

也称为简单分页，要求进程的所有页面在运行前一次性全部装入内存。

• 地址结构计算：

  • 设逻辑地址为 A，页面大小为 L (通常为 $2$ 的幂次)。
  • 逻辑页号 $P = \lfloor A / L \rfloor$
  • 页内偏移 $d = A \pmod L$

• 核心数据结构：

  • 进程页表：存放本进程的“逻辑页号 -> 物理页框号”映射。
  • 物理页框表：整个系统一张，记录所有物理页框的使用情况（可用位图或链表实现）。
  • 请求表：记录系统中每个进程页表的位置和大小。

  

• 地址变换过程：

  1. CPU 产生逻辑地址，硬件（MMU）将其分解为页号 p 和偏移 d。
  2. 系统访问页表寄存器（PTR），获取当前进程页表的基地址和长度。
  3. 用页号 p 作为索引，在页表中查找对应的页表项（地址为：页表基地址 + p * 页表项大小）。
  4. 从页表项中取出物理页框号 f。
  5. 将页框号 f 和偏移 d 拼接成最终的物理地址（物理地址 = f * 页面大小 + d）。

  

• 硬件支持：快表（TLB）

  • 问题：上述地址变换过程需要访问内存两次（一次访问页表，一次访问目标数据），效率较低。
  • 解决方案：引入一个基于高速相联存储器（Cache）的快表（Translation Lookaside Buffer, TLB），用于缓存最近访问过的页表项。
  • 带快表的地址变换：
    1. 根据页号 p 查找快表。
    2. 命中（Hit）：若在快表中找到，直接获取页框号 f，完成地址转换（只需一次访存）。
    3. 缺失（Miss）：若快表中未找到，则正常查询内存中的页表，获取页框号 f，并同时将该页表项更新到快表中，以备后续使用（需要两次访存）。

• 多级页表

  • 问题：对于具有巨大地址空间的进程，页表本身可能非常大，难以找到连续的内存空间存放。
  • 解决方案：将页表本身也进行分页管理。将页表分页后，建立上一级的页表来索引这些页面，形成二级或多级页表结构。例如，二级页表将逻辑地址分为：页目录索引、页表索引和页内偏移。

  

• 优缺点总结：

  • 优点：
    • 没有外碎片，内碎片最多为一个页的大小。
    • 程序不必连续存放，内存利用率高。
  • 缺点：
    • 仍要求程序一次性全部装入内存，无法运行超过物理内存大小的程序。
    • 实现共享困难，因为一个页面中可能混合了共享和私有数据。

# 虚拟页式存储管理

在简单页式管理的基础上，引入请求调页和页面置换功能，是现代操作系统最核心的内存管理技术。

• 虚拟存储器基本概念：

  • 定义：为用户提供一个远大于物理内存的、可寻址的逻辑地址空间（虚拟地址空间）。
  • 原理：基于局部性原理，程序运行时只将部分活跃页面装入内存，其余留在外存。当需要访问的页面不在内存时，通过缺页中断机制将其从外存调入。
  • 好处：
    • 运行大程序：可在较小内存中运行大程序。
    • 提高并发度：可在内存中容纳更多进程并发执行。

  

• 实现原理与缺页中断

  • 页表项扩展：为支持虚拟存储，页表项中需增加额外标志位：
    • 存在位/驻留位（Present Bit）：表示该页是否在内存中。1表示在，0表示不在。
    • 修改位（Modified/Dirty Bit）：表示该页调入内存后是否被修改过。
    • 访问位（Accessed/Referenced Bit）：记录该页最近是否被访问过，用于页面置换。
    • 外存地址：指出该页在外存（如磁盘交换区）的位置。
  • 缺页中断（Page Fault）：
    1. CPU 访问一个逻辑地址，MMU 进行地址转换。
    2. MMU 发现对应页表项的存在位为 0，表示该页不在内存中。
    3. MMU 产生缺页中断，将控制权交给操作系统。
    4. 操作系统中断处理程序：
       a. 找到该页在外存的位置。
       b. 在内存中寻找一个空闲页框。若无空闲，则执行页面置换算法，选择一个页面换出。
       c. 将目标页面从外存读入该页框。
       d. 更新页表（修改存在位、物理页框号等）。
       e. 返回到被中断的指令处，重新执行。

• 页面调入策略

  • 请求调页（Demand Paging）：仅在发生缺页时才调入所需的页面。实现简单，但I/O开销大。
  • 预先调页（Prepaging）：根据预测，提前将可能要用到的页面调入内存。可能减少缺页中断，但若预测不准会造成浪费。

• 页面分配策略

  • 固定分配：为每个进程分配固定数量的页框，运行期间不变。
  • 可变分配：根据进程运行时的缺页率动态调整其分配的页框数。

• 页面置換策略
  当发生缺页且无空闲页框时，需选择一个内存中的页面将其换出。置换算法的优劣直接影响系统性能。

  • 目标与抖动问题：理想的算法是换出未来最长时间内不会被访问的页面。如果算法不当，可能导致频繁地换入换出同一页面，造成系统性能急剧下降，这种现象称为抖动（Thrashing）。

  • 常用算法：

    • 最优置换算法（OPT）：置换未来最长时间内不会被访问的页面。这是一种理想算法，无法实现，仅用作性能评估的基准。
    • 最近未使用算法（NRU）：根据访问位（R）和修改位（M）将页面分为四类，优先淘汰未访问、未修改的页面。
    • 先进先出算法（FIFO）：置换最早进入内存的页面。简单但性能差，可能换出常用页，并存在 Belady 异常（分配页框增多，缺页率反而上升的现象）。
    • 第二次机会算法：对 FIFO 的改进。检查最老页面的访问位 R，若为 0 则替换；若为 1，则将其 R 位清 0 并移到队尾，给予“第二次机会”。
    • 时钟算法（Clock）：第二次机会算法的环形链表实现，效率更高。
    • 最近最少使用算法（LRU）：置换最长时间未被使用的页面。性能接近 OPT，但硬件实现开销大。
    • 最不常用算法（NFU）：用软件计数器模拟 LRU，每次时钟中断时，给被访问页的计数器加 1，置换计数值最小的页。
    • 老化算法（Aging）：对 NFU 的改进。计数器定期右移一位，并将 R 位加到最高位，能更好地模拟“时间”的流逝。

    

• 工作集模型（Working Set）

  • 思想：一个进程在某段时间内集中访问的页面集合称为其工作集。如果系统能为进程分配足够容纳其工作集的页框，就可以显著降低缺页率，避免抖动。
  • 应用：通过监控进程的工作集大小来动态调整其分配的页框数。

  

• 页面清除策略
  决定何时将修改过的页面写回外存。

  • 请求清除：仅在页面被选中换出时才写回。
  • 预清除：系统周期性地将修改过的页面写回外存，但页面本身仍保留在内存中。
  • 页缓冲：维护一个已修改和未修改的空闲页框队列，优化 I/O 操作。

• 页面置换算法小结

算法	评价
OPT	不可实现，用于基准测试
NRU	非常简陋
FIFO	可能替换掉重要的页，性能差
二次机会	对 FIFO 的重大改进
CLOCK	等价于二次机会，实现更高效
LRU	性能优异，但硬件实现代价大
老化 (Aging)	有效近似 LRU 的算法，实现可行
工作集	理论优秀，但实现代价较大

# 段式与段页式存储管理

• 段式存储管理（Segmentation）
  • 思想：按程序的逻辑结构划分地址空间，如代码段、数据段、堆栈段等。每个段的大小可变，有独立的段号。
  • 地址结构：逻辑地址由 段号 (s) 和 段内偏移 (d) 组成。
  • 特点：便于实现共享和保护，但会产生外碎片。该技术在现代通用操作系统中已较少单独使用。
• 段页式存储管理（Segmentation with Paging）
  • 思想：结合分段和分页的优点。先将逻辑地址空间分段，再将每个段分页。
  • 地址结构：逻辑地址由 段号 (s)、段内页号 (p) 和 页内偏移 (d) 组成。
  • 应用：主要在 x86 架构中得到硬件支持。但现代操作系统（如 Windows, Linux）在使用 x86 架构时，通常采用“平坦模型”，将段基址设为 0，段限长设为最大值，从而绕过分段机制，实质上只使用分页管理。

# 实存与虚拟页式存储管理对比

特性	实存页式存储管理	虚拟页式存储管理
存储介质	仅使用物理内存	物理内存 + 磁盘（作为后备存储）
程序大小限制	进程大小 ≤ 物理内存	可运行远大于物理内存的程序
缺页中断	无	有，是实现虚拟存储的核心机制
页面置换	无	有（如 LRU、FIFO 等算法）
应用场景	嵌入式系统、部分实时系统	现代通用操作系统（Windows、Linux、macOS等）