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

• 作者: 张坤龙 谭龙飞 陈春光 韩昭
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 并发 非阻塞 自组织 链表 可线性化 互斥
• 年，卷（期）: 2013,（8）
• 所属期刊栏目: 专栏
• 页码范围: 31-37
• 页数: 7页
• 分类号: TP311.1
• 字数: 5963字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2013.08.007

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈春光	天津大学软件学院	7	25	3.0	4.0
2	张坤龙	天津大学计算机科学与技术学院	8	24	3.0	4.0
3	谭龙飞	天津大学计算机科学与技术学院	1	8	1.0	1.0
4	韩昭	天津大学计算机科学与技术学院	1	8	1.0	1.0