基于Transpose规则的无锁自组织链表算法

摘要：

自组织链表可以依据访问序列动态调整链表结构,提高链表性能.在分析并研究现有自组织链表算法的基础上,结合Transpose规则,提出无锁自组织链表算法.线程可标记被访问的结点并尝试与标记结点前驱相交换,也可直接物理删除已被标记的结点,同时其他线程发现该标记结点时会辅助该线程完成相应操作,从而保证链表的非阻塞特性.实验结果表明,该算法性能与Harris-Michael链表算法相当,并且其无锁实现方式比粗粒度锁算法更具优势.

关键词：并发、自组织、链表、无锁、Transpose规则

所属期刊栏目：43

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

资助基金：天津市科技支撑计划项目15ZCZDSY00960;天津市自然科学基金面上项目15JCQNJC00200

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

页数：共6页

页码：23-28