11

互いに多くの通信を行っているスレッドがたくさんあります。私はこれがロックフリーであることを望みます。

スレッドごとに、他のスレッドがメッセージを送信できるメールボックスが必要です (ただし、メッセージを削除できるのは所有者だけです)。これは、複数の生産者と単一の消費者の状況です。ロックフリー/ハイパフォーマンスの問題でこれを行うことは可能ですか? (これは、巨大なシミュレーションの内側のループにあります。)

4

4 に答える 4

10

Lock-free Multiple Producer Single Consumer (MPSC) キューは、最も簡単に実装できるロックフリー アルゴリズムの 1 つです。

最も基本的な実装では、push() と flush() のみを使用した単純なロックのない単一リンク リスト (SList) が必要です。この関数は、InterlockedFlushSList() および InterlockedPushEntrySList() として Windows API で使用できますが、これらは独自に展開するのが非常に簡単です。

CAS (インターロックされた比較と交換) を使用して SList に複数の Producer push() アイテム。

シングル コンシューマは、XCHG (連動交換) を使用して SList の先頭を NULL と交換する flush() を実行します。コンシューマは、逆順のアイテムのリストを持っています。

アイテムを順番に処理するには、処理する前に、flush() から返されたリストを単純に逆にする必要があります。順序を気にしない場合は、すぐにリストをたどって処理することができます。

独自の関数をロールする場合の 2 つの注意事項:

1) メモリの順序付けが弱いシステム (PowerPC など) を使用している場合は、push() 関数の先頭に「メモリ バリアの解放」を配置し、flush() の最後に「メモリ バリアの取得」を配置する必要があります。 ） 関数。

2) pop() 関数の実行中に SLists の ABA 問題が発生するため、関数を大幅に簡素化および最適化できます。push() と flush() のみを使用する場合、SList で ABA の問題が発生することはありません。これは、非ロックフリー コードと非常によく似た単一のポインターとして実装できることを意味し、ABA 防止シーケンス カウンターは必要ありません。

于 2010-09-30T02:53:36.800 に答える
3

CompareAndSwap確かに、アトミックな命令がある場合:

for (i = 0; ; i = (i + 1) % MAILBOX_SIZE)
{
    if ((mailbox[i].owned == false) &&
        (CompareAndSwap(&mailbox[i].owned, true, false) == false))
        break;
}

mailbox[i].message = message;
mailbox[i].ready = true;

メッセージを読み取った後、消費スレッドはmailbox[i].ready = false; mailbox[i].owned = false;(その順序で) 設定するだけです。

于 2010-01-28T02:12:31.170 に答える
2

これはロチェスター大学の論文で、ノンブロッキングの並行キューを示しています。この論文で説明されているアルゴリズムは、ロックレス キューを作成するための 1 つの手法を示しています。

于 2010-01-28T02:01:27.907 に答える
0

Intel スレッドのビルディング ブロックを見たいと思うかもしれませんが、Intel の開発者による講義で、それらの線に沿って何かを言及したことを思い出します。

于 2010-01-28T01:57:46.273 に答える