第3章: 相互排除の理論とミューテックス
3.1 相互排除問題の歴史
クリティカルセクション問題の起源
クリティカルセクション問題（Critical Section Problem）は、1960年代初頭の並行プログラミング研究から生まれた。複数のプロセスが共有リソースにアクセスする際、データの一貫性をどのように保証するかという根本的な問題である。
問題の形式的定義（Dijkstra, 1965）:
N個のプロセス P₀, P₁, ..., P_{n-1} が存在し、
各プロセスは以下の構造を持つ:
while (true) {
エントリーセクション // クリティカルセクションへの入場を試みる
クリティカルセクション // 共有リソースにアクセス
イグジットセクション // クリティカルセクションからの退出を通知
残余セクション // クリティカルセクション外の処理
}
相互排除の要件
1963年、オランダの数学者Theodorus J. Dekkerは、相互排除問題の最初の正しい解法を発見した。Dijkstraはこれを形式化し、相互排除が満たすべき3つの要件を定義した（"Solution of a Problem in Concurrent Programming Control", Communications of the ACM, 1965）:
1. 相互排除（Mutual Exclusion）: 任意の時点で、クリティカルセクション内に存在できるプロセスは高々1つ。
∀t: |{i : P_i がクリティカルセクション内 at time t}| ≤ 1
2. 進行（Progress）: クリティカルセクションが空で、入場を希望するプロセスが存在するなら、有限時間内にいずれかのプロセスが入場できる。
(CS空 ∧ ∃P_i: P_i が入場希望) → ◇(∃P_j: P_j がCS内)
3. 有界待機（Bounded Waiting）: プロセスが入場を希望してから実際に入場するまでに、他のプロセスが入場できる回数に上限がある。
∀P_i: P_i が入場希望 → ◇_{k回以内}(P_i がCS内)
Dekkerのアルゴリズム（1963年）
Dekkerのアルゴリズムは、2プロセスの相互排除問題に対する最初の正しい解法である:
/* Dekker's Algorithm - 1963 */
/* 2プロセス向け相互排除 */
int flag[2] = {0, 0}; /* flag[i] = 1: プロセスiが入場希望 */
int turn = 0; /* 次に入場する権利を持つプロセス */
void enter_critical_section(int i)
{
int j = 1 - i; /* 他のプロセス */
flag[i] = 1; /* 入場希望を表明 */
while (flag[j])
{
if (turn == j)
{
flag[i] = 0; /* 一時的に譲歩 */
while (turn == j)
; /* busy wait */
flag[i] = 1; /* 再度希望を表明 */
}
}
/* クリティカルセクションに入場 */
}
void leave_critical_section(int i)
{
turn = 1 - i; /* 権利を他のプロセスに譲る */
flag[i] = 0; /* 入場希望を取り下げ */
}
Dekkerのアルゴリズムの特徴:
- 正しさ: 相互排除を保証
- 公平性: ターン変数により餓死を防止
- ビジーウェイト: CPUを消費しながら待機
Petersonのアルゴリズム（1981年）
Gary L. Petersonは1981年に、Dekkerのアルゴリズムをより単純化した解法を発表した（"Myths About the Mutual Exclusion Problem", Information Processing Letters, 1981）:
/* Peterson's Algorithm - 1981 */
/* よりシンプルな2プロセス相互排除 */
int flag[2] = {0, 0}; /* flag[i] = 1: プロセスiが入場希望 */
int turn; /* 譲歩するプロセス */
void enter_critical_section(int i)
{
int j = 1 - i;
flag[i] = 1; /* 入場希望を表明 */
turn = i; /* 自分が譲歩する意思を表明 */
/* 相手が希望していて、かつ自分が譲歩すべきなら待機 */
while (flag[j] && turn == i)
; /* busy wait */
/* クリティカルセクションに入場 */
}
void leave_critical_section(int i)
{
flag[i] = 0; /* 入場希望を取り下げ */
}
Petersonのアルゴリズムの正しさの証明:
定理: Petersonのアルゴリズムは相互排除を満たす。
証明: 背理法による。P₀とP₁が同時にクリティカルセクション内にあると仮定する。
両者がクリティカルセクションに入るためには、while条件が偽になる必要がある:
- P₀:
flag[1] == 0 || turn == 1 - P₁:
flag[0] == 0 || turn == 0
turnは0か1のいずれかなので、少なくとも一方はturn条件を満たさない。
したがって、少なくとも一方はflag条件（flag[j] == 0）を満たす必要がある。
しかし、入場時にflag[i] = 1を設定し、退出時まで変更しないため、
両者がクリティカルセクション内にいるならflag[0] == flag[1] == 1。
これは矛盾。したがって、相互排除は満たされる。 ∎
Lamportのベーカリーアルゴリズム（1974年）
Leslie Lamportは1974年に、N個のプロセスに対応したアルゴリズムを発表した（"A New Solution of Dijkstra's Concurrent Programming Problem", Communications of the ACM, 1974）:
/* Lamport's Bakery Algorithm - 1974 */
/* N プロセス向け相互排除 */
#define N 5 /* プロセス数 */
int choosing[N] = {0}; /* choosing[i] = 1: プロセスiが番号取得中 */
int number[N] = {0}; /* number[i]: プロセスiの順番票 */
int max(void)
{
int m = 0;
for (int i = 0; i < N; i++)
if (number[i] > m)
m = number[i];
return m;
}
void enter_critical_section(int i)
{
choosing[i] = 1;
number[i] = max() + 1; /* 順番票を取得 */
choosing[i] = 0;
for (int j = 0; j < N; j++)
{
/* jが番号取得中なら待機 */
while (choosing[j])
;
/* (number[j], j) < (number[i], i) なら待機 */
/* 辞書式順序で比較 */
while (number[j] != 0 &&
(number[j] < number[i] ||
(number[j] == number[i] && j < i)))
;
}
}
void leave_critical_section(int i)
{
number[i] = 0;
}
ベーカリーアルゴリズムの名前の由来:
- パン屋で順番待ちをする客のシステムに似ている
- 番号札を取り、小さい番号から順に呼ばれる
- 同じ番号の場合は、プロセスIDで順序付け
3.2 ハードウェア支援による同期
アトミック命令の発展
1960年代後半、ソフトウェアだけの相互排除アルゴリズムは非効率であることが認識され、ハードウェアレベルでの支援が導入された。
Test-and-Set命令（TAS）: IBM System/360（1964年）で導入された:
/* Test-and-Set の擬似コード */
/* ハードウェアによりアトミックに実行される */
bool test_and_set(bool *target)
{
bool old = *target;
*target = true;
return old;
}
/* TASを使った相互排除 */
bool lock = false;
void enter_critical_section(void)
{
while (test_and_set(&lock))
; /* スピンロック */
}
void leave_critical_section(void)
{
lock = false;
}
Compare-and-Swap命令（CAS）: IBM System/370（1970年代）で導入されたより汎用的な命令:
/* Compare-and-Swap の擬似コード */
/* ハードウェアによりアトミックに実行される */
bool compare_and_swap(int *ptr, int expected, int new_value)
{
if (*ptr == expected)
{
*ptr = new_value;
return true;
}
return false;
}
/* CASを使った相互排除 */
int lock = 0;
void enter_critical_section(void)
{
while (!compare_and_swap(&lock, 0, 1))
; /* スピンロック */
}
void leave_critical_section(void)
{
lock = 0;
}
スピンロックの理論
スピンロック（Spinlock）は、ロックが利用可能になるまでCPUを消費しながら待機するロック機構である。
John M. Mellor-CrummeyとMichael L. Scottは1991年に、スピンロックのスケーラビリティを分析した（"Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors", ACM TOCS, 1991）:
スピンロックの分類:
1. Test-and-Set Lock (TAS Lock)
- 単純だがキャッシュラインの競合が激しい
- O(n²) のバスト ラフィック（n: プロセス数）
2. Test-and-Test-and-Set Lock (TTAS Lock)
- ローカルキャッシュでスピン
- ロック解放時にキャッシュ無効化のストーム
3. Ticket Lock
- FIFO順序を保証
- 公平だがスケーラビリティに限界
4. MCS Lock (Mellor-Crummey & Scott, 1991)
- キューベースのスピンロック
- ローカル変数でスピン
- O(1) のメモリトラフィック
TTASロックの実装:
/* Test-and-Test-and-Set Lock */
int lock = 0;
void enter_critical_section(void)
{
while (1)
{
/* まずローカルキャッシュで確認（読み取りのみ） */
while (lock)
; /* ローカルスピン */
/* ロックが解放されたようなら、TASを試行 */
if (!test_and_set(&lock))
break; /* ロック取得成功 */
}
}
ブロッキングロック vs スピンロック
Maurice Herlihy と Nir Shavit は "The Art of Multiprocessor Programming"（2008年）において、ロック戦略の選択基準を示した:
スピンロックが有利な場合:
- クリティカルセクションが非常に短い
- スレッド数 ≤ CPUコア数
- コンテキストスイッチのコスト > スピン待機のコスト
ブロッキングロックが有利な場合:
- クリティカルセクションが長い
- スレッド数 > CPUコア数
- I/O待機を含む処理
期待待機時間の比較:
スピンロック:
T_spin = T_cs × (n-1) / 2 （nスレッド、均等競合時）
CPUを100%消費
ブロッキングロック:
T_block = T_context_switch × 2 + T_wakeup
CPUを解放
3.3 POSIXミューテックスの理論と実装
IEEE POSIX.1c-1995の規定
POSIXミューテックスは、IEEE Std 1003.1c-1995で標準化された。規格は以下を定義している:
pthread_mutex_t型:
/* 実装依存の不透明型 */
/* 以下は典型的なLinux glibcの実装 */
typedef union {
struct {
int __lock;
unsigned int __count;
int __owner;
unsigned int __nusers;
int __kind;
int __spins;
pthread_list_t __list;
} __data;
char __size[40];
long int __align;
} pthread_mutex_t;
ミューテックスの種類
POSIX規格は4種類のミューテックスを定義している:
1. PTHREAD_MUTEX_NORMAL（デフォルト）:
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_NORMAL);
/* 動作:
* - 同一スレッドによる二重ロック: デッドロック
* - 未ロック状態でのアンロック: 未定義動作
* - 他スレッドがロック中のアンロック: 未定義動作
*/
2. PTHREAD_MUTEX_ERRORCHECK:
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ERRORCHECK);
/* 動作:
* - 同一スレッドによる二重ロック: EDEADLK を返す
* - 未ロック状態でのアンロック: EPERM を返す
* - 他スレッドがロック中のアンロック: EPERM を返す
*/
3. PTHREAD_MUTEX_RECURSIVE:
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
/* 動作:
* - 同一スレッドによる再帰的ロック: 許可（カウント増加）
* - アンロックはカウント分必要
*/
4. PTHREAD_MUTEX_DEFAULT:
/* 実装依存、通常は NORMAL と同等 */
Futexの理論（Linux実装）
Linux 2.6以降、ミューテックスはFutex（Fast Userspace muTEX）を使用して実装される（Franke, Russell, Kirkwood, 2002）。
Futexの設計原理:
目標: ロック競合がない場合、システムコールを回避する
非競合時（Fast Path）:
1. ユーザー空間でアトミック操作のみ
2. CASでロック状態を変更
3. カーネル呼び出し不要
競合時（Slow Path）:
1. futex() システムコールを呼び出し
2. カーネルの待機キューで待機
3. ロック解放時に起床通知
Futexの基本操作:
#include <linux/futex.h>
#include <sys/syscall.h>
/* Futex システムコール */
long futex(uint32_t *uaddr, int futex_op, uint32_t val,
const struct timespec *timeout, uint32_t *uaddr2, uint32_t val3);
/* FUTEX_WAIT: 値が変わるまで待機 */
/* *uaddr == val なら待機、そうでなければ即座に戻る */
futex(uaddr, FUTEX_WAIT, val, timeout, NULL, 0);
/* FUTEX_WAKE: 待機中のスレッドを起床 */
/* 最大 val 個のスレッドを起床させる */
futex(uaddr, FUTEX_WAKE, val, NULL, NULL, 0);
ミューテックスのFutex実装:
/* 単純化したFutexベースミューテックス */
typedef struct {
uint32_t state; /* 0: unlocked, 1: locked no waiters, 2: locked with waiters */
} futex_mutex_t;
void futex_mutex_lock(futex_mutex_t *m)
{
uint32_t c;
/* Fast path: ロックが空いている場合 */
c = __sync_val_compare_and_swap(&m->state, 0, 1);
if (c == 0)
return; /* ロック取得成功 */
/* Slow path: 競合が発生 */
do {
/* 状態を "locked with waiters" に変更 */
if (c == 2 || __sync_val_compare_and_swap(&m->state, 1, 2) != 0)
{
/* カーネルで待機 */
syscall(SYS_futex, &m->state, FUTEX_WAIT, 2, NULL, NULL, 0);
}
/* 再度ロック取得を試行 */
c = __sync_val_compare_and_swap(&m->state, 0, 2);
} while (c != 0);
}
void futex_mutex_unlock(futex_mutex_t *m)
{
/* 状態を減少 */
if (__sync_fetch_and_sub(&m->state, 1) != 1)
{
/* 待機者がいる場合 */
m->state = 0;
syscall(SYS_futex, &m->state, FUTEX_WAKE, 1, NULL, NULL, 0);
}
}
3.4 レースコンディションの形式的定義
Netzer-Millerの分類（1992年）
Robert H. B. NetzerとBarton P. Millerは1992年に、データレースを形式的に分類した（"What are Race Conditions? Some Issues and Formalizations", ACM LOPLAS, 1992）:
定義（データレース）:
2つのメモリアクセス a₁ と a₂ がデータレースを形成する条件:
1. 異なるスレッドによるアクセス: thread(a₁) ≠ thread(a₂)
2. 同一メモリ位置へのアクセス: addr(a₁) = addr(a₂)
3. 少なくとも一方が書き込み: write(a₁) ∨ write(a₂)
4. 同期がない: ¬synchronized(a₁, a₂)
レースの種類:
1. 一般的レース（General Race）:
- 同期がなく、実行順序が非決定的
- 結果はスケジューリングに依存
2. データレース（Data Race）:
- 同一メモリ位置への競合するアクセス
- 少なくとも一方が書き込み
3. 高レベルレース（High-Level Race）:
- 同期があっても意味的に不正確
- 例: check-then-act パターン
Time-of-Check to Time-of-Use（TOCTOU）
TOCTOU問題は、高レベルレースの典型例である:
/* TOCTOU バグの例 */
/* スレッド1: ファイルの安全な書き込みを試みる */
if (access("/tmp/file", W_OK) == 0) /* Time-of-Check */
{
/* 攻撃者がシンボリックリンクを入れ替える可能性 */
fd = open("/tmp/file", O_WRONLY); /* Time-of-Use */
write(fd, data, len);
close(fd);
}
/* この間隔で攻撃可能！ */
修正方法:
/* TOCTOU を回避 */
/* オープンしてからチェック */
fd = open("/tmp/file", O_WRONLY);
if (fd < 0)
return -1;
/* ファイル記述子に対して権限チェック */
if (fstat(fd, &st) < 0)
{
close(fd);
return -1;
}
/* 所有者とパーミッションを確認 */
if (st.st_uid != getuid())
{
close(fd);
return -1;
}
/* 安全に書き込み */
write(fd, data, len);
close(fd);
Happens-Before関係とデータレース
Leslie Lamportの"Time, Clocks, and the Ordering of Events in a Distributed System"（1978）で導入されたHappens-Before関係（→）を用いて、データレースを定義できる:
定義（Happens-Before）:
イベント a が イベント b より前に発生する（a → b）:
1. 同一スレッド内で a が b より前に実行される
2. a がロック解放で、b が同じロックの取得
3. 推移律: a → c ∧ c → b ⟹ a → b
データレースの定義（Happens-Before基準）:
2つのメモリアクセス a, b がデータレースである:
1. addr(a) = addr(b)
2. write(a) ∨ write(b)
3. ¬(a → b) ∧ ¬(b → a) （順序付けがない）
3.5 ミューテックスAPI詳解
pthread_mutex_init
#include <pthread.h>
int pthread_mutex_init(pthread_mutex_t *restrict mutex,
const pthread_mutexattr_t *restrict attr);
セマンティクス:
mutex: 初期化するミューテックスへのポインタattr: 属性（NULLでデフォルト）- 成功時0、失敗時エラー番号を返す
実装注意点:
int init_mutexes(t_data *data)
{
int i;
int ret;
data->forks = malloc(sizeof(pthread_mutex_t) * data->num_philos);
if (!data->forks)
return (-1);
i = 0;
while (i < data->num_philos)
{
ret = pthread_mutex_init(&data->forks[i], NULL);
if (ret != 0)
{
/* エラー: 初期化済みミューテックスを破棄 */
while (--i >= 0)
pthread_mutex_destroy(&data->forks[i]);
free(data->forks);
return (-1);
}
i++;
}
return (0);
}
pthread_mutex_lock / unlock
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
メモリ順序保証（C11標準以降）:
pthread_mutex_lock は acquire セマンティクス:
- 以降のメモリ操作がロック取得より前に移動しない
- 他スレッドの release 以前の書き込みが可視
pthread_mutex_unlock は release セマンティクス:
- 以前のメモリ操作がロック解放より後に移動しない
- 他スレッドの acquire 以降の読み取りで可視
pthread_mutex_trylock
int pthread_mutex_trylock(pthread_mutex_t *mutex);
戻り値:
- 0: ロック取得成功
- EBUSY: ミューテックスが既にロック中
- EINVAL: 無効なミューテックス
使用例:
/* トライロックによるデッドロック回避パターン */
int try_take_forks(t_philo *philo)
{
int first, second;
first = philo->left_fork_id;
second = philo->right_fork_id;
pthread_mutex_lock(&philo->data->forks[first]);
if (pthread_mutex_trylock(&philo->data->forks[second]) != 0)
{
/* 2本目取得失敗: 1本目を解放して再試行 */
pthread_mutex_unlock(&philo->data->forks[first]);
return (0); /* 失敗 */
}
return (1); /* 成功 */
}
pthread_mutex_destroy
int pthread_mutex_destroy(pthread_mutex_t *mutex);
前提条件:
- ミューテックスはアンロック状態でなければならない
- 待機中のスレッドがいてはならない
リソースリーク防止:
void cleanup_all(t_data *data)
{
int i;
/* 全スレッドの終了を待機 */
i = 0;
while (i < data->num_philos)
{
pthread_join(data->philos[i].thread, NULL);
i++;
}
/* ミューテックスを破棄 */
i = 0;
while (i < data->num_philos)
{
pthread_mutex_destroy(&data->forks[i]);
i++;
}
pthread_mutex_destroy(&data->print_mutex);
pthread_mutex_destroy(&data->death_mutex);
/* メモリを解放 */
free(data->forks);
free(data->philos);
}
3.6 デッドロックの検出と回避
資源割当グラフ（Resource Allocation Graph）
Holt（1972）は、デッドロックを検出するための資源割当グラフを提案した:
グラフ G = (V, E) where:
V = P ∪ R （プロセス集合 ∪ リソース集合）
エッジの種類:
要求エッジ: P_i → R_j （P_i が R_j を要求中）
割当エッジ: R_j → P_i （R_j が P_i に割り当て済み）
デッドロック条件:
グラフにサイクルが存在する
食事する哲学者問題での資源割当グラフ:
デッドロック状態:
P₀ → F₀ → P₀ ← 要求
↓ ↑
F₄ F₁
↓ ↑
P₄ → F₃ → P₃ → F₂ → P₂ → P₁
↓ ↑
└──────────────┘
サイクル: P₀ → F₀ → P₀ ... 全員がサイクル形成
Coffman条件の破壊によるデッドロック回避
循環待機の防止
リソースの全順序付け:
/* フォークに全順序を付与 */
/* 常に小さい番号のフォークから取得 */
void take_forks_ordered(t_philo *philo)
{
int first, second;
if (philo->left_fork_id < philo->right_fork_id)
{
first = philo->left_fork_id;
second = philo->right_fork_id;
}
else
{
first = philo->right_fork_id;
second = philo->left_fork_id;
}
pthread_mutex_lock(&philo->data->forks[first]);
print_status(philo, "has taken a fork");
pthread_mutex_lock(&philo->data->forks[second]);
print_status(philo, "has taken a fork");
}
証明: この方法でデッドロックが発生しないことを示す。
仮にデッドロックが発生したとする。サイクルが存在するので:
P_{i₁} は F_{j₁} を保持し F_{j₂} を待機
P_{i₂} は F_{j₂} を保持し F_{j₃} を待機
...
P_{i_k} は F_{j_k} を保持し F_{j₁} を待機
順序付けにより、各プロセスは小さい番号のフォークから取得する。 したがって: j₁ < j₂ < j₃ < ... < j_k < j₁
これは矛盾。よってデッドロックは発生しない。 ∎
保持と待機の防止
全リソースの同時取得:
/* フォークを2本同時に取得する試み */
/* 両方取れなければ何も取らない */
int take_forks_atomic(t_philo *philo)
{
pthread_mutex_lock(&philo->data->fork_allocation_mutex);
/* 両方のフォークが利用可能か確認 */
if (philo->data->fork_available[philo->left_fork_id] &&
philo->data->fork_available[philo->right_fork_id])
{
philo->data->fork_available[philo->left_fork_id] = 0;
philo->data->fork_available[philo->right_fork_id] = 0;
pthread_mutex_unlock(&philo->data->fork_allocation_mutex);
return (1); /* 成功 */
}
pthread_mutex_unlock(&philo->data->fork_allocation_mutex);
return (0); /* 失敗 */
}
42プロジェクトでの実践的解法
偶奇による開始時間のずらし:
void *philosopher_routine(void *arg)
{
t_philo *philo = (t_philo *)arg;
/* 偶数番号の哲学者は少し待機 */
if (philo->id % 2 == 0)
ft_usleep(philo->data->time_to_eat / 2);
while (!check_simulation_end(philo->data))
{
/* 思考 */
print_status(philo, "is thinking");
/* フォーク取得 */
take_forks_ordered(philo);
/* 食事 */
print_status(philo, "is eating");
update_last_meal_time(philo);
ft_usleep(philo->data->time_to_eat);
/* フォーク解放 */
release_forks(philo);
/* 睡眠 */
print_status(philo, "is sleeping");
ft_usleep(philo->data->time_to_sleep);
}
return (NULL);
}
3.7 ライブロックと餓死
ライブロックの形式的定義
定義（ライブロック）:
システムがライブロック状態にある条件:
1. 全てのプロセスが活動している（ブロックされていない）
2. 有用な仕事をしていない
3. この状態が無限に続く
例: 廊下で向き合った2人が、互いに譲り合って進めない状態
ライブロックの回避:
/* 指数バックオフによるライブロック回避 */
int take_forks_with_backoff(t_philo *philo)
{
int backoff = 100; /* 初期バックオフ: 100マイクロ秒 */
int max_backoff = 10000; /* 最大: 10ミリ秒 */
while (1)
{
pthread_mutex_lock(&philo->data->forks[philo->left_fork_id]);
if (pthread_mutex_trylock(&philo->data->forks[philo->right_fork_id]) == 0)
return (1); /* 成功 */
pthread_mutex_unlock(&philo->data->forks[philo->left_fork_id]);
/* ランダムな待機（指数バックオフ） */
usleep(backoff + rand() % backoff);
backoff = (backoff * 2 > max_backoff) ? max_backoff : backoff * 2;
}
}
餓死の防止
定義（餓死）:
プロセス P が餓死している条件:
1. P が永久に待機状態にある
2. 他のプロセスは進行している
公平性（Fairness）の種類:
1. 弱い公平性（Weak Fairness）:
無限に有効なアクションはいつか実行される
2. 強い公平性（Strong Fairness）:
無限に頻繁に有効になるアクションはいつか実行される
3. FIFO公平性:
リクエスト順に処理される
食事する哲学者問題では、フォークの取得順序による公平性が必要:
/* 最後の食事時刻による優先度 */
int should_yield(t_philo *philo)
{
int i;
long my_last_meal;
long neighbor_last_meal;
my_last_meal = get_last_meal_time(philo);
/* 隣の哲学者の最後の食事時刻を確認 */
for (i = -1; i <= 1; i += 2)
{
int neighbor = (philo->id + i + philo->data->num_philos)
% philo->data->num_philos;
neighbor_last_meal = get_last_meal_time(&philo->data->philos[neighbor]);
/* 隣がより飢えているなら譲る */
if (neighbor_last_meal < my_last_meal)
return (1);
}
return (0);
}
3.8 データレース検出ツール
ThreadSanitizer（TSan）
Google開発のThreadSanitizerは、コンパイル時の計装によりデータレースを検出する:
# コンパイル
gcc -fsanitize=thread -g -O1 philo.c -lpthread -o philo
# 実行
./philo 5 800 200 200
TSanの動作原理:
1. 全てのメモリアクセスを記録
2. Happens-Before関係を追跡
3. 順序付けのないアクセスを検出
4. 片方が書き込みならデータレース報告
出力例:
==================
WARNING: ThreadSanitizer: data race (pid=12345)
Write of size 4 at 0x7b1234567890 by thread T1:
#0 set_death /path/philo.c:156
Previous read of size 4 at 0x7b1234567890 by thread T2:
#0 check_death /path/philo.c:123
Location is global 'g_data' of size 48 at 0x7b1234567890
SUMMARY: ThreadSanitizer: data race /path/philo.c:156 in set_death
==================
Helgrind（Valgrind）
# コンパイル（最適化なし推奨）
gcc -g -O0 philo.c -lpthread -o philo
# Helgrind実行
valgrind --tool=helgrind ./philo 5 800 200 200
Helgrindの検出対象:
- データレース
- 不正なミューテックス操作
- デッドロックの可能性
- 条件変数の誤用
DRD（Data Race Detector）
valgrind --tool=drd ./philo 5 800 200 200
DRDはHelgrindより高速だが、検出精度が若干低い場合がある。
3.9 Philosophersでの実装パターン
完全な初期化関数
int init_all_mutexes(t_data *data)
{
int i;
/* フォークのミューテックス */
data->forks = malloc(sizeof(pthread_mutex_t) * data->num_philos);
if (!data->forks)
return (-1);
i = 0;
while (i < data->num_philos)
{
if (pthread_mutex_init(&data->forks[i], NULL) != 0)
{
while (--i >= 0)
pthread_mutex_destroy(&data->forks[i]);
free(data->forks);
return (-1);
}
i++;
}
/* 出力用ミューテックス */
if (pthread_mutex_init(&data->print_mutex, NULL) != 0)
{
cleanup_forks(data);
return (-1);
}
/* 死亡フラグ用ミューテックス */
if (pthread_mutex_init(&data->death_mutex, NULL) != 0)
{
pthread_mutex_destroy(&data->print_mutex);
cleanup_forks(data);
return (-1);
}
/* 食事カウント用ミューテックス */
if (pthread_mutex_init(&data->meal_mutex, NULL) != 0)
{
pthread_mutex_destroy(&data->death_mutex);
pthread_mutex_destroy(&data->print_mutex);
cleanup_forks(data);
return (-1);
}
return (0);
}
スレッドセーフな状態アクセス
/* 死亡フラグのアトミックな読み取り */
int check_simulation_end(t_data *data)
{
int result;
pthread_mutex_lock(&data->death_mutex);
result = data->simulation_end;
pthread_mutex_unlock(&data->death_mutex);
return (result);
}
/* 死亡フラグのアトミックな設定 */
void set_simulation_end(t_data *data)
{
pthread_mutex_lock(&data->death_mutex);
data->simulation_end = 1;
pthread_mutex_unlock(&data->death_mutex);
}
/* 最終食事時刻の更新 */
void update_last_meal_time(t_philo *philo)
{
pthread_mutex_lock(&philo->data->meal_mutex);
philo->last_meal_time = get_timestamp_ms();
pthread_mutex_unlock(&philo->data->meal_mutex);
}
/* 最終食事時刻の取得 */
long get_last_meal_time(t_philo *philo)
{
long result;
pthread_mutex_lock(&philo->data->meal_mutex);
result = philo->last_meal_time;
pthread_mutex_unlock(&philo->data->meal_mutex);
return (result);
}
出力の保護
void print_status(t_philo *philo, char *status)
{
long timestamp;
pthread_mutex_lock(&philo->data->print_mutex);
if (!check_simulation_end(philo->data))
{
timestamp = get_timestamp_ms() - philo->data->start_time;
printf("%ld %d %s\n", timestamp, philo->id, status);
}
pthread_mutex_unlock(&philo->data->print_mutex);
}
void print_death(t_philo *philo)
{
long timestamp;
pthread_mutex_lock(&philo->data->print_mutex);
timestamp = get_timestamp_ms() - philo->data->start_time;
printf("%ld %d died\n", timestamp, philo->id);
pthread_mutex_unlock(&philo->data->print_mutex);
}
3.10 まとめ
本章では、相互排除の理論とミューテックスの実装について学んだ:
次章では、セマフォについて学び、Philosophersのボーナス課題（プロセスベース実装）に備える。
---