深入探索并发编程系列1 : 锁不慢；锁竞争慢

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核心上。当执行任务时，每个线程有一半的时间是持有锁的，但如果其中一个线程在另一个线程持有锁的情况下试图获取锁，此线程会被强制等待。这就是锁竞争。

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

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

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

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

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

锁频率benchmark

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

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

正如你想的那样，锁频率很高的话，锁本身的开销就已经高于所执行的任务本身了. 在网上找到的一些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章中的例子来解释，让读者更好的理解：

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个、直到核数的两倍）。试试看。