簡言

1.無鎖能夠實現的核心原理即CAS

2. c++語言中CAS一般有三種操作，即gcc的CAS實現，windows的CAS實現，c++11的CAS實現

3. 這篇博客主要講c++11的CAS實現，原理

4. 完整代碼下載請移步?https://blog.csdn.net/yzf279533105/article/details/119802375

概要

1. gcc的CAS實現函數如下

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

2.windows的CAS實現函數如下

InterlockedCompareExchange ( __inout LONG volatile *Target,__in LONG Exchange,__in LONG Comperand);

3. c++11的CAS實現函數如下

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

多線程新建節點的核心原理（三步缺一不可）

1. 確定當tail->next為NULL時，就把tail->next指向新節點即可，CAS操作

2. 再把tail更新指向為新節點，CAS操作

3. 若第二步失敗或落后時，其他線程可以修正即把tail更新為最新，CAS操作

代碼如下

// 壓入隊列一個節點 void NoLockList::enqueueOne(int n) {// 新建節點Node* pnew = new Node();pnew->value = n;pnew->next = NULL;Node* ptail = NULL;Node* ptailnext = NULL;Node* pNULL = NULL;while (true){ptail = pTail; // 每次拿隊列最新的Tailptailnext = pTail.load()->next;// 若pTail不是真正鏈表末尾，則后移pTail// 注意此步不可簡單地continue，因為其他線程可能因為某種原因導致只加入了新節點，未能更新Tail指針，這里可以修正if (ptailnext != NULL){pTail.compare_exchange_weak(ptail, ptailnext);continue;}// 核心：若pTail->next為空，則確定pTail是鏈表尾節點，則pTail->next改為指向新節點，修改失敗則重試if (pTail.load()->next.compare_exchange_weak(pNULL, pnew)){// 更新尾指針pTail，即使更新失敗也沒關系，說明其他線程已經更新了pTailpTail.compare_exchange_weak(ptail, pnew);return;}} }

多線程刪除節點的核心原理（二者缺一不可）

1. 若head->next不為空，就把head指針后移，并free舊的head指針，CAS操作

2. 若head和tail指針相等，說明tail指針落后了（tail未能及時后移），就把tail指針后移，CAS操作

代碼如下

// 出隊列 int NoLockList::dequeueOne(int thread, bool stop) {Node* phead = NULL;Node* ptail = NULL;Node* pheadNext = NULL;while (true){phead = pHead;ptail = pTail;pheadNext = phead->next;// 鏈表為空(只有一個初始節點)if (pheadNext==NULL){cout<<"dequeueOne::pheadNext==NULL"<<endl;return -1;}// 鏈表不為空，但pHead指針和pTail相等，說明pTail未能及時更新,則后移pTailif (phead == ptail){cout<<"dequeueOne::phead == ptail, thread="<<thread<<endl;pTail.compare_exchange_weak(ptail,pheadNext);continue;}// 隨機暫停一段時間if (stop){usleep(500+rand()%500);}// 核心：若pList->pHead確定是鏈表頭部節點，則后移Head；失敗則重試if ( pHead.compare_exchange_weak(phead, pheadNext)){int val = phead->value;free(phead);cout<<"dequeueOne,suc, thread="<<thread<<endl;return val;}cout<<"dequeueOne::retry, thread="<<thread<<endl;} }

總結

以上是生活随笔為你收集整理的无锁链表的c++实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。