内存管理

• 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。

应用场景

虽然上文举例的动态内存分配场景是进程向操作系统申请内存，但是在实际应用场景中，基本没有人这样子用。

动态内存分配最常见的场景就是进程堆上的内存分配，在 C 语言中可以通过 malloc 函数申请内存，并通过 free 函数释放内存，这里申请和释放的内存就是堆上的空闲内存块中的空间。

页式管理

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

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

段式管理

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

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

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

段定义

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

段表

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

地址转换

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

段页式管理

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

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

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

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

2 - 虚拟内存管理

页框分配

驻留集大小

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

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

什么是抖动

抖动（Thrashing）是指操作系统中发生的一种现象，当它花费大量时间在页面置换（将内存中的页面换入换出到磁盘）上而非执行实际的计算。这通常发生在系统的物理内存非常紧张，多个进程频繁请求的页面不在物理内存中时。

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

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

内存分配策略

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

固定分配

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

可变分配

操作系统中的可变分配包含两种主要思路：第一种就是将 内存分为若干页面，然后根据进程的需求为其动态地分配内存页面。第二种思路与 动态分区分配 一致，在一块连续的内存上动态地申请连续的某个长度的存储空间。

内存置换策略

• 局部置换
  • 每个运行的进程被分配了一定数量的内存帧（物理内存中的页面），并且仅在这些分配给它的帧中进行页面置换。
  • 当一个进程需要更多的内存空间时，它只能换出自己的页面，而不能影响到其他进程的页面。
• 全局置换
  • 操作系统可以从整个物理内存的范围内选择页面进行置换，不局限于特定进程的内存帧。
  • 如果一个进程需要更多的内存，操作系统可以从其他进程占用的帧中换出页面。

局部置换

全局置换

分配和置换策略的组合

可以选择分配策略和置换策略之一进行组合，但不存在固定分配全局置换方式。

页置换算法

OPT

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

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

FIFO

FIFO（First-In-First-Out）页面置换算法是一种简单的页面置换策略，其中最早进入内存的页面被置换出去。它的工作原理类似于排队，即首先进入内存的页面也是首先离开内存的页面。

LRU

LRU（Least Recently Used）页面置换算法是一种常用的页面置换策略，它基于最近的页面访问历史来决定哪个页面应该被置换出内存。LRU算法的基本思想是，总是选择最长时间没有被访问的页面进行置换，以期望最小化未来的缺页次数。

LRU替换策略如下：

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

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

LRU代码实现

Clock

简单clock替换算法

CLOCK算法的核心思想是使用一个类似时钟的数据结构，以跟踪每个页面的访问状态。CLOCK算法维护一个环形链表，其中每个页面都有一个位（也称为访问位或引用位）。算法以时钟指针的方式扫描环形链表，查找可以被替换的页面。

Clock替换策略如下：

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

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

clock算法代码实现

改进型clock算法

CLOCK-Pro算法通过引入更多的信息来更准确地确定页面是否被访问，以便更好地进行页面替换决策并且减少磁盘I/O次数。

CLOCK-Pro算法引入了两个新的位来跟踪页面的状态：

• 访问位：与标准CLOCK算法相同，R位用于标记页面是否最近被访问，0表示未被访问，1表示已被访问。
• 修改位（脏位）：M位用于标记页面是否被修改，0表示未修改，1表示已修改。

1. 当页面需要进入内存时，R位和M位都被设置为0，表示页面最近未被访问且未被修改。
2. 当访问一个页面时，R位被设置为1，表示页面最近被访问。
3. 当修改一个页面时，M位被设置为1，表示页面已被修改。
4. 当需要替换页面时，CLOCK-Pro算法首先查看R位，选择R位为0的页面进行替换，这是与标准CLOCK算法相同的部分。
5. 如果所有页面的R位都为1，CLOCK-Pro算法会选择M位为0的页面进行替换，以便选择一个未被修改的页面进行替换。
6. 如果所有页面的R位和M位都为1，CLOCK-Pro算法会选择最早满足这两个条件的页面进行替换，以模拟LRU策略。

LFU

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

基本步骤：

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

内存映射文件

mmap 是一种在 Unix/Linux 操作系统中用于实现内存映射文件的系统调用。内存映射文件是一种非常有用的技术，它允许将文件映射到进程的地址空间中，使文件的内容可以像内存一样被访问。

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