Posted on 2014-09-12 13:05
鑫龍 閱讀(422)
評論(0) 編輯 收藏 引用 所屬分類:
linux編程
轉自：http://www.cnblogs.com/jiayy/p/3246167.html
在看多核編程相關論文時，往往一個并發算法會說自己是wait-free的或者lock-free的，或者是 non-blocking 的，這些專有詞匯其實表示的是并發的程度，或者說并發的級別。并發級別的理解是閱讀各種并發算法設計論文以及并發數據結構實現的必備基礎。
1.1 Wait-freedom 無等待并發
Wait-freedom 指的是每一個線程都一直運行下去而無須等待外部條件，整個流程中任何操作都能在一個有限的步驟內完成，這是最高的并發級別，沒有任何阻塞。
結合之前原子操作部分的知識，可以簡單認為能夠直接調用一個原子操作實現的算法或程序就屬于Wait-free，比如下面的 increment_reference_counter 函數就是wait-free的，它封裝了atomic_increment這個原子自增原語，多個線程可以同時調用這個函數對同一個內存變量進行自增，而無須任何阻塞（其實也是有阻塞的，是總線鎖級別）
與此做對比，CAS類的調用就不是wait-free的，注意wait-free的原語都不能包含內部循環，CAS原語使用時通常包含在“循環直到成功”的循環內部。
void increment_reference_counter(rc_base* obj)
{
atomic_increment(obj->rc);
}
1.2 Lock-freedom 無鎖并發
Lock-freedom 指的是整個系統作為一個整體一直運行下去，系統內部單個線程某段時間內可能會饑餓，這是比wait-freedom弱的并發級別，但系統整體上看依然是沒有阻塞的。所有wait-free的算法顯然都滿足lock-free的要求。
Lock-free算法通常可以通過同步原語 CAS實現。
void stack_push(stack* s, node* n)
{
node* head;
do
{
head = s->head;
n->next = head;
}
while ( ! atomic_compare_exchange(s->head, head, n));
}
多個線程同時調用上述函數，理論上某個線程可以一直困在循環內部，但一旦有一個線程原子操作失敗而返回循環，意味著有其他線程成功執行了原子操作而退出循環，從而保證系統整體是沒有阻塞的。
其實前面的原子自增函數也可以用下面的原語實現，在這種實現里，不再是所有線程都無阻塞了，某些線程可能會因為CAS失敗而回繞若干次循環。
void increment_reference_counter(rc_base* obj)
{
Int rc;
Do {
rc = obj->rc;
} while(!atomic_compare_exchange(obj->rc,rc,rc+1));
}
1.3 Obstruction-freedom 無阻塞并發
Obstruction-free 是指在任何時間點，一個孤立運行線程的每一個操作可以在有限步之內結束。只要沒有競爭，線程就可以持續運行，一旦共享數據被修改，Obstruction-free 要求中止已經完成的部分操作，并進行回滾，obstruction-free 是并發級別更低的非阻塞并發，該算法在不出現沖突性操作的情況下提供單線程式的執行進度保證，所有 Lock-Free 的算法都是 Obstruction-free 的。
1.4 Blocking algoithms 阻塞并發
阻塞類的算法是并發級別最低的同步算法，它一般需要產生阻塞。可以簡單認為基于鎖的實現是blocking的算法。詳細參考第五章
上述幾種并發級別可以使用下圖描述：
藍色是阻塞的算法，綠色是非阻塞算法，金字塔越上方，并發級別越高，性能越好，右邊的金字塔是實現工具（原子操作、鎖、互斥體等）