锁的开销 | xbay

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

在计算机里，“很大”实在是一个太过于模糊的概念。比如同样是函数调用，在一个移动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。

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

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来设置自选锁尝试的次数。