lock-free stackと並行アルゴリズムの区分

この記事は
カーネル／VM Advent Calendar http://atnd.org/events/10701
のために書かれました。

これまで複数回に渡ってlock-freeデータ構造を紹介して来ましたが
そもそもの前提を話していなかったり目的も不明だったりと不備だった点があったので
根元から一度おさらいしてみたいと思います。

まずロックを用いる事の欠点から

上図のような構図でロックによる相互排他を行うと様々な問題が発生します。
具体的に言うと排他に成功したスレッドに様々な災難が降りかかります。

主な事例として

↑ロック確保できたのにOSによってプリエンプションされる。

↑物理メモリに乗ってない仮想メモリにアクセスしてしまった。

↑キャッシュミスヒットによるメモリ待ち。

そんなに気にするほどのパフォーマンス低下ではないと思うかも知れませんが
マルチコアの方向へ舵を切った新世代CPUを使いこなすに当たっては重大なスループット低下を招きます。

ロック内のスレッドが無駄にした1クロックは

ロック外のすべてのスレッドにとっての1クロックでもあるのです。

至高のパフォーマンスを目指す近代のアルゴリズマー達はこの問題を決して野放しにはしませんでした。

その対策の一部がこれから紹介するnon-blockingデータ構造の数々です。