Xbox 360 および Microsoft Windows のロックレスプログラミングに関する考慮事項

[アーティクル]
06/12/2023

ロックレスプログラミングは、ロックの取得と解放のコストをかけずに、複数のスレッド間で変更データを安全に共有する方法です。これは万能薬のように聞こえますが、ロックレスプログラミングは複雑で微妙であり、時にはそれが約束する利点を与えません。ロックレスプログラミングは、Xbox 360 では特に複雑です。

ロックレスプログラミングはマルチスレッドプログラミングに有効な手法ですが、軽く使用しないでください。それを使用する前に、複雑さを理解する必要があります,そしてそれは実際にあなたが期待する利益を与えているかどうかを確認するために慎重に測定する必要があります. 多くの場合、データの共有頻度を減らすなど、よりシンプルで高速なソリューションがあります。これは代わりに使用する必要があります。

ロックレスプログラミングを正しく安全に使用するには、ハードウェアとコンパイラの両方に関する重要な知識が必要です。この記事では、ロックレスプログラミング手法を使用する際に考慮すべきいくつかの問題の概要について説明します。

ロックを使用したプログラミング

マルチスレッドコードを記述する場合、多くの場合、スレッド間でデータを共有する必要があります。複数のスレッドが共有データ構造の読み取りと書き込みを同時に行うと、メモリ破損が発生する可能性があります。この問題を解決する最も簡単な方法は、ロックを使用することです。たとえば、ManipulateSharedData を一度に 1 つのスレッドでのみ実行する必要がある場合、次のコードのように、CRITICAL_SECTIONを使用してこれを保証できます。

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

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

// Destroy
DeleteCriticalSection(&cs);

このコードは非常に単純で簡単で、正しいことを簡単に伝えることができます。ただし、ロックを使用したプログラミングには、いくつかの潜在的な欠点があります。たとえば、2 つのスレッドが同じ 2 つのロックを取得しようとしても、別の順序で取得しようとすると、デッドロックが発生する可能性があります。設計が悪い、またはスレッドが優先度の高いスレッドによってスワップアウトされているために、プログラムがロックを保持しすぎる場合は、他のスレッドが長時間ブロックされる可能性があります。ソフトウェアスレッドには開発者によってハードウェアスレッドが割り当てられ、オペレーティングシステムがアイドル状態であっても別のハードウェアスレッドに移動しないため、このリスクは Xbox 360 で特に大きいです。 Xbox 360 には、優先度の低いスレッドがロックを解除するのを待っている間に、優先度の高いスレッドがループで回転する、優先度の逆転に対する保護もありません。最後に、遅延プロシージャ呼び出しまたは割り込みサービスルーチンがロックの取得を試みると、デッドロックが発生する可能性があります。

これらの問題にもかかわらず、重要なセクションなどの同期プリミティブは、通常、複数のスレッドを調整する最適な方法です。同期プリミティブが遅すぎる場合は、通常、使用頻度を低くすることをお勧めします。ただし、複雑さを増す余裕がある人にとっては、もう 1 つのオプションはロックレスプログラミングです。

ロックレスプログラミング

ロックレスプログラミングは、名前が示すように、ロックを使用せずに共有データを安全に操作するための一連の手法です。メッセージの受け渡し、データのリストとキューの共有、その他のタスクに使用できるロックレスアルゴリズムがあります。

ロックレスプログラミングを行う場合は、非アトミック操作と並べ替えという 2 つの課題に対処する必要があります。

非アトミック操作

アトミック操作とは、操作の半分が完了したときに他のスレッドが表示されないように保証される、不可分な操作です。ロックレスプログラミングではアトミック操作が重要です。ロックレスプログラミングがないと、他のスレッドで半書きの値が表示されたり、それ以外の場合は一貫性のない状態が表示されたりする可能性があるためです。

最新のプロセッサでは、自然に配置されたネイティブ型の読み取りと書き込みがアトミックであると仮定できます。メモリバスが読み取りまたは書き込み中の型と少なくとも同じ幅である限り、CPU はこれらの型を 1 つのバストランザクションで読み取りおよび書き込みするため、他のスレッドが半完了状態で表示できなくなります。 x86 と x64 では、8 バイトを超える読み取りと書き込みがアトミックであるという保証はありません。つまり、ストリーミング SIMD 拡張機能 (SSE) レジスタと文字列操作の 16 バイトの読み取りと書き込みがアトミックではない可能性があります。

自然に整列されていない型の読み取りと書き込み (たとえば、4 バイトの境界を越える DWORD の書き込み) は、アトミックであるとは限りません。 CPU では、これらの読み取りと書き込みを複数のバストランザクションとして実行する必要がある場合があります。これにより、別のスレッドが読み取りまたは書き込みの途中でデータを変更または表示できる可能性があります。

共有変数をインクリメントするときに発生する読み取り/変更/書き込みシーケンスなどの複合操作はアトミックではありません。 Xbox 360 では、これらの操作は複数の命令 (lwz、addi、stw) として実装され、スレッドはシーケンスの途中でスワップされる可能性があります。 x86 と x64 では、メモリ内の変数をインクリメントするために使用できる 1 つの命令 (inc) があります。この命令を使用する場合、変数のインクリメントは単一プロセッサシステムではアトミックですが、マルチプロセッサシステムではアトミックではありません。 x86 および x64 ベースのマルチプロセッサシステムで inc atomic を作成するには、ロックプレフィックスを使用する必要があります。これにより、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 の古い値を見ながら、アライブフラグが設定されていることを確認できます。同様の再配置は、読み取り時に発生する可能性があります。

このコードでは、1 つのスレッドがスプライト配列に新しいエントリを追加します。

// 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 キャッシュ書き込み帯域幅を向上させるために、ストアキューを通過し、バッファーを格納します。ストアギャザーバッファーを使用すると、1 回の操作で 64 バイトのブロックを L2 キャッシュに書き込むことができます。 8 つのストアギャザーバッファーがあり、複数の異なるメモリ領域への効率的な書き込みを可能にします。

通常、ストアギャザーバッファーは先入れ先出し (FIFO) 順に L2 キャッシュに書き込まれます。ただし、書き込みのターゲットキャッシュ行が L2 キャッシュにない場合は、キャッシュ行がメモリからフェッチされている間、その書き込みが遅延する可能性があります。

ストア収集バッファーが厳密な FIFO 順序で L2 キャッシュに書き込まれる場合でも、個々の書き込みが L2 キャッシュに順番に書き込まれるという保証はありません。たとえば、CPU が場所0x1000に書き込み、次に場所0x2000に書き込み、次に場所0x1004に書き込むとします。最初の書き込みでは、ストア収集バッファーが割り当てられ、キューの先頭に配置されます。 2 番目の書き込みでは、別のストア収集バッファーが割り当てられ、キューの次に格納されます。 3 番目の書き込みでは、最初のストア収集バッファーにデータが追加され、キューの先頭に残ります。したがって、3 番目の書き込みでは、2 番目の書き込みの前に L2 キャッシュに移動します。

ストアギャザーバッファーによって発生する並べ替えは、基本的に予測できません。特に、コア上の両方のスレッドがストアギャザーバッファーを共有するため、ストアギャザーバッファーの割り当てと空き時間は非常に可変です。

これは、書き込みを並べ替える方法の 1 つの例です。他にも可能性があるかもしれません。

x 86 および x64

x86 および x64 CPU は命令の順序を変更しますが、通常は他の書き込みに対して書き込み操作の順序を変更しません。書き込み結合メモリにはいくつかの例外があります。さらに、文字列操作 (MOVS および STOS) と 16 バイトの SSE 書き込みを内部的に並べ替えることができますが、それ以外の場合、書き込みは相互に相対して並べ替えられません。

読み取りの CPU 再配置について

一部の CPU では、プログラム以外の順序で共有ストレージから取得されるように、読み取りを再配置します。この再配置は、シングルスレッドの非ドライバーコードには表示されませんが、マルチスレッドコードで問題が発生する可能性があります。

Xbox 360

キャッシュミスにより、読み取りが遅延する可能性があります。これにより、実質的に共有メモリからの読み取りが順序外れになり、これらのキャッシュミスのタイミングは根本的に予測できません。プリフェッチと分岐の予測により、データが共有メモリから順に外れる可能性もあります。これらは、読み取りを並べ替える方法のほんの一例です。他にも可能性があるかもしれません。この読み取りの再配置は、PowerPC メモリモデルで特に許可されます。

x 86 および x64

x86 および x64 CPU は命令の順序を変更しますが、通常、他の読み取りに対する読み取り操作の順序は変更されません。文字列操作 (MOVS および STOS) と 16 バイトの SSE 読み取りは内部的に並べ替えることができますが、それ以外の場合、読み取りは相互に相対して並べ替えられません。

その他の並べ替え

x86 および x64 CPU は、他の書き込みに対する書き込みの順序を変更したり、他の読み取りに対して読み取りを並べ替えたりすることはありませんが、書き込みに対する読み取りを並べ替えることができます。具体的には、プログラムが 1 つの場所に書き込み、その後に別の場所から読み取る場合、書き込まれたデータがそこに書き込まれる前に、読み取りデータが共有メモリから取得される可能性があります。この並べ替えは、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 よりもはるかに積極的にメモリ操作の順序が変更されます。詳細については、プロセッサのドキュメントを参照してください。

アクティビティの並べ替え	x 86 および x64	Xbox 360
読み取りの前に移動する読み取り	いいえ	はい
書き込みの前に移動する書き込み	いいえ	はい
読み取りの前に移動する書き込み	いいえ	はい
書き込みの前に移動する読み取り	はい	はい

Read-AcquireとWrite-Releaseバリア

読み取りと書き込みの並べ替えを防ぐために使用されるメインコンストラクトは、読み取り/取得および書き込み解放バリアと呼ばれます。読み取り/取得は、リソースの所有権を取得するためのフラグまたはその他の変数の読み取りであり、並べ替えの障壁と組み合わせられます。同様に、書き込みリリースは、リソースの所有権を放棄するフラグまたはその他の変数の書き込みであり、並べ替えの障壁と組み合わせています。

ハーブサッターの正式な定義は次のとおりです。

読み取り/取得は、すべての読み取りと書き込みの前に、プログラムの順序で実行されるのと同じスレッドによって実行されます。
書き込みリリースは、プログラムの順序で、その前にあるのと同じスレッドによってすべての読み取りと書き込みの後に実行されます。

ロックを取得するか、(ロックなしで) 共有リンクリストから項目をプルすることによって、コードがメモリの所有権を取得すると、常に読み取りが関係します。フラグまたはポインターをテストして、メモリの所有権が取得されているかどうかを確認します。この読み取りは InterlockedXxx 操作の一部である可能性があります。この場合、読み取りと書き込みの両方が含まれますが、所有権が取得されたかどうかを示す読み取りです。メモリの所有権が取得されると、通常、値はそのメモリから読み取られるか、そのメモリに書き込まれます。これらの読み取りと書き込みは、所有権を取得した後に実行することが非常に重要です。読み取り/取得バリアは、これを保証します。

ロックを解除するか、アイテムを共有リンクリストにプッシュすることによって、メモリの所有権が解放されると、常に書き込みが関係し、メモリが使用可能になったことを他のスレッドに通知します。コードはメモリの所有権を持っていましたが、おそらくそこから読み取りまたは書き込みを行い、所有権を解放する前にこれらの読み取りと書き込みを実行することが非常に重要です。書き込みリリースバリアによって、これが保証されます。

読み取り/取得と書き込みリリースのバリアを単一の操作と考えるのが最も簡単です。ただし、読み取りまたは書き込み、および読み取りまたは書き込みの移動を許可しないバリアという 2 つの部分から構築する必要がある場合があります。この場合、バリアの配置が重要です。読み取り/取得バリアの場合、最初にフラグの読み取り、次にバリア、次に共有データの読み取りと書き込みが行われます。書き込み解放バリアの場合、共有データの読み取りと書き込みが最初に行われ、次にバリア、次にフラグの書き込みが行われます。

// 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 の並べ替えを防ぐことが重要です。

オペレーティングシステムによって提供される同期プリミティブを使用する利点の 1 つは、それらのすべてに適切なメモリバリアが含まれることです。

コンパイラの並べ替えの防止

コンパイラのジョブは、パフォーマンスを向上させるためにコードを積極的に最適化することです。これには、役に立つ場所や動作が変更されない場所での再配置命令が含まれます。 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 の並べ替えは、コンパイラの並べ替えよりも微妙です。それが直接起こるのを見ることはできません。不可解なバグが表示されます。読み取りと書き込みの CPU の並べ替えを防ぐためには、一部のプロセッサでメモリバリア命令を使用する必要があります。 Xbox 360 と Windows のメモリバリア命令の汎用名は MemoryBarrier です。このマクロは、プラットフォームごとに適切に実装されます。

Xbox 360 では、 MemoryBarrier は lwsync (軽量同期) として定義され、ppcintrinsics.h で定義されている __lwsync 組み込みでも使用できます。 __lwsync はコンパイラのメモリバリアとしても機能し、コンパイラによる読み取りと書き込みの再配置を防ぎます。

lwsync 命令は、1 つのプロセッサコアを L2 キャッシュと同期する Xbox 360 のメモリバリアです。 これにより、lwsync より前のすべての書き込みが、その後の書き込みの前に L2 キャッシュに書き込まれることが保証されます。また、 lwsync に続く読み取りでは、以前の読み取りよりも L2 から古いデータが取得されていないことも保証されます。妨げにならない並べ替えの 1 つの種類は、別のアドレスへの書き込みの前に移動する読み取りです。したがって、 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 による読み取り順序変更を防ぐ方法が 1 つあります。ポインターを読み取り、そのポインターを使用して他のデータを読み込む場合、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 命令では、キャッシュ可能なメモリへの読み取りと書き込みの並べ替えのみが禁止されます。デバイスドライバーの作成者や Xbox 360 のゲーム開発者にとって一般的な手法であるPAGE_NOCACHEまたはPAGE_WRITECOMBINEとしてメモリを割り当てる場合、 MemoryBarrier はこのメモリへのアクセスには影響しません。ほとんどの開発者は、キャッシュ不可能なメモリの同期は必要ありません。ただし、この点についてはこの記事では取り扱いません。

インターロックされた関数と CPU の並べ替え

リソースを取得または解放する読み取りまたは書き込みが 、InterlockedXxx 関数のいずれかを使用して行われる場合があります。 Windows では、これは物事を簡略化します。Windows では、 InterlockedXxx 関数はすべてフルメモリバリアであるためです。その前と後の両方に CPU メモリバリアが効果的に存在します。つまり、完全な読み取り/取得または書き込み解放バリアがすべて単独で行われます。

Xbox 360 では、 InterlockedXxx 関数には CPU メモリバリアが含まれていません。読み取りと書き込みのコンパイラの並べ替えを防ぎますが、CPU の並べ替えは行いません。したがって、ほとんどの場合、Xbox 360 で InterlockedXxx 関数を使用する場合は、読み取り/取得または書き込み/解放バリアにするために、 __lwsyncに先行またはフォローする必要があります。便宜上、読みやすくするために、多くの InterlockedXxx 関数の Acquire バージョンと Release バージョンがあります。これらは、組み込みのメモリバリアが付属しています。たとえば、 InterlockedIncrementAcquire は、インターロックされたインクリメントの後に __lwsync メモリバリアを実行して、完全な読み取り/取得機能を提供します。

意図をより明確にし、メモリバリア命令を正しい場所に簡単に取得できるように、InterlockedXxx 関数の Acquire バージョンと Release バージョンを使用することをお勧めします (そのほとんどは Windows でも使用でき、パフォーマンスの低下はありません)。メモリバリアのない Xbox 360 での InterlockedXxx の使用は、多くの場合バグであるため、非常に慎重に検討する必要があります。

このサンプルでは、InterlockedXxxSList 関数の Acquire バージョンと Release バージョンを使用して、1 つのスレッドがタスクまたはその他のデータを別のスレッドに渡す方法を示します。 InterlockedXxxSList 関数は、1 つの共有リンクリストをロックなしで維持するための関数ファミリです。これらの関数の Acquire および Release バリアントは 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 以降では、volatile 変数からの読み取りは読み取り/取得セマンティクスを持つよう定義され、volatile 変数への書き込みは書き込みリリースセマンティクスを持つよう定義されています。つまり、コンパイラは読み取りと書き込みを後に並べ替えることはありません。また、Windows では、CPU で同じことが行われなくなります。

これらの新しい保証は、Visual C++ 2005 と今後のバージョンの Visual C++ にのみ適用されることを理解しておくことが重要です。他のベンダーのコンパイラは、通常、Visual C++ 2005 の追加の保証なしで、異なるセマンティクスを実装します。また、Xbox 360 では、CPU が読み取りと書き込みを並べ替えないようにするための命令はコンパイラによって挿入されません。

Lock-Free データパイプの例

パイプは、1 つ以上のスレッドが他のスレッドによって読み取られたデータを書き込む構造です。パイプのロックレスバージョンは、スレッドからスレッドに作業を渡すエレガントで効率的な方法です。 DirectX SDK では、 DXUTLockFreePipe.h で使用できる単一リーダーのシングルライターロックレスパイプである LockFreePipe が提供されます。 AtgLockFreePipe.h の Xbox 360 SDK では、同じ LockFreePipe を使用できます。

LockFreePipe は、2 つのスレッドにプロデューサーとコンシューマーの関係がある場合に使用できます。プロデューサースレッドは、コンシューマースレッドが後日処理できるようにパイプにデータを書き込むことができます。ブロックする必要はありません。パイプがいっぱいになると書き込みが失敗し、プロデューサースレッドは後でもう一度試す必要がありますが、これはプロデューサースレッドが先にある場合にのみ発生します。パイプが空になった場合、読み取りは失敗し、コンシューマースレッドは後でもう一度試す必要がありますが、これはコンシューマースレッドが実行する作業がない場合にのみ発生します。 2 つのスレッドのバランスが整っていて、パイプが十分な大きさである場合、パイプは遅延やブロックなしでデータをスムーズに渡すことができます。

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 を使用することを検討してください。これにより、取得しようとしたときにクリティカルセクションが所有されている場合は、すぐにミューテックスに遅延するのではなく、クリティカルセクションが使用可能になるまでオペレーティングシステムがしばらくスピンします。スピンカウントの恩恵を受けることができる重要なセクションを特定するには、特定のロックの一般的な待機の長さを測定する必要があります。

共有ヒープがメモリ割り当て (既定の動作) に使用される場合、すべてのメモリ割り当てと空き時間にはロックの取得が含まれます。スレッドの数と割り当ての数が増えると、パフォーマンスレベルがオフになり、最終的には減少し始めます。スレッドごとのヒープを使用したり、割り当ての数を減らしたりすると、このロックのボトルネックを回避できます。

あるスレッドがデータを生成していて、別のスレッドがデータを消費している場合、データを頻繁に共有する可能性があります。これは、あるスレッドがリソースを読み込み、別のスレッドがシーンをレンダリングしている場合に発生する可能性があります。レンダリングスレッドがすべての描画呼び出しで共有データを参照する場合、ロックのオーバーヘッドが高くなります。各スレッドにプライベートデータ構造があり、フレームごとに 1 回同期される場合は、はるかに優れたパフォーマンスを実現できます。

ロックレスアルゴリズムは、ロックを使用するアルゴリズムよりも高速であるとは限りません。ロックを回避する前に、ロックによって実際に問題が発生しているかどうかを確認チェックし、ロックレスコードが実際にパフォーマンスを向上させるかどうかを測定する必要があります。

プラットフォームの相違点の概要

InterlockedXxx 関数は、Windows では CPU の読み取り/書き込みの並べ替えを防止しますが、Xbox 360 では並べ替えできません。
Visual Studio C++ 2005 を使用した揮発性変数の読み取りと書き込みは、Windows では CPU の読み取り/書き込みの並べ替えを防止しますが、Xbox 360 ではコンパイラの読み取り/書き込みの並べ替えのみが禁止されます。
書き込みは Xbox 360 では並べ替えされますが、x86 または x64 では並べ替えされません。
読み取りは Xbox 360 で並べ替えられますが、x86 または x64 では、読み取りと書き込みが異なる場所を対象とする場合にのみ、書き込みに対してのみ順序が変更されます。

Recommendations

正しく使用する方が簡単であるため、可能な場合はロックを使用します。
ロックのコストが大きくならないように、ロックの頻度が高くなりすぎないようにしてください。
長い屋台を避けるために、ロックを長く保持しないようにしてください。
必要に応じてロックレスプログラミングを使用しますが、メリットによって複雑さが正当化されることを確認してください。
遅延プロシージャ呼び出しと通常のコードの間でデータを共有する場合など、他のロックが禁止されている場合は、ロックレスプログラミングまたはスピンロックを使用します。
正しいと証明された標準のロックレスプログラミングアルゴリズムのみを使用します。
ロックレスプログラミングを行う場合は、必要に応じて volatile フラグ変数とメモリバリア命令を使用してください。
Xbox 360 で InterlockedXxx を 使用する場合は、 Acquire と Release のバリエーションを使用します。

リファレンス

MSDN ライブラリ。 "volatile (C++)"。C++ 言語リファレンス。
ヴァンス・モリソン "マルチスレッドアプリにおけるLow-Lock手法の影響を理解する"MSDN マガジン、2005 年 10 月。
ライオンズ、マイケル。 "PowerPC ストレージモデルと AIX プログラミング"IBM developerWorks、2005 年 11 月 16 日。
McKenney、Paul E. "モダンマイクロプロセッサのメモリ順序付け、パート 2"Linux ジャーナル、2005 年 9 月。 [この記事には、いくつかの x86 の詳細があります。]
Intel Corporation。 "Intel® 64 アーキテクチャメモリの順序付け"2007 年 8 月。 [IA-32 と Intel 64 の両方のプロセッサに適用されます。
ニーブラー、Eric。 "トリップレポート: C++ のスレッドでのアドホック会議"C++ ソース、2006 年 10 月 17 日。
ハート、トーマス E. 2006。 "ロックレス同期を高速にする: メモリの再利用によるパフォーマンスへの影響"。2006国際並列分散処理シンポジウム(IPDPS 2006)、ギリシャ、ロードス島、2006年4月の議事録。

次の方法で共有

Xbox 360 および Microsoft Windows のロックレスプログラミングに関する考慮事項

ロックを使用したプログラミング

ロックレスプログラミング

非アトミック操作

原子性の保証

並べ替え

書き込みの CPU 再配置について

Xbox 360

x 86 および x64

読み取りの CPU 再配置について

Xbox 360

x 86 および x64

その他の並べ替え

概要の並べ替え

Read-AcquireとWrite-Releaseバリア

コンパイラの並べ替えの防止

CPU の並べ替えの防止

インターロックされた関数と CPU の並べ替え

揮発性変数と並べ替え

Lock-Free データパイプの例

Xbox 360 のパフォーマンス

Windows パフォーマンス

パフォーマンスに関する考え方

プラットフォームの相違点の概要

Recommendations

リファレンス

フィードバック

フィードバック

その他のリソース

次の方法で共有

Xbox 360 および Microsoft Windows のロックレス プログラミングに関する考慮事項

ロックを使用したプログラミング

ロックレス プログラミング

非アトミック操作

原子性の保証

並べ替え

書き込みの CPU 再配置について

Xbox 360

x 86 および x64

読み取りの CPU 再配置について

Xbox 360

x 86 および x64

その他の並べ替え

概要の並べ替え

Read-AcquireとWrite-Releaseバリア

コンパイラの並べ替えの防止

CPU の並べ替えの防止

インターロックされた関数と CPU の並べ替え

揮発性変数と並べ替え

Lock-Free データ パイプの例

Xbox 360 のパフォーマンス

Windows パフォーマンス

パフォーマンスに関する考え方

プラットフォームの相違点の概要

Recommendations

リファレンス

フィードバック

フィードバック

その他のリソース

Xbox 360 および Microsoft Windows のロックレスプログラミングに関する考慮事項

ロックレスプログラミング

Lock-Free データパイプの例