- 1
- 2
- 3
- 4
- 5
高并发无锁二叉树的实现及应用
资料介绍
多核处理器时代的到来对数据结构的设计和使用带来了革命性的变化它成为了主流软件开发的一个拐点：而对越来越瞢及的多核体系结构，开发者必须编写可扩展的并行程序才能够享受到随着处理器核数的增多面带来的性能提升编写并行程序会遇到很多挑战，其中一个重要的问题便是多线程环境下对共享内存的同步访问间题。并发执行线程之间的通信交流以及同步是通过共享内存中的特定数据结构完成的。传统的解决方案中使用锁来保持问步，但是基于锁的同步往往伴随着非常严重的缺陷：简单的粗粒度锁都是不可扩展的；复杂的细粒度镇不仅使用复杂，而且还增加了引起死锁和数据竞争等严重问题的风险，近年来无锁数据结构开始兴起，使用CAS这种细粒度同步原语不仅能摆脱死锁和数据克争问题，更重要的是它是可扩展的。本文的并发二叉搜案树算法同样也是基于该原理。
本文针对异步共享内存模型提出了一个放宽条件的二又搜索树的无锁并发实现。基于二又树的特性，使用种优化的结点重用策略使得删除操作是无等持的剩除操作并不将结点从物理内存中删除，而是将其标记为逻辑剧除结点，后续的插入操作可以通过重用某逻辑制除结点或者新建结点插入的方式完成。该策略不仅有效的避免了ABA问题，而且使得插入操作是无锁的，实验数据表明本文的结点重用策略是有效的，算法具有良好的并发度，在高负载下的性能表现大约为目前性能最好的并发树的两倍，并且算法具有良好的扩展性本文还证明了算法在并发环境下的安全性以及插入算法的无锁性和删除算法的无等待性，并且指出了算法中的线性化点。指出了算法在应用上有关性能的注意事项，并给出了两个具体应用：一是利用本文算法构造出通用并行内排序算法井给出了实验性能参数：二是实现了一个线程安全的动态索引，并在实验中与squd服务器实现的版本对比。本文算法实现上有一定的复杂度，但是对外暴露的接口和普通树一样方便使用。实验结果表明两个应用不仅性能优良，而且具备突出的可扩展性。
部分文件列表
| 文件名 | 大小 |
| 高并发无锁二叉树的实现及应用.pdf | 16M |
最新上传
- 打赏
- 30日榜单
-
21ic小能手 打赏10.00元 3天前
-
21ic小能手 打赏20.00元 3天前
-
21ic小能手 打赏15.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
21ic下载 打赏310.00元 3天前
用户：小猫做电路
-
21ic下载 打赏310.00元 3天前
用户：gsy幸运
-
21ic下载 打赏310.00元 3天前
用户：liqiang9090
-
21ic下载 打赏310.00元 3天前
用户：zhengdai
-
21ic下载 打赏160.00元 3天前
用户：w1966891335
-
21ic下载 打赏160.00元 3天前
用户：w178191520
-
21ic下载 打赏160.00元 3天前
用户：kk1957135547
-
21ic下载 打赏40.00元 3天前
用户：WK520077778
-
21ic下载 打赏40.00元 3天前
用户：sun2152
-
21ic下载 打赏30.00元 3天前
用户：xuzhen1
-
21ic下载 打赏50.00元 3天前
用户：铁蛋锅
-
21ic下载 打赏30.00元 3天前
用户：xzxbybd
-
21ic下载 打赏40.00元 3天前
用户：z00
-
21ic下载 打赏40.00元 3天前
用户：forgot
-
21ic下载 打赏40.00元 3天前
用户：happypcb
-
21ic下载 打赏20.00元 3天前
用户：zhaoqshan
-
21ic下载 打赏5.00元 3天前
用户：17724187683
-
21ic下载 打赏5.00元 3天前
用户：zmm1818
-
21ic小能手 打赏15.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
chenruiji 打赏1.00元 3天前
资料：血糖仪原理图
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
资料：测试智能语音控制模块
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
全部评论(0)