如何在C中编写一个线程安全且高效的无锁内存分配器？

Question

如何在C中编写线程安全且高效的无锁内存分配器？通过高效的我的意思是：

1. 快速分配&释放

2. 优化内存使用情况（最少浪费，没有外部碎片）

3. 最少的元数据开销

Answer 1

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

本文提出了一种完全无锁的内存分配器。它只使用广泛可用的操作系统支持和硬件原子指令。它提供了保证供应，即使在任意线程 终止和死机故障，并且它不受死锁不管调度策略，因此它甚至可以在中断处理程序和实时应用 使用 ，无需特殊的调度支持。此外，通过利用一些高层次的结构从囤积居奇，我们的分配 是高度可扩展性，空间的限制，以爆破一个常数因子， 并且能够避免错误共享的...

Answer 2

Depends中关于你的意思是效率。如果我关心的是让事情变得更快，那么我可能会让每个线程都有自己独立的内存池来处理，而自定义的“malloc”会从该池中获取内存。当然，如果我的担心是速度的话，我可能会首先避免分配。

没有一个答案;你会平衡一系列的担忧。这将是几乎不可能得到一个无锁分配器，但你可以早做很少的锁定（通过分配每个线程大池），也可以使锁又小又紧，他们必须是正确的。

Answer 3

可以使用无锁列表和一些不同大小的桶。

所以：

typedef struct 
{ 
    union{ 
     SLIST_ENTRY entry; 
    void* list; 
}; 
byte mem[]; 
} mem_block; 

typedef struct 
{ 
    SLIST_HEADER root; 
} mem_block_list; 

#define BUCKET_COUNT 4 
#define BLOCKS_TO_ALLOCATE 16 

static mem_block_list Buckets[BUCKET_COUNT]; 

void init_buckets() 
{ 
    for(int i = 0; i < BUCKET_COUNT; ++i) 
    { 
     InitializeSListHead(&Buckets[i].root); 
     for(int j = 0; j < BLOCKS_TO_ALLOCATE; ++j) 
     { 
      mem_block* p = (mem_block*) malloc(sizeof(mem_block) + (0x1 << BUCKET_COUNT) * 0x8); 
      InterlockedPushEntrySList(&Buckets[i].root, &p->entry); 
     } 
    } 
} 

void* balloc(size_t size) 
{ 
    for(int i = 0; i < BUCKET_COUNT; ++i) 
    { 
     if(size <= (0x1 << i) * 0x8) 
     { 
      mem_block* p = (mem_block*) InterlockedPopEntrySList(&Buckets[i].root); 
      p->list = &Buckets[i]; 
     } 
    } 

    return 0; // block to large 
} 

void bfree(void* p) 
{ 
    mem_block* block = (mem_block*) (((byte*)p) - sizeof(block->entry)); 
    InterlockedPushEntrySList(((mem_block_list*)block)->root, &block->entry); 
} 

SLIST_ENTRY, InterlockedPushEntrySList, InterlockedPopEntrySList, InitializeSListHead是在Win32下的无锁单链表操作的功能。在其他操作系统上使用相应的操作。

缺点：

• 架空的sizeof(SLIST_ENTRY)
• 的桶只能在开始长出有效一次，之后就可以运行内存不足而不得不请求OS /桶等。 （其他桶导致碎片）
• 此示例有点太简单，必须扩展才能处理更多的案例