内存管理

• 1: 内存管理概念
• 2: 虚拟内存管理

# 内存管理

## 基础

- 基本概念：虚拟和逻辑地址，地址转换，内存共享，内存保护，内存分配和回收
- 连续分配管理方式
- 页式管理
- 段式管理
- 段页式管理

## 虚拟内存

- 基本概念
- 请求页式管理
- 页框分配
- 页置换算法
- 内存映射文件
- 虚拟存储器性能的影响因素和改进方法

1 - 内存管理概念

内存管理的基本概念

• 逻辑地址和物理地址空间
• 地址变换
• 内存共享

共享内存（Shared Memory）是多个进程共享的内存区域。它是最快的IPC（进程间通信）机制之一，因为进程直接读写内存，无需进入内核态。但是，因为多个进程可以同时访问这些内存，所以可能需要某种同步机制（如信号量）来防止竞态条件。

• 内存保护

内存保护是现代操作系统中的一个核心功能，用于防止一个进程访问另一个进程的内存空间。这不仅保障了系统的稳定性，而且提高了安全性，因为它可以防止恶意软件损害其他进程或篡改其数据。

可以通过如下机制实现内存保护机制：

1. 分段与分页:
   • 分段: 内存被划分为不同的段，每个段都有其起始地址和长度。段常常用于表示高级的数据结构，如函数或对象。
   • 分页: 内存被划分为固定大小的页面，例如4KB。操作系统为每个进程维护一个页表，来映射其虚拟地址到物理地址。
2. 访问权限: 每个段或页面都有与之相关的访问权限。例如，一个页面可能被标记为只读，这意味着任何尝试写入该页面的操作都会引发一个异常。
3. 隔离: 由于每个进程都有其独立的地址空间，所以一个进程不能直接访问另一个进程的内存。这为每个进程提供了一种形式的隔离，确保了一个出错的进程不会影响其他进程。

连续分配管理方式

单一连续分配

内存在此方式下分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分；在用户区内存中，仅有一道用户程序，即整个内存的用户空间都由该程序独占。

这种方式的优点是简单、无外部碎片，无需进行内存保护，因为内存中永远只有一道程序。缺点是只能用于单用户、单任务的操作系统中，存储器的利用率极低。

固定分区分配

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该内存，如此循环。

为了方便内存分配，通常将分区按大小排队，并为之建立一张分区说明表，其中各表项包含每个分区的起始地址、大小和状态。当有用户程序需要装入时，便检索该表，以找到合适的分区基于分配并将其状态设置为“已分配”；未找到合适分区时，则拒绝为给程序分配内存。

动态分区分配

动态分区分配的含义就是将内存看成一整块连续的区域，每次分配的时候直接从其中的空闲区域申请一块内存即可。

申请过的内存可以释放掉，成为空闲内存的一部分，释放后的内存可以被其他进程所用。

通过对一段连续的内存进行动态地分配，内存中的区域可以从逻辑上被划分为空闲和占用两个部分。下图中的内核内存（kernel memory）以及进程内存（process memory）就是被占用的内存。

操作系统可以通过一个表格的形式来记录以上空闲内存的大小和起始地址：

当进程申请内存时，操作系统会遍历空闲块表，根据设定的[#算法]选择出空闲块，然后为进程分配所需的内存空间。

内存碎片

由于每块进程申请的内存大小不同，所以在分配的内存之间可能出现内存碎片。

内存碎片就是大小比较小的空闲块，无法被其他进程再利用（进程不会申请这么小的空间）。

算法

适应算法

内存空间中的空闲区域可能大小不一，且分布在内存中不同的位置，操作系统使用空闲块表来记录这些空闲区域的信息。

当进程申请一块新的内存时，必须从已有的空闲空间中选出一块分配给进程。动态分区的分配策略主要包含四种算法：first fit、next fit、best fit、worst fit。

• First Fit（首次适应）：遍历空闲块表，找到第一个足够的空闲块分配给进程。
• Next Fit（临近适应）：遍历空闲块表，找到第二个足够的空闲块分配给进程。
• Best Fit（最佳适应）：遍历空闲块表，找到一个利用率最高的空闲块给进程。
• Worst Fit（最坏适应）：与最佳适应的目标相反，找到一个利用率最低的空闲块给进程。

上图中内存中有 6 个空闲块，其大小分别为 8, 22, 20, 14, 10, 24，当进程申请一段大小为 16 的内存时，不同的算法会分别定位到不同的内存块：

• First Fit：从上到下遍历空闲块，22 是第一个可以容纳 16 的块，选择 22。
• Next Fit：20 是第二个可以容纳 16 的快，选择 20。
• Best Fit：20 是能容纳 16 且利用率最高的块，利用率 = 16 / 20 = 80%，选择 20。
• Best Fit：24 是能容纳 16 且利用率最低的块，利用率 = 16 / 24 ≈ 66.7%，选择 24。

伙伴算法

伙伴算法（Buddy Algorithm）将内存分为大小为2的幂次方的块（例如，1KB、2KB、4KB、8KB等）。当需要分配内存时，算法寻找合适的块；如果没有合适的块，就将更大的块一分为二，直到满足需求。释放内存时，算法尝试将相邻的“伙伴”块合并为更大的块，以减少内存碎片。

内存分配过程

• 假设需要分配大小为 $S$ 的内存，算法找到最小的大小为 $2^n$（n为正整数）块，使得$2^n \ge S$。
  • 如果有，直接分配该块。
  • 如果没有，查找更大一级（$2^{(n+1)}$）的空闲块，将其一分为二，生成两个 $2^n$ 的伙伴块：
    • 一个用于分配。
    • 另一个加入 $2^n$ 的空闲链表。
  • 如果 $2^{(n+1)}$ 也没有空闲块，继续向上查找，直到找到合适大小的块或失败。 分配后更新空闲链表。

下图包含一个使用伙伴算法的内存分配实例：

内存释放过程

• 释放一块内存时，检查其“伙伴”块是否也空闲：
  • 伙伴块是指与当前块大小相同、地址相邻、且由同一父块分割而来的块。
  • 例如，地址为 $A$ 的 $2^n$ 块，其伙伴地址为 $A ± 2^n$（具体取决于地址对齐）。
• 如果伙伴块空闲，合并为一个 $2^{(n+1)}$ 的块，并加入更高一级的空闲链表。
• 重复检查合并，直到无法合并（伙伴不空闲或达到最大块大小）。

伙伴关系

伙伴块的地址满足特定关系。例如，假设内存起始地址为 0，块大小为$2^n$，则地址 $A$ 的伙伴地址为 $A ⊕ 2^n$（按位异或）。 通过这种关系，算法可以快速定位伙伴块。

页式管理

页式管理的细节详见 组成原理中的对应章，这里仅给出基本的思想以与段式管理和段页式管理进行对比。

页式内存管理的基本思想是将虚拟内存和物理内存分为若干个大小固定的页面，然后通过页表建立从虚拟页面到物理页面的映射，这样进程就可以离散地 使用物理内存中的不同页面。

段式管理

段式内存管理将程序的不同部分（例如代码、数据和堆栈）划分为不同的段（segments）。每个段在物理内存中可以不连续，但在逻辑上都被视为连续的。

段式管理的主要优点是它比较简单，有助于提供更好的保护和共享机制，在 8086 CPU 中使用的内存管理策略就是段式管理。

下文介绍一下段式内存管理中的三个关键概念：段、段表 以及 如何进行地址转化。

段定义

• 每个段都有一个明确的角色，例如代码段、数据段或堆栈段。
• 每个段都有一个起始地址和长度。
• 段内的地址是连续的，但不同段之间的地址可以不连续。

段表

• 段表是一种数据结构，用于存储每个段的基地址（在物理内存中的起始地址）和限制（段的长度或末尾地址）。
• 当一个程序需要访问其内存段时，会使用段号和段内偏移作为地址。这个地址被称为逻辑地址或段地址。
• 逻辑地址通过段表转换为物理地址。

地址转换

• 为了从逻辑地址获取物理地址，首先需要从逻辑地址中提取段号，然后使用段号在段表中查找相应的基地址和限制。
• 然后，检查逻辑地址中的偏移量是否小于该段的限制。如果偏移量超出限制，则产生段越界错误。
• 如果偏移量有效，则将偏移量加到段的基地址上，得到物理地址。

段页式管理

段页式管理（paged segmentation）是一种将段式内存管理与分页式内存管理相结合的策略。 在段页式管理中，程序首先被划分为逻辑上的段，然后每个段进一步被划分为固定大小的页。 首先，操作系统通过段表对不同的段进行管理。 在每一个段的内部，采用分页的方式将段分为不同的页，实现虚拟页面到物理页面的映射。

在使用段页式内存管理的策略时，虚拟地址可以拆分为三个部分：段号（Segment No）、页号（Page No）、页内偏移（Offset）。

在地址翻译的过程中，首先通过虚拟地址中的段号在段表中找到页表的起始地址，接下来再通过页号在页表中找到该地址对应的物理页面号。

它结合了两者的优势，旨在提供灵活性和减少内存碎片。

2 - 虚拟内存管理

页框分配

在虚拟内存管理中，页框分配是操作系统为进程分配物理内存（页框）的过程。 它直接影响着系统的性能，因为分配的页框数量会影响进程的缺页率和系统的整体吞吐量。

驻留集大小

驻留集是指当前在物理内存中实际驻留的进程页面的集合。驻留集大小是表示这个集合中页面数量的指标，通常以页框（或页面框）的数量来度量。这个指标决定了进程可以直接访问的物理内存页面数量，以及在物理内存中保持的页面的范围。

驻留集大小的合理设置对系统性能至关重要。如果驻留集大小太小，进程可能经常发生页面置换，导致频繁的缺页中断，从而降低性能。如果驻留集大小太大，可能会浪费物理内存资源，并导致其他进程无法获得足够的内存。

抖动

抖动（Thrashing）是指操作系统中频繁发生的页面置换现象，即刚被换出的页面马上又要被换入内存，刚被换入的页面马上又要被换出外存，导致系统大部分时间都用于页面的换入换出，而真正用于进程运行的时间很少。

当系统为一个进程分配的物理内存不足以满足其工作集（当前活跃的页面集合）的需求时，就会频繁发生缺页中断。操作系统必须不停地从磁盘读取所需的页面到内存中，同时写出其他页面以释放空间。因为磁盘访问速度远慢于内存访问，这种频繁的磁盘 I/O 活动显著减慢了系统性能。

抖动的直接后果是 CPU 使用率下降，因为 CPU 在等待必要的页面从磁盘加载时处于空闲状态。系统资源被过多地用于管理内存和磁盘之间的数据交换，而非执行用户程序。抖动严重时，系统的吞吐量下降，响应时间增加，用户和应用程序都会感受到系统变得迟钝和无响应。

内存分配策略

内存分配策略包含 固定分配 和 可变分配 两种方式：

• 固定分配
  • 内存被划分为固定大小的区块。
  • 每个程序或进程被分配一个或多个这样的区块，不管它们实际上需要多少内存。
• 可变分配
  • 内存不是被划分为固定大小的区块，而是根据每个程序的需求动态分配。
  • 当一个程序请求内存时，操作系统查看可用内存并分配足够的连续空间给该程序，这个空间刚好满足其需求。

固定分配中可以分为两种方式， 一种是将内存分为若干大小相同的分区， 另一种是将内存分为大小不同的分区。

可变分配也包含两种分配方式， 一种就是将 内存分为若干页面，然后根据进程的需求为其动态地分配内存页面。 另一种思路与 动态分区分配 一致，在一块连续的内存上动态地申请连续的某个长度的存储空间。

内存置换策略

内存置换策略分为 局部置换 和 全局置换两种。

局部置换策略是指在选择要换出的页面时，仅限于该进程自身所拥有的内存页面范围内进行选择。 也就是说，一个进程的缺页不会影响到其他进程的内存页面。

全局置换策略是指在选择要换出的页面时，可以在整个系统的内存页面范围内进行选择。 也就是说，一个进程的缺页可能会导致其他进程的内存页面被换出。

页置换算法

在操作系统中，进程运行时，如果它要访问的页面不在内存中，就会产生缺页中断。 这时，操作系统需要从磁盘中将该页面调入内存。 但如果此时内存已满，操作系统就需要选择一个页面将其移出内存，以便为新页面腾出空间。 这个选择要移出哪个页面的算法，就叫做页面置换算法。

FIFO

FIFO（First-In-First-Out）页面置换算这是最简单的页面置换算法。 它总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面。

FIFO 的实现方法是把调入内存的页面按先后顺序放入队列中，当需要置换页面时，选择队头的页面即可。

OPT

OPT（Optimal）页面置换算法，也称为最佳页面置换算法，是一种理论上的页面置换算法， 其目标是选择最佳的页面来置换，以最大程度地减少未来的页面访问次数。、

那么什么叫做最佳的置换页面呢？OPT 算法假设你可以预知未来，即你可以知道当前进程驻留集中的哪个页面 是在将来最早会被替换的（在驻留集中停留的时间最短），也就是说，你需要知道未来的页面访问序列。

但这在实际情况下是不可能的， 因此 OPT 算法通常用于理论研究和性能评估，以作为其他页面置换算法的性能上限的比较基准。

OPT 页面置换算法的例子：

加入内存系统中有 3 个页框，页面引用序列为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2，则置换页面如下：

内存置换次数为 4，缺页率为 4/12 = 1/3

LRU

LRU（Least Recently Used）基于最近的页面访问历史来决定哪个页面应该被置换出内存。

LRU 算法是基于时间局部性思想：如果一个页面在最近被使用的话，那么这个页面在将来很可能被再次使用。 所以 LRU 算法会选择 最近一直没有被使用的页面 进行替换。

如果内存中包含 3 个页面，A 页面在 1 分钟前被使用过，B 页面在 2 分钟前被使用过，C 页面在三分钟前被使用过。 那么在这种情况下，LRU 算法会优先替换 C 页面，因为该页面上次使用的使用的时间距离现在最远。

我们可以使用一个队列来保存内存中的页面，最近被使用过的页面放在队列尾部，表示这些页面不会优先被替换。 最近没使用过的页面会放在队列头部，表示这些页面会优先被替换。 基于这种思路，LRU 算法可以用如下过程进行描述：

假设内存中 Mem 最多可以容纳 N 个页面（将其看成一个长度最大为 N 的队列），当访问一个页面 P 时：

• 如果 P 在队列中出现
  • 将 P 移动到队列末尾
• 如果 P 不在队列中
  • 如果队列没有满的话，将 P 加入队列末尾
  • 如果队列满的话，将队列头部的页面淘汰，并且将 P 加入队列末尾

在上图中，当进程访问 C 页面时，发现 C 页面出现在其驻留集中，所以需要将 C 移动到队列尾部， 这样刚刚访问过的 C 页面的淘汰优先级就会降到最低。

LRU 算法的例子：

加入内存系统中有 3 个页框，页面引用序列为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2，则置换页面如下：

内存置换次数为 6，缺页率为 6/12 = 1/2

Clock

根据 LRU 代码实现 可知，用代码实现一个高效的 LRU 算法需要用到一个散列表和一个基于链表的队列， 这从软件层面实现不算特别复杂，但若是要用硬件实现相应的逻辑则不大容易。

Clock 算法的提出是为了解决 LRU 算法在硬件实现上的复杂性，该算法流程相比 LRU 更加简单， 可以更高效地使用硬件电路进行实现。

此外，Clock 算法的目的与 LRU 算法类似：保证最近刚访问过的页面可以在将来尽量晚被淘汰。

简单 Clock

CLOCK 算法的核心思想是使用一个类似时钟的数据结构，以跟踪每个页面的访问状态。

页面的访问状态用一个比特位（访问位）来表示：

• 0 表示该页面未分配 或者 已分配但可以被替换
• 1 表示该页面已分配但不可被替换

初始情况下进程的所有页面都未被分配，所有页面的访问位都为 0。

当一个新页面被添加时，时钟中的指针会不断旋转，直到找到一个访问位为 0 的页面将其替换。 如果当前页面的访问位为 1，则将其设置为 0，并移动到下一个位置进行查找。

在实际的 Clock 算法实现中，我们需要使用一种可以循环遍历的数据结构来模拟时钟结构。常用的选择是数组或循环链表。 数组和链表中的每个元素都需要记录 访问位 和 页面号。

Clock 替换策略如下：

假设内存最多可以容纳 N 个页面，我们可以用一个长度为 N 的数组来作为作为数据结构来模拟时钟， 当访问一个页面 P 时：

• 如果 P 在数组中出现
  • 将 P 的引用为标记为 1
• 如果 P 不在数组中，判断指针指向的页面引用位的数值
  • 引用位为 0，则替换该页面，并将指针移动到下一个位置
  • 引用位为 1，将该页面的引用位置为 0，将指针移动到下一个位置继续判定

那么 clock 算法是如何保证最近访问过的页面尽量晚被淘汰呢？这主要包含两点：

1. 若访问的页面在时钟中存在，则将该页面的访问位设置为 1，这可以保证这个页面尽量晚被淘汰。
2. 若访问的是新页面（在时钟中不存在），找到一个可替换的页面，将新页面加载到这个位置，并将新页面的访问位 设置为 1，这可以保证新页面尽量晚被淘汰。

简单 Clock 算法的例子：

加入内存系统中有 3 个页框，页面引用序列为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2，内存页框初始状态为 -1:0, -1:0, -1:0（粗体表示时钟指针指向的位置，引号前面的-1 表示当前页面为空，引号后面的表示引用位的值）

置换页面过程如下：

内存置换次数为 5，缺页率为 5/12

改进型 Clock

简单 Clock 算法仅使用一个“访问位”来记录页面是否被访问过。 当发生缺页中断时，算法从时钟指针的当前位置开始扫描内存中的页面，寻找第一个访问位为 0 的页面进行淘汰。 这种算法虽然实现简单，但存在一个明显的缺陷：它没有考虑页面是否被修改过。

为了解决简单 Clock 算法的缺陷，改进型 Clock 算法引入了“修改位”的概念。每个页面都有两个状态位：

• 访问位（R）： 表示页面是否被访问过。
• 修改位（M）： 表示页面是否被修改过。

根据这两个状态位，页面可以按照 淘汰优先级 分为四种类型：

• (0, 0)： 最近既没有被访问，也没有被修改。
• (0, 1)： 最近没有被访问，但是被修改了。
• (1, 0)： 最近被访问了，但是没有被修改。
• (1, 1)： 最近被访问了，也被修改了。

当访问一个新页面时，改进型 Clock 算法的运行过程如下：

• 算法首先尝试寻找 (0, 0) 类型的页面，如果找到，则立即替换。
• 如果第一轮扫描没有找到 (0, 0) 类型的页面，则进行第二轮扫描，寻找 (0, 1) 类型的页面。
• 如果前两轮都没有找到，那么会将所有访问位设置 为 0 然后重复前两轮扫描。

LFU

LFU（Least Frequently Used）算法的核心思想是：当主存没有足够的空间加载新的页面时，系统会选择那些在过去使用次数最少的页面进行置换。

基本步骤：

1. 初始化：当一个页面首次加载到内存中时，为其分配一个计数器并将其设置为 1（表示该页面被访问过一次）。
2. 页面命中：如果要访问的页面已经在内存中，则增加该页面的访问计数。
3. 页面置换：当需要为新的页面腾出空间时（也就是说，当内存中的页面已满并且需要加载一个新页面时），系统会查看所有当前在内存中的页面的访问计数，选择访问次数最少的那个页面进行置换。

内存映射文件

mmap是一种内存映射文件的方法，即将一个文件映射到进程的地址空间， 实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的一一对映关系。

• mmap 允许将文件映射到进程的虚拟地址空间，使文件的内容可以像内存一样直接访问，而不需要显式的读取或写入文件。
• 这意味着当你修改映射到内存中的文件内容时，实际上是在修改物理存储设备上的文件。因此，内存映射文件对于高性能 I/O 操作非常有用，因为可以避免显式的 I/O 操作。

以下内容为扩展内容，了解即可，基本不会考察。

常规文件操作需要从磁盘到页缓存再到用户主存的两次数据拷贝。而mmap操控文件，只需要从磁盘到用户主存的一次数据拷贝过程。

若要理解上述差别，首先需要了解常规文件的系统操作：

1. 进程发起读文件请求。
2. 内核通过查找进程文件符表，从而找到文件的 inode。
3. 在 inode 中查找要请求的文件页是否已经缓存在页缓存中。如果存在，则直接返回这片文件页的内容。
4. 如果不存在，则通过inode定位到文件磁盘地址，将数据从磁盘复制到页缓存。之后再次发起读页面过程，进而将页缓存中的数据发给用户进程。

总结来说，常规文件操作为了提高读写效率和保护磁盘，使用了页缓存机制。这样造成读文件时需要先将文件页从磁盘拷贝到页缓存中，由于页缓存处在内核空间，不能被用户进程直接寻址，所以还需要将页缓存中数据页再次拷贝到内存对应的用户空间中。这样，通过了两次数据拷贝过程，才能完成进程对文件内容的获取任务。写操作也是一样，待写入的buffer在内核空间不能直接访问，必须要先拷贝至内核空间对应的主存，再写回磁盘中（延迟写回），也是需要两次数据拷贝。

而使用mmap操作文件中，创建新的虚拟内存区域和建立文件磁盘地址和虚拟内存区域映射这两步，没有任何文件拷贝操作。而之后访问数据时发现内存中并无数据而发起的缺页异常过程，可以通过已经建立好的映射关系，只使用一次数据拷贝，就从磁盘中将数据传入内存的用户空间中，供进程使用。