2010-12-22この記事は カーネル／VM Advent Calendar http://atnd.org/events/10701 のために書かれました。 これまで複数回に渡ってlock-freeデータ構造を紹介して来ましたが そもそもの前提を話していなかったり目的も不明だったりと不備だった点があったので 根元から一度おさらいしてみたいと思います。 まずロックを用いる事の欠点から 上図のような構図でロックによる相互排他を行うと様々な問題が発生します。 具体的に言うと排他に成功したスレッドに様々な災難が降りかかります。 主な事例として ↑ロック確保できたのにOSによってプリエンプションされる。 ↑物理メモリに乗ってない仮想メモリにアクセスしてしまった。 ↑キャッシュミスヒットによるメモリ待ち。 そんなに気にするほどのパフォーマンス低下ではないと思うかも知れませんが マルチコアの方向へ舵を切った新世代CPU
冬のLock-Free祭り
