c# - ロック（待機）無料の二重リンクリストは可能ですか？

Question

C＃タグを使用してこの質問をしますが、可能であれば、どの言語でも可能であるはずです。

インターロック操作を使用して二重リンクリストを実装し、待機なしのロックを提供することは可能ですか？挿入、追加、削除、そしてクリアするのを待たずにしたいと思います。

score 16 · Accepted Answer

はい、可能です。これが、C++でのSTLのようなロックフリーの二重リンクリストの実装です。

ABA問題なしで動作するには、64ビットのコンペアアンドスワップが必要です。このリストは、ロックフリーのメモリマネージャがあるためにのみ可能です。

12ページのベンチマークを確認してください。リストのパフォーマンスは、競合が増加するにつれてスレッドの数に比例して増加します。アルゴリズムは、互いに素なアクセスの並列処理をサポートしているため、リストサイズが大きくなると、競合が減少する可能性があります。

score 11 · Accepted Answer

単純なグーグル検索は、多くのロックフリーの二重リンクリストペーパーを明らかにします。

ただし、これらはアトミックCAS（コンペアアンドスワップ）に基づいています。

C＃での操作がどれほどアトミックかはわかりませんが、このWebサイトによると

http://www.albahari.com/threading/part4.aspx

C＃操作は、32ビットフィールドの読み取りと書き込みに対してのみアトミックであることが保証されています。CASについての言及はありません。

score 4 · Accepted Answer

これは、ロックフリーの二重リンクリストを説明する論文です。

素並列アクセス可能であり、最新のコンピューターシステムで使用可能なアトミックプリミティブを使用する並行dequeの効率的で実用的なロックフリー実装を紹介します。以前に知られているdequesのロックフリーアルゴリズムは、使用できないアトミック同期プリミティブに基づいているか、機能のサブセットのみを実装しているか、互いに素なアクセス用に設計されていません。私たちのアルゴリズムは二重にリンクされたリストに基づいており、1語のコンペアアンドスワップのみが必要です...

ロス・ベンチーナには、「ロックフリーとウェイトフリーのアルゴリズムに関するいくつかのメモ」の多数の論文とソースコードの例で私が見つけた本当に良いリンクがいくつかあります。

score 2 · Accepted Answer

1回のショットで複数の参照を設定する必要があり、インターロックされた操作の能力が制限されているため、これが可能であるとは思いません。

たとえば、追加操作を実行します。ノードBをAとCの間に挿入する場合は、1つのアトミック操作でB-> next、B-> prev、A-> next、およびC->prevを設定する必要があります。インターロックはそれを処理できません。「B」の準備中に別のスレッドが挿入を決定する可能性があるため、Bの要素を事前設定しても役に立ちません。

この場合、ロックをなくそうとするのではなく、可能な限りきめ細かくロックすることに重点を置きます。

score 1 · Accepted Answer

脚注を読む-VS2010の最終リリースの前に4.0からConcurrentLinkedListをプルする予定です

score 1 · Accepted Answer

さて、あなたは実際にそれを行う方法を尋ねていません。ただし、C＃でアトミックCASを実行できる場合は、完全に可能です。

実際、私は現在、C++で二重にリンクされた待機フリーリストの実装に取り組んでいます。

これがそれを説明する紙です。 http://www.cse.chalmers.se/~tsigas/papers/Haakan-Thesis.pdf

そして、あなたにいくつかの手がかりを提供するかもしれないプレゼンテーション。 http://www.ida.liu.se/~chrke/courses/MULTI/slides/Lock-Free_DoublyLinkedList.pdf

score 1 · Accepted Answer

ほとんどのアーキテクチャで、コピー可能なすべてのデータ構造に対してロックフリーアルゴリズムを記述できます[1]。しかし、効率的なものを書くのは難しいです。

私は、HåkanSundellとPhilippasTsigasによる.Net用のロックフリーの二重リンクリストの実装を作成しました。概念上、アトミックPopLeftをサポートしていないことに注意してください。

[1]：Maurice Herlihy：待機なしの同期の不可能性と普遍性の結果（1988）

score 0 · Accepted Answer

FWIW、.NET 4.0は、System.Collections.Concurrent名前空間にスレッドセーフな二重リンクリストであるConcurrentLinkedListを追加しています。ドキュメントまたはそれを説明しているブログ投稿を読むことができます。

score -1 · Accepted Answer

答えは、「はい、可能ですが、難しい」という非常に深い資格があると言えます。あなたが求めているものを実装するには、基本的に、衝突がないことを保証するために操作を一緒にコンパイルする何かが必要です。そのため、その目的のための一般的な実装を作成することは非常に困難であり、それでもいくつかの重要な制限があります。正確なニーズに合わせた特定の実装を作成する方がおそらく簡単であり、それでも、決して「単純」ではありません。

c# - ロック（待機）無料の二重リンクリストは可能ですか？

9 に答える 9

Related

Reference