计算机工程2017，Vol.43Issue(9)：23-28,6.DOI:10.3969/j.issn.1000-3428.2017.09.005
基于Transpose规则的无锁自组织链表算法
Lock-free Self-organizing Linked-list Algorithm Based on Transpose Rule
摘要
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.关键词
并发/自组织/链表/无锁/Transpose规则Key words
concurrency/self-organization/linked-list/lock-free/Transpose rule分类
信息技术与安全科学引用本文复制引用
孙静,张亚平,李鹏飞,张坤龙..基于Transpose规则的无锁自组织链表算法[J].计算机工程,2017,43(9):23-28,6.基金项目
天津市科技支撑计划项目(15ZCZDSY00960) （15ZCZDSY00960）
天津市自然科学基金面上项目(15JCQNJC00200). （15JCQNJC00200）
