c - 片方向リスト挿入同期

Question

重複を含まない N 個の整数とk個のスレッド (ここでk << N )のソートされた片方向リンクのリストがあり、それぞれが何らかの整数 (ヘッド ノードより大きい) をリストに挿入しようとしているとします。

次のようなリストへの挿入を同期することは可能ですか?

• スレッドは、その (直前の) 前のノードへのアクセスのみをブロックできます
  (「リスト全体」をロックしません)。
• 最大で O(k) 個のミューテックスと条件変数を使用できます
• プリエンプション/割り込みは発生しない

?

Answer 1

まず、コレクションへの挿入が非常にまれなタスクである場合、リンクされたリストはこれに対する優れた解決策ではありません-挿入ポイントを見つけることはO(N)、並べ替えられたリストであっても操作であり、したがってスケーリングが不十分になるためです。 .

それでもそれを行う必要がある場合は、ソートされたリストへの挿入 (削除とは異なり) をロックレス操作として実行できますが、注意が必要です。

1. 挿入ポイントを見つけ、cur
2. 新しいノードを作成します (前/次のリンケージをcur/に割り当てますcur->next)
3. Atomic op:compare_and_swap(cur->next, new, new->next);
   失敗した場合: if (new->value == next->value) return; // someone beat us to it
   Else:cur = cur->nextダンスを繰り返します (リストはソートされ、誰かが私たちの前に挿入されます)

つまり、新しいノードをリンクしようとする試みの結果は、成功するか、誰かが私たちを打ち負かして同じノードを挿入するか (この場合、問題ありません - 既にそこにあります)、または誰かがギャップに挿入されます (つまり、既存はN、、、N+3私たちが試みたN+1、他の誰かが成功しN+2た) 場合、成功するか、「私たちの」ノードが他の誰かによって完了されるまで再試行します。

削除を同期するのははるかに困難です。そのためのRCU（Read-Copy-Update）を検索します。