内存管理算法
基础算法
Linear allocator
它的思路是预先创建内存块，然后在内存块上一直分配内存，这些分配出去的内存不用释放，到最后再一次性把内存块回收。
Free List
Free List 的本质是一个链式结构，每个节点代表一个空闲内存块，节点之间通过指针（或偏移量）连接。分配器通过维护这个链表，快速定位满足请求的空闲块，并在释放时将块重新加入链表。Free List 是几乎所有内存分配器的基础结构。
根据空闲块的排序规则，Free List 可分为以下几类：
| 组织方式 | 排序依据 | 典型用途 | 优缺点 |
|---|---|---|---|
| 地址有序链表 | 按空闲块的起始地址升序排列 | 首次适应（FF）算法 | 分配时从头遍历，找到第一个足够大的块；释放时快速合并相邻块（地址连续）。 |
| 大小有序链表 | 按空闲块的大小升序/降序排列 | 最佳适应（BF）、最差适应（WF）算法 | 分配时快速定位目标大小（如最佳适应找最小足够大的块）；但插入需维护顺序，开销较高。 |
| 混合有序链表 | 按大小分桶 + 桶内地址有序 | 优化版分配器（如TCMalloc、Jemalloc） | 将空闲块按大小划分为多个桶（如8B、16B、...、4MB），桶内按地址排序；平衡分配速度与碎片。 |
分配过程：
- 遍历链表：从链表头开始，检查每个空闲块的大小是否≥请求大小。
- 分割块（若需要）：若找到的块比请求大，将其分割为两部分：分配部分（满足请求）和剩余部分（作为新的空闲块，重新插入链表）。
- 更新链表：将原块从链表中移除，剩余部分（若有）插入链表。
分割块会造成外部碎片，不分割块会造成内部碎片。例如空闲块大小为4K，申请了1K，就有3K的碎片。
回收流程：
- 标记块为空闲：清除块的内存标记（如“已分配”标志位）。
- 查找合并相邻块（若需要）：检查释放块的前后地址是否有其他空闲块（通过链表遍历或地址计算）。若存在相邻空闲块，将它们合并为一个更大的块，并更新链表（移除相邻块，插入合并后的块）。
- 插入链表：将合并后的块（或原块）插入链表的正确位置（按地址或大小排序）
链表的存储的元数据通常包括：
- 块大小：记录空闲块的总大小（用于快速判断是否满足分配请求）。
- 状态标记：标记块是否空闲（避免重复释放）。
- 对齐填充：确保块起始地址满足对齐要求（如64位系统通常按16字节对齐）。
实现技巧：元数据可直接存储在空闲块的内存头部（称为“块头”）
Fixed Size Allocator
顾名思议，Fixed Size Allocator 只能分配和释放固定大小的内存。它的核心思想是预创建内存块，然后将内存块切割成多个固定大小的小块，并将它们链接起来形成一个Free List。
他只能分配固定大小的内存，Slab分配器就是这种思路，Buddy System扩展了这种思路。
一些经典的内存分配器
Slab/Slub
Slab分配器的核心思想是：为每种小对象类型（如task_struct、dentry）创建专用的“对象池”（Slab缓存），每个池内的对象按类型紧密排列，避免跨页碎片，并通过预分配和重用机制减少内存分配的开销。广泛应用于需要频繁创建/销毁小数据结构的场景，例如用来管理Linux内核的task_struct，file、dentry、inode等。Slub是Slab的改进版，被Linux内核使用。
Buddy System
Buddy System伙伴系统的核心是2的幂次方块管理。内存被预先划分为多个大小为 2k（k=0,1,2,…）的块（称为“页框”或“伙伴块”）。例如，若总内存为8MB，则可能的块大小为1KB（\(2^{10}\)）、2KB（\(2^{11}\)）、4KB（\(2^{12}\)）……直到8MB（\(2^{23}\)）。
1. 分配流程（以请求大小 S 为例）
步骤1：确定最小块大小 2k
找到最小的 k，使得 2k≥S（即 k=⌈log2S⌉）。例如，请求5KB时，k=3（23=8KB）。
步骤2：查找空闲块
检查大小为 2k 的空闲块链表。若存在空闲块，直接分配；若不存在，进入步骤3。
步骤3：分裂父块
若当前大小 2k 无空闲块，将父块（大小为 2k+1）从空闲链表中移除，并分裂为两个 2k 的“伙伴块”（互为伙伴）。将其中一个伙伴块分配给请求，另一个加入 2k 空闲链表。若父块也不存在，继续向上分裂（直到最大块，如系统总内存）。
2. 释放流程（以释放块 B 为例）
步骤1：标记块为空闲
将块 B 标记为空闲，并检查其是否有相邻的“伙伴块”（即地址连续且大小相同的块）。
步骤2：合并伙伴块
若存在相邻的空闲伙伴块，将两者合并为一个更大的块（大小为 2×2k=2k+1），并从原 2k 空闲链表中移除这两个块，将合并后的块加入 2k+1 空闲链表。重复此过程，直到没有更大的相邻伙伴块可合并。
实现
通常，系统为每个可能的 2k 大小维护一个双向链表（或数组索引），存储该大小的空闲块。例如：
- 对于 k=0（块大小 \(2^0=1\) 单位，如1KB），维护链表
free_list[0]； - 对于 k=1（块大小 \(2^1=2\) 单位，如2KB），维护链表
free_list[1]； - 以此类推，直到最大块大小 kmax（如系统总内存对应的 k）。
每个链表节点保存空闲块的起始地址（大小隐含为 \(2^k\)）。
Jemalloc
Jemalloc是一款专为高并发、大内存场景设计的内存分配器，其核心目标是解决传统分配器（如glibc的malloc）在多线程环境下的锁竞争、内存碎片和大规模内存管理效率低下的问题。