第2章: POSIXスレッドの理論と実践
2.1 スレッド実装モデルの歴史
ユーザレベルスレッド
1970年代から1980年代にかけて、スレッドは主にユーザレベルで実装されていた。OSはスレッドを認識せず、ユーザ空間のライブラリがスレッドスケジューリングを担当した。
ユーザレベルスレッドの特徴:
プロセス内:
┌─────────────────────────────┐
│ スレッドスケジューラ(ライブラリ)│
├─────────────────────────────┤
│ [T1] [T2] [T3] [T4] │
│ ↓ ↓ ↓ ↓ │
│ ユーザ空間スタック │
└─────────────────────────────┘
↓
┌─────────────────────────────┐
│ カーネル │
│ (プロセスは1つとして認識) │
└─────────────────────────────┘
長所:
- コンテキストスイッチが高速（カーネル呼び出し不要）
- 移植性が高い
- カスタムスケジューリングが可能
短所:
- 1スレッドがブロックすると全スレッドがブロック
- マルチプロセッサの恩恵を受けられない
カーネルレベルスレッド
1990年代、OSはスレッドを直接サポートするようになった。カーネルレベルスレッドでは、OSがスレッドのスケジューリングを担当する。
カーネルレベルスレッドの特徴:
┌─────────────────────────────┐
│ [T1] [T2] [T3] [T4] │
│ ユーザ空間 │
└──────────┬──────────────────┘
↓ システムコール
┌─────────────────────────────┐
│ カーネル │
│ スレッドスケジューラ │
│ [KT1] [KT2] [KT3] [KT4] │
│ ↓ ↓ ↓ ↓ │
│ [CPU1] [CPU2] │
└─────────────────────────────┘
長所:
- マルチプロセッサを活用可能
- 1スレッドのブロックが他に影響しない
- OSスケジューラによる公平なスケジューリング
短所:
- コンテキストスイッチにカーネル呼び出しが必要
- スレッド生成コストが高い
ハイブリッドモデル（M:N モデル）
現代のシステムは、両方の長所を組み合わせたハイブリッドモデルを採用することもある（Solaris、一部のLinux実装など）。
M個のユーザレベルスレッドをN個のカーネルスレッドにマッピングする:
ユーザ空間: [T1] [T2] [T3] [T4] [T5] [T6] (M個)
↓ ↓ ↓
カーネル: [KT1] [KT2] [KT3] (N個, N < M)
↓ ↓ ↓
CPU: [C1] [C2] [C3]
2.2 POSIXスレッド標準
IEEE POSIX.1c-1995
1995年、IEEEはPOSIX.1cとしてスレッドAPIを標準化した。これは「POSIX Threads」または「pthreads」として知られる。
標準化の目的:
- 異なるUNIX間での移植性
- マルチスレッドプログラミングの統一的インターフェース
- 同期プリミティブの標準化
pthreadのスレッドモデル
POSIX.1c では、スレッドは以下の属性を持つ:
/* スレッド識別子 */
typedef ... pthread_t;
/* スレッド属性 */
typedef struct {
int detachstate; /* PTHREAD_CREATE_JOINABLE / DETACHED */
int schedpolicy; /* スケジューリングポリシー */
int inheritsched; /* スケジューリング継承 */
int scope; /* 競合スコープ */
size_t stacksize; /* スタックサイズ */
void *stackaddr; /* スタックアドレス */
/* ... */
} pthread_attr_t;
スレッド競合スコープ
POSIX.1cは2種類の競合スコープ（contention scope）を定義:
Linux（NPTL）はシステム競合スコープのみをサポートする。
2.3 pthread API
スレッドの作成
#include <pthread.h>
int pthread_create(pthread_t *thread,
const pthread_attr_t *attr,
void *(*start_routine)(void *),
void *arg);
形式的意味論:
precondition:
thread ≠ NULL
start_routine ≠ NULL
postcondition:
*thread = 新しいスレッドの識別子
新しいスレッドは start_routine(arg) を実行開始
return 0 (成功) または エラーコード
戻り値:
0: 成功EAGAIN: システムリソース不足EINVAL: 無効な属性EPERM: 権限不足
スレッドの終了と待機
void pthread_exit(void *retval);
int pthread_join(pthread_t thread, void **retval);
pthread_joinの意味論:
blocking_call:
呼び出しスレッドは thread が終了するまでブロック
終了後、threadのリソースを解放
retval ≠ NULL なら、*retval = threadの戻り値
注意: 各スレッドは、pthread_joinまたはpthread_detachのいずれかで処理する必要がある。どちらも行わないとリソースリークが発生する。
スレッドの分離
int pthread_detach(pthread_t thread);
分離されたスレッドは:
pthread_joinできない- 終了時に自動的にリソースが解放される
- SCHED_OTHER: デフォルトの時分割スケジューリング
- SCHED_FIFO: 先入れ先出しリアルタイムスケジューリング
- SCHED_RR: ラウンドロビンリアルタイムスケジューリング
2.4 スレッドスケジューリング
スケジューリングポリシー
POSIX.1bは以下のスケジューリングポリシーを定義:
int pthread_attr_setschedpolicy(pthread_attr_t *attr, int policy);
int pthread_attr_getschedpolicy(const pthread_attr_t *attr, int *policy);
優先度
struct sched_param {
int sched_priority;
};
int pthread_attr_setschedparam(pthread_attr_t *attr,
const struct sched_param *param);
優先度の範囲はポリシーにより異なる:
int min = sched_get_priority_min(SCHED_FIFO);
int max = sched_get_priority_max(SCHED_FIFO);
コンテキストスイッチ
コンテキストスイッチとは、CPUが1つのスレッドから別のスレッドに実行を切り替えることである。
スイッチ時に保存されるコンテキスト:
- プログラムカウンタ（PC）
- スタックポインタ（SP）
- 汎用レジスタ
- 浮動小数点レジスタ
- CPU状態レジスタ
時間 →
Thread A: [実行][保存]─────────────[復元][実行]
Thread B: ─────────[復元][実行][保存]─────────
↑ ↑
コンテキストスイッチ
コンテキストスイッチのオーバーヘッド:
- 直接コスト: レジスタ保存・復元（～1μs）
- 間接コスト: キャッシュの無効化（～数十μs）
2.5 メモリモデルとデータレース
データレースの形式的定義
Leslie Lamportの研究（"How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", 1979）に基づく定義:
データレース: 2つの操作が以下の条件を全て満たすとき、データレースが発生:
- 同じメモリ位置にアクセス
- 少なくとも1つが書き込み
- 同期によって順序付けられていない
happens-before関係
happens-before（→）関係は、イベント間の因果関係を定義する:
a → b (aはbの前に起こる)
- 同一スレッド内: 順序通り
- 異なるスレッド間: 同期操作による
ミューテックスによるhappens-before:
Thread 1: Thread 2:
x = 1
unlock(m) ──────→ lock(m)
y = x // x = 1 が保証
C11/C++11メモリモデル
2011年、CとC++の標準はメモリモデルを形式化した:
/* C11 アトミック操作 */
#include <stdatomic.h>
atomic_int counter = 0;
void increment(void) {
atomic_fetch_add(&counter, 1); /* アトミック */
}
しかし、42のphilosophersではC11アトミックは通常使用せず、ミューテックスを使用する。
2.6 メモリレイアウトと共有
プロセスのメモリ構造
高位アドレス
┌─────────────────────────────┐
│ カーネル空間 │ ← ユーザアクセス不可
├─────────────────────────────┤
│ 環境変数、コマンドライン引数 │
├─────────────────────────────┤
│ スタック (メインスレッド) │ ↓ 成長方向
├─────────────────────────────┤
│ スタック (Thread 2) │ ← pthread_createで確保
├─────────────────────────────┤
│ スタック (Thread 3) │
├─────────────────────────────┤
│ [未使用] │
├─────────────────────────────┤
│ 共有ライブラリ │
├─────────────────────────────┤
│ ヒープ (malloc) │ ↑ 成長方向
├─────────────────────────────┤
│ BSS (未初期化データ) │ ← 共有
├─────────────────────────────┤
│ DATA (初期化済みデータ) │ ← 共有
├─────────────────────────────┤
│ TEXT (コード) │ ← 共有、読み取り専用
└─────────────────────────────┘
低位アドレス
スタックサイズ
各スレッドは独自のスタックを持つ。デフォルトサイズはシステムにより異なる:
pthread_attr_t attr;
size_t stacksize;
pthread_attr_init(&attr);
pthread_attr_getstacksize(&attr, &stacksize);
printf("デフォルトスタックサイズ: %zu bytes\n", stacksize);
/* 典型的には 8MB (8388608 bytes) */
カスタムスタックサイズの設定:
pthread_attr_setstacksize(&attr, 1024 * 1024); /* 1MB */
2.7 Philosophersでのスレッド実装
データ構造
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;
pthread_mutex_t meal_mutex; /* last_meal_time保護 */
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 end_mutex; /* simulation_end保護 */
pthread_mutex_t print_mutex; /* 出力保護 */
t_fork *forks;
t_philo *philos;
} t_data;
スレッド生成
int create_philosophers(t_data *data)
{
int i;
i = 0;
while (i < data->num_philos)
{
data->philos[i].id = i + 1;
data->philos[i].meals_eaten = 0;
data->philos[i].last_meal_time = data->start_time;
data->philos[i].left_fork = &data->forks[i];
data->philos[i].right_fork = &data->forks[(i + 1) % data->num_philos];
data->philos[i].data = data;
if (pthread_create(&data->philos[i].thread, NULL,
philosopher_routine, &data->philos[i]) != 0)
return (error_cleanup(data, i));
i++;
}
return (1);
}
スレッド関数
void *philosopher_routine(void *arg)
{
t_philo *philo;
philo = (t_philo *)arg;
/* 偶数番号の哲学者は少し待機（デッドロック回避） */
if (philo->id % 2 == 0)
precise_usleep(1);
while (!is_simulation_end(philo->data))
{
/* 思考 */
print_status(philo, "is thinking");
/* フォーク取得 → 食事 */
if (!eat(philo))
break;
/* 睡眠 */
print_status(philo, "is sleeping");
precise_usleep(philo->data->time_to_sleep);
}
return (NULL);
}
終了処理
void wait_for_philosophers(t_data *data)
{
int i;
i = 0;
while (i < data->num_philos)
{
pthread_join(data->philos[i].thread, NULL);
i++;
}
}
void cleanup(t_data *data)
{
int i;
/* ミューテックスの破棄 */
i = 0;
while (i < data->num_philos)
{
pthread_mutex_destroy(&data->forks[i].mutex);
pthread_mutex_destroy(&data->philos[i].meal_mutex);
i++;
}
pthread_mutex_destroy(&data->end_mutex);
pthread_mutex_destroy(&data->print_mutex);
/* メモリ解放 */
free(data->forks);
free(data->philos);
}
2.8 時間管理
高精度時刻取得
#include <sys/time.h>
long get_time_ms(void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return (tv.tv_sec * 1000L + tv.tv_usec / 1000L);
}
精密な待機
usleep()は保証された精度がないため、アクティブなポーリングと組み合わせる:
void precise_usleep(long duration_ms)
{
long start;
long elapsed;
long remaining;
start = get_time_ms();
while (1)
{
elapsed = get_time_ms() - start;
if (elapsed >= duration_ms)
break;
remaining = duration_ms - elapsed;
if (remaining > 10)
usleep(remaining * 500); /* 半分の時間待機 */
else
usleep(100); /* 短い間隔でポーリング */
}
}
2.9 まとめ
本章では、POSIXスレッドの理論的基盤と実装を学んだ:
次章では、ミューテックスと相互排除の理論について詳しく学ぶ。
---