title: Dynamic Lock-free memory allocators
body: <p>One of the difficulties in writing algorithms or data structures that satisfy lock-free progress guarantees is dynamic memory allocation: calling something like <code>malloc</code> or <code>new</code> isn't guaranteed to be lock-free in a portable manner.  However, many lock-free implementations of <code>malloc</code> or <code>new</code> exist, and there are also a variety of lock-free memory allocators that can be used to implement lock-free algorithms/data-structures.</p>
  
  <p>However, I still don't understand how this can actually completely satisfy lock-free progress guarantees, unless you specifically limit your data-structure or algorithm to some pre-allocated static memory pool.  But if you need <strong>dynamic</strong> memory allocation, I don't understand how any alleged lock-free memory allocator can ever be truly lock-free in the long-run.  The problem is that no matter how amazing your lock-free <code>malloc</code> or <code>new</code> might be, ultimately you may run out of memory, at which point you have to fall back on asking the operating system for more memory.  That means that ultimately you have to call <code>brk()</code> or <code>mmap()</code> or some such low-level equivalent to actually get access to more memory.  And there is simply no guarantee that any of these low-level calls are implemented in a lock-free manner.</p>
  
  <p>There's simply no way around this, (unless you're using an ancient OS like MS-DOS that doesn't provide memory protection, or you write your own completely lock-free operating system - two scenarios that are not practical or likely.)  So, how can any dynamic memory allocator truly be lock-free?</p>