Lock Freeって何

複数スレッドや複数コアから同じデータを更新する場合、
通常はlockをかけて排他制御を行いますが、lockをかけずに行う方法があるらしいです。

lockをかける場合、その間そのデータにはアクセスできず、並列処理を止めてしまうため、
並列数が大きくなるに従って性能が劣化していくそうです。
lockなしで排他処理を行う場合、並列数を増やしても性能の劣化が無くなるそうです。

やっていることとしては、値をコピーして変更を加え、
「コピー前の値と現在の値が一緒かどうかをチェック」「変更した値を書き込む」を一括にやる命令を利用し、
比較と更新を同時にするというものだそうです。
(Compare-and-Swap、CAS命令)

この比較して更新する命令があることで、
ロックせずに複数から値を変更しても一貫性が保たれるらしいです。
また、この命令が無いとlock freeが実現できない事が証明されているらしいです。
コンペア・アンド・スワップ

i386ではCMPXCHG〜命令でこれが出来るらしく、
goのatomicパッケージでも利用されているようです。
https://github.com/golang/go/blob/master/src/sync/atomic/asm_386.s#L34