NBBS: A Non-Blocking Buddy System for Multi-Core Machines

作     者：Marotta, Romolo Ianni, Mauro Pellegrini, Alessandro Quaglia, Francesco 

作者机构：Univ Roma La Sapienza I-00185 Rome Italy Lockless Srl I-00185 Rome Italy Univ Roma Tor Vergata I-00133 Rome Italy 

出 版 物：《IEEE TRANSACTIONS ON COMPUTERS》 (IEEE计算机汇刊)

年 卷 期：2022年第71卷第3期

页      面：599-612页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Instruction sets Resource management Memory management Proposals Scalability Message systems Data structures Non-blocking algorithms shared-memory algorithms back-end memory allocation buddy system 

摘      要：Common implementations of core memory allocation components handle concurrent allocation/release requests by synchronizing threads via spin-locks. This approach is not prone to scale, a problem that has been addressed in the literature by introducing layered allocation services or replicating the core allocators-the bottom-most ones within the layered architecture. Both these solutions tend to reduce the pressure of actual concurrent accesses to each individual core allocator. In this article, we explore an alternative approach to scalability of memory allocation/release, which can be still combined with those literature proposals. We present a fully non-blocking buddy system, where threads performing concurrent allocations/releases do not undergo any spin-lock based synchronization. Our solution allows threads to proceed in parallel, and commit their allocations/releases unless a conflict is materialized while handling the allocator metadata-memory fragmentation and coalescing are also carried out in a fully non-blocking manner. Conflict detection relies in our solution on atomic Read-Modify-Write (RMW) machine instructions, guaranteed to execute atomically by the processor firmware. We also provide a proof of the correctness of our non-blocking buddy system and show the results of an experimental study that outlines the effectiveness of our solution.