无等待是不够的

以目前针对演进条件(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), …

在我们自己的数据结构中，我们正试图遵循这一惯例，并指出每个函数的演进条件的顺序是什么。

<a href="http://sourceforge.net/projects/ccfreaks/files/">http://sourceforge.net/projects/ccfreaks/files/</a>