16

今日は、ロックレス キューを調査してきました。複数のプロデューサー、複数のコンシューマーの状況があります。テストのために、Win32 で Interlocked SList を使用するシステムを実装したところ、スレッド化されたタスク ベースのコードのパフォーマンスが 2 倍になりました。残念ながら、複数のプラットフォームをサポートしたいと考えています。複数のプラットフォームでの連動自体は問題なく、問題なく連動できると考えて間違いありません。しかし、実際の実装は私を失います。

大きな問題は、リストのプッシュ/ポップが 1 つのインターロック呼び出しのみを使用することを保証する必要があることです。そうしないと、別のスレッドが挟み込んで物事を台無しにするためのスペースを残していることになります。Microsoft の実装が内部でどのように機能するのかよくわかりません。詳しく知りたいです。

誰でも有用な情報を教えてもらえますか (プラットフォームと言語はまったく関係ありません)。

それに加えて、ロックレスベクターを実装できるかどうか知りたいです。それは私にとって非常に多くの用途があります:)乾杯！

編集: ハーブの DDJ の記事を読んだ後、私がすでに持っていたものとかなり似た、削減されたロック キューを確認できます。しかし、ダブルコンペアアンドスワップ (DCAS) 操作を使用して真のロックレスキューイングを行うことができる論文が最後にあることに気付きました。cmpxchg8b (または cmpxchg16b) を使用してキューを実装した人はいますか?

私はこの時点で（論文を読んでいない）ただ黙想していますが、このシステムを使用してヘッドポインターとテールポインターを同時に更新し、別のスレッドが2つのアトミック操作の間にジャンプする問題を回避できます。ただし、次のヘッド ポインターを取得してテール ポインターに対してテストし、テールを変更したかどうかを確認する必要があります。他のスレッドがこの情報を変更する準備をしている間に、別のスレッドがこの情報を変更しないようにするにはどうすればよいでしょうか? これはロックレスな方法でどの程度正確に実装されていますか? それとも、研究論文である解読不能性を読んだほうがよいでしょうか? ;)

4

5 に答える 5

11

おそらく、限られたサイズのキューを最も簡単に実装できるでしょう...私は最近それについて考えていて、このデザインを思いつきましたが、おそらく他にも多くの興味深いアイデアを見つけることができます: (警告: いくつかの問題があるかもしれません!)

  • キューはアイテムへのポインタの配列です
  • 循環バッファーと同じ方法でキューを処理する 2 つのポインター (ヘッド、テール) を管理する必要があります。
  • head==の場合tail、アイテムはありません
  • したい場合はenqueue(ptr)、Interlocked-Swap tailwith NULL (prev_tailはスワップされた値です)
    • の場合prev_tail == NULL、もう一度やり直してください
    • prev_tail + 1(ラップアラウンドあり) ==の場合head、キューがいっぱいです
    • それ以外の場合は、入力ptrし*prev_tailて割り当てprev_tail+1ますtail（バッファラップアラウンドに注意してください）
  • コピーをdequeue()作成するため tmp_head=head とチェックtmp_head == tail
    • true の場合、キューが空なので戻る
    • それが間違っている場合
      • *tmp_head名前を付けて保存ptr
      • CAS を行う: 比較headしてtmp_headスワップheadするhead+1
      • CAS が失敗した場合 -- 関数全体を最初からやり直す
      • 成功した場合 -- 戻るptr

ヘッド CAS 操作とテール CAS 操作の両方を待機できますが、キューが競合していない場合は、不要なロックなしで、最初は成功するはずです。

無制限のサイズのキューは「少し」難しくなります;) しかし、ほとんどのニーズに対して十分な大きさのキューを作成できるはずです。

于 2009-11-12T23:28:42.507 に答える
3

低ロック キューの Herb Sutters 実装を参照してください。

http://www.drdobbs.com/hpc-high-performance-computing/211601363

c++0x アトミックを使用しますが、特定のアーキテクチャのアトミック ops (GNU を使用する __sync_*、solaris の atomic_* など) を使用して実装するのは簡単です (そうあるべきです)。

于 2010-03-11T13:14:44.183 に答える
3

このトピックに関する興味深い議論があると思いますここ、特にこのスレッド 。

于 2009-11-12T22:19:55.640 に答える
2

これらの人は、そこにインスピレーションを見つけることができるかもしれません。その他の興味深いファイルは、yqueue.hpp と atomic_ptr.hpp です。

于 2009-11-12T22:13:09.303 に答える
1

viraptor ソリューションはロックされています。私が認識している複数のプロデューサー/複数のコンシューマーのロックレス キュー アルゴリズムはありません。

于 2010-01-19T07:12:45.857 に答える