第4章: セマフォの理論と同期プリミティブ
4.1 セマフォの発明と歴史
Dijkstraのセマフォ（1965年）
セマフォ（Semaphore）は、Edsger W. Dijkstraが1965年に発明した同期プリミティブである。"Cooperating Sequential Processes"（1965年）において、Dijkstraは以下のように定義した:
セマフォの形式的定義:
セマフォ S は非負整数変数であり、以下の2つの不可分操作のみで操作される:
P(S): wait操作
while S = 0 do nothing; // ブロック
S := S - 1;
V(S): signal操作
S := S + 1;
P/V命名の由来:
- P: オランダ語 "proberen"（試す）または "passeren"（通過する）
- V: オランダ語 "verhogen"（増加する）または "vrijgeven"（解放する）
Dijkstraはオランダ人であり、当時の論文はオランダ語で書かれることが多かった。
THE Multiprogramming System（1968年）
Dijkstraは、THE Multiprogramming Systemにおいてセマフォを実装した（"The Structure of the 'THE'-Multiprogramming System", Communications of the ACM, 1968）。このシステムは階層構造を持ち、各層がセマフォを使用して同期した:
THE システムの階層構造:
レベル 5: ユーザープログラム
レベル 4: ユーザープログラムのためのバッファリング
レベル 3: オペレータコンソール
レベル 2: メモリ管理（仮想記憶）
レベル 1: プロセス割り当て（セマフォ使用）
レベル 0: ハードウェア
各レベル間の通信にセマフォが使用された
セマフォの種類
1. 二値セマフォ（Binary Semaphore）:
値は0または1のみ
ミューテックスと同等の機能
しかし所有権の概念がない
2. 計数セマフォ（Counting Semaphore）:
値は0以上の任意の整数
N個のリソースを管理
例: 駐車場の空き台数、プールコネクション数
3. 強セマフォ vs 弱セマフォ:
強セマフォ（Strong Semaphore）:
- 待機キューはFIFO
- 餓死が発生しない
弱セマフォ（Weak Semaphore）:
- 待機スレッドの選択順序は未定義
- 餓死の可能性がある
4.2 セマフォの理論的基盤
不変条件（Invariant）
セマフォの動作は以下の不変条件を満たす:
不変条件1（非負性）:
∀t: S(t) ≥ 0
セマフォの値は常に非負
不変条件2（カウント保存）:
S(t) = S(0) + #V(t) - #P(t)
ここで:
S(0): 初期値
#V(t): 時刻tまでに完了したV操作の数
#P(t): 時刻tまでに完了したP操作の数
生産者-消費者問題（Producer-Consumer Problem）
Dijkstraが提示した典型的なセマフォ使用例:
/* 有界バッファ問題（Bounded Buffer Problem） */
/* Dijkstra, 1965 */
#define N 10 /* バッファサイズ */
sem_t empty; /* 空きスロット数 */
sem_t full; /* データ入りスロット数 */
sem_t mutex; /* バッファへの排他アクセス */
int buffer[N];
int in = 0, out = 0;
void producer(void)
{
int item;
while (1)
{
item = produce_item();
sem_wait(&empty); /* 空きスロットを確保 */
sem_wait(&mutex); /* バッファをロック */
buffer[in] = item;
in = (in + 1) % N;
sem_post(&mutex); /* バッファをアンロック */
sem_post(&full); /* データ入りスロット数を増加 */
}
}
void consumer(void)
{
int item;
while (1)
{
sem_wait(&full); /* データを待つ */
sem_wait(&mutex); /* バッファをロック */
item = buffer[out];
out = (out + 1) % N;
sem_post(&mutex); /* バッファをアンロック */
sem_post(&empty); /* 空きスロット数を増加 */
consume_item(item);
}
}
void init(void)
{
sem_init(&empty, 0, N); /* 初期: N個の空きスロット */
sem_init(&full, 0, 0); /* 初期: 0個のデータ */
sem_init(&mutex, 0, 1); /* バイナリセマフォ */
}
読者-作家問題（Readers-Writers Problem）
Courtois, Heymans, and Parnas（1971）が形式化した問題:
第1読者-作家問題（読者優先）:
/* Courtois et al., 1971 */
int readers_count = 0;
sem_t mutex; /* readers_count 保護 */
sem_t write_lock; /* 書き込みの排他制御 */
void reader(void)
{
sem_wait(&mutex);
readers_count++;
if (readers_count == 1)
sem_wait(&write_lock); /* 最初の読者が作家をブロック */
sem_post(&mutex);
/* 読み取り処理 */
read_data();
sem_wait(&mutex);
readers_count--;
if (readers_count == 0)
sem_post(&write_lock); /* 最後の読者が作家を許可 */
sem_post(&mutex);
}
void writer(void)
{
sem_wait(&write_lock); /* 排他的アクセス */
write_data();
sem_post(&write_lock);
}
問題点: 作家が餓死する可能性がある。
第2読者-作家問題（作家優先）: 読者は待機中の作家がいる間は新規に開始できない。
4.3 モニタの概念
Hoareのモニタ（1974年）
C.A.R. Hoareは1974年にモニタ（Monitor）を提案した（"Monitors: An Operating System Structuring Concept", Communications of the ACM, 1974）:
モニタの定義:
モニタは、共有データとそれを操作する手続きを
カプセル化した抽象データ型である。
特性:
1. 一度に1つのスレッドのみがモニタ内で実行可能
2. 条件変数（condition variable）で待機と通知
3. 相互排除が言語レベルで保証される
Hoareセマンティクス vs Mesaセマンティクス:
Hoareセマンティクス (signal-and-wait):
- signalを発行したスレッドは即座にブロック
- 起こされたスレッドが即座に実行
- 条件は確実に満たされている
Mesaセマンティクス (signal-and-continue):
- signalを発行したスレッドは続行
- 起こされたスレッドはキューに入る
- 条件を再確認する必要がある（while ループ）
POSIXの条件変数はMesaセマンティクスを採用している。
Hansen の Concurrent Pascal（1975年）
Per Brinch Hansenは、モニタを言語レベルで実装した最初の言語Concurrent Pascalを設計した（"The Programming Language Concurrent Pascal", IEEE Transactions on Software Engineering, 1975）。
{ Hansen's Concurrent Pascal - 1975 }
type buffer = monitor
var pool: array [0..N-1] of item;
count, in, out: integer;
nonempty, nonfull: condition;
procedure entry put(x: item);
begin
if count = N then nonfull.wait;
pool[in] := x;
in := (in + 1) mod N;
count := count + 1;
nonempty.signal
end;
procedure entry get(var x: item);
begin
if count = 0 then nonempty.wait;
x := pool[out];
out := (out + 1) mod N;
count := count - 1;
nonfull.signal
end;
end;
4.4 POSIXセマフォの標準
POSIX.1b-1993（リアルタイム拡張）
POSIXセマフォは、IEEE Std 1003.1b-1993（POSIX.1b）で標準化された。これはリアルタイムシステム向けの拡張であった。
2種類のセマフォ:
1. 名前付きセマフォ（Named Semaphore）:
#include <semaphore.h>
#include <fcntl.h>
/* 作成またはオープン */
sem_t *sem = sem_open("/my_semaphore", O_CREAT | O_EXCL, 0644, 1);
/* プロセス間で共有可能 */
/* ファイルシステム上に存在（/dev/shm/sem.* など） */
2. 無名セマフォ（Unnamed Semaphore）:
#include <semaphore.h>
sem_t sem;
/* 初期化 */
sem_init(&sem, 0, 1); /* 0: スレッド間共有, 1: 初期値 */
/* プロセス間共有の場合 */
sem_init(&sem, 1, 1); /* 共有メモリに配置が必要 */
System V セマフォとの比較
System V セマフォは、より古い（1983年）IPCメカニズムである:
| 特性 | POSIX セマフォ | System V セマフォ | |------|---------------|------------------| | API | sem_open, sem_wait | semget, semop | | 複雑さ | シンプル | 複雑 | | セマフォセット | 1つずつ | 複数をまとめて操作可能 | | パフォーマンス | 高速 | オーバーヘッド大 | | 移植性 | 高い | UNIX系のみ |
42のPhilosophersでは、POSIXセマフォ（名前付き）を使用する。
4.5 セマフォAPI詳解
sem_open
#include <semaphore.h>
#include <fcntl.h>
sem_t *sem_open(const char *name, int oflag);
sem_t *sem_open(const char *name, int oflag, mode_t mode, unsigned int value);
パラメータ:
name: セマフォ名（"/"で始まる、例: "/philo_forks"）oflag: フラグ（O_CREAT, O_EXCL など）mode: パーミッション（0644 など）value: 初期値
戻り値: 成功時はセマフォポインタ、失敗時はSEM_FAILED
エラー処理:
sem_t *init_semaphore(const char *name, int initial_value)
{
sem_t *sem;
/* 既存のセマフォを削除（クリーンスタート） */
sem_unlink(name);
sem = sem_open(name, O_CREAT | O_EXCL, 0644, initial_value);
if (sem == SEM_FAILED)
{
perror("sem_open");
return (NULL);
}
return (sem);
}
sem_wait / sem_post
int sem_wait(sem_t *sem); /* P操作 */
int sem_post(sem_t *sem); /* V操作 */
sem_waitのセマンティクス:
アトミックに実行:
1. セマフォ値 > 0 なら、値を1減らして返る
2. セマフォ値 = 0 なら、値が正になるまでブロック
sem_postのセマンティクス:
アトミックに実行:
1. セマフォ値を1増やす
2. 待機中のプロセス/スレッドがいれば1つ起床
sem_trywait / sem_timedwait
int sem_trywait(sem_t *sem);
#include <time.h>
int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout);
sem_trywait:
- 非ブロッキング操作
- 成功時: 0
- 失敗時: -1（errno = EAGAIN）
sem_timedwait:
/* タイムアウト付きwait */
struct timespec ts;
clock_gettime(CLOCK_REALTIME, &ts);
ts.tv_sec += 5; /* 5秒後にタイムアウト */
if (sem_timedwait(sem, &ts) == -1)
{
if (errno == ETIMEDOUT)
printf("タイムアウト\n");
}
sem_getvalue
int sem_getvalue(sem_t *sem, int *sval);
注意: この関数の結果は即座に古くなる可能性がある（他のスレッドによる変更）。デバッグ目的以外では使用を避けるべき。
sem_close / sem_unlink
int sem_close(sem_t *sem);
int sem_unlink(const char *name);
使い分け:
/* 各プロセスで: クローズ */
sem_close(sem);
/* 親プロセスで最後に: 削除 */
sem_unlink("/philo_forks");
4.6 条件変数の理論
Hoar の条件変数（1974年）
条件変数は、モニタ内でスレッドが特定の条件を待機するためのメカニズムである。
形式的定義:
条件変数 cv は2つの操作を持つ:
wait(cv, mutex):
1. mutexを解放
2. cvの待機キューに追加
3. スリープ
4. 起床後、mutexを再取得
signal(cv):
1. 待機キューから1つのスレッドを起床
broadcast(cv):
1. 待機キューの全スレッドを起床
Mesaセマンティクスと偽の起床
POSIXの条件変数はMesaセマンティクスを採用している:
/* 正しい使用法: while ループ */
pthread_mutex_lock(&mutex);
while (!condition) /* if ではなく while */
pthread_cond_wait(&cond, &mutex);
/* 処理 */
pthread_mutex_unlock(&mutex);
while が必要な理由:
- Mesaセマンティクス: signalからwakeupの間に他のスレッドが条件を変更する可能性
- 偽の起床（Spurious Wakeup）: システムが理由なくスレッドを起床させることがある
pthread_cond API
#include <pthread.h>
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
/* 動的初期化 */
int pthread_cond_init(pthread_cond_t *cond, const pthread_condattr_t *attr);
/* 待機 */
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
int pthread_cond_timedwait(pthread_cond_t *cond, pthread_mutex_t *mutex,
const struct timespec *abstime);
/* 通知 */
int pthread_cond_signal(pthread_cond_t *cond);
int pthread_cond_broadcast(pthread_cond_t *cond);
/* 破棄 */
int pthread_cond_destroy(pthread_cond_t *cond);
4.7 読み書きロック
理論的背景
読み書きロックは、読み取りと書き込みを区別する同期プリミティブである。
不変条件:
1. 書き込みロック保持中は、他のロックなし
2. 読み取りロック保持中は、書き込みロックなし
3. 複数の読み取りロックは共存可能
状態遷移:
読み取り要求
↓
[空き] ←→ [読み取り中(n)]
↑↓ ↑↓
[書き込み中] ←─┘
読み取り要求は待機
pthread_rwlock API
#include <pthread.h>
pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;
/* 読み取りロック */
int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock);
/* 書き込みロック */
int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock);
/* アンロック */
int pthread_rwlock_unlock(pthread_rwlock_t *rwlock);
使用例:
pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;
int shared_data = 0;
void *reader(void *arg)
{
pthread_rwlock_rdlock(&rwlock);
int value = shared_data; /* 読み取り */
pthread_rwlock_unlock(&rwlock);
return (NULL);
}
void *writer(void *arg)
{
pthread_rwlock_wrlock(&rwlock);
shared_data++; /* 書き込み */
pthread_rwlock_unlock(&rwlock);
return (NULL);
}
4.8 バリア同期
バリアの概念
バリア（Barrier）は、複数のスレッドが特定のポイントで同期するためのメカニズムである。
形式的定義:
バリア B(n) は n 個のスレッドを同期させる:
barrier_wait(B):
count++
if count < n:
block until count = n
else:
wake all blocked threads
count = 0
pthread_barrier API
#include <pthread.h>
pthread_barrier_t barrier;
/* 初期化: count スレッドで同期 */
int pthread_barrier_init(pthread_barrier_t *barrier,
const pthread_barrierattr_t *attr,
unsigned count);
/* 待機 */
int pthread_barrier_wait(pthread_barrier_t *barrier);
/* 破棄 */
int pthread_barrier_destroy(pthread_barrier_t *barrier);
戻り値の特殊性:
int ret = pthread_barrier_wait(&barrier);
if (ret == PTHREAD_BARRIER_SERIAL_THREAD)
{
/* このスレッドが「シリアルスレッド」 */
/* 全員が到達した後の後処理を1スレッドだけで実行 */
}
else if (ret == 0)
{
/* 通常のスレッド */
}
4.9 ロックフリープログラミング
アトミック操作の歴史
ロックフリープログラミングは、Herlihy（1991年）の"Wait-Free Synchronization"で理論的基盤が確立された。
アトミック操作の分類:
1. Load/Store
単純な読み書き
2. Test-and-Set (TAS)
読み取りと設定を不可分に実行
3. Compare-and-Swap (CAS)
条件付き更新
4. Fetch-and-Add (FAA)
加算と旧値取得
C11アトミック
#include <stdatomic.h>
atomic_int counter = ATOMIC_VAR_INIT(0);
/* アトミック操作 */
atomic_fetch_add(&counter, 1); /* counter++ */
atomic_fetch_sub(&counter, 1); /* counter-- */
atomic_load(&counter); /* 読み取り */
atomic_store(&counter, 0); /* 書き込み */
/* Compare-and-Swap */
int expected = 5;
atomic_compare_exchange_strong(&counter, &expected, 10);
メモリオーダリング
C11は6つのメモリオーダリングを定義している:
/* 最も緩い: 順序保証なし */
memory_order_relaxed
/* Acquire-Release: ロック/アンロック相当 */
memory_order_acquire /* 以降の操作が先に実行されない */
memory_order_release /* 以前の操作が後に実行されない */
memory_order_acq_rel /* 両方 */
/* 最も厳しい: 全順序 */
memory_order_seq_cst /* デフォルト */
4.10 Philosophersボーナス課題の実装
アーキテクチャ概要
ボーナス課題では、各哲学者をプロセスとして実装し、セマフォで同期する:
┌─────────────────────────────────────────────┐
│ 親プロセス │
│ ┌─────────────────────────────────────┐ │
│ │ セマフォ管理 │ │
│ │ /philo_forks (count = N) │ │
│ │ /philo_write (count = 1) │ │
│ │ /philo_death (count = 0) │ │
│ └─────────────────────────────────────┘ │
│ │ │
│ ┌────────────┼────────────┐ │
│ ↓ ↓ ↓ │
│ ┌───────┐ ┌───────┐ ┌───────┐ │
│ │Philo 1│ │Philo 2│ │Philo N│ │
│ │(fork) │ │(fork) │ │(fork) │ │
│ └───────┘ └───────┘ └───────┘ │
└─────────────────────────────────────────────┘
データ構造
typedef struct s_data
{
int num_philos;
long time_to_die;
long time_to_eat;
long time_to_sleep;
int must_eat_count;
long start_time;
sem_t *forks; /* フォーク用セマフォ */
sem_t *write_sem; /* 出力用セマフォ */
sem_t *death_sem; /* 死亡通知用セマフォ */
sem_t *meal_sem; /* 食事時刻保護用 */
pid_t *pids; /* 子プロセスPID配列 */
} t_data;
typedef struct s_philo
{
int id;
long last_meal_time;
int meals_eaten;
t_data *data;
} t_philo;
セマフォ初期化
int init_semaphores(t_data *data)
{
/* 既存のセマフォを削除（前回の実行の残骸対策） */
sem_unlink("/philo_forks");
sem_unlink("/philo_write");
sem_unlink("/philo_death");
sem_unlink("/philo_meal");
/* フォーク用: 初期値 = 哲学者数 */
data->forks = sem_open("/philo_forks", O_CREAT | O_EXCL,
0644, data->num_philos);
if (data->forks == SEM_FAILED)
return (error_return("sem_open forks failed"));
/* 出力用: バイナリセマフォ */
data->write_sem = sem_open("/philo_write", O_CREAT | O_EXCL,
0644, 1);
if (data->write_sem == SEM_FAILED)
return (cleanup_and_return(data, 1));
/* 死亡通知用: 初期値0（待機状態から開始） */
data->death_sem = sem_open("/philo_death", O_CREAT | O_EXCL,
0644, 0);
if (data->death_sem == SEM_FAILED)
return (cleanup_and_return(data, 2));
/* 食事時刻保護用 */
data->meal_sem = sem_open("/philo_meal", O_CREAT | O_EXCL,
0644, 1);
if (data->meal_sem == SEM_FAILED)
return (cleanup_and_return(data, 3));
return (0);
}
プロセス生成
int create_philosophers(t_data *data)
{
int i;
t_philo philo;
data->pids = malloc(sizeof(pid_t) * data->num_philos);
if (!data->pids)
return (-1);
i = 0;
while (i < data->num_philos)
{
data->pids[i] = fork();
if (data->pids[i] == -1)
{
kill_all_children(data, i);
return (-1);
}
else if (data->pids[i] == 0)
{
/* 子プロセス */
philo.id = i + 1;
philo.last_meal_time = data->start_time;
philo.meals_eaten = 0;
philo.data = data;
philosopher_routine(&philo);
exit(0); /* 到達しない（ルーチン内でexit） */
}
i++;
}
return (0);
}
哲学者ルーチン
void philosopher_routine(t_philo *philo)
{
pthread_t monitor_thread;
/* 死亡監視スレッドを起動 */
pthread_create(&monitor_thread, NULL, death_monitor, philo);
pthread_detach(monitor_thread);
/* 偶数番号は開始をずらす（競合緩和） */
if (philo->id % 2 == 0)
ft_usleep(philo->data->time_to_eat / 2);
while (1)
{
/* 思考 */
print_status(philo, "is thinking");
/* フォークを2本取得 */
sem_wait(philo->data->forks);
print_status(philo, "has taken a fork");
sem_wait(philo->data->forks);
print_status(philo, "has taken a fork");
/* 食事 */
print_status(philo, "is eating");
sem_wait(philo->data->meal_sem);
philo->last_meal_time = get_timestamp_ms();
philo->meals_eaten++;
sem_post(philo->data->meal_sem);
ft_usleep(philo->data->time_to_eat);
/* フォークを返却 */
sem_post(philo->data->forks);
sem_post(philo->data->forks);
/* 必要回数食べたら終了 */
if (philo->data->must_eat_count > 0 &&
philo->meals_eaten >= philo->data->must_eat_count)
exit(0);
/* 睡眠 */
print_status(philo, "is sleeping");
ft_usleep(philo->data->time_to_sleep);
}
}
死亡監視
void *death_monitor(void *arg)
{
t_philo *philo = (t_philo *)arg;
long current_time;
long time_since_meal;
while (1)
{
usleep(1000); /* 1ms間隔でチェック */
sem_wait(philo->data->meal_sem);
current_time = get_timestamp_ms();
time_since_meal = current_time - philo->last_meal_time;
sem_post(philo->data->meal_sem);
if (time_since_meal > philo->data->time_to_die)
{
print_death(philo);
sem_post(philo->data->death_sem); /* 親に通知 */
exit(1);
}
}
return (NULL);
}
親プロセスの監視
void wait_for_death(t_data *data)
{
int i;
int status;
/* いずれかの子プロセスからの死亡通知を待つ */
sem_wait(data->death_sem);
/* 全子プロセスを終了 */
i = 0;
while (i < data->num_philos)
{
kill(data->pids[i], SIGKILL);
i++;
}
/* ゾンビプロセスの回収 */
i = 0;
while (i < data->num_philos)
{
waitpid(data->pids[i], &status, 0);
i++;
}
}
クリーンアップ
void cleanup(t_data *data)
{
/* セマフォをクローズ */
if (data->forks != SEM_FAILED)
sem_close(data->forks);
if (data->write_sem != SEM_FAILED)
sem_close(data->write_sem);
if (data->death_sem != SEM_FAILED)
sem_close(data->death_sem);
if (data->meal_sem != SEM_FAILED)
sem_close(data->meal_sem);
/* セマフォを削除 */
sem_unlink("/philo_forks");
sem_unlink("/philo_write");
sem_unlink("/philo_death");
sem_unlink("/philo_meal");
/* メモリ解放 */
if (data->pids)
free(data->pids);
}
4.11 同期プリミティブの選択ガイド
| 用途 | 推奨プリミティブ | 理由 | |------|-----------------|------| | 単一リソース保護 | ミューテックス | シンプル、所有権あり | | N個のリソース | 計数セマフォ | カウント管理が容易 | | プロセス間同期 | 名前付きセマフォ | プロセス境界を越える | | 条件待機 | 条件変数 | 効率的なスリープ | | 読み取り多数 | 読み書きロック | 並行読み取り可能 | | 全員同期 | バリア | N個のスレッド同期 | | 単純カウンタ | アトミック操作 | ロックフリー |
4.12 まとめ
本章では、セマフォと同期プリミティブの理論について学んだ:
- セマフォの歴史: Dijkstra（1965）、P/V操作
- セマフォの種類: 二値、計数、強/弱
- 古典的問題: 生産者-消費者、読者-作家
- モニタ: Hoare（1974）、条件変数
- POSIXセマフォ: 名前付き/無名、API
- 他の同期プリミティブ: 読み書きロック、バリア、アトミック
- ボーナス実装: プロセスベースの哲学者問題
- Dijkstra, E. W. (1965). "Cooperating Sequential Processes", Technical Report EWD-123
- Dijkstra, E. W. (1968). "The Structure of the 'THE'-Multiprogramming System", Communications of the ACM, 11(5)
- Hoare, C. A. R. (1974). "Monitors: An Operating System Structuring Concept", Communications of the ACM, 17(10)
- Hansen, P. B. (1975). "The Programming Language Concurrent Pascal", IEEE Transactions on Software Engineering, SE-1(2)
- Courtois, P. J., Heymans, F., & Parnas, D. L. (1971). "Concurrent Control with Readers and Writers", Communications of the ACM, 14(10)
- Herlihy, M. (1991). "Wait-Free Synchronization", ACM TOPLAS, 13(1)
- IEEE (1993). "POSIX.1b-1993: Realtime Extension", IEEE Std 1003.1b-1993
- Boehm, H. J. (2005). "Threads Cannot Be Implemented as a Library", PLDI 2005
次章では、Philosophersの完全な実装戦略とデバッグ技法について学ぶ。
---