基于MTF规则的非阻塞自组织链表

• 作者: 康超凡
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 并发 无锁 自组织 链表
• 年，卷（期）: 2017,（7）
• 所属期刊栏目: 算法
• 页码范围: 286-292,307
• 页数: 8页
• 分类号: TP311.11
• 字数: 7251字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2017.07.053

摘要

自组织链表是一种特殊的链表.与静态链表相比,将自组织链表应用于并发环境下,需要考虑自组织操作对链表状态的改变.因此,对于并发自组织链表,尤其是具有非阻塞特性的自组织链表的研究更加复杂.近些年来,并发链表的研究成果显著,而关于并发自组织链表算法的研究屈指可数.在这种背景下,提出了一种基于MTF(Move-To-Front)自组织规则的无锁自组织链表,证明了该链表算法实现了在集合上的插入、删除,以及查找操作,并且算法的实现是无锁的.实验结果表明,该算法的性能在大多数情况下都优于Harris算法,具有一定的使用价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	康超凡	天津大学计算机科学与技术学院	3	7	2.0	2.0