OS-内存管理

空闲空间管理

当内存总被划分为固定大小的块时，内存的管理比较容易。但如果需要将内存划分为可变长度的块，比如malloc和free、操作系统的分段操作，会出现我们熟悉的内存碎片问题。

接下来需要解决三个问题：

如何管理空闲空间？
如何让碎片最小化？
这些方法各自的时间和空间开销如何？

以下内容主要讨论外部碎片。与之对应的是内部碎片，即分配程序返回了比请求大小更大的内存，这种浪费被称为内部碎片。

一些重要概念：

空闲列表：在堆上管理空闲内存的数据结构被称为空闲列表。
分割：将空闲空间分割出满足需求的大小，并分配出去。
合并：将释放的内存进行整理合并，消除内存碎片化。

追踪已分配内存大小：free(void*) 并不要求我们提供内存大小信息，说明被分配的内存存在某种方式维护自身的大小。最常见的方式是插入一个头，比如：

1
2
3
4


typedef struct header {
    int size;  // 分配的内存块大小
    int magic; // 幻数（Magic Number），用于校验内存块的完整性
} header;

size：记录分配的内存块大小（不包括头块本身）。
magic：一个特殊的幻数，用于校验内存块的正常性。

内存分配时的操作：

当调用 malloc(size) 时，内存分配库会分配 size + sizeof(header) 字节的内存块。
在返回给用户的内存指针之前，插入头块，并初始化 size 和 magic 字段。
返回给用户的内存指针实际上是头块之后的地址。

1
2
3
4
5
6


void* malloc(size_t size) {
    header* hdr = (header*)sbrk(sizeof(header) + size); // 分配内存
    hdr->size = size;
    hdr->magic = 0x12345678; // 设置幻数
    return (void*)(hdr + sizeof(header)); // 返回用户可用内存的起始地址
}

分配策略

常见的分配策略有：

最优匹配（Best Fit）

描述：遍历整个空闲列表，找到满足需求且尽可能小的内存块。
优点：
- 减少内存浪费，选择最接近需求大小的块。
缺点：
- 需要遍历整个空闲列表，性能开销较高。
- 可能产生大量难以利用的小碎片。
适用场景：对内存利用率要求高，但对性能要求不高的场景。

首次匹配（First Fit）

描述：返回找到的第一个满足需求的内存块。
优点：
- 查找速度快，无需遍历整个空闲列表。
缺点：
- 容易在空闲列表头部堆积大量小碎片，导致后续分配效率降低。
适用场景：对性能要求高，但对内存碎片容忍度较高的场景。

下次匹配（Next Fit）

描述：与首次匹配类似，但每次查找的起点是上一次分配的内存块之后。
优点：
- 避免空闲列表头部堆积小碎片，查找效率较高。
缺点：
- 可能无法充分利用内存，导致碎片分布更均匀但总量增加。
适用场景：需要平衡性能和内存利用率的场景。

除此之外，还有一些较为复杂的实现：

分离空闲列表：

基本思想是：

为常见的大小请求创建独立的空闲列表，从而避免内存碎片并加速分配，比如分别创建管理8、16、24、……、512字节的空间列表。
其余请求交给通用分配器。

伙伴系统：

基本概念：

伙伴系统将内存划分为大小为2的幂次方的块，例如1KB、2KB、4KB等。
当有内存分配请求时，系统会递归地将较大的块一分为二，直到找到刚好满足请求大小的块。

分配过程：
当请求一个特定大小的内存块时，系统会查找一个足够大的空闲块。如果找到的块比请求的大小大，系统会将其一分为二，直到得到合适大小的块。

释放与合并：

当内存块被释放时，系统会检查其“伙伴”块是否也是空闲的。如果是，系统会将这两个块合并成一个更大的块。
这个过程会递归进行，直到无法再合并或达到最大块大小。

优点：

高效合并：由于伙伴系统通过简单的位操作即可确定伙伴块，合并操作非常高效。
减少碎片：通过合并操作，伙伴系统能够有效减少内存碎片。

分页

在《CSAPP》中介绍了操作系统会将内存划分为若干个大小相同的块。现在是时候继续探究操作系统为什么需要分页，如何进行分页了。

重要概念：

分页：操作系统会将内存划分成固定长度的分片，这种操作被称为“分页”。
页帧：将物理内存划分为成固定长度的块，这就是页帧。
页表：保存地址空间中每个虚拟页面与物理内存的映射关系。重要的是，每个进程有各自独立的页表。

页表

页表的核心功能是保存以下两个关键信息：

虚拟页面号（VPN）到物理页面号（PFN）的映射：通过查找页表，操作系统可以将虚拟页面号（VPN）转换为物理页面号（PFN），从而确定虚拟页面在物理内存中的具体位置。
页内偏移量（Offset）：偏移量用于标识页面内的具体字节位置。在地址转换过程中，偏移量保持不变，因为它仅用于定位页面内的数据，而不涉及页面本身的映射。

页表项（PTE）中包含许多内容，其中重要的有：

位类型	技术作用	实现价值
有效位	标记虚拟页是否已分配物理帧	支持稀疏地址空间，避免无效页面的物理内存占用
保护位	控制访问权限（读/写/执行）	实现内存保护机制，阻止非法操作（如代码段写入）
存在位	标识页是否驻留物理内存（0=已交换到磁盘）	支持虚拟内存扩展，允许物理内存不足时换出页面
脏位	标记页内容自载入后是否被修改	优化页面换出策略，避免回写未修改页至磁盘
参考位	记录页访问频率（通常通过定期清零实现）	支撑LRU等页面置换算法，提升缓存效率

页表有许多优点：

不会有内存碎片：物理内存按固定页框分配，避免可变分区导致的碎片问题。
支持稀疏虚拟地址：得益于有效位，被分配的内存不需要连续存储或标记某个范围内有效。

页表带来了两个问题：

额外的内存读取：为了读取一块内存，必须先读取一次页表以得到实际内存地址。
内存浪费：页表为了映射物理地址，必须占用内存空间。

OS-内存管理

空闲空间管理

分配策略

分页

页表

相关文章：