５年くらい前に作ったマルチスレッドの分散アルゴリズム群を64bit対応にして再リリース。 ソースコードや使い方はこちらを参照プログラムリスト： Queue "Bringing Practical LockFree Synchronization to 64Bit Applications" by Simon Doherty, Maurice He…

3年ほど前に(後述するライブラリを目的に)読んだ"Introduction Of Reliable Distributed Programming"を、復習も兼ねてレビュー。 注意：すでに2nd Edition "Introduction to Reliable and Secure Distributed Programming" が出ているが、このレビューは1st…

続いて、Open Address型ハッシュテーブルのアルゴリズム3題。オープンアドレスハッシュ/Cuchooハッシュ/ConcurrentCuchooハッシュハッシュテーブル全般についてはこちらを参照のこと。

しばらく間があいてしまったが、Chain型Hashtableのアルゴリズム3題。単純なハッシュ/Stripedハッシュ/細粒度ハッシュハッシュテーブル全般についてはこちらを参照のこと。

特になんていうこともない細粒度LockのListアルゴリズム。 "the Art of Multiprocessor Programming"に載っていたJava版をCで再実装したもの。詳細はこちらソースはこちら

特になんていうこともないSkiplistのLazy版アルゴリズム。"A Simple Optimistic skip-list Algorithm"の[実装。詳細はこちらソースはこちら

引き続きCASベースのLock-Free Listアルゴリズムの実装。ソースはこちら 論文は"Lock-Free Linked Lists and Skip Lists" Mikhail Fomitchev, Eric Ruppert。先日の "A Pragmatic Implementation of Non-Blocking Linked-Lists"と比較すると:先日の実装は、…

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)リストの…

引き続き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なアルゴリズムが実装できないた…