ランク操作をサポートするロックフリーのスキップリスト実装および/または研究論文を知っている人はいますか (つまり、k 番目の要素を見つける)? または、そのような操作が機能しない根本的な理由を知っている人はいますか?
ボーナスポイント：
ガベージ コレクションを想定していない実装。私の経験では、かなりの数の研究論文がメモリ管理を無視しています。
サポート：
ランク操作が通常のスキップリストでどのように行われるかについての説明: 「A Skip List Cookbook」 by William Pugh
ロックフリーのスキップリストのより良い説明の 1 つについては、Keir Fraser による「Practical lock-freedom」を参照してください。
優れたロックフリー スキップリスト実装の 1 つ: http://www.1024cores.net/home/parallel-computing/concurrent-skip-list
スキップリスト内の要素のローカル プロパティであり、他の要素との操作の影響を受けないkey、value、およびlevelとは異なり、要素のランク、つまりリスト内の位置は、要素の挿入と削除によって変化するプロパティです。低ランクで。したがって、同時スキップリストの場合、要素のランクは非常に一時的です。これは、下位ランクの要素を挿入または削除する同時実行操作によっていつでも変更される可能性があるためです。
たとえば、レベル 1 リストでk番目の要素の線形検索を行うとします。kステップを実行した時点で、同時修正によって任意の数の前の要素が追加または削除される可能性があるため、見つけた要素の現在のランクは実際には不明です。さらに、スレッドがk回の前方反復を実行している間、現在の位置と、検索を開始したときにk番目だった要素との間で同時変更を行うことができます。したがって、検索が終了するのは、現在のランクkの要素でも、検索開始時のランクkの要素でもありません。それはただのランダム要素です！
簡単に言うと、並行リストの場合、要素のランクは定義が不十分な概念であり、ランクによる検索は定義が不十分な操作です。これが、それが機能しない根本的な理由であり、実装者がそのような操作を提供することを気にするべきではない理由です。