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

doi:10.3969/j.issn.1000-3428.2013.08.007

计算机工程 ›› 2013, Vol. 39 ›› Issue (8): 31-37. doi: 10.3969/j.issn.1000-3428.2013.08.007

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

陈春光^a，张坤龙^b，谭龙飞^b，韩昭^b

(天津大学 a. 软件学院；b. 计算机科学与技术学院，天津 300072)

收稿日期:2012-09-19 出版日期:2013-08-15 发布日期:2013-08-13
作者简介:陈春光(1986－)，男，硕士研究生、CCF会员，主研方向：并发数据结构，数据库技术；张坤龙，副教授、博士；谭龙飞、韩昭，硕士研究生
基金资助:
国家自然科学基金资助项目(10978016)

Concurrent Non-blocking Self-organizing Linked List Algorithm

CHEN Chun-guang ^a, ZHANG Kun-long ^b, TAN Long-fei ^b, HAN Zhao ^b

(a. School of Computer Software; b. School of Computer Science and Technology, Tianjin University, Tianjin 300072, China)

Received:2012-09-19 Online:2013-08-15 Published:2013-08-13

摘要/Abstract

摘要：

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

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

Abstract:

Self-organizing linked lists perform well for handling requests with strong locality. Non-blocking algorithm can provide better robust and reliable. It uses MTF(Move-to-Front) concurrent rule to do concurrent operation, and presents the non-blocking self-organizing linked list algorithm which supports linearizable search, insert and remove operations using CAS primitive. Experimental results show that this algorithm performs well for long linked lists with high percentages of search operations. With the data sequence in experiment, when the percentage of lookup reaches 90% and the data range becomes 4 096, it provides the best performance.

Key words: concurrent, non-blocking, self-organizing, linked list, linearizability, mutex

中图分类号:

TP311.1

陈春光, 张坤龙, 谭龙飞, 韩昭. 并发非阻塞自组织链表算法[J]. 计算机工程, 2013, 39(8): 31-37.

CHEN Chun-Guang, ZHANG Kun-Long, TAN Long-Fei, HAN Zhao. Concurrent Non-blocking Self-organizing Linked List Algorithm[J]. Computer Engineering, 2013, 39(8): 31-37.

http://www.ecice06.com/CN/Y2013/V39/I8/31

参考文献

[1] Susanne A, Jeffery W. Self-organizing Data Structure[M]// Fiat A, Woeginger G. Online Algorithms: The State of the Art. Berlin, Germany: Springer-Verlag, 1998: 13-51.
[2] Valois J D. Lock-free Linked Lists Using Compare-and- swap[C]//Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing. New York, USA: ACM Press, 1995.
[3] Harris T L. A Pragmatic Implementation of Non-blocking Linked-lists[C]//Proceedings of the 15th International Con- ference on Distributed Computing. London, UK: [s. n.], 2001.
[4] Michael M M. High Performance Dynamic Lock-free Hash Tables and List-based Sets[C]//Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures. New York, USA: ACM Press, 2002.
[5] IBM. IBM System/370 Extended Architecture——Principles of Operation: USA, SA22-7085[P]. 1983-03-20.
[6] Treiber R K. Systems Programming: Coping with Parallelism[R]. IBM Almaden Research Center, Tech. Rep.: RJ 5118, 1986.
[7] Michael M M. Safe Memory Reclamation for Dynamic Lock- free Objects Using Atomic Reads and Writes[C]//Proceedings of the 21st Annual Symposium on Principles of Distributed Computing. New York, USA: [s. n.], 2002.
[8] Michael M M. Hazard Pointers: Safe Memory Reclamation for Lock-free Objects[J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(8): 491-504.
[9] Michael M M. Scalable Lock-free Dynamic Memory Alloca- tion[C]//Proceedings of Special Interest Group on Programming Languages Notices. Verona, Italy: [s. n.], 2004.
[10] Mikhail F, Eric R. Lock-free Linked Lists and Skip Lists[C]// Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing. New York, USA: ACM Press, 2004.
[11] Steve H, Maurice H, Victor L, et al. A Lazy Concurrent List-based Set Algorithm[C]//Proceedings of the 9th Inter- national Conference on Principles of Distributed Systems. Pisa, Italy: [s. n.], 2005.
[12] Anastasia B, Erez P. Locality-conscious Lock-free Linked Lists[C]//Proceedings of the 12th International Conference on Distributed Computing and Networking. Berlin, Germany: [s. n.], 2011.
[13] Herlihy M, Shavit N. 多处理器编程的艺术[M]. 金海, 胡侃, 译. 北京: 机械工业出版社, 2009.
[14] Burrows M, Wheeler D J. A Block-sorting Lossless Data Compression Algorithm[R]. Digital Systems Research Center, Tech. Rep.: 124, 1994.
编辑金胡考

[1]	毕翔, 黄晃, 张本宏, 卫星. 基于分簇与改进Q学习的车联网V2V复合路由算法[J]. 计算机工程, 2023, 49(3): 221-230,247.
[2]	刘强, 张颖, 周卫祥, 蒋先涛, 周薇娜, 周谋国. 自适应类增量学习的物联网入侵检测系统[J]. 计算机工程, 2023, 49(2): 169-174.
[3]	奚智雯, 蔡晶晶, 阳文敏, 柴志雷. 基于微服务架构FPGA云平台的并发请求调度机制[J]. 计算机工程, 2022, 48(7): 206-213.
[4]	赵蓓英, 姬伟峰, 翁江, 吴玄, 李映岐. 基于启发式Q学习的FANET可信路由算法[J]. 计算机工程, 2022, 48(5): 162-169.
[5]	姚政, 吴怀宇, 陈洋. 基于两阶段优化的并发流任务计算卸载策略[J]. 计算机工程, 2022, 48(12): 62-71.
[6]	杜欣欣, 胡晓辉, 赵佳楠. 一种软件定义车载自组织网络的QoS路由算法[J]. 计算机工程, 2022, 48(11): 184-191,200.
[7]	任智, 周舟, 吴本源, 陈加林. 优化链路状态路由协议的低开销拓扑维护算法[J]. 计算机工程, 2021, 47(9): 120-127,135.
[8]	张本宏, 吴浩浩, 俞磊. 车载自组织网络中基于竞争的时分多址MAC协议[J]. 计算机工程, 2021, 47(5): 154-159.
[9]	高子轩, 郑烇. NDMANET中基于内容优先级的缓存策略研究[J]. 计算机工程, 2021, 47(3): 190-195.
[10]	孙家泽, 易刚, 舒新峰. 基于Adaboost模型的并发程序数据竞争语句级检测[J]. 计算机工程, 2021, 47(12): 215-220.
[11]	乔钰, 胡晓辉, 曹乐. 基于局部密度预测的传输参数自适应拥塞控制策略[J]. 计算机工程, 2021, 47(12): 185-191,199.
[12]	曹乐, 胡晓辉, 乔钰. 一种车载自组织网络连通性维护方法[J]. 计算机工程, 2021, 47(10): 153-159.
[13]	孟磊, 冶忠林, 赵海兴, 杨燕琳. 超网络模型构建中优先连接方法研究[J]. 计算机工程, 2020, 46(10): 103-111.
[14]	鲍禹含, 付印金, 陈卫卫. 多云存储关键技术研究进展[J]. 计算机工程, 2020, 46(10): 18-32,40.
[15]	廖书亚, 李德敏, 张光林, 徐梦然. 基于信息丢失概率的停车场信息获取算法[J]. 计算机工程, 2020, 46(1): 315-320.

选择文件类型/文献管理软件名称

选择包含的内容

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

Concurrent Non-blocking Self-organizing Linked List Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

Concurrent Non-blocking Self-organizing Linked List Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价