Xbox 360 和 Microsof Windows 的无锁编程注意事项

  • 项目

无锁编程是一种在多个线程之间安全共享更改数据的方法，无需获取和释放锁。 这听起来像是灵丹妙药，但无锁编程是复杂而微妙的，有时并不能带来它所承诺的好处。 Xbox 360 上的无锁编程特别复杂。

无锁编程是多线程编程的有效技术，但不应轻取使用。 在使用之前，必须了解复杂性，并且应仔细测量，以确保它确实能带来预期的收益。 在许多情况下，有更简单、更快的解决方案，例如共享数据的频率较低，应改用。

正确且安全地使用无锁编程需要对硬件和编译器有大量了解。 本文概述了尝试使用无锁编程技术时要考虑的一些问题。

使用锁编程

编写多线程代码时，通常需要在线程之间共享数据。 如果多个线程同时读取和写入共享数据结构，则可能发生内存损坏。 解决此问题的最简单方法是使用锁。 例如，如果一次只能由一个线程执行 ManipulateSharedData，则可以使用 CRITICAL_SECTION 来保证这一点，如以下代码所示：

// Initialize
CRITICAL_SECTION cs;
InitializeCriticalSection(&cs);

// Use
void ManipulateSharedData()
{
    EnterCriticalSection(&cs);
    // Manipulate stuff...
    LeaveCriticalSection(&cs);
}

// Destroy
DeleteCriticalSection(&cs);

此代码相当简单明了，很容易判断它是正确的。 但是，使用锁编程有几个潜在的缺点。 例如，如果两个线程尝试获取相同的两个锁，但以不同的顺序获取它们，则可能会出现死锁。 如果某个程序持有锁定时间过长（由于设计不佳或线程已被优先级较高的线程交换掉），则其他线程可能会被阻塞很长时间。 此风险在 Xbox 360 上尤其大，因为软件线程由开发人员分配了一个硬件线程，并且操作系统不会将它们移动到另一个硬件线程，即使其中一个线程处于空闲状态。 Xbox 360 也没有针对优先级反转的保护，高优先级线程在等待低优先级线程释放锁时循环旋转。 最后，如果延迟的过程调用或中断服务例程尝试获取锁，则可能会出现死锁。

尽管存在这些问题，同步基元（如关键部分）通常是协调多个线程的最佳方法。 如果同步基元太慢，最佳解决方案通常是降低使用频率。 但是，对于那些能够承受额外复杂性的人来说，另一个选项是无锁编程。

无锁编程

顾名思义，无锁编程是一系列技术，用于在不使用锁的情况下安全地操作共享数据。 有无锁算法可用于传递消息、共享列表和数据队列以及其他任务。

执行无锁编程时，必须应对两个挑战：非原子操作和重新排序。

非原子操作

原子操作是不可分割的，即保证其他线程在操作完成一半时永远不会看到该操作。 原子操作对于无锁编程非常重要，因为如果没有它们，其他线程可能会看到半写入的值，或者其他不一致的状态。

在所有新式处理器上，可以假定自然对齐本机类型的读取和写入是原子的。 只要内存总线至少与正在读取或写入的类型一样宽，CPU 会在单个总线事务中读取和写入这些类型，从而使其他线程无法看到它们处于半完成状态。 在 x86 和 x64 上，不能保证大于 8 个字节的读取和写入是原子的。 这意味着流式处理 SIMD 扩展 (SSE) 寄存器和字符串操作的 16 字节读取和写入可能不是原子操作。

不自然对齐的类型读取和写入（例如，写入跨越四字节边界的 DWORD）不保证是原子的。 CPU 可能必须以多个总线事务的形式执行这些读取和写入操作，这可能允许另一个线程修改或查看读取或写入中间的数据。

复合操作（例如递增共享变量时发生的读取-修改-写入序列）不是原子操作。 在 Xbox 360 上，这些操作以多个指令 (lwz、addi 和 stw) 实现，线程可以在序列中部分交换出来。 在 x86 和 x64 上，有一个指令 (inc) ，可用于递增内存中的变量。 如果使用此指令，则递增变量在单处理器系统上是原子的，但在多处理器系统上仍不是原子变量。 在基于 x86 和 x64 的多处理器系统上使 inc 原子需要使用锁前缀，这会阻止另一个处理器在 inc 指令的读取和写入之间执行自己的读取-修改-写入序列。

以下代码显示了部分示例：

// This write is not atomic because it is not natively aligned.
DWORD* pData = (DWORD*)(pChar + 1);
*pData = 0;

// This is not atomic because it is three separate operations.
++g_globalCounter;

// This write is atomic.
g_alignedGlobal = 0;

// This read is atomic.
DWORD local = g_alignedGlobal;

保证原子性

可以通过组合以下各项来确保使用原子操作：

  • 自然原子操作
  • 用于包装复合操作的锁
  • 实现常用复合操作的原子版本的操作系统函数

递增变量不是原子操作，如果在多个线程上执行递增可能会导致数据损坏。

// This will be atomic.
g_globalCounter = 0;

// This is not atomic and gives undefined behavior
// if executed on multiple threads
++g_globalCounter;

Win32 附带一系列函数，这些函数提供多个常见操作的原子读取-修改-写入版本。 这些是 InterlockedXxx 系列函数。 如果共享变量的所有修改都使用这些函数，则修改将是线程安全的。

// Incrementing our variable in a safe lockless way.
InterlockedIncrement(&g_globalCounter);

重组

一个更微妙的问题是重新排序。 读取和写入并不总是按照你在代码中编写的顺序发生，这可能会导致非常混乱的问题。 在许多多线程算法中，线程写入一些数据，然后写入一个标志，该标志告诉其他线程数据已准备就绪。 这称为写释放。 如果对写入重新排序，其他线程可能会看到已设置标志，然后才能看到写入的数据。

同样，在许多情况下，线程从标志读取，然后读取一些共享数据（如果该标志指出线程已获取对共享数据的访问权限）。 这称为读取-获取。 如果读取被重新排序，则数据可能在标志之前从共享存储中读取，并且看到的值可能不是最新的。

读取和写入的重新排序可以由编译器和处理器完成。 编译器和处理器已经进行了多年重新排序，但在单处理器计算机上，问题就不那么大了。 这是因为读取和写入的 CPU 重新排列在单处理器计算机上是不可见的， (非设备驱动程序代码不属于设备驱动程序) ，并且编译器重新排列读取和写入不太可能在单处理器计算机上导致问题。

如果编译器或 CPU 重新排列以下代码中显示的写入操作，另一个线程可能会看到活动标志已设置，同时仍会看到 x 或 y 的旧值。 读取时可能会发生类似的重新排列。

在此代码中，一个线程将新条目添加到子画面数组：

// Create a new sprite by writing its position into an empty
// entry and then setting the ‘alive' flag. If ‘alive' is
// written before x or y then errors may occur.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
g_sprites[nextSprite].alive = true;

在下一个代码块中，另一个线程从子画面数组读取：

// Draw all sprites. If the reads of x and y are moved ahead of
// the read of ‘alive' then errors may occur.
for( int i = 0; i < numSprites; ++i )
{
    if( g_sprites[nextSprite].alive )
    {
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

为了使此子画面系统安全，我们需要防止编译器和 CPU 对读取和写入重新排序。

了解写入的 CPU 重新排列

某些 CPU 重新排列写入，以便以非程序顺序对其他处理器或设备在外部可见。 这种重新排列永远不会对单线程非驱动程序代码可见，但它可能会导致多线程代码出现问题。

Xbox 360

虽然 Xbox 360 CPU 不会对指令重新排序，但它会重新排列写入操作，这些操作在指令本身之后完成。 PowerPC 内存模型专门允许这种写入重新排列。

Xbox 360 上的写入不会直接转到 L2 缓存。 相反，为了提高 L2 缓存写入带宽，它们通过存储队列，然后存储-收集缓冲区。 存储-收集缓冲区允许在一次操作中将 64 字节块写入 L2 缓存。 有 8 个存储-收集缓冲区，可以有效地写入内存的多个不同区域。

存储-收集缓冲区通常按先入先出 (FIFO) 顺序写入 L2 缓存。 但是，如果写入的目标缓存行不在 L2 缓存中，则从内存提取缓存行时，该写入可能会延迟。

即使存储收集缓冲区以严格的 FIFO 顺序写入 L2 缓存，这并不能保证单个写入按顺序写入 L2 缓存。 例如，假设 CPU 写入位置0x1000，然后写入位置0x2000，然后写入位置0x1004。 第一次写入分配存储-收集缓冲区，并将其放在队列的前面。 第二个写入分配另一个存储-收集缓冲区，并将其放在队列中的下一个。 第三次写入将其数据添加到第一个存储-收集缓冲区，该缓冲区保留在队列的前面。 因此，第三次写入最终在第二次写入之前进入 L2 缓存。

存储-收集缓冲区导致的重新排序根本无法预测，特别是因为核心上的两个线程共享存储-收集缓冲区，从而使存储-收集缓冲区的分配和清空变得高度可变。

这是如何重新排序写入的一个示例。 可能还有其他可能性。

x86 和 x64

即使 x86 和 x64 CPU 对指令重新排序，它们通常不会相对于其他写入对写入操作重新排序。 写合并内存存在一些例外情况。 此外， (MOVS 和 STOS) 和 16 字节 SSE 写入的字符串操作可以在内部重新排序，但除此之外，写入不会彼此重新排序。

了解读取的 CPU 重新排列

某些 CPU 重新排列读取，以便它们有效地以非程序顺序来自共享存储。 这种重新排列永远不会对单线程非驱动程序代码可见，但可能会导致多线程代码出现问题。

Xbox 360

缓存未命中可能会导致某些读取延迟，这实际上会导致读取来自共享内存的无序，并且这些缓存未命中时间从根本上是不可预知的。 预提取和分支预测还会导致数据来自共享内存的无序。 这些只是如何重新排序读取的几个示例。 可能存在其他可能性。 PowerPC 内存模型专门允许这种读取重新排列。

x86 和 x64

即使 x86 和 x64 CPU 执行重新排序指令，它们通常不会相对于其他读取对读取操作重新排序。 (MOVS 和 STOS) 和 16 字节 SSE 读取的字符串操作可以在内部重新排序，但否则，读取不会相互重新排序。

其他重新排序

即使 x86 和 x64 CPU 不会相对于其他写入对写入重新排序写入或相对于其他读取对读取重新排序，它们也可以对相对于写入的读取重新排序。 具体而言，如果程序写入一个位置，然后从其他位置读取，则读取数据可能来自共享内存，然后写入数据。 这种重新排序可能会破坏某些算法，例如 Dekker 的互斥算法。 在 Dekker 算法中，每个线程都设置一个标志来指示它想要进入关键区域，然后检查另一个线程的标志，以查看另一个线程是否在关键区域或尝试输入它。 初始代码如下所示。

volatile bool f0 = false;
volatile bool f1 = false;

void P0Acquire()
{
    // Indicate intention to enter critical region
    f0 = true;
    // Check for other thread in or entering critical region
    while (f1)
    {
        // Handle contention.
    }
    // critical region
    ...
}


void P1Acquire()
{
    // Indicate intention to enter critical region
    f1 = true;
    // Check for other thread in or entering critical region
    while (f0)
    {
        // Handle contention.
    }
    // critical region
    ...
}

问题是 P0Acquire 中 f1 的读取可以在对 f0 的写入到共享存储之前从共享存储进行读取。 同时，在对 f1 的写入到共享存储之前，P1Acquire 中对 f0 的读取可以从共享存储进行读取。 净效果是两个线程将其标志设置为 TRUE，并且两个线程将另一个线程的标志视为 FALSE，因此它们都进入关键区域。 因此，虽然在基于 x86 和 x64 的系统上重新排序的问题不如 Xbox 360 上常见，但它们肯定仍可能发生。 在上述任何平台上没有硬件内存屏障的情况下，Dekker 的算法都无法正常工作。

x86 和 x64 CPU 不会在上一次读取之前对写入重新排序。 x86 和 x64 CPU 仅在以前的写入之前重新排序读取（如果它们面向不同的位置）。

PowerPC CPU 可以在写入之前对读取进行重新排序，并且可以在读取之前对写入重新排序，只要它们位于不同的地址。

重新排序摘要

与 x86 和 x64 CPU 相比，Xbox 360 CPU 对内存操作进行更积极的重新排序，如下表所示。 有关更多详细信息，请参阅处理器文档。

重新排序活动 x86 和 x64 Xbox 360
读取在读取之前移动 否 是
写入操作在写入之前移动 否 是
写入操作在读取之前移动 否 是
读取在写入之前移动 是 是

 

Read-Acquire和Write-Release障碍

用于防止读取和写入重新排序的main构造称为读取-获取和写入-释放屏障。 读取-获取是读取标志或其他变量以获取资源所有权，以及阻止重新排序的障碍。 同样，写释放是一个标志或其他变量的写入，用于放弃资源的所有权，以及阻止重新排序的障碍。

Herb Sutter 的正式定义是：

  • 读取-获取在按程序顺序执行的同一线程执行所有读取和写入操作之前。
  • 写入释放在按程序顺序由其前面的同一线程执行所有读取和写入操作后执行。

当代码获取某些内存的所有权时，无论是通过获取锁，还是从共享链接列表 (拉取项而不) ，始终涉及读取 -- 测试标志或指针以查看是否已获取内存的所有权。 此读取可能是 InterlockedXxx 操作的一部分，在这种情况下，它涉及读取和写入，但读取指示是否已获得所有权。 获取内存所有权后，通常会从该内存中读取或写入值，在获取所有权后执行这些读取和写入操作非常重要。 读取-获取屏障可保证这一点。

释放某些内存的所有权时（通过释放锁或将项目推送到共享链接列表）时，始终会涉及写入，通知其他线程内存现在可供他们使用。 虽然代码拥有内存的所有权，但它可能从内存中读取或写入内存，在释放所有权之前执行这些读取和写入操作非常重要。 写释放屏障可以保证这一点。

最简单的方法就是将读取-获取和写入-释放屏障视为单个操作。 但是，有时必须从两个部分构造它们：读取或写入，以及不允许读取或写入移动的屏障。 在这种情况下，屏障的放置至关重要。 对于读取-获取屏障，首先读取标志，然后读取屏障，然后读取和写入共享数据。 对于写入释放屏障，首先读取和写入共享数据，然后是屏障，然后是写入标志。

// Read that acquires the data.
if( g_flag )
{
    // Guarantee that the read of the flag executes before
    // all reads and writes that follow in program order.
    BarrierOfSomeSort();

    // Now we can read and write the shared data.
    int localVariable = sharedData.y;
    sharedData.x = 0;

    // Guarantee that the write to the flag executes after all
    // reads and writes that precede it in program order.
    BarrierOfSomeSort();
    
    // Write that releases the data.
    g_flag = false;
}

读取-获取和写入释放之间的唯一区别是内存屏障的位置。 读取-获取在锁定操作之后具有屏障，而写入释放之前具有屏障。 在这两种情况下，屏障位于对锁定内存的引用和对锁的引用之间。

若要了解为什么在获取和发布数据时都需要屏障，最好 (和最准确的) 将这些障碍视为保证与共享内存同步，而不是与其他处理器同步。 如果一个处理器使用写释放将数据结构释放到共享内存，而另一个处理器使用读取-获取从共享内存访问该数据结构，则代码将正常工作。 如果任一处理器未使用适当的屏障，则数据共享可能会失败。

使用正确的屏障来防止平台的编译器和 CPU 重新排序至关重要。

使用操作系统提供的同步基元的优点之一是，所有这些基元都包含适当的内存屏障。

阻止编译器重新排序

编译器的工作是积极优化代码以提高性能。 这包括重新排列指令（无论它在哪里有用，无论它不会在何处更改行为）。 由于 C++ 标准从未提及多线程处理，并且编译器不知道哪些代码需要线程安全，因此编译器在确定可以安全地进行哪些重新排列时假定代码是单线程的。 因此，当不允许对读取和写入进行重新排序时，需要告知编译器。

使用 Visual C++，可以使用编译器内部 _ReadWriteBarrier来阻止编译器重新排序。 在代码中插入 _ReadWriteBarrier 时，编译器不会在代码中移动读取和写入操作。

#if _MSC_VER < 1400
    // With VC++ 2003 you need to declare _ReadWriteBarrier
    extern "C" void _ReadWriteBarrier();
#else
    // With VC++ 2005 you can get the declaration from intrin.h
#include <intrin.h>
#endif
// Tell the compiler that this is an intrinsic, not a function.
#pragma intrinsic(_ReadWriteBarrier)

// Create a new sprite by filling in a previously empty entry.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
// Write-release, barrier followed by write.
// Guarantee that the compiler leaves the write to the flag
// after all reads and writes that precede it in program order.
_ReadWriteBarrier();
g_sprites[nextSprite].alive = true;

在以下代码中，另一个线程从子画面数组中读取：

// Draw all sprites.
for( int i = 0; i < numSprites; ++i )
{

    // Read-acquire, read followed by barrier.
    if( g_sprites[nextSprite].alive )
    {
    
        // Guarantee that the compiler leaves the read of the flag
        // before all reads and writes that follow in program order.
        _ReadWriteBarrier();
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

请务必了解 ，_ReadWriteBarrier 不会插入任何其他指令，并且它不会阻止 CPU 重新排列读取和写入，它只会阻止编译器重新排列它们。 因此，在 x86 和 x64 (上实现写释放屏障时， _ReadWriteBarrier 就足够了，因为 x86 和 x64 不会对写入重新排序，正常写入足以释放锁) ，但在大多数其他情况下，还需要防止 CPU 重新排序读取和写入。

在写入不可缓存的写入组合内存时，还可以使用 _ReadWriteBarrier ，以防止写入重新排序。 在这种情况下 ，_ReadWriteBarrier 通过保证写入按处理器的首选线性顺序进行，从而有助于提高性能。

还可以使用 _ReadBarrier 和 _WriteBarrier 内部函数更精确地控制编译器重新排序。 编译器不会跨 _ReadBarrier移动读取，也不会跨 _WriteBarrier移动写入。

阻止 CPU 重新排序

CPU 重新排序比编译器重新排序更微妙。 你永远无法直接看到它发生，你只能看到莫名其妙的 bug。 为了防止对读取和写入进行 CPU 重新排序，需要在某些处理器上使用内存屏障指令。 在 Xbox 360 和 Windows 上，内存屏障指令的通用名称是 MemoryBarrier。 此宏是针对每个平台适当实现的。

在 Xbox 360 上， MemoryBarrier 定义为 lwsync (轻型同步) ，也可通过 ppcintrinsics.h 中定义的 __lwsync 内部函数获取。 __lwsync 还充当编译器内存屏障，防止编译器重新排列读取和写入。

lwsync 指令是 Xbox 360 上的内存屏障，可将一个处理器核心与 L2 缓存同步。 它保证 lwsync 之前的所有写入操作都会在后续写入之前将其写入 L2 缓存。 它还保证 任何遵循 lwsync 的读取不会从 L2 获取比以前的读取更早的数据。 它无法阻止的一种重新排序是读取在写入到其他地址之前移动。 因此， lwsync 强制实施与 x86 和 x64 处理器上的默认内存排序匹配的内存排序。 若要获取完整的内存排序，需要更昂贵的同步指令 (也称为重量级同步) ，但在大多数情况下，这不是必需的。 下表显示了 Xbox 360 上的内存重新排序选项。

Xbox 360 重新排序 未同步 lwsync sync
读取在读取之前移动 是 否 否
在写入之前移动写入 是 否 否
写入操作在读取之前移动 是 否 否
读取在写入之前移动 是 是 否

 

PowerPC 还具有同步指令 isync 和 eieio (用于控制缓存抑制内存) 的重新排序。 正常同步时不需要这些同步指令。

在 Windows 上， MemoryBarrier 在 Winnt.h 中定义，并提供不同的内存屏障指令，具体取决于你是编译 x86 还是 x64。 内存屏障指令充当完整屏障，防止跨屏障对读取和写入的所有重新排序。 因此，Windows 上的 MemoryBarrier 提供了比在 Xbox 360 上更强大的重新排序保证。

在 Xbox 360 和许多其他 CPU 上，还有一种方法可以阻止 CPU 的读取重新排序。 如果读取指针，然后使用该指针加载其他数据，则 CPU 保证指针的读取时间不会早于指针的读取时间。 如果锁定标志是指针，并且共享数据的所有读取操作都脱离了指针，则可以省略 MemoryBarrier ，以适度节省性能。

Data* localPointer = g_sharedPointer;
if( localPointer )
{
    // No import barrier is needed--all reads off of localPointer
    // are guaranteed to not be reordered past the read of
    // localPointer.
    int localVariable = localPointer->y;
    // A memory barrier is needed to stop the read of g_global
    // from being speculatively moved ahead of the read of
    // g_sharedPointer.
    int localVariable2 = g_global;
}

MemoryBarrier 指令仅阻止对可缓存内存的读取和写入重新排序。 如果将内存分配为PAGE_NOCACHE或PAGE_WRITECOMBINE，这是 Xbox 360 上设备驱动程序作者和游戏开发人员的常用技术， 则 MemoryBarrier 对访问此内存没有影响。 大多数开发人员不需要同步不可缓存的内存。 这超出了本文的范围。

互锁函数和 CPU 重新排序

有时，获取或释放资源的读取或写入操作是使用 InterlockedXxx 函数之一完成的。 在 Windows 上，这简化了事情：因为在 Windows 上， InterlockedXxx 函数都是全内存屏障。 它们之前和之后实际上都有一个 CPU 内存屏障，这意味着它们本身都是完整的读取-获取或写入释放屏障。

在 Xbox 360 上， InterlockedXxx 函数不包含 CPU 内存屏障。 它们阻止编译器对读取和写入进行重新排序，但不阻止 CPU 重新排序。 因此，在大多数情况下，在 Xbox 360 上使用 InterlockedXxx 函数时，应在它们前面或后面加上 一个__lwsync，使它们成为读取-获取或写入释放屏障。 为方便起见和更易于阅读，许多 InterlockedXxx 函数都有 Acquire 和 Release 版本。 它们附带了内置的内存屏障。 例如， InterlockedIncrementAcquire 执行后跟 __lwsync 内存屏障的互锁增量，以提供完整的读取-获取功能。

建议使用 InterlockedXxx 函数的获取和发布版本， (大多数函数在 Windows 上也可用，) 不会造成性能损失，以使意图更加明显，并更轻松地在正确位置获取内存屏障指令。 在 Xbox 360 上使用 InterlockedXxx 时，应非常仔细地检查，因为它通常是一个 bug。

此示例演示一个线程如何使用 InterlockedXxxSList 函数的 Acquire 和 Release 版本将任务或其他数据传递给另一个线程。 InterlockedXxxSList 函数是一系列函数，用于维护没有锁的共享单独链接列表。 请注意， 这些 函数的获取和 发布 变体在 Windows 上不可用，但这些函数的常规版本是 Windows 上的完整内存屏障。

// Declarations for the Task class go here.

// Add a new task to the list using lockless programming.
void AddTask( DWORD ID, DWORD data )
{
    Task* newItem = new Task( ID, data );
    InterlockedPushEntrySListRelease( g_taskList, newItem );
}

// Remove a task from the list, using lockless programming.
// This will return NULL if there are no items in the list.
Task* GetTask()
{
    Task* result = (Task*)
        InterlockedPopEntrySListAcquire( g_taskList );
    return result;
}

可变变量和重新排序

C++ 标准规定，可变变量的读取不能缓存，易失性写入不能延迟，并且易失性读取和写入不能相互移动。 这足以与硬件设备通信，这是 C++ 标准中的易失性关键字 (keyword) 的目的。

但是，标准的保证不足以使用 volatile 进行多线程处理。 C++ 标准不会阻止编译器相对于易失性读取和写入对非易失性读取和写入重新排序，并且它没有说明如何阻止 CPU 重新排序。

Visual C++ 2005 超越了标准 C++，为可变变量访问定义多线程友好的语义。 从 Visual C++ 2005 开始，从易失变量读取定义为具有读取-获取语义，对可变变量的写入定义为具有写入释放语义。 这意味着编译器不会重新排列任何读取和写入操作，在 Windows 上，它将确保 CPU 也不会这样做。

请务必了解，这些新保证仅适用于 Visual C++ 2005 和 Visual C++ 的未来版本。 其他供应商的编译器通常会实现不同的语义，而没有 Visual C++ 2005 的额外保证。 此外，在 Xbox 360 上，编译器不会插入任何指令来阻止 CPU 重新排序读取和写入。

Lock-Free数据管道示例

管道是一种构造，它允许一个或多个线程写入数据，然后由其他线程读取。 管道的无锁版本可以是将工作从线程传递到线程的一种优雅而高效的方法。 DirectX SDK 提供 LockFreePipe，这是 DXUTLockFreePipe.h 中提供的单读取器、单写入器无锁管道。 AtgLockFreePipe.h 的 Xbox 360 SDK 中提供了相同的 LockFreePipe。

当两个线程具有生成者/使用者关系时，可以使用 LockFreePipe。 生成者线程可以将数据写入管道，供使用者线程稍后处理，而不会阻塞。 如果管道填满，写入将失败，生成者线程稍后必须重试，但仅当生成者线程位于前面时，才会发生这种情况。 如果管道清空，读取将失败，并且使用者线程稍后必须重试，但仅当使用者线程无法执行任何工作时，才会发生这种情况。 如果两个线程均衡良好，并且管道足够大，则管道允许它们顺利传递数据，且无延迟或阻塞。

Xbox 360 性能

Xbox 360 上的同步指令和函数的性能将因正在运行的其他代码而异。 如果另一个线程当前拥有锁，则获取锁需要更长的时间。 如果其他线程写入同一缓存行，InterlockedIncrement 和关键节操作将花费更长的时间。 存储队列的内容也可能会影响性能。 因此，所有这些数字都只是通过非常简单的测试生成的近似值：

  • lwsync 被测量为采用 33-48 个周期。
  • InterlockedIncrement 测量为采用 225-260 个周期。
  • 获取或释放关键部分的度量值大约需要 345 个周期。
  • 获取或释放互斥体被测量为大约需要 2350 个周期。

Windows 性能

Windows 上的同步指令和函数的性能因处理器类型和配置以及正在运行的其他代码而异。 多核和多套接字系统执行同步指令通常需要更长的时间，如果另一个线程当前拥有该锁，则获取锁需要更长的时间。

但是，即使是从非常简单的测试生成的一些度量值也很有用：

  • MemoryBarrier 被测量为采用 20-90 个周期。
  • InterlockedIncrement 测量为采用 36-90 个周期。
  • 获取或释放关键部分被测量为需要 40-100 个周期。
  • 获取或释放互斥体需要大约 750-2500 个周期。

这些测试是在一系列不同处理器上的 Windows XP 上完成的。 短时间在单处理器计算机上，而多处理器计算机上的时间较长。

虽然获取和释放锁比使用无锁编程更昂贵，但最好减少共享数据的频率，从而完全避免成本。

性能想法

获取或释放关键部分包括内存屏障、 InterlockedXxx 操作以及处理递归和回退到互斥（如有必要）的一些额外检查。 你应该谨慎实现自己的关键部分，因为在等待锁释放的循环中旋转，而不回退到互斥体，可能会浪费相当大的性能。 对于经常争用但不长时间保留的关键节，应考虑使用 InitializeCriticalSectionAndSpinCount ，以便操作系统将旋转一段时间，等待关键节可用，而不是在尝试获取关键节时立即延迟为互斥。 为了识别可从旋转计数中获益的关键部分，必须测量特定锁的典型等待时间长度。

如果共享堆用于内存分配（默认行为），则每个内存分配和可用都涉及获取锁。 随着线程数和分配数的增加，性能级别关闭，最终开始降低。 使用每线程堆或减少分配数可以避免这种锁定瓶颈。

如果一个线程正在生成数据，而另一个线程正在使用数据，则它们最终可能会频繁共享数据。 如果一个线程正在加载资源，而另一个线程正在呈现场景，则可能会发生这种情况。 如果呈现线程在每次绘图调用中引用共享数据，则锁定开销将很高。 如果每个线程都有专用数据结构，然后每帧同步一次或更少，则可以实现更好的性能。

不保证无锁算法比使用锁的算法快。 在尝试避免锁之前，应检查查看锁是否确实导致问题，并且应该测量无锁代码是否确实提高了性能。

平台差异摘要

  • InterlockedXxx 函数可防止在 Windows 上（但在 Xbox 360 上）上阻止 CPU 读/写重新排序。
  • 使用 Visual Studio C++ 2005 读取和写入易失变量会阻止 Windows 上的 CPU 读/写重新排序，但在 Xbox 360 上，它仅阻止编译器读/写重新排序。
  • 写入在 Xbox 360 上重新排序，但不在 x86 或 x64 上重新排序。
  • 读取在 Xbox 360 上重新排序，但在 x86 或 x64 上，仅当读取和写入针对不同位置时才重新排序。

建议

  • 尽可能使用锁，因为它们更易于正确使用。
  • 避免锁定过于频繁，这样锁定成本就不会变得很大。
  • 避免锁定时间过长，以避免长时间停滞。
  • 在适当的时候使用无锁编程，但请确保增益证明复杂性是正当的。
  • 在禁止使用其他锁的情况下，例如在延迟过程调用和普通代码之间共享数据时，请使用无锁编程或旋转锁。
  • 仅使用经证明是正确的标准无锁编程算法。
  • 执行无锁编程时，请务必根据需要使用可变标志变量和内存屏障指令。
  • 在 Xbox 360 上使用 InterlockedXxx 时，请使用 获取 和 发布 变体。

参考