Lockfree Container for C++
MultiCoreを搭載するシステムが大多数を占めるようになった昨今、Core数の増加は大量のThreadを実行させるプログラムスタイルへと構造自体に変化をもたらしました。
しかし、プロセス間の排他手法であるsemaphore、そしてthread間の排他手法であるmutexと速度に応じてロックの粒度は少なくなってきました。
しかし、さらに速度が重視される分野や大量のコアを利用するアプリケーションの場合にはmutexでも粒度が大きすぎます。
これをLinuxKernelなどではatomicと云う手段を使って解決を試みています。
CPUごとに存在するCAS命令等を用いてまさにこれ以上分解できない最小限のロック粒度であるatomic命令を利用しています。
しかし、このatomic命令を使ってアルゴリズムを構築するのは容易ではないため、この分野においてはまだまだDCASなどの論文等の発表をはじめちょうど議論になっている分野です。
そこで、このatomic命令を利用したhashmapやlinked listなどのアルゴリズムの実装の提案です。