ロック（待機）フリーの二重リンクリストは可能ですか？

C＃タグでこの質問をしますが、可能であればどの言語でも可能です。ロック（待機）フリーの二重リンクリストは可能ですか？

ノーウェイトロックを提供するために連動操作を使用して二重リンクリストを実装することは可能ですか？私は挿入し、追加し、削除し、待たずにクリアしたいと思う。

出典

2009-05-11 esac

は、すべてのスレッドがプロセスを作ることができる無料の手段を待って、いくつかのスレッドが進歩を遂げることができます無料の手段をロック....無料のロックとフリー待つ異なっています。 – user997112

単純なgoogle検索では、多くのロックフリーの二重リンクリストペーパーが公開されます。

ただし、それらは原子CAS（比較とスワップ）に基づいています。

私はC＃での操作がどのように原子知りませんが、このウェブサイトによると

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

C＃の操作はのみ読み取りおよび32ビットのフィールドを記述するための原子であることが保証されています。 CASの言及はありません。

出典

2009-05-11 20:06:03 Unknown

+13

C＃（.NET）にはアトミックのCompare-and-Swapが絶対にあります。 Interlocked.CompareExchangeと呼ばれます。 http://esdn.microsoft.com/en-us/library/system.threading.interlocked.compareexchange.aspx – Cheeso

@ Cheeso、その場合、可能です。 – Unknown

これは、マルチスレッドのユーザーインターフェイスを実装するために使用できます。 – luvieere

ワンショットで複数のリファレンスを設定する必要があり、連動した操作の能力が限られているので、これは可能ではないと思います。

たとえば、AとCの間にノードBを挿入する場合は、B-> next、B-> prev、A-> next、およびC-> prevを1つに設定する必要があります原子操作。連動してもそれは処理できません。 Bの要素をプリセットすることは助けにはならない。なぜなら、「B」を準備している間に別のスレッドが挿入を行うことができるからだ。

私はこの場合ロックを可能な限り細かくし、それを排除しようとはしません。

出典

2009-05-11 20:03:28

"可能な限り細かいロックを取得する" - アプリケーションのマクロ動作に応じて、多くの短いロックを取り出すコストが避けられた待機時間よりも重要な場合があるため、速度が遅くなる可能性があります。 –

良い点、Earwicker。プロファイリングにはここで利点があります –

この回答は間違っています。二重リンクリストが実装されました。キーは、バックポインタが常に最新のものではないため、逆方向にトラバースするときには余分な作業が必要です。 –

-1

私は答えが非常に深い認定されていると言います。「はい、それはです。ですが、難しいです。あなたが求めているものを実装するには、基本的には、衝突を起こさないために操作をまとめてコンパイルするものが必要です。したがって、その目的のために一般的な実装を作成することは非常に難しく、依然としていくつかの重要な制限があります。正確なニーズに合わせた特定の実装を作成する方が簡単かもしれませんし、それでいてどんな方法でも「シンプル」ではないでしょう。

出典

2009-05-11 20:04:20

「衝突を確実に防ぐために操作をまとめてコンパイルするもの」 - それはどういう意味ですか？ –

現代のCPUが高い命令スループットを達成するために1つのコアで複数の実行ユニットをどのように利用するか、命令の実行ユニットとの相互作用が非相互依存性であることがチェックされ、マイクロ命令がインターリーブされ、順序依存の動作がすべて保持される。これは基本的にコンパイル操作です。 –

ほとんどの言語では、コンパイラとCPUの両方から読取り/書込み操作を移動できないようにする何らかの「メモリ障壁」が備わっているため、これはほとんど問題ではないため、操作を再配置しないことを確認できますあなたがコードであることを無効にする方法で。（その理由は、c/C++のvolatileキーワードが発明されたのですが、volatileは他の揮発性変数に対してのみ保証されているため、メモリバリアが導入されています）。 –

paperここには、ロックフリーの二重リンクリストがディスクリートされています。

我々は互いに素並列アクセス可能であり、現代のコンピュータシステムに用意されていアトミックプリミティブを使用しています同時両端キューの効率的かつ実用的なロックフリーな実装を提示。以前にdequeのの公知のロックフリーアルゴリズムはいずれかの非利用可能原子同期プリミティブに基づいている、のみ機能のサブセットを実装する、または互いに素なアクセスのために設計されていません。当社のアルゴリズムは、二重リンクリストに基づいてで、は、単一の単語スワップを比較-と-を必要と...

ロスBencinaは、私はちょうどnumerious論文やソースコードexcamplesで見つかったいくつかの本当に良いリンクがあります"Some notes on lock-free and wait-free algorithms"の場合

出典

2009-05-29 11:08:33 RandomNickName42

しかし、AFAIK、* ALL *の二重リンクリスト（実際には、単独でリンクされたリストでもよい）はGCを必要とします。 –

私はValoisの1995年の単独リンクリストはGCを必要としないと信じています - 私はこの論文を読む必要があります。 –

Valois紙では、参照カウントを使用してロックフリーのメモリ管理を保証しています。参照カウントは、ノードへのグローバルポインタの数を表す。さらに、各スレッドは、現在使用しているノードへのポインタのハザードリストを保持します。スレッドが参照カウント0のハザードリストからポインタを削除したい場合、他のスレッドのハザードリストをスキャンして、誰かがまだそれを使用しているかどうかを確認し、誰も削除しないようにする必要があります。ロックを取ることなくハザードリストを安全にスキャンするには、いくつかのトリックがあります。 – JanKanis