c - ピーターソンロックアルゴリズムのテスト済みの実装?

Question

CでのPeterson の Lock アルゴリズムの適切な/正しい実装を知っている人はいますか? 私はこれを見つけることができないようです。ありがとう。

Answer 1

x86 でメモリ フェンスを注文した人で説明されているように、Peterson のアルゴリズムは C99 では正しく実装できません。

Peterson のアルゴリズムは次のとおりです。

LOCK:

interested[id] = 1                interested[other] = 1
turn = other                      turn = id

while turn == other               while turn == id
  and interested[other] == 1        and interested[id] == 1


UNLOCK:

interested[id] = 0                interested[other] = 0

ここにはいくつかの仮定が隠されています。まず、各スレッドは、順番を譲る前に、ロックを取得することに関心があることに注意する必要があります。ターンを放棄すると、ロックの取得に関心のある他のスレッドから見えるようにする必要があります。

また、すべてのロックと同様に、クリティカル セクションでのメモリ アクセスは、lock() 呼び出しを超えて引き上げることも、unlock() 呼び出しを超えて沈めることもできません。つまり、lock() には少なくとも取得セマンティクスが必要であり、unlock() には少なくともリリース セマンティクスが必要です。

C11 でこれを実現する最も簡単な方法は、順次一貫性のあるメモリ順序を使用することです。これにより、プログラムの順序で実行されるスレッドの単純なインターリーブであるかのようにコードが実行されます (警告: 完全にテストされていないコードですが、例に似ていますDmitriy V'jukov のRelacy Race Detectorで):

lock(int id)
{
    atomic_store(&interested[id], 1);
    atomic_store(&turn, 1 - id);

    while (atomic_load(&turn) == 1 - id
           && atomic_load(&interested[1 - id]) == 1);
}

unlock(int id)
{
    atomic_store(&interested[id], 0);
}

これにより、コンパイラはアルゴリズムを壊すような最適化を行わず (アトミック操作全体でロード/ストアをホイスト/シンクすることによって)、適切な CPU 命令を発行して、CPU もアルゴリズムを壊さないようにします。メモリ モデルを明示的に選択しない C11/C++11 アトミック操作の既定のメモリ モデルは、順次整合性のあるメモリ モデルです。

C11/C++11 は弱いメモリ モデルもサポートしているため、可能な限り多くの最適化が可能です。以下は、 Anthony Williamsによる C++11 への翻訳の C11 への翻訳です。元々は Dmitriy V'jukov によって彼自身の Relacy Race Detector [petersons_lock_with_C++0x_atomics] [the-inscrutable-c-memory ] ​​の構文で作成されたアルゴリズムです。 -モデル] . このアルゴリズムが正しくない場合、それは私のせいです (警告: これもテストされていないコードですが、Dmitriy V'jukov と Anthony Williams の優れたコードに基づいています):

lock(int id)
{
    atomic_store_explicit(&interested[id], 1, memory_order_relaxed);
    atomic_exchange_explicit(&turn, 1 - id, memory_order_acq_rel);

    while (atomic_load_explicit(&interested[1 - id], memory_order_acquire) == 1
           && atomic_load_explicit(&turn, memory_order_relaxed) == 1 - id);
}

unlock(int id)
{
    atomic_store_explicit(&interested[id], 0, memory_order_release);
}

取得および解放セマンティクスとの交換に注意してください。交換はアトミック RMW 操作です。アトミック RMW 操作は、RMW 操作での書き込みの前に格納された最後の値を常に読み取ります。また、同じアトミック オブジェクトのリリースからの書き込みを読み取るアトミック オブジェクトの取得 (または、リリースを実行したスレッドからのそのオブジェクトへのその後の書き込み、または任意のアトミック RMW 操作からのその後の書き込み) は、synchronizes-with を作成します。リリースと取得の関係。

したがって、この操作はスレッド間の同期ポイントであり、1 つのスレッドでの交換と任意のスレッドによって実行された最後の交換 (または最初の交換の場合はターンの初期化) の間には常に同期関係があります。

そのため、ストア tointerested[id] と exchange from/to の間には sequenced-before 関係があり、 from/toturnの 2 つの連続する交換の間に synchronizes-with 関係があり、 exchange from/toと の load のturn間に sequenced-before 関係があります。これは、スレッド間の同期を提供することで、異なるスレッドへのアクセス間の発生前の関係になります。これにより、アルゴリズムを機能させるために必要なすべての順序が強制されます。turninterested[1 - id]interested[x]turn

では、これらのことは C11 以前はどのように行われていたのでしょうか? これには、コンパイラと CPU 固有のマジックの使用が含まれていました。例として、かなり強く順序付けられた x86 を見てみましょう。IIRC、すべての x86 ロードには取得セマンティクスがあり、すべてのストアにはリリース セマンティクスがあります (SSE では、CPU 間の一貫性を実現するために CPU フェンスを発行する必要があるという犠牲を払って、より高いパフォーマンスを達成するために正確に使用される非一時的な移動を保存します)。Bartosz Milewsky が who-ordered-memory-fences-on-an-x86turnで説明しているように、Peterson のアルゴリズムが機能するには、とへのアクセス間の順序を確立する必要がありinterestedます。へのinterested[1 - id]書き込み前からのロードを見るとinterested[id]、これは悪いことです。

したがって、GCC/x86 でそれを行う方法は次のようになります (警告:次のようなものをテストしましたが、実際には、間違った実装のピーターソンアルゴリズムでコードの修正バージョンをテストしましたが、テストはマルチスレッドの正確性を保証するものではありませんコード):

lock(int id)
{
    interested[id] = 1;
    turn = 1 - id;
    __asm__ __volatile__("mfence");

    do {
        __asm__ __volatile__("":::"memory");
    } while (turn == 1 - id
           && interested[1 - id] == 1);
}

unlock(int id)
{
   interested[id] = 0;
}

これMFENCEにより、異なるメモリ アドレスへのストアとロードが並べ替えられるのを防ぐことができます。そうしないと、ロードが進行している間、書き込みがinterested[id]ストア バッファでキューに入れられる可能性があります。interested[1 - id]現在の多くのマイクロアーキテクチャでSFENCEは、a はストア バッファ ドレインとして実装される可能性があるため、a で十分かもしれSFENCEませんが、IIUC はそのように実装する必要はなく、単純にストア間の並べ替えを防ぐことができます。そのSFENCEため、どこでも十分ではない可能性があり、完全な が必要MFENCEです。

コンパイラバリア ( __asm__ __volatile__("":::"memory")) は、コンパイラが の値を既に知っていると判断するのを防ぎますturn。メモリを破壊したことをコンパイラに伝えているため、レジスタにキャッシュされたすべての値をメモリから再読み込みする必要があります。

PS: これには結びの段落が必要だと思いますが、私の頭は疲れ果てています。

Answer 2

実装がどれほど優れているか、または正しいかについては断言しませんが、(簡単に) テストされました。これは、ウィキペディアで説明されているアルゴリズムをそのまま翻訳したものです。

struct petersonslock_t {
    volatile unsigned flag[2];
    volatile unsigned turn;
};
typedef struct petersonslock_t petersonslock_t;

petersonslock_t petersonslock () {
    petersonslock_t l = { { 0U, 0U }, ~0U };
    return l;
}

void petersonslock_lock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    l->flag[p] = 1;
    l->turn = !p;
    while (l->flag[!p] && (l->turn == !p)) {}
};

void petersonslock_unlock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    l->flag[p] = 0;
};

Greg は、メモリ コヒーレンシがわずかに緩和された SMP アーキテクチャ (x86 など) では、同じメモリ位置へのロードは順番に行われますが、1 つのプロセッサの別の場所へのロードは、別のプロセッサには順不同に見える可能性があると指摘しています。

Jens Gustedt と ninjalj は、atomic_flag型を使用するように元のアルゴリズムを変更することを推奨しています。これは、フラグとターンを設定すると が使用され、atomic_flag_test_and_setそれらをクリアするとatomic_flag_clearC11 から使用されることを意味します。または、 への更新の間にメモリ バリアを課すこともできますflag。

編集:私は当初、すべての状態の同じメモリ位置に書き込むことで、これを修正しようとしました。ninjalj は、ビット単位の操作によって、元のアルゴリズムのロードとストアではなく、状態操作が RMW に変わったことを指摘しました。したがって、アトミックなビット単位の操作が必要です。C11 は、組み込みの GCC と同様に、そのような演算子を提供します。以下のアルゴリズムは GCC ビルトインを使用していますが、他の実装に簡単に変更できるようにマクロでラップされています。ただし、上記の元のアルゴリズムを変更することをお勧めします。

struct petersonslock_t {
    volatile unsigned state;
};
typedef struct petersonslock_t petersonslock_t;

#define ATOMIC_OR(x,v)   __sync_or_and_fetch(&x, v)
#define ATOMIC_AND(x,v)  __sync_and_and_fetch(&x, v)

petersonslock_t petersonslock () {
    petersonslock_t l = { 0x000000U };
    return l;
}

void petersonslock_lock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    unsigned mask = (p == 0) ? 0xFF0000 : 0x00FF00;
    ATOMIC_OR(l->state, (p == 0) ? 0x000100 : 0x010000);
    (p == 0) ? ATOMIC_OR(l->state, 0x000001) : ATOMIC_AND(l->state, 0xFFFF00);
    while ((l->state & mask) && (l->state & 0x0000FF) == !p) {}
};

void petersonslock_unlock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    ATOMIC_AND(l->state, (p == 0) ? 0xFF00FF : 0x00FFFF);
};