基于无锁方法的二叉搜索树算法研究

发布时间：2020-05-07 01:22

【摘要】：随着多核/众核技术的发展,高并发的数据结构成为并发程序设计的研究热点。二叉搜索树应用范围广泛,在并发数据结构中占有重要地位。高并发无锁二叉搜索树算法的设计与实现将对并发程序的设计提供强有力支持。目前针对二叉搜索树算法的研究,存在多个线程对共享资源的同步访问问题。传统解决方案使用锁机制进行同步,以确保线程的安全访问,但容易引起锁竞争和死锁等问题,导致算法效率低下。针对二叉搜索树算法使用锁机制引起的问题,本文提出了一种新的无锁算法。该算法使用比较和交换(CAS)指令,在异步共享内存系统中完成对二叉搜索树的搜索,插入和删除操作。本文算法使用外部(面向叶子)搜索树模型,该模型的优点是不存在删除具有两个孩子结点的情况,从而提高了删除操作的效率。与研究二叉搜索树需要获得内部节点的方式不同,本文算法运用整体的思想,通过操作子树来处理插入和删除操作。本文介绍了无锁二叉搜索树算法的设计细节,在各种条件(不同的树形大小,工作量分布和争用度)下进行了实验,将本文的算法与Bronson等人基于锁的算法、Ellen等人基于无锁的算法进行了吞吐量大小的比较。实验结果表明,当线程数大于4时,本文算法的吞吐量优于其他两个并发BST算法,可以有效地减少更新(插入或删除)操作之间的争用。当并发性较高时,本文的算法将具有一定竞争力。
【图文】：

上述 7 类演进条件，按照演进条件的限定要求对其进行从小到塞、无饥饿、无干扰、无锁、无等待、有界无等待、集居数无程度比较低则线程并发执行的操作会被其他任务或因素影响，反之，线程并发执行的操作受到的干扰少，性能得到提升。演低的演进条件。如果某个数据结构符合演进程度高的要求，，则低的要求[44]。如：“无锁的数据结构是无干扰的”（反之不对法包含无干扰方法的要求。

使用原子操作的方式进行多线程并。统计显示执行CAS操作运行的时间大约是锁以它是并发数据结构设计的重要方式[47]。使用，它不仅可以使程序的性能得到提升，有效避展的。使用CAS操作方式在并发数据结构设计叉搜索树。无锁并发中CAS的用法：的有锁方式 假设在多线程环境下需要实现具otalCount，由于线程会并发修改totalCount计数器行同步，如下图 2-4 所示。
【学位授予单位】：河北科技大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP311.12

【参考文献】

相关期刊论文 前2条

1 王防修;周康;;一种构建严格平衡二叉搜索树的非递归算法[J];武汉工业学院学报;2013年04期

2 孙召伟;赵建利;朱东生;;数据结构中递归转非递归算法分析及模型设计研究[J];河北科技大学学报;2011年01期

相关博士学位论文 前1条

1 彭建章;非阻塞算法与多进程网络程序优化研究[D];中国科学技术大学;2013年

相关硕士学位论文 前5条

1 刘正阳;C/C++多线程程序并发访存问题的软件分析研究[D];北京邮电大学;2017年

2 谢文韬;基于无锁结构的大容量数据高性能检索系统研究[D];东南大学;2017年

3 路佳佳;面向多核共享内存的低功耗研究[D];北京工业大学;2016年

4 曹红星;一种无锁并发跳表算法的可线性化证明[D];中国科学技术大学;2014年

5 刘恒;并发数据结构及其在动态内存管理中的应用[D];重庆大学;2013年

本文编号：2652188