2-1 ロック競合の管理: 大小のクリティカル・セクション

概要

マルチスレッド・アプリケーションでは、共有リソースにアクセスするコード領域へのエントリーの同期をとるために、ロックが使用されます。ロックで保護されたコード領域を「クリティカル・セクション」と呼びます。クリティカル・セクションを実行中のスレッドがある間は、ほかのスレッドは入ることができません。つまり、クリティカル・セクションでは実行がシリアル化されます。このトピックでは、クリティカル・セクションのサイズ (クリティカル・セクション内でスレッドが費やす時間の長さとして定義) の概念とパフォーマンスへの影響について説明します。

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

はじめに

クリティカル・セクションは、複数のスレッドが共有リソースにアクセスする際のデータの整合性を確保します。また、クリティカル・セクション内では、コード実行はシリアルに処理されます。スレッドがクリティカル・セクションで費やす時間をできるだけ少なくすることで、ほかのスレッドがロック取得のためにアイドル状態で待機 (「ロック競合」) する時間を短縮できます。つまり、クリティカル・セクションをできる限り小さな状態に保つことが重要になります。ただし、小さなクリティカル・セクションが多数あると、個別のロックの取得と解放にかかるシステム・オーバーヘッドが生じます。ここでは、大小のクリティカル・セクションを使い分ける方法を紹介します。

コードサンプル 1 のスレッド関数には、2 つのクリティカル・セクションが含まれています。それぞれのクリティカル・セクションでは異なるデータが保護され、DoFunc1 関数と DoFunc2 関数の処理は独立していると仮定します。また、いずれの更新関数の実行時間もごくわずかなものと仮定します。

コードサンプル 1:
Begin Thread Function ()
  Initialize ()
  BEGIN CRITICAL SECTION 1
    UpdateSharedData1 ()
  END CRITICAL SECTION 1
  DoFunc1 ()
  BEGIN CRITICAL SECTION 2
    UpdateSharedData2 ()
  END CRITICAL SECTION 2
  DoFunc2 ()
End Thread Function ()

2 つのクリティカル・セクションは、DoFunc1 への呼び出しで区切られています。DoFunc1 でスレッドが費やす時間がわずかであれば、2 つのクリティカル・セクションの同期にかかるオーバーヘッドは妥当とは言えないでしょう。この場合、コードサンプル 2 のように 2 つの小さなクリティカル・セクションを 1 つの大きなクリティカル・セクションにまとめる方法があります。

コードサンプル 2:
Begin Thread Function ()
  Initialize ()
  BEGIN CRITICAL SECTION 1
    UpdateSharedData1 ()
    DoFunc1 ()
    UpdateSharedData2 ()
  END CRITICAL SECTION 1
  DoFunc2 ()
End Thread Function ()

DoFunc1 で費やされる時間が 2 つの更新ルーチンで費やされる時間の合計よりも極端に長い場合、この方法は適切とは言えません。クリティカル・セクションのサイズを大きくすると、ロック競合の可能性も高くなります。特にスレッド数が増える場合は注意が必要です。

前の例を使用して、UpdateSharedData2 でスレッドが費やす時間が長い場合を考えてみましょう。コードサンプル 2 にあるように、1 つのクリティカル・セクションを使用して、UpdateSharedData1UpdateSharedData2 のアクセスを同期する方法は、ロック競合の可能性が高いため、もはや有効な解決策とは言えません。実行時にアクセスを取得したスレッドはクリティカル・セクションでかなりの時間を費やします。その間、残りのスレッドはブロックされたままになります。ロックが解放されると、待機していたスレッドの内の 1 つがクリティカル・セクションに入ることができ、残りの待機スレッドはまた長時間ブロックされたままになります。したがって、この場合はコードサンプル 1 のほうが良い解決策と言えます。

ロックを特定の共有データと関連付けすることは、良いプログラミングの慣例と言えます。特定の共有変数へのアクセスをすべて同じロックで保護しても、別のロックで保護されている別の共有変数にほかのスレッドがアクセスすることは防げません。共有データ構造では、構造内の各要素に個別のロックを作成することも、あるいは構造全体へのアクセスを保護するために 1 つのロックを作成することもできます。要素の更新にかかる計算コストによっては、このいずれかが現実的な解決策に成り得るでしょう。また、場合によっては、最適なロックの粒度はこの両極端な解決策の中間にあるかもしれません。例えば、共有配列では 2 つのロックを使用して、1 つのロックで偶数の要素を、もう 1 つのロックで奇数の要素を保護することができます。

UpdateSharedData2 の完了に著しく時間がかかる場合、このルーチンの処理を分割して、新しいクリティカル・セクションを作ると良いかもしれません。コードサンプル 3 では、元の UpdateSharedData2 が別のデータを処理する 2 つの関数に分けられています。別のクリティカル・セクションを使用することでロック競合の軽減が期待されます。UpdateSharedData2 の実行全体に保護が不要な場合は、関数呼び出しを囲む代わりに、関数内の共有データがアクセスされるポイントにクリティカル・セクションを挿入することを検討してください。

コードサンプル 3:
Begin Thread Function ()
  Initialize ()
  BEGIN CRITICAL SECTION 1
    UpdateSharedData1 ()
  END CRITICAL SECTION 1
    DoFunc1 ()
  BEGIN CRITICAL SECTION 2
    UpdateSharedData2 ()
  END CRITICAL SECTION 2
  BEGIN CRITICAL SECTION 3
    UpdateSharedData3 ()
  END CRITICAL SECTION 3
  DoFunc2 ()
End Thread Function ()

アドバイス

クリティカル・セクションのサイズは、ロックの取得と解放に伴うオーバーヘッドを考慮してバランスよく設定すると良いでしょう。ロックによるオーバーヘッドを軽減するには、小さなクリティカル・セクションをまとめることを検討してください。大きなクリティカル・セクションで著しいロック競合が見られる場合は、小さなクリティカル・セクションに分割します。ロック競合が最小限に抑えられるように、ロックを特定の共有データと関連付けると良いでしょう。最適な解決策は、おそらく、各々の共有データ要素を個別にロックする方法と、すべての共有データに対してロックを 1 つ設定するという両極端な方法の中間にあるでしょう。

同期では、実行がシリアルに行われることに注意してください。大きなクリティカル・セクションは、アルゴリズムにわずかな並列性しか備わっていないか、あるいはスレッド間のデータ分割が最適さに多少欠けていることを示します。前者の場合、アルゴリズムを変更しない限りは何もできません。後者の場合、スレッドが同期することなくアクセスできるように共有データのローカルコピーを作成してみてください。

クリティカル・セクションのサイズとロックの粒度に関する先の議論では、コンテキスト・スイッチで生じるコストが考慮されていません。スレッドがロックを取得するために待機し、クリティカル・セクションでブロックされている場合、オペレーティング・システムは、アクティブなスレッドをアイドルスレッドと入れ替えます。これをコンテキスト・スイッチと言います。CPU が解放され、有益な処理が行えるため、これは一般に好ましい動作とされています。しかしながら、小さなクリティカル・セクションに入るために待機しているスレッドの場合は、コンテキスト・スイッチよりもスピンウェイトがより効果的かもしれません。スピンウェイトでは、待機スレッドは CPU を手放しません。しがたって、スピンウェイトは、クリティカル・セクションで費やされる時間がコンテキスト・スイッチのコストよりも小さな場合にのみ使用することが推奨されます。

コードサンプル 4 は、Win32 スレッド API を使用する際に採用すると良いヒューリスティックを示しています。このサンプルでは、Win32 の CRITICAL_SECTION オブジェクトでスピンウェイト・オプションが使用されています。クリティカル・セクションに入ることのできないスレッドは、CPU を手放さないでスピンします。スピンウェイト中に CRITICAL_SECTION が利用可能になった場合は、コンテキスト・スイッチが回避されます。スピンカウント・パラメーターで、スレッドがブロックされるまでにスピンする回数を指定できます。シングルプロセッサー・システムでは、スピンカウント・パラメーターは無視されます。コードサンプル 4 では、アプリケーションの各スレッドで 1000 回のスピンカウントが使用されますが、上限は 8000 に設定されています。

コードサンプル 4:
int gNumThreads;
CRITICAL_SECTION gCs;
int main ()
{
  int spinCount = 0;
  ...
  spinCount = gNumThreads * 1000;
  if (spinCount > 8000) spinCount = 8000;
  InitializeCriticalSectionAndSpinCount (&gCs, spinCount);
  ...
}
DWORD WINAPI ThreadFunc (void *data)
{
  ...
  EnterCriticalSection (&gCs);
  ... 
  LeaveCriticalSection (&gCs);
}

利用ガイド

インテル® ハイパースレッディング・テクノロジー (インテル® HT テクノロジー) 対応プロセッサーを使用する場合は、一般にスピンウェイトによってパフォーマンスに支障をきたす可能性があります。コードサンプル 4 のようなスピンカウント・パラメーターには別のアプローチが必要です。複数の物理 CPU を備えた真の対称型マルチプロセッサー (SMP) システムとは異なり、インテル®HT テクノロジーは同じ CPU コアに 2 つの論理プロセッサーを作成します。そのため、スピンスレッドと有益な処理を行うスレッドが論理プロセッサーの獲得のために競合します。したがって、インテル®HT テクノロジー対応のシステムでスピンスレッドを使用した場合、SMP システムよりも広範囲にわたりマルチスレッド・アプリケーションのパフォーマンスに影響を及ぼしかねません。コードサンプル 4 のヒューリスティックでは、スピンカウントを少なくするか、あるいは使用しない方が良いでしょう。