アルゴリズム
５年くらい前に作ったマルチスレッドの分散アルゴリズム群を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なアルゴリズムが実装できないた…
