并发数据结构-1.1 并发的数据结构的设计-阿里云开发者社区

开发者社区> boxti> 正文

并发数据结构-1.1 并发的数据结构的设计

简介:
+关注继续查看

原文链接译文链接,译者:董明鑫,校对:周可人

随着多个处理器共享同一内存的机器在商业上的广泛使用,并发编程的艺术也产生了巨大的变化。当前的趋势向着低功耗芯片级多线程(CMT)发展,所以这样的机器一定会更加广泛的被使用。

共享内存多处理器是指并发的执行多个线程的系统,这些线程在共享的内存中通过数据结构通讯和同步。这些数据结构的效率对于性能是很关键的,而目前熟练掌握为多处理器机器设计高效数据结构这一技术的人并不多。对大多数人来说,设计并发的数据结构比设计单线程的难多了,因为并发执行的线程可能会多种方式地交错运行他们的指令,每一种方式会带来不同的,甚至不符合预期的输出。这就要求设计者改变他们对运算的认识,理解新的设计方法,采用新的编程工具集。此外,设计可扩展的并发数据结构,使得当机器执行越来越多的并发线程时依旧表现良好也是新的挑战。本文主要介绍设计并发数据结构的相关挑战,和一些重要的数据结构相关内容的总结。我们的总结绝不是全面的;相反,我们特意选取了一些能说明设计的关键问题的流行的数据结构,希望我们提供了足够的背景和知识,让有兴趣的读者接触那些我们没有提到的内容。

1.1 并发的数据结构的设计

共享内存多处理器的一些特性使得并发数据结构的设计和校验比相对应的单线程结构难度显著增加。

acquire(Lock);

oldval = X;                                                                                      oldval = X;

X = oldval + 1;                                                                                X = oldval + 1;

return oldval;                                                                                 release(Lock);

return oldval;

图1.1:顺序的和基于锁机制的fetch-and-inc操作代码片段

难点的根源在于并发:因为线程是在不同的处理器上并发的执行,而且受操作系统的调度决策、缺页、中断等等影响,我们必须按照全部异步的想法来思考,以保证不同的线程能够随意交错的运行。这显著提升了正确设计并发数据结构的复杂度。

为多处理器系统设计并发的数据结构在性能和可扩展性上也有大量的挑战。在现代的机器上,处理器和内存的布局、数据在内存中的布局、多处理器体系结构中各个元素间的通信负载全都对性能有影响。此外,正确性和性能两者联系非常的紧密:算法的改进在提高性能的同时经常使其更加难以设计和检验正确的数据结构实现。

下面的例子阐述了影响数据结构设计的各个多处理器特征。假设我们想要实现一个共享的计数器数据结构,用于支持fetch-and-inc操作,即计数器加一然后返回增加前的值。一个普通的顺序fetch-and-inc实现的代码就如图1.1中左边部分所展示的那样。

如果我们允许多个线程并发地调用fetch-and-inc操作,上述实现运行起来并不正确。来看看原因,注意大多数编译器会把这份源代码转换成机器指令:把 X 的值装进一个寄存器,然后把寄存器中的值加一,然后再把这个寄存器的值存回 X 。假如计数器初始化为 0 ,两个不同的处理器并发的执行两个fetch-and-inc操作。然后就有可能两个操作都从 X 中读出 0 ,然后都把 1 存回 X 并且返回 0 。这显然是不正确的:两个操作中有一个应该返回 1 。

如上所述,两个fetch-and-inc操作不正确的交错结果导致了不正确的行为。一个自然并且普通的方法来阻止这样的交错就是用互斥锁(也被叫做 mutex 或者 lock)。锁是一个在任意时间点,都是不被(其他线程)获取,只被一个线程所获取的构造。如果一个线程 t1 希望获取已经被另一个线程 t2 所获取到的锁,那么 t1 必须等到 t2 释放这个锁。

如图 1.1 右半部分所示,我们能通过锁机制得到一个正确的顺序实现。我们通过阻止所有的交错来预防坏的交错。这样很容易得到一个正确的共享计数器,然而这种简单是有代价的:锁机制引发了许多关于性能和软件工程上的问题。


文章转自 并发编程网-ifeve.com

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
[20180312]不好的数据结构设计3.txt
[20180312]不好的数据结构设计3.txt --//上个星期提到一种不好的数据结构设计.今天在提到一种: --//就是本来一行保存的信息,变成竖着保存,涉及一些安全信息,通过例子来说明: 1.
720 0
[redis设计与实现][3]基本数据结构——字典
Redis字典采用哈希表实现。 哈希表: [cce lang=”c”] typedef struct dictht { //哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表掩码,用于计算索引值,总是等于size –
1142 0
合并数据
原文:合并数据   在实际项目开发过程中,经常有合并数据的需求。这里合并数据的意思是,对于源表A,目标表B,如果A中存在B中不存在则插入记录,如果A中存在B中也存在则更新记录,如果A中不存在B中存在则删除记录。
516 0
【数道云大数据】Hadoop大数据技术有什么市场价值?2019年Hadoop大数据技术7大应用领域
由于国家对大数据、AI等等技术的关注,在多次发展规划中都提高了大数据技术,因此大数据技术对于这个时代的发展来说至关重要,大数据也正处于发展期、巩固期,基于已有的技术去完善和不断的发展大数据技术产品,满足互联网不符按发在的需求,使国家的技术产业得到进步和发展。
924 0
+关注
boxti
12535
10037
文章
1327
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载