lbq1221119

在研究handle table的時候順便研究的東西。Baidu了下，發現國內這方面的資料幾乎沒得，然后就準備瞎bb下，為下面的一篇介紹handle table的結構做準備。

關于lock-free data structure。以及解決這個問題中使用的CAS（compare and swap）操作。以及使用CAS操作的時候出現的A-B-A Problem。

對于lock-free data structure問題的解決，一般是使用流行的CAS操作。來防止需要讀寫的區域的數值和預期的數值不一樣的情況。

Shared,non-blocking的數據結構，和shared blocking的數據結構相比，采用了比較原始的同步方法。咱討論最多的一個同步方法，就是CAS（compare and swap）。

       關于CAS操作的偽代碼如下：

CAS(A,B,C)

BEGIN ATOMIC

if (A==C) {A=B; return TRUE; }

else { return FALSE; }

END ATOMIC

在使用CAS操作的時候，在計算之前，首先記錄下一個變量的值。經常是記錄一個shared data structure 實現的pointer。然后把這個變量的值存起來。這個時候，當得到了這個變量的新的值，需要update這個共享變量的數值的時候，就需要采用CAS操作來自動update這個共享變量的值。

CAS操作首先檢查shared var的值和已經保存起來的值是不是一樣的，如果是一樣的，就執行update操作。如果不是一樣的，就報錯。

如果操作失敗了的話，就使用這個shared var的新的值來重新做一次計算操作。這個原理，和數據庫管理系統里面的并發控制是非常類似的。然后，就把這個shared var所在的link list里面相關的節點，指向一個新的node。這個過程就叫做swap。

就如上面的偽代碼里面給出的實現，下面給一個代碼實現：

bool cas(volatile word* memory, word newValue, word expectedValue)

{

       atomically

       {

              if(*memory == expectedValue)

              {

                     *memory = newValue;

                     return true;

              }

              return false;

       }

}

這里介紹了對共享變量的最常用的CAS操作，那么使用這個操作的時候，會出現一個比較經典的問題，叫做A-B-A Problem。

ABA Problem就是譬如一個共享變量A，需要update到一個新的值C，而記錄這個變量的值是B，此時A=B；在記錄和update的這段時間中，這個共享變量被其余的job或者是thread操作修改了很多次，但是在update之前，還是回到了最開始的值。這就叫做ABA Problem。在構造一個特定的程序的時候，就會出現問題。

下面是在一個調用stack里面的ABA Problem：

其中，foo為一個操作head節點的作業，bar為一個中間操作shared var(head_)的作業。

對與CAS產生的這個ABA的問題，通常的解決方案是采用CAS的一個變種DCAS。

DCAS，是對于每一個shared var增加了一個引用的表示修改次數的標記符。對于每個shared var，如果引用修改了一次，這個計數器就增加一個。然后在這個變量需要update的時候，就同時檢查變量的值和計數器的值。

DCAS的偽代碼如下：

DCAS(A1,A2,B1,B2,C1,C2)

BEGIN ATOMIC

if ((A1==B1) && (A2==B2)) { A1=C1; A2=C2; return TRUE; }

else { return FALSE; }

END ATOMIC

另外，還有NON-BLOCKING LINK LIST及其改進算法，不扯遠了。如果想繼續研究，請找University of Manitoba, Canada的一篇叫做“MANAGING LONG LINKED LISTS USING LOCK FREE TECHNIQUES”的論文。

在handle table中，就定義了一個link list：

EX_PUSH_LOCK HandleTableLock[HANDLE_TABLE_LOCKS]

來防止在handle allocation的時候出現的ABA Problem。再看看這個結構體的定義，里面用了一個ActiveCount來標識引用了多少次：

+1c struct   _ERESOURCE HandleTableLock

+1c    struct   _LIST_ENTRY SystemResourcesList

+1c       struct   _LIST_ENTRY *Flink

+20       struct   _LIST_ENTRY *Blink

+24    struct   _OWNER_ENTRY *OwnerTable

+28    int16    ActiveCount

+2a    uint16   Flag

+2c    struct   _KSEMAPHORE *SharedWaiters

+30    struct   _KEVENT *ExclusiveWaiters

+34    struct   _OWNER_ENTRY OwnerThreads[2]

          uint32   OwnerThread

          int32    OwnerCount

          uint32   TableSize

8/18/2008 2:33:01 PM  lbq1221119@cnblogs  首發sscli.cnblogs.com