ノンブロッキング・アルゴリズム

ノンブロッキング・アルゴリズムは並行アルゴリズムです。並行アルゴリズムのスレッド安全性はロック処理に由来するのではなく、compare-and-swapなどの、マシン・レベルに近いアトミックなハードウェア・プリミティブに由来します。ノンブロッキング・アルゴリズムの設計と実装はきわめて困難になる場合がありますが、より高いスループットが期待でき、デッドロックや優先順位の逆転などのliveness（ライブネス）問題に対してより強固な対応が可能になります。

http://www-06.ibm.com/jp/developerworks/java/060519/j_j-jtp04186.shtml?ca=drs-