5

単純なポインターインクリメントアロケーターの場合 (正式な名前はありますか?) ロックフリーのアルゴリズムを探しています。些細なことのように思えますが、私の実装が正しいかどうかについてのフィードバックが欲しいです。

非スレッドセーフ実装:

byte * head;  // current head of remaining buffer
byte * end;   // end of remaining buffer

void * Alloc(size_t size)
{
   if (end-head < size)
     return 0; // allocation failure

   void * result = head;
   head += size;
   return head;
}

スレッドセーフな実装での私の試み:

void * Alloc(size_t size)
{
  byte * current;
  do 
  {
     current = head;
     if (end - current < size)
        return 0;  // allocation failure
  } while (CMPXCHG(&head, current+size, current) != current));
  return current;
}

whereCMPXCHGは引数付きの連動比較交換で(destination, exchangeValue, comparand)、元の値を返します

私には良さそうです - 別のスレッドが get-current と cmpxchg の間に割り当てを行うと、ループが再試行されます。コメントはありますか？

4

1 に答える 1

3

現在のコードは機能しているようです。コードは以下のコードと同じように動作します。これは、副作用のない単一のデータ ワードで動作するロックフリー アルゴリズムを実装するために使用できる単純なパターンです。

do
{
    original = *data; // Capture.

    result = DoOperation(original); // Attempt operation
} while (CMPXCHG(data, result, original) != original);

編集:インターロックされた追加の最初の提案は、ここではうまく機能しません。十分なスペースが残っていない場合、割り当ての試行と失敗をサポートしているためです。InterlockedAdd を使用した場合、ポインターは既に変更されており、後続の割り当てが失敗します。

于 2009-08-28T21:01:25.790 に答える