C++ ’ 目录归档

并行编程中的内存回收Hazard Pointer

感谢同事【kevinlynx】在本站发表此文

接上篇使用RCU技术实现读写线程无锁,在没有GC机制的语言中,要实现Lock free的算法,就免不了要自己处理内存回收的问题。

Hazard Pointer是另一种处理这个问题的算法,而且相比起来不但简单,功能也很强大。锁无关的数据结构与Hazard指针中讲得很好,Wikipedia Hazard pointer也描述得比较清楚,所以我这里就不讲那么细了。

一个简单的实现可以参考我的github haz_ptr.c
阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 并行编程中的内存回收Hazard Pointer

无锁有序链表的实现

感谢同事【kevinlynx】在本站发表此文

无锁有序链表可以保证元素的唯一性,使其可用于哈希表的桶,甚至直接作为一个效率不那么高的map。普通链表的无锁实现相对简单点,因为插入元素可以在表头插,而有序链表的插入则是任意位置。

本文主要基于论文High Performance Dynamic Lock-Free Hash Tables实现。
阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 无锁有序链表的实现

线程基础之JAVA和C++0x的特性

译文连接   译文地址  译者:衣着时   校对:丁一    (有兴趣参与试译或校对的同学,请加入并发网试译者QQ群:369468545)

JAVA特性

JAVA线程通常是一个带有run()方法的java.lang.Thread的子类,然后调用这个子类对象的start()方法。我们之前定义过,数据竞争是因为两个线程同时访问内存单元,在JAVA中,内存单元是一个对象字段或数组元素。

由于JAVA旨在支持运行不受信任代码作为受信任的应用程序的一部分,必须限制不受信任代码的数据争用造成的破坏。因此不允许数据争用的任意行为,所以,JAVA语言规范包含了一个复杂的规则集,用来定义线程间的共享对象的行为,包括数据争用的行为,这些规则的影响甚至专家都觉得惊讶。然而这些规则保证了免除数据争用的程序的连续一致,对于程序来讲是个更加容易的模型。

如上所述JAVA的数据争用定义的可替换的定义是,并发冲突操作必须被阻止同时出现通过执行相同的线程,或者引入强制实施线程间的顺序的同步变量。如果采用了这些机制,就可以说一个内存操作发生在另一个内存操作之前。因此不会发生交叉存储。这基本相当于我们的定义。 阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 线程基础之JAVA和C++0x的特性

gcc的 “-fpack-struct” 编译选项导致程序core dump的分析

感谢网友【nanxiao】的投稿

最近team引入gcov来做代码分析。编译好的程序在Solaris上运行的好好的,结果在Linux上一运行就会产生core dump文件。这篇文章就介绍整个分析过程。

首先用gdb分析core文件,显示是strlen调用出了问题:

(gdb) 
#0  0x00000034e433386f in __strlen_sse42 () from /lib64/libc.so.6
#1  0x000000000053c57a in __gcov_init ()
#2  0x000000000053c4b9 in _GLOBAL__I_65535_0_g_cmd_param () at source/rerun/aicent_ara_rerun.c:963
#3  0x000000000053dc26 in __do_global_ctors_aux ()
#4  0x0000000000403743 in _init ()
#5  0x00007fff6d6b3ce8 in ?? ()
#6  0x000000000053db55 in __libc_csu_init ()
#7  0x00000034e421ecb0 in __libc_start_main () from /lib64/libc.so.6
#8  0x0000000000404449 in _start ()

由于我们使用的gcc是用安装包形式安装的,没有源码。所以就从github上找了相应版本的gcc源代码,希望能有所帮助。以下是__gcov_init函数的代码(https://github.com/gcc-mirror/gcc/blob/gcc-4_4_7-release/gcc/libgcov.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

阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Harris’s Linked List

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)。尽管这个细微的差异可能看起来并不重要,但是当我们的目标是从同步或是并发算法中挖掘最大性能时,就需要关注这个差异了。

阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Ticket Lock的Relaxed Atomics优化

使用CAS实现无锁的SkipList

感谢同事【付哲】发布此文。

无锁

并发环境下最常用的同步手段是互斥锁和读写锁,例如pthread_mutex和pthread_readwrite_lock,常用的范式为:

void ConcurrencyOperation() {
	mutex.lock();
	// do something
	mutex.unlock();
}

这种方法的优点是:

  1. 编程模型简单,如果小心控制上锁顺序,一般来说不会有死锁的问题;
  2. 可以通过调节锁的粒度来调节性能。 阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 使用CAS实现无锁的SkipList

《C++ 并发编程》- 第1章 你好,C++的并发世界

Snip20131231_6
本文是《C++ 并发编程》的第一章,感谢人民邮电出版社授权并发编程网发表此文,版权所有,请勿转载。该书将于近期上市。

本章主要内容

  • 何谓并发和多线程
  •  为什么要在应用程序中使用并发和多线程
  •  C++并发支持的发展历程
  •  一个简单的C++多线程程序是什么样的

这是C++用户的振奋时刻。距1998年初始的C++标准发布13年后,C++标准委员会给予程序语言和它的支持库一次重大的变革。新的C++标准(也被称为C++11或C++0x)于2011年发布并带来了很多的改变,使得C++的应用更加容易并富有成效。

阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 《C++ 并发编程》- 第1章 你好,C++的并发世界

《C++ Concurrency in Action》中文版

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

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

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 《C++ Concurrency in Action》中文版

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

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

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

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

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: C++11 并发编程指南——前言

并行快速排序

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

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

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

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

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 并行快速排序

return top