How to write a thread-safe and efficient, lock-free memory allocator in C?

c multithreading memory performance allocation
Viet picture Viet · Jan 3, 2010 · Viewed 8.1k times · Source

How to write a thread-safe and efficient, lock-free memory allocator in C? By efficient I mean:

  1. Fast allocation & deallocation

  2. Optimal memory usage (minimal wastage and no external fragmentation)

  3. Minimal meta-data overhead

Answer

paxos1977 picture paxos1977 · Jan 3, 2010

http://www.research.ibm.com/people/m/michael/pldi-2004.pdf

This paper presents a completely lock-free memory allocator. It uses only widely-available operating system support and hardware atomic instructions. It offers guaranteed availability even under arbitrary thread termination and crash-failure, and it is immune to dead-lock regardless of scheduling policies, and hence it can be used even in interrupt handlers and real-time applications without requiring special scheduler support. Also, by leveraging some high-level structures from Hoard, our allocator is highly scalable, limits space blowup to a constant factor, and is capable of avoiding false sharing...

Related questions

Undefined reference to pthread_create in Linux

I picked up the following demo off the web from https://computing.llnl.gov/tutorials/pthreads/ #include <pthread.h> #include <stdio.h> #define NUM_THREADS 5 void *PrintHello(void *threadid) { long tid; tid = (long)threadid; printf("Hello …

Read More
Mutex example / tutorial?

I'm new to multithreading, and was trying to understand how mutexes work. Did a lot of Googling but it still left some doubts of how it works because I created my own program in which locking didn't work. One absolutely …

Read More
Programmatically find the number of cores on a machine

Is there a way to determine how many cores a machine has from C/C++ in a platform-independent way? If no such thing exists, what about determining it per-platform (Windows/*nix/Mac)?

Read More