wait-free是指什么?

一、wait-free是指什么

wait-free是指指一个线程能够在有限步内make progress。对于一个算法，Obstruction-freedom(无障碍)/Lock-freedom(无锁)/Wait-freedom(无等待)，从弱到强描述了在并发环境下线程的演进保证(guarantee of progress)这个属性。换句话说，它描述了线程随着指令序列的执行取得进展(make progress)的能力。

而lock-free的意思就是：只要有task在往前走(make progress)，那总有task能往前走；wait-free的意思是，只要某个task活着，不管别人在干什么，它都一定能往前走。

为什么有lock就不是lock-free了，因为只要拿到lock的那个task挂掉不动了，这个系统就完蛋了，每个task都不能再往前走了。

Lock-free和wait-free的区别在哪，在于starvation。大部分的lock-free的算法都是基于某些竞争性的原语的(primitives)。Starvation一般都是在有多个task竞争(race)的时候，也许有一个运气好的task总是在赢，那么别的task就很可怜地什么都做不了了。这不是因为没轮到他们，而只是因为他们运气坏。实际上整个系统还是在运行的，就是那个运气好的task自己一直在跑，所以这不是死锁(dead-lock)。有人把这个东西定义为live-lock，这也没法翻译了(总不能真翻成活锁吧)。

很少有天然的wait-free的算法(最天然的那个，single-reader-single-writer queue大家都知道了)。新的wait-free的算法，大都是靠胜者的施舍，也就是说有task一直赢的话，就分给输家一点，让输家能往前动一下。

延伸阅读：

二、从底层去看lock-free

lock-free是一个非常底层的东西，lock-free编程需要atomic指令这个指令是cpu提供的，cpu原生的指令有非常多都是atomic的，这些指令集分为2大类，分别是store-and-load 和read-modify-write

store-and-load

这些指令用于读，写数据到内存中，许多的cpu架构都保证这些操作是原子的，比如mov

read-modify-write

有一些操作需要多个指令比如要对内存中的一个数据进行+1，这至少需要三个原子操作指令，虽然说这3个原子操作是原子的，但是加一起就不是原子的了read-modify-write就是file the gap，在一个原子操作下去执行多个操作，比如test-and-set :将1写入到内存的地址中，然后返回旧的值，fetch-and-add:在内存中的值加上一个数字，然后返回老的值。