lock-free 和 wait-free
正好看到有文章介绍 rethinkdb 的产品使用的是 lock-free 的算法。文件见下面的连接[1]，其中对于这两个的名字解释如下：
In lock-free systems, while any particular computation may be blocked for some period of time, all CPUs are able to continue performing other computations. To put it differently, while a given thread might be blocked by other threads in a lock-free system, all CPUs can continue doing other useful work without stalls.
By contrast, wait-free algorithms ensure that in addition to all CPUs continuing to do useful work, no computation can ever be blocked by another computation. Wait-free algorithms have stronger guarantees than lock-free algorithms, and ensure a high thorughput without sacrificing latency of a particular transaction.
《The art of multiprocessor programming》书中说到：
A concurrent object implementation is wait-free if each method call finishes in a finite number of steps. A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps.
大嘴牛个人的理解是这里的 lock-free 并不是说没有用于保护的锁的意思，而是指对于整个系统而言没有出现比如死锁的状况，而 wait-free 则表示根本不需要等待锁的时间。wait-free 比 lock-free 更加难实现，要求更加高，比如使用在嵌入式实时系统中等等。
[1]. http://www.rethinkdb.com/blog/2010/06/lock-free-vs-wait-free-concurrency/