多核的未来

UT Austin的Yale Patt教授上个月来Chalmers交流,做了题为《Future Microprocessors: Multi-core, Mega-nonsense, and What We Must Do Differently Moving Forward》的讲座。Yale Patt是计算机体系结构学术圈的巨擘,他最有名的研究成果是和Branch Predictor和HPS microarchitecture,他的学生们也巨牛无比,学术界有名的有UIUC的Wen-Mei Hwu,CMU的Onur Mutlu等等,工业界Intel不少核心工程师也出自他的门下。这个讲座主要谈了他对未来的多核处理器的发展的看法,有趣的是他二十年前也预测过现在的处理器,我还专门问了他当时的预测是否靠谱,他说“那我得回去查查看才行”,人非常的Nice。

阅读全文>>

UT Austin的Yale Patt教授上个月来Chalmers交流,做了题为《Future Microprocessors: Multi-core, Mega-nonsense, and What We Must Do Differently Moving Forward》的讲座。Yale Patt是计算机体系结构学术圈的巨擘,他最有名的研究成果是和Branch Predictor和HPS microarchitecture,他的学生们也巨牛无比,学术界有名的有UIUC的Wen-Mei Hwu,CMU的Onur Mutlu等等,工业界Intel不少核心工程师也出自他的门下。这个讲座主要谈了他对未来的多核处理器的发展的看法,有趣的是他二十年前也预测过现在的处理器,我还专门问了他当时的预测是否靠谱,他说“那我得回去查查看才行”,人非常的Nice。

简单介绍一下关键的几点:

1. 为什么要多核?
It is easier than designing a much better uni-core
It is cheaper than designing a much better uni-core
It was embarrassing to continue making L2 bigger
It was the next obvious step

2. Asymmetric Chip Multiprocessor才是未来
一个chip上既有Large Core,又有Small Core,前者专门用来加速那些诸如Critical Section之类的串行代码。

3. ILP未死
其实还有ILP的性能很多可挖掘的空间,只是多核设计上更经济更简单,所以大家都慢慢转到多核上来了

4. Parallel Programming is NOT Hard
如果从新生就开始进行并行编程的教育,从一开始就thinking in parallel,并行编程就不难,关键是打破Abstraction。

UIUC的Distinguished Lecture Series也有他今年4月在UIUC的讲座,甚至还有video。

Enjoy!

多核编程的难题(二)

刚刚过去的一个月一直都在忙着赶实验赶论文,直到前几天完成一篇短论文的写作才得以抽身来补上这一篇关于多核的曙光的文章。我将分几个方面来阐述一下我对多核上并行编程持乐观态度的原因。

1. 较易并行化的应用
如果一个应用的子任务之间依赖关系比较小,相互独立性强,那么它就具有很好的可并行性。很容易我们就会想到服务端的应用。服务端应用的特征就是为多用户提供相似的服务,因为它本身具有内在的并行性,所以相比那些子任务之间依赖性很强的应用来说,它们是比较适合多核的。这些应用常见的例子有大型数据库、飞机票预订系统、银行交易系统、网络搜索、游戏服务器以及云计算所提供的软件即服务(SaaS)等等。

阅读全文>>

刚刚过去的一个月一直都在忙着赶实验赶论文,直到前几天完成一篇短论文的写作才得以抽身来补上这一篇关于多核的曙光的文章。我将分几个方面来阐述一下我对多核上并行编程持乐观态度的原因。

1. 较易并行化的应用

如果一个应用的子任务之间依赖关系比较小,相互独立性强,那么它就具有很好的可并行性。很容易我们就会想到服务端的应用。服务端应用的特征就是为多用户提供相似的服务,因为它本身具有内在的并行性,所以相比那些子任务之间依赖性很强的应用来说,它们是比较适合多核的。这些应用常见的例子有大型数据库、飞机票预订系统、银行交易系统、网络搜索、游戏服务器以及云计算所提供的软件即服务(SaaS)等等。

另一种大量采用并行化的成功案例就是图像处理了。举个简单的例子,渲染一幅图像这个任务就充满了大量的数据级并行(data-level parallelism):一幅图像是由许许多多的像素组成的,而现在的GPU都有成百个核心,我们可以比较容易的做到让每个GPU核心分别负责渲染图像的一部分,从而快速的完成整个计算任务。虽然现在来讲GPU上面的编程很难,但是它所能提供的性能提升确实非常可观。

还有很火的GPGPU应用(General-purpost computing on GPU),它们在Scientific Computing领域也有不少成功案例,虽然John Carmack就在Twitter上对GPGPU编程的困难性这样评价过:“Hundreds of GPGPU research papers valiantly struggling with graphic API limitations are painfully obsolete with CUDA / OpenCL available.”其实Scientific Computing可以算是多核上的杀手级应用了,典型的例如天气预测、气候模拟等运用,为了得到更精确的结果肯定就需要处理更多的数据,而且是必须在短时间内出结果,要不然你预测后天的天气但是一个礼拜才给你出结果怎么行?这些大数据量的计算任务对性能的需求永远都是非常大的。而且这些应用本身有很多数据级的并行性,再加上这个领域一般都是行业专家和软件工程师的组合,大规模的应用并行计算是很自然的事情。

2. 我们有持乐观态度的理由

为什么我们可以对多核发展持乐观态度?因为第一点,现在整个工业界、学术界都在研究多核,研究怎样简化并行编程、怎样降低功耗、怎样持续提升性能。Intel和Microsoft资助UIUC和UC Berkeley建立了两个重点实验室,其他顶级研究机构对多核的研究也如火如荼,大量最顶尖的人才都在帮助普及并行计算。第二点,Motivation,即“动机”。免费午餐都结束了,想继续提升性能?你只能进行并行编程。不管是客户端应用也好服务器端应用也好,用户对性能的需求肯定是不会停止的。当并行编程成为持续提升性能的唯一选择时,再困难你也得去做对不对?不过大家不用特别担心,对广大的程序员来讲,一项新技术的普及本身就是需要时间的,现在来讲大量帮助程序员进行并行编程的软硬件工具都在处在发展阶段,我们有理由相信并行编程会更容易更大众。

3. 多核的发展趋势

9月初我去参加斯德哥尔摩举办的Multicore Day时听了一位在Intel负责Nehalem的首席工程师的演讲,里面有几点我记忆深刻:
(1)单核的性能仍在提升
虽然整个工业界主题是往多核发展,但是处理器的单线程性能仍然在持续提升,这是由需求决定的。例如Nehalem架构的i7的单线程性能是奔4的5倍,这一需求也在Google在Micro 2010的论文”Brawny cores still beat wimpy cores, most of the time“中得到印证。这篇文章的核心观点就是性能较弱但是功耗较低的”小号“处理器只有在它们的单核性能接近中档的”大号“处理器时才具有足够的竞争力,否则它们羸弱的单核性能会成为Google现有应用中的性能瓶颈。虽然当初整个业界因为单核性能提升太困难而被迫转向更易实施的多核
(2)CPU和GPU的融合趋势
现在业界已经认同GPU比CPU更适合做数据级并行,而且这类应用需求量很大,这种需求就催生了Intel的Larrabee项目。虽然Larrabee流产了,但是它的技术还在,以后迟早会出现在Intel的产品线上。为了追求更高的性能,GPU和CPU结合的方案会是最好的选择,当然,怎样在这样的硬件上编程又是一个很大的难题。
(3)性能与功耗都重要
Intel的工程师一直在努力确保处理器的性能提升的同时它的功耗也一直在稳步下降。为什么说功耗很重要?我们可以举个很简单的例子,笔记本电脑上运行PowerPoint的速度已经很快了,让PowerPoint运行速度快个一两倍其实并不那么重要,但是如果在保证它运行速度的同时还能让笔记本的续航时间提升一些,这就很有意义了。服务器端更不用说了,现在哪个数据中心不把功耗当做头等大事来考虑?

4. 并行编程的普及教育

虽然说传统的应用一直都以串行计算为背景,所以现在来讲大家普遍觉得并行编程很困难。但是我们换个思路看看:如果从大一开始我们就教新生《并行算法》《并行编程导论》呢?如果程序员一开始就接受的是并行编程的教育,并行编程还是困难的吗?其实我们整个世界本身就充满了并行,人可以同时听课和做笔记,同时吃饭和交流,而计算机硬件更是可以并行工作,为什么软件就不可以?算法导论最新的第三版专门添加了一章《多线程算法》,(该书其中一位作者Prof. Charles Leiserson创办的并行编程的公司Cilk Art也已被Intel收购)让我大胆想象一下,整本算法导论通篇都是“并行”的时代还会远吗?

多核编程的难题(一)

最近David Patterson老爷子(就是计算机体系结构–量化方法的作者之一)发表了一篇文章《The trouble with multicore》,文章高屋建瓴的分析了一下多核发展的当前形势,文章开篇就说了一句话“造芯片的家伙们正忙着生产那些大多数程序员不知道如何编程的多核CPU”。这不由的让我想起我跟我导师Per Stenstrom的一次对话,我问他说“现在多核出来了,有一大堆新的难题等着我们去解决,作为研究人员您是否觉得很兴奋呢?”结果他说“其实我还是有点沮丧的,因为我们是被迫转到多核上来的。”

阅读全文>>

最近David Patterson老爷子(就是计算机体系结构–量化方法的作者之一)发表了一篇文章《The trouble with multicore》,文章高屋建瓴的分析了一下多核发展的当前形势,文章开篇就说了一句话“造芯片的家伙们正忙着生产那些大多数程序员不知道如何编程的多核CPU”。这不由的让我想起我跟我导师Per Stenstrom的一次对话,我问他说“现在多核出来了,有一大堆新的难题等着我们去解决,作为研究人员您是否觉得很兴奋呢?”结果他说“其实我还是有点沮丧的,因为我们是被迫转到多核上来的。”

其实这就道出了多核发展中的一个关键:造硬件的没办法在单核上继续像以前那样容易地提升性能了(有兴趣的朋友可以查下“Power Wall”),为了利用更多的晶体管提高性能,只好走多核这条路,但是在他们选择走这条路的时候,所有人都不知道该如何在多核平台上有效的进行编程,David Patterson管这个叫“Hail Mary”,简单翻译过来就是“让我们多核吧,但是该咋进行多核编程就祈祷奇迹的发生吧!”

好吧,为什么多核编程很困难?一个形象的例子就是把编程比作写书,理论上10个作者同时写一本书应该会比一个人写快10倍。但是他们首先要把任务均匀的分成10份,否则任务最多的那个作者会拖后腿肯定就快不了10倍了。但是呢光这个还不够,如果这个故事中的某一部分必须要在其他部分写完之后才能写,这种顺序上的依赖关系也会拖慢速度;而且10个作者的故事情节还得一致,那么他们肯定少不了沟通啊,这又慢了一点。这就是三个多核编程的最大挑战:“load balancing(负载均衡)”、“sequential dependency(顺序依赖关系)”和“synchronization(同步)”。

难道就没有人尝试着解决这个问题吗?有啊!从60年代开始,一堆一堆的天才们尝试着创造新的编程语言好让并行编程更加美好:APL,Id,Linda,Occam,SISAL等等,他们中有的确实让并行编程更加容易了,但是没有一个人能成功的让他们向传统的串行编程语言一样兼具性能、效率和灵活性,更没有像C/C++、Java这样主要为串行编程设计的语言一样流行。我记得有人问过“Java的并发包挺好用的啊,是不是足够解决多核编程的问题了呢?”,我觉得不然。在语言上进行并行编程的扩展确实是有效的办法,但是它却不能从根本上解决并行编程困难的问题。最根本的原因是这些语言并不是天生为并发而设计的,这就决定了所有的库都只能给你提供并行编程最原始的工具,但是对程序员来说并行编程却并没有因为有了这些库就变得更容易了,你还是得面临死锁dead lock、数据竞跑data race、伪共享false sharing、锁竞争lock contention等种种问题。

讲到这我就想起Erlang了,它就是一种天生为并发设计的语言。它的并发模型核心是基于消息传递机制的轻量级进程,进程之间不共享内存。这样的模型好处就在于每个进程是相互独立的,要通信就发消息好了,最大程度上减少了进程间的依赖关系,从而能提高整体性能,而且核越多跑的越快。但是我们要考虑到Erlang最初是Ericsson为电信系统设计的语言,由它编写的程序的目标就是为了提高系统的throughput以便为更多的用户提供服务,这也是大部分服务器端程序的目标。它们的共同特征是每个用户的请求大部分情况下都是彼此独立的,所以多核对这样的高并发应用来讲其实是有点天生一对的感觉。但是对于传统的客户端程序来讲,latency才是它们的首要目标。例如大型的商业软件,它所希望的是完成一个任务的速度能够更快,或者单位时间内能处理更多的数据。

另一个解决并行编程难的思路就是设计更易进行并行编程的硬件,现在最火的Transactional Memory(事务性内存)就是其中的典范。但是现在它们还只处于研究阶段,里面有一大堆的问题尚待解决,最主要的就是性能还不足以到商用阶段。

还有的人尝试过用编译器自动并行化,但是多年的研究表明纯粹让编译器来给你进行自动并行化是完全走不通了。它能在一定程度上提升程序的性能,但是非常有限,而且随着核数的增加它对性能的提升会更加有限。

那么多核时代的曙光在哪里呢?请看我下一篇文章

二进制的二三事

二进制是计算机的自然语言,逻辑门中神奇的0/1组合犹如那起起伏伏的“滴答”之声构成了曼妙的电子世界。不仅如此,二进制中的0和1往往也是我们解决实际问题的利器。

阅读全文>>

二进制是计算机的自然语言,逻辑门中神奇的0/1组合犹如那起起伏伏的“滴答”之声构成了曼妙的电子世界。不仅如此,二进制中的0和1往往也是我们解决实际问题的利器。

Task1:求一个固定长度集合所有子集

最直观的方法就是穷举:对集合中的每个元素来说它要么在当前子集中,要么不在当前子集中,以此依次类推穷举出所有可能的值。如果我们用0表示该元素在当前子集中,用1表示该元素不在当前子集中,我们就可以用一串0/1序列来表示当前的子集。

例如集合{a, b, c, d, e}中的子集{a, b, c}可以用“11100”来表示,子集{c, d, e}可以用“00111”来表示,空子集{}可以用“00000”来表示。

那么对任意固定长度的集合a[n],我们可以从a[0]开始穷举a[0]在子集中和a[0]不在子集中两种情况,再依次类推从a[1]开始一直穷举到a[n-1]为止。于是我们可以得到一个很直观的递归程序:

void sub_sets_recu(int index, int length, char *array, char *bits)
{
	int j = 0;

	if (index >= length) {
		for (j = 0; j < length; j++) {
			if (bits[j] == '1') {
				printf("%c", array[j]);
			}
		}
		printf("\n");
	}
	else {
		bits[index] = '1';
		sub_sets_recu(index+1, length, array, bits);
		bits[index] = '0';
		sub_sets_recu(index+1, length, array, bits);
	}
}

但是递归版本的缺点就是需要一个额外的数组bits来存储0/1序列,那么有没有办法改进呢?我们可以先试试把递归改成迭代的方式会不会有效果。

迭代的关键就在于明白你究竟要做哪些计算步骤,为此我们可以先画出递归函数的Execution Tree来看看:

—                       ○
|                     0/  \1
|                     ○    ○
|                  0/  \1   .
|                  ○    ○     .
n层             .       .      .
|                .         .
|               .           .
|             /  \        /  \
|           ○   ○     ○    ○

上图中,第i层的值为1的边来表示a[i]在子集中,值为0的边表示a[i]不在子集中,那么从根节点到所有叶子节点所经过的边的组合就是所有可能的子集组合,例如从根节点到最左叶子节点的组合为“00000”,即空子集。根据完全二叉树的性质,第n层有2^n个节点,所以共有2^n个不同的子集。既然所有的解都已经存储在这颗二叉树中,那么我们自然就可以依此构建一个遍历所有路径的迭代算法。

思路是有了,但是实际编码中我们需要用到一个跟二进制编码相关的trick了。我们知道任意一个十进制的数是可以用二进制来表示的,反过来我们也可以用十进制来表示二进制啊,“用二进制来思考”其实就是这个trick的关键。既然我们的解是“00000”~“11111”,那么它们自然可以用十进制的0~31来表示。很自然的我们就可以想到如果我们依次遍历0~31这些数,根据它们二进制值中每一位的值是0还是1即可确定当前元素是否在子集中。关于二进制的位操作等相关知识Matrix67的blog[1]有一个系列写的很不错,在此就不再赘述。

void sub_sets_iter(int length, char *array)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < (1<<length); i++) {
		for (j = 0; j < length; j++) {
			if ((i & (1<<j)) != 0) {
				printf("%c", array[j]);
			}
		}
		printf("\n");
	}
}

再加上测试用的main函数:

int main()
{
	char a[5] = {'a','b','c','d','e'};
	char b[5];
	int i;

#ifdef USE_RECU
	for (i = 0; i < 10000000; i++) {
		sub_sets_recu(0, 5, a, b);
	}
#else
	for (i = 0; i < 10000000; i++) {
		sub_sets_iter(5, a);
	}
#endif
	return 0;
}

好,代码全写完了,当然应该比试比试两个算法孰优孰劣。测试平台是:cygwin + gcc 3.4.4 + Core2 Duo T7300@2.0GHz

在测试时已经把两个算法中的printf给注释掉了,只比拼速度。先把gcc的优化设成-O0看看:

$ time ./recu.exe

real    0m8.847s
user    0m8.811s
sys     0m0.046s

$ time ./iter.exe

real    0m5.093s
user    0m4.999s
sys     0m0.046s

再看看gcc -O3的结果:

$ time ./recu_o3.exe

real    0m8.285s
user    0m8.234s
sys     0m0.031s

$ time ./iter_o3.exe

real    0m1.887s
user    0m1.796s
sys     0m0.031s

结果显示迭代算法优于递归算法。感兴趣的朋友可以反汇编一下编译器优化后的代码,看看为什么迭代算法优化后能快那么多。关于递归与迭代已经有很多分析了,简单说来递归更加直观易懂,但是栈的开销比较大;迭代的算法不容易一开始就想出来,但是一般来说效率更高。从编译器的角度来讲,部分的编译器能把相对简单的递归算法转化成迭代算法,因为递归的算法对编译器来说是更友好的算法,更易于在此基础上做更多的优化。从体系结构的角度来讲,递归算法更易于发挥CPU流水线的特点让多步运算同时执行,而某些特定的架构,例如GPU就没有对递归提供有效的硬件支持,因为栈空间是一个大问题。

Task2:小白鼠试毒药问题

实验室里有1000个一模一样的瓶子,但是其中的一瓶有毒。可以用实验室的小白鼠来测试哪一瓶是毒药。如果小白鼠喝掉毒药的话,会在一个星期的时候死去,其他瓶子里的药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药?

这个问题关键是跳出思维,并不是说瓶子和小白鼠必须一一对应,然后我们用1000只小白鼠,每只各试一瓶药水,等一个礼拜然后出结果。其实我们仔细想想,小白鼠试毒只有两种结果,非“死”即“生”,又是一个0/1状态。很显然我们可以再次构建一个0/1组成的二叉树,由此即可表示不同的试毒结果。假设我们需要n个小白鼠,那么2^n-1应大于等于1000(因为有1000种可能的结果,减一是指要除去小白鼠全部不死的情况 — 多谢danqi指正),那么最小的n就是10了。

总结

解决此类问题的关键在于找到能用0/1表示的状态,然后想办法用0/1组成的二进制数来表示不同的结果,从而达到节省存储空间,提高解题效率的目的。

二进制真是神奇,文章的最后附一张0和1构成的Fibonacci数列(来自[2]):

相关文献

[1] 位运算讲解系列文章
[2] Fibonacci数列转二进制图形的惊异发现

转载请注明来自www.parallellabs.com

聊一聊瑞典的程序员

在瑞典这个发达国家,IT企业的基本工资都相差不大。认识的一位Ericsson的员工(入职刚一年)工资是税前29K SEK/M(~30%的税率),资格老一点的员工能有40K~50K SEK/M。不过工资高的人交的税也会相应的增加(40%~50%),所以有一个流行的说法就是大学教授和码头工人的税后工资差不多。小公司的薪资也很不错,而且还有不同程度的股份。

阅读全文>>

在瑞典这个发达国家,IT企业的基本工资都相差不大。认识的一位Ericsson的员工(入职刚一年)工资是税前29K SEK/M(~30%的税率),资格老一点的员工能有40K~50K SEK/M。不过工资高的人交的税也会相应的增加(40%~50%),所以有一个流行的说法就是大学教授和码头工人的税后工资差不多。小公司的薪资也很不错,而且还有不同程度的股份。

瑞典的大学都是免学费的(明年开始向外国学生收费),由政府承担教育经费。瑞典的教育、医疗大都是免费的,它们需要的大量资金都由政府的税收收入来支持,取之于民用之于民。大学生的生活费大都是向政府申请的贷款(生活费大约7K SEK/M,父母大都不支持他们的生活费),所以很多我身边的瑞典朋友早早就开始在企业兼职来补贴生活费,这样在他们研究生毕业的时候很多人都已经有了几年的兼职经验。

像瑞典这样的欧美发达国家,很多计算机专业的大学生很早就开始学习编程了,而且还非常普遍。他们在高中的时候就会开设编程相关的课程,更早一点的十二、三岁就开始学习编程了。我的一个瑞典朋友在高中的最后一年用汇编写了一个40K行的操作系统!另一个我认识的前辈在高中毕业之后就去了瑞典的一家游戏公司做开发,工作了七八年之后又回学校读本科,但是没读完又加入了另一家创业公司。

瑞典的实习工资也很不错。Volvo的实习生能给到25K SEK/M,而其他公司的实习生大都能给到17K~20K SEK/M。另一种实习的方式是去做毕业设计。Ericsson的Master Thesis为期6个月,Offer的基本工资是35K,奖金根据最后的表现最多给15K,所以税前最多能拿50K,扣掉30%的税后能拿到30K左右。

高工资,高税收,高福利,大家收入都差不多,所以人们都很“安居乐业”。总而言之,我相信瑞典人真的不富(贫富差距不大),但是也没啥压力。这样的环境很容易出两种人,一种是真正爱搞研究搞创新的人,他们能弄出一些Great Idea开创一片天地;另一种就是在公司养老的人,能完成工作,但也就仅限于此。

多线程程序中操作的原子性

原子操作就是不可再分的操作。在多线程程序中原子操作是一个非常重要的概念,它常常用来实现一些同步机制,同时也是一些常见的多线程Bug的源头。本文主要讨论了三个问题:1. 多线程程序中对变量的读写操作是否是原子的?2. 多线程程序中对Bit field(位域)的读写操作是否是线程安全的?3. 程序员该如何使用原子操作?

阅读全文>>

0. 背景

原子操作就是不可再分的操作。在多线程程序中原子操作是一个非常重要的概念,它常常用来实现一些同步机制,同时也是一些常见的多线程Bug的源头。本文主要讨论了三个问题:1. 多线程程序中对变量的读写操作是否是原子的?2. 多线程程序中对Bit field(位域)的读写操作是否是线程安全的?3. 程序员该如何使用原子操作?

1. 多线程环境下对变量的读写操作是否是原子的?

我们先从一道很热门的百度笔试题讲起。很多人讲不清楚其背后的原理,下面我们就来对它进行一下剖析(其实这个题目有点歧义,后面我们会讲到):

以下多线程对int型变量x的操作,哪几个需要进行同步:( )
A. x=y; B. x++; C. ++x; D. x=1;

要彻底理解这个问题,我们首先需要从硬件讲起。以常见的X86 CPU来说,根据Intel的参考手册,它基于以下三种机制保证了多核中加锁的原子操作(8.1节):
(1)Guaranteed atomic operations (注:8.1.1节有详细介绍)
(2)Bus locking, using the LOCK# signal and the LOCK instruction prefix
(3)Cache coherency protocols that ensure that atomic operations can be carried out on cached data structures (cache lock); this mechanism is present in the Pentium 4, Intel Xeon, and P6 family processors

这三个机制相互独立,相辅相承。简单的理解起来就是
(1)一些基本的内存读写操作是本身已经被硬件提供了原子性保证(例如读写单个字节的操作);
(2)一些需要保证原子性但是没有被第(1)条机制提供支持的操作(例如read-modify-write)可以通过使用”LOCK#”来锁定总线,从而保证操作的原子性
(3)因为很多内存数据是已经存放在L1/L2 cache中了,对这些数据的原子操作只需要与本地的cache打交道,而不需要与总线打交道,所以CPU就提供了cache coherency机制来保证其它的那些也cache了这些数据的processor能读到最新的值(关于cache coherency可以参加我的一篇博文)。

那么CPU对哪些(1)中的基本的操作提供了原子性支持呢?根据Intel手册8.1.1节的介绍:

从Intel486 processor开始,以下的基本内存操作是原子的:
• Reading or writing a byte(一个字节的读写)
• Reading or writing a word aligned on a 16-bit boundary(对齐到16位边界的字的读写)
• Reading or writing a doubleword aligned on a 32-bit boundary(对齐到32位边界的双字的读写)

从Pentium processor开始,除了之前支持的原子操作外又新增了以下原子操作:
• Reading or writing a quadword aligned on a 64-bit boundary(对齐到64位边界的四字的读写)
• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus(未缓存且在32位数据总线范围之内的内存地址的访问)

从P6 family processors开始,除了之前支持的原子操作又新增了以下原子操作:
• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line(对单个cache line中缓存地址的未对齐的16/32/64位访问)

那么哪些操作是非原子的呢?
Accesses to cacheable memory that are split across bus widths, cache lines, and
page boundaries are not guaranteed to be atomic by the Intel Core 2 Duo, Intel®
Atom™, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, P6 family, Pentium, and
Intel486 processors.(说点简单点,那些被总线带宽、cache line以及page大小给分隔开了的内存地址的访问不是原子的,你如果想保证这些操作是原子的,你就得求助于机制(2),对总线发出相应的控制信号才行)。

需要注意的是尽管从P6 family开始对一些非对齐的读写操作已经提供了原子性保障,但是非对齐访问是非常影响性能的,需要尽量避免。当然了,对于一般的程序员来说不需要太担心这个,因为大部分编译器会自动帮你完成内存对齐。

回到最开始那个笔试题。我们先反汇编一下看看它们到底执行了什么操作:

x = y;
mov eax,dword ptr [y]
mov dword ptr [x],eax

x++;
mov eax,dword ptr [x]
add eax,1
mov dword ptr [x],eax

++x;
mov eax,dword ptr [x]
add eax,1
mov dword ptr [x],eax

x = 1;
mov dword ptr [x],1

(1)很显然,x=1是原子操作。
因为x是int类型,32位CPU上int占32位,在X86上由硬件直接提供了原子性支持。实际上不管有多少个线程同时执行类似x=1这样的赋值语句,x的值最终还是被赋的值(而不会出现例如某个线程只更新了x的低16位然后被阻塞,另一个线程紧接着又更新了x的低24位然后又被阻塞,从而出现x的值被损坏了的情况)。

(2)再来看x++和++x。
其实类似x++, x+=2, ++x这样的操作在多线程环境下是需要同步的。因为X86会按三条指令的形式来处理这种语句:从内存中读x的值到寄存器中,对寄存器加1,再把新值写回x所处的内存地址(见上面的反汇编代码)。

例如有两个线程,它们按照如下顺序执行(注意读x和写回x是原子操作,两个线程不能同时执行):

time    Thread 1         Thread 2
0      load eax, x
1                            load eax, x
2      add eax, 1        add eax, 1
3      store x, eax
4                            store x, eax

我们会发现最终x的值会是1而不是2,因为Thread 1的结果被覆盖掉了。这种情况下我们就需要对x++这样的操作加锁(例如Pthread中的mutex)以保证同步,或者使用一些提供了atomic operations的库(例如Windows API中的atomic库,Linux内核中的atomic.h,Java concurrent库中的Atomic Integer,C++0x中即将支持的atomic_int等等,这些库会利用CPU提供的硬件机制做一层封装,提供一些保证了原子性的API)。

(3)最后来看看x=y。
在X86上它包含两个操作:读取y至寄存器,再把该值写入x。读y的值这个操作本身是原子的,把值写入x也是原子的,但是两者合起来是不是原子操作呢?我个人认为x=y不是原子操作,因为它不是不可再分的操作。但是它需要不需要同步呢?其实问题的关键在于程序的上下文。

例如有两个线程,线程1要执行{y = 1; x = y;},线程2要执行{y = 2; y = 3;},假设它们按如下时间顺序执行:

time    Thread 1        Thread 2
0        store y, 1
1                            store y, 2
2        load eax, y
3                            store y, 3
4        store x, eax

那么最终线程1中x的值为2,而不是它原本想要的1。我们需要加上相应的同步语句确保y = 2不会在线程1的两条语句之间发生。y = 3那条语句尽管在load y和store x之间执行,但是却不影响x=y这条语句本身的语义。所以你可以说x=y需要同步,也可以说x=y不需要同步,看你怎么理解题意了。x=1是否需要同步也是一样的道理,虽然它本身是原子操作,但是如果有另一个线程要读x=1之后的值,那肯定也需要同步,否则另一个线程读到的就是x的旧值而不是1了。

2. 对Bit field(位域)的读写操作是否是线程安全的?

Bit field常用来高效的存储有限位数的变量,多用于内核/底层开发中。一般来说,对同一个结构体内的不同bit成员的多线程访问是无法保证线程安全的。

例如Wikipedia中的如下例子:

struct foo {
    int flag : 1;
    int counter : 15;
};

struct foo my_foo;

/* ... */

/* in thread 1 */

pthread_mutex_lock(&my_mutex_for_flag);
my_foo.flag = !my_foo.flag;
pthread_mutex_unlock(&my_mutex_for_flag);

/* in thread 2 */

pthread_mutex_lock(&my_mutex_for_counter);
++my_foo.counter;
pthread_mutex_unlock(&my_mutex_for_counter);

两个线程分别对my_foo.flag和my_foo.counter进行读写操作,但是即使有上面的加锁方式仍然不能保证它是线程安全的。原因在于不同的成员在内存中的具体排列方式“跟Byte Order、Bit Order、对齐等问题都有关,不同的平台和编译器可能会排列得很不一样,要编写可移植的代码就不能假定Bit-field是按某一种固定方式排列的”[3]。而且一般来讲CPU对内存操作的最小单位是word(X86的word是16bits),而不是1bit。这就是说,如果my_foo.flag和my_foo.counter存储在同一个word里,CPU在读写任何一个bit member的时候会同时把两个值一起读进寄存器,从而造成读写冲突。这个例子正确的处理方式是用一个mutex同时保护my_foo.flag和my_foo.counter,这样才能确保读写是线程安全的。

C++0x草案中对bit field是这样定义的:
连续的多个非0bit的bit fields是属于同一个memory location的;长度为0bit的bit field会把占单独的一个memory location。对同一个memory location的读写不是线程安全的;对不同memory location的读写是线程安全的。
例如在下图的例子中bf1和bf2是同一个memory location,bf3是一个单独的memory location,bf4是一个单独的memory location:
bit field

这里有一个因为Bit field不是线程安全所导致的一个Linux内核中的Bug

引用一下Pongba的总结

所以,如果你的多个bitfields是连续的,同时又想要无冲突的读取它们,有两种做法,一是在中间用0大小bitfield隔开,但这种做法实际上就消除了bitfield的节省内存的初衷,因为为了使它们不冲突,至少被隔开的两个bitfield肯定不可能共享byte了。另一种做法当然就是用锁了。

3. 程序员该怎么用Atomic操作?

一般情况下程序员不需要跟CPU提供的原子操作直接打交道,所以只需要选择语言或者平台提供的atomic API即可。而且使用封装好了的API还有一个好处是它们常常还提供了诸如compare_and_swap,fetch_and_add这样既有读又有写的较复杂操作的封装。

常见的API如下:

Windows上InterlockedXXXX的API
GNU/Linux上linux kernel中atomic_32.h
GCC中的Atomic Builtins (__sync_fetch_and_add()等)
Java中的java.util.concurrent.atomic
C++0x中的atomic operation
Intel TBB中的atomic operation

4. 参考文献:

[1] 关于变量操作的原子性(atomicity)FAQ
[2] http://en.wikipedia.org/wiki/Atomic_operation
[3] 关于内存对齐、bit field等 –《Linux C编程一站式学习》
[4] Do you need mutex to protect an ‘int’?
[5] C++ Concurrency in Action
[6] Multithreaded simple data type access and atomic variables
[6] http://www.newsmth.net/bbscon.php?bid=335&id=236629
[7]
http://www.newsmth.net/bbscon.php?bid=335&id=209239
[8]
http://www.newsmth.net/bbscon.php?bid=335&id=186723
转载请注明来自parallellabs.com

第三次软件危机

The major cause of the software crisis is that the machines have become several orders of magnitude more powerful! To put it quite bluntly: as long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem, and now we have gigantic computers, programming has become an equally gigantic problem.

造成软件危机的主要原因是因为计算机的计算能力正在呈指数级地增长!说的简单些:在没有计算机的时候,编程根本就不是一个问题;当一些计算能力较弱的计算机出现时,编程成了一个中等难度的问题,而现在,我们拥有了计算能力超绝的计算机,编程就变为了一个同样复杂的问题。

– Edsger Dijkstra, 1972年图灵奖获奖感言

阅读全文>>

The major cause of the software crisis is that the machines have become several orders of magnitude more powerful! To put it quite bluntly: as long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem, and now we have gigantic computers, programming has become an equally gigantic problem.

造成软件危机的主要原因是因为计算机的计算能力正在呈指数级地增长!说的简单些:在没有计算机的时候,编程根本就不是一个问题;当一些计算能力较弱的计算机出现时,编程成了一个中等难度的问题,而现在,我们拥有了计算能力超绝的计算机,编程就变为了一个同样复杂的问题。

– Edsger Dijkstra, 1972年图灵奖获奖感言

第一次软件危机 (60年代~70年代)

这个时期主要的软件开发方式是使用机器语言或者汇编语言在特定的机器上进行软件的设计与编写。此时的软件规模较小,也不需要使用系统化的软件开发方法,基本上是个人设计编码、个人操作使用的模式。这个时代的程序一个典型特征就是依赖特定的机器,程序员必须根据所使用的计算机的硬件特性编写特定的程序。

然而从60年代中期开始,大容量、高速度计算机问世,程序设计的复杂度也随之增长。1968 年北大西洋公约组织的计算机科学家在联邦德国召开国际会议,第一次讨论软件危机问题,并正式提出“软件工程”一词,从此一门新兴的工程学科——软件工程学——为研究和克服软件危机应运而生,“软件危机”的概念也是在那次会议上由F. L. Bauer提出的。

当时业界最迫切的需求是需要在不损失性能的前提下获得更好的“抽象性”和“可移植性”。此时,比汇编和机器语言更高级的语言相聚诞生,典型的代表莫过于C语言(1972年)。C语言让程序员能让程序员编写的代码在没有或只有较少机器相关性的同时又有不输于汇编语言的性能,而且丰富的语言特性也使得编程难度大大降低,成功的解决了“抽象性”和“可移植性”的问题。

第二次软件危机(80年代~90年代)

这次危机可以归因于软件复杂性的进一步增长。这个时候的大规模软件常常由数百万行代码组成,有数以百计的程序员参与其中,怎样高效、可靠的构造和维护这样规模的软件成为了一个新的难题。著名的《人月神话》中提及,IBM公司开发的OS/360系统共有4000多个模块,约100万条指令,投入5000人年,耗资数亿美元,结果还是延期交付。在交付使用后的系统中仍发现大量(2000个以上)的错误。

这时候人们典型需求的是更好的“可组合性”(Composability)、“可延展性”(Malleability)以及“可维护性”(Maintainability)。程序的性能已经不是一个大问题了,因为摩尔定律能帮你搞定它(70年代编写的C程序仍然能在现在的计算机上运行,而且它还更快!)。为了解决这次危机,面向对象的编程语言(C++、C#、Java等)诞生了,更好的软件工程方法(设计模式、重构、测试、需求分析等等)诞生了,而程序员们也越来越不需要知道硬件是怎么工作的了。软件和硬件的界限越来越牢固,Java编写的代码能在任何JVM支持的平台上运行,程序员也非常乐于享受这样的便利。

第三次软件危机(2005年至今)

兄弟们,“免费的午餐已经结束了”。
摩尔定律在串行机器上宣告失效,多核时代正式来临!

这个时候怎样在多核平台上仍然能保持性能的持续增长就成为了这一次软件危机的核心。并行编程给我们带来了许许多多新的技术难题,现阶段想要高效的利用这些多核平台以获得更好的性能,就必须对计算机的硬件有较深入的理解,而广大程序员却更喜欢能有一些更加便利的编程模型(也许是一门新的语言、也许是新的编程模型)来简单高效地进行并行编程。我们正处在这次危机的开端,前路满是荆棘。但是只要有问题,就会有机会。多核时代,你们的机会在哪里呢?

实施并行编程的五大障碍

近期看见一篇来自Intel的很有意思的分析文章,作者提到在他向45名与会的各公司程序员/开发经理/战略师提问“什么是实施并行编程的最大障碍”时,下面五个因素被提及的次数最多:遗留代码(legacy code)、教育(education)、工具(tools)、对众核趋势的恐惧(fear of many cores)以及可维护性(maintainability)。文章虽然是一篇Intel Parallel Studio的软文,但是其中提及的这五大障碍却非常值得讨论,下面是我对这五大障碍的一些粗浅看法,希望能起到一个抛砖引玉的作用,欢迎大家给出你们的看法。

阅读全文>>

近期看见一篇来自Intel的很有意思的分析文章,作者提到在他向45名与会的各公司程序员/开发经理/战略师提问“什么是实施并行编程的最大障碍”时,下面五个因素被提及的次数最多:遗留代码(legacy code)、教育(education)、工具(tools)、对众核趋势的恐惧(fear of many cores)以及可维护性(maintainability)。文章虽然是一篇Intel Parallel Studio的软文,但是其中提及的这五大障碍却非常值得讨论,下面是我对这五大障碍的一些粗浅看法,希望能起到一个抛砖引玉的作用,欢迎大家给出你们的看法。

1. 遗留代码

众所周知,怎样把公司的那些遗留代码给并行化是一件非常困难的事情。100K~1000K的代码量都非常正常,而并行编程本身又是非常容易出错的,一大堆诸如data race, dependency, non-deterministic, memory consistency, dead lock, serialization bottleneck, thread safe等的问题随便哪一个拉出来都让人头大,更别说要高效可靠的并行化这些庞大的遗留代码了。更困难的是很多遗留代码还有编写者已经离职,文档注释不全等问题,这无疑是雪上加霜。从成本上来讲,如果能通过一些优秀的编译器(例如Intel的ICC)自动并行化一些遗留代码无疑是最省钱的,但是这种方法最大的缺陷就在于像Intel ICC这种自动型编译器能自动并行化的代码非常少,从而导致它能提供的性能优化非常有限,而且就算是真正能获得speedup的代码也有很多约束条件(例如loop的循环之间没有dependence,并且该loop应该是一个程序热点)。所以目前的现状就是大量的遗留代码并不能有效的被并行化,从商业的角度上来讲,如果能有一种解决方案能在短时间内快速可靠的通过实施并行化让遗留代码在多核平台上获得10%~30%的性能提升,那么它就已经能为公司节省大量成本了。

2. 教育

第二大的障碍可能就是程序员缺乏并行编程方面的教育了。其实并行编程已经有二三十年的历史,不过在多核CPU出现之前那些并行编程都是“专家”们的玩具。那时候的并行编程大都是跑在集群、大型机或者服务器上,通过MPI(message passing interface)或者SMP(对称多处理器,即一个主板上有多个单核CPU,属于shared memory model)来完成并行计算。Pthread标准是1995年建立的,之后出来了Windows版的Win32 thread,后来又出来了“编译指导”、面向data parallel模型的OpenMP(OpenMP 3.0加入了task parallel支持),task parallel的鼻祖Cilk,Intel的Intel Thread Building Block(task parallel),Java 1.5开始对多线程提供较好的支持(加入了Java Memory Model),近几年随着GPU的发展,Nvidia又开始搞CUDA(data-parallel),Apple一看不对,并行编程以后是主流啊,我得插一手,于是自己撑旗弄了个针对CPU和GPU混合编程的OpenCL,微软一看也坐不住了也要随着Visual Studio2010开始搞C#的并行库,马上C++0x也要加入多线程支持,甚至连老古董Erlang也因为天生支持并行被重新热炒,总之随着摩尔定律在串行世界的失效,整个业界都开始被迫往并行编程方向发展。

可是对程序员来说呢是什么情况呢?我们现在所接受的教育大都还是串行世界的那些算法和数据结构,高德纳在一篇访谈里说“在我看来,这种现象或多或少是由于硬件设计者已经无计可施了导致的,他们将Moore定律失效的责任推脱给软件开发者,而他们给我们的机器只是在某些指标上运行得更快了而已。如果多线程的想法被证明是失败的,我一点都不会感到惊讶……你听说过有多少程序员对这种未来一片光明的机器抱有强烈的兴趣?我几乎没有听说过,除了他们的诉苦。尽管我们学院那些搞硬件的家伙一直想让我相信我是错的”,可见硬件发展被迫向多核转移直接导致程序员们免费的午餐已经结束了。那么程序员现在受到良好的并行编程教育了吗?很显然,现在随便问一个普通的程序员:“你觉得并行编程容易么?”,十有八九会说“我觉得很难”。前一阵有人讨论服务器编程用多线程好还是多进程好?其实根本原因就在于哪怕多线程有性能优势,可是isolation的多进程模式能在programming productivity和performance之间找到比较好的折衷,所以国内很有服务器开发者都选择了多进程(例如云风)。从大趋势上来讲,不管是研究体系机构的,还是写OS/Compiler的,还是定义编程语言的,现在都在积极努力的为广大的程序员提供一个更容易使用的并行编程模型,Intel这几年不也在搞多核培训么,这都是好现象,但是,离真正的全民并行编程时代还有相当长的路要走。近几年的IT技术热门书单里面很少有并行编程的书籍就是个很好的写照。

3. 工具

工欲善其事,必先利其器。那么现阶段我们能用的,并且好用的并行编程工具有多少呢(欢迎大家补充)?

(1) IDE: Intel Parallel Studio,微软马上出来的VS2010算一个,Sun的Sun Studio(不知道它的未来如何,但是它本来就很小众),Nvidia的CUDA平台什么的就先不算了
(2) Compiler: Intel的ICC(能自动并行化一些代码),Nema Labs的FASThread(一套可以快速可靠的指导程序员实施并行化的解决方案,特别适合将遗留代码并行化)
(3) Performance Tuning: Intel Vtune Analyzer(综合性能分析),Thread profiler,Acumem的Thread Spotter(针对多核Cache的性能分析和优化)
(4) Debugging: Petra的Jinx

总体上我个人觉得它们对程序员来说确实有用,但是前提条件是你要会用。这其实又跟第二点“教育”有很大关系了。

4. 对众核的恐惧

现在我们看到4核已经非常普遍了,等过几年那可就是8核,16核,32核了。怎样确保你的代码在核数倍增的趋势下仍能有很好的性能,很好的可伸缩性?这真的是个问题。我现在所做的研究就是多线程程序中锁竞争的性能分析,目的就是为了帮助程序员更好的解决由锁竞争造成的性能瓶颈。实际上,为了得到很好的可伸缩性,程序员需要往往需要使用并行友好的数据结构(例如concurrent hash map),使用细粒度的锁甚至无锁编程,设计data parallel的算法,性能调优(例如典型的false sharing问题)等等等等,这其中每一项都是不小的挑战。我曾经翻译过的一篇文章对设计多线程程序提供了一些有用的建议

5. 可维护性

毫无疑问,我们希望并行代码能够与现存的runtime系统、build系统以及其他现有代码一起正确的工作,我们更希望这些并行代码易于理解、便于维护并且有较长的生命周期。可是现阶段真正掌握并行编程的程序员少之又少,而且并行编程又是这么困难,哪怕你对这些并行代码只是做一些小小的改动都很有可能导致新的bug,新的性能瓶颈,那真的是一件非常痛苦的事情。

为什么程序员需要关心顺序一致性(Sequential Consistency)而不是Cache一致性(Cache Coherence?)

本文所讨论的计算机模型是Shared Memory Multiprocessor,即我们现在常见的共享内存的多核CPU。本文适合的对象是想用C++或者Java进行多线程编程的程序员。本文主要包括对Sequential Consistency和Cache Coherence的概念性介绍并给出了一些相关例子,目的是帮助程序员明白为什么需要在并行编程时关注Sequential Consistency。

阅读全文>>

最后一次修改:2010年11月11日

本文所讨论的计算机模型是Shared Memory Multiprocessor,即我们现在常见的共享内存的多核CPU。本文适合的对象是想用C++或者Java进行多线程编程的程序员。本文主要包括对Sequential Consistency和Cache Coherence的概念性介绍并给出了一些相关例子,目的是帮助程序员明白为什么需要在并行编程时关注Sequential Consistency。

Sequential Consistency(下文简称SC)是Java内存模型和即将到来的C++0x内存模型的一个关键概念,它是一个最直观最易理解的多线程程序执行顺序的模型。Cache Coherence(下文简称CC)是多核CPU在硬件中已经实现的一种机制,简单的说,它确保了对在多核CPU的Cache中一个地址的读操作一定会返回那个地址最新的(被写入)的值。

那么为什么程序员需要关心SC呢?因为现在的硬件和编译器出于性能的考虑会对程序作出违反SC的优化,而这种优化会影响多线程程序的正确性,也就是说你用C++编写的多线程程序可能会得到的不是你想要的错误的运行结果。Java从JDK1.5开始加入SC支持,所以Java程序员在进行多线程编程时需要注意使用Java提供的相关机制来确保你程序的SC。程序员之所以不需要关心CC的细节是因为现在它已经被硬件给自动帮你保证了(不是说程序员完全不需要关心CC,实际上对程序员来说理解CC的大致工作原理也是很有帮助的,典型的如避免多线程程序的伪共享问题,即False Sharing)。

那么什么是SC,什么是CC呢?

1. Sequential Consistency (顺序一致性)

SC的作者Lamport给的严格定义是:
“… the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.”

这个概念初次理解起来拗口,不过不要紧,下面我会给出个很直观的例子帮助理解。

假设我们有两个线程(线程1和线程2)分别运行在两个CPU上,有两个初始值为0的全局共享变量x和y,两个线程分别执行下面两条指令:

初始条件: x = y = 0;

线程 1 线程 2
x = 1; y=1;
r1 = y; r2 = x;

因为多线程程序是交错执行的,所以程序可能有如下几种执行顺序:

Execution 1 Execution 2 Execution 3
x = 1;
r1 = y;
y = 1;
r2 = x;
结果:r1==0 and r2 == 1
y = 1;
r2 = x;
x = 1;
r1 = y;
结果: r1 == 1 and r2 == 0
x = 1;
y = 1;
r1 = y;
r2 = x;
结果: r1 == 1 and r2 == 1

当然上面三种情况并没包括所有可能的执行顺序,但是它们已经包括所有可能出现的结果了,所以我们只举上面三个例子。我们注意到这个程序只可能出现上面三种结果,但是不可能出现r1==0 and r2==0的情况。

SC其实就是规定了两件事情:
(1)每个线程内部的指令都是按照程序规定的顺序(program order)执行的(单个线程的视角)
(2)线程执行的交错顺序可以是任意的,但是所有线程所看见的整个程序的总体执行顺序都是一样的(整个程序的视角)

第一点很容易理解,就是说线程1里面的两条语句一定在该线程中一定是x=1先执行,r1=y后执行。第二点就是说线程1和线程2所看见的整个程序的执行顺序都是一样的,举例子就是假设线程1看见整个程序的执行顺序是我们上面例子中的Execution 1,那么线程2看见的整个程序的执行顺序也是Execution 1,不能是Execution 2或者Execution 3。

有一个更形象点的例子。伸出你的双手,掌心面向你,两个手分别代表两个线程,从食指到小拇指的四根手指头分别代表每个线程要依次执行的四条指令。SC的意思就是说:
(1)对每个手来说,它的四条指令的执行顺序必须是从食指执行到小拇指
(2)你两个手的八条指令(八根手指头)可以在满足(1)的条件下任意交错执行(例如可以是左1,左2,右1,右2,右3,左3,左4,右4,也可以是左1,左2,左3,左4,右1,右2,右3,右4,也可以是右1,右2,右3,左1,左2,右4,左3,左4等等等等)

其实说简单点,SC就是我们最容易理解的那个多线程程序执行顺序的模型。

2. Cache Conherence (缓存一致性)

那么CC是干什么用的呢?这个要详细说的话就复杂了,写一本书绰绰有余。简单来说,我们知道现在的多核CPU的Cache是多层结构,一般每个CPU核心都会有一个私有的L1级和L2级Cache,然后多个CPU核心共享一个L3级缓存,这样的设计是出于提高内存访问性能的考虑。但是这样就有一个问题了,每个CPU核心之间的私有L1,L2级缓存之间需要同步啊。比如说,CPU核心1上的线程A对一个共享变量global_counter进行了加1操作,这个被写入的新值存到CPU核心1的L1缓存里了;此时另一个CPU核心2上的线程B要读global_counter了,但是CPU核心2的L1缓存里的global_counter的值还是旧值,最新被写入的值现在还在CPU核心1上呢!怎么把?这个任务就交给CC来完成了!

CC是Cache之间的一种同步协议,它其实保证的就是对某一个地址的读操作返回的值一定是那个地址的最新值,而这个最新值可能是该线程所处的CPU核心刚刚写进去的那个最新值,也可能是另一个CPU核心上的线程刚刚写进去的最新值。举例来说,上例的Execution 3中,r1 = y是对y进行读操作,该读操作一定会返回在它之前已经执行的那条指令y=1对y写入的最新值。可能程序员会说这个不是显而意见的么?r1肯定是1啊,因为y=1已经执行了。其实这个看似简单的”显而易见“在多核processor的硬件实现上是有很多文章的,因为y=1是在另一个CPU上发生的事情,你怎么确保你这个读操作能立刻读到别的CPU核心刚刚写入的值?不过对程序员来讲你不需要关心CC,因为CPU已经帮你搞定这些事情了,不用担心多核CPU上不同Cache之间的同步的问题了(感兴趣的朋友可以看看体系结构的相关书籍,现在的多核CPU一般是以MESI protocol为原型来实现CC)。总结一下,CC和SC其实是相辅相承的,前者保证对单个地址的读写正确性,后者保证整个程序对多个地址读写的正确性,两者共同保证多线程程序执行的正确性。

3. 为什么要关心SC?

好,回到SC的话题。为什么说程序员需要关心SC?因为现在的CPU和编译器会对代码做各种各样的优化,有时候它们可能会为了优化性能而把程序员在写程序时规定的代码执行顺序(program order)打乱,导致程序执行结果是错误的。

例如编译器可能会做如下优化,即把线程1的两条语序调换执行顺序:
初始条件: x=y=0;

线程 1 线程 2
r1 = y; y=1;
x = 1; r2 = x;

那么这个时候程序如果按如下顺序执行就可能就会出现r1==r2==0这样程序员认为”不正确“的结果:

Execution 4
r1 = y;
y = 1;
r2 = x;
x = 1;

为什么编译器会做这样的优化呢?因为读一个在内存中而不是在cache中的共享变量需要很多周期,所以编译器就”自作聪明“的让读操作先执行,从而隐藏掉一些指令执行的latency,提高程序的性能。实际上这种类似的技术是在单核时代非常普遍的优化方法,但是在进入多核时代后编译器没跟上发展,导致了对多线程程序进行了违反SC的错误优化。为什么编译器很难保证SC?因为对编译器来讲它很难知道多个线程在执行时会按照什么样的交错顺序执行,因为这需要一个整个程序运行时的视角,而只对一份静态的代码做优化的编译器是很难得到这种运行时的上下文的。那么为什么硬件也保证不了呢?因为CPU硬件中的写缓冲区(store buffer)会把要写入memory的值缓存起来,然后当前线程继续往下执行,而这个被缓存的值可能要很晚才会被其他线程“看见”,从而导致多线程程序逻辑出错。其实硬件也提供了一些例如Memory Barrier等解决方案,但是开销是一个比较大的问题,而且很多需要程序员手动添加memory barrier,现在还不能指望CPU或者编译器自动帮你搞定这个问题。(感兴趣的朋友可以在本文的参考文献中发现很多硬件优化造成SC被违反的例子以及Memory Barrier等解决方案)

好了,我们发现为了保证多线程的正确性,我们希望程序能按照SC模型执行;但是SC的对性能的损失太大了,CPU硬件和编译器为了提高性能就必须要做优化啊!为了既保证正确性又保证性能,在经过十几年的研究后一个新的新的模型出炉了:sequential consistency for data race free programs。简单地说这个模型的原理就是对没有data race的程序可以保证它是遵循SC的,这个模型在多线程程序的正确性和性能间找到了一个平衡点。对广大程序员来说,我们依赖高级语言内建的内存模型来帮我们保证多线程程序的正确性。例如,从JDK1.5开始引入的Java内存模型中已经支持data race free的SC了(例如使用volatile关键字,atomic变量等),但是C++程序员就需要等待C++0x中新的内存模型的atomic类型等来帮助保证SC了(因为atomic类型的值具有acquire和release语义,它隐式地调用了memory barrier指令)。什么意思呢?说简单点,就是由程序员用同步原语(例如锁或者atomic的同步变量)来保证你程序是没有data race的,这样CPU和编译器就会保证你程序是按你所想的那样执行的(即SC),是正确的。换句话说,程序员只需要恰当地使用具有acquire和release语义的同步原语标记那些真正需要同步的变量和操作,就等于告诉CPU和编译器你们不要对这些标记出来的操作和变量做违反SC的优化,而其它未被标记的地方你们可以随便优化,这样既保证了正确性又保证了CPU和编译器可以做尽可能多的性能优化。来告诉编译器和CPU这里这里你不能做违反SC的优化,那里那里你不能做违反SC的优化,然后你写的程序就会得到正确的执行结果了。

从根源上来讲,在串行时代,编译器和CPU对代码所进行的乱序执行的优化对程序员都是封装好了的,无痛的,所以程序员不需要关心这些代码在执行时被乱序成什么样子,因为这些都被编译器和CPU封装起来了,你不用担心内部细节,它最终表现出来的行为就是按你想要的那种方式执行的。但是进入多核时代,程序员、编译器、CPU三者之间未能达成一致(例如诸如C/C++之类的编程语言没有引入多线程),所以CPU、编译器就会时不时地给你捣蛋,故作聪明的做一些优化,让你的程序不会按照你想要的方式执行,是错误的。Java作为引入多线程的先驱从1.5开始支持内存模型,等于是帮助程序员达成了与编译器、CPU(以及JVM)之间的契约,程序员只要正确的使用同步原语就可以保证程序最终表现出来的行为跟你所想的一样(即我们最容易理解的SC模型),是正确的。

本文并未详细介绍所有针对SC问题的解决方案(例如X86对SC的支持,Java对它的支持,C++对它的支持等等),如果想了解更多,可以参考本文所指出的参考文献。下一次我会写一篇关于data race free model, weak ordering, x86 memory model等相关概念的文章,敬请期待。

题外话:

并行编程是非常困难的,在多核时代的程序员不能指望硬件和编译器来帮你搞定所有的事情,努力学习多核多线程编程的一些基础知识是很有必要的,至少你应该知道你的程序到底会以什么样的方式被执行。

参考文献:
[1] Hans Boehm: C++ Memory Model
[2] Bill Pugh: The Java Memory Model
[3] Wiki: Cache Coherence
[4] Wiki: Sequential Consistency
[5] The Memory Model of X86 (中文,从硬件角度讲SC问题)
[6] 《C++0x漫谈》系列之:多线程内存模型

八条设计多线程程序的简单规则

前言:最近在看该作者的《The Art of Concurrency》,里面第四章就是上面这篇文章,觉得很实用而且很有共鸣。作者基于在并行编程领域的20多年工作经验总结成上面八条简单的原则,一下子帮我把之前并行编程时的一些认识给理清了,量化了,实在是“居家旅行,并行编程,必备良药”。花了几天时间把它翻译了一下,不知道各位在看了之后是否有些共鸣呢?

阅读全文>>

更新:
[2010.3.6] Scalability翻译从”可扩展性“改成”可伸缩性“.

前言:最近在看该作者的《The Art of Concurrency》,里面第四章就是上面这篇文章,觉得很实用而且很有共鸣。作者基于在并行编程领域的20多年工作经验总结成下面八条简单的原则,一下子帮我把之前并行编程时的一些认识给理清了,量化了,实在是“居家旅行,并行编程,必备良药”。花了几天时间把它翻译了一下,不知道各位在看了之后是否有些共鸣呢?


作者:Clay Breshears
译者:并行实验室 Parallel Labs

在Intel,并行化技术主要有四个步骤:分析,设计与实现,调试以及性能调优。这些步骤用来对一段串行代码进行并行化。尽管这四个步骤中的第一、三、四步都已经有了很多相关文档,但是关于怎样进行设计与实现的却不多。

并行编程更像是一门艺术,而不是一门科学。这里将会给出八条设计多线程程序的简单规则,你可以把他们一一放进你的多线程程序设计百宝箱中。通过参考这些规则,你能写出高质量、高效率的多线程程序。我努力试着将这些规则按照(半)时间顺序组织起来,但是它们之间并没有硬性的先后顺序。就像“别在泳池边奔跑”和“别在浅水区跳水”一样,两个都是好主意,但是后者也能放在前者的前面,反之亦然。

规则一:找到真正不相关的计算任务
如果你将要执行的运算任务相互之间不独立的话,你是不可能将它们并行化的。我可以很容易的举出一些真实世界中相互独立的任务如何为了达成同一个目的而工作的例子。比如说一个DVD出租店,它先把收到的求租电影的订单分给员工们,员工再从存放电影DVD的地方根据订单找到影片拷贝。当一个员工取出一张古典音乐喜剧的拷贝时,他并不影响另一个寻找最近科幻电影大作的员工,也不影响另一个寻找某热门犯罪连续剧第二季花絮的员工(我假设所有不能被满足的订单在递交给DVD出租店之前就已经被处理过了)。同样的,每个订单的打包和邮递工作也不会影响其他订单的查找、运送和处理工作。

你也可能会遇到某些不能被并行化的而只能串行执行的计算任务,它们大多数是因为循环之间或者计算步骤之间有依赖关系从而导致它们只能按照特定的顺序串行执行。一个很好的例子是驯鹿怀孕的过程。通常驯鹿需要八个月来生小驯鹿,你不可能为了早点生个小驯鹿就让八个驯鹿来一起来生,想一个月就生出一个来。但是,如果圣诞老人希望尽快的扩充雪橇队伍,他可以让八只驯鹿一起生,这样八个月后就能有八只小驯鹿了(注:可以理解为尽管单个任务的执行时间没缩短,但是吞吐量却大了)。

规则二:尽可能地在最高层进行并行化
在对一段串行代码进行并行化时我们有两种方法可以选择,一个是自底向上,另一个是自顶向下。在对我们的代码进行分析的过程中,我们先找到花费了最多执行时间的程序热点(hotspots)。对这些代码段进行并行化是使我们获得最大的性能提升的最好办法。

在自底向上的方法中,你可以考虑先直接对那些程序热点进行并行化。如果这不太可能实现的话,我们可以顺着它的调用栈(call stack)向上查找,看看能不能找到其他的可以并行化的程序热点。假如你的程序热点在一个嵌套循环的最里层,我们可以从内向外的逐一检查每一层循环,看看某一层是否能被并行执行。即使我们能一开始就很顺利的把程序热点并行化了,我们仍然应该去检查一下是否可能在调用栈中更高的某一层上实现并行化。这样做能提高每个线程所执行的任务的粒度。(注:每个线程所执行的任务的粒度可以理解为成功并行化了的部分在整个程序中所占的比例,根据Amdahl定律,并行化的部分越多,程序的整体性能越高)

为了更清楚的描述这条规则,让我们举一个对视频编码程序进行并行化的例子。如果你的程序热点是针对每个像素的计算,你可以先找到对一帧视频中的每个像素进行计算的循环,并考虑对它进行并行化。以此为基础向“上”找,你可能会发现对每一帧进行处理的循环也是可以被并行化的,这意味着每个线程都可以以帧为单位对一组数据进行独立的处理。如果这个视频编码程序同时要对好几个视频进行处理,那么让每个线程单独处理一个视频流将会是最高层的并行化。

在另一种自顶向下的并行化方法中,我们可以先对整个程序以及计算的流程(为了完成计算任务而依序组合起来的各个程序模块)进行分析。如果并行化的机会不是很明显,我们可以挑出那些包含了程序热点的模块并对他们进行分析,如果不行就再分析更小的程序热点模块,直到能找到独立的计算任务为止。

对视频编码程序的例子来说,如果你的程序热点是针对单个像素的计算,采用自顶向下的方法时就可以首先考虑该程序对多个不同的视频流进行编码的情况(每个编码任务都包含了像素计算的任务)。如果你能在这一层成功进行并行化,那么你已经得到了最高层的并行。如果没能成功,那我们可以向“下”找,看看每个视频流的不同帧的计算是否能被并行处理,最后看看每个帧的不同像素的计算是否能被并行处理。

并行任务的粒度可以理解成在进行同步之前所需要完成的计算量。同步之间运行的时间越长,粒度越大。细粒度的并行存在的隐患就是给每个线程分配的任务可能不够多,以至于都不够弥补使用多线程所带来的开销。此时,在计算量不变的情况下使用更多的线程只会让情况变得更加糟糕。粗粒度的并行化拥有相对来说更少的线程开销,并且更可能在线程增多的情况下仍然有很好的可扩展性。尽可能的在最高层对程序热点实现并行化是实现对多线程的粗粒度任务划分的主要方法之一。

规则三:尽早针对众核趋势做好可伸缩性的规划
当我写这本书的时候,四核处理器已经成为了主流。未来处理器的核心数量只会越来越多。所以你应该在你的软件中为这个发展趋势做好规划。可伸缩性(scalability)被用来用来衡量一个程序应对变化的能力,典型的变化有系统资源(例如核心数量,内存大小,总线速度)或数据集大小的增加等。在面对越来越多的可用核心时,你必须写出能灵活高效的利用不同数量的核心的代码。

C. Northcote Parkinson说过,“数据的增长是为了适应处理能力的增加”。这意味着随着计算能力的增长加(核心数量的增加),很有可能我们会有更多的数据需要处理。我们永远会有更多的计算任务需要完成。不管是增加科学模拟中的建模精度,还是处理更清晰的高清视频,又或者搜索许多更大的数据库,如果你拥有了更多的计算资源,总会有人想要处理更多的数据。

用数据分解(data decomposition)的方法来设计和实现并行化能给你提供更多的高可扩展性的解决方案。任务分解(task decomposition)的方法可能会面临程序中可独立运行的函数或者代码段数量有限或者数量固定的问题。等到每一个独立的任务已经在单独的线程和核心上运行的时候,再想通过增加线程的数量来利用空闲的多余核心的方法就提高不了程序的性能了。因为在一个程序中数据的大小比独立的计算任务的数量更有可能增加,所以基于数据分解的设计将更有可能获得很好的可伸缩性。

即使有的程序已经基于任务分解的模式给每个线程分配了不同的计算任务,我们仍然可以在需要处理的数据增加的时候利用更多的线程来完成工作。例如我们需要修建一个杂货店,这项工程由一些不同的任务组成。如果开发商又买了一块相邻的地皮,并且商店要盖的楼层数翻倍了,我们可以雇佣更多的工人去完成这些的任务,比如说更多的油漆工,更多的盖顶工,更多的电工。因此,我们应该注意是否能对增加了的数据进行数据分解,以便利用空闲核心上的可用线程来完成这个工作,哪怕是在我们已经采用了任务分解的方式的程序中。

规则四:尽可能利用已有的线程安全库
如果你的程序热点的计算任务能通过库函数调用来完成,强烈建议你考虑使用同等功能的库函数,而不是调用自己手写的代码。即使是串行程序,“重新造轮子”来完成已经被高度优化的库函数实现了的功能仍不是一个好主意。许多的库,例如Intel Math Kernel Library(Intel MKL)和Intel Integrated Performance Primitives (Intel IPP),提供了能更好的利用多核处理器的并行版本的函数。

比使用并行版本的函数库更重要的一点是:我们需要确保所有的库函数调用都是线程安全的(thread-safe)。如果你已经把你串行代码中的程序热点替换成了一个库函数调用,你仍有可能在调用树(call tree)的更高层上发现能把程序分解成独立的计算任务的代码段。当你有好几个并行的计算任务,并且它们都同时调用了库函数(特别是第三方函数库),那么函数库中引用并更新共享变量的函数可能会造成数据竞争(data race)。记得好好检查你在并行编程中所调用的函数库的文档中关于线程安全性的描述。当你在设计和编写自己的用于并行执行的函数库时,请务必确保函数是可重入(reentrant)的。如果不能确保的话,你应该给共享的资源加上同步机制。

规则五:使用合适的多线程模型
如果并行版的函数库不足以完成程序的并行化,而你又想使用可以自己控制的线程,在隐式的多线程模型能满足你的功能需求的前提下请尽量使用该模型(例如OpenMP或者Intel Thread Building Block)而不是显式的多线程模型(例如Pthread)。显式的多线程模型确实能提供对线程的更精确的控制。但是,如果你仅仅是想把你的计算密集型循环给并行化,或者你不需要显式多线程模型提供的诸多特性,那么我们最好还是能满足需要就好。实现的复杂度越高,犯错误的几率就越大,以后代码的维护难度也会越大。

OpenMP采用的是数据分解的方法,它尤其适合并行化那些需要处理大量数据的循环。尽管这种类型的并行化可能是唯一一种你能引入的并行模式,但是可能还会有其他的要求(例如由你的雇主或者管理层所决定的工程方案)让你不能使用OpenMP。如果是那样的话,我建议你先使用OpenMP来快速开发出并行化后的模型,估算一下可能的性能提升、可扩展性以及大概需要多少时间才能把这些串行代码用显式多线程库给并行化。

规则六:永远不要假设具体的执行顺序
在串行程序中我们可以非常容易地预测某个程序的当前状态结束之后它会变成什么状态。然而,多个线程的执行顺序却是不确定的,它是由操作系统的调度器(scheduler)决定的。这意味着我们不可能准确的预测两个执行状态之间多个线程的执行顺序,甚至连预测哪个线程会在下一步被调度执行也不能。这样的机制主要是为了隐藏程序运行时的延迟,特别是当运行的线程的数量多于核心的数量时。例如,如果一个线程因为要访问不在cache中的地址,或者需要处理一个I/O请求而被阻塞了(blocked),那么操作系统的调度器就会把该线程调度到等待队列里,同时把另一个等待执行的线程调度进来并执行它。

数据竞争(data race)就是由这种调度的不确定性造成的。如果你假设一个线程对共享变量的写操作会在另一个线程对该共享变量的读操作之前完成,你的预测可能会一直正确,有可能有些时候会正确,也有可能从来都不会正确。如果你足够幸运的话,有时候在一个特定平台上每次你运行这个程序时线程的执行顺序都不会改变。但是系统间的每个不同(例如数据在磁盘上存储的位置,内存的速度或者插座中的交流电源)都有可能影响线程的调度。对一段需要特定的线程执行顺序的代码来说,如果仅仅依靠乐观的估计而不采取任何实质性的措施的话,很有可能会受到数据竞争,死锁等问题的困扰。

从性能的角度来讲,最好的情形当然是让所有的线程尽可能没有约束的运行,就像比赛中的赛马或猎犬的一样。除非必要的话,尽可能不要规定一个特定的执行顺序。你需要找到那些确实需要规定执行顺序的地方,并且实现一些必要的同步方法来调整线程间的执行顺序。

拿接力赛跑来说,第一棒的选手会竭尽全力的奔跑。但是为了成功的完成接力赛,第二个,第三个和最后一棒都需要先等到拿到接力棒之后才能开始跑他们的赛段。接力棒的交接就是他们的同步机制,这样就确保了接力过程中的“执行”顺序。

规则七:尽可能使用线程本地存储或者对特定的数据加锁
同步(Synchronization)本身并不属于计算任务,它只是为了确保程序的并行执行能得到正确的结果所产生的额外开销。虽然它产生了额外的开销但是又不可或缺。因此我们还是要尽可能的把同步所产生的开销降低到最低。你可以使用线程私有的存储空间或者独占的内存地址(例如一个用线程ID来进行索引的数组)来达到这个目的。

那些很少需要在线程间共享的临时变量可以被每个线程单独地在本地进行声明或分配。那些存储着每个线程的部分结果(partial result)的变量也应该是线程私有的。但是在把每个线程的部分结果保存到一个共享的变量的时候就需要采取一些适当的同步措施了。如果我们能确保这样的共享更新操作能尽可能少的进行,我们就可以把同步的额外开销降到最低了。如果我们使用显式的线程编程模型的话,我们可以使用那些线程本地存储(Thread Local Storage)的API来保证线程私有变量在多个并行区域的执行过程中,或者在一个并行函数的多次调用的过程中的一致性。

如果线程本地存储不可行,而且你必须用同步的对象(例如锁)来协调对共享资源的访问的话,请确保对数据进行了适当的锁操作。最简单的方法就是对锁和数据对象采取一一对应的分配策略。如果对变量的内存地址的访问都是在同一个临界区进行的话,我们就可以使用一把锁来对多个数据进行保护。

如果你有大量的数据需要保护,例如由一万个数据的数组,我们该怎么办呢?如果我们对整个数组只用一个锁来进行保护的话,很可能会造成严重的锁竞争从而导致性能瓶颈。那么我们是不是可以给每个数组元素创建一个锁呢?然而即使是有32个或者64个线程在同时访问这个数组,这样做看起来也浪费了很多的内存空间来保护那些只有百分之一不到的发生概率的访问冲突。不过有一种折中的解决方案,叫做“取模锁”(modulo lock)。取模锁是用来保护数据集合中的所有的第N个元素,其中N是锁的数量。例如,有两个锁,一个保护所有的奇数个的元素,另一个保护所有的偶数个元素。当需要访问一个被保护的变量时,线程需要先对要访问的地址进行取模操作,然后再去获得对应的取模锁。使用的锁的数量应该是基于线程的数量以及两个线程同时访问相同元素的可能性来决定。

但是,当你决定用锁来对数据进行保护时,请一定不要用多于一个的锁来给一个单独的元素进行加锁。西格尔定律告诉我们“一个人看着一个表能知道现在几点了,但是他要是有两个表那么他就确定不了时间了”。如果两个不同的锁都对同一个变量进行了保护,那么可能出现代码中的某一部分通过第一个锁来进行访问的同时,代码中的另一部分通过第二个锁也进行了访问。正在执行这两个代码段的多个线程就可能发生数据竞争,因为它们都以为它们对这个被保护的变量有独占的访问权限。

规则八:敢于更换更易并行化的算法
当比较串行或者并行程序的性能的时候,运行时间就是衡量的首要标准。程序员会根据算法的时间复杂度来进行选择。时间复杂度和一个程序的性能是息息相关的。它的含义就是,当其他的一切条件都一样时,完成同样功能的时间复杂度为O(NlogN)的算法(例如快速排序)要比O(n^2)的算法(例如选择排序)要快。

在并行程序中,拥有更好的时间复杂度的算法也会更快一些。然而,有些时候时间复杂度更好的算法却不是很容易被并行化。如果算法的热点不太容易被并行化的话(而且在调用栈的更高层中你又找不到能很容易被并行化的热点),那么你可以尝试换一个稍微慢一点但是却更容易被并行化的算法。当然,还有可能一些其他的改动措施也能让你比较轻松的把某一段代码给并行化了。

这里我们可以给出一个线性代数中两个矩阵相乘的例子。Strassen的算法拥有最好的时间复杂度:O(n^2.81)。这当然比传统的三重循环的O(n^3)的算法要好。Strassen的算法把每个分成四部分,然后进行七次递归调用来对n/2 x n/2的子矩阵进行乘运算。如果想把这七次递归调用并行化的话,我们可以在每次的递归调用的时候创建一个新线程来进行运算,直到子矩阵到达一个预设的大小为止。这样的话线程的数量就会指数级的成倍增长。随着子矩阵越来越小,给新创建的线程分配的计算任务就会越来越少。还有另一种方法,就是先创建一个有七个线程的线程池。七次子矩阵相乘的运算任务可以分别分配给这七个线程以完成并行化。这样的话线程池就会跟串行版本的程序一样递归调用Strassen算法来对子矩阵进行乘运算。然而,这种方法的缺点就在于对一个拥有大于八个核的系统来说,永远只有七个核在工作,其他的资源都被浪费了。

另一个更容易被并行化的矩阵乘法就是三重循环的算法了。我们可以有很多方法来对矩阵进行数据分解(按行分解,按列分解或者按块分解)然后再把它们分配给不同的线程。通过用OpenMP在某一层循环中加上编译指示,或者用显式线程模型实现矩阵分割,我们很容易的就能完成并行化。只需要更少的代码改动就可以对这个简单的串行算法完成并行化,并且代码的整体结构改动也会比Strassen算法要少很多。

总结
我们已经列出了八条简单的规则,在把串行程序并行化的过程中你应该时刻记住它们。通过遵循这些规则以及一些实际的编程规则,你应该可以更容易的创造更健壮的并行化解决方案,同时能包含更少的并行化时的问题,以及在更短的时间里得到最好的性能。

原文链接:8 Simple Rules for Designing Threaded Applications

瑞典Ericsson总部Master Thesis面试回忆录

2009 May 5th:

晚上刚从超市回来就发现Gtalk弹出新邮件的消息,第一眼就看见标题中Interview的字眼,立刻欣喜若狂,急急忙忙打开仔细一看,竟然是我最早申请的职位的Interview!我是April 24th投的这个职位(Master Thesis),另外还投了若干Summer Job(其中就包括我当天刚刚投完的Nema Labs的Summer job,后面会详叙),Volvo的Master Thesis以及其他几个Ericsson的Thesis Position。

因为这个是我投出去的第一份申请,当时完全没有任何经验,而且Cover Letter和CV都不是最好,现在回想之所以能够拿到这个Interview,主要因为以下几点原因:

1. 专业对口,GPA够。职位是做Sensor Network的,我的专业是Networks and Distributed Systems,正好对口,而且我在刚刚结束的课程Project中正好做过Sensor Network的一个项目,可谓牛头对上了马嘴,不亦乐乎。另外GPA也是Ericsson非常看重的,很多职位写明必须4.0(满分5.0)以上,个人觉得4.3以上比较保险。

2. 简历虽然有些小纰漏,但是因为当时也有针对职位的要求进行修改,所以还是能给人第一眼的好印象的。

3. Cover Letter写得也还凑合。除了常规介绍外还重点说了说自己对那个Thesis的看法,扯了扯自己的本科毕设。[…]

阅读全文>>

前言:去年4月份我申请过一些6月份开始的毕业设计和暑假实习,最终拿到了Ericsson的master thesis offer和另一个哥德堡小公司的summer intern,Volvo在我拿到summer intern后也给了interview。现在应该已经有不少一年级的同学要开始找暑假实习了,我觉得你们可以考虑申请6月份开始的毕设(等毕设结束后再回学校把剩下的课程修完)。下面是我去位于Kista的Ericsson总部面试的经历,希望对大家有用。Summer Intern总体上来讲难度比thesis大很多,因为很多瑞典人也要竞争这种职位,而且那些提供summer intern的小公司也不太喜欢招foreigner。

2009 May 5th:

晚上刚从超市回来就发现Gtalk弹出新邮件的消息,第一眼就看见标题中Interview的字眼,立刻欣喜若狂,急急忙忙打开仔细一看,竟然是我最早申请的职位的Interview!我是April 24th投的这个职位(Master Thesis),另外还投了若干Summer Job(其中就包括我当天刚刚投完的Nema Labs的Summer job,后面会详叙),Volvo的Master Thesis以及其他几个Ericsson的Thesis Position。

因为这个是我投出去的第一份申请,当时完全没有任何经验,而且Cover Letter和CV都不是最好,现在回想之所以能够拿到这个Interview,主要因为以下几点原因:

1. 专业对口,GPA够。职位是做Sensor Network的,我的专业是Networks and Distributed Systems,正好对口,而且我在刚刚结束的课程Project中正好做过Sensor Network的一个项目,可谓牛头对上了马嘴,不亦乐乎。另外GPA也是Ericsson非常看重的,很多职位写明必须4.0(满分5.0)以上,个人觉得4.3以上比较保险。

2. 简历虽然有些小纰漏,但是因为当时也有针对职位的要求进行修改,所以还是能给人第一眼的好印象的。

3. Cover Letter写得也还凑合。除了常规介绍外还重点说了说自己对那个Thesis的看法,扯了扯自己的本科毕设。

发信人是后来面试我的Dr. V.,我一查竟然是UCxx的出身,心想又是UCxx啊!不禁由衷的仰慕,立刻对之后的Interview十分的向往。事后证明Dr. V.人真的非常的nice,虽然有些许龅牙,但是至少英语听起来比较舒服啊!

之后的信件往来就是确定面试时间之类,定下下下周五之后立刻跟身在Kista的yoan师兄联系商量借住事宜(在此对师兄的热情相助表示深深感谢!是你让我在Kista感受到家的温暖啊!还顺带连累你熬了个通宵 囧),然后就是买往返的火车票之类。一切定好后剩下的两个礼拜就开始拼命准备,囫囵吞枣扫了些论文,再跟着看了些英文面试的资料,甚至还去了Career Office做了一次咨询。

这其中发生了一件比较逗的事情。因为哥德堡到斯德的来回火车票加起来600多SEK,我心想这一趟下去怎么的也得1000块了,要不问问看他们能不能给报销?再加上外国公司以往报销路费的事听了不少,我就借着发信问问题的机会顺带来了句:“I am wondering whether you will undertake my travel fee for this interview?” 猜猜人家怎么回的?

“it’s not possible to 报销路费, so我们只能电话Interview了”,我心想,大哥我这菜鸟要电话面试不就相当于直接管你要据信么,再说我票都定了大不了当去旅游好了,于是连忙给他发信解释说没关系云云。

2009 May 14th

早上6点的火车去Stockholm,4点半起的,等5点的第一班tram去Central Station。顺利等到4路电车,心想时间肯定来得及,耽误不了。但是不幸恰恰在心情放松麻痹大意的情况下发生了。我在离火车站还有两站路的时候突发奇想拿出口语书开始模拟英语面试,自己边模拟面试官边想着怎么回答,简直就是左右互搏,天人合一,不亦乐乎,十分忘我。练了5,6分钟后我发现不对了:怎么窗外还能看见火车啊?我仔细一看,我靠!还真是Central Station的火车,其中就有我要坐的x2000!我心中大叫不好,刚刚停的那站就是火车站,我给错过了!!我赶紧收拾东西站在门口准备在下站下车赶紧再坐回去,结果老天真给我开了个大玩笑:过了上一站之后Tram就进入郊区了,开了至少5分钟才到下一站!那5分钟简直就是我人生最漫长的一段时间之一,脑子100%运转,不停看表计算时间,同时储备体力随时准备狂奔。

5分钟后终于到达下一站了,赶紧下车,到对面站台看反方向的车几点到:5分钟以后!这意味着我到火车站后离发车只剩10分钟不到!!!而且我还从来没去过火车站都不知道火车在哪!天无绝人之路,我发现旁边竟然还有一个车站!赶紧对了下时间,Tram7马上就到,又多出了5分钟!老天保佑,我心急如焚的等着不紧不慢的7路小电车,来了!上车!走!到!门开的一霎那,我真是卯足了劲往站台冲啊!事后回想我大概只用了1分钟不到就找到了X2000的站台。这还多亏瑞典的火车站不像国内的那么大,还要进候车厅再排队检票上下楼梯什么的,站台离车站正门也就2-3分钟的路,而且上车后再检票。我悬着的心终于放下来了,事后回想就算当天没赶上我也可以再买下一班的,大不了先上车后补票,还好是我之前订的就是周四走周五面试。虽然我这不叫大难不死,但也算是必有后福啊!

顺利到达Stockholm。斯京的火车站和地铁站是连在一起的,下火车后直接就去地铁售票处买了张24h的通票(100SEK),直奔Kista。话说这个Kista号称瑞典最大的科技园区,里面不仅有Ericsson全球总部,华为瑞典分舵等众多IT公司,KTH也有一个分校区在那边。出了Kista地铁站直接就是一个大型Shopping Mall,在把正补觉的师兄吵醒之后顺利放下行李。中午吃了师兄做的红烧肉拌面,话说那个红烧肉确实很够味,真是赞!

下午就出去Kista园区去寻我明天面试的地点去了。来了Kista我最大的感受就是,整个Kista到处都是Ericsson的人。不管是在Shopping Mall里的Restaurant还是在工业园区的大街上,到处都是挂着蓝色Ericsson牌子的人,简直就是Ericsson大山寨。后来听到一个说法,Ericsson这样的国民企业其实更应该被看做一个Community,在Kista的shopping mall里面甚至有专门的Ericsson员工价,由此可见一般。顺便说一句,上次回国刚下飞机在机场大巴上,坐我旁边的竟然是个瑞典小哥,仔细一聊竟然也是学CS的,从Stockholm来中国找他中国女朋友,于是我就问“你是不是给Ericsson工作”,结果竟然猜对了。由此可见爱立信有多庞大。

事实也确实如此。一开始我找到的最显眼的是一栋白色的大型Ericsson办公楼,整个楼占了一个广场的大小,气势直逼瑞典皇宫了(当然更现代点),真不愧是世界级大公司的全球总部啊。于是我就去reception问我的面试官是不是在这栋楼办公,结果人家告诉我:“不好意思,你找的人在对面那栋楼办公,出门后直走就到了”。等我出去仔细一看,原来Ericsson Research是另一栋大红楼。我猜可能那栋大白楼里面应该都是Ericsson负责工业产品的部门吧。踩点完毕后就回家继续做准备去了。Tips:对面试要提前踩点,特别是去不熟悉的地方更要多做准备,因为瑞典人很忌讳迟到(瑞典交通发达,地铁非常准时,也没什么堵车,所以没有迟到的理由)。

虽然最后我拿到了这个Offer,但是说实话在面试之前我还是非常紧张的。这可是我第一次英文面试,两个面试官都是顶尖大学的PHD,还顶着Ericsson总部的光环。我做的主要准备如下:

1)根据Position Description看了几篇该领域的综述型Paper,以到达快速入门的目的;

2)仔细研究该Position的Requirement,结合自己的CV自己进行了若干次模拟面试

3)准备了自己本科毕设的资料(一页A4插图,直观明了)和,因为这个跟该Thesis有点相关

4)给面试专门准备了一份CV,突出了自己项目经验跟该position的相关性

面试的流程大致如下:

跟两份面试官打过招呼后直接把CV和Transcript递上(省了人家自己打印的功夫,而且给你第一印象就是你准备的很充分。“我把简历都给你带过来了,上面的都是你们需要的”)。Dr.V.人非常好的先给我介绍了一下该Thesis的大致背景,很好的帮助我消除了紧张情绪并帮助我快速进入状态。在了解到项目的大致框架后我适时的接过话题(适时把握话题的主动性,不是被人牵着鼻子走。“我对这个很熟,请听听我的想法”),抛出了我对这个项目的具体实现的想法(虽然有些当时我的想法有些许错误,但是很好的表现出自己对这个项目的兴趣,就像是说:“你看,我自己脑子里已经有一个实现了,我很有可能能把这个项目完成的很好”)。

再聊了一些项目的话题后面试官就开始问我的简历上的项目经验了。我就一个一个跟他们解释(“我做过的东西跟这个Thesis都很相关,我很有竞争力”),其中有几个他们比较熟悉的项目他们就会问你一些技术问题或者算法问题。不过只要自己对项目的背景知识和本身的实现比较熟悉基本没什么问题,而且就算真的不会直接说不会也没关系。我其中就有2个问题直接说了不会,很可能他们因为看重我其他的背景和我的学习能力所以没影响我拿offer。

我感觉我整个面试过程中最出彩的地方在介绍我的本科毕设部分。回想当年在白混了3年之后,心想最后一个毕设怎么的也得拿个A做出点像样的东西来,要不大学白过了,于是狠命搞了半年终于如愿以偿。正好毕设跟这个Thesis很相关,当我拿出我做的prototype的照片并向他们介绍它的功能的时候,我分明的感觉到两位Ericsson Researcher都被我打动了(“给我Offer吧!本科毕设我都拿A了,你们这个Thesis我肯定不会让你们失望的!”)。

最后Dr. V.非常Nice的送我下楼,我在电梯里又跟他聊起不能报销差旅费的事情,最后我对他说了我生平最有打动人的效果的一句英语:“I just want to let you know my serious and positive attitude for this position.”结果Dr.V.非常配合的笑着对我说:“Yes!You have!”

The End:May 19th下午正准备跟妞妞mixi,突然接到一个010开头的电话,我还奇怪难道是北京打来的?后来才知道在瑞典Stockholm的区号也是010。也许大家都猜到了,其实就是另一位面试官打来的Offer电话。

P.S. 虽然因为种种原因没去Ericsson,但是我仍然深深的被Ericsson HQ的魅力所吸引,它向我展现了一个世界电信巨头的风采。而Stockholm,它的美丽更是让我留恋。希望下一次妞妞能跟我再一次同游斯德。

P.S.S. 猜猜Kista最大的中国人群体里在哪?不错,就是华为!华为真是牛逼,我问过好几个瑞典人了,华为真的是一个爱立信强有力对手的存在,直接把分舵开到Ericsson老家,有点新东方把分舵开始ETS总部的意思。在此祝华为越来越牛逼!早日出台Kista华为员工价!

Pthreads并行编程之spin lock与mutex性能对比分析

POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。线程同步(Thread Synchronization)是并行编程中非常重要的通讯手段,其中最典型的应用就是用Pthreads提供的锁机制(lock)来对多个线程之间共 享的临界区(Critical Section)进行保护(另一种常用的同步机制是barrier)。

Pthreads提供了多种锁机制:
(1) Mutex(互斥量):pthread_mutex_***
(2) Spin lock(自旋锁):pthread_spin_***
(3) Condition Variable(条件变量):pthread_con_***
(4) Read/Write lock(读写锁):pthread_rwlock_***

Pthreads提供的Mutex锁操作相关的API主要有:
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_trylock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Pthreads提供的与Spin Lock锁操作相关的API主要有:
pthread_spin_lock (pthread_spinlock_t *lock);
pthread_spin_trylock (pthread_spinlock_t *lock);
pthread_spin_unlock (pthread_spinlock_t *lock);

从实现原理上来讲,Mutex是属于sleep-waiting类型 的锁。例如在一个双核的机器上有两个线程(线程A和线程B),它们分别运行在Core0和Core1上。当线程A想要 pthread_mutex_lock操作去得到一个临界区的锁时,如果这个锁正被线程B所持有,那么线程A就会被阻塞(bolcking),Core0 会在此时进行上下文切换(Context Switch),这样Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然,它是属于busy-waiting类型的锁,如果线程A是使用pthread_spin_lock操作去请求锁,那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求,直到得到这个锁为止。

阅读全文>>

POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。线程同步(Thread Synchronization)是并行编程中非常重要的通讯手段,其中最典型的应用就是用Pthreads提供的锁机制(lock)来对多个线程之间共 享的临界区(Critical Section)进行保护(另一种常用的同步机制是barrier)。

Pthreads提供了多种锁机制:
(1) Mutex(互斥量):pthread_mutex_***
(2) Spin lock(自旋锁):pthread_spin_***
(3) Condition Variable(条件变量):pthread_con_***
(4) Read/Write lock(读写锁):pthread_rwlock_***

Pthreads提供的Mutex锁操作相关的API主要有:
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_trylock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Pthreads提供的与Spin Lock锁操作相关的API主要有:
pthread_spin_lock (pthread_spinlock_t *lock);
pthread_spin_trylock (pthread_spinlock_t *lock);
pthread_spin_unlock (pthread_spinlock_t *lock);

从实现原理上来讲,Mutex属于sleep-waiting类型的锁。例如在一个双核的机器上有两个线程(线程A和线程B),它们分别运行在Core0和Core1上。假设线程A想要通过pthread_mutex_lock操作去得到一个临界区的锁,而此时这个锁正被线程B所持有,那么线程A就会被阻塞(blocking),Core0 会在此时进行上下文切换(Context Switch)将线程A置于等待队列中,此时Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然,它属于busy-waiting类型的锁,如果线程A是使用pthread_spin_lock操作去请求锁,那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求,直到得到这个锁为止。

如果大家去查阅Linux glibc中对pthreads API的实现NPTL(Native POSIX Thread Library) 的源码的话(使用”getconf GNU_LIBPTHREAD_VERSION”命令可以得到我们系统中NPTL的版本号),就会发现pthread_mutex_lock()操作如果没有锁成功的话就会调用system_wait()的系统调用(现在NPTL的实现采用了用户空间的futex,不需要频繁进行系统调用,性能已经大有改善),并将当前线程加入该mutex的等待队列里。而spin lock则可以理解为在一个while(1)循环中用内嵌的汇编代码实现的锁操作(印象中看过一篇论文介绍说在linux内核中spin lock操作只需要两条CPU指令,解锁操作只用一条指令就可以完成)。有兴趣的朋友可以参考另一个名为sanos的微内核中pthreds API的实现:mutex.c spinlock.c,尽管与NPTL中的代码实现不尽相同,但是因为它的实现非常简单易懂,对我们理解spin lock和mutex的特性还是很有帮助的。

那么在实际编程中mutex和spin lcok哪个的性能更好呢?我们知道spin lock在Linux内核中有非常广泛的利用,那么这是不是说明spin lock的性能更好呢?下面让我们来用实际的代码测试一下(请确保你的系统中已经安装了最近的g++)。

// Name: spinlockvsmutex1.cc
// Source: http://www.alexonlinux.com/pthread-mutex-vs-pthread-spinlock
// Compiler(spin lock version): g++ -o spin_version -DUSE_SPINLOCK spinlockvsmutex1.cc -lpthread
// Compiler(mutex version): g++ -o mutex_version spinlockvsmutex1.cc -lpthread
#include <stdio.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <errno.h>
#include <sys/time.h>
#include <list>
#include <pthread.h>

#define LOOPS 50000000

using namespace std;

list<int> the_list;

#ifdef USE_SPINLOCK
pthread_spinlock_t spinlock;
#else
pthread_mutex_t mutex;
#endif

//Get the thread id
pid_t gettid() { return syscall( __NR_gettid ); }

void *consumer(void *ptr)
{
    int i;

    printf("Consumer TID %lun", (unsigned long)gettid());

    while (1)
    {
#ifdef USE_SPINLOCK
        pthread_spin_lock(&spinlock);
#else
        pthread_mutex_lock(&mutex);
#endif

        if (the_list.empty())
        {
#ifdef USE_SPINLOCK
            pthread_spin_unlock(&spinlock);
#else
            pthread_mutex_unlock(&mutex);
#endif
            break;
        }

        i = the_list.front();
        the_list.pop_front();

#ifdef USE_SPINLOCK
        pthread_spin_unlock(&spinlock);
#else
        pthread_mutex_unlock(&mutex);
#endif
    }

    return NULL;
}

int main()
{
    int i;
    pthread_t thr1, thr2;
    struct timeval tv1, tv2;

#ifdef USE_SPINLOCK
    pthread_spin_init(&spinlock, 0);
#else
    pthread_mutex_init(&mutex, NULL);
#endif

    // Creating the list content...
    for (i = 0; i < LOOPS; i++)
        the_list.push_back(i);

    // Measuring time before starting the threads...
    gettimeofday(&tv1, NULL);

    pthread_create(&thr1, NULL, consumer, NULL);
    pthread_create(&thr2, NULL, consumer, NULL);

    pthread_join(thr1, NULL);
    pthread_join(thr2, NULL);

    // Measuring time after threads finished...
    gettimeofday(&tv2, NULL);

    if (tv1.tv_usec > tv2.tv_usec)
    {
        tv2.tv_sec--;
        tv2.tv_usec += 1000000;
    }

    printf("Result - %ld.%ldn", tv2.tv_sec - tv1.tv_sec,
        tv2.tv_usec - tv1.tv_usec);

#ifdef USE_SPINLOCK
    pthread_spin_destroy(&spinlock);
#else
    pthread_mutex_destroy(&mutex);
#endif

    return 0;
}

该程序运行过程如下:主线程先初始化一个list结构,并根据LOOPS的值将对应数量的entry插入该list,之后创建两个新线程,它们都执行consumer()这个任务。两个被创建的新线程同时对这个list进行pop操作。主线程会计算从创建两个新线程到两个新线程结束之间所用的时间,输出为下文中的”Result “。

测试机器参数:
Ubuntu 9.04 X86_64
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz
4.0 GB Memory

从下面是测试结果:

gchen@gchen-desktop:~/Workspace/mutex$ g++ -o spin_version -DUSE_SPINLOCK spinvsmutex1.cc -lpthread
gchen@gchen-desktop:~/Workspace/mutex$ g++ -o mutex_version spinvsmutex1.cc -lpthread
gchen@gchen-desktop:~/Workspace/mutex$ time ./spin_version
Consumer TID 5520
Consumer TID 5521
Result - 5.888750

real    0m10.918s
user    0m15.601s
sys    0m0.804s

gchen@gchen-desktop:~/Workspace/mutex$ time ./mutex_version
Consumer TID 5691
Consumer TID 5692
Result - 9.116376

real    0m14.031s
user    0m12.245s
sys    0m4.368s

可以看见spin lock的版本在该程序中表现出来的性能更好。另外值得注意的是sys时间,mutex版本花费了更多的系统调用时间,这就是因为mutex会在锁冲突时调用system wait造成的。

但是,是不是说spin lock就一定更好了呢?让我们再来看一个锁冲突程度非常剧烈的实例程序:

//Name: svm2.c
//Source: http://www.solarisinternals.com/wiki/index.php/DTrace_Topics_Locks
//Compile(spin lock version): gcc -o spin -DUSE_SPINLOCK svm2.c -lpthread
//Compile(mutex version): gcc -o mutex svm2.c -lpthread
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/syscall.h>

#define        THREAD_NUM     2

pthread_t g_thread[THREAD_NUM];
#ifdef USE_SPINLOCK
pthread_spinlock_t g_spin;
#else
pthread_mutex_t g_mutex;
#endif
__uint64_t g_count;

pid_t gettid()
{
    return syscall(SYS_gettid);
}

void *run_amuck(void *arg)
{
       int i, j;

       printf("Thread %lu started.n", (unsigned long)gettid());

       for (i = 0; i < 10000; i++) {
#ifdef USE_SPINLOCK
           pthread_spin_lock(&g_spin);
#else
               pthread_mutex_lock(&g_mutex);
#endif
               for (j = 0; j < 100000; j++) {
                       if (g_count++ == 123456789)
                               printf("Thread %lu wins!n", (unsigned long)gettid());
               }
#ifdef USE_SPINLOCK
           pthread_spin_unlock(&g_spin);
#else
               pthread_mutex_unlock(&g_mutex);
#endif
       }
       
       printf("Thread %lu finished!n", (unsigned long)gettid());

       return (NULL);
}

int main(int argc, char *argv[])
{
       int i, threads = THREAD_NUM;

       printf("Creating %d threads...n", threads);
#ifdef USE_SPINLOCK
       pthread_spin_init(&g_spin, 0);
#else
       pthread_mutex_init(&g_mutex, NULL);
#endif
       for (i = 0; i < threads; i++)
               pthread_create(&g_thread[i], NULL, run_amuck, (void *) i);

       for (i = 0; i < threads; i++)
               pthread_join(g_thread[i], NULL);

       printf("Done.n");

       return (0);
}

这个程序的特征就是临界区非常大,这样两个线程的锁竞争会非常的剧烈。当然这个是一个极端情况,实际应用程序中临界区不会如此大,锁竞争也不会如此激烈。测试结果显示mutex版本性能更好:

gchen@gchen-desktop:~/Workspace/mutex$ time ./spin
Creating 2 threads...
Thread 31796 started.
Thread 31797 started.
Thread 31797 wins!
Thread 31797 finished!
Thread 31796 finished!
Done.

real    0m5.748s
user    0m10.257s
sys    0m0.004s

gchen@gchen-desktop:~/Workspace/mutex$ time ./mutex
Creating 2 threads...
Thread 31801 started.
Thread 31802 started.
Thread 31802 wins!
Thread 31802 finished!
Thread 31801 finished!
Done.

real    0m4.823s
user    0m4.772s
sys    0m0.032s

另外一个值得注意的细节是spin lock耗费了更多的user time。这就是因为两个线程分别运行在两个核上,大部分时间只有一个线程能拿到锁,所以另一个线程就一直在它运行的core上进行忙等待,CPU占用率一直是100%;而mutex则不同,当对锁的请求失败后上下文切换就会发生,这样就能空出一个核来进行别的运算任务了。(其实这种上下文切换对已经拿着锁的那个线程性能也是有影响的,因为当该线程释放该锁时它需要通知操作系统去唤醒那些被阻塞的线程,这也是额外的开销)

总结
(1)Mutex适合对锁操作非常频繁的场景,并且具有更好的适应性。尽管相比spin lock它会花费更多的开销(主要是上下文切换),但是它能适合实际开发中复杂的应用场景,在保证一定性能的前提下提供更大的灵活度。

(2)spin lock的lock/unlock性能更好(花费更少的cpu指令),但是它只适应用于临界区运行时间很短的场景。而在实际软件开发中,除非程序员对自己的程序的锁操作行为非常的了解,否则使用spin lock不是一个好主意(通常一个多线程程序中对锁的操作有数以万次,如果失败的锁操作(contended lock requests)过多的话就会浪费很多的时间进行空等待)。

(3)更保险的方法或许是先(保守的)使用 Mutex,然后如果对性能还有进一步的需求,可以尝试使用spin lock进行调优。毕竟我们的程序不像Linux kernel那样对性能需求那么高(Linux Kernel最常用的锁操作是spin lock和rw lock)。

2010年3月3日补记:这个观点在Oracle的文档中得到了支持:

During configuration, Berkeley DB selects a mutex implementation for the architecture. Berkeley DB normally prefers blocking-mutex implementations over non-blocking ones. For example, Berkeley DB will select POSIX pthread mutex interfaces rather than assembly-code test-and-set spin mutexes because pthread mutexes are usually more efficient and less likely to waste CPU cycles spinning without getting any work accomplished.

p.s.调用syscall(SYS_gettid)和syscall( __NR_gettid )都可以得到当前线程的id:)

转载请注明来自: www.parallellabs.com