选择合适的同步原语最大限度减少开销

摘要

如果线程在一个同步点等待,那么它们无法做有用功。然而,多线程程序中通常需要一定程度的同步化,明确的同步有时甚至优于数据复制或复杂的非阻塞调度算法,然而其本身也存在一些问题。当前市场上存在着大量同步技术,应用程序开发人员应选择一种适当的技术,从而最大限度地降低整体同步开销。

本文是《英特尔® 多线程应用开发指南》的一部分,该系列文章为开发面向英特尔? 平台的高效多线程应用提供了指导。

背景

同步本身可构建序列执行,因此限制了并行能力,而且可能降低整体应用性能。事实上,当前只有很少的多线程程序能够完全避免同步。但幸运的是,我们可通过选择合适的结构来减少与同步有关的系统开销。本文将阐述一些可用的解决方案,针对每个解决方案提供示例代码,并列举出它们的主要优缺点。

Win32* 同步 API

Win32 API 提供了几种保护原子性(atomicity)的机制,本章节主要讨论其中的 3 种。一个增量语句(increment statement )(例如 = var++)说明了不同的结构。如果正在更新的变量在线程之间共享,那么加载→写入→存储指令必须为原子操作(即操作完成之前不能抢占指令序列。)下面的代码演示了如何使用这些 API。

#include 

CRITICAL_SECTION cs; /* InitializeCriticalSection called in main() */
HANDLE mtx;  /* CreateMutex called in main() */
static LONG counter = 0;

void IncrementCounter ()
{
  // Synchronize with Win32 interlocked function
  InterlockedIncrement (&counter);

  // Synchronize with Win32 critical section
  EnterCriticalSection (&cs);
    counter++;
  LeaveCriticalSection (&cs);

  // Synchronize with Win32 mutex
  WaitForSingleObject (mtx, INFINITE);
    counter++
  ReleaseMutex (mtx);
}

比较这三种机制,进而说明哪种机制在各种同步方案中更为适合。Win32 互锁函数(InterlockedIncrement、InterlockedDecrement、InterlockedExchange、InterlockedExchangeAdd、InterlockedCompareExchange)仅限于简单操作,但它们比关键区域更快。此外,需要调用的函数更少;进出一个 Win32 关键区域需要调用 EnterCriticalSection、 LeaveCriticalSection 或者 WaitForSingleObject 和 ReleaseMutex。互锁函数也同样无阻碍,但如果同步对象不可用,那么 EnterCriticalSection和WaitForSingleObject(或WaitForMultipleObjects)将阻碍线程。

如果需要一个关键区域,那么在一个 Win32 CRITICAL_SECTION 上实现同步化所需的开销远远低于实现 Win32 mutex、信号量和 event HANDLE 同步化所需的花费,因为前者是用户空间对象,而后者是内核空间对象。尽管 Win32 关键区比 Win32 mutexes 要快,然而它们并可通用。同其它内核对象一样,Mutexes 也可用于流程内同步化。采用 WaitForSingleObject 和 WaitForMultipleObjects 函数也将有等待时间。线程在指定时间期限结束后继续执行,而不是为获取一个互斥体而无限期等待。将等待时间设置为零,以便线程可无阻碍地测试一个互斥体是否可用。(请注意,使用 TryEnterCriticalSection 函数也可以无阻碍地检测一个 CRITICAL_SECTION 是否可用。)最后,如果一个线程终止而同时带有一个互斥体,操作系统将会发出信号进行处理,从而防止等待线程成为死锁。如果一个线程终止而带有 CRITICAL_SECTION,那么等待进入 CRITICAL_SECTION 的线程变为死锁。

当一个 Win32 线程试图获取一个已被另一线程持有的 CRITICAL_SECTION 或 mutex HANDLE 时,它会立即将 CPU 让与操作系统。通常来说,这是一个好现象。线程受到阻碍,CPU 可做有用功。然而,阻碍和疏通一个线程的开销较大。有时,线程在受阻塞之前试图再次获得锁则更具优势(例如,在 SMP 系统中,在较小的关键段)。Win32 CRITICAL_SECTION 具有一个用户可配置的自旋计数,用以控制放弃 CUP 之前线程的等待时间。InitializeCriticalSectionAndSpinCount 和 SetCriticalSectionSpinCount 函数为试图进入一个特定 CRITICAL_SECTION 的线程设定自转计数。

建议

例如,针对变量(例如增量、减量、交换量)的简单操作而采用速度更快、开销更低的 Win32 互锁函数。

当流程间需要同步化或时间等待,使用 Win32 mutex,信号量或 event HANDLE。否则请使用系统开销更低的 Win32 CRITICAL Sections。

使用 InitializeCriticalSectionAndSpinCount 和 SetCriticalSectionSpinCount 函数来控制 Win32 CRITICAL_SECTION 的自转计数。在放弃 CPU 之前,控制等待线程自转时间对于低争用和高争用关键区域尤为重要。自转计数可显著影响 SMP 系统和采用英特尔® 超线程技术处理器的性能。

英特尔® 线程构建模块同步化 API

英特尔® 线程构建模块(英特尔® TBB)针对原子操作提供了便携式包装器(模板类原子)和不同版本的互斥机制,其中包括在一个“原生”互斥体周围的包装器。鉴于前面已经讨论了采用原子操作和依赖于操作系统的同步化 API 的优势与不足,本章节将跳过tbb::原子 和 tbb::互斥体,而将重点放在快速的用户级同步化类别,例如 spin_mutex、queuing_mutex、spin_rw_mutex 和 queuing_rw_mutex。

最简单的互斥为 spin_mutex。一个线程在获取 spin_mutex 上的锁之前将会保持等待状态。当只针对少数指令保留锁时,spin_mutex 例如,下面的代码使用一个互斥体 FreeListMutex 来保护一个共享的变量空闲表。

Node* FreeList;
typedef spin_mutex FreeListMutexType;
FreeListMutexType FreeListMutex;

Node* AllocateNode()
{
  Node* n;
  {
    FreeListMutexType::scoped_lock lock(FreeListMutex);
    n = FreeList;
    if( n )
    FreeList = n->next;
  }
  if( !n )
    n = new Node();
  return n;
}

scoped_lock 的构造函数将会一直等待,直到 FreeListMutex 上没有其它的锁。析构函数释放锁。AllocateNode 函数内另外的大括号的作用是尽可能缩短锁的生命周期,因此其它等待的线程才能尽快有机会获得锁。

英特尔 TBB 提供的另一个用户级自转互斥是 queuing_mutex,它也是用户级互斥,但与 spin_mutex 相比,queuing_mutex 更为公平。一个公平的互斥体让线程有秩序地抵达。公平互斥避免了“挨饿”线程,因为每个线程均能轮到。不公平互斥较公平互斥的速度更为快些,因为它们首先让正在运行的线程通过,而不是按顺序通过,因此部分线程可能会因中断而进入睡眠状态。如果非常注重可扩展性和公平性,那么应该采用队列互斥体(Queuing mutex)。

并非所有共享数据的访问都需要相互排斥。在大多数实际应用中,对并发数据结构的访问通常是读取访问,只有少部分是写入访问。对于这样的数据结构,读取者之间的相互排斥是没有必要的,这样的序列是可以避免的。英特尔 TBB 读/写锁允许许多读取者进入到关键区域,只有写入者线程能够获得一个排斥访问。忙碌等待读/写互斥体的不公平版本为 spin_rw_mutex,其公平版本为queuing_rw_mutex。读/写互斥体提供与 spin_mutex 和 queuing_mutex 相同的 scoped_lock API,此外它还提供特殊函数,允许一个读锁升级至一个写锁,或将一个写锁降级至一个读锁。

建议

成功地选择合适的同步机制的关键是了解您的应用,其中包括正在处理的数据和处理的方式。

如果关键区域仅有几个指令,并且无需顾及公平性问题,那么应选择 spin_mutex。如果关键区域空间较小,但需要线程按照抵达顺序访问关键区域,那么应使用 queuing_mutex。

如果大多数并发数据访问为读取访问,并且仅有小部分线程需要写入访问数据,则可以使用读/写锁来帮助避免不必要的序列化,从而提高整体应用性能。

使用准则

当连续调用 Win32 互锁函数时,请注意线程抢占问题。例如,当执行多线程时,下列代码段不会针对局部变量生成相同的值。

static LONG N = 0;
LONG localVar;
…
InterlockedIncrement (&N);
InterlockedIncrement (&N);
InterlockedExchange (&localVar, N);

static LONG N = 0;
LONG localVar;
…
EnterCriticalSection (&lock);
 localVar = (N += 2);
LeaveCriticalSection (&lock);

例如,若使用互锁函数,那么任意函数调用之间的线程抢占都可能会产生无法预期的后果。关键区域比较安全,因为原子操作(例如更新全球变量 N 并分配到局部变量)可得到保护。

为了确保安全,无论是采用 CRITICAL_SECTION 变量还是 mutex HANDLE 构建的 Win32 关键区域仅有一个进出点。进入关键区将使同步化失效。跳出一个关键区域而不调用 LeaveCriticalSection 或 ReleaseMutex 将使等待线程变为死锁。单一进出点同样产生清晰代码。

防止线程在终止时持有 CRITICAL_SECTION 变量的情况发生,因为这种情况将会导致等待线程变为死锁。

其它资源

有关编译器优化的更完整信息,请参阅优化通知
类别: