内存管理

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

# 内存管理

## 基础

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

## 虚拟内存

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

1 - 内存管理概念

内存管理的基本概念

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

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

• 内存保护

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

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

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

连续分配管理方式

1. 单一连续分配

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

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

2. 固定分区分配

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

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

3. 动态分区分配

内存空间中的空闲区域可能大小不一，且分布在内存中不同的位置。当进程申请一块新的内存时，必须从已有的空闲空间中选出一块分配给进程。动态分区的分配策略包含以下几种算法：

• First Fit（首次适应）
  • 当需要分配内存时，它不从内存的开始位置开始，而是从上一次分配内存的地方开始。
• Next Fit（临近适应）
  • 这种策略与首次适应相似，但当需要分配内存时，它不从内存的开始位置开始，而是从上一次分配内存的地方开始。
• Best Fit（最佳适应）
  • 为了满足内存请求，最佳适应策略会在所有可用的内存块中查找并选择最小的、但足够大的内存块（申请内存/内存块大小最大），这种策略的目标是最大限度地减少浪费的内存空间。。
• Worst Fit（最坏适应）
  • 与最佳适应的目标相反，其思想是留下最大的连续空闲区域，希望这样可以满足后续的大请求。

页式管理

段式管理

段式内存管理是一种内存组织方法，它将程序的不同部分（例如代码、数据和堆栈）划分为不同的段（segments）。每个段在物理内存中可以不连续，但在逻辑上都被视为连续的。这种方法的主要优点是它允许更为灵活的内存使用，并有助于提供更好的保护和共享机制。

段定义

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

段表

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

地址转换

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

段页式管理

段页式管理是一种将段式内存管理与分页式内存管理相结合的策略。它结合了两者的优势，旨在提供灵活性和减少内存碎片。在段页式管理中，程序首先被划分为逻辑上的段，然后每个段进一步被划分为固定大小的页。

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算法引入了两个新的位来跟踪页面的状态：

• Reference Bit (R位)：与标准CLOCK算法相同，R位用于标记页面是否最近被访问，0表示未被访问，1表示已被访问。
• Modified Bit (M位)：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 操作。

视频讲解