Page 502 - 《软件学报》2024年第4期

2080 软件学报 2024 年第 35 卷第 4 期

锁, tcmalloc 与 Hoard 使用用户态 CAS 自旋锁.
基于无锁数据结构的通用内存分配器包括 lfmalloc [23,24] , scalloc [25] , supermalloc [26] , mimalloc [20] 与 snmalloc [21] .
在现代处理器平台上, 诸如 LL/SC, CAS, SWAP, FAA 等硬件原子原语的引入使得无锁编程成为可能 [27−34] . 无锁编
程消除了死锁与优先级反转问题, 在提供高性能的同时保证系统的高健壮性. lfmalloc [23] 基于 MP-RCS (multi-
processor restartable critical section, 多处理器可重新开始的临界区) 实现了无锁, 而另一个 lfmalloc [24] 是在 Hoard 分
配器架构引入无锁算法实现的无锁分配器. scalloc 同时使用锁和无锁数据结构的混合架构, 并利用操作系统透明
巨页 (transparent huge page) 来降低系统延迟. supermalloc 使用 x86 HTM (hardware transaction memory, 硬件事务
性内存) 机制代替了锁, 在实现无锁的同时相比其他分配器大大简化了代码实现. snmalloc 和 mimalloc 是目前最
先进的无锁分配器. snmalloc 主要针对存在大量非本线程释放的多生产者/多消费者应用场景优化. snmalloc 维护
着每线程私有的堆和分离适配的全局堆. 它使用基于 SWAP 原语的多生产者-单消费者队列处理消费者线程的远
程内存释放操作. 在全局堆的内存分配中, snmalloc 使用基于 CAS 原语的无锁栈. mimalloc 在每个连续内存页
span 中维护了不同用途的自由链表, 其中本地释放使用本地链表, 远程释放使用远程链表. 该远程链表是基于
SWAP 原语的多生产者-单消费者栈. 然而, 无锁数据的结构的引入带来了内存回收与 ABA 问题 [35−37] . 为了避免并
发编程中的 ABA 问题, mimalloc 与 snmalloc 使用带版本戳的 CAS2 原语或 LL/SC 原语. 同时, 该类分配器不允许
向操作系统释放存放元数据 (metadata) 的 span 头部页, 从而避免出现较慢的并发线程访问已释放的页的情况. 这
里的元数据指描述内存块属性 (如大小) 的数据.
1.2 专用内存分配器
与通用内存分配器不同, 专用内存分配器则是针对特定硬件或目标应用场景优化的内存分配器, 需要结合系
统硬件及软件协同设计, 以满足系统整体需求.
高性能计算系统中的内存分配算法设计通常需要考虑整个系统的内存层次结构和 CPU 核心间通信开销.
tbbmalloc 是 Intel Thread Building Block 库中默认的内存分配器 [19] , 它是针对多 socket 的高性能服务器设计的
slab 式内存分配器. 为了尽可能减少系统调用开销与并发竞争导致的核间通信开销, tbbmalloc 使用线程私有堆.
tbbmalloc 将私有的连续内存页 block 划分成许多小内存对象, 并在 block 中维护私有自由链表处理持有线程的内
存申请与释放. 非本线程的申请释放则由公开的自由链表处理. 这种设计能够防止多个跨 socket 的 CPU 核心并发
访问同一个 cache 行而导致的延迟.
TLSF 是针对实时应用设计的 O(1) 时间复杂度的动态内存分配算法 [17] . 它采用二级大小阶划分, 利用硬件
CLZ (count leading zero, 计算前导零) 指令查找二级位图实现 O(1) 的分配与释放流程. TLSF 的内存块采用分割-
合并方式管理, 通过边界标记 (boundary-tag) 维护内存块的大小与上一个内存块指针等元数据. 内存块在分配时分
割出合适的大小, 在释放时尝试与邻接内存块合并. TLSF 的问题在于它在多核并行系统中必须使用一个全局锁来
保证线程安全, 因此缺乏多核可扩展性.
内存隔离的内存分配器: Palloc 与 [6] CAMA . 对于共享内存的多核系统, cache 组相连 (set-associative) 和
[7]
DRAM bank 可能会导致 CPU 访存时间的较大变化 [8] . 在时间敏感的硬实时系统中, 访存时间的变化可能会导致
系统任务超时, 因此更高程度的内存隔离对硬实时系统尤为重要. cache 组与 DRAM bank 通常由内存地址的特定
比特位划分, 内存隔离的分配算法依据这些内存地址比特位以分区管理策略维护空闲内存, 令每个 CPU 核心分配
得到的内存所在的内存区域处于不同的 cache 组或 DRAM bank, 由此降低多核 CPU 共享物理内存对访存时间的
影响. Palloc 是 DRAM bank 感知的页式分配器, 其中空闲物理页依据所在的 DRAM bank 分区管理, 避免同一
DRAM bank 在不同的 CPU 核心间共享. 对于现代 DDR 内存而言, DRAM bank 是接收内存读写命令的基本单位,
不同 DRAM bank 的读写命令是可并行的, 因此受其他 CPU 核心访存影响较小. CAMA 是 cache 感知的内存分配
器, 它按照 CPU cache 组管理内存, 避免同一 cache 组在多核间的共享.
优化内存访问开销的内存分配器 Temeraire. 数据仓库服务器的性能统计信息显示 50%–60% 的 CPU 等待周
期是 data cache 和 TLB 未命中导致的, 为此, Hunter 等人在 tcmalloc 基础上实现了一种巨页感知的加强组件
[4]
Temeraire . 它在 tcmalloc 之上增加了 HugeAllocator 层, 该层使用启发式算法尽可能填充巨页中的碎片, 并使用