| 无锁并发二叉搜索树的实现 |
| |
| 引用本文： | 刘少东,邢永康,刘恒.无锁并发二叉搜索树的实现[J].计算机应用,2012,32(10):2736-2741. |
| |
| 作者姓名： | 刘少东 邢永康 刘恒 |
| |
| 作者单位： | 重庆大学 计算机学院, 重庆 400044 |
| |
| 摘 要： | 针对异步共享内存模型下的并发搜索二叉树（BST）数据结构,提出了一种新的无锁实现方法。通过一种有效的节点重用策略,使得删除操作是无等待的,插入操作是无锁的。实验数据表明,该数据结构是高度可扩展的而且在高负载下能提供很高的吞吐量。
|
| 关 键 词： | 无锁搜索二叉树 无锁 无等待 可扩展 高吞吐量 |
| 收稿时间： | 2012-03-21 |
| 修稿时间： | 2012-05-14 |
Lock-free implementation of concurrent binary search tree |
| |
| LIU Shao-dong,XING Yong-kang,LIU Heng.Lock-free implementation of concurrent binary search tree[J].journal of Computer Applications,2012,32(10):2736-2741. |
| |
| Authors: | LIU Shao-dong XING Yong-kang LIU Heng |
| |
| Affiliation: | College of Computer Science, Chongqing University, Chongqing 400044, China |
| |
| Abstract: | A new scheme for unlocking implementation of concurrent Binary Search Tree(BST) based on asynchronous shared memory systems was provided in this paper.This scheme possessed two outstanding advantages:The deletion is wait-free,and the insertion is lock-free.The experimental results show that this scheme is highly scalable and can produce high throughputs under heavy load. |
| |
| Keywords: | unlocking binary search tree lock-free wait-free scalable high parallel |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
|
