标签 ‘ c++

Harris’s Linked List

原文地址 作者:Pedro Ramalhete,译者:叶磊,校对:周可人

在学术论文中Harris Linked List是使用最广泛的并发数据结构之一。

Harris Linked List是一个基于linked-list的并发有序set(或者是map),可进行无锁性质的插入,删除和查找操作。

http://research.microsoft.com/pubs/67089/2001-disc.pdf

这篇文章最早在2001年的DISC会议上发表,作者是Tim Harris,目前在Oracle就职。

https://labs.oracle.com/pls/apex/f?p=labs:bio:0:296

阅读全文

Ticket Lock的Relaxed Atomics优化

原文地址 作者:Pedro Ramalhete,译者:周可人,校对:梁海舰

Tick lock是mutual lock的一种简单实现:

http://web.mit.edu/6.173/www/currentsemester/readings/R06-scalable-synchronization-1991.pdf

它是由John Mellor-Crummey和Michael Scott在1991年提出的(pdf中2.2节),感谢C++11和C11中新的内存模型,我们可以对单个变量进行具有屏障或者不具有屏障的原子操作。当屏障没有使用,只有原子性保证时,我们称之为“relaxed atomic”:

http://en.cppreference.com/w/cpp/atomic/memory_order

注意在C11/C++11内存模型中,一个原子变量并不具有内在的“顺序一致性”或者“relaxed”性质,然而我们可以在每次访问的时选择它的行为。

原子修饰符只能保证原子性,即这个变量会被单步读或写。其他语言,如Java和Scala则不同,它们可以保证几乎所有的原生类型提供原子性保证,从而表现为“relaxed atomic”。并且,所有被声明为顺序一致性的变量可以在整个程序中保持性质(除非在Java中使用sun.misc.unsafe)。尽管这个细微的差异可能看起来并不重要,但是当我们的目标是从同步或是并发算法中挖掘最大性能时,就需要关注这个差异了。

阅读全文

《C++ Concurrency in Action》中文版

Snip20131231_6
2014年马上就到了,借此文感谢各位同学一直以来对并发编程网的支持和厚爱,祝大家新年快乐,并在新的一年里事事马到成功!在新的一年里如果您对并发编程网有什么要求,请只管在本文的回复里告诉我们。

至此新春之际,并发网和人民邮电出版社将在2014年向大家推送《C++ Concurrency in Action》中文版的样章,该书即将登场,而并发编程网让大家先睹为快!本文是第一篇,主要是包含本书的内容介绍,目录和译者介绍。喜欢的话请猛点赞。
阅读全文

C++11 并发编程指南——前言

开场白:前一段时间(大概在8月初)开始写 《C++11 并发编程指南》(最早更新于:http://www.cnblogs.com/haippy),但是由于个人能力有限,加上 9 月初到现在一直在忙着找工作(革命尚未成功),精力有限,难免出现错误,希望读者不吝指正。

另外,这是我在并发编程网上写的第一篇文章,终于迈开了第一步。受@腾飞同学的鼓励,后续我会在本站持续更新与 C++ 并发编程(尤其是C++11并发编程)相关的文章,但由于个人水平有限,希望读者指出我的错误,并多多包涵 😉

最后,个人一直在 Github上 更新 《C++11 并发编程指南》,目前已经完成了 C++11 新标准中与原子操作和多线程相关的内容,如果你对此感兴趣,也欢迎你加入进来,传播知识,方便他人。 阅读全文

并行快速排序

感谢网友浅水清流投递本稿。

并发算法是多核时代开始流行的技术趋势,比如tbbppl都提供了大量有用的并发算法。

经典算法中,排序是一个很适合采用分治法并发的场合,比如快速排序

常规的快速排序,先在数组中选取一个基准点,将数组分区为小于基准点和大于基准点(相同的数可以到任一边),对分区的子数组递归的执行分区的操作,当子数组长度为1时退出递归。此时数组就完成了排序过程。 阅读全文

return top