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

摘要：

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

关键词：并发、非阻塞、自组织、链表、可线性化、互斥

所属期刊栏目：39

分类号：TP311.1(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目10978016

在线出版日期：2013-11-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：31-37