Chinaunix

标题: 关于传说中的无锁环形缓冲区的疑问 [打印本页]
作者: cookis    时间: 2012-01-14 02:04
标题: 关于传说中的无锁环形缓冲区的疑问
本帖最后由 cookis 于 2012-01-14 02:06 编辑
  1. template<class T>
  2. class RingQueue {
  3. public:

  5.     RingQueue() {
  6.         cout << "RingQueue::ctor" << endl;
  7.     };

  9.     virtual ~RingQueue() {
  10.         cout << "RingQueue::destory" << endl;
  11.     };

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

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

  46.     long size() {
  47.         return this->Push_Count - this->Pop_Count;
  48.     }

  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;

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


作者: zylthinking    时间: 2012-01-14 08:03
这次读旧值，下次可以读新的嘛，有啥关系
作者: 鸡丝拌面    时间: 2012-01-14 17:06
只有一个写者来push。
作者: happy_fish100    时间: 2013-04-28 16:36
我项目中用到了类似实现，一个线程写，一个线程读，经过压测，没有发现异常。
今天和同事交流，他们提到了内存屏障和乱序执行的问题，我就有些纠结了。
我觉得采用这种无锁实现，原理上不存在数据错乱的现象/问题。
请懂行的大拿点评！谢谢！
作者: nspnspnspnsp    时间: 2013-05-12 21:28
感觉没问题，虽然都不是原子的，你仔细想想在边界值的时候，都是先赋值再递增， List[Push_Index] = AData;          Push_Count++;     pop也是这样，其余push操作都是没有用到Pop_Count，（反之pop也是这样）。即便楼主说的情况发生也没有问题。
作者: koolcoy    时间: 2013-05-12 22:48
无锁环形缓冲有个重要的要求：对变量Push_Count和Pop_Count的读/写必须是原子的，否则会出错。 例如，你不能在x86架构下使用64位的Push_Count和Pop_Count.

我个人倾向于去掉Push_Index和Pop_Index，然后将数组List的大小做成一个模板参数，每次用的时候Push_Index用 (Push_Count % 数组大小)  来代替
作者: koolcoy    时间: 2013-05-12 22:57
随便写的，没测试

  2. template<typename T, int tSize>
  3. class RingQueue {
  4. public:
  5.         RingQueue() : Push_Count(0), Pop_Count(0) {}

  7.         bool empty() {
  8.                 return Push_Count == Pop_Count;
  9.         }

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

  19.         T pop() {
  20.                 if (empty()) {
  21.                         throw;
  22.                 }
  23.                 return List[Pop_Count++ % tSize];
  24.         }

  26. private:
  27.         T List[tSize];
  28.         int Push_Count;
  29.         int Pop_Count;
  30. };
复制代码
作者: linux_c_py_php    时间: 2013-05-13 00:13
没了解过, 有什么介绍这个的吗.
作者: 井蛙夏虫    时间: 2013-05-13 00:29
本帖最后由 井蛙夏虫 于 2013-05-13 00:32 编辑

这个是回复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],此时将为新值，而原先的旧值就丢失了。



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2