プロセスの実体と制御構造

現代のオペレーティングシステムにおいて、複数のプログラムを同時に実行する環境を実現するために「プロセス」の概念が導入されている。単なる静的な命令列の集合であるプログラムとは異なり、プロセスはメモリー内での実行状態、資源割当情報、実行コンテキストを統合した動的な実体である。システムは各プロセスに対してプロセス制御ブロック（PCB）を割り当て、これを通じて実行状態の追跡、コンテキストの保存・復元、資源管理を一元化している。PCBが存在しない限り、システムは対象の動作単位を認識・制御することができないため、これがプロセスが存在するための必須条件となる。

状態遷移モデル

プロセスはシステム内の資源競合や外部イベントの影響を受けて、複数の状態を循環する。基本的な状態として「実行中」「準備完了」「ブロック（待機）」の三態が定義され、これに加えて生成途中の「作成中」と終了処理中の「終了中」が追加される場合もある。準備完了状態はCPU割当のみを待っている状態であり、ブロック状態はCPU以外のリソース（I/O完了、メモリー確保、同期イベントなど）を待機している状態を指す。両者を明確に区別する理由は、CPU割り当ての頻度と外部資源待機の時間スケールに大きな差があるためである。

スレッドと実行単位の変遷

プロセスが資源割当の単位である一方、CPUスケジューリングの最小単位として「スレッド」が導入された。スレッドは同じプロセス空間内の共有メモリーや開いたファイルディスクリプタを共有しつつ、独自のプログラムカウンター、レジスタセット、実行スタック、およびスレッド制御ブロック（TCB）を持つ軽量な実行ストリームである。スレッド切り替えはプロセス切り替えよりもはるかにオーバーヘッドが低く、同一プロセス内での並列処理や対話型応答の高速化に寄与する。実装方式にはユーザー空間で管理するユーザーレベルスレッド、カーネル空間で直接管理するカーネルレベルスレッド、およびそれらをハイブリッドに構成する方式が存在し、システムの用途に合わせて選択される。

CPUリソースの割当とスケジューリング理論

利用可能なCPUコア数より実行可能なタスク数が多い場合、システムは適切なアルゴリズムを用いてどのタスクに処理時間を割当てるかを決定する。この処理がスケジューリングであり、その目的はシステム全体のスループット向上、平均応答時間短縮、ユーザー体験の最適化、およびリアルタイム制約の遵守にある。

代表的なスケジューリングアルゴリズム

• 先着順（FCFS）: 到着順に処理を割り当てる単純な非先占方式。実装は容易だが、長時間実行されるタスクが短いタスクを待たせる「 convoy effect」を生じやすく、対話型システムには不向き。
• 最短処理時間優先（SJF）: 推定実行時間が短いタスクを優先する方式。平均待ち時間を理論的に最小化できる利点があるが、実行時間の推定誤差や長期タスクの「飢餓」現象が課題となる。
• タイムスライス方式（RR）: 各タスクに固定時間のスライスを循環配分する先占型アルゴリズム。対話性を確保できるが、スライス長が短すぎるとコンテキストスイッチのオーバーヘッドがシステム性能を阻害する。
• 優先度ベーススケジューリング: タスクの重要度や性質（I/O密集型、CPU密集型、システムプロセス、ユーザープロセス）に応じて優先度を付与し、先占可否の組み合わせで柔軟に制御する。
• マルチレベルフィードバックキュー（MLFQ）: 複数階層のキューを併用し、CPU使用率に応じて動的に優先度を昇降させる。短時間対話タスクは上位キューで迅速に処理され、長時間バッチタスクは下位キューで確実に処理されるよう設計されている。

スケジューラは通常、キュー管理モジュール、割当決定モジュール、コンテキストスイッチ実行モジュールから構成される。コンテキストスイッチ時には、現在のレジスタ値やプログラムカウンターをPCBに保存し、対象タスクの保存済み状態をレジスタに復元する。ハードウェア支援レジスタペアを用いることで、この切り替えコストを大幅に低減させる実装も普及している。

並行実行における同期・排他制御

複数のプロセスやスレッドが同時に実行されるとき、共有リソースへの安全なアクセスを確保する仕組みが必須となる。一度に一つの動作単位のみが利用を許されるリソースを「臨界資源」と呼び、それに対するアクセス制御が「排他」、実行順序やデータ依存性に基づいた協調動作が「同期」として定義される。

信号量と低水準同期プリミティブ

信号量（Semaphore）は整数値と待ち行列を保持する同期構造であり、P操作（待機・デクリメント）とV操作（通知・インクリメント）の原子的操作によって構成される。P操作で値が負になる場合、呼び出し元は自発的にブロックされ、V操作によって待ち行列から解除される。この「権利放棄待機」の性質により、CPUの空回転を防ぎながら安全なリソース共有が可能となる。古典的な同期パターンとしては、バッファー共有による生産者-消費者問題、共有メモリへの同時読み書きを許容する読者-書作者問題、資源配分順序を制御する喫煙者問題などが挙げられる。

管程（Monitor）による高水準同期

信号量を各プロセスで個別に管理すると、同期ロジックが散在しデッドロックの原因になりやすい。管程は共有データ構造と、その構造に対する操作をカプセル化したモジュールであり、内部では排他制御が自動的に行われる。条件変数（Condition Variable）を用いることで、特定の状態が満たされるまで実行を一時停止し、他のプロセスによる状態変更時に選択的に再開させる柔軟な同期を実現する。

哲学者の夕食問題に対する制御戦略

有限のリソース配分において循環待機を防ぐための古典的課題。以下の三つのアプローチで解決策が示される。

// 戦略1: 同時食事人数を制限して完全な循環待機を防ぐ
semaphore stick_lock[5] = {1, 1, 1, 1, 1};
semaphore dining_mutex = 1;
int active_diners = 0;
semaphore max_diners_limit = 0;

void philosopher_task(int id) {
    while (true) {
        // 食事開始前の人数チェック
        P(dining_mutex);
        active_diners++;
        if (active_diners == 5) P(max_diners_limit);
        V(dining_mutex);

        // 左右のフォークを取得
        P(stick_lock[id]);
        P(stick_lock[(id + 1) % 5]);

        // 食事処理
        eat_phase();

        // フォークの解放
        V(stick_lock[id]);
        V(stick_lock[(id + 1) % 5]);

        // 人数更新と待機状態の解除
        P(dining_mutex);
        active_diners--;
        if (active_diners == 4) V(max_diners_limit);
        V(dining_mutex);

        // 思索フェーズ
        think_phase();
    }
}

// 戦略2: 両方のフォーク取得を原子的操作で保護
semaphore stick_lock[5] = {1, 1, 1, 1, 1};
semaphore access_guard = 1;

void philosopher_task(int id) {
    while (true) {
        P(access_guard);
        P(stick_lock[id]);
        P(stick_lock[(id + 1) % 5]);
        V(access_guard);

        eat_phase();

        V(stick_lock[id]);
        V(stick_lock[(id + 1) % 5]);

        think_phase();
    }
}

// 戦略3: 取得順序の非対称化による deadlock 排除
semaphore stick_lock[5] = {1, 1, 1, 1, 1};

void philosopher_task(int id) {
    while (true) {
        int first, second;
        // 偶数番は左→右、奇数番は右→左の順序で取得
        if (id % 2 == 0) {
            first = id;
            second = (id + 1) % 5;
        } else {
            first = (id + 1) % 5;
            second = id;
        }

        P(stick_lock[first]);
        P(stick_lock[second]);

        eat_phase();

        V(stick_lock[first]);
        V(stick_lock[second]);

        think_phase();
    }
}

資源循環待機（デッドロック）の解析と対処

複数の実行単位が相互に相手の保有するリソースを要求し合い、外部からの介入がない限り処理が進展しない状態をデッドロックと呼ぶ。発生の必要条件は「相互排他」「保持と待機」「優先譲渡の禁止」「循環待機」の四つであり、これらが同時に成立するとシステムは停止状態に陥る。

対策としては、発生前に条件の一つを人為的に破る「予防」、状態遷移グラフや安全性行列を用いて安全なリソース割当を計算する「回避」、実行中に資源配分グラフを周期ごとに走査して循環を検出し、プロセスの巻き戻しや終了により状態を解消する「検出と回復」の三つが主流である。実装コスト、システム可用性、リソース利用率のトレードオフを考慮し、ターゲット環境に応じた手法が選択される。