Yebangyu's Blog

Fond of Concurrency Programming , Distributed System and Machine Learning

【翻译】深入探索并发编程系列(一):锁不慢;锁竞争慢

译者按

Preshing 的博客是学习并发编程的不可多得的资料,讲解比较详细。身边的很多朋友从中受益良多。

我们在和作者沟通后,获得了授权,着手翻译了他的博客,刊登在这里,以飨朋友诸君。

和一般的翻译不同,我们加上了独家的注释。注释要么是纠正错误,要么是辅助理解,要么是补充扩展;相信对大家会大有裨益。

正文翻译:@Diting0x

审校 && 注释:@睡眼惺忪的小叶先森

原文地址: Preshing

原文

锁(也叫互斥量)在很长一段时间都被误解了。1986年,在Usenet的有关于多线程的讨论会中,Matthew Dillon说过:大多数人都对锁有个误解,认为锁是慢的。25年后,这种误解似乎在某一时间段又突然出现了。

在某些平台上或者当锁被高度竞争时,锁确实慢。另外,当你在开发一个多线程程序时,由于锁的引入,给性能带来巨大的瓶颈是很常见的。但这并不意味着所有的锁都是缓慢的。我会在这篇文章中解释,有的时候,使用锁的策略反而能带来非常好的性能。

大家对锁的误解可能源自于某个最容易忽视的原因:不是所有的程序员都会意识到轻量级锁和内核锁的区别。我会在下一篇文章中对轻量级锁做专门介绍:总是使用轻量级锁。在这篇文章中,假设你在Windows平台下做C/C++开发,你需要的正是一个Critical Section对象。

有时候,锁是慢的这个结论是由benchmark支撑的。例如,这篇文章在高负载状态下来测试锁的性能:每个线程必须持有锁来完成任何一项任务(高竞争),并且锁都是在极短的时间间隔下被持有(高频率)。这种方式似乎很完美,但在实际应用中,却要避免这种使用锁的方式注1。基于这种考虑,我设计了一种benchmark,同时包含对锁使用的最坏情况和最好情况。

由于一些其它的考虑,大家可能不愿意用锁了。存在一系列的技术被称为无锁编程(或者不含锁编程注2)。无锁编程是极具挑战性的,但其本身可以在许多实际应用场景下带来高度的性能回报。据我所知,有些程序员会花费许多天甚至几周的时间来设计某种无锁算法,之后再做一系列测试,但在几个月后才发现隐藏的bug. 风险与回报并存对于相当一部分程序员都是有诱惑力的,这当然也包括我,在以后的几篇文章中会提到这些。有了无锁编程的诱惑,大家开始觉得锁使用起来很枯燥,缓慢并且非常糟糕。

但也不能把锁贬的一文不值。在现实软件中,当大家为了保护内存分配器的时候,锁就是一个让人敬仰的东西。Doug Lea的分配器是在游戏开发中非常著名的内存分配器注3,但其只支持单线程,这时候我们就必须使用锁机制来进行保护。在游戏运行时,经常会碰到多个线程抢占一个内存分配器,每秒钟抢占次数可达到15000次左右。在加载过程中,每秒钟会达到100000次甚至更多。虽然这并不是个大问题。但你却可以看到,锁能非常出色的来处理这些负载。

锁竞争benchmark

在这次测试中,我们创建一个线程来生成随机数,采用传统的Mersenne Twister生成器来实现。此线程时而获取锁,时而释放锁。获取与释放锁的间隔时间是随机的,但它都很接近我们提前决策出的平均值。举个例子,假设我们要每秒钟获取锁15000次,让持有锁的时间保持在总时间的50%. 下图是部分的timeline。红色说明锁正在被持有,灰色说明锁被释放。

MUTEX1

这是个泊松分布过程。如果我们知道生成单个随机数的平均时间–在2.66GHz的四核Xeon处理器上需要6.349ns–那么我们用工作单元(work units)而不是秒来衡量时间。可以用我之前的文章中介绍的方法,How to Generate Random Timings for a Poisson Process,算出获取与释放锁的时间间隔有多少个工作单元。下面代码是C++的实现。我省略了一些细节,喜欢的话,可以在 这里 下载完整的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
QueryPerformanceCounter(&start);
for (;;)
{
    // Do some work without holding the lock
    workunits = (int) (random.poissonInterval(averageUnlockedCount) + 0.5f);
    for (int i = 1; i < workunits; i++)
        random.integer();       // Do one work unit
    workDone += workunits;

    QueryPerformanceCounter(&end);
    elapsedTime = (end.QuadPart - start.QuadPart) * ooFreq;
    if (elapsedTime >= timeLimit)
        break;

    // Do some work while holding the lock
    EnterCriticalSection(&criticalSection);
    workunits = (int) (random.poissonInterval(averageLockedCount) + 0.5f);
    for (int i = 1; i < workunits; i++)
        random.integer();       // Do one work unit
    workDone += workunits;
    LeaveCriticalSection(&criticalSection);

    QueryPerformanceCounter(&end);
    elapsedTime = (end.QuadPart - start.QuadPart) * ooFreq;
    if (elapsedTime >= timeLimit)
        break;
}

现在假设我们运行两个这样的线程,每个线程运行在不同的CPU核心上。当执行任务时,每个线程有一半的时间是持有锁的,但如果其中一个线程在另一个线程持有锁的情况下试图获取锁,此线程会被强制等待。这就是锁竞争。

MUTEX2

在我看来,这是锁在实际程序中应用的非常好的例子。当我们运行上述的场景时,可以发现每个线程会花费25%的时间在等待,75%的时间在执行实际的任务。与单线程相比,两个线程都获得了1.5X的性能提升。

我在2.66GHZ的四核Xeon处理器上做过不同的测试,从一个线程到两个线程,一直到最多四个线程的情况,每个线程都分别运行在不同的CPU核心上。同时,我还改变锁被持有的时间,从锁绝不被持有,到每个线程必须100%的时间持有锁。在所有的case中,锁频率保持一个常数–在执行任务过程中,线程每秒钟获取锁15000次。

MUTEX3

结果很有意思。对于短的锁持有时间,比如持有时间占比<10%的情况, 系统可能达到很高的并发性。虽然不是最完美的并发,但很接近。说明锁是非常快的!

为了把结果解释清楚一些,我用这个分析器分析了多线程游戏引擎中的内存分配锁.在游戏运行时,每秒钟有15000个锁来自三个线程,锁的持有时间在2%左右。正好落在图表中左侧的舒适区(comfort zone).

这些结果都表明一旦锁持有时间超过90%,就没有必要再使用多线程了。这时,单线程会表现的更好。同时,最让人吃惊的是4个线程的性能都急剧下降到60%左右。这看起来像是个异常情况,所以我又重新运行这些测试很多次了,甚至还改变了测试顺序。得到的结果却是一样的。我对此最好的解释就是,测试可能触碰到了Windows分配器的盲区,我没有更进一步的去研究这个问题。

锁频率benchmark

一个轻量级锁也会带来开销。正如我的下一篇文章中说的,对Windows Critical Section的lock/unlock成对操作会花费23.5ns(基于上述测试的CPU). 因此可以说明,每秒钟有15000个锁已经足够少了,锁的开销并不会在很大程度上影响整个结果。但如果我们提高锁频率,又会发生什么呢?

算法中,严格控制锁与锁之间执行的任务数,因此我做了一系列新的测试:锁与锁的间隔时间从10ns到最高31ns(相对应每秒钟大约32000次锁).每次测试都使用两个线程。

MUTEX4

正如你想的那样,锁频率很高的话,锁本身的开销就已经高于所执行的任务本身了. 在网上找到的一些benchmarks,包括前面提到的那个分析器, 都落在图表中的右下角。在这些高频率下,和一些CPU指令的规模一样,锁的间隔比较小。好消息是,当锁与锁之间的任务比较简单的时候,无锁编程更可行。

与此同时,结果表明当锁频率达到每秒钟32000次时(锁间隔是3.1us)也是可以接受的。在游戏开发中,内存分配器就可能会在加载过程中达到这个频率。如果锁间隔比较短暂,你仍然可以得到1.5X的并发度。

我们已经了解了一系列锁性能的例子:有性能表现的很好的时候,也有性能慢的跟爬虫似的时候。我已经证明了游戏引擎中的内存分配器一直都能保持非常好的性能。把这个例子运用到实际场景中,不能说锁是慢的。不得不承认,锁很容易被滥用,但你不必太害怕–只要经过仔细的分析,任何情况下都能找出导致性能瓶颈的因素。当你正在考虑锁有多可靠,并去理解锁的相关优化方法时(相比无锁编程),锁有时候表现的真的非常出色。

写这篇文章的目的是为了让锁得到应有的尊敬–欢迎批评指正。锁在工业应用程序中有广泛的应用,至于锁的性能,并不总是能达到一个很好的均衡。如果你在自己的经验中发现类似这样的例子,非常乐意看到你的评论注4

译者注

注释1:一种避免或者降低锁冲突的科学思想是partition,避免资源集中。例如,对于hashtable,可以由之前的一个hashtable对应一把锁,改为每个bucket配置一把锁,这样冲突将大大降低。再例如,计数程序,如果大家都对同一个全局变量进行读写而加一把锁,那么冲突严重,可以适当的选择多个计数器,不同的线程累加对应的计数器,一个线程负责将这些计数器的值求和。等等等等。

注释2: 这里的无锁编程,原文为lock free。不含锁编程,原文为lockless。但是需要注意的是,lock free并不是无锁的意思,它的本质是说一组线程,总有(至少)一个线程能make progress,和有没有锁没有本质联系。lock free目前一般都翻译为无锁(有些地方也翻译为锁无关),因此本文也采用这种译法,但是读者需要特别注意。另外lockless就是真正的无锁、不包含锁的编程。

注释3: Doug Lea是并发编程的大牛,《Java并发编程实战》的作者之一,非常乐意分享。他写的这个分配器非常出名,glibc所采用的内存分配器实现就是基于他设计的算法。

注释4: 本文的描述和试验可能让人有点迷糊,这里提供一下Paul E. McKenney大叔在他的著作《Is Parallel Programming Hard, And, If So, What Can You Do About It?》中第4章中的例子来解释,让读者更好的理解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
pthread_rwlock_t rwl = PTHREAD_RWLOCK_INITIALIZER;
int holdtime = 0;
int thinktime = 0;
long long *readcounts;
int nreadersrunning = 0;
#define GOFLAG_INIT 0
#define GOFLAG_RUN  1
#define GOFLAG_STOP 2
char goflag = GOFLAG_INIT;
void *reader(void *arg)
{
   int i;
   long long loopcnt = 0;
   long me = (long)arg;
   __sync_fetch_and_add(&nreadersrunning, 1);
   while (ACCESS_ONCE(goflag) == GOFLAG_INIT) {
     continue;
   }
   while (ACCESS_ONCE(goflag) == GOFLAG_RUN) {
     if (pthread_rwlock_rdlock(&rwl) != 0) {
       perror("pthread_rwlock_rdlock");
       exit(-1);
     }
     for(i=1;i<holdtime;i++){
       barrier();
     }
     if (pthread_rwlock_unlock(&rwl) != 0) {
       perror("pthread_rwlock_unlock");
       exit(-1);
     }
     for (i=1;i<thinktime;i++) {
       barrier();
     }
     loopcnt++;
   }
   readcounts[me] = loopcnt;
   return NULL;
}

其中16-18行等待测试开始的信号;19行开始测试;holdtime控制临界区的长短,thinktime用来控制两次申请锁之间的间隔。测试的时候有三个变量:holdtime、thinktime、线程数(1个、2个、4个、直到核数的两倍)。试试看。