6

現在の実装では、コード内でロックフリー キューを使用して、単一のプロデューサーとコンシューマーの間のロックの競合を減らすことを検討してきました。キューの実装はたくさんありますが、ノードのメモリ管理を最適に管理する方法についてはあまり明確ではありませんでした。

たとえば、プロデューサーは次のようになります。

queue.Add( new WorkUnit(...) );

そして、消費者は次のようになります。

WorkUnit* unit = queue.RemoveFront();
unit->Execute();
delete unit;

現在、メモリ プールを割り当てに使用しています。プロデューサがメモリを割り当て、コンシューマがそれを削除することに気付くでしょう。プールを使用しているため、適切に保護するためにメモリ プールに別のロックを追加する必要があります。これは、そもそもロックフリー キューのパフォーマンス上の利点を無効にしているようです。

これまでのところ、私たちの選択肢は次のとおりだと思います。

  • ロックのないメモリ プールを実装します。
  • メモリ プールをダンプし、スレッドセーフ アロケータに依存します。

他に検討できるオプションはありますか? ロックフリー メモリ プールの実装を回避しようとしていますが、その道をたどる可能性があります。

ありがとう。

4

5 に答える 5

4

オブジェクトを作成し、不要になったときに破棄できるのはプロデューサーだけです。コンシューマーは、オブジェクトを使用して使用済みとしてマークすることしかできません。それがポイントです。この場合、メモリを共有する必要はありません。これは、効果的なロック フリー キューの実装について私が知っている唯一の方法です。

このようなアルゴリズムについて詳しく説明しているこの素晴らしい記事を読んでください。

于 2011-06-23T22:30:51.807 に答える
1

もう 1 つの可能性は、スレッドごとに個別のメモリ プールを用意することです。これにより、ヒープを使用するスレッドは 1 つだけになり、割り当てのためのロックを回避できます。

これにより、ロックフリー機能を管理してブロックを解放する必要があります。幸いなことに、これは管理が非常に簡単です。ヒープごとに空きブロックのリンク リストを維持します。ブロック自身のアドレスをリンク リストのリンク フィールド (として使用するメモリ) に入れ、リンク リストの先頭を保持しているポインターとアトミック交換を行います。

于 2011-06-23T22:57:18.100 に答える
0

Intel の TBB を参照してください。商用プロジェクトの場合、どちらかといえばいくらかかるかはわかりませんが、すでに並行キュー、並行メモリアロケーターなどがあります。

キュー インターフェイスも非常に危険に見えます。たとえば、RemoveFront() 呼び出しです。キューが空の場合はどうなるでしょうか。newanddelete呼び出しも非常に冗長に見えます。Intel の TBB と Microsoft の PPL (VS2010 に含まれる) には、これらの問題はありません。

于 2011-06-23T22:31:51.823 に答える
0

私はまったく同じ懸念を持っていたので、メモリ割り当てを管理する独自のロックフリー キュー (シングル プロデューサー、シングル コンシューマー) を作成しました (一連の連続したブロックを割り当てますstd::vector)。

最近GitHub でコードをリリースしました。（また、ブログにも書いています。）

スタック上にノードを作成し、それをキューに入れ、スタック上の別のノードにデキューする場合、ポインター/手動割り当てを使用する必要はまったくありません。さらに、ノードが構築と代入の移動セマンティクスを実装している場合、コピーではなく自動的に移動されます:-)

于 2013-02-08T23:31:04.177 に答える
0

要件が正確に何であるかはわかりませんが、プロデューサーがデータを作成し、このデータをキューにプッシュするシナリオがあり、このデータを取得して使用してから破棄する単一のコンシューマーがいる場合は、安全なキューを踏むか、このシナリオで安全な独自の単一のリンクされたリストを作成できます。

  • リスト要素を作成する
  • リスト要素にデータを追加する
  • 次の要素のポインターを null からリスト要素 (または他の言語で同等のもの) に変更します。

コンシューマーはどのような方法でも実装でき、ほとんどのリンクされたリストは、デフォルトでこの種の操作に対して安全です (ただし、その実装を確認してください)。

このシナリオでは、コンシューマはこのメモリを解放する必要があります。または、定義済みのフラグを設定するプロデューサに同じ方法で戻すことができます。プロデューサは、どのバケットが空いているかを見つけるためにすべてのフラグ (1000 以上ある場合) をチェックする必要はありませんが、このフラグをツリーのように実装して、使用可能なプールを検索する log(n) を有効にすることができます。これはロックせずにO（1）時間で実行できると確信していますが、方法がわかりません

于 2011-06-23T23:54:48.707 に答える