[已经招到了,谢谢大家!]IBM中国研究院招聘Hadoop实习生

我们组最近有一个实习生的名额,做Hadoop性能优化相关的研究工作,如果大家感兴趣的话请给我发邮件:)

IBM Research China is looking for graduate computer science/engineering students who are interested in Hadoop performance optimizations works.

Location: Beijing
Job Tile: Research Intern
Job Openings: 1
Expected Duration: at least 3 months (full-time preferred)

Job responsibilities:
– Write MapReduce program and analyze Hadoop performance model.
– Tune and optimize the performance of Hadoop workloads.
– Publish high quality research papers to report your work.

Requirements:
– Creative and Self-motivated
– Knowledge of Parallel Computing and Distributed Systems.
– Knowledge of Java.
– Familiarity with Linux as development and testing environments.
– Knowledge of Apache Hadoop is a plus.
– Past research experience is a plus.

If you’re interested, please feel free to send your Chinese or English resume with the mail title of “Intern_Your Name_University_Major_Grade” (e.g. Intern_Zhang San_XXU_CS_Master) to chengc_at_cn.ibm.com.

我们组最近有一个实习生的名额,做Hadoop性能优化相关的研究工作,如果大家感兴趣的话请给我发邮件:)

IBM Research China is looking for graduate computer science/engineering students who are interested in Hadoop performance optimizations works.

Location: Beijing
Job Tile: Research Intern
Job Openings: 1
Expected Duration: at least 3 months (full-time preferred)

Job responsibilities:
– Write MapReduce program and analyze Hadoop performance model.
– Tune and optimize the performance of Hadoop workloads.
– Publish high quality research papers to report your work.

Requirements:
– Creative and Self-motivated
– Knowledge of Parallel Computing and Distributed Systems.
– Knowledge of Java.
– Familiarity with Linux as development and testing environments.
– Knowledge of Apache Hadoop is a plus.
– Past research experience is a plus.

If you’re interested, please feel free to send your Chinese or English resume with the mail title of “Intern_Your Name_University_Major_Grade” (e.g. Intern_Zhang San_XXU_CS_Master) to chengc_at_cn.ibm.com.

IBM中国研究院招聘大规模数据分析实习生

帮同事发文,招聘实习生:

IBM Research China is looking for undergraduate and graduate computer science/engineering students who are interested in Big Data Analytics development and performance optimizations works.

Location: Beijing
Job Tile: Research Intern
Job Openings: 1-2
Expected Duration: at least 3 months (full time)

Job responsibilities:
– Develop text mining solutions such as Topic Detection and Tracking (TDT).
– Write Apache MapReduce user function code to implement Social Network Analysis (SNA), Machine Learning and Text Mining algorithms.
– Tune and optimize the performance of Apache MapReduce/HDFS based analytics workload on POWER7.
– Publish high quality research papers to report your work.

Required skills:
– Knowledge of 1) Parallel Computing and Distributed Systems or 2) Machine Learning and Data Mining
– Knowledge of Java
– Familiarity with Linux as development and testing environments.
– Experience of Apache Hadoop will be a plus.

We also encourage exceptional students to generate and implement their own ideas about Big Data Analytics related works over the course of internship.

If you’re interested, please feel free to drop us an email to jwshi_at_cn.ibm.com with your resume.

浅析C++多线程内存模型

注:本文发表于《程序员》2011年第6期并行编程专栏,略有删改。

在即将到来的C++1x标准中,一个重大的更新就是引入了C++多线程内存模型。本文的主要目的在于介绍C++多线程内存模型涉及到的一些原理和概念,以帮助大家理解C++多线程内存模型的作用和意义。

阅读全文>>

注:本文发表于《程序员》2011年第6期并行编程专栏,略有删改。

在即将到来的C++1x标准中,一个重大的更新就是引入了C++多线程内存模型。本文的主要目的在于介绍C++多线程内存模型涉及到的一些原理和概念,以帮助大家理解C++多线程内存模型的作用和意义。

1. 顺序一致性模型(Sequential Consistency)

在介绍C++多线程模型之前,让我们先介绍一下最基本的顺序一致性模型。对多线程程序来说,最直观,最容易被理解的执行方式就是顺序一致性模型。顺序一致性的提出者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)从单个线程的角度来看,每个线程内部的指令都是按照程序规定的顺序(program order)来执行的;
(2)从整个多线程程序的角度来看,整个多线程程序的执行顺序是按照某种交错顺序来执行的,且是全局一致的;

下面我们通过一个例子来理解顺序一致性。假设我们有两个线程(线程1和线程2),它们分别运行在两个CPU核上,有两个初始值为0的全局共享变量x和y,两个线程分别执行下面两条指令:
初始条件: x = y = 0;

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

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

顺序 1 顺序 2 顺序 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

顺序一致性模型的第一个约定要求每个线程内部的语句都是按照程序规定的顺序执行,例如,线程1里面的两条语句在该线程中一定是x=1先执行,r1=y后执行。顺序一致性的第二个约定要求多线程程序按照某种顺序执行,且所有线程看见的整体执行顺序必须一致,即该多线程程序可以按照顺序1、顺序2或者顺序3(以及其他可能的执行顺序)执行,且线程1和线程2所观察到的整个程序的执行顺序是一致的(例如,如果线程1“看见”整个程序的执行顺序是顺序 1,那么线程2“看见”的整个程序的执行顺序也必须是顺序1,而不能是顺序2或者顺序3)。依照顺序一致性模型,虽然这个程序还可能按其他的交错顺序执行,但是r1和r2的值却只可能出现上面三种结果,而不可能出现r1和r2同时为0的情况。

然而,尽管顺序一致性模型非常易于理解,但是它却对CPU和编译器的性能优化做出了很大的限制,所以常见的多核CPU和编译器大都没有实现顺序一致性模型。例如,编译器可能会为了隐藏一部分读操作的延迟而做如下优化,把线程1中对y的读操作(即r1=y)调换到x=1之前执行:

初始条件:x=y=0;

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

在这种情况下,该程序如果按下面的顺序执行就可能就会出现r1和r2都为0这样的违反顺序一致性的结果:

顺序 4
r1 = y;
y = 1;
r2 = x;
x = 1;

那么为什么编译器会做这样的乱序优化呢?因为读一个在内存中而不是在cache中的共享变量需要较长的时钟周期,所以编译器就“自作聪明”的让读操作先执行,从而隐藏掉一些指令执行的延迟,从而提高程序的性能。实际上,这种优化是串行时代非常普遍的,因为它对单线程程序的语义是没有影响的。但是在进入多核时代后,编译器缺少语言级的内存模型的约束,导致其可能做出违法顺序一致性规定的多线程语义的错误优化。同样的,多核CPU中的写缓冲区(store buffer)也可能实施乱序优化:它会把要写入内存的值先在缓冲区中缓存起来,以便让该写操作之后的指令先执行,进而出现违反顺序一致性的执行顺序。

因为现有的多核CPU和编译器都没有遵守顺序一致模型,而且C/C++的现有标准中都没有把多线程考虑在内,所以给编写多线程程序带来了一些问题。例如,为了正确地用C++实现Double-Checked Locking,我们需要使用非常底层的内存栅栏(Memory Barrier)指令来显式地规定代码的内存顺序性(memory ordering)[5]。然而,这种方案依赖于具体的硬件,因此可移植性很差;而且它过于底层,不方便使用。

2. C++多线程内存模型

为了更容易的进行多线程编程,程序员希望程序能按照顺序一致性模型执行;但是顺序一致性对性能的损失太大了,CPU和编译器为了提高性能就必须要做优化。为了在易编程性和性能间取得一个平衡,一个新的模型出炉了:sequential consistency for data race free programs,它就是即将到来的C++1x标准中多线程内存模型的基础。对C++程序员来说,随着C++1x标准的到来,我们终于可以依赖高级语言内建的多线程内存模型来编写正确的、高性能的多线程程序。

C++内存模型可以被看作是C++程序和计算机系统(包括编译器,多核CPU等可能对程序进行乱序优化的软硬件)之间的契约,它规定了多个线程访问同一个内存地址时的语义,以及某个线程对内存地址的更新何时能被其它线程看见。这个模型约定:没有数据竞跑的程序是遵循顺序一致性的。该模型的核心思想就是由程序员用同步原语(例如锁或者C++1x中新引入的atomic类型的共享变量)来保证你程序是没有数据竞跑的,这样CPU和编译器就会保证程序是按程序员所想的那样执行的(即顺序一致性)。换句话说,程序员只需要恰当地使用具有同步语义的指令来标记那些真正需要同步的变量和操作,就相当于告诉CPU和编译器不要对这些标记好的同步操作和变量做违反顺序一致性的优化,而其它未被标记的地方可以做原有的优化。编译器和CPU的大部分优化手段都可以继续实施,只是在同步原语处需要对优化做出相应的限制;而且程序员只需要保证正确地使用同步原语即可,因为它们最终表现出来的执行效果与顺序一致性模型一致。由此,C++多线程内存模型帮助我们在易编程性和性能之间取得了一个平衡。

在C++1x标准之前,C++是在建立在单线程语义上的。为了进行多线程编程,C++程序员通过使用诸如Pthreads,Windows Thread等C++语言标准之外的线程库来完成代码设计。以Pthreads为例,它提供了类似pthread_mutex_lock这样的函数来保证对共享变量的互斥访问,以防止数据竞跑。人们不禁会问,Pthreads这样的线程库我用的好好的,干嘛需要C++引入的多线程,这不是多此一举么?其实,以线程库的形式进行多线程编程在绝大多数应用场景下都是没有问题的。然而,线程库的解决方案也有其先天缺陷。第一,如果没有在编程语言中定义内存模型的话,我们就不能清楚的定义到底什么样的编译器/CPU优化是合法的,而程序员也不能确定程序到底会怎么样被优化执行。例如,Pthreads标准中并未对什么是数据竞跑(Data Race)做出精确定义,因此C++编译器可能会进行一些错误优化从而导致数据竞跑[3]。第二,绝大多数情况下线程库能正确的完成任务,而在极少数对性能有更高要求的情况下(尤其是需要利用底层的硬件特性来实现高性能Lock Free算法时)需要更精确的内存模型以规定好程序的行为。简而言之,把内存模型集成到编程语言中去是比线程库更好的选择。

3. C++1x中引入的atomic类型

C++作为一种高性能的系统语言,其设计目标之一就在于提供足够底层的操作,以满足对高性能的需求。在这个前提之下,C++1x除了提供传统的锁、条件变量等同步机制之外,还引入了新的atomic类型。相对于传统的mutex锁来说,atomic类型更底层,具备更好的性能,因此能用于实现诸如Lock Free等高性能并行算法。有了atomic类型,C++程序员就不需要像原来一样使用汇编代码来实现高性能的多线程程序了。而且,把atomic类型集成到C++语言中之后,程序员就可以更容易地实现可移植的多线程程序,而不用再依赖那些平台相关的汇编语句或者线程库。

对常见的数据类型,C++1x都提供了与之相对应的atomic类型。以bool类型举例,与之相对应的atomic_bool类型具备两个新属性:原子性与顺序性。顾名思义,原子性的意思是说atomic_bool的操作都是不可分割的,原子的;而顺序性则指定了对该变量的操作何时对其他线程可见。在C++1x中,为了满足对性能的追求,atomic类型提供了三种顺序属性:sequential consistency ordering(即顺序一致性),acquire release ordering以及relaxed ordering。因为sequential consistency是最易理解的模型,所以默认情况下所有atomic类型的操作都会使sequential consistency顺序。当然,顺序一致性的性能相对来说比较差,所以程序员还可以使用对顺序性要求稍弱一些的acquire release ordering与最弱的relaxed ordering。

在下面这个例子中,atomic_bool类型的变量data_ready就被用来实现两个线程间的同步操作。需要注意的是,对data_ready的写操作仍然可以通过直接使用赋值操作符(即“=”)来进行,但是对其的读操作就必须调用load()函数来进行。在默认的情况下,所有atomic类型变量的顺序性都是顺序一致性(即sequential consistency)。在这个例子中,因为data_ready的顺序性被规定为顺序一致性,所以线程1中对data_ready的写操作会与线程2中对data_ready的读操作构建起synchronize-with的同步关系,即#2->#3。又因为writer_thread()中的代码顺序规定了#1在#2之前发生,即#1->#2;而且reader_thread中的代码顺序规定了#3->#4,所以就有了#1->#2->#3->#4这样的顺序关系,从而可以保证在#4中读取data的值时,#1已经执行完毕,即#4一定能读到#1写入的值(10)。

#include <atomic>
#include <vector>
#include <iostream>

std::vector<int> data;
std::atomic_bool data_ready(false);

// 线程1
void writer_thread()
{
data.push_back(10); // #1:对data的写操作
data_ready = true; // #2:对data_ready的写操作
}

// 线程2
void reader_thread()
{
while(!data_ready.load()) // #3:对data_ready的读操作
{
std::this_thread::sleep(std::milliseconds(10));
}
std::cout << ”data is ” << data[0] << ”\n”; // #4:对data的读操作
}

相信很多朋友会纳闷,这样的执行顺序不是显然的么?其实不然。如果我们把data_ready的顺序性制定为relaxed ordering的话,编译器和CPU就可以自由地做违反顺序一致性的乱序优化,从而导致#1不一定在#2之前被执行,最终导致#4中读到的data的值不为10。

简单的来说,在atomic类型提供的三种顺序属性中,acquire release ordering对顺序性的约束程度介于sequential consistency(顺序一致性)和relaxed ordering之间,因为它不要求全局一致性,但是具有synchronized with的关系。Relaxed ordering最弱,因为它对顺序性不做任何要求。由此可见,除非非常必要,我们一般不建议使用relaxed ordering,因为这不能保证任何顺序性。关于这三种属性更详细的信息大家可以参考[1]。

通过上面的例子我们可以看到,C++1x中的多线程内存模型为了通过atomic类型提供足够的灵活性和性能,最大限度地将底层细节(三种不同的顺序属性)暴露给了程序员。这样的设计原则一方面给程序员提供了实现高性能多线程算法的可能,但却也大大增加了使用上的难度。我个人的建议是,如果常规的mutex锁、条件变量、future信号能满足您的设计需求,那么您完全不需要使用atomic变量。如果您决定使用atomic变量,请尽量使用默认的顺序一致性属性。

4. 总结

本文对C++1x标准中新引入的多线程内存模型进行了简要介绍。C++1x多线程内存模型的引入使得广大C++程序员可以享受语言原生支持的多线程机制,并为实现高性能多线程算法提供了足够丰富的工具(例如atomic类型)。但是,多线程内存模型本身的复杂性,以及一些底层机制(例如不同的顺序性属性)的引入也给使用C++进行多线程编程带来了不小的复杂度。如何高效、可靠的利用好这些新引入的多线程机制将会成为一个新的挑战。

参考资料

[1] C++ Concurrency in Action
[2] C++1x standard draft
[3] Threads cannot be implemented as a library
[4] Memory Models: A Case for Rethinking Parallel Languages and Hardware
[5] The “Double-Checked Locking is Broken” Declaration

Facebook的Realtime Hadoop及其应用

在今年的SIGMOD‘11上,Facebook又发了一篇新paper(点此下载),讲述了它们在提高Hadoop实时性上的工作及其应用。简单来讲,他们的项目需求主要有:

1. Elasticity(伸缩性)
2. High write throughput(高写吞吐量)
3. Efficient and low-latency strong consistency semantics within a data center(单个data center内高性能、低延迟的强一致性)
4. Efficient random reads from disk(disk的高性能随机读)
5. High Availability and Disaster Recovery(高可靠性、灾后恢复能力)
6. Fault Isolation(错误隔离)
7. Atomic read-modify-write primitives(read-modify-write原子操作)
8. Range Scans(范围扫描)

阅读全文>>

在今年的SIGMOD‘11上,Facebook又发了一篇新paper(点此下载),讲述了它们在提高Hadoop实时性上的工作及其应用。简单来讲,他们的项目需求主要有:

1. Elasticity(伸缩性)
2. High write throughput(高写吞吐量)
3. Efficient and low-latency strong consistency semantics within a data center(单个data center内高性能、低延迟的强一致性)
4. Efficient random reads from disk(disk的高性能随机读)
5. High Availability and Disaster Recovery(高可靠性、灾后恢复能力)
6. Fault Isolation(错误隔离)
7. Atomic read-modify-write primitives(read-modify-write原子操作)
8. Range Scans(范围扫描)

最终他们选择了Hadoop和HBase作为解决方案的基石,因为HBase已经满足了上述需求中的大部分。与此同时,他们还做了如下三点改进以满足实时性需求:
1. File Appends
2. Name Node的高可靠性优化 (AvatarNode)
3. HBase的读性能的优化

文章还列举了三个基于此方案的应用:Facebook Message,Facebook Insight,Facebook Metric Systems,大家可以着重看看这三个应用的特点及需求是怎样被这个方案满足的。

在现在这个时代,只有大公司才有如此大的数据来做新东西,难怪Facebook,Google的paper被大量追捧了。

参考资料:
[1] Facebook’s New Realtime Analytics System: HBase To Process 20 Billion Events Per Day
[2] Real Time Analytics for Big Data: An Alternative Approach

下面是这篇文章的slides:

《程序员的自我修养》中关于加锁不能保证线程安全的一个错误

在《程序员的自我修养 — 链接装载与库》一书第28页“过度优化”这一节中,作者提到了编译器优化可能造成多线程bug的情况。但是《程》中所给出的例子其实是错误的。Pthreads线程库帮程序员保证了pthread mutex(spin lock也一样)所保护的临界区内共享变量的可见性:即Thread 1一执行完unlock(),x的最新值1一定能被Thread 2看见。(为了实现这一点,Pthreads线程库在实现的时候都会根据相应的硬件平台调用相应的memory barrier来保证内存可见性,感兴趣的同学可以看看nptl的实现)所以,只要正确的用锁保护好你的共享变量,你的程序就会是线程安全的。

阅读全文>>

在《程序员的自我修养 — 链接装载与库》一书第28页“过度优化”这一节中,作者提到了编译器优化可能造成多线程bug的情况(我手中的是09年6月第二次印刷那版)。原文如下:

线程安全是一个非常烫手的山芋,因为即使合理的使用了锁,也不一定能保证线程安全,这是源于落后的编译器技术已经无法满足日益增长的并发需求。很多看似无错的代码在优化和并发前又产生了麻烦。最简单的例子,让我们看看如下代码:

x = 0;
Thread 1 Thread 2
lock(); lock();
x++; x++;
unlock(); unlock();

由于有lock和unlock的保护,x++的行为不会被并发所破坏,那么x的值似乎必然是2了。然后,如果编译器为了提高x的访问速度,把x放到了某个寄存器里,那么我们知道不同线程的寄存器是各自独立的,因此如果Thread 1先获得锁,则程序的执行可能会呈现如下的执行情况:

*1 Thread 1:读取x的值到某个寄存器R[1] (R[1]=0)
*2 Thread 1:R[1]++
*3 Thread 2:读取x的值到某个寄存器R[2] (R[2]=0)
*4 Thread 2:R[2]++
*5 Thread 2:将R[2]写回至x(x=1)
*6 Thread 1:(很久以后)将R[1]写回至x(x=1)

可见在这样的情况下即使正确的加锁,也不能保证多线程安全。

这个“加锁后仍不能保证线程安全”的结论其实是错误的。在对一段代码进行加锁操作之后,被锁保护起来的代码就形成了一个临界区,在任何时刻最多只能有一个线程运行这个临界区中的代码,而其他的线程必须等待(例如pthread_mutex_lock是阻塞型等待,pthread_spin_lock是忙等待)。给临界区加锁之后相当于给临界区内的代码添加了原子性的语义。

既然加锁之后临界区内的代码是原子操作的,那么就不可能出现《程》中描述的那种执行顺序,因为Thread 2必须要等到Thread 1执行完x++和unlock()之后才能获得锁并随即进行x++操作。即如下所述的执行顺序:

*1 Thread 1:lock()
*2 Thread 1:读取x的值到某个寄存器R[1] (R[1]=0)
*3 Thread 1:R[1]++
*4 Thread 1:将R[1]写回至x(x=1)
*5 Thread 1:unlock()
*6 Thread 2:lock() //得到锁
*7 Thread 2:读取x的值到某个寄存器R[2] (R[2]=1)
*8 Thread 2:R[2]++
*9 Thread 2:将R[2]写回至x(x=2)
*10 Thread 2:unlock()

其实,这里更值得讨论的一个问题是memory visibility(内存可见性)。例如,在Thread 1将R[1]的值写回至x的这一步中,如果Thread 1只是将值放到了这个CPU核的write buffer(write buffer是多核CPU中为于优化写性能的一种硬件)里,而未将最新值直接更新至内存,那么处在另一个CPU核上的Thread 2真的有可能在第7步时读到的是x的旧值0,这下该怎么办?这个问题其实就是共享变量的值何时能被其他线程可见的问题。

好在正是因为内存可见性在共享内存的并行编程中如此的重要,所以以pthread为代表的线程库早就规定好了自己的内存模型,其中就包括了memory visibility的定义:

Memory Visibility
– When will changes of shared data be visible to other threads?
– Pthreads standard guarantees basic memory visibility rules
» thread creation
• memory state before calling pthread_create(…) is visible to created thread
» mutex unlocking (also combined with condition variables)
• memory state before unlocking a mutex is visible to thread which locks same mutex
» thread termination (i.e. entering state “terminated”)
• memory state before termination is visible to thread which joins with terminated thread
» condition variables
• memory state before notifying waiting threads is visible to woke up threads

说简单点,Pthreads线程库帮程序员保证了pthread mutex(spin lock也一样)所保护的临界区内共享变量的可见性:即Thread 1一执行完unlock(),x的最新值1一定能被Thread 2看见。(为了实现这一点,Pthreads线程库在实现的时候都会根据相应的硬件平台调用相应的memory barrier来保证内存可见性,感兴趣的同学可以看看nptl的实现)

所以,只要正确的用锁保护好你的共享变量,你的程序就会是线程安全的。《程》中所给出的上述例子其实是错误的。

PS.《程》确实是本好书,作者作为我的同龄人功力还是令人钦佩的。但是这个例子也反映了一个现实:写书最怕的就是出现重大的原则性错误,而博客作为互联网上的公开资源,能更容易的吸收大家的修改意见,保证文章的正确性。

参考文献:
[1] Programming with POSIX Threads
[2] Mutex and Memory Visibility

你好,2011!

2010年总结与2011年计划。

阅读全文>>

2010年总结

爱人。在08年8月24日踏上去瑞典的飞机时我曾跟我的女友说:“宝贝,你放心,等我回来”。今年我最大的成就之一就是实现了两年前的诺言。

家人。在暑假时我抽时间跟家人完成了一次欧洲游。“活在当下”是《追逐日光》作者的一句感慨,不要等到已经失去与你所爱的人相处的机会时再去后悔。

研究。10年大部分时间都用来做研究了。我非常庆幸能有机会与我的导师Per Stenström一起共事,从他身上我学到了非常非常多的东西,是他帮助我找到了自己的兴趣和方向,他给我的那句寄语更是让我终生受益。临别之际我跟他说,“现在我因你而骄傲,将来我一定努力使你因我而自豪。”

2010年最有感触的一句话:”仰望星空与脚踏实地”。前者提醒我想成为的是一个对社会有用的人;后者提醒我在特定的环境下该如何把事情做好。

2011年计划

自修。希望能全方面提升自己的修养。

研究。希望能发一篇顶级Paper。现在正在冲刺ICS。

工作。希望能在北京找到一份让我感到Exciting的工作,牛同事越多越好。

编程。希望今年至少能写三万行代码。

交际。希望能参加更多的线下聚会,认识更多的朋友。

读书。希望能读完12本书,至少3本非技术的。

博客。希望能写24篇博客。其实我觉得我写Wiki的形式更好,因为我的博客都很长。

锻炼。希望每周能锻炼一次。

效率。希望能全方面提升自己的个人效率。

感情,亲情。放在心中。

2011年的箴言:”Stay Hungry,Stay Foolish”。
郭去疾先生对这句话的解读我非常喜欢,特此与大家分享:

“乔布斯说stay hungry,我以为饥渴有三个层次:贪婪、成就动机、好奇心。三者分别关注:瞬间的结果,持续的过程,和远大的未知。三者也恰好对应了三种人:卑劣的投机者,艰辛的攀登者,与幸福的探索者。

乔布斯说的stay foolish,放在语言环境中(斯坦福毕业典礼),我觉得很有针对性的,是特别说给这些所谓名校毕业生听的,因为他们比较容易持才放旷,不可一世,或者投机取巧,追求捷径。翻译成中文,就是:切不要聪明反被聪明误。”

祝大家新年里幸福,平安,健康,开心!

移动设备进入多核时代!

Nvidia最近发布了代号为Tegra 2的新一代双核移动处理器,移动设备即将进入多核时代。该款处理器由两个基于ARM Cortex A9的核心及其它视频音频图形专用核心(可看成Accelerator)组成,是一个典型的异构(Heterogeneous)平台。这个平台的关键特征有两个:低功耗(比高频单核的处理器耗电小),高性能(异构平台的性能优势)。

阅读全文>>

Nvidia最近发布了代号为Tegra 2的新一代双核移动处理器,移动设备即将进入多核时代。该款处理器由两个基于ARM Cortex A9的核心及其它视频音频图形专用核心(可看成Accelerator)组成,是一个典型的异构(Heterogeneous)平台。这个平台的关键特征有两个:低功耗(比高频单核的处理器耗电小),高性能(异构平台的性能优势)。

我之前也讲过为什么我们要迁移到多核平台,简单来说,继续提升核心频率及电压的办法会让处理器的功耗呈指数级增加,此时的功耗会难以让人接受;而在晶体管数目持续增加的前提下,工业界自然就(被迫)选择了更加容易实现的多核方案来继续提升硬件的性能。这个趋势也即将体现在移动处理器上。

Nvidia的白皮书《The Benefits of Multiple CPU Cores in Mobile Devices》中提到了几个多核对移动应用带来的好处:

1. 更快的网页加载速度

现在的网页内容越来越丰富,也越来越复杂。HTML5,Flash,Javascript,视频等内容的呈现都需要强大的处理能力。Nvidia提供的测试数据表明Tegra 2的Javascript性能提升了1.5~2倍,网页平均加载速度提升了46%。事实上Firefox,Chrome等桌面浏览器都已经采用了多线程,而Android浏览器,Safari等采用的Webkit内核也已经实现了多线程。在浏览器已经并行化的前提下,多核移动处理器自然能提供更快更丰富的网页渲染体验。

2. 更低的功耗及更高的性能瓦特比

对多核来讲,任务调度及电源管理算法是提升性能瓦特比的关键。Tegra 2能通过如下几点降低功耗:
1)把任务平均分配到两个核心上,这样每个核心都不必跑在最高频率/电压上,而只需要以较低的频率/电压就能完成任务,从而节省功耗
2)如果要执行的任务是高度并行化的,Tegra 2就能更快的完成这个任务,从而更快的进入超低功耗待机模式,节省更多电量
3)如果任务只需要一个核心的话,其他计算单元可以被关闭从而节省电量

续航能力一直是手机、Tablet等移动设备的关键问题之一,在电池技术没有突破性进展的今天,我们只能寄希望于硬件/软件上的优化手段来降低功耗了。

3. 提升游戏体验

Tegra 2的图形处理单元叫做Ultra Low Power (ULP) GeForce GPU,性能应该很不错。现在的一些主流游戏引擎早已经完成了并行化(多线程分别用来完成渲染,音频,网络,解码,碰撞检测,透明等任务)。白皮书中提供的测试数据表明虚幻3引擎在Tegra 2双核心上快了将近70%。一个值得注意的地方时很多游戏引擎是通过task parallelism的方式以适应不同的处理器核心数目,这说明基于这些引擎的游戏可以在几乎不修改程序的情况下在以后的4核乃至8核移动平台上取得更好的游戏体验。游戏在最受欢迎的移动应用中还是占了大头的,所以多核对移动游戏应用的影响会非常大。

下面是一些主流游戏引擎使用的线程数:
Game/Engine(Number of Threads)
Unreal Engine 3(4+)
Id Tech 5(6+)
Frostbite(14)
Civilization 5(12)
Mafia 2(4)
Crysis(8)
Uncharted 2(8)
Killzone 2(8+)

4. 更平滑的用户体验及更快的多任务处理能力

多任务处理在手机/Tablet上都非常常见。当你一边听着歌,一边下载电影,一边上网冲浪时,多核处理器就能帮你把这些任务分配到不同的核心上进行处理,从而给你提供更好的更平滑的用户体验。我记得iPad上的一些电子杂志的界面响应速度是个很大的问题,因为渲染速度太慢了,性能更高的多核平台就能提供更快的处理速度,提升用户体验,当然,这个前提是该程序能充分利用好多核。

想到这我还要插一句题外话。iOS一开始不支持对第三方程序的多任务处理功能其实主要是因为iPhone/iPad上内存有限(256MB)且没有硬盘(即没有swap),具体可参考Robert Love(该大牛现在在做Android)这篇《Why the iPad and iPhone don’t Support Multitasking》;至于Android怎么解决多任务处理的可以参考这篇《Multitasking Android Way》(想看这两篇都要会功夫,你懂的)

移动设备的多核时代已经到来,移动开发者们,你们准备好了么?

剖析为什么在多核多线程程序中要慎用volatile关键字?

这篇文章详细剖析了为什么在多核时代进行多线程编程时需要慎用volatile关键字。

主要内容有:
1. C/C++中的volatile关键字
2. Visual Studio对C/C++中volatile关键字的扩展
3. Java/.NET中的volatile关键字
4. Memory Model(内存模型)
5. Volatile使用建议

阅读全文>>

这篇文章详细剖析了为什么在多核时代进行多线程编程时需要慎用volatile关键字。

主要内容有:
1. C/C++中的volatile关键字
2. Visual Studio对C/C++中volatile关键字的扩展
3. Java/.NET中的volatile关键字
4. Memory Model(内存模型)
5. Volatile使用建议

1. C/C++中的volatile关键字

1.1 传统用途

C/C++作为系统级语言,它们与硬件的联系是很紧密的。volatile的意思是“易变的”,这个关键字最早就是为了针对那些“异常”的内存操作而准备的。它的效果是让编译器不要对这个变量的读写操作做任何优化,每次读的时候都直接去该变量的内存地址中去读,每次写的时候都直接写到该变量的内存地址中去,即不做任何缓存优化。它经常用在需要处理中断的嵌入式系统中,其典型的应用有下面几种:

a. 避免用通用寄存器对内存读写的优化。编译器常做的一种优化就是:把常用变量的频繁读写弄到通用寄存器中,最后不用的时候再存回内存中。但是如果某个内存地址中的值是由片外决定的(例如另一个线程或是另一个设备可能更改它),那就需要volatile关键字了。(感谢Kenny老师指正)
b. 硬件寄存器可能被其他设备改变的情况。例如一个嵌入式板子上的某个寄存器直接与一个测试仪器连在一起,这样在这个寄存器的值随时可能被那个测试仪器更改。在这种情况下如果把该值设为volatile属性的,那么编译器就会每次都直接从内存中去取这个值的最新值,而不是自作聪明的把这个值保留在缓存中而导致读不到最新的那个被其他设备写入的新值。
c. 同一个物理内存地址M有两个不同的内存地址的情况。例如两个程序同时对同一个物理地址进行读写,那么编译器就不能假设这个地址只会有一个程序访问而做缓存优化,所以程序员在这种情况下也需要把它定义为volatile的。

1.2 多线程程序中的错误用法

看到这里,很多朋友自然会想到:恩,那么如果是两个线程需要同时访问一个共享变量,为了让其中两个线程每次都能读到这个变量的最新值,我们就把它定义为volatile的就好了嘛!我想这个就是多线程程序中volatile之所以引起那么多争议的最大原因。可惜的是,这个想法是错误的。

举例来说,想用volatile变量来做同步(例如一个flag)?错!为什么?很简单,虽然volatile意味着每次读和写都是直接去内存地址中去操作,但是volatile在C/C++现有标准中即不能保证原子性(Atomicity)也不能保证顺序性(Ordering),所以几乎所有试图用volatile来进行多线程同步的方案都是错的。我之前一篇文章介绍了Sequential Consistency模型(后面简称SC),它其实就是我们印象中多线程程序应该有的执行顺序。但是,SC最大的问题是性能太低了,因为CPU/编译器完全没有必要严格按代码规定的顺序(program order)来执行每一条指令。学过体系结构的同学应该知道不管是编译器也好CPU也好,他们最擅长做的事情就是帮你做乱序优化。在串行时代这些乱序优化对程序员来说都是透明的,封装好了的,你不用关心它们到底给你乱序成啥样了,因为它们会保证优化后的程序的运行结果跟你写程序时预期的结果是一模一样的。但是进入多核时代之后,CPU和编译器还会继续做那些串行时代的优化,更重要的是这些优化还会打破你多线程程序的SC模型语义,从而使得多线程程序的实际运行结果与我们所期待的运行结果不一致!

拿X86来说,它的多核内存模型没有严格执行SC,即属于weak ordering(或者叫relax ordering?)。它唯一允许的乱序优化是可以把对不同地址的load操作提到store之前去(即把store x->load y乱序优化成load y -> store x)。而store x -> store y、load x -> load y,以及load y -> store x不允许交换执行顺序。在X86这样的内存模型下,volatile关键字根本就不能保证对不同volatile变量x和y的store x -> load y的操作不会被CPU乱序优化成load y -> store x。

而对多线程读写操作的原子性来说,诸如volatile x=1这样的写操作的原子性其实是由X86硬件保证的,跟volatile没有任何关系。事实上,volatile根本不能保证对没有内存对齐的变量(或者超出机器字长的变量)的读写操作的原子性。

为了有个更直观的理解,我们来看看CPU的乱序优化是如何让volatile在多线程程序中显得如此无力的。下面这个著名的Dekker算法是想用flag1/2和turn来实现两个线程情况下的临界区互斥访问。这个算法关键就在于对flag1/2和turn的读操作(load)是在其写操作(store)之后的,因此这个多线程算法能保证dekker1和dekker2中对gSharedCounter++的操作是互斥的,即等于是把gSharedCounter++放到临界区里去了。但是,多核X86可能会对这个store->load操作做乱序优化,例如dekker1中对flag2的读操作可能会被提到对flag1和turn的写操作之前,这样就会最终导致临界区的互斥访问失效,而gSharedCounter++也会因此产生data race从而出现错误的计算结果。那么为什么多核CPU会对多线程程序做这样的乱序优化呢?因为从单线程的视角来看flag2和flag1、turn是没有依赖关系的,所以CPU当然可以对他们进行乱序优化以便充分利用好CPU里面的流水线(想了解更多细节请参考计算机体系结构相关书籍)。这样的优化虽然从单线程角度来讲没有错,但是它却违反了我们设计这个多线程算法时所期望的那个多线程语义。(想要解决这个bug就需要自己手动添加memory barrier,或者干脆别去实现这样的算法,而是使用类似pthread_mutex_lock这样的库函数,后面我会再讲到这点)

当然,对不同的CPU来说他们的内存模型是不同的。比如说,如果这个程序是在单核上以多线程的方式执行那么它肯定不会出错,因为单核CPU的内存模型是符合SC的。而在例如PowerPC,ARM之类的架构上运行结果到底如何就得去翻它们的硬件手册中内存模型是怎么定义的了。

/*
 * Dekker's algorithm, implemented on pthreads
 *
 * To use as a test to see if/when we can make
 * memory consistency play games with us in 
 * practice. 
 *
 * Compile: gcc -O2 -o dekker dekker.c -lpthread
 * Source: http://jakob.engbloms.se/archives/65
 */ 

#include <assert.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#undef PRINT_PROGRESS 

static volatile int flag1 = 0;
static volatile int flag2 = 0;
static volatile int turn  = 1;
static volatile int gSharedCounter = 0;
int gLoopCount;
int gOnePercent;

void dekker1( ) {
        flag1 = 1;
        turn  = 2;
        while((flag2 ==  1) && (turn == 2)) ;
        // Critical section
        gSharedCounter++;
        // Let the other task run
        flag1 = 0;
}

void dekker2(void) {
        flag2 = 1;
        turn = 1;
        while((flag1 ==  1) && (turn == 1)) ;
        // critical section
        gSharedCounter++;        
        // leave critical section
        flag2 = 0;
}

//
// Tasks, as a level of indirection
//
void *task1(void *arg) {
        int i,j;
        printf("Starting task1\n");
        // Do the dekker very many times
#ifdef PRINT_PROGRESS
	for(i=0;i<100;i++) {
	  printf("[One] at %d%%\n",i);
	  for(j=gOnePercent;j>0;j--) {
	    dekker1();
	  }
	}
#else
	// Simple basic loop
        for(i=gLoopCount;i>0;i--) {
                dekker1();
        }
#endif

}

void *task2(void *arg) {
        int i,j;
        printf("Starting task2\n");
#ifdef PRINT_PROGRESS
	for(i=0;i<100;i++) {
	  printf("[Two] at %d%%\n",i);
	  for(j=gOnePercent;j>0;j--) {
	    dekker2();
	  }
	}
#else
        for(i=gLoopCount;i>0;i--) {
                dekker2();
        }
#endif
}

int
main(int argc, char ** argv)
{
        int            loopCount = 0;
        pthread_t      dekker_thread_1;
        pthread_t      dekker_thread_2;
        void           * returnCode;
        int            result;
        int            expected_sum;

        /* Check arguments to program*/
        if(argc != 2) 
        {
                fprintf(stderr, "USAGE: %s <loopcount>\n", argv[0]);
                exit(1);
        }

        /* Parse argument */
        loopCount   = atoi(argv[1]);	/* Don't bother with format checking */
        gLoopCount  = loopCount;
	gOnePercent = loopCount/100;
        expected_sum = 2*loopCount;
        
        /* Start the threads */
        result = pthread_create(&dekker_thread_1, NULL, task1, NULL);
        result = pthread_create(&dekker_thread_2, NULL, task2, NULL);

        /* Wait for the threads to end */
        result = pthread_join(dekker_thread_1,&returnCode);
        result = pthread_join(dekker_thread_2,&returnCode);
        printf("Both threads terminated\n");

        /* Check result */
        if( gSharedCounter != expected_sum ) {
                printf("[-] Dekker did not work, sum %d rather than %d.\n", gSharedCounter, expected_sum);
                printf("    %d missed updates due to memory consistency races.\n", (expected_sum-gSharedCounter));
                return 1;
        } else {
                printf("[+] Dekker worked.\n");
                return 0;
        }
}

2. Visual Studio对C/C++中volatile关键字的扩展

虽然C/C++中的volatile关键字没有对ordering做任何保证,但是微软从Visual Studio 2005开始就对volatile关键字添加了同步语义(保证ordering),即:对volatile变量的读操作具有acquire语义,对volatile变量的写操作具有release语义。Acquire和Release语义是来自data-race-free模型的概念。为了理解这个acquire语义和release语义有什么作用,我们来看看MSDN中的一个例子

// volatile.cpp
// compile with: /EHsc /O2
// Output: Critical Data = 1 Success
#include <iostream>
#include <windows.h>
using namespace std;

volatile bool Sentinel = true;
int CriticalData = 0;

unsigned ThreadFunc1( void* pArguments ) {
   while (Sentinel)
      Sleep(0);   // volatile spin lock

   // CriticalData load guaranteed after every load of Sentinel
   cout << "Critical Data = " << CriticalData << endl;
   return 0;
} 

unsigned  ThreadFunc2( void* pArguments ) {
   Sleep(2000);
   CriticalData++;   // guaranteed to occur before write to Sentinel
   Sentinel = false; // exit critical section
   return 0;
}

int main() {
   HANDLE hThread1, hThread2; 
   DWORD retCode;

   hThread1 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc1,
      NULL, 0, NULL);
   hThread2 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc2,
      NULL, 0, NULL);

   if (hThread1 == NULL || hThread2 == NULL)       {
      cout << "CreateThread failed." << endl; 
      return 1;
   }

   retCode = WaitForSingleObject(hThread1,3000);

   CloseHandle(hThread1);
   CloseHandle(hThread2);

   if (retCode == WAIT_OBJECT_0 && CriticalData == 1 )
      cout << "Success" << endl;
   else
      cout << "Failure" << endl;
}

例子中的 while (Sentinel) Sleep(0); // volatile spin lock 是对volatile变量的读操作,它具有acquire语义,acquire语义的隐义是当前线程在对sentinel的这个读操作之后的所有的对全局变量的访问都必须在该操作之后执行;同理,例子中的Sentinel = false; // exit critical section 是对volatile变量的写操作,它具有release语义,release语义的隐义是当前线程在对sentinel这个写操作之前的所有对全局变量的访问都必须在该操作之前执行完毕。所以ThreadFunc1()读CriticalData时必定已经在ThreadFunc2()执行完CriticalData++之后,即CriticalData最后输出的值必定为1。建议大家用纸画一下acquire/release来加深理解。一个比较形象的解释就是把acquire当成lock,把release当成unlock,它俩组成了一个临界区,所有临界区外面的操作都只能往这个里面移,但是临界区里面的操作都不能往外移,简单吧?

其实这个程序就相当于用volatile变量的acquire和release语义实现了一个临界区,在临界区内部的代码就是 Sleep(2000); CriticalData++; 或者更贴切点也可以看成是一对pthread_cond_wait和pthread_cond_signal。

这个volatile的acquire和release语义是VS自己的扩展,C/C++标准里是没有的,所以同样的代码用gcc编译执行结果就可能是错的,因为编译器/CPU可能做违反正确性的乱序优化。Acquire和release语义本质上就是为了保证程序执行时memory order的正确性。但是,虽然这个VS扩展使得volatile变量能保证ordering,它还是不能保证对volatile变量读写的原子性。事实上,如果我们的程序是跑在X86上面的话,内存对齐了的变量的读写的原子性是由硬件保证的,跟volatile没有任何关系。而像volatile g_nCnt++这样的语句本身就不是原子操作,想要保证这个操作是原子的,就必须使用带LOCK语义的++操作,具体请看我这篇文章

另外,VS生成的volatile变量的汇编代码是否真的调用了memory barrier也得看具体的硬件平台,例如x86上就不需要使用memory barrier也能保证acquire和release语义,因为X86硬件本身就有比较强的memory模型了,但是Itanium上面VS就会生成带memory barrier的汇编代码。具体可以参考这篇

但是,虽然VS对volatile关键字加入了acquire/release语义,有一种情况还是会出错,即我们之前看到的dekker算法的例子。这个其实蛮好理解的,因为读操作的acquire语义不允许在其之后的操作往前移,但是允许在其之前的操作往后移;同理,写操作的release语义允许在其之后的操作往前移,但是不允许在其之前的操作往后移;这样的话对一个volatile变量的读操作(acquire)当然可以放到对另一个volatile变量的写操作(release)之前了!Bug就是这样产生的!下面这个程序大家拿Visual Studio跑一下就会发现bug了(我试了VS2008和VS2010,都有这个bug)。多线程编程复杂吧?希望大家还没被弄晕,要是晕了的话也很正常,仔仔细细重新再看一遍吧:)

想解决这个Bug也很简单,直接在dekker1和dekker2中对flag1/flag2/turn赋值操作之后都分别加入full memory barrier就可以了,即保证load一定是在store之后执行即可。具体的我就不详述了。

#include <iostream>
#include <windows.h>
using namespace std;

static volatile int flag1 = 0;
static volatile int flag2 = 0;
static volatile int turn = 1; // must have "turn", otherwise the two threads might introduce deadlock at line 13&23 of "while..."
static int gCount = 0;

void dekker1() {
	flag1 = 1;
	turn = 2;
	while ((flag2 == 1) && (turn == 2));
	// critical section
	gCount++;
	flag1 = 0; 	// leave critical section
}

void dekker2() {
	flag2 = 1;
	turn = 1;
	while ((flag1 == 1) && (turn == 1));
	// critical setion
	gCount++;
	flag2 = 0; 	// leave critical section
}

unsigned ThreadFunc1( void* pArguments ) {
	int i;
	//cout << "Starting Thread 1" << endl;
	for (i=0;i<1000000;i++) {
		dekker1();
	}
	return 0;
} 

unsigned  ThreadFunc2( void* pArguments ) {
	int i;
	//cout << "Starting Thread 2" << endl;
	for (i=0;i<1000000;i++) {
		dekker2();
	}
	return 0;
}

int main() {
	HANDLE hThread1, hThread2;
	//DWORD retCode;

	hThread1 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc1,
		NULL, 0, NULL);
	hThread2 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc2,
		NULL, 0, NULL);

	if (hThread1 == NULL || hThread2 == NULL) {
		cout << "CreateThread failed." << endl;
		return 1;
	}

	WaitForSingleObject(hThread1,INFINITE);
	WaitForSingleObject(hThread2,INFINITE);
	cout << gCount << endl;

	if (gCount == 2000000)
		cout << "Success" << endl;
	else
		cout << "Fail" << endl;
}

3. Java/.NET中的volatile关键字

3.1 多线程语义

Java和.NET分别有JVM和CLR这样的虚拟机,保证多线程的语义就容易多了。说简单点,Java和.NET中的volatile关键字也是限制虚拟机做优化,都具有acquire和release语义,而且由虚拟机直接保证了对volatile变量读写操作的原子性。 (volatile只保证可见性,不保证原子性。java中,对volatile修饰的long和double的读写就不是原子的 (http://java.sun.com/docs/books/jvms/second_edition/html /Threads.doc.html#22244),除此之外的基本类型和引用类型都是原子的。– 多谢liuchangit指正) 这里需要注意的一点是,Java和.NET里面的volatile没有对应于我们最开始提到的C/C++中对“异常操作”用volatile修饰的传统用法。原因很简单,Java和.NET的虚拟机对安全性的要求比C/C++高多了,它们才不允许不安全的“异常”访问存在呢。

而且像JVM/.NET这样的程序可移植性都非常好。虽然现在C++1x正在把多线程模型添加到标准中去,但是因为C++本身的性质导致它的硬件平台依赖性很高,可移植性不是特别好,所以在移植C/C++多线程程序时理解硬件平台的内存模型是非常重要的一件事情,它直接决定你这个程序是否会正确执行。

至于Java和.NET中是否也存在类似VS 2005那样的bug我没时间去测试,道理其实是相同的,真有需要的同学自己应该能测出来。好像这篇InfoQ的文章中显示Java运行这个dekker算法没有问题,因为JVM给它添加了mfence。另一个臭名昭著的例子就应该是Double-Checked Locking了。

3.2 volatile int与AtomicInteger区别

Java和.NET中这两者还是有些区别的,主要就是后者提供了类似incrementAndGet()这样的方法可以直接调用(保证了原子性),而如果是volatile x进行++操作则不是原子的。increaseAndGet()的实现调用了类似CAS这样的原子指令,所以能保证原子性,同时又不会像使用synchronized关键字一样损失很多性能,用来做全局计数器非常合适。

4. Memory Model(内存模型)

说了这么多,还是顺带介绍一下Memory Model吧。就像前面说的,CPU硬件有它自己的内存模型,不同的编程语言也有它自己的内存模型。如果用一句话来介绍什么是内存模型,我会说它就是程序员,编程语言和硬件之间的一个契约,它保证了共享的内存地址里的值在需要的时候是可见的。下次我会专门详细写一篇关于它的内容。它最大的作用是取得可编程性与性能优化之间的一个平衡。

5. volatile使用建议

总的来说,volatile关键字有两种用途:一个是ISO C/C++中用来处理“异常”内存行为(此用途只保证不让编译器做任何优化,对多核CPU是否会进行乱序优化没有任何约束力),另一种是在Java/.NET(包括Visual Studio添加的扩展)中用来实现高性能并行算法(此种用途通过使用memory barrier保证了CPU/编译器的ordering,以及通过JVM或者CLR保证了对该volatile变量读写操作的原子性)。

一句话,volatile对多线程编程是非常危险的,使用的时候千万要小心你的代码在多核上到底是不是按你所想的方式执行的,特别是对现在暂时还没有引入内存模型的C/C++程序更是如此。安全起见,大家还是用Pthreads,Java.util.concurrent,TBB等并行库提供的lock/spinlock,conditional variable, barrier, Atomic Variable之类的同步方法来干活的好,因为它们的内部实现都调用了相应的memory barrier来保证memory ordering,你只要保证你的多线程程序没有data race,那么它们就能帮你保证你的程序是正确的(是的,Pthreads库也是有它自己的内存模型的,只不过它的内存模型还些缺点,所以把多线程内存模型直接集成到C/C++中是更好的办法,也是将来的趋势,但是C++1x中将不会像Java/.NET一样给volatile关键字添加acquire和release语义,而是转而提供另一种具有同步语义的atomic variables,此为后话)。如果你想实现更高性能的lock free算法,或是使用volatile来进行同步,那么你就需要先把CPU和编程语言的memory model搞清楚,然后再时刻注意Atomicity和Ordering是否被保证了。(注意,用没有acquire/release语义的volatile变量来进行同步是错误的,但是你仍然可以在C/C++中用volatile来修饰一个不是用来做同步(例如一个event flag)而只是被不同线程读写的共享变量,只不过它的新值什么时候能被另一个线程读到是没有保证的,需要你自己做相应的处理)

Herb Sutter 在他的那篇volatile vs. volatile中对这两种用法做了很仔细的区分,我把其中两张表格链接贴过来供大家参考:

volatile的两种用途
volatile两种用途的异同

最后附上《Java Concurrency in Practice》3.1.4节中对Java语言的volatile关键字的使用建议(不要被英语吓到,这些内容确实对你有用,而且还能顺便帮练练英语,哈哈):

So from a memory visibility perspective, writing a volatile variable is like exiting a synchronized block and reading a volatile variable is like entering a synchronized block. However, we do not recommend relying too heavily on volatile variables for visibility; code that relies on volatile variables for visibility of arbitrary state is more fragile and harder to understand than code that uses locking.

Use volatile variables only when they simplify implementing and verifying your synchronization policy; avoid using volatile variables when veryfing correctness would require subtle reasoning about visibility. Good uses of volatile variables include ensuring the visibility of their own state, that of the object they refer to, or indicating that an important lifecycle event (such as initialization or shutdown) has occurred.

Locking can guarantee both visibility and atomicity; volatile variables can only guarantee visibility.

You can use volatile variables only when all the following criteria are met:
(1) Writes to the variable do not depend on its current value, or you can ensure that only a single thread ever updates the value;
(2) The variable does not participate in invariants with other state variables; and
(3) Locking is not required for any other reason while the variable is being accessed.

参考资料

1. 《Java Concurrency in Practice》3.1.4节
2. volatile vs. volatile(Herb Sutter对volatile的阐述,必看)
3. The “Double-Checked Locking is Broken” Declaration
4. Threading in C#
5. Volatile: Almost Useless for Multi-Threaded Programming
6. Memory Ordering in Modern Microprocessors
7. Memory Ordering @ Wikipedia
8. 内存屏障什么的
9. The memory model of x86
10. VC 下 volatile 变量能否建立 Memory Barrier 或并发锁
11. Sayonara volatile(Concurrent Programming on Windows作者的文章 跟我观点几乎一致)
12. Java 理论与实践: 正确使用 Volatile 变量
13. Java中的Volatile关键字

Jeff Dean关于Google系统架构的讲座

上个月Jeff Dean在Standford的Computer Systems Colloquium (EE380)这门讨论课上详细讲了讲Google的系统架构发展过程,因为这是份很新的资料,所以特意把它的Slide下下来与大家分享一下。这门课是Standford的讲座课程,每一节课都由不同的顶级工程师/科学家/投资人前来讲授IT行业的最新动向,非常非常有料,绝对值得深挖。这门课的每节课都是带视频的,Jeff Dean的这个讲座的录像在这里

阅读全文>>

上个月Jeff Dean在Standford的Computer Systems Colloquium (EE380)这门讨论课上详细讲了讲Google的系统架构发展过程,因为这是份很新的资料,所以特意把它的Slide下下来与大家分享一下。这门课是Standford的讲座课程,每一节课都由不同的顶级工程师/科学家/投资人前来讲授IT行业的最新动向,非常非常有料,绝对值得深挖。这门课的每节课都是带视频的,Jeff Dean的这个讲座的录像在这里。想要下载该视频的同学可以去这里(要会功夫,你懂的)。

这个讲座的主要内容包括:
• Evolution of various systems at Google
– computing hardware
– core search systems
– infrastructure software

• Techniques for building large-scale systems
– decomposition into services
– design patterns for performance & reliability

个人的一点小感想:Jeff Dean在Google的这几年能面临这么多有意思的挑战,编程模型,可靠性,伸缩性,运行时环境等等等等,真是羡煞旁人。随着Google业务的扩展,整个系统的设计也面临各种各样新的挑战。只有有了扎实的基本功,在面对没有现成解决方案的新问题时才能游刃有余,做工程是如此,做研究更是如此。

可能有些同学会因为这是个英语的讲座而头疼。我觉得大家可以坚持看,哪个单词看不懂的就查字典,刚开始可能痛苦点,但是只要坚持下去,积少成多,你就会发现自己的英语慢慢就上来了,至少看这些英文slides是没问题了。

Building Software Systems at Google and Lessons Learned

另外还有几个关于Jeff Dean的Google架构的博文:
Jeff Dean 在WSDM 2009上面的演讲 Keynote 和视频终于出来了
来自Jeff Dean的分布式系统设计模式(更新版)
Jeff Dean的Stanford演讲

我还发现了Jeff另外一个在09年做的类似主题的讲座,内容稍有重复,但是可以算是一个补充,例如这个里面包括了BigTable等内容。

Enjoy!

Erlang User Conference 2010见闻(兼谈程序员职业生涯)

这是我第一次参加关于Erlang的技术大会,总来的说收获非常大,不管是技术上的还是非技术上的都是如此。首先不得不说的是会议举行的地点。我从别人那得知之前的会议一直都是在Ericsson的总部大楼举行的,但是因为参会人数越来越多,好像是从去年开始就转移到市中心一个很有历史的电影院ASTORIA举行了。由于这个举办地是电影院的缘故,从去年开始EUC就开始有电影海报了!去年海报是由哈利波特改的,今年的是星球大战。

阅读全文>>

1. Erlang User Confernece 2010

这是我第一次参加关于Erlang的技术大会,总来的说收获非常大,不管是技术上的还是非技术上的都是如此。首先不得不说的是会议举行的地点。我从别人那得知之前的会议一直都是在Ericsson的总部大楼举行的,但是因为参会人数越来越多,好像是从去年开始就转移到市中心一个很有历史的电影院ASTORIA举行了。由于这个举办地是电影院的缘故,从去年开始EUC就开始有电影海报了!去年海报是由哈利波特改的,今年的是星球大战。去年那张如下,有意思吧?

Erlang-the-Movie

海报上面的四个人是Erlang最早的设计者们:Joe Armstrong, Mike Williams, Robert Virding还有当时的团队经理Bjarne Däcker。有了海报没有电影怎么能行?点这里观看Erlang – The Movie

因为我赶早乘火车去的斯德,所以我到的时候已经快9点了,大会即将开始。在去之前我就很期待能见到Joe Armstrong本人,结果意外的是在签到处我就见到Joe本人了!不知道为什么,他出现在我面前时的形象与我之前想象的一模一样,后来我想明白了,根本原因在于他穿的就是他那件非常眼熟的紫黑线衫!哈哈!Joe爷爷人非常开朗,时不时从他坐的地方传出爽朗的笑声,此为后话。因为会议即将开始所以我就赶紧进去找座位坐下,正好赶上Bjarne Däcker在致开幕辞,这是每年的传统了。仔细看了下我的签到卡,这已经是第16届Erlang大会了!

Klarna无疑是这届大会最吸引眼球的公司。开幕第一个Talk就是关于他们怎么使用Erlang相关的工具来解决他们的CodeManagement,Translation,Testing等问题的。Klarna有两个中国程序员,我见到其中之一的Wang Jia。Klarna是由三位瑞典银行家在05年创立的公司,提供第三方电子支付解决方案。他们最早的开发者就是从当时提供Erlang咨询的公司(其实也是Ericsson前员工)跳出来的。传闻说当时创始人提出业务需求后,他们说这个太简单了,用Erlang几天就开发出来了,虽然最后花了大概一个礼拜,但是可见Erlang开发效率之高。现在他们应该是Erlang程序员最多的公司,而且随着业务的增长他们的开发团队也在快速扩张。一年前他们只有20个左右,现在已经解决60人了,听说还要继续招人。Good for them! 我还见到另一个在Mobile Art做Erlang开发的中国人张浩,他已经用Erlang做开发3年多了。我们聊了很多关于职业发展的问题,非常有收获。

此次大会的slides和talk都可以在这里下载

2. 关于职业生涯

除技术之外我最大的感触就是看见一群爷爷级的人物仍然热衷于参加这样的技术盛会,让我很有编程编到老的冲动。Joe Armstrong老爷子是1950年生的,早年在英国念物理PhD,后来自己钱花光了,就跑去了爱丁堡做人工智能了。他的导师Donald Michie在二战时跟图灵一起工作过,所以收藏有图灵所有的论文。Joe就在满是图灵的论文的办公室里工作了整整一年多,难怪如此之牛。做研究讲究家谱,大师之所以成为大师还是需要一些机缘在里面的(当然,独力开创一片新天地的神牛除外)。关于Joe的更多趣闻可以看《Coders at Works》,中文版应该快出版了,但是如果有条件的话还是推荐大家读英文版,边学大师的经验边学英语,一举两得,岂不快哉?如果大家好奇Joe是怎么修炼到大师级的,他自己一句话很有代表性:“So I would characterize that period, which took 20 years, as learning how to program”。这句话的上下文我就不详述了,简单地说你可以理解成他花了20年学会了如何编程(注意,这个“如何编程”可不是指精通C++之类的)。这说明要想成为大师,没有十几二十年的功力肯定是不行的。十年学会编程不是空谈,而是实实在在的。说到程序员的基本功,我必须要站出来批评一下《Coders at Works》此书在豆瓣的一个不负责任的书评,这位同学说“去他的算法内功基础,对于程序员实用主义才是王道”,这完全是误人子弟,而且可悲的是这个观点竟然有很多人支持。表面上这句话好像抓住了“实用主义”的大旗,但是这位同学却借此抨击算法基本功的重要性,实在是荒谬。(Update:该同学已经把标题改掉了)就拿Google Fellow Jeff Dean来说,他绝对算得上是实用主义的大师了吧?可是如果你去看看他关于Google整个系统架构演变过程的讲座,你就会发现把Google的那些诸如MapReduce、GFS之类的看家法宝化繁为简之后都可以还原成最基本的算法、数据结构之类的问题。Google整个架构的发展是根据需求的变化而发展而来的,MapReduce之类的不就是在遇到需要解决大规模并行编程这个问题时产生的实用的解决方案吗?可是,如果没有扎实的基本功它能被设计出来么?哪一个大师不是编程十几二十年以上?他们的基本功可能差么?想真正成为杰出的程序员,没有扎实的基本功是绝对不可能的,因为你会发现当你需要面对一个没有现成的解决方案的问题时,你的基本功就是最可信赖的法宝。

我在国内念书时确实也不知道天有多高,国内IT界有多浮躁,到了瑞典之后我有机会在Nema Labs(创业公司),Ericsson(大公司)实习,跟我的导师Per Stenström学习,与John Hughes这样的大师交流,眼界真的开阔了很多。浮躁在中国是很普遍的社会性现象,就拿程序员职业生涯发展来说,中国现在很难找到有十几二十年经验的超级程序员,为什么?因为他们都转到管理方向去了,当CEO,CTO去了。我觉得这是由中国“官本位”的社会思想导致的。大家都觉得管人的比被管的等级高,要拿更高的工资,这实在是大错特错。实际上在外国公司里终身从事技术工作的超级工程师大有人在,而且这些超级工程师的工资往往比他们的Manager高得多。在瑞典,做基站的超级工程师时薪4K多克朗的都有(克朗跟人民币几乎等值,绝对真实),50W年薪的比比皆是,这样的待遇还会让你觉得当一辈子工程师没前(钱)途吗?我觉得走管理路线本身没有错,前提是你确实喜欢管理,善于交流,适合你的性格,而不是为了职业发展“被迫”往管理方向转。在现代企业中,管理者与被管理者本身没有高低贵贱之分,只是职能不同罢了。最顶级的程序员不仅受人尊重,更可以拿高薪。可惜国内社会风气普遍浮躁,这样的状况想要改变还需要很长时间。从供需的角度来讲,超级程序员的身价是由市场需求决定的。就拿华为来说,我上次跟他们在瑞典这边的一位技术负责人聊天时了解到他们在Kista最喜欢有十几年以上经验的超级工程师,因为这样的人才国内根本招不到。为什么他们需要招这样的人?因为华为的竞争对手也是世界级的企业(例如Ericsson),这个时候科技创新就是企业最重要的核心竞争力,自然就需要最顶级的工程师才能在竞争中胜出。我们看到的Google花250W美金挽留一位女工程师的例子(未经证实,可能是Facebook负责招聘的人炒作)不也刚刚发生么?国内不也出现了年薪200W的工程师牛新庄么?我觉得随着中国IT行业的发展,科技创新将会变得越来越重要,而超级程序员也会越来越成为香饽饽,如果各位同学确实热爱编程,愿意一辈子编程,我希望你坚持下去,因为只要你成为超级程序员肯定会有赏识你的公司。现在的盛大创新院好像做的不错,他们给高级研究员年薪能有30W+,可以算是一个招聘高端人才的例子。而一个反例就是不依靠科技创新的公司(例如团购网站),它们确实是不怎么需要高端人才的,这样的公司不怎么靠技术取胜。

当然,技术不是最重要的,哪怕对Google,对Facebook也是一样。再高端的技术也必须找到市场,满足消费者的需求才能创造财富。我现在相信的是市场>管理>技术。是走管理路线还是走技术路线最好是按照你自己的性格特点来,喜欢干哪个就做哪个,而不是跟风去做管理。只要你努力,做什么都会有回报。

3. 关于英语

关于程序员个人发展,我不得不提及英语能力。我个人感觉,英语是阻碍中国程序员提升眼界的一道非常重要的关卡。关于英语于程序员之重要性,Joe在此书里面说了一句“If you are not good at English you’ll never be a very good programmer.”在欧美IT企业引领科技潮流的今天我们不去学习他们的技术怎么可能追上甚至超越他们?我建议所有有追求的程序员一定要把英语当做最基本的一门编程语言来学习!我自己的亲身经历是:英语帮我打开了另一个更广阔的世界的大门,从此直接阅读原版书酣畅淋漓的学习新知识,从此随意阅读最新的论文了解新动态,从此直接与最厉害的程序员毫无障碍的交流!

4. 创新+创业

我在最近一次Ericsson Research Day上有幸与John Hughes在Demo Session成为邻居,所以才出现了我在推上征求推友关于Erlang问题的一幕。John是从Basic开始学习编程的,在牛津念博士时就做的就是函数式编程的研究,他也是Haskell的创始人之一,95年他来到Chalmers任教至今。他学术上最有影响力的论文之一“QuickCheck: A lightweight Tool for Random Testing of Haskell Programs”成为了他后来创办的Quviq的技术核心。这个公司目前只有四名员工,当然四个人各个都是教授(我知道另一个专做编译器前端的传奇公司EDG也只有5个人)。John为人非常亲切,我跟他聊的非常开心。他追求的编程之美(好吧,我本也不想再用XX之美,但是实在没更合适的词了)是make programming easier — I like my programs to be short, beautiful, and elegant, and I hate drudgery。我还问他你编程是不是有快40年了?他老人家(其实他跟Joe都是精气神特好,非常年轻的那种)想了半天说还真有四十年了。我最羡慕他一点是,他跟我导师Per Stenström一样横跨学术界与工业界,创新与创业双管齐下,互利互惠,既是学识渊博的教授,又是能给社会创造价值的企业家,人生如此,夫复何求?我跟他说真羡慕你真能享受双倍乐趣啊,他说是啊,真是太有趣了!其实中国教授也有在工业界与学术界都取得成功的例子,例如普林斯顿的Li Kai教授和UCSD的Zhou Yuanyuan教授,所以说主要还是环境问题导致的。我个人是龙芯的坚决拥护者,很多人说怎么用MIPS的授权,怎么浪费国家的钱什么什么的,我觉得这些都是扯淡。从我知道的情况来看,龙芯他们组最近把Micro, HPCA, ISCA, ISSCC这些最顶级的会议全发了一个遍,学术水平毫无疑问!胡伟武老师用毛泽东思想来带领团队是有效的(不管是否有失偏薄),而且也有Chen Yunji这样的青年才俊,我相信至少龙芯团队培养出来的这批人才已经足以对社会做出贡献。现在龙芯商业化还处在初期阶段,任重而道远,我祝福他们,看好他们!

中国的发展需要创新!需要最高端的科技人才!需要最顶尖的程序员!

多线程程序常见Bug剖析(下)

上一篇文章我们专门针对违反原子性(Atomicity Violation)的多线程程序Bug做了剖析,现在我们再来看看另一种常见的多线程程序Bug:违反执行顺序(Ordering Violation)。

简单来说,多线程程序各个线程之间交错执行的顺序的不确定性(Non-deterministic)是造成违反执行顺序Bug的根源[注1]。正是因为这个原因,程序员在编写多线程程序时就不能假设程序会按照你设想的某个顺序去执行,而是应该充分考虑到各种可能的顺序组合,从而采取正确的同步措施。

阅读全文>>

上一篇文章我们专门针对违反原子性(Atomicity Violation)的多线程程序Bug做了剖析,现在我们再来看看另一种常见的多线程程序Bug:违反执行顺序(Ordering Violation)。

简单来说,多线程程序各个线程之间交错执行的顺序的不确定性(Non-deterministic)是造成违反执行顺序Bug的根源[注1]。正是因为这个原因,程序员在编写多线程程序时就不能假设程序会按照你设想的某个顺序去执行,而是应该充分考虑到各种可能的顺序组合,从而采取正确的同步措施。

1. 违反执行顺序(Ordering Violation)

举例来说,下面这个来自Mozilla的多线程Bug产生的原因就是程序员错误地假设S1一定会在S2之前执行完毕,即在S2访问mThread之前S1一定已经完成了对mThread的初始化(因为线程2是由线程1创建的)。事实上线程2完全有可能执行的很快,而且S1这个初始化操作又不是原子的(因为需要几个时钟周期才能结束),从而在线程1完成初始化(即S1)之前就已经运行到S2从而导致Bug。

例1:
    Thread 1                                 Thread 2
void init(...)                           void mMain(...)
{ ...                                    { ...
 S1: mThread=                              ...
      PR_CreateThread(mMain, ...);         S2: mState = mThread->State;
  ...                                      ...
}                                        }

上面这个例子是一个线程读一个线程写的情况,除此之外还有违反写-写顺序以及违反一组读写顺序的情况。例如下面这个程序,程序员错误的以为S2(写操作)一定会在S4(也是写操作)之前执行。但是实际上这个程序完全有可能先执行S4后执行S2,从而导致线程1一直hang在S3处:

例2:
    Thread 1                                 Thread 2
int ReadWriteProc(...)                   void DoneWaiting(...)
{                                        {
  ...                                     /*callback func of PBReadAsync*/
 S1: PBReadAsync(&p);
 S2: io_pending = TRUE;                   ...
  ...                                     S4: io_pending = FALSE;
 S3: while (io_pending) {...}             ...
  ...                                    }
}

下面这个是违反一组读写操作顺序的例子:程序员假设S2一定会在S1之前执行,但是事实上可能S1在S2之前执行,从而导致程序crash。

例3:
    Thread 1                                 Thread 2
void js_DestroyContext(...){             void js_DestroyContext(...){
  /* last one entering this func */      /* non-last one entering this func */
  S1: js_UnpinPinnedAtom(&atoms);          S2: js_MarkAtom(&atoms,...);
}                                        }

调试违反执行顺序这种类型的Bug最困难的地方就在只有某几种执行顺序才会引发Bug,这大大降低了Bug重现的几率。最简单的调试手段自然是使用printf了,但是类似printf这样的函数会干扰程序的执行顺序,所以有可能违反执行顺序的Bug更难产生了。我所知道的目前最领先的商业多线程Debugger是Corensic的Jinx,他们的技术核心是用Hypervisor来控制线程的执行顺序以找出可能产生Bug的那些特定的执行顺序(学生、开源项目可以申请免费使用,Windows/Linux版均有)。八卦一下,这个公司是从U of Washington发展出来的,他们现在做的Deterministic Parallelism是最热门的方向之一。

2. Ordering Violation的解决方案

常见的解决方案主要有四种:
(1)加锁进行同步
加锁的目的就在于保证被锁住的操作的原子性,从而这些被锁住的操作就不会被别的线程的操作打断,在一定程度上保证了所需要的执行顺序。例如上面第二个例子可以给{S1,S2}一起加上锁,这样就不会出现S4打断S1,S2的情况了(即S1->S4->S2),因为S4是由S1引发的异步调用,S4肯定会在{S1,S2}这个原子操作执行完之后才能被运行。

(2)进行条件检查
进行条件检查是另一种常见的解决方案,关键就在于通过额外的条件语句来迫使该程序会按照你所想的方式执行。例如下面这个例子就会对n的值进行检查:

例4:
retry:
  n = block->n;
  ...
  ...
  if (n!=block->n)
  {
    goto retry;
  }
  ...

(3)调整代码执行顺序
这个也是很可行的方案,例如上面的例2不需要给{S1,S2}加锁,而是直接调换S2与S1的顺序,这样S2就一定会在S4之前执行了!

(4)重新设计算法/数据结构
还有一些执行顺序的问题可以通过重新设计算法/数据结构来解决。这个就得具体情况具体分析了。例如MySQL的bug #7209中,一个共享变量HASH::current_record的访问有顺序上的冲突,但是实际上这个变量不需要共享,所以最后的解决办法就是线程私有化这个变量。

3. 总结

多线程Bug确实是个非常让人头痛的问题。写多线程程序不难,难的在于写正确的多线程程序。多线程的debug现在仍然可以作为CS Top10学校的博士论文题目。在看过这两篇分析多线程常见Bug的文章之后,不知道各位同学有没有什么关于多线程Bug的经历与大家分享呢?欢迎大家留言:)

需要注意的是,违反执行顺序和违反原子性这两种Bug虽然是相互独立的,但是两者又有着潜在的联系。例如,上一篇文章中我所讲到的第一个违反原子性的例子其实是因为执行顺序的不确定性造成的,而本文的第二个例子就可以通过把{S1,S2}加锁保证原子性来保证想要的执行顺序。

参考

[1] Learning from Mistakes – A Comprehensive Study on Real World Concurrency Bug Characteristics
[2] Understanding, Detecting and Exposing Concurrency Bugs
[3] Practical Parallel and Concurrent Programming
[4] Java concurrency bug patterns for multicore systems

注1:严格来讲,多线程交错执行顺序的不确定性只是违反执行顺序Bug的原因之一。另一个可能造成违反执行顺序Bug的原因是编译器/CPU对代码做出的违反多线程程序语义的乱序优化,这种“错误的优化”直接引出了编程语言的内存模型(memory model)这个关键概念。后面我会专门分析下C++与Java的内存模型,敬请期待。

多线程程序常见Bug剖析(上)

编写多线程程序的第一准则是先保证正确性,再考虑优化性能。本文重点分析多线程编程中除死锁之外的两种常见Bug:违反原子性(Atomicity Violation)和违反执行顺序(Ordering Violation)。现在已经有很多检测多线程Bug的工具,但是这两种Bug还没有工具能完美地帮你检测出来,所以到目前为止最好的办法还是程序员自己有意识的避免这两种Bug。本文的目的就是帮助程序员了解这两种Bug的常见形式和常见解决办法。

阅读全文>>

编写多线程程序的第一准则是先保证正确性,再考虑优化性能。本文重点分析多线程编程中除死锁之外的另两种常见Bug:违反原子性(Atomicity Violation)和违反执行顺序(Ordering Violation)。现在已经有很多检测多线程Bug的工具,但是这两种Bug还没有工具能完美地帮你检测出来,所以到目前为止最好的办法还是程序员自己有意识的避免这两种Bug。本文的目的就是帮助程序员了解这两种Bug的常见形式和常见解决办法。

1. 多线程程序执行模型

在剖析Bug之前,我们先来简单回顾一下多线程程序是怎么执行的。从程序员的角度来看,一个多线程程序的执行可以看成是每个子线程的指令交错在一起共同执行的,即Sequential Consistency模型。它有两个属性:每个线程内部的指令是按照代码指定的顺序执行的(Program Order),但是线程之间的交错顺序是任意的、不确定的(Non deterministic)。

我原来举过一个形象的例子。伸出你的双手,掌心面向你,两个手分别代表两个线程,从食指到小拇指的四根手指头分别代表每个线程要依次执行的四条指令。
(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等等等等)

好了,现在让我们来看看程序员在写多线程程序时是怎么犯错的。

2. 违反原子性(Atomicity Violation)

何谓原子性?简单的说就是不可被其他线程分割的操作。大部分程序员在编写多线程程序员时仍然是按照串行思维来思考,他们习惯性的认为一些简单的代码肯定是原子的。

例如:

	Thread 1						Thread 2
S1: if (thd->proc_info)				...
{							S3: thd->proc_info=NULL;
  S2: fputs(thd->proc_info,...)
}

这个来自MySQL的Bug的根源就在于程序员误认为,线程1在执行S1时如果从thd->proc_info读到的是一个非空的值的话,在执行S2时thd->proc_info的值肯定也还是非空的,所以可以调用fputs()进行操作。事实上,{S1,S2}组合到一起之后并不是原子操作,所以它们可能被线程2的S3打断,即按S1->S3->S2的顺序执行,从而导致线程1运行到S2时出错(注意,虽然这个Bug是因为多线程程序执行顺序的不确定性造成的,可是它违反的是程序员对这段代码是原子的期望,所以这个Bug不属于违反顺序性的Bug)。

这个例子的对象是两条语句,所以很容易看出来它们的组合不是原子的。事实上,有些看起来像是原子操作的代码其实也不是原子的。最著名的莫过于多个线程执行类似“x++”这样的操作了。这条语句本身不是原子的,因为它在大部分硬件平台上其实是由三条语句实现的:

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

同样,下面这个“r.Location = p”也不是原子的,因为事实上它是两个操作:“r.Location.X = p.X”和“r.Location.Y = p.Y”组成的。

struct RoomPoint {
   public int X;
   public int Y;
}

RoomPoint p = new RoomPoint(2,3);
r.Location = p;

从根源上来讲,如果你想让这段代码真正按照你的心意来执行,你就得在脑子里仔细考虑是否会出现违反你本意的执行顺序,特别是涉及的变量(例如thd->proc_info)在其他线程中有可能被修改的情况,也就是数据竞争(Data Race)[注1]。如果有两个线程同时对同一个内存地址进行操作,而且它们之中至少有一个是写操作,数据竞争就发生了。

有时候数据竞争可是隐藏的很深的,例如下面的Parallel.For看似很正常:

Parallel.For(0, 10000, 
    i => {a[i] = new Foo();})

实际上,如果我们去看看Foo的实现:

class Foo {
	private static int counter;
	private int unique_id;
	public Foo()
       {
		unique_id = counter++;
       }
}

同志们,看出来哪里有数据竞争了么?是的,counter是静态变量,Foo()这个构造函数里面的counter++产生数据竞争了!想避免Atomicity Violation,其实根本上就是要保证没有数据竞争(Data Race Free)。

3. Atomicity Violation的解决方案

解决方案大致有三(可结合使用):
(1)把变量隔离起来:只有一个线程可以访问它(isolation)
(2)把变量的属性定义为immutable的:这样它就是只读的了(immutability)
(3)同步对这个变量的读写:比如用锁把它锁起来(synchronization)

例如下面这个例子里面x是immutable的;而a[]则通过index i隔离起来了,即不同线程处理a[]中不同的元素;

Parallel.For(1,1000, 
i => {
    a[i] = x;
});

例如下面这个例子在构造函数中给x和y赋值(此时别的线程不能访问它们),保证了isolation;一旦构造完毕x和y就是只读的了,保证了immutability。

public class Coordinate
{
   private double x, y;

   public Coordinate(double a,
                     double b)
   {
      x = a;
      y = b;
   }
   public void GetX() {
      return x; 
   }
   public void GetY() {
      return y; 
   }
}

而我最开始提到的关于thd->proc_info的Bug可以通过把S1和S2两条语句用锁包起来解决(同志们,千万别忘了给S3加同一把锁,要不然还是有Bug!)。被锁保护起来的临界区在别的线程看来就是“原子”的,不可以被打断的。

	Thread 1						Thread 2
LOCK(&lock)
S1: if (thd->proc_info)				LOCK(&lock);
{							S3: thd->proc_info=NULL;
  S2: fputs(thd->proc_info,...)		UNLOCK(&lock);
}
UNLOCK(&lock)

还有另一个用锁来同步的例子,即通过使用锁(Java中的synchronized关键字)来保证没有数据竞争:

“Java 5 中提供了 ConcurrentLinkedQueue 来简化并发操作。但是有一个问题:使用了这个类之后是否意味着我们不需要自己进行任何同步或加锁操作了呢?
也就是说,如果直接使用它提供的函数,比如:queue.add(obj); 或者 queue.poll(obj);,这样我们自己不需要做任何同步。”但是,两个原子操作合起来可就不一定是原子操作了(Atomic + Atomic != Atomic),例如:

if(!queue.isEmpty()) {  
   queue.poll(obj);  
}  

事实情况就是在调用isEmpty()之后,poll()之前,这个queue没有被其他线程修改是不确定的,所以对于这种情况,我们还是需要自己同步,用加锁的方式来保证原子性(虽然这样很损害性能):

synchronized(queue) {  
    if(!queue.isEmpty()) {  
       queue.poll(obj);  
    }  
}  

但是注意了,使用锁也会造成一堆Bug,死锁就先不说了,先看看初学者容易犯的一个错误(是的,我曾经也犯过这个错误),x在两个不同的临界区中被修改,加了锁跟没加一样,因为还是有数据竞争:

int x = 0;
pthread_mutex_t lock1;
pthread_mutex_t lock2;

pthread_mutex_lock(&lock1);
x++;
pthread_mutex_unlock(&lock1);
...
...
pthread_mutex_lock(&lock2);
x++;
pthread_mutex_unlock(&lock2);

事实上,类似x++这样的操作最好的解决办法就是使用类似java.util.concurrent.atomic,Intel TBB中的atomic operation之类的方法完成,具体的例子可以参考这篇文章

总结一下,不管是多条语句之间的原子性也好,单个语句(例如x++)的原子性也好都需要大家格外小心,有这种意识之后很多跟Atomicity Violation相关的Bug就可以被避免了。其实归根结底,我们最终是想让多线程程序按照你的意愿正确的执行,所以在清楚什么样的情形可能让你的多线程程序不能按你所想的那样执行之后我们就能有意识的避免它们了(或者更加容易的修复它们)。下一篇文章我们再来仔细分析下Ordering Violation。

[注1] 严格意义上来讲,Data Race只是Atomicity Violation的一个特例,Data Race Free不能保证一定不会出现Atomicity Violation。例如文中Java实现的那个Concurrent Queue的例子,严格意义上来讲它并没有data race,因为isEmpty()和poll()都是线程安全的调用,只不过它们组合起来之后会出现违反程序员本意的Atomicity Violation,所以要用锁保护起来。

P.S. 参考文献中的前两篇是YuanYuan Zhou教授的得意门生Dr. Shan Lu的论文,后者现在已经是Wisconsin–Madison的教授了。