17

単一のプロデューサーと複数のコンシューマーをサポートするロックフリー キュー データ構造を実装する方法を探しています。Maged Michael と Michael Scott (1996) による古典的な方法を見てきましたが、彼らのバージョンでは連結リストを使用しています。境界のある循環バッファーを利用する実装が欲しいです。アトミック変数を使用するものはありますか?

余談ですが、これらの古典的な方法が、多くの動的メモリ管理を必要とするリンクリスト用に設計されている理由がわかりません。マルチスレッド プログラムでは、すべてのメモリ管理ルーチンがシリアル化されます。動的データ構造と組み合わせて使用​​することにより、ロックフリー メソッドの利点を無効にしていませんか?

Intel 64 ビット アーキテクチャで pthread ライブラリを使用して C/C++ でこれをコーディングしようとしています。

ありがとう、シリッシュ

4

4 に答える 4

9

循環バッファーを使用すると、ヘッドがテールを​​通過するのを防ぐためにブロックが必要になるため、ロックが必要になります。ただし、それ以外の場合は、ヘッド ポインターとテール ポインターをアトミックに簡単に更新できます。または場合によっては、バッファーが非常に大きく、上書きが問題にならないこともあります。(実際には、X 分間の市場データを保持するサイズの循環バッファーを備えた自動取引システムでこれを見ることができます。X 分間遅れている場合は、バッファーを上書きするよりもはるかに悪い問題が発生します)。

C++ で MS キューを実装したとき、実装が非常に簡単なスタックを使用してロック フリー アロケータを作成しました。MSQueue がある場合、コンパイル時に sizeof(MSQueue::node) がわかります。次に、必要なサイズの N 個のバッファーのスタックを作成します。N は大きくなる可能性があります。つまり、pop() が null を返す場合、ヒープに追加のブロックを要求するのは簡単で、これらはスタックにプッシュされます。より多くのメモリを求めるブロッキング呼び出し以外では、これはロック解放操作です。

T は非自明な dtor を持つことができないことに注意してください。私は、実際に機能する重要な dtors を許可するバージョンに取り組みました。しかし、プロデューサーが所有権を解放し、コンシューマーが所有権を取得した場合、T を必要な T へのポインターにするだけの方が簡単であることがわかりました。もちろん、これには T 自体がロックフリー メソッドを使用して割り当てられる必要がありますが、スタックで作成した同じアロケーターがここでも機能します。

いずれにせよ、ロックフリー プログラミングのポイントは、データ構造自体が遅くなることではありません。ポイントは次のとおりです。

  1. ロックフリーは、私をスケジューラから独立させます。ロックベースのプログラミングは、スケジューラーに依存して、ロックの所有者がロックを解放できるように実行されていることを確認します。これが「優先順位の逆転」の原因です。Linux では、これを確実に行うためのロック属性がいくつかあります。
  2. スケジューラから独立している場合、OS でのタイムスライスの管理がはるかに簡単になり、コンテキストの切り替えがはるかに少なくなります。
  3. デッドロック、ライブロック、スケジューリング、同期化などについて心配する必要がないため、ロックフリー メソッドを使用して正しいマルチスレッド プログラムを作成する方が簡単です。ロックを解除する方法はありません
  4. ロックフリーの方法は、スケーリングがはるかに簡単です。実際、ネットワークを介したメッセージングを使用して、ロックフリーの方法を実装しました。このような分散ロックは悪夢です

そうは言っても、ロックベースの方法が望ましい、または必要な場合は多くあります

  1. コストがかかるものやコピーが不可能なものを更新するとき。ほとんどのロック フリー メソッドは、何らかのバージョニングを使用します。つまり、オブジェクトのコピーを作成し、それを更新し、共有バージョンがコピーしたときと同じかどうかを確認してから、バージョンを更新する現在のバージョンを作成します。そうでない場合は、もう一度 ecopy し、更新を適用して、もう一度確認してください。うまくいくまでこれを続けてください。オブジェクトが小さい場合はこれで問題ありませんが、オブジェクトが大きい場合やファイル ハンドルが含まれている場合などはお勧めできません。
  2. ほとんどのタイプは、ロックなしでアクセスすることはできません (STL コンテナーなど)。これらには、たとえば assert(vector.size()==vector.end()-vector.begin()) のように、非アトミック アクセスを必要とする不変条件があります。したがって、共有されているベクターを更新/読み取りする場合は、ロックする必要があります。
于 2010-04-24T14:12:05.130 に答える
6

これは古い質問ですが、誰も受け入れられた解決策を提供していません。だから私はこの情報を探しているかもしれない他の人に提供します.

このウェブサイト: http://www.1024cores.net

完全な説明とともに、いくつかの本当に便利なロックフリー/ウェイトフリー データ構造を提供します。

あなたが求めているのは、リーダー/ライターの問題に対するロックフリーのソリューションです。

参照: http://www.1024cores.net/home/lock-free-algorithms/reader-writer-problem

于 2011-12-06T11:18:00.940 に答える
1

従来の1ブロックの循環バッファの場合、これはアトミック操作では安全に実行できないと思います。1回の読み取りで多くのことを行う必要があります。次のような構造があるとします。

uint8_t* buf;
unsigned int size; // Actual max. buffer size
unsigned int length; // Actual stored data length (suppose in write prohibited from being > size)
unsigned int offset; // Start of current stored data

読んだら、次のことを行う必要があります（これはとにかく私がそれを実装した方法です、後で説明するようにいくつかのステップを交換することができます）：

  1. 読み取り長が保存長を超えていないか確認してください
  2. オフセット+読み取り長がバッファー境界を超えていないかどうかを確認します
  3. データを読み上げる
  4. オフセットを増やし、長さを減らします

これを機能させるために、確実に同期（非常にアトミック）に何をすべきですか？実際にステップ1と4を1つのアトミックステップに結合するか、明確にするために：これを同期化してください：

  1. read_lengthを確認してください。これは次のようになります。read_length=min(read_length,length);
  2. read_lengthで長さを減らします：length-=read_length
  3. オフセットからローカルコピーを取得するunsigned int local_offset = offset
  4. read_lengthでオフセットを増やします：offset+=read_length

その後、local_offsetから始めてmemcpy（または何でも）を実行し、読み取りが循環バッファーサイズ（2つのmemcpyに分割）を超えているかどうかを確認します...。これは「かなり」スレッドセーフです。writeメソッドは、読み取っているメモリを上書きする可能性があるため、その可能性を最小限に抑えるために、バッファが本当に十分に大きいことを確認してください。

さて、3と4（リンクリストの場合はそうなると思います）または1と2を不可分操作で組​​み合わせることができると想像できますが、このすべての取引を1つの不可分操作で行うことはできません:)。

ただし、消費者が非常に賢く、何を読むべきかを常に知っている場合は、「長さ」のチェックをやめることができます。書き込みオフセットを決定するための（offset + length）％sizeの古い方法は機能しなくなるため、新しいwoffset変数も必要になります。これは、実際には常にリストから1つの要素（=固定、既知のサイズ）を読み取るリンクリストの場合に近いことに注意してください。また、ここで、循環リンクリストにすると、その時点で読んでいる位置に多くの読み取りまたは書き込みを行うことができます。

最後に、私のアドバイスは、ロックを使用することです。リアルタイム720p60ビデオストリーマーにはCircularBufferクラスを使用し、読み取りと書き込みに完全に安全です）。ロックによる速度の問題はまったくありません。

于 2010-04-23T23:22:49.427 に答える