轉(zhuǎn)載時請注明出處和作者聯(lián)系方式
文章出處：http://www.limodev.cn/blog
作者聯(lián)系方式：李先靜 <xianjimli@gmail.com>

無鎖(lock-free)數(shù)據(jù)結(jié)構(gòu)

      提到并行計算通常都會想到加鎖，事實(shí)卻并非如此，大多數(shù)并發(fā)是不需要加鎖的。比如在不同電腦上運(yùn)行的代碼編輯器，兩者并發(fā)運(yùn)行不需要加鎖。在一臺電腦上同時運(yùn)行的媒體播放放器和代碼編輯器，兩者并發(fā)運(yùn)行不需要加鎖(當(dāng)然系統(tǒng)調(diào)用和進(jìn)程調(diào)度是要加鎖的)。在同一個進(jìn)程中運(yùn)行多個線程，如果各自處理獨(dú)立的事情也不需要加鎖(當(dāng)然系統(tǒng)調(diào)用、進(jìn)程調(diào)度和內(nèi)存分配是要加鎖的)。在以上這些情況里，各個并發(fā)實(shí)體之間沒有共享數(shù)據(jù)，所以雖然并發(fā)運(yùn)行但不需要加鎖。

多線程并發(fā)運(yùn)行時，雖然有共享數(shù)據(jù)，如果所有線程只是讀取共享數(shù)據(jù)而不修改它，也是不用加鎖的，比如代碼段就是共享的“數(shù)據(jù)”，每個線程都會讀取，但是不用加鎖。排除所有這些情況，多線程之間有共享數(shù)據(jù)，有的線程要修改這些共享數(shù)據(jù)，有的線程要讀取這些共享數(shù)據(jù)，這才是程序員需要關(guān)注的情況，也是本節(jié)我們討論的范圍。

在并發(fā)的環(huán)境里，加鎖可以保護(hù)共享的數(shù)據(jù)，但是加鎖也會存在一些問題：

• 由于臨界區(qū)無法并發(fā)運(yùn)行，進(jìn)入臨界區(qū)就需要等待，加鎖帶來效率的降低。
• 在復(fù)雜的情況下，很容易造成死鎖，并發(fā)實(shí)體之間無止境的互相等待。
• 在中斷/信號處理函數(shù)中不能加鎖，給并發(fā)處理帶來困難。
• 優(yōu)先級倒置造成實(shí)時系統(tǒng)不能正常工作。低級優(yōu)先進(jìn)程拿到高優(yōu)先級進(jìn)程需要的鎖，結(jié)果是高/低優(yōu)先級的進(jìn)程都無法運(yùn)行，中等優(yōu)先級的進(jìn)程可能在狂跑。

由于并發(fā)與加鎖(互斥)的矛盾關(guān)系，無鎖數(shù)據(jù)結(jié)構(gòu)自然成為程序員關(guān)注的焦點(diǎn)，這也是本節(jié)要介紹的：

      CPU提供的原子操作

大約在七八年前，我們用apache的xerces來解析XML文件，奇怪的是多線程反而比單線程慢。他們找了很久也沒有找出原因，只是證實(shí)使用多進(jìn)程代替多線程會快一個數(shù)量級，在Windows上他們就使用了多進(jìn)程的方式。后來移植到linux時候，我發(fā)現(xiàn)xerces每創(chuàng)建一個結(jié)點(diǎn)都會去更新一些全局的統(tǒng)計信息，比如把結(jié)點(diǎn)的總數(shù)加一，它使用的pthread_mutex實(shí)現(xiàn)互斥。這就是問題所在：一個XML文檔有數(shù)以萬計的結(jié)點(diǎn)，以50個線程并發(fā)為例，每個線程解析一個XML文檔，總共要進(jìn)行上百萬次的加鎖/解鎖，幾乎所有線程都在等待，你說能快得了嗎？

當(dāng)時我知道Windows下有InterlockedIncrement之類的函數(shù)，它們利用CPU一些特殊指令，保證對整數(shù)的基本操作是原子的。查找了一些資源發(fā)現(xiàn)Linux下也有類似的函數(shù)，后來我把所有加鎖去掉，換成這些原子操作，速度比多進(jìn)程運(yùn)行還快了幾倍。下面我們看++和—的原子操作在IA架構(gòu)上的實(shí)現(xiàn)：

#define ATOMIC_SMP_LOCK "lock ; "
typedef struct { volatile int counter; } atomic_t;

static __inline__ void atomic_inc(atomic_t *v)
{
    __asm__ __volatile__(
        ATOMIC_SMP_LOCK "incl %0"
        :"=m" (v->counter)
        :"m" (v->counter));
}

static __inline__ void atomic_dec(atomic_t *v)
{
    __asm__ __volatile__(
        ATOMIC_SMP_LOCK "decl %0"
        :"=m" (v->counter)
        :"m" (v->counter));
}

單入單出的循環(huán)隊列。單入單出的循環(huán)隊列是一種特殊情況，雖然特殊但是很實(shí)用，重要的是它不需要加鎖。這里的單入是指只有一個線程向隊列里追加數(shù)據(jù)(push)，單出只是指只有一個線程從隊列里取數(shù)據(jù)(pop)，循環(huán)隊列與普通隊列相比，不同之處在于它的最大數(shù)據(jù)儲存量是事先固定好的，不能動態(tài)增長。盡管有這些限制它的應(yīng)用還是相當(dāng)廣泛的。這我們介紹一下它的實(shí)現(xiàn)：

數(shù)據(jù)下定義如下：

typedef struct _FifoRing
{
    int r_cursor;
    int w_cursor;
    size_t length;
    void* data[0];

}FifoRing;

創(chuàng)建函數(shù)

FifoRing* fifo_ring_create(size_t length)
{
    FifoRing* thiz = NULL;

    return_val_if_fail(length > 1, NULL);

    thiz = (FifoRing*)malloc(sizeof(FifoRing) + length * sizeof(void*));

    if(thiz != NULL)
    {
        thiz->r_cursor = 0;
        thiz->w_cursor = 0;
        thiz->length   = length;
    }

    return thiz;
}

這里我們要求隊列的長度大于1而不是大于0，為什么呢？排除長度為1的隊列沒有什么意義的原因外，更重要的原因是隊列頭與隊列尾重疊 (r_cursor= =w_cursor) 時，到底表示是滿隊列還是空隊列？這個要搞清楚才行，上次一個同事犯了這個錯誤，讓我們查了很久。這里我們認(rèn)為隊列頭與隊列尾重疊時表示隊列為空，這與隊列初始狀態(tài)一致，后面在寫的時候始終保留一個空位，避免隊列頭與隊列尾重疊，這樣可以消除歧義了。

追加數(shù)據(jù)(push)

隊列頭和隊列尾之間還有一個以上的空位時就追加數(shù)據(jù)，否則返回失敗。

取數(shù)據(jù)(pop)

隊列頭和隊列尾不重疊表示隊列不為空，取數(shù)據(jù)并移動隊列頭。

      單寫多讀的無鎖數(shù)據(jù)結(jié)構(gòu)
      單寫表示只有一個線程去修改共享數(shù)據(jù)結(jié)構(gòu)，多讀表示有多個線程去讀取共享數(shù)據(jù)結(jié)構(gòu)。前面介紹的讀寫鎖可以有效的解決這個問題，但更高效的辦法是使用無鎖數(shù)據(jù)結(jié)構(gòu)。思路如下：

就像為了避免顯示閃爍而使用的雙緩沖一樣，我們使用兩份數(shù)據(jù)結(jié)構(gòu)，一份數(shù)據(jù)結(jié)構(gòu)用于讀取，所有線程都可以在不加鎖的情況下讀取這個數(shù)據(jù)結(jié)構(gòu)。另外一份數(shù)據(jù)結(jié)構(gòu)用于修改，由于只有一個線程會修改它，所以也不用加鎖。

在修改之后，我們再交換讀/寫的兩個函數(shù)結(jié)構(gòu)，把另外一份也修改過來，這樣兩個數(shù)據(jù)結(jié)構(gòu)就一致了。在交換時要保證沒有線程在讀取，所以我們還需要一個讀線程的引用計數(shù)。現(xiàn)在我們看看怎么把前面寫的雙向鏈表改為單寫多讀的無鎖數(shù)據(jù)結(jié)構(gòu)。

為了保證交換是原子的，我們需要一個新的原子操作CAS(compare and swap)。

數(shù)據(jù)結(jié)構(gòu)

兩個鏈表，一個用于讀一個用于寫。rd_index_and_ref的最高字節(jié)記錄用于讀取的雙向鏈表的索引，低24位用于記錄讀取線程的引用記數(shù)，最大支持16777216個線程同時讀取，應(yīng)該是足夠了，所以后面不考慮它的溢出。

讀取操作

修改操作

先修改用于修改的雙向鏈表，修改完成之后等到?jīng)]有線程讀取時，交換讀/寫兩個鏈表，再修改另一個鏈表，此時兩個鏈表狀態(tài)保持一致。

稍做改進(jìn)，對修改的操作進(jìn)行加鎖，就可以支持多讀多寫的數(shù)據(jù)結(jié)構(gòu)，讀是無鎖的，寫是加鎖的。


      真正的無鎖數(shù)據(jù)結(jié)構(gòu)
      Andrei Alexandrescu的《Lock-FreeDataStructures》估計是這方面最經(jīng)典的論文了，對他的方法我開始感到驚奇后來感到失望，驚奇的是算法的巧妙，失望的是無鎖的限制和代價。作者最后說這種數(shù)據(jù)結(jié)構(gòu)只適用于WRRMBNTM(Write-Rarely-Read-Many -But-Not-Too-Many)的情況。而且每次修改都要拷貝整個數(shù)據(jù)結(jié)構(gòu)（甚至多次），所以不要指望這種方法能帶來多少性能上的提高，唯一的好處是能避免加鎖帶來的部分副作用。有興趣的朋友可以看下這篇論文，這里我就不重復(fù)了。

本節(jié)示例請到這里下載。