關(guān)于傳說中的無鎖環(huán)形緩沖區(qū)的疑問

cookis

1. template<class T>
   
2. class RingQueue {
   
3. public:
   
4. 
   
5.     RingQueue() {
   
6.         cout << "RingQueue::ctor" << endl;
   
7.     };
   
8. 
   
9.     virtual ~RingQueue() {
   
10.         cout << "RingQueue::destory" << endl;
    
11.     };
    
12. 
    
13.     void InitQueue() {
    
14.         Push_Count = 0;
    
15.         Push_Index = 0;
    
16.         Pop_Count = 0;
    
17.         Pop_Index = 0;
    
18.         memset(List, 0, sizeof (List));
    
19.     }
    
20. 
    
21.     bool Push(const T& AData) {
    
22.         if (Push_Count - Pop_Count < Max_Count) {               // tag 1:  讀取 Pop_Count
    
23.             List[Push_Index] = AData;
    
24.             Push_Count++;                                                      
    
25.             if (Push_Index == High_Index)
    
26.                 Push_Index = 0;
    
27.             else
    
28.                 Push_Index++;
    
29.             return true;
    
30.         } else
    
31.             return false;
    
32.     }
    
33.     T Pop() {
    
34.         T result = NULL;
    
35.         if (Push_Count != Pop_Count) {
    
36.             result = List[Pop_Index];
    
37.             Pop_Count++;                                                     // tag 2 : 重置
    
38.             if (Pop_Index == High_Index)
    
39.                 Pop_Index = 0;
    
40.             else
    
41.                 Pop_Index++;
    
42.         }
    
43.         return result;
    
44.     }
    
45. 
    
46.     long size() {
    
47.         return this->Push_Count - this->Pop_Count;
    
48.     }
    
49. 
    
50. private:
    
51.     RingQueue(const RingQueue& orig);
    
52.     T List[524288 * 2]; //2^19  4M�ռ�
    
53.     const static unsigned long Max_Count = 524288 * 2;
    
54.     const static unsigned long High_Index = 524288 * 2 - 1;
    
55.     unsigned long Push_Count;
    
56.     unsigned long Push_Index;
    
57.     unsigned long Pop_Count;
    
58.     unsigned long Pop_Index;
    
59. 
    
60. };

復(fù)制代碼

這段時(shí)前一陣看到一位仁兄貼的 無鎖的ring buffer，我有個(gè)小疑問
1. 當(dāng)thread 1 在 tag 1 處 讀取 Pop_Count變量時(shí)，thread 2 恰好在tag 2 處在重置Pop_Count ，
   這時(shí)候 Pop_Count 不需要互斥嗎？ i++操作肯定不是原子的

zylthinking

這次讀舊值，下次可以讀新的嘛，有啥關(guān)系

雞絲拌面

只有一個(gè)寫者來push。

happy_fish100

我項(xiàng)目中用到了類似實(shí)現(xiàn)，一個(gè)線程寫，一個(gè)線程讀，經(jīng)過壓測，沒有發(fā)現(xiàn)異常。
今天和同事交流，他們提到了內(nèi)存屏障和亂序執(zhí)行的問題，我就有些糾結(jié)了。
我覺得采用這種無鎖實(shí)現(xiàn)，原理上不存在數(shù)據(jù)錯(cuò)亂的現(xiàn)象/問題。
請懂行的大拿點(diǎn)評！謝謝！

nspnspnspnsp

感覺沒問題，雖然都不是原子的，你仔細(xì)想想在邊界值的時(shí)候，都是先賦值再遞增， List[Push_Index] = AData;          Push_Count++;     pop也是這樣，其余push操作都是沒有用到Pop_Count，（反之pop也是這樣）。即便樓主說的情況發(fā)生也沒有問題。

koolcoy

無鎖環(huán)形緩沖有個(gè)重要的要求：對變量Push_Count和Pop_Count的讀/寫必須是原子的，否則會出錯(cuò)。 例如，你不能在x86架構(gòu)下使用64位的Push_Count和Pop_Count.

我個(gè)人傾向于去掉Push_Index和Pop_Index，然后將數(shù)組List的大小做成一個(gè)模板參數(shù)，每次用的時(shí)候Push_Index用 (Push_Count % 數(shù)組大小)  來代替

koolcoy

隨便寫的，沒測試

1. 
   
2. template<typename T, int tSize>
   
3. class RingQueue {
   
4. public:
   
5.         RingQueue() : Push_Count(0), Pop_Count(0) {}
   
6. 
   
7.         bool empty() {
   
8.                 return Push_Count == Pop_Count;
   
9.         }
   
10. 
    
11.         bool push(const T& a) {
    
12.                 if (Push_Count - Pop_Count >= tSize) {
    
13.                         return false;
    
14.                 }
    
15.                 List[Push_Count++ % tSize] = a;
    
16.                 return true;
    
17.         }
    
18. 
    
19.         T pop() {
    
20.                 if (empty()) {
    
21.                         throw;
    
22.                 }
    
23.                 return List[Pop_Count++ % tSize];
    
24.         }
    
25. 
    
26. private:
    
27.         T List[tSize];
    
28.         int Push_Count;
    
29.         int Pop_Count;
    
30. };
    

復(fù)制代碼

linux_c_py_php

沒了解過, 有什么介紹這個(gè)的嗎.

井蛙夏蟲

這個(gè)是回復(fù)7樓的。

你的實(shí)現(xiàn)有問題，考慮這種情況:
當(dāng)push了tsize次，此時(shí)Puch_Count為tsize;沒有pop，此時(shí)Pop_Count為0;
現(xiàn)在運(yùn)行到pop最后一句，假設(shè)編譯的代碼產(chǎn)生臨時(shí)變量temp存儲Pop_Count++取出的Pop_Count值，然后將Pop_count加1, 此時(shí)Pop_Count為1，temp為0;
然后另一線程運(yùn)行push,檢查(Push_Count - Pop_count)為tsize-1,運(yùn)行"List[Push_count++%tSize]=a;"，將新值寫入List[0];
然后pop線程讀取List[temp]也就是List[0],此時(shí)將為新值，而原先的舊值就丟失了。