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

Question

如何用C编写一个线程安全、高效、无锁的内存分配器？我所说的高效是指：

快速分配和deallocation

• Optimal内存使用(最小损耗和没有外部fragmentation)

• Minimal元-数据开销

)

Answer 1

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

本文提出了一种完全无锁的内存分配器.它只使用广泛可用的操作系统支持和硬件原子指令.即使在任意线程终止和崩溃失败的情况下，它也提供了保证的可用性，并且不管调度策略如何，它都不受死锁的影响，因此它甚至可以用于中断处理程序和实时应用程序，而不需要特殊的调度器支持。此外，通过利用来自Hoard的一些高级结构，我们的分配器具有高度的可伸缩性，将空间膨胀限制在一个常数因子上，并且能够避免错误的共享.

。

Answer 2

取决于你对效率的理解。如果我的关注点是快速完成任务，那么我可能会给每个线程一个单独的内存池来处理，还有一个自定义的“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下用于无锁单链表操作的函数.在其他OSes上使用相应的操作。

缺点：

sizeof( SLIST_ENTRY )

• The存储桶的
• 开销在开始时只能有效地增长一次，之后就会耗尽内存，必须询问OS/其他存储桶。(其他水桶导致fragmentation)
• This示例有点过于简单，必须进行扩展以处理更多的情况，