7

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

  1. 快速分配和释放

  2. 最佳内存使用（最小浪费且无外部碎片）

  3. 最小的元数据开销

4

3 回答 3

13

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

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

于 2010-01-03T19:11:03.063 回答
4

取决于你所说的效率。如果我关心的是让事情变得更快，那么我可能会给每个线程它自己的单独内存池以使用它，以及一个从该池中获取内存的自定义“malloc”。当然，如果我关心的是速度，我可能会首先避免分配。

没有一个答案；您将平衡一系列问题。获得无锁分配器几乎是不可能的，但是您可以尽早且不频繁地进行锁定（通过为每个线程分配大池），或者您可以使锁变得如此小而紧，以至于它们必须是正确的。

于 2010-01-03T18:58:58.487 回答
2

您可以使用一个无锁列表和几个不同大小的存储桶。

所以 ：

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 )
  • 存储桶在开始时只能有效增长一次，之后您可能会耗尽内存并且必须询问操作系统/其他存储桶。（其他桶导致碎片）
  • 这个示例有点太简单了，必须扩展以处理更多案例
于 2010-01-03T19:29:55.273 回答