首次接觸無鎖數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，請(qǐng)各位大佬多多指教~~~

CAS(Compare && Swap)原子操作

CAS是無鎖(lock free)的數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。用偽代碼描述：

input: reg, old_val, new_val
/*是old_val， reg替換為new_val，返回為true；否則返回為false*/
if (* reg == old_val) {
     * reg == new_val;
      return true;
} else {
       return false;
}

CAS相似的原子操作：
fetch and add，一般用來對(duì)變量做+1的原子操作
test and set， 寫值到內(nèi)存位置并傳回其舊值
test test and set : 和雙檢查鎖一樣為了減少對(duì)鎖的多次競(jìng)爭(zhēng)，對(duì)鎖的競(jìng)爭(zhēng)代價(jià)比普通判斷鎖的狀態(tài)要大，這里需要著重強(qiáng)調(diào)，在high level programming的背景下，盡量少用雙重檢測(cè)鎖的形式，因?yàn)榈诙螜z查和設(shè)置并不一定是原子操作。test test and set偽代碼（Wikipedia test test and set）如下:

boolean locked := false // shared lock variable
procedure EnterCritical() {
  do {
    while (locked == true) skip // spin until lock seems free
  } while TestAndSet(locked) // actual atomic locking, this cost of step >> the cost above !!!;
}

在此稍微記錄一下，

• GCC的原子CAS的API

bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)

• C++11的CAS
  C++11的STL中的atomic類的函數(shù)可以跨平臺(tái)。

template< class T >
bool atomic_compare_exchange_weak( std::atomic* obj,
                                   T* expected, T desired );
template< class T >
bool atomic_compare_exchange_weak( volatile std::atomic* obj,
                                   T* expected, T desired );

無鎖隊(duì)列的鏈表實(shí)現(xiàn)

EnQueue(x) {
  // 準(zhǔn)備新加入的結(jié)點(diǎn)數(shù)據(jù)
  q = new record();
  q->value = x; 
  q->next = NULL;
  do {
    p = tail; // 鏈表尾指針的快照
  } while( CAS(p->next, NULL, q)!= true)
  CAS(tail, p, q);
}

do while的Re-Try-Loop，如果別的進(jìn)程已經(jīng)加成功了，tail就變了，p!=tail, p->next!= NULL，那么就重試。
這里存在一個(gè)問題，如果在CAS(tail, p, q)之前線程掛掉了或者停掉了，其它線程更新了p->next，卻沒有更新tail，然后就一直進(jìn)入死循環(huán)。為了解決這個(gè)問題，下面推出了改良版的EnQueue()

EnQueue(x)
{
  q = new record();
  q->value = x;
  q->next = NULL;

  p = tail;
  oldp = p;
  do {
    while (p->next!= NULL) {
      p = p->next;
    } while (CAS(p->next, NULL, q)!= TRUE); // 如果沒有把結(jié)點(diǎn)鏈在尾上，再試
    CAS (tail , oldp, q); // 置尾結(jié)點(diǎn)
  }
}

fetch會(huì)很影響性能， 所以可以結(jié)合以上兩個(gè)版本，如果retry的次數(shù)超過一個(gè)閾值，那么自己就fetch指針。
但是這里存在一個(gè)問題，就oldq能不能及時(shí)更新，若不能及時(shí)更新，其余線程在插入時(shí)會(huì)插到未定義的位置。個(gè)人覺得還是選擇未改良版比較好。

DeQueue // 出隊(duì)列

DeQueue() {
  do {
    p = head;
    if (p -> next == NULL) {
      return ERR_EMPTY_QUEUE;
    }
  } while ( CAS(head, p, p->next)!= TRUE);
  return p->next->value;
}

CAS的ABA問題：

1. 進(jìn)程p1在共享變量中讀到值為A
2. p1被搶占了，進(jìn)程p2執(zhí)行
3. p2把共享變量里的值從A改成B，再改回到A，此時(shí)被p1搶占。
4. p1回來看到共享變量里的值沒有被改變，于是繼續(xù)執(zhí)行。

看來好像沒有問題，但是上式的CAS其實(shí)判斷的是指針地址，然而指針內(nèi)容改變了，不就炸了？這就是內(nèi)存管理中的重用內(nèi)存問題。

解決ABA的問題

例如在32位系統(tǒng)上檢查64位的內(nèi)容：

1. 一次用CAS檢查雙倍長(zhǎng)度的值，前半部分是指針，后半部分是一個(gè)計(jì)數(shù)器
2. 只有這兩個(gè)都一樣，才算通過，要用該指針符新的值，計(jì)數(shù)器加1。
   這種方法線程次數(shù)上應(yīng)該也沒問題，但是一旦多了，可能會(huì)溢出循環(huán)計(jì)數(shù)。

所以有論文提出了使用結(jié)點(diǎn)內(nèi)存的引用計(jì)數(shù)，這和智能指針沒啥區(qū)別嘛，但是需要保證加引用計(jì)數(shù)和減引用計(jì)數(shù)為原子操作。

用數(shù)組實(shí)現(xiàn)無鎖隊(duì)列

無鎖隊(duì)列可以用ring buffer實(shí)現(xiàn)，定位head和tail可以聲明兩個(gè)計(jì)數(shù)器，一個(gè)用來計(jì)數(shù)EnQueue的次數(shù)，一個(gè)用來計(jì)數(shù)DeQueue的次數(shù)，當(dāng)隊(duì)列滿或空，可以拋出異常，沒有內(nèi)存泄露的問題。

reference

[1]. 無鎖隊(duì)列的實(shí)現(xiàn)
[2]. 無鎖隊(duì)列的環(huán)形數(shù)組實(shí)現(xiàn)