- Authors
- Name
- Youngju Kim
- @fjvbn20031
背景：競合状態
複数のプロセス（またはスレッド）が共有データに同時にアクセスすると、実行順序によって結果が異なる場合がある。これを**競合状態（Race Condition）**と呼ぶ。
// 競合状態の例：2つのスレッドが共有変数countをインクリメント
// countの初期値が5の場合
// スレッド A: count++
// 内部的に：
// register_A = count (register_A = 5)
// register_A = register_A + 1 (register_A = 6)
// count = register_A (count = 6)
// スレッド B: count++
// 内部的に：
// register_B = count (register_B = 5)
// register_B = register_B + 1 (register_B = 6)
// count = register_B (count = 6)
// インターリーブ実行シナリオ：
// T0: Aが register_A = count (register_A = 5)
// T1: Aが register_A = register_A + 1 (register_A = 6)
// T2: Bが register_B = count (register_B = 5) <-- まだ5！
// T3: Bが register_B = register_B + 1 (register_B = 6)
// T4: Aが count = register_A (count = 6)
// T5: Bが count = register_B (count = 6)
// 結果：count = 6（期待値7ではない！）
クリティカルセクション問題（Critical Section Problem）
クリティカルセクション（Critical Section）は共有データにアクセスするコード領域である。
[プロセス構造]
do {
[エントリセクション（Entry Section）]
-- クリティカルセクションに入るための許可要求 --
[クリティカルセクション（Critical Section）]
-- 共有データにアクセス --
[イグジットセクション（Exit Section）]
-- クリティカルセクション使用完了通知 --
[リメインダセクション（Remainder Section）]
} while (true);
クリティカルセクション問題の解決条件は以下の3つである。
- 相互排除（Mutual Exclusion）: 1つのプロセスがクリティカルセクションを実行中の場合、他のプロセスは入ることができない
- 進行（Progress）: クリティカルセクションに誰もいない時、入ろうとするプロセスの中から1つが選ばれなければならない。決定が無限に遅延してはならない
- 有界待機（Bounded Waiting）: プロセスがクリティカルセクション進入を要求した後、他のプロセスがクリティカルセクションに入る回数に上限がなければならない
ピーターソンの解法（Peterson's Solution）
2つのプロセス間のクリティカルセクション問題をソフトウェアで解決する古典的アルゴリズムである。
// ピーターソンの解法（2つのプロセス i, j）
int turn; // 誰の番か
bool flag[2]; // クリティカルセクション進入意思
// プロセス iのコード
void process_i() {
while (true) {
flag[i] = true; // 私(i)は入りたい
turn = j; // 相手(j)に譲る
while (flag[j] && turn == j)
; // 相手が望んでいて相手の番なら待機
// クリティカルセクション
// ... 共有データにアクセス ...
flag[i] = false; // 使い終わった
// リメインダセクション
}
}
ピーターソンの解法は3つの条件（相互排除、進行、有界待機）をすべて満たす。しかし、現代のコンピュータアーキテクチャではコンパイラやプロセッサの命令再順序化（reordering）のため正しく動作しない場合がある。
ハードウェア同期サポート
メモリバリア（Memory Barrier）
メモリバリア（またはメモリフェンス）はプロセッサに対してバリア前後のメモリアクセス順序を保証するよう指示する。
// メモリバリアの使用例
// スレッド 1
while (!flag)
memory_barrier(); // flagの読み取りがこの時点より前に再順序化されないことを保証
print(x);
// スレッド 2
x = 100;
memory_barrier(); // xの書き込みがflagの書き込みより前に完了することを保証
flag = true;
CAS（Compare-And-Swap）
CASはアトミックなハードウェア命令で、同期の基本ビルディングブロックである。
// CASのロジック（実際には1つのアトミック命令）
bool compare_and_swap(int *value, int expected, int new_value) {
if (*value == expected) {
*value = new_value;
return true;
}
return false;
}
// CASを利用したアトミックインクリメント
void atomic_increment(int *counter) {
int old_val;
do {
old_val = *counter;
} while (!compare_and_swap(counter, old_val, old_val + 1));
// 成功するまでリトライ
}
// CASを利用した相互排除
int lock = 0;
void acquire() {
while (!compare_and_swap(&lock, 0, 1))
; // lockが0（使用可能）なら1（使用中）に変更
}
void release() {
lock = 0;
}
アトミック変数（Atomic Variables）
CASのようなハードウェア命令をベースに、基本データ型に対するアトミック操作を提供する。
// C11 アトミック変数
#include <stdatomic.h>
atomic_int counter = 0;
void increment() {
atomic_fetch_add(&counter, 1); // アトミックインクリメント
}
// Javaのアトミック変数
// import java.util.concurrent.atomic.AtomicInteger;
// AtomicInteger counter = new AtomicInteger(0);
// counter.incrementAndGet(); // アトミックインクリメント
アトミック変数は単一変数に対する競合状態は解決するが、複雑なクリティカルセクション問題の一般的な解決策にはならない。
ミューテックスロック（Mutex Lock）
ミューテックスは最もシンプルな同期ツールで、クリティカルセクションを保護するロック装置である。
// ミューテックスの使用パターン
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void critical_section() {
pthread_mutex_lock(&mutex); // ロック獲得（acquire）
// クリティカルセクション
// 共有データにアクセス
pthread_mutex_unlock(&mutex); // ロック解放（release）
}
[ミューテックスの動作]
スレッド A スレッド B
| |
|-- lock() 成功 ---- |
| (クリティカルセクション) |-- lock() 試行
| 共有データアクセス | (待機/ブロック)
| | ...
|-- unlock() ------- |
| ----->|-- lock() 成功
| | (クリティカルセクション)
| | 共有データアクセス
| |-- unlock()
スピンロック（Spinlock）: ロックを獲得するまで繰り返しチェックして待機（ビジーウェイト）。マルチコアで短いクリティカルセクションに適している。コンテキストスイッチのオーバーヘッドを回避できるためである。
// スピンロック実装（CASベース）
typedef struct {
atomic_flag flag;
} spinlock_t;
void spin_lock(spinlock_t *lock) {
while (atomic_flag_test_and_set(&lock->flag))
; // ロックされるまで繰り返し（ビジーウェイト）
}
void spin_unlock(spinlock_t *lock) {
atomic_flag_clear(&lock->flag);
}
セマフォ（Semaphore）
セマフォはミューテックスより一般的な同期ツールである。整数変数でwait()とsignal()操作のみを許可する。
// セマフォの基本操作（アトミック）
wait(S) { // P操作またはacquire
while (S <= 0)
; // 待機
S--;
}
signal(S) { // V操作またはrelease
S++;
}
セマフォの種類
- カウンティングセマフォ: 値の範囲に制限なし。利用可能なリソースの数を追跡
- バイナリセマフォ: 0または1のみ。ミューテックスに類似
// カウンティングセマフォの使用例：最大5つの同時接続
#include <semaphore.h>
sem_t connection_pool;
void init() {
sem_init(&connection_pool, 0, 5); // 初期値5
}
void handle_request() {
sem_wait(&connection_pool); // 接続獲得（残数減少）
// データベース操作の実行
// ...
sem_post(&connection_pool); // 接続返却（残数増加）
}
セマフォによる順序制御
// S1がS2より先に実行されることを保証
sem_t sync_sem;
sem_init(&sync_sem, 0, 0); // 初期値0
// プロセス 1
void process1() {
S1; // 先に実行する文
sem_post(&sync_sem); // signal
}
// プロセス 2
void process2() {
sem_wait(&sync_sem); // wait（S1完了まで待機）
S2; // S1の後に実行
}
ビジーウェイトなしのセマフォ
実際の実装ではビジーウェイトの代わりに待ちキューを使用する。
typedef struct {
int value;
struct list_head waiting_list; // 待機プロセスリスト
} semaphore;
void wait(semaphore *S) {
S->value--;
if (S->value < 0) {
// 現在のプロセスを待機リストに追加
add_to_list(&S->waiting_list, current_process);
block(); // プロセスを待機状態に切り替え
}
}
void signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
// 待機リストからプロセスを1つ起こす
process *P = remove_from_list(&S->waiting_list);
wakeup(P); // Pを準備状態に切り替え
}
}
モニター（Monitor）
セマフォは強力だが使いにくくエラーが発生しやすい。モニターはプログラミング言語レベルで同期をサポートする高水準の構造体である。
[モニター構造]
+------------------------------------+
| monitor |
| |
| 共有データ |
| +-----------+ |
| | 変数群 | |
| +-----------+ |
| |
| 条件変数 |
| condition x, y; |
| |
| procedure P1() { ... } |
| procedure P2() { ... } |
| procedure P3() { ... } |
| |
| 初期化コード |
| |
+------------------------------------+
^ ^ ^
| | |
スレッド1 スレッド2 スレッド3
（一度に1つだけモニター内部で実行）
条件変数（Condition Variable）
モニター内で特定の条件が満たされるまで待機するために使用する。
x.wait(): 呼び出したプロセスを条件xの待ちキューに入れてモニターを解放x.signal(): 条件xの待ちキューから1つのプロセスを起こす
// Javaでのモニターパターン（synchronized キーワード）
public class BoundedBuffer {
private final Object[] buffer;
private int count = 0;
private int in = 0;
private int out = 0;
public BoundedBuffer(int size) {
buffer = new Object[size];
}
// synchronized: 一度に1つのスレッドのみ実行
public synchronized void produce(Object item)
throws InterruptedException {
while (count == buffer.length) {
wait(); // バッファが満杯なら待機
}
buffer[in] = item;
in = (in + 1) % buffer.length;
count++;
notifyAll(); // 待機中の消費者を起こす
}
public synchronized Object consume()
throws InterruptedException {
while (count == 0) {
wait(); // バッファが空なら待機
}
Object item = buffer[out];
out = (out + 1) % buffer.length;
count--;
notifyAll(); // 待機中の生産者を起こす
return item;
}
}
// Pthreads条件変数の使用
#include <pthread.h>
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int ready = 0;
// 待機するスレッド
void *waiter(void *arg) {
pthread_mutex_lock(&mutex);
while (!ready) {
// 条件が満たされるまで待機
// 待機中はmutexが自動的に解放され、起床時に再獲得
pthread_cond_wait(&cond, &mutex);
}
printf("条件充足！進行します。\n");
pthread_mutex_unlock(&mutex);
return NULL;
}
// シグナルを送るスレッド
void *signaler(void *arg) {
pthread_mutex_lock(&mutex);
ready = 1;
pthread_cond_signal(&cond); // 待機中のスレッドを起こす
pthread_mutex_unlock(&mutex);
return NULL;
}
活性問題（Liveness Problems）
同期ツールを不適切に使用すると、プロセスが永遠に進行できない状況が発生する可能性がある。
デッドロック（Deadlock）
2つ以上のプロセスが互いに相手が保有するリソースを待ち、永遠に待機する状態である。
[デッドロックの例]
スレッド A スレッド B
lock(mutex1); lock(mutex2);
// mutex1を保有 // mutex2を保有
lock(mutex2); lock(mutex1);
// mutex2を待機！ // mutex1を待機！
// 互いに相手のリソースを待ってデッドロック
解決：リソース獲得順序を常に同じに保つ
スレッド A スレッド B
lock(mutex1); lock(mutex1); // 同じ順序で獲得
lock(mutex2); lock(mutex2);
飢餓（Starvation）
プロセスが必要なリソースを永遠に得られない状態である。例えば、優先度の低いプロセスが高い優先度のプロセスに常に押される場合である。
優先度逆転（Priority Inversion）
高い優先度のプロセスが低い優先度のプロセスが保有するリソースを待つ状況である。
[優先度逆転シナリオ]
優先度：H > M > L
1. LがリソースRを獲得して実行中
2. Hが到着、Rを要求 -> Lが保有中なので待機
3. Mが到着、Lをプリエンプト -> Mが実行
4. HはLがRを返すのを必要とするが、LはMにプリエンプトされている
5. 結果：MがHより先に実行！（優先度逆転）
解決：優先度継承プロトコル
LがRを保有している間、Hの優先度を継承
-> LがMにプリエンプトされない -> LがRを早く返却
火星探査機パスファインダーで優先度逆転バグが実際に発生した事例が有名である。優先度継承プロトコルを有効にして解決した。
まとめ
プロセス同期は共有リソースに対する競合状態を解決するために不可欠である。ハードウェアレベルのCASとアトミック変数から、ミューテックスとセマフォ、そして高水準のモニターまで様々なツールが存在する。これらのツールを正しく使用しないと、デッドロック、飢餓、優先度逆転などの活性問題が発生する可能性がある。