并发非阻塞自组织链表算法

作者：陈春光; 张坤龙; 谭龙飞; 韩昭

来源：计算机工程, 2013, (08): 31-37.

• 并发
• 非阻塞
• 自组织
• 链表
• 可线性化
• 互斥 concurrent
• non-blocking
• self-organizing
• linked list
• linearizability
• mutex

利用自组织链表处理局部性较强的请求可提高性能,而非阻塞算法则能保证健壮性和可靠性。基于此,提出一种并发非阻塞自组织链表算法。使用MTF并发规则进行自组织操作,采用同步原语CAS实现并发程序,以保证查找、插入和删除操作的可线性化。实验结果表明,与Heller、Harris算法相比,随着读操作比例增大、链表变长,该算法的性能得到迅速改善。当读操作比例为90%、键值范围为4 096时,其消耗时间最少。

• 单位
  天津大学