第3章　正当性の検証と性能測定

マルチスレッドアプリケーションの開発は、単にコードを動かすだけでなく、「常に正しく動作すること（正当性）」と「期待通りに速いこと（性能）」の二つを保証しなければなりません。本章では、まず並行プログラムの動作原理を理解し、いかにしてその正しさを証明するかを検証し、次にその性能を客観的に評価する指標を学びます。

3.1 並列アルゴリズムの検証

並行アルゴリズムの検証に対する基本的な考え方は、M. Ben-Ariによる以下の4つのポイントに要約されます。

1.プログラムとは連続したアトミックな実行文である。意味: 実行が完了するまで割り込まれない最小単位の処理。

2.並行プログラムは複数のスレッド内のアトミックな実行文のインタリーブである。意味: 複数のスレッドの最小処理単位が、OSにより予測不可能な順序で交互に実行されること。

3.アトミックな実行文のすべての組み合わせは、ここで検証する並行アルゴリズムのすべての性質を満たさなければならない。意味: 実行順序が指数関数的に増加する全インタリーブパターンにおいて、プログラムが期待通りの結果となることを保証する必要がある。

4.どのインタリーブでもスレッドの実行文が（不公平に）除外されることはない。意味: スレッドは実行順序がどうであれ、必ず実行されるという「公平性」の原則。

インタリーブ：2人の作業員の作業手順が予測できないこと。 AさんとBさんが同時に作業し、Aさんが「1人目の年齢を読み込む」と「合計に加える」の間で、Bさんが割り込んで「1人目の年齢を読み込む」という作業を始めるかもしれません。

アトミック実行分：割り込みの入らない最小単位の作業。「合計に1を加える」という作業は「メモリから合計を読み込む」「1を加える」「メモリに書き戻す」の3ステップ。この途中で他の人に割り込まれたら合計が狂います。「1を加える」作業全体を誰も割り込めない用にする。

3.2 例題：クリティカルセクション問題

正当性の検証の技術を実践するために、我々はクリティカルセクション問題に取り組みます。これは、複数のスレッドが共有リソースに安全にアクセスする領域（クリティカルリージョン）への侵入を、外部の同期オブジェクトを使わずに制御する問題です。

この解法が満たす性質は次の2点です。

排他制御の必須性（相互排除）: 同時に1スレッドのみがクリティカルリージョンに入る。

非妨害の必須性: クリティカルリージョン外のスレッドは、他のスレッドの侵入を妨げてはならない。

タスク例：リストの集計をする際に2人が共同で使う1台の電卓と1本のペンを管理する

3.2.1 第1段階

第1段階ではクリティカルリージョンへ排他制御を加えます。

int threadNumber = 0;
 void ThreadZero()
 {
  while (TRUE) do {
    while (threadNumber == 1) do {} // spin-wait　スピンウェイト
    CriticalRegionZero;
    threadNumber = 1;
    OtherStuffZero;
  }
 }
 void ThreadOne()
 {
  while (TRUE) do {
    while (threadNumber == 0) do {} // spin-wait　スピンウェイト
    CriticalRegionOne;
    threadNumber = 0;
    OtherStuffOne;
  }
 }

このプログラムをシングルコア上で実行させると、2スレッドが入れ替わりながら動作し、次に示すようなトレース結果になります。 1.whileループに入る。 2.threadNumberが0なのでT1はウェイトする。 3.T0がwhileループに入る。 4.threadNumberが0なので、T0は処理を進める。 5.T0がクリティカルリージョンへ入る。 6.T0がクリティカルリージョンを終え、threadNumberに1を代入する。 7.T1がクリティカルリージョンへ入る。

問題点: この方法は排他制御は保証しますが、一方のスレッドがクリティカルリージョンへの侵入を控えた場合、もう一方のスレッドは永遠に待たされることになり、非妨害の性質に反します。また、許可を持つスレッドがthreadNumberを変更する前に終了すると、デッドロックが発生します。

クリティカルリージョン：電卓を使う瞬間 2人にとって電卓を操作している間は、邪魔されたくない「クリティカルな時間」です。この短い時間だけは、電卓の利用権を独占する必要があります。

3.2.2 第2段階

int Thread0inside = 0;
 int Thread1inside = 0;
 void ThreadZero()
 {
  while (TRUE) do {
    while (Thread1inside) do {}  // spin-wait　スピンウェイト
    Thread0inside = 1;
    CriticalRegionZero;
    Thread0inside = 0;
    OtherStuffZero;
  }
}
 void ThreadOne()
 {
  while (TRUE) do {
    while (Thread0inside) do {}
    Thread1inside = 1;
    CriticalRegionOne;
    Thread1inside = 0;
    OtherStuffOne;
  }
 }

次に、スレッドがクリティカルリージョンを実行中であることを示すフラグ（ThreadXinside）を使用することで、厳密な交互実行の強制を排除しようとします。スレッドは相手のフラグが安全であることを確認してから、自身のフラグをセットします。

問題点: 2つのスレッドがほぼ同時に動作し、お互いに相手がまだ入っていないことを確認した後、両者がクリティカルリージョンに侵入してしまうインタリーブが存在します。 1.while文でThread1insideを調べる。 2.T0はThread1insideが0（FALSE）であることを知る。 3.T1がwhile文でThread0insideを調べる。 4.T1はThread0insideが0（FALSE）であることを知る。 5.T0がクリティカルリージョンへ入る。 6.T1もクリティカルリージョンへ入る。これにより、排他制御の最も重要な性質が破綻します。

排他制御の破綻：2人が同時に電卓を操作して、合計を書き換えてしまうこと。「Aさんが電卓を使っているか確認」→「まだ使っていない」→Aさんが電卓を使う。この間にBさんが同じ確認をして「まだ使っていない」と判断すると、2人が同時に電卓を叩き始め、合計がメチャクチャになります。

3.2.3 第3段階

int Thread0WantsToEnter = 0;
 int Thread1WantsToEnter = 0;
 void ThreadZero()
 {
  while (TRUE) do {
    Thread0WantsToEnter = 1;
    while (Thread1WantsToEnter) do {}  // spin-wait　スピンウェイト
    CriticalRegionZero;
    Thread0WantsToEnter = 0;
    OtherStuffZero;
  }
 }
 void ThreadOne()
 {
  while (TRUE) do {
    Thread1WantsToEnter = 1;
    while (Thread0WantsToEnter) do {}
    CriticalRegionOne;
    Thread1WantsToEnter = 0;
    OtherStuffOne;
  }
 }

この段階では、スレッドはフラグを確認する前に、クリティカルリージョンへ入る意図を表明する（ThreadXWantsToEnter=1）ように手順を変更します。

問題点: 2つのスレッドが同時に意図を表明し合った場合、お互いのフラグが1であることを確認すると、両スレッドとも相手のフラグが戻されるのを永遠に待ち続けるデッドロック状態に陥ります。 1.T0 が Thread0WantsToEnter へ 1 を代入する。 2.T1 も Thread1WantsToEnter へ 1 を代入する。 3.T0 は while ループの条件として Thread1WantsToEnter を調べる。 4.T0 は Thread1WantsToEnter が 1（TRUE）と確認する。 5.T0 はスピンウェイトする。 6.T1 は while の条件で Thread0WantsToEnter を調べる。 7.T1 は Thread0WantsToEnter が 1（TRUE）であることを確認する。 8.T1 もスピンウェイトする。

デッドロック：2人がお互いに「相手が先に終わるのを待つ」状態。「これから電卓を使うぞ」→「相手も電卓を使おうとしている」→「じゃあ、相手が先に終わるまで待とう」とお互いが待ち続け、誰も作業が進まなくなるのがデッドロックです。

デッドロックを発生させる4つの条件

デッドロックは、以下の4つの条件がすべて揃った場合に発生するため、アルゴリズムを修正するには、少なくとも一つを不成立にしなければなりません。

相互排除：リソースが一度に1スレッドに占有されている。

獲得後のウェイト：占有中のスレッドが、他のリソースの解放を待つ。

プリエンプトなし：占有されたリソースが強制的に奪われない。

循環待ち：リソースの解放を待つスレッドが環状に連鎖している。

3.2.4　第4段階

int Thread0WantsToEnter = 0;
 int Thread1WantsToEnter = 0;
 void ThreadZero()
 {
  while (TRUE) do {
    Thread0WantsToEnter = 1;
    while (Thread1WantsToEnter) do { // not quite a spin-wait　純粋なスピンウェイトではない
      Thread0WantsToEnter = 0;
      delay(someRandomCycles);
      Thread0WantsToEnter = 1;
    }

    CriticalRegionZero;
    Thread0WantsToEnter = 0;
    OtherStuffZero;
  }
 }
 void ThreadOne()
 {
  while (TRUE) do {
    Thread1WantsToEnter = 1;
    while (Thread0WantsToEnter) do {
      Thread1WantsToEnter = 0;
      delay(someRandomCycles);
      Thread1WantsToEnter = 1;
    }
    CriticalRegionOne;
    Thread1WantsToEnter = 0;
    OtherStuffOne;
  }
 }

デッドロックの原因である「獲得後のウェイト」を排除するため、競合が発生した場合は自身の意図を一旦取り下げ（ThreadXWantsToEnter=0）、ランダムな時間遅延(delay(someRandomCycles))後に再試行します。

問題点: デッドロックは回避されますが、運の悪いスレッドが常に相手の再試行に敗北し続けると、クリティカルリージョンへ永遠に入れない可能性が残り、スターベーションが発生します。 1.T0 がクリティカルリージョンへ入る。 2.T1 が Thread1WantsToEnter へ 1 を代入する。 3.T1 は T0 がクリティカルリージョンを実行していることを知る。 4.T1 は Thread1WantsToEnter を元へ戻し遅延する。 5.T0 がクリティカルリージョンを終了する。 6.T0 がすぐに OtherStuffZero を実行する。 7.T0 がクリティカルリージョンへの実行権を得る。 8.T1 が Thread1WantsToEnter へ 1 を代入する。 9.T1 は while の条件式で Thread0WantsToEnter を調べ、T0 がクリティカルリージョンを実行していることを知る。 10.T1 は Thread1WantsToEnter を元へ戻し遅延する。 11.T0 がクリティカルリージョンを終了する。 12.T0 がすぐに OtherStuffZero を実行する。 13.T0 がクリティカルリージョンへの実行権を得る。

スターベーション：運の悪い方が永遠に電卓を使えないこと。 2人が同時に電卓を使おうとしたとき、再試行ルールで「運の悪い方」が常に電卓の使用権を譲り続け、永遠に自分の集計作業を進められない状態です

3.2.5 Dekkerのアルゴリズムによる解決

第4段階ではデッドロックを回避するためランダムな遅延を導入しましたが、これは運の悪いスレッドが永遠に待たされるスターベーションの問題を残しました。

int favored;
 int Thread0WantsToEnter, Thread1WantsToEnter;
 void ThreadZero()
 {
  while (TRUE) do {
    Thread0WantsToEnter = 1;
    while (Thread1WantsToEnter) do {
      if (favored == 1) {
        Thread0WantsToEnter = 0;
        while (favored == 1) do {}  // spin-wait　スピンウェイト
        Thread0WantsToEnter = 1;
      }
    }
    CriticalRegionZero;
    favored = 1;
    Thread0WantsToEnter = 0;
    OtherStuffZero;
  }
 }
 void ThreadOne()
 {
  while (TRUE) do {
    Thread1WantsToEnter = 1;
    while (Thread0WantsToEnter) do {
      if (favored == 0) {
        Thread1WantsToEnter = 0;
        while (favored == 0) do {}
        Thread1WantsToEnter = 1;
      }
    }
    CriticalRegionOne;
    favored = 0;
    Thread1WantsToEnter = 0;
    OtherStuffOne;
  }
 }

最終的な解決策であるDekkerのアルゴリズムは、デッドロックの回避とスターベーションの解消を両立します。これは、競合が発生した際に優先権（favored）という変数を用いてタイ・ブレーカーとして機能させることで実現されます。優先権を持つスレッドが実行を完了した後、相手に優先権を譲る（favored = 1）ことで、すべてのスレッドが最終的にクリティカルリージョンへ入ることが保証されます。

Dekkerのアルゴリズム：「順番待ちの札（優先権）」を使って、デッドロックもスターベーションも防ぐ最終的なルール。競合が起きたら、「次はBさんが優先的に使う権利がある」という札（favored）を渡します。札を持たないAさんはBさんが終わるまで待ちますが、Bさんは自分の作業を終えたら、必ずAさんに札を渡すルールです。これにより、全員が公平に作業できます。

3.2.6 何を学んだか?

Ben-Ariの並行性一般化を用いた正当性の検証方法と、2スレッドのアトミックな実行文がインタリーブすることの実演です。

3.2.7 スレッドは悪くない、悪いのはそのようにプログラミングすることだ

クリティカルセクション問題の考察を締めくくるのは、この哲学的な教訓です。スレッドはプログラマが記述した通りに動くだけであり、問題が発生した場合は、プログラマの設計、すなわち並行性の原則を考慮に入れなかったことに原因があります。

3.3 性能指標（現状把握）

正当性の検証が済んだ後、次に必要となるのは、並行アルゴリズムがハードウェアの能力をどれだけ引き出しているかを客観的に評価する指標です。

タスク例：集計作業にかかった時間を測定して報告する。

3.3.1 高速化率

性能向上の度合いを示す最も基本的な指標が高速化率です。

高速化率：1人でやった時間と2人でやった時間の比。 1人で集計したら100分かかった。2人で分担したら60分で終わった。この場合、高速化率は 100/60 = 1.67倍です。理想は2倍（50分）ですが、連絡の手間（オーバーヘッド）などでロスが出ます。

$\text{高速化率} \ (S) = \frac{\text{最良の逐次実行時間}}{\text{並列実行時間}}$

アムダールの法則 (Amdahl's Law) は、プログラムの逐次実行部分が、いかに並列化の絶対的な上限を定めるかを示します。高速化率は逐次部分の割合（$1 - \text{pctPar}$）の逆数が上限となります。一方、グスタフソン・バーシスの法則 (Gustafson-Barsis's Law) は、コア数の増加に伴い処理データ量も増加する大規模な問題に適しており、より現実的な性能向上を予測します。

アムダールの法則：「必ず1人でしかできない作業」が全体の速さを制限する法則。 2人で分担しても、最後の合計を電卓に打ち込む作業は1人しかできません

3.3.2 および 3.3.3 実行効率とコア利用率

そして、どれだけリソースを有効活用できたかを示すのが実行効率です。

$\text{実行効率} \ (E) = \frac{\text{高速化率} \ (S)}{\text{コア数} \ (p)} \times 100\%$

この効率が100%に近いほど、コアを最大限に活用できています。この指標は、論理コア数が増加するHT（Hyper-Threading）技術を用いた場合など、物理コアを十分に使い切れているかを判断する上で重要となります。

実行効率：2人の作業員のサボり度合い。 2人で作業した結果が1.67倍の高速化なら、実行効率は 1.67 / 2 = 83.5%です。残りの16.5%は、電卓の順番待ちや、連絡を取り合う手間（オーバーヘッド）でロスしている「サボり時間」です。

3.4 並列性に対応するハードウェアの進化

並行プログラミングが主流になった背景には、プロセッサが従来のクロックスピード向上路線から、複数のプロセッサコアを1チップに集積するマルチコアプロセッサへと舵を切った歴史的経緯があります。この進化の過程は、複数の段階を経て、現代の並列処理環境を築き上げました。

命令レベルの並列性（ILP）の進化初期の性能向上は、シングルコアプロセッサ内部での命令処理の工夫によって実現されました。

アウトオブオーダ実行: プロセッサは、命令の実行順序を元のプログラムの順序に戻しつつ、利用可能なパラメータに基づいて命令を実行する。これにより、命令の依存関係を考慮しながら、命令のスループットが向上します。

実行ユニットの複数化: 複数の実行ユニットを持つプロセッサでは、命令のパラメータが利用可能であれば、複数の命令を同時に実行し、整数演算、浮動小数点演算、メモリアクセスなど、さまざまな命令を並行して処理することが可能となります。

データ並列性（DLP）と論理並列性の導入さらなる性能向上のために、複数のデータを同時に処理する技術や、論理的な並列性が導入されました。

SSE（Streaming SIMD Extensions）: SSEは、同時に複数のデータを処理できる特殊なレジスタを導入します。同じ命令を用いて複数のデータを一度に処理することで、データ処理の効率が大幅に向上する（ベクトル並列）。

Intel HTテクノロジ（ハイパースレッディング）: HTテクノロジは、プロセッサ内の実行ユニットを効率的に活用し、スレッドの状態に応じてリソースを割り当てることで、論理プロセッサを仮想的に追加し、スレッド間の競合を減少させ、全体の処理能力を向上させます。

物理コアによる真の並列性の実現物理的な限界を超克するために、複数のプロセッサを組み合わせるアーキテクチャが主流となりました。

SMP（対称型マルチプロセッシング）: SMPシステムでは、複数のプロセッサが一つのマザーボード上に搭載され、メモリなどのリソースを共有し、複数のスレッドが異なるプロセッサで同時に実行可能となり、スケーラビリティが向上します。

マルチコアプロセッサの登場: 伝統的なプロセッサのクロックスピードを向上させることが物理的限界（発熱や消費電力）に達したため、同一チップ上に複数のプロセッサコアを搭載するマルチコア技術が採用され、発熱量や消費電力を抑えつつ、同時にアプリケーションの性能を向上させることが可能となりました。

このハードウェアの進化こそが、プログラマに並行プログラミングという新たな思考様式を要求する最大の動機となったのです。

第3章 正当性の検証と性能測定