次の方法で共有

Xbox 360 と Microsoft Windows でのロックレス プログラミングの考慮事項

  • [アーティクル]

ソフトウェア デザイン エンジニア、Bruce Dawson 著

ゲーム ディベロッパー グループ

ロックレス プログラミングとは、刻々と変化するデータを、ロックの取得や解放といったコストを伴うことなく、複数のスレッド間で安全に共有するための方法です。そのように言うと、万能な解決策のように聞こえるかもしれませんが、ロックレス プログラミングには、複雑かつ難解であり、ときには思ったほどの効果が得られない場合もあります。ロックレス プログラミングは、Xbox 360 では特に複雑です。

ロックレス プログラミングは、マルチ スレッド プログラミングにおいて有効なテクニックですが、安易に使用するべきではありません。ロックレス プログラミングを使用する前に、必ずさまざまな問題点を理解した上で、期待する効果を得られるかどうかについて慎重に検討を行ってください。実際には、より単純で効率のよい解決策が見つかることがほとんどです。たとえば、データを共有する頻度を減らすことができるのであれば、あえて、ロックレス プログラミングを選ぶ必要はありません。

ロックレス プログラミングを正確かつ安全に使用するには、ハードウェアとコンパイラの両方について熟知している必要があります。このホワイト ペーパーでは、ロックレス プログラミングのテクニックを使用する場合に考慮する必要のある問題について簡単に説明しています。

ロックを使ったプログラミング

マルチ スレッド コードを記述していると、データを複数のスレッド間で共有しなければならないケースがたびたびあります。共有されたデータ構造に対し、複数のスレッドが同時に読み書きを行うと、メモリーが破損する場合があります。この問題を解決する最も簡単な方法は、ロックを使用することです。たとえば、同時に複数のスレッドから実行されては困る ManipulateSharedData があるとき、次のように、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 には、"優先順位の逆転" (優先度の低いスレッドによってロックが解放されるのを、優先度の高いスレッドがループ状態で待つこと) に対する保護機構が存在しません。さらに、受動的プロシージャ呼び出し (DPC) または割り込みサービス ルーチン (ISR) がロックを取得しようとした場合にも、デッドロックが発生することがあります。

こうした問題点を踏まえても、同期プリミティブ (クリティカル セクションなど) が、複数のスレッドを制御する最も有力な手段であることに変わりはありません。同期プリミティブではパフォーマンスが低すぎるという場合は、その使用頻度を減らすのが普通です。しかし、それを承知の上で、複雑さをいとわないという方のための選択肢として、ロックレス プログラミングがあります。

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

ロックレス プログラミングはその名前が示唆するように、共有されたデータを、ロックを使わずに操作するためのテクニックの一つです。一口にロックレスなアルゴリズムと言っても、メッセージの受け渡しのためのアルゴリズムもあれば、リストやキューのデータを共有するためのアルゴリズムもあります。

ロックレスなプログラミングを実現するためには、2 つの課題を克服する必要があります。非アトミック操作と順序変更です。

非アトミック操作

アトミックな操作とは、それ以上分割することのできない処理のことです。つまり、操作の途中で他のスレッドによって観測されないことが保証された操作をいいます。アトミックな操作は、ロックレス プログラミングにおいて重要な意味を持ちます。操作が "アトミック" でなければ、書き込み途中の値など、不完全な状態が、他のスレッドから参照されてしまう可能性があります。

最近のプロセッサであれば、自然にアラインメントされたネイティブ タイプの読み取りと書き込みは、アトミックであると考えることができます。メモリー バスの幅が、読み取りまたは書き込みの対象となる型と同じかそれ以上であれば、CPU は、これらの型の読み取りと書き込みを 1 回のバス トランザクションで実行するため、不完全な状態が他のスレッドによって参照されることはありません。x86 および x64 では、8 バイトを超える読み取りおよび書き込みがアトミックな操作である保証はありません。つまり、SSE (ストリーミング SIMD 拡張命令) レジスタの 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);

順序変更

順序変更の問題はさらにやっかいです。読み取りと書き込みは、常にコードに記述した順序で行われるとは限りません。このことが、きわめて複雑な問題を招くことがあります。一般に、マルチ スレッド アルゴリズムでは、スレッドがなんらかのデータを書き込むと、そのデータの処理が完了していることを他のスレッドに伝えるための情報をフラグに書き込みます。これを "Write-Release" といいます。書き込みの順序が変更された場合、他のスレッドからは、まだデータが書き込まれていないにもかかわらず、フラグが設定されているように見えてしまう可能性があります。

同様に、スレッドは、フラグから情報を読み取り、共有データに対するアクセス権を取得できたことがわかって初めて、その共有データを読み取るのが一般的です。これを "Read-Acquire" といいます。読み取りの順序が変更された場合は、フラグの前に共有ストレージからデータが読み取られることがあり、表示される値が最新のものではない可能性があります。

読み取りと書き込みの順序変更は、コンパイラによって行われる場合とプロセッサによって行われる場合とがあります。こうした順序変更は今になって始まったことではありませんが、シングル プロセッサ マシンでは、それほど大きな問題にはなりませんでした。これはシングルプロセッサのマシンでは CPU による読み取りと書き込みの順序変更が不可視であり (デバイス ドライバーの一部でない非デバイス ドライバー コードの場合)、またシングルプロセッサのマシンではコンパイラによる読み取りと書き込みの順序変更でも問題が起こる可能性が低いからです。

次のコードに示した書き込みの順序がコンパイラまたは CPU によって変更された場合、他のスレッドは、仮に alive フラグが設定されていたとしても、古い状態の 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 バイト ブロックを 1 回の操作で L2 キャッシュに書き込むことができます。実際には 8 つのストア収集バッファーが存在するため、複数の異なるメモリー領域に対して、より効率的に書き込みを行うことが可能です。

ストア収集バッファーから L2 キャッシュへの書き込みは、先入れ先出し (FIFO) 方式で実行されますが、書き込み先のキャッシュ ラインが L2 キャッシュに存在しない場合は、キャッシュ ラインをメモリーからフェッチするまでの間、書き込みが遅延することもあります。

ストア収集バッファーが厳密に FIFO の順番で L2 キャッシュに書き込まれるからといって、それぞれの書き込みが、規則的に L2 キャッシュに書き込まれるとは限りません。たとえば、CPU が 0x1000 番地、0x2000 番地、0x1004 番地の順に書き込みを行うとします。最初の書き込みが、ストア収集バッファーに割り当てられ、キューの先頭に格納されます。2 番目の書き込みは、別のストア収集バッファーに割り当てられ、キューの 2 番目に格納されます。3 番目の書き込みで、そのデータが、キューの先頭にある最初のストア収集バッファーに追加されたとしたらどうでしょうか。3 番目の書き込みは、2 番目の書き込みよりも先に、L2 キャッシュに到達することになります。

ストア収集バッファーに起因する順序変更は、基本的に予測できません。特に、複数のストア収集バッファーがコア上の複数のスレッドによって共有され、その割り当てと解放がばらばらに行われることを考えれば、その理由は明らかです。

これは、書き込みの順序が変更される例の一つに過ぎません。他にもさまざまな可能性が考えられます。

x86 および x64

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

CPU による読み取りの順序変更について

一部の CPU では、共有ストレージから効率よくデータを読み取るために、プログラムの命令とは異なる順序で読み取りが実行される場合があります。この変更はシングルスレッドの非ドライバー コードからは見えませんが、マルチスレッド コードでは問題が起こることがあります。

Xbox 360

キャッシュ ミスは一部の読み取り操作を遅延させる場合があり、これによって読み取りデータが効率的に共有メモリーから不規則に取得されます。このキャッシュ ミスのタイミングは基本的に予測不可能です。プリフェッチと分岐予測によって、データを共有メモリーから順番どおりに取得できなくなる場合もあります。以上、読み取りの順序が具体的にどのように変更されるかを示しましたが、これは一つの例に過ぎません。他にもさまざまな可能性が考えられます。この読み取り順序の変更は、特に PowerPC メモリー モデルで発生します。

x86 および x64

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

その他の順序変更

x86 の CPU および 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
    ...
}

問題は、f0 への書き込みが共有ストレージに対して実行される前に、P0Acquire の f1 の読み取りが共有ストレージから読み取られる場合があることです。一方で、f1 への書き込みが共有ストレージに対して実行される前に、P1Acquire の f0 の読み取りが共有ストレージから読み取られる場合があります。この結果、両方のスレッドでフラグが TRUE に設定され、両方のスレッドで他方のスレッドのフラグが FALSE と確認されるため、両方のスレッドがクリティカル領域に入ることになります。このため、x86 ベースおよび x64 ベースのシステムでの順序変更による問題は、Xbox 360 での問題より一般的ではないものの、発生する可能性はあります。Dekker のアルゴリズムは、これらのプラットフォームではハードウェア メモリー バリアがなければ機能しなくなります。

x86 の CPU および x64 の CPU では、書き込みが前の読み取りより先になるように順序変更されることはありません。x86 の CPU および x64 の CPU では、ターゲットの場所が異なる場合に、読み取りが前の書き込みより先になるように順序変更されるだけです。

PowerPC の CPU では、ターゲットのアドレスが異なる限り、読み取りが書き込みより先になるように、また書き込みが読み取りより先になるように順序変更できます。

順序変更の概要

Xbox 360 の CPU では、次の表に示すように、x86 の CPU および x64 の CPU の場合よりも積極的にメモリー操作の順序が変更されます。詳細については、プロセッサのドキュメントを参照してください。

順序変更の処理 x86 および x64 Xbox 360

読み取りを読み取りの先に移動する

不可

可

書き込みを書き込みの先に移動する

不可

可

書き込みを読み取りの先に移動する

不可

可

読み取りを書き込みの先に移動する

可

可

Read-Acquire バリアと Write-Release バリア

読み取りと書き込みの順序変更を回避する代表的な手段として、Read-Acquire バリアと Write-Release バリアがあります。Read-Acquire とは、リソースの所有権を獲得するための変数 (フラグ) の読み取りと、順序変更を防ぐための保護機構 (バリア) とを組み合わせた概念です。同様に、Write-Release とは、リソースの所有権を解放するための変数 (フラグ) の書き込みと、順序変更を防ぐための保護機構 (バリア) とを組み合わせた概念です。

以下は、Herb Sutter 氏による定義を引用したものです。

  • Read-Acquire は、それに続く (同じスレッドによる) すべての読み取りと書き込みの前に、プログラムの記述順序で実行される。
  • Write-Release は、それに先行する (同じスレッドによる) すべての読み取りと書き込みの後に、プログラムの記述順序で実行される。

プログラム コード内でロックを取得するか、(ロックを使わず) 共有リンク リストからアイテムを取り出すことによって、メモリーの所有権を獲得する場合、常にフラグの読み取りが実行されます。つまり、フラグまたはポインターを調べることで、メモリーの所有権を獲得できたかどうかが判断されます。このような読み取りのしくみは、InterlockedXxx 系の操作に使用されています。この場合、読み取りと書き込みの両方が伴いますが、所有権を獲得できたかどうかは、読み取りで判断されます。メモリーの所有権が獲得されると、通常、そのメモリーとの間で値が読み書きされます。非常に重要な点は、これらの読み取りと書き込みが、所有権の獲得後に実行されるということです。これを保証するのが、Read-Acquire バリアです。

ロックを解放するか、アイテムを共有リンク リストにプッシュすることによってメモリーの所有権を解放する場合、常にフラグの書き込みが実行され、他のスレッドは、そのメモリーが使用可能になったことを知ることができます。メモリーの所有権がある間は、そのメモリーに対してデータを書き込んだり、メモリーからデータを読み取ったりすることができます。ここで重要なことは、こうした読み取りと書き込みが、所有権の解放前に実行されるという点です。これを保証するのが、Write-Release バリアです。

Read-Acquire バリアと Write-Release バリアを単純に 1 つの操作として考えることもできます。しかし、実際には、1) 読み取りまたは書き込みと、2) 特定の境界を越えた、読み取り命令や書き込み命令の移動を禁止する バリア の 2 つの視点で捉えなければならない場合もあります。この場合、バリアを配置する位置がきわめて重要です。Read-Acquire バリアの場合、まず、フラグを読み取るコードがあって、次にバリアが、その後、共有データの読み取りと書き込みを行うコードが存在します。Write-Release バリアの場合、まず共有データの読み取りと書き込みを行うコードがあって、次にバリアがあり、その後、フラグを書き込むコードが記述されます。

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

Read-Acquire と Write-Release の違いは、メモリー バリアの位置だけです。Read-Acquire バリアがロック操作の後に置かれるのに対し、Write-Release バリアはロック操作の前に置かれます。どちらの場合も、バリアは、ロックされたメモリーの参照と、ロックの参照との間に存在します。

所有権の獲得時と解放時の両方でバリアが必要となるのはなぜでしょうか。バリアとは、他のプロセッサとの同期ではなく、あくまで共有メモリーとの同期を保証するために必要な要素であると考えるのが、おそらく最も適切かつ正確でしょう。一方のプロセッサが、Write-Release を使用して、データ構造を共有メモリーに解放し、もう一方のプロセッサが、Read-Acquire を使用して、共有メモリーから同じデータ構造へのアクセス権を獲得した場合、コードは正しく実行されます。どちらかのプロセッサで、バリアが適切に使用されなかった場合、データの共有は失敗する可能性があります。

適切なバリアを使用し、コンパイラおよび 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 に限って言えば、Write-Release バリアを実装する場合、_ReadWriteBarrier だけで十分です (x86 および x64 では、書き込みの順序変更はされず、通常の書き込みだけでロックを解放できるため)。ただし、それ以外の場合は、CPU についても、読み取りと書き込みの順序変更を回避するように気を配る必要があります。

キャッシュ不可能な書き込み結合メモリーに対する書き込みも、_ReadWriteBarrier を使用して順序変更を禁止することができます。この場合、_ReadWriteBarrier により、書き込みが常にプロセッサによる理想的な線形順序で実行されることが保証され、パフォーマンスの向上を期待できます。

組み込み関数 _ReadBarrier と _WriteBarrier を使用して、コンパイラによる順序変更をさらに細かく制御することも可能です。コンパイラによって、_ReadBarrier を越えて読み取りが移動されることも、_WriteBarrier を越えて書き込みが移動されることもありません。

CPU による順序変更の防止

CPU による順序変更は、コンパイラによる順序変更よりもやっかいです。直接目に見える形で発生するわけではなく、単に説明のつかないバグとなって現れます。プロセッサによっては、CPU による読み取りと書き込みの順序変更を防ぐために、メモリー バリア命令を使用する必要があります。Xbox 360 および Windows のメモリー バリア命令には、MemoryBarrier という名前が総称として用いられます。このマクロが各プラットフォームに合わせて適切に実装されています。

Xbox 360 の MemoryBarrier は、lwsync (lightweight sync) として定義されており、ppcintrinsics.h で定義された __lwsync 組み込み関数を通じて利用することもできます。また、__lwsync には、コンパイラのメモリー バリアとしての機能、つまり、コンパイラによる読み取りと書き込みの順序変更を禁止する働きもあります。

lwsync 命令は、Xbox 360 において、特定のプロセッサ コアと L2 キャッシュを同期するメモリー バリアです。lwsync に先行するすべての書き込みが、それに続くあらゆる書き込みよりも先に L2 キャッシュに到達することが保証されます。また、lwsync に続くあらゆる読み取りについて、先行する読み取りよりも古いデータが L2 から取得されてしまうことがないように保証されます。阻止しない順序変更の種類の 1 つは、別のアドレスへの書き込みの前への読み取りの移動です。このため、lwsync は x86 および x64 プロセッサ上で既定のメモリーの順序変更と一致するメモリーの順序変更を強制します。完全なメモリーの順序変更を取得するには、より負荷の大きな sync 命令 (重量関数とも呼ばれます) が必要ですが、ほとんどの場合、これは必要ありません。Xbox 360 上のメモリーの順序変更オプションを次の表に示します。

Xbox 360 での順序変更 sync なし 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 命令で禁止できるのは、キャッシュ可能メモリーに対する読み取りと書き込みの順序変更だけです。デバイス ドライバーの開発者や Xbox 360 ゲームの開発者がよく用いる手法として、メモリーを PAGE_NOCACHE または PAGE_WRITECOMBINE として割り当てることがありますが、その場合、MemoryBarrier は、こうしたメモリーへのアクセスには効果がありません。ほとんどの開発者にとって、キャッシュ不可能メモリーの同期は不要であり、このドキュメントでは特に説明しません。

Interlocked 関数と CPU の順序変更

リソースを獲得または解放する読み取りまたは書き込みには、しばしば、InterlockedXxx 関数が使用されます。Windows の場合は、この関数を用いることによって、同期の問題を簡単に解決できます。Windows の InterlockedXxx 系のすべての関数には、完全なメモリー バリアが使用されているためです。つまり、これらの関数の前後には、CPU のメモリー バリアが効果的に適用されます。あるいは、それ自体が Read-Acquire バリアまたは Write-Release バリアを備えていると考えることもできるでしょう。

Xbox 360 の InterlockedXxx 関数には、CPU のメモリー バリアは存在しません。コンパイラによる読み取りと書き込みの順序変更は防止できますが、CPU による順序変更は防止できません。そのため、InterlockedXxx 関数を Xbox 360 上で使用する場合は、開発者自身が、その前後に __lwsync を追加し、Read-Acquire バリアまたは Write-Release バリアを張る必要があります。コードをより記述しやすく、読みやすくするために、InterlockedXxx 関数の多くには、Acquire バージョンと Release バージョンが存在します。これらは、メモリー バリアが組み込まれたものです。たとえば、InterlockedIncrementAcquire は、InterlockedIncrement に続けて __lwsync メモリー バリアを張ることによって、完全な Read-Acquire 機能を実現します。

Acquire バージョンおよび Release バージョンの InterlockedXxx 関数 (そのほとんどは、パフォーマンスを犠牲にすることなく、Windows でも利用可能) の使用をお勧めします。そうすることで、コードの意図を明確にし、メモリー バリア命令を適切な位置へと簡単に配置することができます。Xbox 360 上で、メモリー バリアを使わずに InterlockedXxx が使用されている箇所が見つかった場合は、バグである可能性が高いため、入念に調査する必要があります。

以下のサンプルでは、Acquire/Release バージョンの InterlockedXxxSList 関数を使って、スレッドからスレッドへと、タスクやその他のデータを渡す方法を示しています。InterlockedXxxSList 関数は、ロックを使わずに、一方向の共有リンク リストを扱う関数ファミリです。なお、Windows では、これらの関数の Acquire バージョンおよび Release バージョンは利用できません。それ自体が完全なメモリー バリアを提供するためです。

// 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 には、volatile 変数へのアクセスに関して、標準の C++ を補うために、マルチスレッドを想定したセマンティクスが定義されています。Visual C++ 2005 以降では、volatile 変数からの読み取りには Read-Acquire セマンティクスが、volatile 変数への書き込みには Write-Release セマンティクスが適用されるように定義されています。つまり、コンパイラによって、読み取りと書き込みが、互いを飛び越えて移動されることはありません。さらに、Windows 上では、CPU による順序変更も確実に防ぐことができます。

これらの新しい保証内容は、Visual C++ 2005 以降のバージョンにしか適用されないことに注意してください。他のベンダーのコンパイラでは通常、Visual C++ 2005 に関するこの追加の保証なしに、別のセマンティクスが実装されます。また、Xbox 360 上では、CPU による読み取りと書き込みの順序変更を禁止するような命令が、コンパイラによって挿入されることはありません。

ロックフリー データ パイプの例

パイプは、1 つまたは複数のスレッドがデータを書き込み、他のスレッドがそれを読み取るコンストラクトです。パイプのロックレス バージョンは、スレッドからスレッドに作業を渡す洗練された効率的な方法となります。DirectX SDK はシングルリーダー、シングルライター ロックレス パイプである LockFreePipe を提供します。これは、DXUTLockFreePipe.h で使用できます。同じ LockFreePipe は AtgLockFreePipe.h の Xbox 360 SDK でも使用できます。

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 関数で CPU による読み取り/書き込みの順序変更を防止できるのは Windows に限られます。この関数を Xbox 360 で使用しても CPU による順序変更を防止することはできません。
  • Visual Studio C++ 2005 で volatile 変数を使用した場合、Windows に限り、CPU による読み取り/書き込みの順序変更を防止できます。Xbox 360 では、コンパイラによる読み取り/書き込みの順序変更しか防止できません。
  • Xbox 360 では書き込みの順序が変更されます。x86 または x64 では書き込みの順序は変更されません。
  • Xbox 360 では読み取りの順序が変更されますが、x86 または x64 では、読み取りの順序は、読み取りと書き込みのターゲットの場所が異なるときにのみ、書き込みに対して変更されます。

推奨事項

  • 可能であれば、より確実なロックを使用することをお勧めします。
  • ロックを頻繁に使用することは避け、コストの増大を防ぐようにします。
  • ストールが発生してしまうため、ロックをあまり長い間保持し続けることは避けます。
  • 複雑であるという欠点を補ってあまりある価値があるという場合にのみ、ロックレス プログラミングを使用します。
  • 受動的プロシージャ呼び出しと通常のコード間でデータを共有する場合など、他のロックが禁止されている状況で、ロックレス プログラミングまたはスピン ロックを使用します。
  • 正しい動作が証明されている標準的なロックレス プログラミング アルゴリズム以外は用いないようにします。
  • ロックレス プログラミングを行う場合は、必要に応じて volatile フラグ変数とメモリー バリア命令を使用します。
  • Xbox 360 では、Acquire バージョンと Release バージョンの InterlockedXxx 関数を利用できます。

参考文献