无锁编程与有锁编程的性能对比与分析

 

      最近维护的一个网络服务器遇到性能问题，于是就对原有的程序进行了较大的框架改动。改动最多的是线程工作模式与数据传递方式，最终的结果是改变锁的使用模式。经过一番改进，基本上可以做到GMb网卡全速工作处理。在性能达标之后，一度在想有没有什么办法使用更加轻量级锁，或者去掉锁的使用，为此搜索一些相关的研究成果，并做了一些实验来验证这些成果，因而就有这篇文章。希望有做类似工作的同行可以有所借鉴。如果有人也有相关的经验，欢迎和我交流。

 

1 无锁编程概述

      本节主要对文献[1]进行概括，做一些基础知识的介绍。

      所谓有锁编程，就是当你需要共享数据的时候，你需要有序的去访问，所有改变共享数据的操作都必须表现出原子的语义，即便是像++k，这种操作也需要使用锁进行。有锁编程面临时效率的下降、死锁、优先级反转等问题，都需要设计者小心的进行优化和解决。本文并不对这三个问题进行讨论。

      在无锁编程中，并不是说所有操作都是原子的，只有一个很有限的操作集是原子的，这就意味着无锁编程十分困难。那么这个有限的操作集是否存在，存在的话包含哪些原子操作呢？2003年Maurice Herlihy的一篇论文”Wait-Free Synchronization”[3]解决了这个问题。这里给出文章的结论，文章指出像test-and-set,swap,fetch-and-add甚至是原子队列对于多线程而言都无法做到lock-free。而最朴素最简单的原语CAS(compare-and-swap)操作即可以完成所有的无锁功能，其他的如LL/SC (load linked/storeconditional)。CAS的伪码如下：

template <class T>bool CAS(T* addr, T expected, T value) { if (*addr == expected) { *addr = value; return true; } return false;}  

      CAS将expected与一个内存地址进行比较，如果比较成功，就将内存内容替换为new。当前大多数机器都在硬件级实现了这个操作，在Inter处理器上这个操作是CMPXCHG，因而CAS是一个最基础的原子操作。

      wait-free / lock-free 与 有锁对比

      wait-free的过程可以通过有限步骤完成，而不管其他线程的速度。

      lock-free的过程保证至少一个线程在执行，其他线程可能会被延迟，但系统整体仍在前进。

      有锁的情况下，如果某个线程占有锁，则其他线程就无法执行。更普通的，有锁需要避免死锁和活锁的情况。 

2 无锁编程的相关研究与进展

       本节内容对文献[2]进行概述，介绍当前已经实现的无锁算法与数据结构。

        近二十年来研究者们对lock-free和wait-free的算法和数据结构进行了大量的研究。实现了一些wait-free和lock-free的算法，比如FIFO的队列和LIFO的栈，而更复杂的优化级队列、hash表及红黑树的lock-free算法也渐渐为人所知。

        无锁算法的实现都依赖内存屏障，因而具有平台相关性。下面将列举目前已经较为成熟的原子操作和算法数据结构的实现。

• MidiShare Source Code is available under the GPL license. MidiShare includes implementations of lock-free FIFO queues and LIFO stacks.
• Appcore is an SMP and HyperThread friendly library which uses Lock-free techniques to implement stacks, queues, linked lists and other useful data structures. Appcore appears currently to be for x86 computers running Windows. The licensing terms of Appcore are extremely unclear.
• Noble – a library of non-blocking synchronisation protocols. Implements lock-free stack, queue, singly linked list, snapshots and registers. Noble is distributed under a license which only permits non-commercial academic use.
• lock-free-lib published under the GPL license. Includes implementations of software transactional memory, multi-workd CAS primitives, skip lists, binary search trees, and red-black trees. For Alpha, Mips, ia64, x86, PPC, and Sparc.
• Nonblocking multiprocessor/multithread algorithms in C++ (for MSVC/x86) posted by Joshua Scholar to musicdsp.org, and are presumably in the public domain. Included are queue, stack, reference-counted garbage collection, memory allocation, templates for atomic algorithms and types. This code is largely untested. A local mirror is here.
• Qprof includes the Atomic_ops library of atomic operations and data structures under an MIT-style license. Only available for Linux at the moment, but there are plans to support other platforms. download available here
• Amino Concurrent Building Blocks provides lock free datastructures and STM for C++ and Java under an Apache Software (2.0) licence.

      其中Noble已经进行了商业化，License相当不便宜。

3 性能分析

      本节对PTHREAD中的mutex，windows中的原子增，及CAS原子操作进行对比，并对MidiShare中实现的无锁FIFO队列与基于STL的list实现的有锁队列进行的性能对比和分析，并对优化方式进行了总结。

3.1 原子增的性能测试

      测试机CPU为Intel E5300 2.60GHZ

      首先是对简单的递增操作进行了测试，分别对无任何同步机制的++操作、pthread_mutex保护的++操作，以及CAS的语义实现的atomic_add1()以及windows下的interlockedIncrease()进行了单个线程情况下的定量测试。 

i++	3.2亿
lock(p_mutex);i++;unlock(p_mutex);	2千万
CAS_atomic_add1(i)	4千万
interlockedIncrease(&i)	4千万

      首先在无任何同步情况下，CPU可以每秒执行++操作3.2亿次，接近于CPU的主频速率。而每次++时执行thread_mutex_lock()及unlock()操作情况下，CPU每秒只能执行2千万次，这就是说CPU每秒钟可以执行加锁及解锁操作共4千万次，加解锁的开销是执行加法指令的的15倍左右。而CAS的情况稍好，为每秒4千万次。这个速度与windows下的interlockedIncrease()的执行速度十分近似。

      从上面的测试结果来看，windows下的原子增操作与CAS实现的增操作代价基本是相同的，估计windows底层也是借助汇编指令CMPXCHG的CAS来实现原子增操作的。当然pthread_mutex作为一种互斥锁，也是拥有相当高的效率的，在没有锁突然的情况下，加锁开销与一次CAS的开销相当。

      但如果对比无同步的++操作，硬件级的同步也造成了至少8倍的性能下降。

      接着，对pthread_mutex的程序进行了逻辑优化，分别测试了++执行8次、20,100次进行一次加解锁的情况。

lock();for(k=0;k<8;i++,k++);unlock()	1.2亿
lock();for(k=0;k<20;i++,k++);unlock()	2亿
lock();for(k=0;k<100;i++,k++);unlock()	3.4亿

      结果CPU每秒钟可以执行++的次数为1.2亿/2亿/3.4亿，这种情况与预期是一致的，因为每秒钟调用加解锁的次数分别是原来的1/8、1/20和1/100，当执行100次++进行一次加解锁后，性能已经达到了无任何同步时的性能。当然原子的interlockedIncrease()和CAS实现的atomic_add1()都不具备这种批量处理的改进优势，无论如果，它们最好的执行情况已经固定了。

对于在单线程与多线程的情况下的windows下的原子操作的性能测试情况，可以参考文献[4]，这里只列出其中的结论。其所列的测试机CPU为Intel2.66GHZ双核处理器。

      单个线程执行2百万次原子增操作

interlockedIncrease	78ms
Windows CriticalSection	172ms
OpenMP的lock操作	250ms

      两个线程对共享变量执行2百万次原子增操作

interlockedIncrease	156ms
Windows CriticalSection	3156ms
OpenMP的lock操作	1063ms

3.2 无锁队列与有锁队列的性能测试

      这里测试的无锁列队由MidiShare实现的，而有锁队列是通过pthread_mutex与c++的STL list共同实现。这里只列出测试结果。

      对于存储相同的数据的情况下，从主线程enque并从子线程deque，计算每秒钟enque/deque的次数，当然二者基本上是相同的。

      无锁队列的性能在150w -200w次入队操作，这个性能已经无法再有任何提高，因为每次入队出队操作都是硬件级的互斥。而对于有锁队列，根据每次加解锁之间处理入队的次数的不同，有以下的结果：

lock();for(k=0;k<x;i++,k++);unlock()	结果(次/s)
x=1	40万
x=10	190万
x=128	350万
x=1000	400万
x=10000	396万

      这说明通过对锁之间的数据进行批处理，可以极大的提高系统的性能，而使用原子操作，则无法实现批处理上的改进。

4 结论

      通过上面的无锁和有锁的性能测试，可以得出这样的结论，对于CAS实现的硬件级的互斥，其单次操作性能比相同条件下的应用层的较为高效，但当多个线程并发时，硬件级的互斥引入的代价与应用层的锁争用同样令人惋惜。因此如果纯粹希望通过使用CAS无锁算法及相关数据结构而带来程序性能的大量提升是不可能的，硬件级原子操作使应用层操作变慢，而且无法再度优化。相反通过对有锁多线程程序的良好设计，可以使程序性能没有任何下降，可以实现高度的并发性。

      但是我们也要看到应用层无锁的好处，比如不需要程序员再去考虑死锁、优先级反转等棘手的问题，因此在对应用程序不太复杂，而对性能要求稍高时，可以采用有锁多线程。而程序较为复杂，性能要求满足使用的情况下，可以使用应用级无锁算法。

     至于如何对多线程的工作模式进行更好的调度，可以参考文献[5]，文献介绍了一种较好的线程间合作的工作模式，当然前提是机器的处理器个数较多，足以支持多组线程并行的工作。如果处理器个数较，较多的线程之间在各个核心上来回调度增加了系统上下文切换的开销，会导致系统整体性能下降。

 

参考文献

[1] Lock-Free Data Structures http://www.drdobbs.com/184401865

[2] Some notes on lock-freewait-free algorithms http://www.rossbencina.com/code/lockfree

[3] Wait-Free Synchronization http://www.podc.org/dijkstra/2003.html

[4] OpenMP创建线程中的锁及原子操作性能比较 http://blog.163.com/kangtao-520/blog/static/772561452009510751068/

[5] 多核编程中的线程分组竞争模式 http://kangtao-520.blog.163.com/blog/static/77256145200951074121305/