簡言

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

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

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

4. 具體原理分析可參考：https://blog.csdn.net/yzf279533105/article/details/119798571

實驗過程

1. 預先加入10000個節點，加上一個空節點，一共10001個節點

2. 開500個線程增加10萬節點，同時開500個線程刪除10萬節點

3. 打印鏈表長度，發現仍然是10001

實驗如下圖

完整代碼

#include <iostream> #include <atomic> #include <thread> #include <unistd.h> #include <stdlib.h>using namespace std;// 節點 struct Node {int value;atomic<Node*> next; };// 無鎖鏈表 struct NoLockList {atomic<Node*> pHead;atomic<Node*> pTail;void enqueueOne(int thread, int n, bool stop); // 入隊int dequeueOne(int thread, bool stop); // 出隊void enqueueMany(int thread, int m, bool stop); // 入隊多個節點void dequeueMany(int thread, int m, bool stop); // 出隊多個節點int len(); // 長度 };// 壓入隊列一個節點 void NoLockList::enqueueOne(int thread, int n, bool stop) {// 新建節點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);cout<<"enqueueOne::ptailnext != NULL, thread="<<thread<<endl;continue;}if (stop){usleep(500+rand()%500);}// 核心：若pTail->next為空，則確定pTail是鏈表尾節點，則pTail->next改為指向新節點，修改失敗則重試if (pTail.load()->next.compare_exchange_weak(pNULL, pnew)){// 更新尾指針pTail，即使更新失敗也沒關系，說明其他線程已經更新了pTailpTail.compare_exchange_weak(ptail, pnew);cout<<"enqueueOne,suc, thread="<<thread<<endl;return;}cout<<"enqueueOne::retry"<<endl;} }// 出隊列 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;} }// 入隊多個節點 void NoLockList::enqueueMany(int thread, int m, bool stop) {for (int i=0;i<m;i++){enqueueOne(thread, i,stop);} }// 出隊多個節點 void NoLockList::dequeueMany(int thread, int m, bool stop ) {for (int i=0;i<m;i++){dequeueOne(thread, stop);} }// 隊列長度 int NoLockList::len() {if (pHead.load() == pTail.load()){return 1;}int le = 1;Node* p = pHead;while (p->next.load()){p = p->next.load();le++;}return le; }int main() {NoLockList list;// 初始化第一個空節點Node* pNew = new Node();pNew->value = 0;pNew->next = NULL;list.pHead = pNew;list.pTail = pNew;// 10萬個節點const int nodeNum = 100000;// 1000個線程const int threadNum = 1000;// 初始10000節點for (int i=0;i<10000;i++){list.enqueueOne(0, i,false);}cout<<"start, list elements is : "<<list.len()<<endl;// 多個線程進行入隊，出隊操作thread en[threadNum];thread de[threadNum];for (int i=0;i<threadNum;i++){en[i] = thread(&NoLockList::enqueueMany, &list, i, nodeNum/threadNum,true);de[i] = thread(&NoLockList::dequeueMany, &list, i, nodeNum/threadNum,true);}for (int i=0;i<threadNum;i++){de[i].join();en[i].join();}cout<<"end, list elements is : "<<list.len()<<endl;return 0; }

總結

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

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