10

スタックのロックフリーの実装をいくつか見てきました...私の質問は、原子性ではなく可視性に関するものです。たとえば、ロック フリー スタックの要素 (ポインターではない) は最大 64 ビットである必要がありますか? 可視性を保証できないため、そう思います。実際の例: この構造体を安全に挿入し、ロックのないコンテナーから削除できますか

struct person
{
   string name;
   uint32_t age;
}

編集：一部の人々は質問に混乱しています。少し説明すると、ライターが人物をスタックにプッシュすると、リーダーはそれを取得します。リーダーが（メモリの可視性）人物の正しいコンテンツを見ることが保証されます。

4

7 に答える 7

3

間違っているかもしれませんが、質問は間違っていると思います。

アトミック命令は通常、単一ポインター長のデータを処理します。せいぜい、2 ポインター長分のデータを使用します。

典型的な構造は、大きすぎるためアトミックに操作できません。

したがって、ロックフリースタックは、要素へのポインタを操作するだけです（AFAIKは、ポインタの長さの境界で整列する必要があります-これが当てはまらないプラットフォームは知りません）。

于 2011-09-29T03:31:05.503 に答える
2

私は自分自身の質問に少し混乱していることを認めなければなりません...

ロックフリーのデータ構造は、ノードへの (マシン サイズとアライメントの) ポインターを操作することによって存在します。これらのノードには、ロックのないデータ構造の実際の「コンテンツ」が含まれます。そのコンテンツは任意のサイズにすることができるため、構造体をそこに置くことができます。ロックフリーのデータ構造の通常のノードは次のようになります。

struct Node { ATOMIC_PTR next; コンテンツ; }

コンテンツは、何かを含むメモリへのポインタ、または何かを含む直接メモリへのポインタです。ロックフリーのデータ構造を変更するときは、最初に新しいノードを割り当て、次に必要なコンテンツを入力し、最後にアトミック操作を使用してさまざまな関連ポインターを正しく設定するため、可視性はここでは問題になりません。それはあなたが行う最後のことであり、これらの操作には通常、可視性と順序を保証するためにメモリバリア自体が含まれているため、問題ありません。

于 2011-10-14T08:06:12.450 に答える
1

SOに関する他のQnAによると、

すべてのx86インターロック命令（CASを含む）は、完全なメモリバリアを意味します。したがって、少なくともx86では、ロックフリーコンテナーの要素の可視性を気にする必要はありません（CASを使用していると仮定します）。

于 2012-02-07T09:15:27.007 に答える
0

要素をスタックまたはキュー内に特定の順序で格納する必要がなく、スレッドセーフキューを使用して次のインデックスを保持する場合は、任意のサイズのデータ​​要素に対してスレッドセーフなデキューの実装を実装できます。未割り当てのアイテム、およびエンキュー/スタックされたアイテムを保持するデータスロットのインデックスを保持するためのスレッドセーフなデキュー。デキューにアイテムを書き込むには、「未割り当てスロット」キューから番号をプルし、目的のデータをそのスロットに書き込み、その番号のインデックスを「メイン」デキューにエンキューする必要があります。アイテムをフェッチするには、その番号を「メイン」デキューからプルし、別の場所にコピーしてから、その番号を「未割り当てスロット」キューにエンキューする必要があります。

このアプローチの1つの注意点は、ストールするスレッドが他のスレッドの進行を任意に遅らせることができない限り、「ロックフリー」である可能性がある一方で、1つのキューからスロットインデックスを取得する時間と別のキューに格納すると、アレイスロットが任意の時間使用できなくなる可能性があります。対照的に、より小さなデータ型で使用される待機のないスタックまたはキューの実装には、その制限がありません。スレッドは読み取りまたは書き込み中に存在しなくなる可能性があり、システムは読み取りまたは書き込みが完了したことを示す有効な状態になるか、またはスレッドが開始されなかったことを示す有効な状態になります。

于 2012-02-07T23:03:40.937 に答える
0

注：このアプローチを実際にテストする場合にのみ、この回答を正解としてマークしてください。

以下の構造体がロックフリーコンテナに安全に挿入および削除されるかどうかについての質問について：

struct person
{
   string name;
   uint32_t age;
}

冗長エンコーディングを使用すると、任意の長さのマルチバイトシーケンスをロックフリーコンテナに安全に挿入/削除できます。一度に4バイト（32ビット）を操作するためのアトミック命令がすでにあると仮定します。その場合、次のuint32_t ageようにフィールドをエンコードできます。

struct age_t
{
   uint32_t age_low;
   uint32_t age_high;
}

このフィールドage_lowには、32ビットの下位ビット（たとえば、下位16ビット）が格納されますuint32_t age。このフィールドage_highには、残りの上位ビットが格納されます。概念的に：

struct age_t
{
   uint16_t age_low;
   uint16_t id_low;
   uint16_t age_high;
   uint16_t id_high;
}

フィールドid_lowとにid_highは、ライターを識別するIDが含まれている必要があります。

読み取りは2つのアトミック32ビット読み取りとして実装され、すべてのid_部分が互いに同等である場合に成功します。失敗した場合は、読み取り操作を再開する必要があります。

書き込みは2つのアトミック32ビット書き込みとして実装され、その後にage_t値全体の読み取りが続きます。前の文で言及された読み取りが成功し、読み取られたIDが書き込まれたIDと同等である場合、書き込みは成功します。

価値についてstring：原則は同じです。値が分割された方法と同様に、バイナリ値を分割する方法を理解する必要がありますage。person構造全体の読み取り/書き込みに関しても同じです。

于 2011-10-12T21:45:51.543 に答える
0

スレッド セーフ コンテナー (ロックフリーまたはロック付き) は、コンテナーに入れるアイテムのスレッド セーフではなく、リスト/コンテナーのスレッド セーフを解決します。したがって、ロックフリースタックは、プッシュとポップがスレッドセーフでロックフリーであることを確認しますが、同じ構造体インスタンスへのポインターを保持する 2 つの異なるスレッドがある場合 (たとえば、スタックにプッシュされたスレッドは引き続きポンターと別のスレッドを保持します)スタックをポップします)構造体の一貫性を確保するために、他のスレッドセーフ対策を使用する必要があります

于 2011-11-28T11:09:04.540 に答える
0

はい、構造は使用できます。ロックフリーのデータ構造に必要なのは、構造の内部を表す単一の値をアトミックに更新する方法だけだからです。要素またはペイロードのサイズは、そのロックフリーの性質に影響を与えません。

私が理解しているように、ロックフリーのデータ構造は次のように機能します。

  1. データをコピーする
  2. データを変更する
  3. 元のオブジェクトが変更されていないことを原子的にチェックし、更新します
  4. それ以外は最初からやり直し

したがって、3 番目のステップをアトミックに実行できる限り、すべて問題ありません。

要素自体をアトミックに更新可能にしても、コンテナは要素をグループとしてまとめて管理する必要があるため、何のメリットもありません。

于 2011-09-29T03:45:54.293 に答える