第1章: 並行プログラミングの理論と食事する哲学者問題
1.1 並行計算の歴史
タイムシェアリングシステムの誕生
1961年、MITのFernando CorbatóらはCTSS（Compatible Time-Sharing System）を開発した。これは、複数のユーザーが1台のコンピュータを「同時に」利用できる最初のタイムシェアリングシステムであった。
Corbatóの洞察:
コンピュータは人間より遥かに速い
→ 人間がキーを打つ間にCPUは何千もの命令を実行できる
→ 複数のユーザーを高速に切り替えれば、全員が専用機を使っているように感じる
この概念は、並行計算（Concurrent Computing）の基礎となった。Corbatóは後にこの業績でチューリング賞を受賞した（1990年）。
Edsger Dijkstraと並行プログラミング
1960年代、オランダのコンピュータ科学者Edsger Dijkstraは、並行プログラミングの理論的基盤を確立した。Dijkstraの貢献は計り知れない:
- セマフォの発明（1965年）: 同期プリミティブの提案
- 食事する哲学者問題（1965年）: リソース競合の教育的モデル
- 銀行家のアルゴリズム（1965年）: デッドロック回避アルゴリズム
- 構造化プログラミング（1968年）: goto文の害悪
Dijkstraは"Cooperating Sequential Processes"（1965年）において、並行プログラミングの本質的な困難さを初めて形式的に記述した。
Carl Adam Petriとペトリネット
1962年、ドイツの数学者Carl Adam Petriは博士論文においてペトリネット（Petri Net）を発明した。これは並行システムを数学的にモデル化する形式手法である。
ペトリネットの構成要素:
- プレース（Place）: 状態を表す円
- トランジション（Transition）: 遷移を表す四角形
- トークン（Token）: 現在の状態を示すマーカー
哲学者問題のペトリネット表現:
(思考中) (フォーク利用可能)
○──────→ □ ←───────○
P1 T1 F1
│
↓
(食事中)
○
P2
ペトリネットは、デッドロックの検出や到達可能性分析に利用される。
1.2 食事する哲学者問題
Dijkstraの原典（1965年）
Dijkstraは"Cooperating Sequential Processes"（1965年）において、以下の問題を提示した:
> N人の哲学者が円形のテーブルに座っている。各哲学者の前にはスパゲッティの皿があり、隣り合う哲学者の間に1本ずつフォークが置かれている。哲学者は食事をするために、両側の2本のフォークを必要とする。
この問題は、コンピュータシステムにおける資源競合を象徴的に表現している。
問題の形式的定義
状態空間:
- 各哲学者は状態$S_i \in \{THINKING, HUNGRY, EATING, SLEEPING\}$を持つ
- 各フォークは状態$F_j \in \{FREE, TAKEN\}$を持つ
不変条件:
- 隣り合う哲学者は同時に食事できない
- 食事をするには両側のフォークが必要
安全性要件:
- デッドロック自由: システムは常に進行可能
- 餓死自由: 全ての哲学者はいつか食事できる
- 相互排除: 共有リソースへの安全なアクセス
- 相互排除（Mutual Exclusion）: リソースは一度に1つのプロセスのみが使用
- 保持と待機（Hold and Wait）: リソースを保持しながら他のリソースを待機
- 非横取り（No Preemption）: リソースは自発的にのみ解放される
- 循環待機（Circular Wait）: プロセスの循環的な待機チェーンが存在
デッドロックの条件（Coffman条件）
1971年、E.G. Coffman, M.J. Elphick, A. Shoshaniは論文"System Deadlocks"において、デッドロック発生の必要十分条件を定式化した（"Coffman条件"）:
食事する哲学者問題において:
- 相互排除: フォークは1人の哲学者のみ使用可能 ✓
- 保持と待機: 1本のフォークを持ちながらもう1本を待つ ✓
- 非横取り: フォークは所有者のみ解放可能 ✓
- 循環待機: 全員が左のフォークを持ち、右を待つと発生 ✓
4条件のうち1つでも破れば、デッドロックは発生しない。
1.3 プロセスとスレッドの理論
プロセスの概念史
プロセス（Process）という用語は、1960年代のMulticsプロジェクトで確立された。
Multicsの設計者たちは、実行中のプログラムを表す概念が必要だと認識した。プロセスは以下を含む:
- プログラムコード
- データ（ヒープ、スタック）
- 実行状態（レジスタ、PC）
- リソース（ファイル、メモリ）
プロセスの形式的定義（Silberschatz, "Operating System Concepts"）:
プロセス = 実行中のプログラムのインスタンス
= (コード, データ, 実行コンテキスト, リソース)
スレッドの概念史
スレッド（Thread）という概念は、1960年代後半から1970年代にかけて発展した。
用語の由来: "thread of execution"（実行の糸）から。プログラムの実行を「糸」に例え、複数の糸が同時に進行するイメージ。
スレッドの定義（IEEE POSIX.1c-1995）:
スレッド = プロセス内の実行の流れ
= (スタック, レジスタ, スケジューリング属性)
※アドレス空間はプロセス内で共有
プロセス vs スレッドの比較
| 属性 | プロセス | スレッド | |-----|---------|---------| | アドレス空間 | 独立 | 共有 | | 作成コスト | 高い | 低い | | コンテキストスイッチ | 遅い | 速い | | 通信 | IPC必要 | メモリ共有 | | 障害の影響 | 独立 | 全スレッドに波及 | | 同期 | 複雑 | ミューテックス等 |
なぜ食事する哲学者問題はスレッドで実装するのか
- メモリ共有: フォーク状態を全哲学者が共有
- 軽量性: プロセスより生成・切り替えコストが低い
- 同期容易: ミューテックスで直接メモリを保護可能
- 実践的: 実際のサーバーアプリケーションと同様の構造
1.4 並行性と並列性
Rob Pikeの定義
Go言語の設計者Rob Pikeは、並行性と並列性の違いを明確に定義した（"Concurrency is not Parallelism", 2012）:
並行性（Concurrency）: > "Concurrency is about dealing with lots of things at once." > （並行性は、複数の物事を同時に扱うこと）
時間 →
CPU: [A][B][A][C][B][A][C][B]
タイムスライシングによる切り替え
並列性（Parallelism）: > "Parallelism is about doing lots of things at once." > （並列性は、複数の物事を同時に実行すること）
時間 →
CPU1: [A][A][A][A][A][A][A][A]
CPU2: [B][B][B][B][B][B][B][B]
物理的に同時実行
Amdahlの法則（1967年）
Gene Amdahlは1967年に、並列化による高速化の限界を定式化した（"Validity of the single processor approach to achieving large scale computing capabilities"）:
$$S(n) = \frac{1}{(1-p) + \frac{p}{n}}$$
ここで:
- $S(n)$: n個のプロセッサでの高速化率
- $p$: 並列化可能な部分の割合
- $n$: プロセッサ数
例: 90%が並列化可能な場合($p = 0.9$)
- $n = 2$: $S = 1.82$倍
- $n = 10$: $S = 5.26$倍
- $n = \infty$: $S = 10$倍（限界）
並列化不可能な10%が、全体の性能を制限する。
Gustafsonの法則（1988年）
John Gustafsonは、Amdahlの法則に対する補完的な見方を提案した:
$$S(n) = n - (1-p)(n-1)$$
問題サイズを大きくすれば、並列化可能部分も増大する。つまり、十分に大きな問題では、Amdahlの限界を超えられる。
1.5 42のPhilosophersプロジェクト
プロジェクト仕様
42のPhilosophersプロジェクトでは、Dijkstraの問題を以下の形式で実装する:
./philo number_of_philosophers time_to_die time_to_eat time_to_sleep \
[number_of_times_each_philosopher_must_eat]
引数:
number_of_philosophers: 哲学者の人数（= フォーク数）time_to_die: 最後の食事開始から死亡までの時間（ms）time_to_eat: 食事の所要時間（ms）time_to_sleep: 睡眠の所要時間（ms）number_of_times_each_philosopher_must_eat: 終了条件（オプション）
状態遷移モデル
各哲学者の状態遷移を有限オートマトンで表現:
取得成功
┌─────────┐
↓ │
[THINKING] ─→ [HUNGRY] ─→ [EATING] ─→ [SLEEPING]
↑ │
└──────────────────────────────────────┘
睡眠完了
ログ形式
プログラムは以下の形式でログを出力:
timestamp_in_ms X has taken a fork
timestamp_in_ms X is eating
timestamp_in_ms X is sleeping
timestamp_in_ms X is thinking
timestamp_in_ms X died
タイムスタンプはプログラム開始からのミリ秒。出力は競合なく行う必要がある（ログ出力もクリティカルセクション）。
実装要件
1.6 時間とタイミング
POSIXの時間関数
UNIXシステムでは、gettimeofday()が標準的な高精度時刻取得関数である:
#include <sys/time.h>
long get_timestamp_ms(void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return (tv.tv_sec * 1000L + tv.tv_usec / 1000L);
}
struct timeval:
tv_sec: 1970年1月1日からの秒数tv_usec: マイクロ秒（0-999999）- システムコールのオーバーヘッド:
usleep()は正確ではない - スケジューリングの遅延: スレッドがすぐ再開されるとは限らない
- クロック精度: システムクロックの解像度に依存
タイミングの課題
精密な待機の実装:
void precise_sleep(long duration_ms, long start_time)
{
long elapsed;
while (1)
{
elapsed = get_timestamp_ms() - start_time;
if (elapsed >= duration_ms)
break;
/* ビジーウェイトを避けるため短いsleep */
usleep(500);
}
}
1.7 データ構造の設計
基本構造体
typedef struct s_fork
{
pthread_mutex_t mutex;
int id;
} t_fork;
typedef struct s_philo
{
int id;
pthread_t thread;
long last_meal_time;
int meals_eaten;
t_fork *left_fork;
t_fork *right_fork;
struct s_data *data;
} t_philo;
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;
int simulation_end;
pthread_mutex_t print_mutex;
t_fork *forks;
t_philo *philos;
} t_data;
メモリレイアウト
t_data:
┌─────────────────────────────────────────┐
│ num_philos, time_to_die, etc. │
├─────────────────────────────────────────┤
│ forks* ──────→ [Fork 0][Fork 1]...[N-1] │
├─────────────────────────────────────────┤
│ philos* ─────→ [Philo 0][Philo 1]...[N-1]│
└─────────────────────────────────────────┘
各哲学者:
┌─────────────────────────────────────────┐
│ id, thread, last_meal_time, etc. │
├─────────────────────────────────────────┤
│ left_fork* ──→ forks[id] │
│ right_fork* ──→ forks[(id+1) % n] │
│ data* ──→ t_data構造体 │
└─────────────────────────────────────────┘
1.8 まとめ
本章では、並行プログラミングの歴史と理論的基盤を学んだ:
次章では、POSIXスレッド（pthread）の理論と実装について詳しく学ぶ。
---