Lock-free, Wait-free
マルチコア環境でコアを同期させるためにロック機能がある。片方がロックすることで他のコアがデータを書き換えることができないようにする。ただロックするとロックされたままになるデッドロックが起こる可能性がある。
これを回避する方法がLock-free。
Wikipedia
http://ja.wikipedia.org/wiki/Lock-freeとWait-freeアルゴリズム
Compare and Swap(CAS)と呼ばれるアトミックな操作が必要なのだそうだ。これは指定されたメモリにある値と指定された値を比較し、一致すればメモリを書き換える。結果として書き替えを行ったことを示す値と書き換える前の値を返す。