無等待是不夠的

以目前針對演進條件(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>