什么是并发数据结构? 引用上的定义

In computer science, a concurrent data structure is a particular way of storing and organizing data for access by multiple computing threads (or processes) on a computer.

简而言之，并发数据结构即允许多线程同时访问（读和写）的数据结构。

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

问题描述：

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

safety特性：

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

liveness特性：

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

事实上Java.util.concurrent包中一些数据结构就是按照并发数据结构的原则来设计的，比如ConcurrentLinkedQueue，是一个lock-free的双端队列，ConcurrentSkipListMap则是一个lock-free的跳表。Lock-free就是liveness的一个具体表现。为了让大家更加了解并发数据结构的设计原则和设计技巧，这里推荐了一篇综述性质的论文<<>>，期待大家共同参与翻译。

论文目录

1. Designing Concurrent Data Structures………….
   • Performance
   • Blocking Techniques
   • Nonblocking Techniques
   • Complexity Measures
   • Correctness
   • Verification Techniques
   • Tools of the Trade
2. Shared Counters and Fetch-and-φ Structures ….. 1-12
3. Stacks and Queues ……………………………… 1-14
4. Pools ……………………………………………. 1-17
5. Linked Lists…………………………………….. 1-18
6. Hash Tables …………………………………….. 1-19
7. Search Trees…………………………………….. 1-20
8. Priority Queues…………………………………. 1-22
9. Summary ……………………………………….. 1-23

如何翻译

1. 你可从以上几篇文章中挑选某一篇进行翻译，翻译时间最好是一个星期以内，翻译前请发邮件到125353769@qq.com，联系人为梁海舰。
2. 译者署名的顺序由翻译的字数确定。
3. 校对：与其他译者交叉校对+本站编辑校对，互相讨论翻译与技术问题。
4. 如何提交：在并发编程网用QQ登陆，然后发布译文。
5. 建议。建议多增加译者注解，无论对于翻译还是读者都有好处。

注意事项