lock-free stackと並行アルゴリズムの区分 - くまメモ
この記事は カーネル／VM Advent Calendar http://atnd.org/events/10701 のために書かれました。 これまで複数回に渡ってlock-freeデータ構造を紹介して来ましたが そもそもの前提を話していなかったり目的も不明だったりと不備だった点があったので 根元から一度おさらいしてみたいと思います。 まずロックを用いる事の欠点から 上図のような構図でロックによる相互排他を行うと様々な問題が発生します。 具体的に言うと排他に成功したスレッドに様々な災難が降りかかります。 主な事例として ↑ロック確保できたのにOSによってプリエンプションされる。 ↑物理メモリに乗ってない仮想メモリにアクセスしてしまった。 ↑キャッシュミスヒットによるメモリ待ち。 そんなに気にするほどのパフォーマンス低下ではないと思うかも知れませんが マルチコアの方向へ舵を切った新世代CPU
Lock-freeとWait-freeアルゴリズム - Wikipedia
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズム
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「java.util.concurrent.atomicパッケージに関しての質問」（1） Java Solution － ＠IT
マルチコア時代のLock-free入門
