引き続きLock-Freeアルゴリズム。Lock-Free Queueの2実装。
CAS based Lock-Free Queue
一つ目はCASを使ったLock-Free Queueの論文で提案されたアルゴリズムの実装。
特徴としては:
1. 非常にシンプル
2. スレッド数に制限がないこと(予めスレッド数の上限を設定しなくてよい)
3. 使われるメモリ領域はqueueの要素数に比例し、スレッド数に依存しない(スレッドはメモリ領域を要求しない)
これはかなり良い性質である。なぜならLock-Freeなアルゴリズムは複雑怪奇なものが多く、予めスレッド数の上限を指定しなければならないものや、スレッド毎にかなりのメモリ領域を要求するものも多いからだ*1。
LL/SC based Lock-Free Queue]
二つ目はLL/SCを利用したLock-Free Queueの論文の実装。
このアルゴリズムもよい特徴を備えている。
1. スレッド数に制限がないこと(予めスレッド数の上限を設定しなくてよい)
2. 使われるメモリ領域はqueueの要素数に比例し、各スレッドも8バイト(X86環境)か16バイト(X86_64環境)程度しか使わない
連日、Lock-Freeアルゴリズムをアップしたが、
Concurrnt Algorithm == Lock-Free, Wait-Free Algorithmというわけではない。要するに掴みネタ。
Lock-FreeでなくともLazyなやつとかFineGrainedなやつとかもあって、そっちのほうが実用的な気もする。
とりあえず、今回の目的意識をここに書いてみた。
今後は、もう少し時間間隔をあけて少しずつ実装や調査結果などをアップしていく予定。
