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