多核并行计算中锁机制的影响研究

徐永新

（华为技术有限公司 江苏省南京市 210012）

随着摩尔定律的逐渐失效，CPU 往多核、众核方向发展，单一CPU 上集成的核数越来越多。随着核数增加，锁对性能的影响也越来越显著。根据阿姆达尔定律，多核并行计算的效率受限于流程中的串行处理部分，串行部分越大，则加速比提升的越慢。因此，学术界及工业界都在千方百计减少多核多线程场景下串行执行流程的处理时间，其中锁是一种比较典型的串行执行场景。锁的存在将导致多线程的执行性能降低。

在某些对事件响应有较高实时性要求的场合，锁的存在也会影响线程对特定事件的响应时间。某线程在尝试获取锁的过程中，存在时间不确定性，可能需要较短或者较长时间才能获取到锁，这种执行时间的不确定，将导致线程对具体业务时延的不确定。

1 锁的种类

在多核并行计算场景中，处于不同核上的多线程尝试访问一个公共资源的时候，往往需要加锁操作。根据业务线程访问共享资源的不同特征，需要合理选择不同的锁机制来配合完成业务的特定功能。

1.1 自旋锁

自旋锁是一种获取不到资源时在原地忙等，以期获取到共享资源的锁机制。

一个线程想要获取被自旋锁保护的共享资源的时候，必须先得到锁，使用完共享资源的时候，必须释放锁。在获取锁的时候，如果该共享资源没有被任何其他线程占有，则直接获取该锁；反之，如果该资源已被其他线程占有，则申请者会在原地自旋等待，即忙等，不断循环检测该锁是否可以被获取。忙等状态，CPU 一直处于空转而不休眠，浪费了CPU 资源。

自旋锁的优点是不会导致调用线程的休眠，没有线程切换的开销。自旋锁适合于持有锁的时间特别短的场合。如果锁的粒度较小，其他线程忙等的时间也较短，对CPU 的浪费可以控制在一个较小的范围内。

1.2 互斥锁

互斥锁的功能和自旋锁类似，不同之处在于互斥锁获取不到共享资源的时候，线程不会在原地等待，而会处于休眠阻塞状态。

使用互斥锁获取不到共享资源的线程会被阻塞，此时将发生上下文切换，操作系统会调度其他线程来运行，从而不会浪费该核的处理时间。当共享资源被释放的时候，操作系统又会重新调度等待在该共享资源的线程来运行。

互斥锁的优点是等锁阶段不会导致CPU 空转，缺点是会有上下文切换的开销，所以互斥锁适用于持有锁时间相对较长的场合。

1.3 读写锁

读写锁把对共享资源的访问，分成了读者和写者，读者只会对共享资源进行读操作，而写者只会对共享资源做写操作。

读写锁相对于自旋锁来说，能提高并发读的效率，因为读写锁允许多个读者同时进行访问。在任意一个时刻，只允许一个写者进行写操作，而这个写者在获取锁之前，必须等其他的所有读者或者写者释放锁。

读写锁适合于读多写少的场合，这种情况下，多个读者并发访问能提升多核的并发性能。

1.4 顺序锁

顺序锁是对读写锁的一种改进，允许写操作更高的优先级，即使有读者正在进行读操作，也允许写者同时进行写操作。这样的好处是写者不用等待，可以更快的做数据的更新。

为了保证读者写者数据的一致性，读者需要在读取操作的前后分别读取一次顺序计数器，如果两次读取该计数器的值都是一样的，说明期间没有发生写操作，读到的数据是有效的。反之，说明读到的数据是无效的，因为写者已经改写了顺序计数器，需要读者重新读取一次。

顺序锁适用于需要写者及时更新数据的场合，且写者不能频繁更新数据。

1.5 基于CAS的免锁

CAS（或Compare And Swap）是CPU 所支持的一种原子操作，其本质上是一种乐观锁，线程每次都假设没有冲突，直接去操作某个值，提交新的值时再检测有没有冲突，如果没有冲突就提交成功，如果有冲突就失败重新尝试，直到尝试成功为止。

CAS 操作可以有效减少多线程并行执行情况下锁的粒度。CAS操作包含三个操作数：内存位置、预期原值、新值。比如队列的入队操作，要改变队头指针head 的值，使用CAS 操作的伪码如下：

如果队头head 的内存地址里面的值和current 值相等，说明没有其他线程来改动该值，将内存里面的值换成新的值；反之，不相等则说明已经被其他线程改过了，需要重新从队头取值并重新尝试。这个判断和新值的替换是一个不可分割的原子操作。

CAS 操作完全不受操作系统行为的影响，所以该机制可以很好解决死锁，饿死，优先级反转等问题。

图1：基于悲观锁机制的实验方案

图2：基于CAS 机制的实验方案

图3：基于无锁机制的实验方案

2 锁机制的对比实验

为了对比几种典型锁机制对多核并发计算性能的影响，笔者设计了一组实验，在多核多线程场景下，分别采用不同的锁机制访问公共资源，测量相应的性能数据。

在实验中，公共资源是一个环形队列，该队列的每一个元素都指向一个固定大小的缓冲区，该缓冲区存放待处理的数据。每个核上绑定一个线程，该线程需要从环形队列的队头取出缓冲区的数据进行处理，并将处理完毕之后的缓冲区放回环形队列的尾部。

2.1 基于悲观锁的方案

悲观锁是一种持有保守态度的锁，每次操作都会对临界区做上锁操作，而得不到锁的线程就会处于等待状态直到它得到锁。在线程越多的情况下，发生锁竞争的可能性也越大。

图4：一秒钟内入队出队次数统计

在该实验方案中，多个线程绑定在不同的核上，每个核都使用自旋锁来竞争公共的环形队列。入队出队操作都要加锁操作。其示意图如图1所示。

2.2 基于CAS操作的方案

基于CAS 操作的实验方案中，多个线程并发执行出队操作时，同时尝试修改head 值，操作成功的线程获得了队头元素，失败的线程则重新尝试。入队操作也是采用一样的方式并发修改tail 值。其示意图如图2所示。

2.3 基于无锁的方案

无论采用悲观锁还是乐观锁，多个线程并发操作时，都会存在冲突的情况。作为对比，在基于无锁机制的方案中，每个线程都独立拥有一个环形队列。这样，每个线程都能完全并行的执行入队出队操作，线程之间不存在锁冲突。其示意图如图3所示。

3 实验数据

笔者在AMD Ryzen 5 4600H CPU 上构建了多线程测试程序，每个线程绑定一个核，测试程序中使用延时模仿业务流程处理。其主流程伪码如下：

针对自旋悲观锁实现，基于CAS 操作的实现，以及基于无锁机制的实现，分别使用1～6 个线程测出了一组对比数据。

3.1 性能比较数据

测试程序在一秒钟时间内入队出队次数统计如图4所示。

由图4 中可见，随着核数的增加，悲观锁机制入队出队次数逐渐增加，后由于冲突的增大，其性能反而降低。CAS 机制的入队出队性能也经历了从低到高再到低的过程。无锁机制随着核数增加，其性能基本呈现线性增长。

3.2 耗时比较数据

测试程序统计了在一秒钟时间内，入队操作操作消耗的平均cycle 数，其结果如图5所示。

由图5 中可见，随着核数的增加，基于悲观锁的机制消耗的平均cycle 数逐渐增加。基于CAS 的机制消耗的平均cycle 数也逐渐增加，不过比悲观锁要好。而无锁的机制随着核数增加，其消耗的cycle 数基本保持稳定。

4 结语

从实验数据可以看出，无锁机制性能表现最好，悲观锁的性能表现最差，而基于CAS 的乐观锁表现居中。因此，为了减少锁对性能影响，实际业务中一般存在下面几种锁优化手段：

（1）减少锁的粒度；

（2）合理选择锁的类型；

（3）尽量选择免锁或无锁算法。

锁的存在对并行程序性能有较大的影响，只有根据具体的场合，合理选择相应类型的锁机制，才能把对性能的影响降低到最低。