无等待是不够的
以目前针对演进条件(progress condition，注：参考[1])的算法和数据结构的分类来看，是不足以区分不同演进条件的能力和每一个演进条件的性能/延迟。
我们提出了一种新的“大O”记号来表示无等待的算法和数据结构。下面是它的工作原理：
一个算法或功能被称为“Wait-Free O(x)“，表示需要最多O(x)操作完成。
一些示例：
- a)”Wait-Free O(NThreads)“表示：一个算法，扫描每个活动线程的状态
- b)”Wait-Free O(ln NThreads)“表示：一个算法，需要自身插入到活动的线程（使用二分法）的排序列表
- c)”Wait-Free O(NThreads^2)“表示：一个算法，扫描活动线程的每个状态平方次数
- d)”Wait-Free O(1)“表示：一个算法，做3次操作，不论活动线程和其他变量数目
- e)”Wait-Free O(N)“表示：一个算法，获取确定数值N，比如一个数列当前元素的数量N，并且做了O(N)操作
- f)”Wait-Free O(N^2)“表示：一个算法，获取确定数值N，并且做了O(N^2)操作
根据当前表示法，示例a)、b)和c)都是”Wait-Free Bounded”，但示例b)显然比c)或a)更好。
根据当前表示法，示例d)、e)和f)都是”Wait-Free Population Oblivious”，崦示例d)显然比e)或f)更好
也许更有意思的是，示例b)可能比示例f)更好。特别地，如果N > NThreads，即使b)是”Bounded”而f)是”Population Oblivious”，它只是用来显示”Wait-Free Population Oblivious”未必比”Wait-Free Bounded”更好。
无锁如何？
那么，在这个新的表示法中，无锁也可以写成”Wait-Free O(infinity)”形式，但要注意的是，尽管所有的无锁算法都有一个最坏情况O(infinity)，它们大多数都有一个预计的操作数O(1)或O(N)，并且不依赖于线程的数量。
再比方说：
一个链表，对于contains()方法是无等待（Wait-Free）的，但这永远不会比”Wait-Free O(N_elements)”更好（N_elements是在某个时刻contains()操作时，链表中元素的数量）
匹配新旧之间的分类：
- Wait-Free Bounded：O(ln NThreads), O(NThreads), O(NThreads^2), …
- Wait-Free Population Oblivious：O(1), O(ln N), O(N), O(N^2), …
http://sourceforge.net/projects/ccfreaks/files/
参考：
[1] 多处理器编程的艺术
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/140754.html