CASベースの比較的単純なアルゴリズムを[実装。論文は"A Pragmatic Implementation of Non-Blocking Linked-Lists" アルゴリズムを簡単に図示する(原論文の図に注釈したもの)： 図の上部は避けなければならない状況の説明で、削除(10)と挿入(20)が並行して …

超基本的なリストとLazyListアルゴリズムの実装。 List and LazyList 論文: "A Lazy Concurrent List-Based Set Algorithm"の[実装。List処理の基本:追加,削除は、1)リストの検索、と2)リストの追加,削除の2段階に分けることができる。このうち、1)リストの…

無理矢理"concurrent"ネタの流れでpg_rmanの紹介。 concurrent pg_restore バージョン8.4のpg_restoreから、リストアを並行して行う"-j"オプションが追加された。百聞は一見にしかず、実際に従来の1プロセスでのリストアと、2プロセスでの並行リストアを行っ…

引き続きLock-Freeアルゴリズム。Lock-Free Queueの2実装。 CAS based Lock-Free Queue 一つ目はCASを使ったLock-Free Queueの論文で提案されたアルゴリズムの実装。特徴としては: 1. 非常にシンプル 2. スレッド数に制限がないこと(予めスレッド数の上限を…

マルチコアCPUの時代なので、アルゴリズムの復習がてらいろいろ実装してみることにした。 手始めにSkiplistとLock-Free Skiplist。言語はC。Javaは楽すぎて難点が分からないし、LL系ではatomicな処理ができないのでlock-freeなアルゴリズムが実装できないた…