C/C++におけるプロセス同期の徹底解説｜クリティカルセクションからセマフォまで

プロセス同期（Process Synchronization）とは、共有データへの同時アクセスによって発生するデータ不整合の問題を解決するための手法です。協調プロセス（cooperating process）とは、他のプロセスに影響を与えたり、影響を受けたりするプロセスのことであり、このようなプロセス間ではデータの不整合が生じる可能性があります。そのため、データの一貫性を維持するためにはプロセス同期が不可欠となります。

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

すべてのプロセスには、クリティカルセクション（Critical Section）と呼ばれる特別なコード領域が存在します。この領域では、共通変数の変更、テーブルの更新、ファイルへの書き込みなどが行われます。クリティカルセクションで最も重要なポイントは、あるプロセスがクリティカルセクション内で実行している間、他のどのプロセスもクリティカルセクション内で実行できないという点です。

各プロセスは、クリティカルセクションに入る前に許可を要求しなければなりません。この要求を実装するコード部分をエントリセクション（Entry Section）、クリティカルセクションの終わりに当たる部分をエグジットセクション（Exit Section）、そして残りのコードをレメインダーセクション（Remainder Section）と呼びます。

以下は、特定のプロセスP1におけるクリティカルセクションの構造です。

クリティカルセクションが満たすべき3つの要件

• 相互排他（Mutual Exclusion）：あるプロセス（例えばP1）がクリティカルセクション内で実行されている間、他のプロセス（例えばP2）はクリティカルセクション内で実行できません。
• 進行（Progress）：クリティカルセクション内で実行中のプロセスが存在せず、入場を希望するプロセスがいる場合、レメインダーセクションで実行されていないプロセスのみが入場の選択に参加でき、その選択が無期限に延期されることはありません。
• 有界待機（Bounded Waiting）：あるプロセスがクリティカルセクションへの入場を要求してから、その要求が許可されるまでの間に、他のプロセスがクリティカルセクションに入場できる回数には上限が設けられます。

オペレーティングシステムでクリティカルセクションを扱うために一般的に使用される2つのアプローチがあります。

プリエンプティブカーネル（Preemptive Kernel）：カーネルモードで実行中のプロセスがプリエンプト（実行の横取り）されることを許可します。

ノンプリエンプティブカーネル（Non-Preemptive Kernel）：カーネルモードで実行中のプロセスがプリエンプトされることを許可しません。

ピーターソンの解法（Peterson's Solution）

ピーターソンの解法は、クリティカルセクション問題に対する古典的なソフトウェアベースの解決策です。この解法は、クリティカルセクションとレメインダーセクションを交互に実行する2つのプロセスに限定されます。ピーターソンの解法では、2つのプロセス間で共有される次の2つのデータ項目が必要です。

• int turn;
• boolean flag[2];

ここで、変数turnはどのプロセスがクリティカルセクションに入る番かを示し、flag配列はプロセスがクリティカルセクションに入る準備ができているかどうかを示します。

turn == i の場合、プロセスPiがクリティカルセクションに入ることが許可されていることを意味します。

flag[j] が TRUE の場合、プロセスjがクリティカルセクションに入る準備ができていることを意味します。

以下は、ピーターソンの解法におけるプロセスPの構造です。

ピーターソンの解法は、以下の3つの条件をすべて満たします。

• 相互排他：一度に1つのプロセスのみがクリティカルセクションにアクセスできます。
• 進行：クリティカルセクション外のプロセスは、他のプロセスのクリティカルセクションへの入場を妨げません。
• 有界待機：すべてのプロセスは、無期限に待つことなくクリティカルセクションに入る機会を得られます。

同期ハードウェア

同期ハードウェアは、以下の2種類の命令を使用して実装されます。

• TestAndSet()
• swap()

TestAndSet()は、同期の問題を解決するためのハードウェアによるソリューションです。この方式では、複数のプロセス間で共有される「ロック（Lock）」と呼ばれる共有変数を使用します。ロックの値は0または1のいずれかを取り、1はロック取得中、0はロック解放中を表します。

プロセスがクリティカルセクションに入ろうとする際は、必ずロックの値を確認する必要があります。ロックの値が1の場合、その値が0に変わるまで待機しなければなりません。

以下は、TestAndSet()を使用した相互排他の実装です。

セマフォ（Semaphore）

セマフォは、TestAndSet()やswap()命令が抱える問題（ビジーウェイトなど）を克服するために使用される同期ツールです。セマフォSは、wait()とsignal()という2つの標準的なアトミック操作を通じてアクセスできる整数変数です。

wait()の関数：

wait(S) {
    while (S <= 0)
        ; // 何もしない（ビジーウェイト）
    S--;
}

signal()の関数：

signal(S) {
    S++;
}

あるプロセスがセマフォの値を変更している間、他のプロセスが同じセマフォの値を同時に操作することはできません。

以下は、セマフォを使用した相互排他の実装です。

オペレーティングシステムでは、主に以下の2種類のセマフォが使用されます。

カウンティングセマフォ（Counting Semaphore）：この種のセマフォの値は、制限のない範囲（任意の整数値）を取ることができます。有限個の同一リソースへのアクセス制御などに利用されます。

バイナリセマフォ（Binary Semaphore）：この種のセマフォの値は0または1のみを取ります。ミューテックスロック（Mutex Lock）とも呼ばれ、オペレーティングシステムは複数プロセス間のクリティカルセクション問題を解決するためにこれを使用します。