Xbox 360 および Microsoft Windows のロックレス プログラミングに関する考慮事項
ロックレス プログラミングは、ロックの取得と解放のコストなしに、複数のスレッド間で変更データを安全に共有する方法です。 これは一見、万能の解決策に思えるものの、実際には複雑で微妙な技術であり、期待したほどの利点が得られない場合もあります。 ロックレス プログラミングは特に 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 では、メモリ内の変数をインクリメントするために使用できる単一の命令 (inc) があります。 この命令を使用すると、変数のインクリメントは単一プロセッサ システムではアトミックですが、マルチ プロセッサ システムではまだアトミックではありません。 x86 および x64 ベースのマルチ プロセッサ システムで inc をアトミックにするには、lock プレフィックスを使用する必要があります。これにより、他のプロセッサが 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 が次のコードに示された書き込みを並べ替えると、別のスレッドは、alive フラグが設定されているのを見ながらも、まだ x または y の古い値を見る可能性があります。 読み取り時にも同様の並べ替えが起こる可能性があります。
このコードでは、1 つのスレッドが 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 バイトのブロックを 1 回の操作で L2 キャッシュに書き込むことができます。 8 つのストアギャザーバッファーがあり、メモリの複数の異なる領域への効率的な書き込みが可能です。
ストアギャザー バッファーは通常、先入れ先出し (FIFO) 順で L2 キャッシュに書き込まれます。 ただし、書き込みの対象キャッシュ ラインが L2 キャッシュにない場合、そのキャッシュ ラインがメモリからフェッチされている間、その書き込みが遅延する可能性があります。
ストアギャザー バッファーが厳密な FIFO 順で L2 キャッシュに書き込まれる場合でも、個々の書き込みが順番に L2 キャッシュに書き込まれることは担保されません。 たとえば、CPU がアドレス 0x1000 に書き込み、次にアドレス 0x2000 に書き込み、次にアドレス 0x1004 に書き込むとします。 最初の書き込みは、ストアギャザー バッファーを割り当て、キューの先頭に置きます。 2 番目の書き込みは、別のストアギャザー バッファーを割り当て、キューのその次に置きます。 3 番目の書き込みは、最初のストアギャザー バッファーにデータを追加し、キューの先頭に残ります。 したがって、3 回目の書き込みは、2 回目の書き込みよりも先に L2 キャッシュに送られることになります。
ストアギャザーバッファーによる並べ替えは基本的に予測できません。これは特に、1 つのコア上の 2 つのスレッドがストアギャザーバッファーを共有するため、ストアギャザー バッファーの割り当てと空にするタイミングが非常に不安定になるためです。
これは、書き込みが並べ替えられる可能性の一例です。 他の可能性も考えられます。
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 |
|---|---|---|
| 読み取りを読み取りの前に移動 | いいえ | はい |
| 書き込みを書き込みの前に移動 | いいえ | はい |
| 書き込みを読み取りの前に移動 | いいえ | はい |
| 読み取りを書き込みの前に移動 | はい | はい |
読み取り取得バリアと書き込み解放バリア
読み取りと書き込みの並べ替えを禁止するために使用する主な構成要素は、読み取り取得バリアと書き込み解放バリアと呼ばれます。 読み取り取得は、リソースの所有権を取得するためのフラグまたはその他の変数の読み取りのことであり、並べ替えを禁止するバリアと組み合わせて使用されます。 同様に、書き込み解放は、リソースの所有権を譲渡するためのフラグや他の変数の書き込みであり、並べ替えを禁止するバリアと組み合わせて使用されます。
Herb Sutter 氏による正式な定義は次のとおりです。
- 読み取り取得は、プログラム順序において後続の同じスレッドのすべての読み取りと書き込みよりも先に実行されます。
- 書き込み解放操作は、プログラム順序において先行の同じスレッドのすべての読み取りと書き込みよりも後に実行されます。
コードがメモリの所有権を取得すると、それがロックの取得によるものであれ、(ロックなしで) 共有リンク リストからの項目の取り出しによるものであれ、常に読み取りが含まれます。これにより、メモリの所有権が取得されたかどうかを確認するためのフラグまたはポインターがテストされます。 この読み取りは 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;
次のコードでは、別のスレッドが 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 による並べ替えはコンパイラによる並べ替えよりも微妙です。 直接目にすることはできず、不可解なバグとして現れます。 CPU による読み取りと書き込みの並べ替えを禁止するには、プロセッサによってはメモリ バリア命令を使用する必要があります。 Xbox 360 と Windows での汎用的なメモリ バリア命令の名前は MemoryBarrier です。 このマクロは各プラットフォームに適切に実装されています。
Xbox 360 では、MemoryBarrier は lwsync (軽量同期) として定義されており、ppcintrinsics.h で定義されている __lwsync 組み込み関数からも使用できます。 __lwsync はコンパイラ メモリ バリアとしても機能して、コンパイラによる読み取りと書き込みの並べ替えを禁止します。
lwsync 命令は Xbox 360 のメモリ バリアで、1 つのプロセッサ コアを L2 キャッシュと同期させます。 これにより、lwsync の前のすべての書き込みが後の書き込みよりも先に L2 キャッシュに確実に到達することが担保されます。 また、lwsync に続く読み取りが、先行する読み取りよりも古いデータを L2 から取得しないことも担保されます。 この方法で禁止できない唯一の並べ替えは、読み取りが異なるアドレスへの書き込みの前に移動することです。 したがって、lwsync は x86 および x64 プロセッサの既定のメモリ順序と一致するメモリ順序を適用します。 完全なメモリ順序を得るには、よりコストのかかる sync 命令 (ヘビーウェイト同期とも呼ばれる) が必要ですが、ほとんどの場合、これは不要です。 Xbox 360 でのメモリ並べ替えオプションを次の表に示します。
| Xbox 360 での並べ替え | No sync | lwsync | sync |
|---|---|---|---|
| 読み取りを読み取りの前に移動 | はい | いいえ | いいえ |
| 書き込みを書き込みの前に移動 | はい | いいえ | いいえ |
| 書き込みを読み取りの前に移動 | はい | いいえ | いいえ |
| 読み取りを書き込みの前に移動 | はい | はい | いいえ |
PowerPC には、同期命令 isync と eieio (キャッシュ禁止メモリへの並べ替えを制御するために使用) もあります。 これらの同期命令は通常の同期目的には必要ありません。
Windows では、MemoryBarrier は Winnt.h で定義されており、コンパイルが x86 用か x64 用かによって異なるメモリ バリア命令が用意されています。 メモリ バリア命令は完全なバリアとして機能し、バリアの後へのすべての読み取りと書き込みの並べ替えを禁止します。 このように、MemoryBarrier は Windows でよりも 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 命令は、キャッシュ可能なメモリへの読み取りと書き込みの並べ替えのみを禁止します。 PAGE_NOCACHE または PAGE_WRITECOMBINE としてメモリを割り当てる場合 (デバイス ドライバー作成者や Xbox 360 ゲーム開発者がよく使用する手法)、MemoryBarrier はこのメモリへのアクセスに影響しません。 ほとんどの開発者はキャッシュ不可能なメモリの同期を必要としません。 ただし、この点についてはこの記事では取り扱いません。
インターロック関数と CPU による並べ替え
リソースを取得または解放する読み取りや書き込みが、InterlockedXxx 関数のいずれかを使用して行われることがあります。 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 バージョンを使用して、あるスレッドが別のスレッドにタスクやその他のデータを渡す方法を示しています。 InterlockedXxxSList 関数は、ロックなしで共有単方向リンク リストを維持するための一連の関数です。 これらの関数の 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;
}
volatile 変数と並べ替え
C++ 標準では、volatile 変数の読み取りはキャッシュできず、volatile な書き込みは遅延できず、volatile な読み取りと書き込みはそれらの間で並べ替えることができないと規定されています。 これはハードウェア デバイスとの通信には十分であり、C++ 標準の volatile キーワードの目的です。
ただし、標準でのこの担保は、マルチスレッドで volatile を使用するには不十分です。 C++ 標準では、コンパイラが volatile な読み書きに対して非 volatile な読み書きの順序を変更することを禁止していません。また、CPU による並べ替えの禁止についても何ら言及していません。
Visual C++ 2005 は標準の C++ を超えて、volatile な変数アクセスに対してマルチスレッドに適したセマンティクスを定義しています。 Visual C++ 2005 以降、volatile 変数からの読み取りは読み取り取得セマンティクスを持つと定義され、volatile 変数への書き込みは書き込み解放セマンティクスを持つと定義されています。 これは、コンパイラが読み取りと書き込みをそれらの間で並べ替えず、Windows では CPU も並べ替えを行わないことを意味します。
重要なのは、これらの新しい担保が Visual C++ 2005 以降のバージョンにのみ適用されるということです。 他のベンダーのコンパイラは一般的に異なるセマンティクスを実装し、Visual C++ 2005 の追加の担保はありません。 また、Xbox 360 では、コンパイラは CPU による読み取りと書き込みの並べ替えを禁止する命令を挿入しません。
ロック制御不要のデータ パイプの例
パイプは、1 つ以上のスレッドがデータを書き込み、それを他のスレッドが読み取ることを可能にする構造です。 ロックレス バージョンのパイプは、スレッド間でタスクを渡すための洗練された効率的な方法です。 DirectX SDK には、単一リーダー、単一ライターのロックレス パイプである LockFreePipe が用意されており、DXUTLockFreePipe.h で使用できます。 同じ LockFreePipe が Xbox 360 SDK にも用意されており、AtgLockFreePipe.h で使用できます。
LockFreePipe は、2 つのスレッドがプロデューサー/コンシューマーの関係にある場合に使用できます。 プロデューサー スレッドは、コンシューマー スレッドが後で処理できるようにパイプにデータを書き込むことができ、ブロックされることはありません。 パイプがいっぱいになると、書き込みは失敗し、プロデューサー スレッドは後で再試行する必要があります。ただし、この状態になるのは、プロデューサー スレッドが先行している場合のみです。 パイプが空になると、読み取りは失敗し、コンシューマー スレッドは後で再試行する必要があります。ただし、この状態になるのは、コンシューマー スレッドが行うタスクがない場合のみです。 2 つのスレッドのバランスが取れていて、パイプが十分に大きい場合、パイプを使用すると、遅延やブロックなしでデータをスムーズに渡すことができます。
Xbox 360 のパフォーマンス
Xbox 360 での同期命令と関数のパフォーマンスは実行中の他のコードに応じて変化します。 別のスレッドが現在ロックを所有している場合、ロックの取得にはさらに時間がかかります。 他のスレッドが同じキャッシュ ラインに書き込んでいる場合、InterlockedIncrement とクリティカル セクション操作にはさらに時間がかかります。 ストア キューの内容もパフォーマンスに影響する可能性があります。 したがって、これらの数値はすべて非常に単純なテストから生成された概算値にすぎません。
- lwsync は 33 ～ 48 サイクルかかると測定されました。
- InterlockedIncrement は 225 ～ 260 サイクルかかると測定されました。
- クリティカル セクションの取得または解放には約 345 サイクルかかると測定されました。
- mutex の取得または解放には約 2,350 サイクルかかると測定されました。
Windows パフォーマンス
Windows での同期命令と関数のパフォーマンスは、プロセッサの種類と構成、および実行中の他のコードに応じて大きく異なります。 マルチコアおよびマルチソケット システムでは、同期命令の実行に時間がかかることが多く、別のスレッドが現在ロックを所有している場合、ロックの取得にはさらに時間がかかります。
しかし、非常に単純なテストから生成された測定値でも役立ちます。
- MemoryBarrier は 20 ～ 90 サイクルかかると測定されました。
- InterlockedIncrement は 36 ～ 90 サイクルかかると測定されました。
- クリティカル セクションの取得または解放には 40 ～ 100 サイクルかかると測定されました。
- mutex の取得または解放には約 750 ～ 2,500 サイクルかかると測定されました。
これらのテストはさまざまな種類のプロセッサ上の Windows XP で行われました。 短い時間はシングルプロセッサ マシンでの結果で、長い時間はマルチプロセッサ マシンでの結果です。
ロックの取得と解放は、ロックレス プログラミングを使用するよりもコストがかかりますが、データを共有する頻度を減らして、最終的にコストを回避することをお勧めします。
パフォーマンスに関する考察
クリティカル セクションの取得または解放は、メモリ バリア、InterlockedXxx 操作、さらに必要に応じて再帰を処理し、mutex にフォールバックするための追加のチェックで構成されます。 独自のクリティカル セクションを実装する際は注意が必要です。なぜなら、mutex にフォールバックせずに、ループ内でロックが解放されるのを待ち続けるスピン ロックにより、パフォーマンスが大幅に低下する可能性があるためです。 激しい競合が発生するが、短時間しか保持されないクリティカル セクションに対しては、InitializeCriticalSectionAndSpinCount の使用を検討するとよいでしょう。これにより、クリティカル セクションを取得しようとしたときに既にそのセクションが所有されていた場合、オペレーティング システムがすぐに mutex に切り替えるのではなく、一定時間スピンしてクリティカル セクションが利用可能になるのを待つようになります。 スピン カウントが効果的なクリティカル セクションを特定するためには、特定のロックの典型的な待ち時間を測定する必要があります。
共有ヒープがメモリ割り当てに使用される場合 (既定の動作)、すべてのメモリ割り当ておよび解放にはロックの取得が伴います。 スレッド数と割り当ての数が増加するにつれて、パフォーマンスは頭打ちになり、最終的に低下し始めます。 スレッドごとのヒープを使用するか、割り当ての数を減らすことで、このロックのボトルネックを回避できます。
1 つのスレッドがデータを生成し、別のスレッドがデータを消費する場合、頻繁にデータを共有することになる可能性があります。 この問題は、1 つのスレッドがリソースを読み込み、別のスレッドがシーンをレンダリングしている場合に起こり得ます。 レンダリング スレッドが描画呼び出しごとに共有データを参照する場合、ロックのオーバーヘッドは高くなります。 各スレッドがプライベートなデータ構造を持ち、フレームごとに 1 回以下で同期させれば、パフォーマンスを大幅に向上させることができます。
ロックレス アルゴリズムが、ロックを使用するアルゴリズムよりも速いことは担保されていません。 ロックを回避しようとする前に、実際にロックが問題の原因となっているかどうかを確認し、ロックレス コードにより実際にパフォーマンスが向上するかどうかを測定するとよいでしょう。
プラットフォームの違いのまとめ
- InterlockedXxx 関数は、Windows では CPU による読み取り/書き込みの並べ替えを禁止しますが、Xbox 360 では禁止しません。
- Visual Studio C++ 2005 を使用した volatile 変数の読み取りと書き込みは、Windows では CPU による読み取り/書き込みの並べ替えを禁止しますが、Xbox 360 ではコンパイラによる読み取り/書き込みの並べ替えのみを禁止します。
- Xbox 360 では書き込みが並べ替えられますが、x86 または x64 では並べ替えられません。
- Xbox 360 では読み取りが並べ替えられますが、x86 または x64 では書き込みに対してのみ並べ替えられます。ただし、読み取りと書き込みが異なるアドレスを対象とする場合のみです。
推奨事項
- ロックを正しく使用するのは簡単なので、可能な限り使用してください。
- ロックのコストが大きくなりすぎないように、頻繁なロックを避けてください。
- 長時間の停止を避けるために、ロックを長時間保持しないようにしてください。
- 適切な場合はロックレス プログラミングを使用しますが、そのメリットが複雑さに見合うものであることを確認してください。
- 他のロックが禁止されている状況、たとえば遅延プロシージャ呼び出しと通常のコードの間でデータを共有する場合などでは、ロックレス プログラミングまたはスピン ロックを使用してください。
- 正しいことが証明されている標準のロックレス プログラミング アルゴリズムのみを使用してください。
- ロックレス プログラミングを行う際は、必要に応じて volatile フラグ変数とメモリ バリア命令を使用するようにしてください。
- Xbox 360 で InterlockedXxx を使用する際は、Acquire バージョンと Release バージョンを使用してください。
関連情報
- 「volatile (C++)」。C++ 言語リファレンス。
- Vance Morrison 氏。 「マルチスレッド アプリケーションにおける低ロック手法の影響を理解する」。MSDN Magazine、2005 年 10 月。
- Lyons, Michael 氏。 「PowerPC ストレージ モデルと AIX プログラミング」。IBM developerWorks、2005 年 11 月 16 日。
- McKenney, Paul E 氏。「最新のマイクロ プロセッサにおけるメモリの順序付け、パート II」。Linux Journal、2005 年 9 月。 [この記事には x86 に関する詳細が含まれています。]
- Intel Corporation。 「Intel® 64 アーキテクチャにおけるメモリの順序付け」。2007 年 8 月。 [IA-32 と Intel 64 の両方のプロセッサに適用されます。]
- Niebler, Eric 氏。 「Trip Report: Ad-Hoc Meeting on Threads in C++」。The C++ Source、2006 年 10 月 17 日。
- Hart, Thomas E 氏。2006 年。 「ロックレス同期の高速化: パフォーマンスへのメモリ再利用の影響」。2006 International Parallel and Distributed Processing Symposium (IPDPS 2006) 会議録、ギリシャ、ロードス島、2006 年 4 月。