Concurrent Fixed-Size Allocation and Free in Constant Time

2020/08/10 by Blelloch, Guy E., Wei, Yuanhao
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2008.04296

Abstract

Our goal is to efficiently solve the dynamic memory allocation problem in a concurrent setting where processes run asynchronously. On p processes, we can support allocation and free for fixed-sized blocks with O(1) worst-case time per operation, Θ(p²) additive space overhead, and using only single-word read, write, and CAS. While many algorithms rely on having constant-time fixed-size allocate and free, we present the first implementation of these two operations that is constant time with reasonable space overhead.

Related

• LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations using only pointer-width CAS
• Concurrent Reference Counting and Resource Management in Wait-free Constant Time
• A distributed resource allocation algorithm for many processes
• Memory Bounds for Concurrent Bounded Queues
• Concurrency and Scalability versus Fragmentation and Compaction with Compact-fit