Xbox 360 和 Microsoft Windows 的 Lockless 程式設計考量

發行項
07/16/2024

無鎖定程式設計是安全地共用多個線程之間變更數據的方法，不需要取得和釋放鎖定的成本。這聽起來像是萬能葯，但無鎖程式設計是複雜而微妙的，有時不會給予它所承諾的好處。 Xbox 360 上的無鎖定程式設計特別複雜。

無鎖定程式設計是多線程程序設計的有效技術，但不應輕視使用。使用之前，您必須瞭解複雜性，而且您應該仔細測量，以確保它實際上會提供您預期的收益。在許多情況下，有更簡單且更快的解決方案，例如共用數據的頻率較低，因此應該改用。

正確且安全地使用無鎖定程序設計，需要您硬體和編譯程式的重要知識。本文概述嘗試使用無鎖定程序設計技術時要考慮的一些問題。

使用Locks進行程序設計

撰寫多線程程式代碼時，通常需要在線程之間共享數據。如果多個線程同時讀取和寫入共用數據結構，可能會發生記憶體損毀。解決此問題最簡單的方式是使用鎖定。例如，如果 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 可能必須做為多個總線交易來執行這些讀取和寫入，這可讓另一個線程修改或查看讀取或寫入中間的數據。

複合作業，例如當您遞增共用變數時所發生的讀取-modify-write 序列，不是不可部分完成的。在 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 的舊值。讀取時可能會發生類似的重新排列。

在此程式代碼中，一個線程會將新的專案新增至 Sprite 陣列：

// 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;

在下一個程式代碼區塊中，另一個線程會從Sprite陣列讀取：

// 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 );
    }
}

若要讓此 Sprite 系統安全無虞，我們必須防止編譯程式和 CPU 重新排序讀取和寫入。

瞭解寫入的CPU重新排列

某些 CPU 會重新排列寫入，讓其他處理器或裝置以非程式順序從外部看到它們。單一線程非驅動程式程式代碼永遠不會看到此重新排列，但它可能會導致多線程程式代碼發生問題。

Xbox 360

雖然 Xbox 360 CPU 不會重新排序指示，但它會重新排列寫入作業，這會在指令本身之後完成。 PowerPC 記憶體模型特別允許重新排列寫入。

Xbox 360 上的寫入不會直接移至 L2 快取。相反地，為了改善 L2 快取寫入頻寬，他們會經過存放佇列，然後儲存收集緩衝區。存放區收集緩衝區允許在一個作業中將64位元組區塊寫入 L2 快取。有八個存放區收集緩衝區，可有效率地寫入數個不同的記憶體區域。

存放區收集緩衝區通常會以先出（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 到共用記憶體之前，從共用記憶體讀取。同時，P1Acquire 中的 f0 讀取可以從共用記憶體讀取，然後寫入 f1 即可將其寫入共用記憶體。淨效果是，這兩個線程都會將其旗標設定為TRUE，而兩個線程都會將另一個線程的旗標視為 FALSE，因此兩者都進入關鍵區域。因此，雖然在 x86 和 x64 型系統上重新排序的問題並不如 Xbox 360 上常見，但它們肯定仍會發生。 Dekker 的演算法無法在這些平台上沒有硬體記憶體屏障的情況下運作。

x86 和 x64 CPU 將不會在先前讀取之前重新排序寫入。如果 x86 和 x64 CPU 以不同的位置為目標，則只會在先前的寫入之前重新排序讀取。

只要讀取位址不同，PowerPC CPU 就可以在寫入之前重新排序讀取，而且可以在讀取之前重新排序寫入。

重新排序摘要

Xbox 360 CPU 重新排列記憶體作業比 x86 和 x64 CPU 更積極，如下表所示。如需詳細資訊，請參閱處理器檔。

重新排序活動	x86 和 x64	Xbox 360
讀取在讀取之前移動	No	Yes
寫入在寫入之前移動	No	Yes
在讀取之前移動寫入	No	Yes
讀取在寫入之前移動	Yes	Yes

讀取取得和寫入發行屏障

用來防止重新排序讀取和寫入的主要建構稱為讀取-取得和寫入釋放屏障。讀取取得是旗標或其他變數的讀取，可取得資源的擁有權，加上重新排序的屏障。同樣地，寫入發行是旗標或其他變數的寫入，以放棄資源的擁有權，加上防止重新排序的障礙。

赫布·薩特的正式定義包括：

讀取取得會在程序順序遵循它的所有讀取和寫入之前執行。
寫入版本會在程序順序之前由相同線程執行所有讀取和寫入之後執行。

當您的程式代碼取得某些記憶體的擁有權時，無論是透過取得鎖定或從共用連結清單提取專案（沒有鎖定），一律會涉及讀取—測試旗標或指標，以查看是否已取得記憶體的擁有權。此讀取可能是 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++ Standard 永遠不會提及多線程，而且因為編譯程式不知道哪些程式代碼需要安全線程，所以編譯程式會假設您的程式代碼在決定可以安全地重新排列什麼時，是單個線程。因此，您必須在不允許重新排序讀取和寫入時告訴編譯程式。

使用 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;

在下列程式代碼中，另一個線程會從Sprite陣列讀取：

// 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 （輕量型同步處理），也可以透過內建__lwsync取得，其定義於 ppcintrinsics.h 中。 __lwsync也可做為編譯程式記憶體屏障，防止編譯程式重新排列讀取和寫入。

lwsync 指令是 Xbox 360 上的記憶體屏障，可同步處理一個處理器核心與 L2 快取。它保證 lwsync 之前的所有寫入都會在後續寫入之前先寫入 L2 快取。它也保證後續 lwsync 的任何讀取不會從 L2 取得比先前讀取更舊的數據。其無法防止的一種重新排序方式是讀取在寫入至不同位址之前移動。因此， lwsync 會強制執行符合 x86 和 x64 處理器上預設記憶體順序的記憶體順序。若要取得完整記憶體順序，需要更昂貴的同步處理指令（也稱為重量級同步），但在大多數情況下，這並非必要。下表顯示 Xbox 360 上的記憶體重新排序選項。

Xbox 360 重新排列	沒有同步處理	lwsync	sync
讀取在讀取之前移動	是	無	No
寫入在寫入之前移動	是	無	No
在讀取之前移動寫入	是	無	No
讀取在寫入之前移動	Yes	是	No

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 記憶體屏障前後都有 CPU 記憶體屏障，這表示它們本身都是完整的讀取取得或寫入釋放屏障。

在 Xbox 360 上 ，InterlockedXxx 函式不包含 CPU 記憶體屏障。它們可防止編譯程式重新排序讀取和寫入，但不會重新排序 CPU。因此，在 Xbox 360 上使用 InterlockedXxx 函式時，您應該在 Xbox 360 上使用 interlockedXxx 函式之前或遵循__lwsync，使其成為讀取取得或寫入發行屏障。為了方便和更容易閱讀，有許多 InterlockedXxx 函式的 Acquire 和 Release 版本。它們隨附內建的記憶體屏障。例如，InterlockedIncrementAcquire 會執行連鎖遞增，後面接著__lwsync記憶體屏障，以提供完整的讀取取得功能。

建議您使用 InterlockedXxx 函式的 Acquire 和 Release 版本（其中大部分可在 Windows 上使用，但不會降低效能），讓您的意圖更加明顯，並讓您更輕鬆地在正確的位置取得記憶體屏障指示。 在 Xbox 360 上使用 InterlockedXxx 時，應該非常仔細地檢查，因為它通常是錯誤。

此範例示範一個線程如何使用 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;
}

Volatile Variables and Reordering

C++ Standard 表示無法快取揮發性變數的讀取、動態寫入無法延遲，且動態讀取和寫入無法彼此移動。這足以與硬體裝置通訊，這是 C++ Standard 中 volatile 關鍵詞的目的。

不過，標準保證不足以針對多線程使用揮發性。 C++ Standard 不會阻止編譯程式重新排序相對於揮發性讀取和寫入的非揮發性讀取和寫入，而且不會說明防止 CPU 重新排序。

Visual C++ 2005 超越標準C++，為揮發性變數存取定義多線程易記語意。從 Visual C++ 2005 開始，從 volatile 變數讀取會定義為具有讀取取得語意，而對 volatile 變數的寫入則定義為具有寫入發行語意。這表示編譯程式不會重新排列任何讀取和寫入，而且在 Windows 上，它會確保 CPU 不會這麼做。

請務必瞭解，這些新的保證僅適用於Visual C++ 2005和未來的Visual C++版本。來自其他廠商的編譯程式通常會實作不同的語意，而不需要 Visual C++ 2005 的額外保證。此外，在 Xbox 360 上，編譯程式不會插入任何指示，以防止 CPU 重新排序讀取和寫入。

無鎖定數據管道的範例

管道是一種建構，可讓一或多個線程寫入數據，然後由其他線程讀取。管線的無鎖定版本可以是一種優雅且有效率的方式，可將工作從線程傳遞至線程。 DirectX SDK 提供 LockFreePipe，這是 DXUTLockFreePipe.h 中提供的單一讀取器、單一寫入器無鎖定管道。在 AtgLockFreePipe.h 的 Xbox 360 SDK 中，有相同的 LockFreePipe 可供使用。

當兩個線程具有生產者/取用者關聯性時，可以使用LockFreePipe 。產生者線程可以將數據寫入管道，供取用者線程在稍後處理，而不需要封鎖。如果管道填滿，寫入會失敗，而產生者線程稍後必須再試一次，但只有在產生者線程領先時才會發生此情況。如果管道清空，讀取會失敗，且取用者線程稍後必須再試一次，但只有在取用者線程無法執行時，才會發生此情況。如果兩個線程平衡良好，且管道夠大，管道可讓它們順暢地傳遞數據，而且沒有延遲或區塊。

Xbox 360 效能

Xbox 360 上同步處理指令和函式的效能會因其他程式代碼執行而有所不同。如果另一個線程目前擁有鎖定，則取得鎖定需要更長的時間。 如果其他線程寫入相同的快取行，InterlockedIncrement 和重要區段作業會花費更長的時間。存放區佇列的內容也會影響效能。因此，所有這些數位只是從非常簡單的測試產生的近似值：

lwsync 測量為採用 33-48 迴圈。
InterlockedIncrement 測量為採用 225-260 迴圈。
取得或釋放重要區段的量值大約為 345 個週期。
取得或釋放 Mutex 測量為大約 2350 個週期。

Windows 效能

Windows 上同步處理指令和函式的效能會因處理器類型和組態以及執行其他程式碼而有所不同。多核心和多套接字系統通常需要較長的時間來執行同步處理指令，如果另一個線程目前擁有鎖定，則取得鎖定需要更長的時間。

不過，即使是從非常簡單的測試產生的一些量測也很有説明：

MemoryBarrier 被測量為採用 20-90 迴圈。
InterlockedIncrement 測量為採用 36-90 迴圈。
取得或釋放關鍵區段的測量是採用 40-100 個週期。
取得或釋放 Mutex 測量為大約 750-2500 迴圈。

這些測試是在各種不同處理器的 Windows XP 上完成的。短時間是在單一處理器計算機上，而較長的時間則位於多處理器計算機上。

雖然取得和釋放鎖定比使用無鎖定程序設計更昂貴，但最好更不頻繁地共用數據，從而完全避免成本。

效能想法

取得或釋放重要區段包含記憶體屏障、 InterlockedXxx 作業，以及處理遞歸的一些額外檢查，並在必要時回復為 Mutex。您應該謹慎實作自己的關鍵區段，因為旋轉在迴圈中等待鎖定自由，而不回到 Mutex，可能會浪費相當大的效能。對於大量競爭但未長時間保留的重要區段，您應該考慮使用 InitializeCriticalSectionAndSpinCount，讓操作系統在等候重要區段可供使用時旋轉一段時間，而不是在嘗試取得關鍵區段時立即延遲至 Mutex。若要識別可受益於微調計數的重要區段，必須測量一般等候特定鎖定的長度。

如果共用堆積用於記憶體配置，即預設行為，則每個記憶體配置和可用都牽涉到取得鎖定。當線程數目和配置數目增加時，效能層級會關閉，最後開始減少。使用個別線程堆積或減少配置數目，可以避免這個鎖定瓶頸。

如果一個線程產生數據，而另一個線程正在取用數據，它們最終可能會經常共享數據。如果一個線程正在載入資源，而另一個線程正在轉譯場景，就可能會發生這種情況。如果轉譯線程參考每個繪製呼叫上的共享數據，鎖定額外負荷會很高。如果每個線程都有私用數據結構，則每個畫面或更少時間都會同步處理一次，則可以達到更好的效能。

無鎖定演算法不保證比使用鎖定的演算法更快。您應該檢查鎖定是否確實造成問題，再嘗試避免它們，您應該測量無鎖定程式代碼是否確實改善效能。

平台差異摘要

InterlockedXxx 函式可防止 Windows 上的 CPU 讀取/寫入重新排序，但無法在 Xbox 360 上重新排序。
使用 Visual Studio C++ 2005 讀取和寫入揮發性變數可防止 Windows 上的 CPU 讀取/寫入重新排序，但在 Xbox 360 上，它只會防止編譯程式讀取/寫入重新排序。
寫入會在 Xbox 360 上重新排序，但無法在 x86 或 x64 上重新排序。
讀取會在 Xbox 360 上重新排序，但在 x86 或 x64 上，只有在讀取和寫入以不同位置為目標時，才會重新排序。

建議

盡可能使用鎖定，因為它們更容易正確使用。
避免鎖定太頻繁，因此鎖定成本不會變得顯著。
避免將鎖定保留太長，以避免長時間的攤位。
適當時使用無鎖定程序設計，但請確定收益證明複雜度合理。
在禁止其他鎖定的情況下，使用無鎖定程序設計或微調鎖定，例如在延遲的程式調用與一般程式代碼之間共用數據時。
只使用已證明正確的標準無鎖定程式設計演算法。
執行無鎖定程序設計時，請務必視需要使用揮發性旗標變數和記憶體屏障指示。
在 Xbox 360 上使用 InterlockedXxx 時，請使用 Acquire 和 Release 變體。

參考資料

“volatile （C++）”。C++語言參考。
萬斯·莫裡森「瞭解多線程應用程式中低鎖定技術的影響。」MSDN Magazine， 2005 年 10 月。
里昂，邁克爾「PowerPC 儲存模型和 AIX 程式設計」。IBM developerWorks，2005年11月16日。
麥肯尼，保羅E.“現代微控制器的記憶排序，第二部分。Linux 日誌，2005 年 9 月。 [本文有一些 x86 詳細數據。]
Intel Corporation。「Intel® 64 架構記憶體排序」。2007 年 8 月。 [適用於 IA-32 和 Intel 64 處理器。]
奈布勒，埃裡克 “行程報告：C++中線程的臨機操作會議。C++來源，2006年10月17日。
哈特，湯瑪斯 E. 2006. 「快速進行無鎖定同步處理：記憶體回收的效能影響。」2006年國際平行和分散式處理研討會（IPDPS 2006），希臘羅茲島，2006年4月。

共用方式為

Xbox 360 和 Microsoft Windows 的 Lockless 程式設計考量

使用Locks進行程序設計

無鎖定程序設計

非不可部分完成的作業

保證不可部分完成性

重組

瞭解寫入的CPU重新排列

Xbox 360

x86 和 x64

了解讀取的CPU重新排列

Xbox 360

x86 和 x64

其他重新排序

重新排序摘要

讀取取得和寫入發行屏障

防止編譯程式重新排序

防止CPU重新排列

聯結函式和CPU重新排序

Volatile Variables and Reordering

無鎖定數據管道的範例

Xbox 360 效能

Windows 效能

效能想法

平台差異摘要

建議

參考資料

意見反應

其他資源