操作系统学习笔记-3.1内存管理

内存的地址

按字节编址（8bit），和按字编址（计算机字长）。
物理地址是指计算机内存的实际地址，用于存储数据和程序代码。它是内存硬件上的一个真实位置，与CPU直接交互。在多进程操作系统中，物理地址用于加载和存取存储在主内存（RAM）中的数据。计算机系统通过物理地址来定位存储单元并读取或写入数据。
在多任务操作系统中，每个进程通常看到的是自己的地址空间（虚拟地址空间），而非直接访问物理地址。虚拟地址通过内存管理单元（MMU，Memory Management Unit）映射为物理地址，从而实现进程之间的内存隔离。
页表
页表（Page Table）是用来维护虚拟地址到物理地址映射关系的表格。在分页系统中，每个进程都有一个页表，记录该进程的每个虚拟页面所对应的物理页面地址。CPU通过页表查找来获取物理地址。
逻辑地址 其实就是相对地址，相对于初始地址相对的地址

绝对装入

编译的时候从逻辑地址转换为目标地址，灵活性很低，换台电脑就不行了。

静态重定位

装入的时候转换定位，必须全部分配，且不能移动

动态重定位

重定位寄存器存储起始位置。将逻辑地址和重定位寄存器相加
变址寄存器的主要功能是处理数组和表的索引操作，而不是用于内存管理
变址寄存器通过基地址和索引值来计算偏移地址，而不是进行内存地址的动态重定位。

链接

链接方式决定了代码和依赖的库（例如系统函数、动态库等）在什么时候和如何绑定到程序的执行环境中。
静态链接是在编译时将所有依赖的库和函数代码直接嵌入到目标程序中，生成一个独立的可执行文件。该文件在运行时不需要额外的动态库支持即可执行。
动态链接，是在程序加载到内存时将所需的共享库动态链接到程序地址空间中。这种方式下，库的代码并不直接嵌入到可执行文件中，而是通过动态链接库（Dynamic Link Library，DLL）进行引用。
运行时动态链接（Run-time dynamic linking）是在程序执行过程中，根据需要动态加载库。这种方式允许程序在执行期间动态加载库并调用库中的函数。

覆盖和交换

1. 覆盖（Overwrite）在内存管理中的作用

定义：在内存管理中，覆盖通常指用新的数据直接替换已有的内存区域内容，而不释放原来的内存空间。

应用场景：

• 堆区数据的复用：在动态分配内存的情况下（例如 malloc 或 new 操作），可以在分配的内存上进行覆盖操作，避免反复分配与释放内存。例如，内存池（memory pool）技术会复用已分配的内存区域，通过覆盖存储新数据。
• 缓冲区覆盖：在网络或文件I/O处理中，为了减少内存分配次数，可以对缓冲区覆盖写入新数据。

注意事项：

• 内存泄漏：如果在覆盖前没有释放指针或对象指向的旧数据，可能导致内存泄漏。，对用户不够透明
• 安全问题：覆盖可能会导致原有数据被意外修改或破坏，因此需要特别小心，避免覆盖掉有效数据。

示例：
在堆区覆盖一个数组：

int* arr = new int[10];
// 对数组赋值
for (int i = 0; i < 10; ++i) {arr[i] = i;
}
// 覆盖原数据
for (int i = 0; i < 10; ++i) {arr[i] = i * 2;
}
delete[] arr;

2. 交换（Swap）在内存管理中的作用

定义：在内存管理中，交换指将两个内存区域的数据对调，而不创建新的空间。这种操作通常在避免内存分配、提升效率上有重要作用。
将磁盘分为文件区和对换区，对换区更快

应用场景：

• 内存分页和分段管理：操作系统的内存管理使用交换技术将内存数据移至硬盘或从硬盘移回内存（称为“换页”或“页面交换”），用于管理虚拟内存并减少内存消耗。
• 数据排序：在快速排序或堆排序中，交换两个内存块的数据，避免频繁分配与释放内存，提升效率。
• 容器内存重排：如在C++的 std::swap 函数中，两块内存的数据可以直接交换，避免重新分配内存空间。

注意事项：

• 数据完整性：交换要确保数据不会被误改或丢失，因此通常需要辅助变量或指令来保障数据的安全性。
• 性能：在交换较大内存块的数据时，直接交换可能导致效率低下，因此可以考虑浅拷贝或指针交换。

示例：
交换两个指针指向的内存块内容：

int* a = new int(5);
int* b = new int(10);int temp = *a;
*a = *b;
*b = temp;delete a;
delete b;

连续分配管理方式

固定分区分配的关键概念

固定分区分配是一种内存管理方式，将内存划分为若干固定大小的分区，每个分区只能分配给一个进程。这种方法通常用于早期操作系统和一些嵌入式系统中，适合并发数较低且程序大小较稳定的应用场景。

1. 分区划分方式：

   • 相等分区（Equal-Sized Partitions）：将内存划分为大小相同的分区，每个分区能分配给一个进程。适合同类应用场景，但容易造成内存浪费。
   • 不等分区（Unequal-Sized Partitions）：将内存划分为大小不同的分区，适合分配给不同大小的程序。这样可以更灵活地利用内存，减少内存浪费。

2. 分配机制：

   • 单一分区分配：一个分区仅供一个进程使用，分区中的内存固定不变。进程无法动态调整所需的内存量。
   • 静态分配：在系统启动时完成分区分配，运行期间不会动态改变分区大小。

优点

• 管理简单：分区大小固定，内存管理结构简单，易于实现。
• 快速分配：因为每个分区大小固定，分配和回收内存的速度较快，适合实时系统。
• 减少碎片化：与动态分区相比，固定分区在一定程度上可以避免内存碎片化。

缺点

• 内存浪费：当进程所需内存比分区小得多时，剩余的内存无法再利用，称为“内部碎片”。
• 缺乏灵活性：每个分区大小固定，无法动态扩展或缩小，进程可能因为不适合的分区而无法加载。
• 并发限制：分区数决定了最大并发进程数，分区少则并发进程受限。

示例

假设系统内存为 1 GB，分为 4 个固定大小的分区：每个分区 256 MB。每次启动进程时，系统会寻找空闲分区分配给进程。例如：

1. 进程 A 需要 200 MB，分配给 256 MB 的分区 1，剩余 56 MB 无法利用，形成内部碎片。
2. 进程 B 需要 300 MB，无法分配任何分区，因为每个分区只有 256 MB 的容量，分区不足则导致分配失败。

动态分区分配是一种内存管理方式，与固定分区分配不同，它不预先划分固定大小的分区，而是根据进程的需求动态分配合适大小的内存区域。这种方法适合现代多任务操作系统，能够更灵活地利用内存资源。

动态分区分配的关键概念

1. 分区动态创建和释放
   在动态分区分配中，内存没有固定的分区划分，系统根据进程的内存需求实时创建相应的内存块。每个进程的内存块分配结束后，会释放回内存池供其他进程使用。

2. 内存分配算法
   动态分区分配常用以下几种算法来管理内存空闲块：

   • 首次适配（First Fit）：从低地址开始，找到第一个足够大的空闲块分配给进程。这种方法简单快速，但容易在低地址区域产生碎片。
   • 最佳适配（Best Fit）：在所有空闲块中选择最小的且刚好能满足要求的块，目的是减少内存浪费。但由于空闲块较小，可能导致更多的很小的碎片。
   • 最坏适应（Worst Fit）：选择最大的空闲块分配给进程，目的是让剩余空间更大，便于后续使用，但效率较低，容易浪费内存。但容易导致大进程无法获取资源
   • 邻近适配（Next Fit）：类似首次适配，但每次从上次查找到的位置继续查找，适合减少低地址区域碎片的堆积。类似循环列表，不断去寻找。

3. 空闲块管理
   动态分区分配需要实时跟踪和管理内存中的空闲块。常见的管理方式包括链表和位图：

   • 链表：用一个链表存储空闲块的信息，每个空闲块有起始地址和大小，方便动态插入和删除。

   • 

   • 包括空闲分区表，空闲分区链

   • 位图：将内存划分成小块，用位图表示每一块是否被占用，适合快速查询。

4. 内存合并和碎片整理
   由于动态分区会产生碎片化问题，因此需要进行合并和碎片整理。当一个内存块被释放时，系统检查相邻的内存块是否也是空闲块，如果是，就合并成一个更大的空闲块。碎片整理（如压缩内存）则是将分散的空闲块集中，以便于大块内存的分配。

优点

• 灵活性高：内存分配基于进程需求大小，可变分区大小使得系统更灵活。
• 减少浪费：相较固定分区分配，动态分区分配可以减少内部碎片，因为分配的内存块大小与需求更接近。

缺点

• 外部碎片：动态分配内存时，可能会产生很多小的、不连续的空闲块，导致外部碎片化。
• （内部碎片）是分配给进程的空间没有用上
• 管理复杂性：需要维护空闲块的信息，增加了系统开销；而碎片整理也需要额外的系统资源和时间。
• 分配效率影响：在分配和释放内存时，需要查找适合的空闲块，算法复杂度较高，可能影响分配速度。

示例

假设一个系统有 1000 KB 的内存，当前情况如下：

• 进程 A 申请了 200 KB；
• 进程 B 申请了 300 KB；
• 进程 C 申请了 100 KB；

当前剩余的空闲块为：

• 空闲块 1：100 KB
• 空闲块 2：300 KB

如果新的进程 D 申请 150 KB，系统可能会选择第二个空闲块分配给 D（基于首次适配算法）。分配后：

• 进程 D 占用空闲块 2 的 150 KB，剩余 150 KB 变为新的空闲块。

当进程 A 释放其内存后，系统可以将释放的 200 KB 和空闲块 1 的 100 KB 合并为一个新的 300 KB 的空闲块。

基本分页存储管理

内存空间分为大小相等的分区，每个分区一个页框（页帧，内存块，物理块，物理

基本地址变换机构

页表寄存器

页表寄存器存储了页表的起始地址 0x3000。
一个虚拟地址 0x1234，其中 0x1 是页号，0x234 是页内偏移。
工作过程如下：

• CPU从页表寄存器中获取页表基地址 0x3000。
• 在页表中使用页号 0x1 找到对应的物理页框地址，例如 0x4000。
• 将物理页框地址 0x4000 和页内偏移 0x234 合并，得到物理地址 0x4234。

快表（Translation Lookaside Buffer，TLB）是一种用于加速虚拟地址到物理地址转换的高速缓存，位于CPU内部。快表存储了最近访问的虚拟页面和物理页面的映射关系，使得CPU在进行内存访问时，可以优先查找快表，避免频繁访问页表，从而提高访问效率。

快表的工作原理

1. TLB查找
   

   当CPU需要访问内存时，会首先查看快表，看是否存在所需虚拟地址的映射关系。

   • 命中（Hit）：如果快表中存在所需的地址映射，则直接返回对应的物理地址。
   • 未命中（Miss）：如果快表中没有相应的映射，则需要访问页表，从中获取映射关系，并将其加载到快表中，完成地址转换。

2. LRU替换算法
   由于快表容量有限，不能存储所有的页表项。因此，常用**最近最少使用（Least Recently Used，LRU）**算法来替换不常访问的页面，将其移出快表，腾出空间供新页面使用。

3. 多级页表与TLB的结合
   在多级页表结构中，虚拟地址转换需要进行多次内存访问。而TLB能缓存虚拟地址与物理地址的映射，使得每次查找都只需一步访问，大大减少了多级页表的性能开销。

快表的优势

• 减少内存访问次数：TLB将最近使用的地址映射关系缓存到CPU内部，避免频繁访问内存中的页表。
• 提高访问速度：由于TLB位于CPU内，访问速度远快于内存，因此快表命中时能显著加快地址转换。
• 减少延迟：对系统性能要求较高的场景（如多任务操作系统和实时系统），TLB可以减少页面管理带来的延迟。

快表的局限性

• 缓存容量有限：TLB只能存储一小部分页表项，无法完全覆盖大规模的内存需求。
• 缺页中断：当快表和页表中都没有目标地址时，CPU会发生缺页中断，需要操作系统将缺页从外存（如磁盘）加载到内存，产生较高的延迟。
• 替换开销：TLB需要动态管理页面的替换策略，虽然大多数情况下LRU算法效率较高，但在特定情况下可能影响性能。

TLB的工作示例

假设有以下内存访问过程：

• 虚拟地址：0x1234
• 页号（从虚拟地址中分解得到）：0x12

1. CPU检查TLB，寻找页号0x12的映射关系。
   • 若找到，则直接使用TLB中的物理地址完成转换。
   • 若未找到，则访问页表，获取0x12对应的物理页框地址，并将该映射关系加载到TLB中。
2. 之后的相同地址访问请求，可直接从TLB中命中，节省查找页表的开销。

二级列表

二级页表（Two-Level Page Table）是一种将页表分为两级的结构，用于提高内存利用效率、减少内存碎片。二级页表的设计旨在避免将整个页表一次性加载到内存中，适用于内存地址空间较大的系统，如32位或更高位系统。

二级页表的结构与工作原理

在二级页表中，页表被分为两个层级：

1. 顶级页表（一级页表）
   顶级页表的每个条目指向一个二级页表的地址，并根据虚拟地址的高位部分（如前10位）来索引相应的次级页表。

2. 次级页表（二级页表）
   每个二级页表存储具体的页表项，即每个虚拟页面到物理页面的映射关系。次级页表的条目由虚拟地址的低位部分索引。

二级页表的地址转换过程

假设一个系统的虚拟地址分为三级字段：一级页号、二级页号和页内偏移。二级页表的工作过程如下：

1. 一级页表查找
   根据虚拟地址的顶级页号部分，在顶级页表中查找对应的次级页表的地址。

2. 二级页表查找
   根据次级页号部分，在选定的次级页表中找到页框号。

3. 物理地址计算
   将页框号和虚拟地址中的页内偏移组合，得到最终的物理地址。

示例

假设一个32位地址空间的虚拟地址结构如下：

• 一级页号：10位（用于查找一级页表）
• 二级页号：10位（用于查找二级页表）
• 页内偏移：12位（用于计算页内的具体地址）

具体地址转换流程为：

1. CPU使用虚拟地址的前10位（顶级页号）索引一级页表，找到对应的二级页表的起始地址。
2. 接着使用虚拟地址的中间10位（次级页号）在二级页表中查找对应的物理页框号。
3. 最后，将物理页框号与虚拟地址的最后12位页内偏移组合，计算出物理地址。
   注意各级页表的大小不能超过一个页面

优点

• 减少内存消耗：只需将正在使用的部分页表加载到内存中，避免为每个进程分配整页的页表，降低内存开销。
• 提高地址空间灵活性：适合于较大虚拟地址空间，便于扩展。
• 按需分配内存：系统仅在需要时为虚拟地址空间分配实际的物理页，未使用的页表不会占用内存。

缺点

• 增加访问开销：二级页表需要访问两级索引，可能会稍微增加地址转换时间。可以通过**TLB（快表）**进行缓存来提高效率。
• 管理复杂：需要维护多个页表，并且在内存中占据更多的表项和地址管理结构。

基本分段存储管理

基本分段存储管理是一种内存管理方式，将一个进程的地址空间划分成多个不同的逻辑段，每个段代表进程的一个逻辑部分，如代码段、数据段、堆栈段等。分段存储管理允许每个段独立地加载到内存中，以适应进程的需求和特性。

基本分段的概念

在分段存储管理中，内存被划分为多个大小可变的段，每个段有一段基址（base）和段长（limit）：

• 段基址：指定段在物理内存中的起始地址。
• 段长：指定段的大小（字节数），用于防止越界访问。

分段存储管理的地址结构

在分段管理系统中，逻辑地址由段号和段内偏移量组成：

• 段号（Segment Number）：用于标识段，系统根据段号在段表中找到段的基址。
• 段内偏移量（Offset）：表示该段内的相对地址，即段内具体访问的位置。

逻辑地址 (s, d) 转换成物理地址的步骤如下：

1. CPU从段表中查找段号 s，获取该段的基址和段长。
2. 检查段内偏移量 d 是否小于段长，以防止越界。
3. 将基址与偏移量相加，得到实际的物理地址。

如果 d 超出段长，则触发越界错误。

分段存储管理的结构

基本分段系统的核心是段表，每个进程都有一个独立的段表。段表中记录了每个段的基址和长度，用于进行地址转换和保护。

1. 段表（Segment Table）

   • 每个进程有一个独立的段表。
   • 每个段表条目包括段基址和段长。

2. 段表寄存器（Segment Table Register, STR）

   • 存储段表在内存中的起始位置。
   • 进程切换时，更新段表寄存器以指向新进程的段表。

分段管理的优点

1. 更贴合逻辑结构：分段管理按进程逻辑结构划分不同的段，更符合程序设计逻辑（代码段、数据段、堆栈段等）。
2. 便于共享和保护：不同进程可以共享相同的代码段或数据段，例如只读代码段，减少内存冗余。
3. 灵活的内存分配：段的大小可变，便于动态增长或收缩，内存利用率更高。

分段管理的缺点

1. 外部碎片：段的大小可变，释放后可能产生不连续的空闲内存块，导致外部碎片。
2. 地址转换开销：每次访问内存时都需要查找段表，增加了地址转换的时间开销。
3. 复杂的段表管理：每个进程都需要维护段表，且段的长度可变，导致内存管理复杂度增加。

基本分段示例

假设有一个进程的地址空间被划分成以下几个段：

• 段0：代码段，长度为 80 KB。
• 段1：数据段，长度为 120 KB。
• 段2：堆栈段，长度为 40 KB。

对应的段表如下：

段号	基址（Base）	长度（Limit）
0	7K	80K
1	3K	120K
2	6K	40K

如果需要访问逻辑地址 $(2,1024)$，即数据段中的第500字节：

1. CPU从段表中查找段2的基址 40K 和长度 6K。
2. 检查偏移 1024 是否小于段长 6K，确认合法。
3. 计算物理地址：40K + 1024 。

段页式分配管理（Segmented-Paged Memory Management）

段页式分配管理的基本原理

段页式管理将进程的地址空间划分为多个段，每个段再细分为页，从而形成段和页的双重管理结构。具体结构如下：

1. 段
   每个进程的地址空间分为若干段，每个段对应进程的一个逻辑单元，如代码段、数据段等。每个段有一个独立的段号和段表，用于管理该段的基本信息。

2. 页
   每个段再细分为固定大小的页，分页管理通过将每个段进一步分解为等大小的页面，将段式管理的外部碎片问题转化为内部碎片问题。

在段页式分配管理中，逻辑地址由段号、页号和页内偏移量组成。系统通过段表找到段的页表，再通过页表查找到具体的物理页框，从而最终完成地址转换。

段页式地址转换过程

假设一个逻辑地址的结构为 (段号, 页号, 页内偏移)，段页式管理的地址转换过程为：

1. 段表查找

   • 根据段号，系统在段表中找到对应段的页表地址和段的大小限制。
   • 确保页号不超出该段的大小范围。

2. 页表查找

   • 根据页号，在该段对应的页表中找到物理页框号。

3. 计算物理地址

   • 将物理页框号与页内偏移量组合，计算得到最终的物理地址。

示例

假设有一个进程的逻辑地址 (2, 3, 400)，表示段号为2、页号为3、页内偏移400的地址。地址转换步骤如下：

1. 段表查找段2

   • 在段表中查找段号2，找到该段的页表起始地址和段长。
   • 确认页号3在段的范围内。

2. 页表查找页3

   • 使用页表基址和页号3，在页表中找到物理页框号（假设为7000）。

3. 计算物理地址

   • 物理地址为 7000 + 400 = 7400。

以下是段式管理、页式管理和段页式管理的对比，包含优点和缺点：

特性	段式管理	页式管理	段页式管理
基本单位	段（大小不固定）	页（固定大小）	段和页相结合
逻辑划分	根据进程的逻辑部分（代码、数据等）	无逻辑划分，以页为单位	先按逻辑划分为段，再将每段分页处理
内存分配方式	动态分配，每段大小可变	固定分配，每页大小相同	每段大小可变，每段内固定大小的页
地址结构	段号 + 段内偏移	页号 + 页内偏移	段号 + 页号 + 页内偏移
段表/页表	段表	页表	段表和页表
外部碎片	存在外部碎片	不存在外部碎片	减少外部碎片
内部碎片	较少	可能产生内部碎片	页内可能存在内部碎片
地址转换速度	快（只需查找段表）	较快（查找页表）	较慢（需查找段表和页表）
内存利用效率	较低（可能产生外部碎片）	较高（消除外部碎片）	高效（减少外部碎片）
应用场景	早期系统，支持按逻辑划分	现代系统，支持虚拟内存管理	复杂内存管理系统，如现代操作系统
共享和保护	可以对每段独立设置保护和共享	共享较困难	段内可以共享，且每段有独立权限
管理开销	较低	较低	较高（需维护段表和多个页表）
优点	支持逻辑划分，方便共享和保护	消除外部碎片，提高内存利用率	结合分段和分页，减少外部碎片，支持灵活共享与保护
缺点	易产生外部碎片，内存利用率较低	难以实现共享，管理灵活性较差	地址转换开销大，管理结构复杂

其它内存管理知识点

• 1. 静态装入是指在编程阶段就把物理地址计算好。
• 2. 可重定位是指在装入时把逻辑地址转换成物理地址，但装入后不能改变动态重定位是指在执行时再决定装入的地址并装入，装入后有可能会换出，所以同一个模块在内存中的物理地址是可能改变的。
• 3. 动态重定位是指在作业运行过程中执行到一条访存指令时，再把逻辑地址转换为主存中的物理地址，实际中是通过硬件地址转换机制实现的。

• 分页存储管理中，作业地址空间是一维的，即单一的线性地址空间，程序员只需要一个记忆符来表示地址。在分段存储分配管理中，段之间是独立的，而且段长不定长，而页长是固定的，因此作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。简言之，确定一个地址需要几个参数，作业地址空间就是几维的。