免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 6287 | 回复: 8

关于传说中的无锁环形缓冲区的疑问 [复制链接]

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2012-01-14 02:04 |显示全部楼层
本帖最后由 cookis 于 2012-01-14 02:06 编辑
  1. template<class T>
  2. class RingQueue {
  3. public:

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

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

  10.     void InitQueue() {
  11.         Push_Count = 0;
  12.         Push_Index = 0;
  13.         Pop_Count = 0;
  14.         Pop_Index = 0;
  15.         memset(List, 0, sizeof (List));
  16.     }

  17.     bool Push(const T& AData) {
  18.         if (Push_Count - Pop_Count < Max_Count) {               // tag 1:  读取 Pop_Count
  19.             List[Push_Index] = AData;
  20.             Push_Count++;                                                      
  21.             if (Push_Index == High_Index)
  22.                 Push_Index = 0;
  23.             else
  24.                 Push_Index++;
  25.             return true;
  26.         } else
  27.             return false;
  28.     }
  29.     T Pop() {
  30.         T result = NULL;
  31.         if (Push_Count != Pop_Count) {
  32.             result = List[Pop_Index];
  33.             Pop_Count++;                                                     // tag 2 : 重置
  34.             if (Pop_Index == High_Index)
  35.                 Pop_Index = 0;
  36.             else
  37.                 Pop_Index++;
  38.         }
  39.         return result;
  40.     }

  41.     long size() {
  42.         return this->Push_Count - this->Pop_Count;
  43.     }

  44. private:
  45.     RingQueue(const RingQueue& orig);
  46.     T List[524288 * 2]; //2^19  4M�ռ�
  47.     const static unsigned long Max_Count = 524288 * 2;
  48.     const static unsigned long High_Index = 524288 * 2 - 1;
  49.     unsigned long Push_Count;
  50.     unsigned long Push_Index;
  51.     unsigned long Pop_Count;
  52.     unsigned long Pop_Index;

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


论坛徽章:
11
未羊
日期:2013-12-16 12:45:4615-16赛季CBA联赛之青岛
日期:2016-04-11 19:17:4715-16赛季CBA联赛之广夏
日期:2016-04-06 16:34:012015亚冠之卡尔希纳萨夫
日期:2015-11-10 10:04:522015亚冠之大阪钢巴
日期:2015-07-30 18:29:402015亚冠之城南
日期:2015-06-15 17:56:392015亚冠之卡尔希纳萨夫
日期:2015-05-15 15:19:272015亚冠之山东鲁能
日期:2015-05-14 12:38:13金牛座
日期:2014-12-04 15:34:06子鼠
日期:2014-10-16 13:40:4715-16赛季CBA联赛之八一
日期:2016-07-22 09:41:40
发表于 2012-01-14 08:03 来自手机 |显示全部楼层
这次读旧值,下次可以读新的嘛,有啥关系

论坛徽章:
0
发表于 2012-01-14 17:06 |显示全部楼层
只有一个写者来push。

论坛徽章:
4
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11IT运维版块每日发帖之星
日期:2016-08-11 06:20:00IT运维版块每日发帖之星
日期:2016-08-15 06:20:00
发表于 2013-04-28 16:36 |显示全部楼层
我项目中用到了类似实现,一个线程写,一个线程读,经过压测,没有发现异常。
今天和同事交流,他们提到了内存屏障和乱序执行的问题,我就有些纠结了。
我觉得采用这种无锁实现,原理上不存在数据错乱的现象/问题。
请懂行的大拿点评!谢谢!

论坛徽章:
0
发表于 2013-05-12 21:28 |显示全部楼层
感觉没问题,虽然都不是原子的,你仔细想想在边界值的时候,都是先赋值再递增, List[Push_Index] = AData;          Push_Count++;     pop也是这样,其余push操作都是没有用到Pop_Count,(反之pop也是这样)。即便楼主说的情况发生也没有问题。

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:49:45
发表于 2013-05-12 22:48 |显示全部楼层
无锁环形缓冲有个重要的要求:对变量Push_Count和Pop_Count的读/写必须是原子的,否则会出错。 例如,你不能在x86架构下使用64位的Push_Count和Pop_Count.

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

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:49:45
发表于 2013-05-12 22:57 |显示全部楼层
随便写的,没测试

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

  5.         bool empty() {
  6.                 return Push_Count == Pop_Count;
  7.         }

  8.         bool push(const T& a) {
  9.                 if (Push_Count - Pop_Count >= tSize) {
  10.                         return false;
  11.                 }
  12.                 List[Push_Count++ % tSize] = a;
  13.                 return true;
  14.         }

  15.         T pop() {
  16.                 if (empty()) {
  17.                         throw;
  18.                 }
  19.                 return List[Pop_Count++ % tSize];
  20.         }

  21. private:
  22.         T List[tSize];
  23.         int Push_Count;
  24.         int Pop_Count;
  25. };
复制代码

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2013-05-13 00:13 |显示全部楼层
没了解过, 有什么介绍这个的吗.

论坛徽章:
4
白羊座
日期:2013-09-17 21:59:30技术图书徽章
日期:2013-10-12 22:16:03白羊座
日期:2013-10-14 11:01:40双子座
日期:2013-12-17 18:26:39
发表于 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],此时将为新值,而原先的旧值就丢失了。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP