lock-freeについて最近学び始めた。lock-freeとはwikiから参照すると
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズムは Lock-free である。
ロックをかけずともマルチスレッドで動作をし続けるというものである。Goを例に出すとロックも何もかけずにgoroutineそれぞれである値をインクリメントする例をあげるとこんな感じ。
func (c *counter) Inc(wg *sync.WaitGroup) { defer wg.Done() c.v["wakuwaku"]++ } func main() { wg := sync.WaitGroup{} c := counter{v: make(map[string]int)} for i := 0; i < 1000; i++ { wg.Add(1) go c.Inc(&wg) } wg.Wait() fmt.Printf("%v", c.v) }
mapはgoroutine safeじゃないので数値はおかしな値になる。なのでインクリメントしている処理をクリティカルセクションとして排他制御をしてあげる。そうすると意図した結果が得られるようになる。
func (c *counter) Inc(wg *sync.WaitGroup) { defer wg.Done() c.mu.Lock() c.v["wakuwaku"]++ c.mu.Unlock() }
インクリメントする直前にロックをかけてインクリメントしたらロックを解除している。このロックされた区間が短かかったり同時に実行されるgoroutineが少なければプログラムの実行時間に対して大きな影響はないと言える。一方でクリティカルセクションでIOをしたりコンテキストスイッチが発生したりしたらどうなるだろうか？ロックを持っているスレッドがIO待ちになった瞬間クリティカルセクション待ちのgoroutineが大量に発生して実行時間が伸び続ける。さらに並列数が多ければ多いほどロック獲得待ちのgoroutineは増え続けてある処理が全く進まないように見えることも起き得る。ここで登場するのがlock-freeである。
wikiにはLock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。と書いてある。Lock-free や Wait-free アルゴリズムを作るには、CPUが専用のアトミックな命令を提供しているのでこれを使う。CASというのがある。goではsync パッケージの sync.Mutex を使う方法を先ほどあげたがCASを使うにはsync/atomic パッケージの atomic.AddUintXXというのがこちらを使うことで実現できる。
CASとはコンペア・アンド・スワップ（Compare-and-Swap、CAS）は、CPUの特別な命令の一種。不可分操作として、あるメモリ位置の内容と指定された値を比較し、等しければそのメモリ位置に別の指定された値を格納する。この操作の結果、置換が行われたかどうかを示す必要があり、単純な真理値を返すか、そのメモリ位置から読み込んだ内容（書き込んだ内容ではない）を返す。と書かれている。上記の AddUintは値の取得、比較、置換(比較の結果次第)までをatomicに実行することでロックを取らずにデータを正しく更新していくというものである。
