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, InitializeSListHeadWin32でのロックフリーの単一リンクリスト操作のための関数です。他のOSで対応する操作を使用します。

欠点：

  • オーバーヘッドsizeof( SLIST_ENTRY )
  • バケットは、開始時に1回だけ効率的に拡張できます。その後、メモリが不足し、OS/他のバケットに問い合わせる必要があります。（他のバケットは断片化につながります）
  • このサンプルは少し簡単すぎるため、より多くのケースを処理するには拡張する必要があります
于 2010-01-03T19:29:55.273 に答える