作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

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

孙静,张亚平,李鹏飞,张坤龙   

  1. (天津大学 软件学院,天津 300072)
  • 收稿日期:2016-07-04 出版日期:2017-09-15 发布日期:2017-09-15
  • 作者简介:孙静(1990—),女,硕士研究生,主研方向为并发数据结构;张亚平,副教授、博士;李鹏飞,硕士研究生;张坤龙,副教授、博士。
  • 基金资助:
    天津市科技支撑计划项目(15ZCZDSY00960);天津市自然科学基金面上项目(15JCQNJC00200)。

Lock-free Self-organizing Linked-list Algorithm Based on Transpose Rule

SUN Jing,ZHANG Yaping,LI Pengfei,ZHANG Kunlong   

  1. (School of Computer Software,Tianjin University,Tianjin 300072,China)
  • Received:2016-07-04 Online:2017-09-15 Published:2017-09-15

摘要:

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

关键词: 并发, 自组织, 链表, 无锁, Transpose规则

Abstract:

Self-organized linked-lists can adjust their structure dynamically according to the access sequences for the sake of improving performance of them.On the basis of summarizing main self-organizing linked-list algorithms,this paper proposes a lock-free self-organizing linked-list algorithm based on Transpose rule.A thread can mark the node accessed and thentry to swap it with its precursor.Or the thread simply deletes the node.And other threads will help with the unfinished operation if they notice the node,so as guarantee the non-blocking characteristic of linked-list.The experimental result shows that the performance of this algorithm is comparable with that of the Harris algorithm,and the lock-free implementation has a good advantage over the coarse-grained lock way.

Key words: concurrency, self-organization, linked-list, lock-free, Transpose rule

中图分类号: