2-3 オーバーヘッドを最小限に抑える適切な同期プリミティブの選択

概要

スレッドは、同期ポイントで待機している間、有益な作業を行っていません。通常、マルチスレッド・プログラムではある程度の同期が必要です。データ重複を排除するアルゴリズムや複雑な非ブロッキング・スケジューリング・アルゴリズムは問題を伴っており、場合によっては明示的な同期の方が適していることがあります。アプリケーション開発者は、さまざまな同期メカニズムの中からオーバーヘッドを最小限に抑える適切なものを選択しなければなりません。

この記事は、「マルチスレッド・アプリケーションの開発のためのインテル・ガイド」の一部で、インテル® プラットフォーム向けにマルチスレッド・アプリケーションを効率的に開発するための手法について説明します。

はじめに

同期構造では、その性質上、実行がシリアル化されます。そのため、並列性が制限され、アプリケーション全体のパフォーマンスが低下する可能性がありますが、実際、同期を全く必要としないマルチスレッド・プログラムはほとんどありません。適切な構造を選択することで、同期に伴うシステム・オーバーヘッドの一部を抑えることができます。この記事は、いくつかの手法とそれぞれの長所および短所について、サンプルコードを使用して説明します。

Win32* 同期 API

Win32 API では、アトミックな性質を保証するいくつかのメカニズムが用意されています。ここでは、そのうちの 3 つについて、インクリメント文 (例: var++) の例を使用して説明します。スレッド間で共有されている変数を更新する場合、ロード → 書き込み→ ストアという一連の命令はアトミックでなければなりません (つまり、この命令シーケンスが完了する前にプリエンプトしないようにする必要があります)。次のコードは、各 API の使用方法を示します。

#include 
CRITICAL_SECTION cs; /* InitializeCriticalSection called in main() */
HANDLE mtx;  /* CreateMutex called in main() */
static LONG counter = 0;
void IncrementCounter ()
{
  // Synchronize with Win32 interlocked function
  InterlockedIncrement (&counter);
  // Synchronize with Win32 critical section
  EnterCriticalSection (&cs);
    counter++;
  LeaveCriticalSection (&cs);
  // Synchronize with Win32 mutex
  WaitForSingleObject (mtx, INFINITE);
    counter++
  ReleaseMutex (mtx);
}

3 つのメカニズムを比較して、それぞれの同期に適したメカニズムについて考えてみましょう。Win32 インターロック関数 (InterlockedIncrement、InterlockedDecrement、InterlockedExchange、InterlockedExchangeAdd、InterlockedCompareExchange) は、単純な操作に限定されますが、クリティカル領域よりも高速で、関数の呼び出し回数も少なくて済みます。Win32 のクリティカル領域の開始時と終了時には、それぞれ EnterCriticalSectionLeaveCriticalSection、または WaitForSingleObjectReleaseMutex を呼び出す必要があります。また、インターロック関数は非ブロッキング型ですが、EnterCriticalSectionWaitForSingleObject (または WaitForMultipleObjects) は同期オブジェクトが利用できない場合にスレッドをブロックします。

クリティカル領域が存在する場合、Win32 CRITICAL_SECTION で同期する方が、Win32 mutex、セマフォー、イベント HANDLE で同期するよりも、システム・オーバーヘッドがはるかに小さくなります。これは、Win32 CRITICAL_SECTION がユーザー空間オブジェクトであるのに対して、Win32 mutex、セマフォー、イベント HANDLE はカーネル空間オブジェクトであるためです。通常、Win32 クリティカル・セクションは、Win32 mutex よりも高速ですが、汎用性の面では劣ります。ほかのカーネル・オブジェクトと同様に、mutex はプロセス間の同期に使用できます。WaitForSingleObject 関数と WaitForMultipleObjects 関数では、待機時間を指定することができます。これにより、スレッドは mutex を取得するまで無制限に待機するのではなく、指定された制限時間が経過した後に実行を再開することができます。待機時間を 0 に設定すると、スレッドは mutex が利用可能かどうかをブロッキングしないでテストできます。(同様に、TryEnterCriticalSection 関数を使用すると、CRITICAL_SECTION が利用可能かどうかをブロッキングしないでチェックできます。) 最後に、スレッドが mutex を保持したまま (解放しないで) 終了した場合、オペレーティング・システムは、待機中のスレッドがデッドロックにならないように、ハンドルに信号を送ります。スレッドが CRITICAL_SECTION を保持したまま終了した場合、この CRITICAL_SECTION へ入るために待機しているスレッドはデッドロックになります。

Win32 スレッドは、CRITICAL_SECTION または mutex HANDLE を取得しようとしたときに、すでにほかのスレッドがこれらを保持している場合は、直ちに CPU をオペレーティング・システムに解放します。一般的に、これは望ましい動作です。スレッドはブロックされ、CPU は自由に有益な処理を行うことができます。スレッドのブロッキングとアンブロッキングにはコストがかかります。場合によっては、スレッドがブロックされる前に、もう一度ロックの取得を試みる方が良いこともあります (例えば、SMP システム上の小さなクリティカル・セクションの場合)。Win32 CRITICAL_SECTION では、スピンカウントを設定することで、スレッドが CPU を解放するまでの時間を制御できます。InitializeCriticalSectionAndSpinCount 関数と SetCriticalSectionSpinCount 関数は、特定の CRITICAL_SECTION に入ろうとするスレッドのスピンカウントを設定します。

アドバイス

変数の簡単な操作 (インクリメント、デクリメント、交換など) には、高速でオーバーヘッドが小さい Win32 インターロック関数を使用すると良いでしょう。

Win32 mutex、セマフォー、イベント HANDLE は、プロセス間の同期や待機時間の指定が必要な場合に使用します。それ以外の場合は、システム・オーバーヘッドが小さい Win32 CRITICAL_SECTION を使用すると良いでしょう。

Win32 CRITICAL_SECTION のスピンカウントは、InitializeCriticalSectionAndSpinCount 関数と SetCriticalSectionSpinCount 関数で制御できます。スレッドが CPU を解放するまでの時間を制御することは、競合が発生しやすい小さなクリティカル・セクションでは特に重要です。SMP システムやインテル® ハイパースレッディング・テクノロジー (インテル® HT テクノロジー) 対応プロセッサーでは、スピンカウントによりパフォーマンスが大きく左右されます。

インテル® スレッディング・ビルディング・ブロック (インテル® TBB) の同期 API

インテル® TBB は、“ネイティブ” mutex のラッパーを含む、アトミック操作 (テンプレート・クラス atomic<T>) とさまざまな相互排他メカニズムの移植性に優れたラッパーを提供します。アトミック操作と OS 依存の同期 API の長所と短所については前述したとおりなので、ここでは tbb::atomic<T>tbb::mutex は省略して、spin_mutexqueuing_mutexspin_rw_mutexqueuing_rw_mutex などの高速なユーザーレベルの同期クラスについて説明します。

spin_mutex は、最も単純な mutex です。spin_mutex のロックを取得しようとするスレッドは、ロックが取得できるまでビジー状態で待機します。spin_mutex は、少数の命令でロックが保持される場合にのみ適しています。例えば、次のコードは、mutex FreeListMutex を使用して共有変数 FreeList を保護します。

Node* FreeList;
typedef spin_mutex FreeListMutexType;
FreeListMutexType FreeListMutex;
Node* AllocateNode()
{
  Node* n;
  {
    FreeListMutexType::scoped_lock lock(FreeListMutex);
    n = FreeList;
    if( n )
    FreeList = n->next;
  }
  if( !n )
    n = new Node();
  return n;
}

scoped_lock のコンストラクターは、FreeListMutex にほかのロックがなくなるまで待機します。ロックはデストラクターによって解放されます。AllocateNode 関数内の中括弧で囲まれたコードセクションは、ロックの存続時間をできるだけ短くして、待機中のほかのスレッドができるだけ早くロックを取得できるようにします。

インテル® TBB では、queuing_mutex という別のスピン mutex も提供されています。これもユーザーレベルの mutex ですが、spin_mutex とは異なり、queuing_mutex はフェア mutex です。フェア mutex は、到着順にスレッドを処理し、スレッドが欠乏状態にならないようにします。アンフェア mutex は、到着順ではなく、実行中のスレッドを優先的に処理するため、フェア mutex よりも高速です。mutex のスケーラビリティーと公平性が重要な場合は、queuing_mutex を使用した方が良いでしょう。

共有データへのアクセスのすべてが相互排他的でなければならないわけではありません。実際のアプリケーションの多くでは、並行データ構造へのアクセスのほとんどは読み取りであり、書き込みはわずかです。このようなデータ構造では、読み取りアクセスでの保護は必要なく、排除することでシリアル化を軽減できます。インテル® TBB の読み取り/書き込みロックは、クリティカル領域への書き込みを 1 つのスレッドだけに制限しつつ、複数のスレッドが読み取りアクセスをできるようにします。ビジー・ウェイトの読み取り/書き込み mutex には、アンフェアな spin_rw_mutex とフェアな queuing_rw_mutex があります。読み取り/書き込み mutex には、spin_mutexqueuing_mutex と同じ scoped_lock API に加えて、読み取りロックから書き込みロックへのアップグレード機能と、書き込みロックから読み取りロックへのダウングレード機能も用意されています。

アドバイス

適切な同期手法を選択するためには、処理するデータや処理のパターンも含めてアプリケーションをよく理解することが重要です。

クリティカル領域に少数の命令しかない場合は、公平性を考慮する必要がないため、spin_mutex を使用した方が良いでしょう。ただし、クリティカル領域が短くても、到着順にスレッドを処理する必要がある場合は queuing_mutex を使用します。

並行データへのアクセスのほとんどが読み取りで、書き込みがわずかな場合は、読み取り/書き込みロックを使用することで、不必要なシリアル化を回避し、アプリケーション全体のパフォーマンスを向上させることができます。

利用ガイド

Win32 インターロック関数を続けて呼び出す場合は、スレッド・プリエンプションに注意してください。例えば、次のコードセグメントを複数のスレッドで実行した場合、localVar の値は常に一定ではありません。

static LONG N = 0;
LONG localVar;
…
InterlockedIncrement (&N);
InterlockedIncrement (&N);
InterlockedExchange (&localVar, N);
  
static LONG N = 0;
LONG localVar;
…
EnterCriticalSection (&lock);
 localVar = (N += 2);
LeaveCriticalSection (&lock);

この例では、インターロック関数を続けて呼び出していますが、呼び出しの間にスレッド・プリエンプションが発生すると、予期しない結果を引き起こします。クリティカル・セクションは、どちらのアトミック操作 (グローバル変数 N の更新と localVar への割り当て) も保護されているため安全です。

CRITICAL_SECTION 変数を使用する場合も、mutex HANDLE を使用する場合も、安全性を確保するためには Win32 クリティカル領域の入口と出口を 1 つにする必要があります。クリティカル・セクションへのジャンプは、同期の意味をなくします。また、LeaveCriticalSectionReleaseMutex を呼び出さずにクリティカル・セクションからほかのコードセグメントへジャンプすると、待機中のスレッドがデッドロックになります。入口と出口を 1 つに制限することで、コードをよりわかりやすいものにすることができます。

待機中のスレッドがデッドロックにならないようにするためには、スレッドが CRITICAL_SECTION 変数を保持したまま終了しないように注意する必要があります。