algorithm - ロックフリースキップリストを実装する方法

Question

ロックフリースキップリストを実装する必要があります。論文を探してみました。残念ながら、私が見つけたのは、ロックフリーの単一リンクリスト（多くのフレーバー）だけでした。しかし、ロックフリースキップリストを実装するにはどうすればよいですか？

Answer 1

ロックフリースキップリストについては、The Art of Multiprocessor Programmingの本と、このテーマに関する博士号の論文に基づいたテクニカルレポートPracticallock-freedomで説明されています。スキップリストの説明は53ページから始まります。これらのソースに基づく実装例は、このgoogleコードプロジェクトに含まれています。

SOの質問SkipListvs. Binary Tree、およびSkip Listsには、関連する議論、文献へのリンク、および実装（必ずしもロックフリーではない）があります-それらを使用したことがありますか？。

Answer 2

このペーパーでは、ロックフリーおよび待機フリーのスキップリストを紹介します。実装は簡単です-数週間前にIntelThreadingChallenge 2010の一部として実装しました（ページの途中にある[スキップリスト]タブを参照してください）。

Javaには、並行スキップリストjava.util.concurrent.ConcurrentSkipListMapの実装が含まれています。