基于循环数组的无锁队列

引言

最近对于注重性能的应用程序,我们有了一种能显著提高程序性能的选择:多线程.线程的概念实际上已经存在了很长时间.在过去,多数计算机只有一个处理器,线程主要用于将一个大的任务拆分成一系列更小的执行单元.以使得当其中某些执行单元因为等待资源而被阻塞的时候剩余的执行单元能继续执行。举个示例,一个网络应用程序,它监听一个TCP端口,当有外部请求到达时,处理请求.对于一个单线程的应用程序来说,只能在处理完一个请求之后再处理另外的请求,显然这个应用程序对用户非常不友好,它为一个用户服务的时候别的用户就只能干等.而对于多线程解决方案,我们可以让另外的线程来处理接收到的请求,主线程继续等待在服务端口上接受新的请求.

在只有一个处理器的机器上,一个多线程应用程序可能无法达到我们对它的预期.因为所有的线程都要争抢处理器以获得执行机会.而它的性能说不定比一个用单线程方式去解决同样问题的程序还要差,因为线程之间的通讯和数据共享也有不小的开销.

而在一个对称多处理器机器上(SMP),一个多线程应用可以真正的实现多任务并行执行.每个线程都可以拥有单独的处理器以获得执行的机会,不需要再像单处理器一样,必须要等到处理器空闲才能获得执行机会.对一个有N个处理器的SMP系统来说,理论上一个N线程的应用程序只需要它的单线程版本的1/N的时间就可以完成相同的任务(实际上这个理论值是无法达到的,因为线程之间的通讯和数据共享有不小的开销).

SMP的机器在过去是非常昂贵的,只有一些大公司和组织才能负担得起.而现今,多核心处理器已经相当廉价(现今市场上的pc处理器至少都拥有一个以上的核心),所以让应用程序并行化以提高性能现在已经变得非常流行.

但是编写多线程应用程序显然不是一件简单的事.线程之间需要共享数据,互相通信,很快你就会发现又要面对以前就遇到过的老问题:死锁, 对共享数据的非法访问,多线程动态分配/释放内存等.如果你足够幸运,参与到一个对性能有极高要求的项目中,你将会遇到更多导致性能不达标的问题:

  • Cache颠簸(Cache trashing)
  • 在同步机制上的争抢.队列
  • 动态内存分配

本文主要介绍一种基于数组实现的无锁队列用于解决上述三个性能问题,特别是动态内存分配,因为此无锁队列最初的设计目的就是为了解决这个问题.

线程同步如何导致性能下降

Cache颠簸

线程是(wikipedia):"操作系统可以调度运行的最小的执行单元".每种操作系统都有不同的线程实现方式,基本来说,进程拥有一组指令集(代码)和一段内存,线程执行一个代码片段但与包含它的进程共享内存空间.对Linux来说,线程是另一种"执行上下文", 它没有线程的念.Linux通过标准的进程来实现线程.Linux内核没有提供特殊的调度语义或数据结构用于表示线程.线程只是一个与其它进程共享某些资源的普通进程[1].

每一个运行中的任务/线程或成为执行上下文,使用了一组CPU寄存器,包含各种内部状态的数据,如当前正在执行的指令所在的内存地址,当前正在执行操作的操作数和/或操作结果,栈指针等等.所有的这些信息被统称为"上下文".任何抢占式操作系统(几乎所有现代操作系统都是抢占式的)都必须具备几乎在任何时刻停止一个正在运行的任务并在将来将它恢复运行的能力(有些例外情况,例如一个进程声明它在某一段时间内是不可被抢占的).一但任务恢复执行,它会从上次停止的地方继续执行,就好像从来没被打断过一样.这是一件好事,所有的任务共享处理器,当一个任务在等待I/O时,它被其它任务抢占.即使一个单处理的系统也表现得与多处理系统一样,但是如在现实生活中一样,没有免费的午餐:因为处理器被共享,每次任务抢占都有额外的开销用于保存被抢占任务的上下文,将获得运行权的任务的上下文恢复.

在保存和恢复上下文的过程中还隐藏了额外的开销:Cache中的数据会失效,因为它缓存的是将被换出任务的数据,这些数据对于新换进的任务是没用的.处理器的运行速度比主存快N倍,所以大量的处理器时间被浪费在处理器与主存的数据传输上.这就是在处理器和主存之间引入Cache的原因.Cache是一种速度更快但容量更小的内存(也更加昂贵),当处理器要访问主存中的数据时,这些数据首先被拷贝到Cache中,因为这些数据在不久的将来可能又会被处理器访问.Cache misses对性能有非常大的影响,因为处理器访问Cache中的数据将比直接访问主存快得多.

因此每当一个任务被抢占,Cache中的内容都需要被接下来获得运行权的进程覆盖,这意味着,接下来运行的进程需要花费一定的时间来将Cache预热才能达到良好的运行效率(某些操作系统,例如Linux,尝试将进任务恢复到它被抢占时运行的处理器上以减缓这个预热的开销).当然这并不意味任务抢占是坏事,抢占机制使得操作系统得以正常的工作.但对某些系统而言,线程被频繁抢占产生的Cache颠簸将导致应用程序性能下降.

一个运行中的任务在什么情况下会被抢占?这依赖于你所使用的操作系统,但一般来说,中断处理,定时器超时,执行系统调等,有极大的可能导致操作系统考虑将处理器的使用权交给系统中的其它进程.这实际上是操作系统要处理的一个难题,一方面,没人愿意有进程因为无法获得处理器而长期处于饥饿状态.另一方面,有些系统调用是阻塞的,这意味着一个任务向操作系统请求某些资源,这个任务要等待请求的资源被准备好,因为它需要这些资源以执行后续的操作.这是任务抢占的一个正面的例子,因为在资源被准备好之前那个任务将无所事事,操作系统可以将它投入到等待状态,将处理器让给其它任务运行.

资源一般来说指的是在内存,磁盘,网络或外设中的数据,但一些会导致阻塞的同步机制,例如信号量和互斥锁也可以被认为是资源.当一个任务请求获得一个已经被其它任务持有的互斥锁,它将被抢占,直到那个请求的互斥锁被释放,它才会被重新投入到可运行任务队列中.所以如果你担心你的进程被过于频繁的抢占,你应该尽量避免使用会导致阻塞的同步机制.

但是,显然一切没那么简单.如果你使用多于物理处理器数量的线程来执行计算密集型的任务,并且不使用任何会导致阻塞的同步机制,你的系统的响应及时性将变差(操作延时加大).因为操作系统切换任务的次数越少意味着当前处于非运行状态的进程需要等待更长的时间,直到有一个空闲的处理器使得它能恢复执行.而你的应用程序很可能也会受到影响,因为它可能在等待某个线程执行完一些计算才能进行下一步的处理,而那个线程却无法获得处理器来完成它的计算,导致所有其它的线程都在等待它.没有通用的方法解决所有这些问题,这通常依赖于你的应用程序,机器和操作系统.例如对一个实时的计算密集型应用程序,我会选择避免使用导致阻塞的同步机制,同时使用更少的线程.而对于那些需要花费大量时间等待外部(例如网络)数据到来的应用程序,使用非阻塞同步机制可能会杀死你.每种方法都有自己的优点和缺点,一切皆取决于你是如何使用的.

在同步机制上的争抢.队列

队列可被应用到大多数多线程解决方案中.如果两个或更多的线程需要通过有序事件来进行交流,我脑子里第一个跳出来的就是队列.简单易懂,使用方便,被良好的测试.世界上任何一个程序员都要面对队列.它们无处不在.

队列对一个单线程应用程序来说,使用非常简便,对它做一些简单的处理就可以适用于多线程的应用.你所需要的只是一个非线程安全的队列(例如C++的std::queue)和一种阻塞的同步机制(例如互斥锁和条件变量).我随本文一起附上一个用 glib编写的简单的阻塞队列.虽然没有任何必要去重复发明轮子,glib中已经包含了一个线程安全的队列GAsyncQueue[7],但这段代码展示了如何将一个标准队列转换成线程安全的队列.

让我们来看一下这个队列中最常用的几个方法的实现: IsEmpty, PushPop.最基本的存储队列使用的是 std::queue它被声明为成员变量, std::queue m_theQueue.我使用glib的互斥锁和条件变更量的封装来作为同步机制( GMutex* m_mutexCond* m_cond).可以与本文一起被下载的队列实现中还包括了 TryPushTryPop两个方法,它们在队列已满或为空的时候不会阻塞调用线程.

当队列中没有元素的时候 IsEmpty返回true,在任何线程可以访问到不安全的队列实现之前,必须首先获得互斥锁.这意味着调用线程会被阻塞直到互斥锁被释放.

Push将一个元素插入队列尾部.调用线程将会阻塞,如果有其它线程持有互斥锁.如果队列已满调用线程也会阻塞直到有一个线程从队列中 Pop一个元素出列.

Pop将队首元素出列,调用线程将会阻塞,如果有其它线程持有互斥锁.如果队列已满调用线程也会阻塞直到有一个线程 Push一个元素到队列中.

如我在前面的章节中解释过的,阻塞不是微不足道的操作.它导致操作系统暂停当前的任务或使其进入睡眠状态(等待,不占用任何的处理器).直到资源(例如互斥锁)可用,被阻塞的任务才可以解除阻塞状态(唤醒).在一个负载较重的应用程序中使用这样的阻塞队列来在线程之间传递消息会导致严重的争用问题.也就是说,任务将大量的时间(睡眠,等待,唤醒)浪费在获得保护队列数据的互斥锁,而不是处理队列中的数据上.

在最简单的情形下,只有一个线程向队列插入数据(生产者),也只有一个线程从队列中提取数据(消费者),这两个线程争用保护队列的互斥锁.我们也可以把我们的实现从只使用一个互斥锁改为使用两个,一个用于插入数据一个用于提取数据.使用这种方式则只有在队列为空或满的时候才会发生争抢.但是如果有多于一个线程插入数据和提取数据,那么我们的问题又回来了.生产者们和消费者们还是需要继续争抢各自互斥锁.

这种情况下,非阻塞机制大展伸手的机会到了.任务之间不争抢任何资源,在队列中预定一个位置,然后在这个位置上插入或提取数据.这中机制使用了一种被称之为CAS(比较和交换)的特殊操作,这个特殊操作是一种特殊的指令,它可以原子的完成以下操作:它需要3个操作数m,A,B,其中m是一个内存地址,操作将m指向的内存中的内容与A比较,如果相等则将B写入到m指向的内存中并返回true,如果不相等则什么也不做返回false.例如:

使用CAS实现无锁队列已经不是什么新鲜事物了.有很多实现的方案,但大多数都是使用链表的实现.有兴趣的读者可以查看[2][3]或[4].
虽然本文的目的不是描述这种实现,但做一个简单的介绍还是有必要的:

  • 向队列中插入一个元素会动态分配一个新的节点,通过CAS操作将这个节点插入到队列中
  • 移除元素首先通过CAS操作移动链表的指针将节点出列,然后再访问那个出列节点中的数据.

下面是一个简单的基于链表实现的无锁队列(从[2]中拷贝过来的,它的实现基于[5])

在不支持垃圾回收的编程语言中,最后的 g_slice_free调用是不安全的,具体原因可以参看ABA问题:

首先假设队列中只有一个节点,q->head = N1,q->tail = N2,其中N1是哨兵节点

  • 1 线程T1在执行完 data = next->data;之后被暂停.此时next = N2,head = N1
  • 2 线程T2执行 queue_dequeue将节点(N1)出列,并将节点(N1)的内存释放,操作完成后,q->head = N2,q->tail = N2,N2是哨兵节点
  • 3 线程T2执行 queue_enqueue,产生的节点(N3)与(N1)内存地址一致(内存被重用),操作完成后,q->head = N2,q->tail = N3 = N1
  • 4 线程T2再次执行 queue_dequeue,操作完成后q->head = q->tail = N3 = N1,N1重新变会哨兵节点
  • 4 T1恢复执行,接下来执行CAS成功(head = q->head = N1).而实际上此时队列已经为空,没有元素可供出列.

ABA问题可以通过给每个节点增加引用计数来解决.在执行CAS操作之前首先要检查计数值以确定操作的是一个正确的节点.好消息是本文提供的这个无锁链表队列实现没有ABA问题,因为它没有使用动态内存分配.

动态内存分配

在多线程系统中,需要仔细的考虑动态内存分配.当一个任务从堆中分配内存时,标准的内存分配机制会阻塞所有与这个任务共享地址空间的其它任务(进程中的所有线程).这样做的原因是让处理更简单,且它工作得很好.两个线程不会被分配到一块相同的地址的内存,因为它们没办法同时执行分配请求.显然线程频繁分配内存会导致应用程序性能下降(必须注意,向标准队列或map插入数据的时候都会导致堆上的动态内存分配)

存在一些非标准库,提供了无锁内存分配机制,以减少多线程对堆的争抢,例如libhoard[6].除此之外还有更多的其它选择,你可以将标准的C++分配器替换成这些无锁内存分配器,它们可能会大大的提高你的应用程序的性能.

基于循环数组的无锁队列

终于到了本文的重点部分,基于循环数组的无锁队列解决了上一节中提到的3个问题,首先概括一下基于循环数组的无锁队列的特性:

  • 作为一种无锁同步机制,它显著降低了任务抢占的频率,因此有效减缓了cache颠簸.
  • 如所有其它无锁队列一样,线程之间的争抢显著降低,因为它不需要锁去保护任何数据结构:线程所要做的就是索要一块空间,然后将数据写进去.
  • 队列的操作不会导致动态内存分配
  • 没有ABA问题,只是在数组处理上需要一些额外的开销.

它是如何工作的?

队列的实现使用了一个数组和3个作用不同的下标:

  • writeIndex:新元素入列时存放位置在数组中的下标
  • readIndex:下一个出列元素在数组中的下标
  • maximumReadIndex:最后一个已经完成入列操作的元素在数组中的下标.如果它的值跟writeIndex不一致,表明有写请求尚未完成.这意味着,有写请求成功申请了空间但数据还没完全写进队列.所以如果有线程要读取,必须要等到写线程将数完全据写入到队列之后.

必须指明的是使用3种不同的下标都是必须的,因为队列允许任意数量的生产者和消费者围绕着它工作.已经存在一种基于循环数组的无锁队列,使得唯一的生产者和唯一的消费者可以良好的工作[11].它的实现相当简洁非常值得阅读.

Push

以下插图展示了对队列执行操作时各下标是如何变化的。如果一个位置被标记为X,标识这个位置里存放了数据.空白表示位置时空的。对于下图的情况,队列中存放了两个元素。WriteIndex指示的位置是新元素将会被插入的位置,ReadIndex指向的位置中的元素将会在下一次pop操作中被弹出。

Alt text

当生产者准备将数据插入到队列中,它首先通过增加WriteIndex的值来申请空间,MaximumReadIndex指向最后一个存放有效数据的位置(也就是实际的队列尾)。

Alt text

一旦空间的申请完成,生产者就可以将数据拷贝到刚刚申请到的位置中,完成之后增加MaximumReadIndex使得它与WriteIndex的一致。

Alt text

现在队列中有3个元素,接着又有一个生产者尝试向队列中插入元素。

Alt text

在第一个生产者完成数据拷贝之前,又有另外一个生产者申请了一个新的空间准备拷贝数据.现在有两个生产者同时向队列插入数据。

Alt text

现在生产者开始拷贝数据,在完成拷贝之后,对MaximumReadIndex的递增操作必须严格遵循一个顺序:第一个生产者线程首先递增MaximumReadIndex,接着才轮到第二个生产者。这个顺序必须被严格遵守的原因是,我们必须保证数据被完全拷贝到队列之后才允许消费者线程将其出列。

Alt text

第一个生产者完成了数据拷贝,并对MaximumReadIndex完成了递增,现在第二个生产者可以递增MaximumReadIndex了

Alt text

第二个生产者完成了对MaximumReadIndex的递增,现在队列中有5个元素。

Pop

以下插图展示了元素出列的时候各种下标是如何变化的,队列中初始有2个元素。WriteIndex指示的位置是新元素将会被插入的位置,ReadIndex指向的位置中的元素将会在下一次pop操作中被弹出。

Alt text

消费者线程拷贝数组ReadIndex位置的元素,然后尝试用CAS操作将ReadIndex加1,如果操作成功消费者成功的将数据出列,因为CAS操作是原子的,所以只有唯一的线程可以在同一时刻更新ReadIndex的值。如果操作失败,读取新的ReadIndex值,重复以上操作(copy数据,CAS)。

Alt text

现在又有一个消费者将元素出列,队列变成空。

Alt text

现在有一个生产者正在向队列中添加元素,它已经成功的申请了空间,但尚未完成数据拷贝,任何其它企图从队列中移除元素的消费者都会发现队列非空(因为writeIndex不等于readIndex)。但它不能读取readIndex所指向位置中的数据,因为readIndex与MaximumReadIndex相等。消费者将会在do循环中不断的反复尝试,直到生产者完成数据拷贝增加MaximumReadIndex的值,或者队列变成空(这在多个消费者的场景下会发生)。

Alt text

当生产者完成数据拷贝,队列的大小是1,消费者线程可以读取这个数据了。

性能测试

下面的对比图展示了测试程序在2核心的机器上,不同设置和不同线程配置的测试数据。

第2个CAS操作对性能造成的影响

一个已知道的问题是在单一生产者的情况下,第2个CAS将对性能产生影响。下图对比了单生产者优化的队列和任意生产者队列(值越小越好)。

从对比图可以看出,单生产者优化的版本有30%的性能提升。

Alt text

无锁 vs 阻塞队列

下图的测试是在各种线程配置下,并发的插入和移除100W元素所花费的时间(越小越好,队列的数组大小初始为16384)。

在单生产者的情况下,无锁队列战胜了阻塞队列,而随着生产者数量的增加,无锁队列的效率迅速下降。

Alt text

4线程的效率

下面的图,展示了在不同线程数量的配置下,不同的队列执行100W次push和pop操作的性能对比。

一个生产者线程

Alt text

两个生产者线程

Alt text

三个生产者线程

Alt text

一个消费者线程

Alt text

两个消费者线程

Alt text

三个消费者线程

Alt text

使用一台4核心的机器

强烈推荐你在一台拥有4个核心的机器上执行上述测试,这样你就可以观察sched_yield()对性能产生的影响。

结论

基于数组的无锁队列的两个版本已经被证明可以正常的工作,一个版本是多生产者线程安全的,另一个版本是单生产者但可以有多消费者。两个版本的队列都可以安全的作为多线程应用程序的同步机制使用,因为:

  • CAS操作是原子的,线程并行执行push/pop不会导致死锁;
  • 多生产者同时向队列push数据的时候不会将数据写入到同一个位置,产生数据覆盖;
  • 多消费者同时执行pop不会导致一个元素被出列多于1次;
  • 线程不能将数据push进已经满的队列中,不能从空的队列中pop元素;
  • push和pop都没有ABA问题;

但是,虽然这个队列是线程安全的,但是在多生产者线程的环境下它的性能还是不如阻塞队列。因此,在符合下述条件的情况下可以考虑使用这个队列来代替阻塞队列:

  • 只有一个生产者线程;
  • 只有一个频繁操作队列的生产者,但偶尔会有其它生产者向队列push数据;

 

 

参考链接:

https://www.cnblogs.com/sniperHW/p/4172248.html

 

 

 

 

 

Leave a Reply

Your email address will not be published.