3

一部のデータ構造をロックフリーにする方法が本当にわかりません。たとえば、リンクされたリストがある場合、操作をミューテックスで囲むか、新しいノードを再リンクするのに忙しい間に別のスレッドが実行されると、競合状態になる可能性があります。

「ロックフリー」の概念（「ロックなし」という意味ではなく、他のスレッドが終了するのを待たずにスレッドが進行できることを意味します）は意味がありません。

別のスレッドの生産性を妨げずに競合状態を防ぐ方法を理解できないため、「ロックフリー」として実装されているスタック、キュー、またはリンクされたリストなどを使用した簡単な例を教えてください。この二つの目的は相反するのではないでしょうか？

4

7 に答える 7

4

ロックレス データ構造はアトミック操作を使用するため、追加の要件が課される場合があります。たとえば、データ構造は、1 つのリーダー スレッドと 1 つのライター スレッド、またはその他の組み合わせに対してのみ安全である場合があります。単純なリンクされたリストの場合、複数のスレッドが同時に安全に読み書きできることを保証するために、ノード ポインターへのアトミックな読み取りと書き込みを使用します。

それだけでうまくいくかもしれないし、うまくいかないかもしれません。データ構造の内容と検証について追加の保証が必要な場合は、何らかの形式の高レベルのロックなしではおそらくこれを行うことができません。また、データ構造の使用方法に関する追加の要件を考慮したとしても、すべてのデータ構造をロックフリーに書き換えることができるわけではありません。そのような場合、不変オブジェクトが解決策になる可能性がありますが、通常はコピーによるパフォーマンスの低下が伴います。これは、オブジェクトをロックしてから変更するよりも常に望ましいとは限りません。

于 2014-03-01T20:56:16.223 に答える
2

このようなロックフリーのデータ構造を構築できるさまざまなプリミティブが利用可能です。たとえば、次のコードをアトミ​​ックに実行するコンペア アンド スワップ (略して CAS):

CAS(x, o, n)
  if x == o:
    x = n
    return o
  else:
    return x

この操作により、アトミックな更新を行うことができます。たとえば、要素をソートされた順序で格納し、新しい要素を挿入したり、要素が既に存在するかどうかを確認したりできる、非常に単純な連結リストを考えてみましょう。検索操作は以前と同じように機能します。要素が見つかるか、クエリよりも大きな要素が見つかるまで、すべてのリンクをトラバースします。挿入にはもう少し注意が必要です。次のように機能します。

insert(lst, x)
  xn = new-node(x)
  n = lst.head
  while True:
    n = find-before(n, x)
    xn.next = next = n.next
    if CAS(n.next, next, x) == next:
      break

find-before(n,x)x順序で先行する要素を見つけるだけです。もちろん、これは単なるスケッチです。削除をサポートしたい場合、事態はさらに複雑になります。Herlihy と Shavit の「The Art of Multiprocessor Programming」をお勧めします。また、同じモデルを実装するデータ構造を切り替えてロックフリーにすることは、多くの場合有利であることも指摘しておく必要があります。たとえば、 に相当するものを実装したい場合std::map、赤黒木でそれを行うのは面倒ですが、スキップ リストの方がはるかに扱いやすいです。

于 2014-03-01T21:53:12.503 に答える
0

ロックフリーの定義が間違っています。

ロック フリーダムにより、個々のスレッドが枯渇する可能性がありますが、システム全体のスループットが保証されます。プログラム スレッドが十分に長く実行されたときに、スレッドの少なくとも 1 つが進行することを満たす場合、アルゴリズムはロックフリーです (進行状況の適切な定義について) https://en.wikipedia.org/wiki/Non-blocking_algorithm

これは、データ構造にアクセスする複数のスレッドで 1 つだけが許可されることを意味します。残りは失敗します

ロックフリーで重要なことは、メモリ衝突の可能性です。ロックで保護されたデータ構造は、一般にアトミック変数を使用した実装よりも高速ですが、衝突のわずかな可能性があるため、うまくスケーリングできません。

例: 複数のスレッドが常にリスト内のデータを push_back します。これは多くの衝突につながり、従来のミューテックスは問題ありません。ただし、リストの最後にデータをプッシュする 1 つのスレッドと、先頭にデータをポップする 1 つのスレッドがある場合、状況は異なります。リストが空でない場合、push_back() と pop_front() は衝突しません (実装によって異なります)。これらは同じオブジェクトでは動作しないためです。ただし、空のリストの変更がまだあるため、アクセスを保護する必要があります。このシナリオでは、待機することなく両方の関数を同時に呼び出すことができるため、lock-freedom がより良い解決策になります。

要するに、ロックフリーは、複数のライターがほとんど分離され、めったに衝突しない大規模なデータ構造用に設計されています。

少し前に自分でロックフリーリストコンテナを実装しようとしました... https://codereview.stackexchange.com/questions/123201/lock-free-list-in-c

于 2016-10-18T07:10:35.290 に答える
0

変数を 1 ずつインクリメントする単純な操作を想定します。「メモリから cpu に変数を読み取り、cpu レジスタに 1 を追加し、変数を書き戻す」を使用してこれを実装する場合、2 番目のスレッドを確認したいので、全体にある種のミューテックスを配置する必要があります。最初の変数が書き戻されるまで変数を読み取りません。

プロセッサにアトミックな「インクリメント メモリ ロケーション」アセンブリ命令がある場合、ロックは必要ありません。

または、リンクされたリストに要素を挿入するとします。つまり、開始ポインターが新しい要素を指すようにし、新しい要素が前の最初の要素だった要素を指すようにする必要があります。アトミックな「2 つのメモリ セルの交換」操作を使用すると、現在の開始ポインターを新しい要素の「次の」ポインターに書き込み、次に 2 つのポインターを交換できます。次に、どちらのスレッドが最初に実行されるかに応じて、要素が異なる場所に配置されます。リストの順序は変わりませんが、リストのデータ構造はそのまま残ります。

基本的に、それは常に「1 つのアトミック操作で一度に複数のことを行うため、操作を中断されない単一の部分に分割することはできません」ということです。

于 2014-03-01T20:59:35.073 に答える