并发数据结构

《Concurrent Data Structures》(并发数据结构)一文是Mark MoirNir Shavit所撰写的一篇有关并发数据结构的综述性文章。这篇文章从多核处理器基础开始,理清了并发数据结构的基础设计理念和技巧,介绍了数据结构算法相关的正确性证明,并列举了栈,链表,队列,树等常用并发数据结构的设计思路。

为了促进大家对并发数据结构基础概念的了解,并发编程网组织译者翻译该论文。由于时间仓促,如有不到位的地方,还请各位指出。

感谢下列译者:董明鑫,俞升兵,Noodles,张军,huavben,iDestiny,郭振斌

论文目录

1.1 并发的数据结构的设计

1.1.1 性能

1.1.2 阻塞技术

1.1.3 非阻塞技术

1.1.4 复杂度测量&1.1.5 正确性

1.2 共享计数器和Fetch-and-φ结构

1.3 栈和队列

1.4 池

1.5 链表

1.6 哈希表

1.7 查找树

1.8 优先队列&1.9 总结

并发数据结构基础概念和原则

并发数据结构即允许多线程同时访问(读和写)的数据结构。

并发数据结构中的算法的设计原则主要分两大类,liveness(活性)和safety(安全性),这两个概念最初来源于分布式系统设计。其中liveness特性保证算法可以执行,而safety保证算法最终得到想要的结果。举一个例子:

问题描述:

对一段序列进行排序,得到降序序列

safety特性:

当算法结束时,得到的序列为输入序列的降序序列。

liveness特性:

最终算法可以运行结束,并返回一段序列。

更加详细的概念和原则介绍可以参考wiki。,

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 并发数据结构

周 可人

在校学生,从事并发数据结构研究,关注并发和并行技术。

Latest posts by 周 可人 (see all)

FavoriteLoading添加本文到我的收藏
  • Trackback are closed
  • Comments (0)
  1. No comments yet.

You must be logged in to post a comment.

return top