In this work, we introduce our proposed solution through the design of XMalloc, a truly scalable, efficient lock-free memory allocator. We will present (1) our solution for transforming traditional atomic compare-and-swap based lock-free algorithm to scale on SIMD architectures, and (2) a hierarchical cachelike buffer solution to reduce the average latency of accesses to non-scalable or slow resources such as main memory in a many-core machine.

Scalable Lock-Free Dynamic Memory Allocation

  • By Stephane Carrez
  • 2016-05-15 08:11:23

Dynamic memory allocators (malloc/free) rely on mutual exclusion locks for protecting the consistency of their shared data structures under multithreading. The use of locking has many disadvantages with respect to performance, availability, robustness, and programming flexibility. A lock-free memory allocator guarantees progress regardless of whether some threads are delayed or even killed and regardless of scheduling policies. This paper presents a completely lockfree memory allocator.

Practical lock-free data structures

  • By Stephane Carrez
  • 2014-07-23 20:15:53

Cambridge University introduction page that provides interesting papers about concurrent programming without locks. They provide a lock free library with MCAS and transactional memory.

An Introduction to Lock-Free Programming

  • By Stephane Carrez
  • 2014-07-23 20:02:44

An explanation of basic mechanisms used in lock free programming: atomic-read-modify-write operations, compare and swap as well as memory barriers are briefly mentioned.

Lock Free Programming (PDF)

  • By Stephane Carrez
  • 2014-05-31 13:35:28

An interesting presentation by Geoff Langdale about some lock free algorithms and the complexity in implementing such algorithm.

  • Page 1