Lock-Free List ver.1

CASベースの比較的単純なアルゴリズムを[実装

論文は"A Pragmatic Implementation of Non-Blocking Linked-Lists"


アルゴリズムを簡単に図示する(原論文の図に注釈したもの):

図の上部は避けなければならない状況の説明で、削除(10)と挿入(20)が並行して
実行された場合で、挿入するノード(20)が孤児になることをしめしている。
図の下部は今回実装したアルゴリズムで、削除するノードにマーキングして上記
の状況を避ける。


これは前回のLazy Listをごく自然にLock-Free化したもの。両者の比較や、この
アルゴリズムの改良版は次回以降で。