gistfile1.txt

まず

AAA
 BBB

みたいなのじゃ困る、という要求があって

process {
  lock m
  modify v
  unlock m
}

とロックすれば

AAA
   BBB

みたいに直列化できる。

問題 1. ロックはコストが高い
問題 2. A がちんたらしてると B が悲しくなる

2 は具体的には

AAAAAAAAAAAA
            BBB

B が泣く

「計算が依存する値が書き換えられていないことを確認した後、何らかの処理を行う」のようなことをアトミックにできる場合に、「何らかの処理」に副作用を押し込めるとき、

process {
  o = v
  loop {
    modify v
    break if compare_exchange o v
  }
}

みたいにすれば

AAAAAAAAAX AAAAAAAA
  BBB

とかなって、他人に待たされることが無くなるのが lock-free

それでも

AAA  AAA  AAA (gomen...
 BBBX BBBX BBBX (tasukete-

みたいなイジメが発生して困るので「副作用をどうにかしてアトミックに提供されている人に押し付ける」ことにしよう！都合よくアトミックに提供されている人がいるとして

process {
  some_process
  atomic_na_nanika
}

とかやって

AAAa AAAa
 BBBb BBBb

A と B は直列化できなかったけれど本当に直列化したかった a と b はなんとかなりました！が wait-free

という理解なのですがどうなんでしょうか