超基本的なリストとLazyListアルゴリズムの実装。
List and LazyList
論文: "A Lazy Concurrent List-Based Set Algorithm"の[実装。
List処理の基本:追加,削除は、1)リストの検索、と2)リストの追加,削除の2段階に分けることができる。
このうち、1)リストの検索はロックをせず"楽観的"、"怠惰"に行うのがこの論文である。
ロックはノード毎に設定する。今回は各ノードにpthread_mutex変数を設定した。
簡単に図示すると以下のようになる(原論文の図に鍵の絵を加えた)：
ただし、ロックをかけるタイミングによっては削除するノードの次に新ノードを追加してしまう可能性もあるので、削除するノードにマーキングして"論理的に削除"し、追加と削除を並行実行しても不都合が起きないようにしている。
考察
相互排他メカニズム
今回はpthread_mutex変数を使ったが、もっと軽いメカニズム、例えばfutexなどの実装も試す予定。ただし、いろいろと議論や主義などがある： http://postgresql.g.hatena.ne.jp/pgsql/20091019
http://www.atmarkit.co.jp/flinux/rensai/watch2009/watch11a.html
Lock-Free v.s. Lazy
一概にどちらがよいとは言えない。現在デバック中なのではっきりしたことは言えないが、Lock-Freeだからといって処理が速いとは言えない。
アルゴリズムによっては再試行が多すぎて効率的でないものもある。
ここらの議論は次回以降で。
