锁的开销

我在学习多线程编程的时候,得到的第一条关于性能忠告是锁的开销很大。由此引发了三个问题:有多大,为什么以及如何尽量避免。


在计算机里,“很大”实在是一个太过于模糊的概念。比如同样是函数调用,在一个移动APP的大部分地方,我们会鼓励尽量把大的函数拆分以便于阅读和理解代码,而如果这个APP包含一个视频codec,里边为了效率会尽量避免在循环里做函数调用,甚至会把循环展开减少跳转的次数来优化处理器流水线。所以笼统的说某个操作“开销很大”没太大的意义,只有比较精确的测量出实际的开销有多大,我们才能决定使用的方式和优化机制。

锁开销的测量

我们针对的是多线程环境下的锁机制,基于linux做测试。每种编程语言提供的锁机制都不太一样,不过无论如何,最终都会落实到两种机制上,一是处理器提供的原子操作指令(现在一般是CAS—compare and swap),处理器会用轮询的方式试图获得锁,在处理器(包括多核)架构里这是必不可少的机制;二是内核提供的锁系统调用,在被锁住的时候会把当前线程置于睡眠(阻塞)状态。

实际上我们在编程的时候并不会直接调用这两种机制,而是使用编程语言所带函数库里的锁方法,锁方法内部混合使用这两种机制。以pthread库(NPTL)的pthread_mutex来举例,一把锁本质上只是一个int类型的变量,占用4个字节内存并且内存边界按4字节对齐。加锁的时候先用trylock方法(内部使用的是CAS指令)来尝试获得锁,如果无法获得锁,则调用系统调用sys_futex来试图获得锁,这时候如果还不能获得锁,当前线程就会被阻塞。

java之类的语言会使用看起来和pthread_mutex很不一样的锁机制(比如synchronise),但是实际上底层还是通过pthread_mutex的方法来加锁,或者是混合使用CAS和sys_futex—和pthread_mutex差不多。

所以很容易得到一个结论,如果锁不存在冲突,每次获得锁和释放锁的处理器开销仅仅是CAS指令的开销,在x86-64处理器上,这个开销只比一次内存访问(无cache)高一点(大概是1.3倍)。以我现在在使用的MacBoolPro为例,内存的规格是DDR3-1600,实际的时钟频率为800MHz,每个时钟周期1.25ns;突发的内存访问存在8个时钟周期的延迟(这个延迟的缩写也是CAS,参考https://en.wikipedia.org/wiki/CAS_latency),也就是10ns的内存访问延迟,这样算下来,CAS指令的开销大改是十多个ns。

确定一件事情最好的方法是实际测试和观测它,让我们写一段代码来测试无冲突时锁的开销,核心代码大概是这样:

1
2
3
4
5
while(c < MAX) {
pthread_mutex_lock(&mutex);
c = c + 1;
pthread_mutex_unlock(&mutex);
}

其实就是循环的lock和unlock。运行五亿次以后,计算耗时为14.5s左右,平摊到每次加锁/解锁操作大改是14ns每次加锁/解锁(扣除很少的一点循环开销)。这个数值和CAS指令的理论开销吻合得很好。

在锁冲突的情况下,开销就没有这么小了。首先pthread_mutex_lock会真正的调用sys_futex来进入内核来试图加锁,被锁住以后线程会进入睡眠,这带来了上下文切换和线程调度的开销。可以写两个互相解锁的线程来测试这个过程的开销,
代码: https://github.com/tsuna/contextswitch/blob/master/timetctxsw.c
在单核和双核机器上分别测试(都是在一台2.5GHz的Core i5上用vmware建的虚拟机,运行ubuntu linux)。在单核机器上消耗大约1080ns而双核机器上消耗大约3400ns,双核机器上锁冲突的开销大概是单核的3倍。
另外一个c程序可以用来测试“纯上下文切换”的开销,线程只是使用sched_yield来放弃处理器,并不进入睡眠。
代码:https://github.com/tsuna/contextswitch/blob/master/timetctxsw2.c
结论很惊人,在单核处理器上,“纯上下文切换”只消耗了大概150ns。

锁开销的来源

这样我们大致可以把锁冲突的开销分成三部分,“纯上下文切换”开销,大概是150ns,调度器开销(把线程从睡眠变成就绪或者反过来)大概是900ns,在多核系统上,还存在跨处理器调度的开销,那部分开销很大,超过2000ns。在真实的应用场景里,还要考虑上下文切换带来的cache不命中和TLB不命中的开销,开销只会进一步加大。

锁的优化

锁的实现方式对我们的优化方向给予了很好的提示,让我们回想一下--先用一个快的操作(每秒7000万次)来测试锁是否冲突,再用一个慢的操作来实际加锁(每秒30万次)。所以真正消耗时间的不是上锁的次数,而是锁冲突的次数。减少锁冲突的次数才是提升性能的关键。
使用更细粒度的锁,可以减少锁冲突。这里说的粒度包括时间和空间,比如哈希表包含一系列哈希桶,为每个桶设置一把锁,空间粒度就会小很多--哈希值相互不冲突的访问不会导致锁冲突,这比为整个哈希表维护一把锁的冲突机率低很多。减少时间粒度也很容易理解,加锁的范围只包含必要的代码段,尽量缩短获得锁到释放锁之间的时间,最重要的是,绝对不要在锁中进行任何可能会阻塞的操作。使用读写锁也是一个很好的减少冲突的方式,读操作之间不互斥,大大减少了冲突。
锁本身的行为也存在进一步优化的可能性,sys_futex系统调用的作用在于让被锁住的当前线程睡眠,让出处理器供其它线程使用,既然这个过程的消耗高达几千ns,也就是说如果被锁定的时间不超过这个数值的话,根本没有必要进内核加锁--释放的处理器时间还不够消耗的。sys_futex的时间消耗够跑二百多次compare and swap的,也就是说,对于一个锁冲突比较频繁而且平均锁定时间比较短的系统,一个值得考虑的优化方式是先循环调用compare and swap来尝试获得锁(这个操作也被称作自旋锁),在若干次失败(一般是一百次左右)后再进入内核真正加锁。当然这个优化只能在多处理器的系统里起作用(得有另一个处理器来解锁,否则自旋锁无意义)。在glibc的pthread实现里,通过对pthread_mutex设置PTHREAD_MUTEX_ADAPTIVE_NP属性就可以使用这个机制;在Java世界的HotSpot虚拟机里,可以用-XX:PreBlockSpin来设置自选锁尝试的次数。