关于传说中的无锁环形缓冲区的疑问

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. };

复制代码

这段时前一阵看到一位仁兄贴的 无锁的ring buffer，我有个小疑问
1. 当thread 1 在 tag 1 处 读取 Pop_Count变量时，thread 2 恰好在tag 2 处在重置Pop_Count ，
   这时候 Pop_Count 不需要互斥吗？ i++操作肯定不是原子的

zylthinking

这次读旧值，下次可以读新的嘛，有啥关系

鸡丝拌面

只有一个写者来push。

happy_fish100

我项目中用到了类似实现，一个线程写，一个线程读，经过压测，没有发现异常。
今天和同事交流，他们提到了内存屏障和乱序执行的问题，我就有些纠结了。
我觉得采用这种无锁实现，原理上不存在数据错乱的现象/问题。
请懂行的大拿点评！谢谢！

nspnspnspnsp

感觉没问题，虽然都不是原子的，你仔细想想在边界值的时候，都是先赋值再递增， List[Push_Index] = AData;          Push_Count++;     pop也是这样，其余push操作都是没有用到Pop_Count，（反之pop也是这样）。即便楼主说的情况发生也没有问题。

koolcoy

无锁环形缓冲有个重要的要求：对变量Push_Count和Pop_Count的读/写必须是原子的，否则会出错。 例如，你不能在x86架构下使用64位的Push_Count和Pop_Count.

我个人倾向于去掉Push_Index和Pop_Index，然后将数组List的大小做成一个模板参数，每次用的时候Push_Index用 (Push_Count % 数组大小)  来代替

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. };
    

复制代码

linux_c_py_php

没了解过, 有什么介绍这个的吗.

井蛙夏虫

这个是回复7楼的。

你的实现有问题，考虑这种情况:
当push了tsize次，此时Puch_Count为tsize;没有pop，此时Pop_Count为0;
现在运行到pop最后一句，假设编译的代码产生临时变量temp存储Pop_Count++取出的Pop_Count值，然后将Pop_count加1, 此时Pop_Count为1，temp为0;
然后另一线程运行push,检查(Push_Count - Pop_count)为tsize-1,运行"List[Push_count++%tSize]=a;"，将新值写入List[0];
然后pop线程读取List[temp]也就是List[0],此时将为新值，而原先的旧值就丢失了。