16

ロックフリーの単方向リンクリストを作成しようとしています。結果整合性は問題ではありません (間違ったアイテムを含む可能性のあるリストをトラバースする人)。

アイテムを正しく追加できたと思います（ループとInterlocked.CompareExchange）。

Nextしかし、前の項目を取得する必要があり、そのフィールドを現在のノードフィールドに設定する必要があるため、ノード (リスト内の任意の場所) を削除する方法がわかりませんNext。

class Node
{
    Node Next;
    object Value;
}

class SinglyLinkedList
{
    Root _root;

    public void Add(object value)
    {}

    public void Remove(object value)
    {}
}

すなわち

a -> b -> c

に

a -> c

擬似コード:

Node prev;
Node node = _root;
while (node.Value != nodeValue)
{
  prev = node;
  node = node.Next;
}
prev.Next = node.Next;

これをアトミック操作にする方法はprev.Next = node.Next?

代わりに使用することもできますReaderWriterLockSlimが、ロックのないリンクされたリストが存在することを知っているため、この問題は興味深いものでした。

私の懸念：

現在のスレッドがループと割り当ての間で中断されている場合、次のことが発生する可能性があります。

  • prevそれ自体が別のスレッドによって削除された可能性があります。
  • node他のスレッドで削除された可能性があります。
  • Node.Next削除されたかもしれません
4

1 に答える 1

24

はい、追加は、前の .Next ポインターに CAS を使用した単純な 2 ステップのループです。でも外すの大変！

実際には、追加の情報とロジックを使用せずにそれを行うことはできません。

Harris は、一度設定すると誰でもノードを変更できないようにするマーカー ビットを追加することで、この問題の解決策を作成しました。削除は 2 段階になります。最初に (CAS) 削除されたノードにマークを付けて、誰もそれを変更できないようにします (特にその .Next ポインター)。2 番目の CAS は前のノード .Next ポインターであり、もう一方のノードがマークされているため安全です。

問題は、C でハリスが .Next ポインターの最下位 2 ビットをマーカーとして使用したことです。4 バイトでアラインされたポインターでは常に使用されず (つまり 00)、32 ビット ポインターに収まるため、ポインター自体とアトミックに CAS できるため、これは賢明です。これがこのアルゴリズムの鍵です。もちろん、これは少なくとも安全でないコードを使用しない限り、C# では不可能です。

ソリューションはもう少し複雑になり、2 つのフィールド (.Next + マーカー) を含む不変クラスへの参照が追加されます。

これらのアイデアの長い説明に入る代わりに、必要なすべての詳細を説明する参考文献をインターネットで見つけました。以下を参照してください。

Lock-free Linked List (パート 1)問題を説明します。

Lock-free Linked List (Part 2) C ソリューション + スピンロック ソリューションについて説明します。

Lock-free Linked List (パート 3)不変状態の参照について説明します。

このトピックに本当に興味がある場合は、さまざまなソリューションとそのパフォーマンスの分析を含む学術論文があります。

于 2013-06-03T17:07:52.433 に答える