免费注册 查看新帖 |

Chinaunix

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

[算法] 关于无锁(lock-free)数据结构所需MCAS(多字比较交换)操作的Harris实现方案请教 [复制链接]

论坛徽章:
0
发表于 2012-10-26 10:23 |显示全部楼层
最近在考虑无锁数据结构,Harris有关于这方面集大成的一篇介绍CPWL《Concurrent_Programming_Without_Locks》,其中介绍到一般情况下实现所需的MCAS操作。

对于其中实现MCAS的提到的CCAS我有些不太理解,我认为它等同于一个直接的CAS交换再加上后续的比较操作,根据介绍CCAS主要是通过保证CAS和条件判断的线性化而提出的,这也跟我的理解应该是一样,因此我认为可以省略掉CCAS部分,而直接按照下述伪代码实现其中的MCASHelp(在原有基础上修改):
  1. bool MCASHelp (MCASDesc *d) {
  2.     word *v, desired := FAILED;
  3.     bool success;
  4.     /* PHASE 1: Attempt to acquire each location in turn. */
  5.     for ( int i := 0; i < d->N && d->status = UNDECIDED; i++ )
  6.       v := *d->a[i];
  7.       while ( v != d && d->status = UNDECIDED ) {
  8.         if ( IsMCASDesc(v) ) {
  9.           MCASHelp((MCASDesc *)v);
  10.         } else {
  11.           if (v != d->e[i]) goto decision point;
  12.           if (CAS(d->a[i], d->e[i], d)) break;
  13.         }
  14.         v := *d->a[i];
  15.       }
  16.     }
  17.     desired := SUCCESSFUL;
  18.     /* PHASE 2: No read-phase is used in MCAS */
  19.     decision point:
  20.     CAS(&d->status, UNDECIDED, desired);
  21.     /* PHASE 3: Release each location that we hold. */
  22.     success := (d->status = SUCCESSFUL);
  23.     for ( int i := 0; i < d->N; i++ )
  24.     CAS(d->a[i], d, success ? d->n[i] : d->e[i]);
  25.     return success:
  26. }
复制代码
我想知道我的认识是否正确,如果不是这样,上述实现中跟原来有什么不同,存在什么问题?

谢过。

论坛徽章:
0
发表于 2012-10-26 10:37 |显示全部楼层
mark一下

字数补丁

论坛徽章:
0
发表于 2012-10-26 14:28 |显示全部楼层
大概介绍一下我的理解:
lock-free可以看作某线程未完成的可能影响到其他人运行的任务可以由其他人帮助完成,已保证整个系统不受阻塞。(相应wait-free,就是每个线程都可以独立完成自己的任务)。
大概介绍一下MCAS过程,CPWL中有个图比较容易理解,就是逐个完成CAS操作,因为这些操作是线性次序的,所以所有参与到帮助过程的线程不会产生不一致的情况,并在最终由一个CAS操作互斥的决定整个过程的成败。

目前我所知有无CCAS的不同在于:
CCAS保证了当一次MCAS完成后,其中所有的MCAS指针都已经被替换完毕,但在失败的情况下,可能与某些CCAS操作产生竞争,就是留下一些注定会失败的CCAS槽位,这些CCAS会返回原先的值(因为条件在CCAS最后判断)。

而去除CCAS,则可能一次MCAS完成后,当失败的情况下,可能会因竞争而遗留下一些MCAS槽位,当然这也MCAS也已经是注定为失败了的,后续的帮助系统也能够进行正确的识别。

因为整个实现中为解决读写冲突,读过程中也脱离不开帮助系统,所以上述两种我以为没有差别。

论坛徽章:
0
发表于 2012-10-30 22:05 |显示全部楼层
我想我知道可能错误在哪里了,上面的理解中提到的只有失败情况下才产生冲突是不对的。是在一次MCAS完成后,其他的辅助MCAS进程会跟后续其他新的写入重叠槽位的MCAS发生冲突,也就是存在ABA问题,这时CCAS能够被设置为返回同样但是可能是新写入的和原先一样的值,而去除了CCAS则无法辨别。

我之前的想法是建立在槽位上的数据是指针,内存不释放前不复用而新分配的假设下,应该是错误的看法。

无锁数据分配和回收大多依赖于GC,而我正在考虑的就是一个简单的不依赖于GC/线程设施的回收方法,已经基本实现,有兴趣的话可以交流。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP