タスク（プロセス）管理

このページでは、タスクの3つの状態と遷移、スケジューリング方式、セマフォなどによる同期・排他制御、デッドロック、プロセスとスレッドの違いがわかります。

一言で言うと：
- 1つのCPUで、たくさんのタスク（プログラム）を順番に切り替えながら動かすための仕組みの話。「どの状態にあるか」「いつ、どの順で切り替えるか」「待ち合わせ方」「同時に触らせない方法」が出てくる。

状態を管理する（状態遷移）→ 切り替える（コンテキスト切替え）→ 順番を決める（スケジューリング）→ 待ち合わせる（同期制御）→ 同時に触らせない（排他制御）→ 軽く分ける（プロセスとスレッド）

覚え方の軸
タスクとタスクの状態遷移：タスクは3つの状態を行き来する
タスク制御の方式
タスクの切り替え：今の状態を保存して入れ替える
タスクのスケジューリング方式：どの順番で実行するか
同期制御：他のタスクの合図を待ち合わせる
排他制御：共有資源を同時に触らせない
プロセスとスレッド：重い並行処理と、軽い並行処理
混同しやすいペア

覚え方の軸

タスクの状態は3つ（実行可能・実行・待ち）、矢印は6本：
- 「実行可能 → 実行」がディスパッチ、「実行 → 実行可能」がプリエンプション、「実行 → 待ち」は入出力要求など。待ち状態から実行状態へ直接は戻らない（必ず実行可能状態を通る）
スケジューリングは「途中で取り上げるか（プリエンプティブか）」で分ける：
- 取り上げない＝到着順だけ。取り上げる＝優先順位、ラウンドロビン、フィードバック待ち行列、処理時間順
「待たせすぎ」問題と、その対策をセットで覚える：
- スタベーション（ずっと順番が来ない）→ エージング（待った分だけ優先度を上げる）
協調の仕方は「待ち合わせる（同期）」と「同時に触らせない（排他）」の2つ：
- どちらにもセマフォが使える。P操作＝借りる・待つ、V操作＝返す・知らせる
重さで並べる：
- プロセス（アドレス空間ごと別。重い）⇔ スレッド（アドレス空間を共有。軽い＝軽量プロセス）

タスクとタスクの状態遷移：タスクは3つの状態を行き来する

タスク（プロセス）：
- CPUから見た「処理の単位」。CPUが実行する「プログラム」のこと
- 補足：
  - タスクとプロセスは厳密には違うが、試験では「タスク＝プロセス」と考えてよい
タスク管理：
- 複数のタスクを切り替えながら、CPUを有効活用できるように実行を制御する（OSの仕事）
- タスクは、OSにリソースを要求して割当てを受ける
タスクの3つの状態

状態	中身
実行可能状態	実行できるが、CPU使用権が来るのを待っている（レジに並んでいる）
実行状態	CPU使用権をもらって処理している（レジで会計中）
待ち状態	入出力の完了や、他のタスクからの合図を待っている（財布を取りに行っている）

状態遷移の6本の矢印
- ①タスクの生成：
  - 生成されたタスクは、実行可能状態の待ち行列に加わる
- ②実行可能 → 実行（ディスパッチ）：
  - ディスパッチャ（CPUスケジューラ）がCPUを割り当てる
- ③実行 → 実行可能（プリエンプション）：
  - 割り当てられたCPU時間が終わったとき、またはより優先度の高いタスクが実行可能になったとき、強制的に中断される（タイマ割込みなど）
- ④実行 → 待ち：
  - スーパバイザコール（SVC）による入出力要求をして完了を待つときや、ある事象の待ち合わせが起きたとき
- ⑤待ち → 実行可能：
  - 待ちの原因の事象が完了したとき（入出力動作の完了＝入出力割込み、待機の完了）
- ⑥タスクの消滅：
  - 実行が終わったタスクは消滅し、使っていた資源（リソース）はすべて解放される
- 注意：
  - 待ち状態から実行状態へ直接は移らない。実行可能状態から実行状態へ移るのはディスパッチだけ
マルチプログラミング（多重プログラミング）：
- 実行中のタスクが入出力をするとCPUが空く。その空き時間に別のタスクを動かして、CPUを効率よく使う
補足：
- 制御系の組込みシステムで使うリアルタイムOS（RTOS）には、3つの状態に加えて「休止状態」がある。あらかじめタスクを生成して休止状態にしておき、起動システムコールで実行可能状態にする（厳密なリアルタイム性のため）

タスク制御の方式

プリエンプション：
- 実行中のタスクのCPU使用権を奪い、実行を一時的に中断させること
プリエンプティブ方式：
- プリエンプション機能を使う方式。OSがCPU割当てを管理するので、強制的にタスクを切り替えられる
ノンプリエンプティブ方式：
- プリエンプション機能を使わない方式。実行中のタスクを中断できない
- タスクが自分からOSに制御を戻すか、終了するまで、他のタスクを実行できない

タスクの切り替え：今の状態を保存して入れ替える

TCB（Task Control Block：タスク制御ブロック）：
- タスクの実行に必要な情報を持つ、主記憶内のデータ構造
- 中身：
  - タスクの識別子（ID）、優先度、現在の状態、CPU使用時間、アドレス管理情報、PSW退避領域など
- 補足：
  - 「プロセス」という用語を使うOSでは、PCB（Process Control Block：プロセス制御ブロック）で管理する。中身はTCBとほぼ同じ
PSW（Program Status Word：プログラム状態語）：
- タスクを再開するために必要な情報（切替え時点のプログラムカウンタの値など）を持つ特殊なレジスタ。タスク切替えで特に重要
- 補足：
  - PSWはCPUのレジスタだが、専用の記憶装置を持たず、情報は主記憶の特定の領域に記憶される
コンテキストスイッチング（コンテキストの切替え）：
- 1つのCPUで複数のタスクを動かすために、CPUが持つ実行中のタスク情報（PSW）、レジスタ群、主記憶のアドレス空間を入れ替える操作
- 手順：
  - ①タスクAのPSWとレジスタ群を退避して中断 → ②タスクBのPSWとレジスタ群を割り当てて実行
- レジスタ群の切替えは速いが、アドレス空間の切替えはオーバヘッドが大きい
- スレッドはアドレス空間を共有するので、切替えのオーバヘッドが大きく減る → マルチプログラミング環境を有効に活用できる
- 例え：
  - 読みかけの本にしおり（PSW）をはさんで、別の本に持ち替える。同じ本の別の章（スレッド）なら、本棚から出し直さなくてよいので速い
コンカレント処理：
- プログラムの同時並行処理（マルチプログラミング）のこと。コンカレント＝「同時期」
タスクを切り替えるタイミング（多くのOSは2つを組み合わせる）
- イベントドリブン方式：
  - 「マウスがクリックされた」「入出力要求が出た」「入出力が終わった」など、環境の変化で起きる割込みで切り替える
- タイムスライス方式：
  - 一定時間ごと（周期的）に切り替える
  - 各タスクに割り当てる時間をタイムクウォンタムという。インターバルタイマを使い、タイムクウォンタムが終わったらタイマ割込みを起こす

タスクのスケジューリング方式：どの順番で実行するか

目的：
- 複数のタスクを（見かけ上）並行処理するとき、応答性とCPUの利用効率を考えて順番を決める
タスクスケジューラ：
- タスクのスケジューリングを行うもの
分類

分類	方式
ノンプリエンプティブ	到着順方式
プリエンプティブ	優先順位方式、ラウンドロビン方式、フィードバック待ち行列方式、処理時間順方式

補足：
- プリエンプティブな方式では、中断されたタスクは中断された状態から再開される
到着順方式（FCFS：First Come First Served）：
- 優先度を持たせず、実行可能状態になった順に実行する。終わるまでプリエンプションは起きない
優先順位方式（優先度順方式ともいう）：
- 優先度の高い順に実行する。実行中より高い優先度のタスクが実行可能になると、プリエンプションが起きる
- 静的優先順位方式：
  - 優先度を最初に決めた値から変えない。優先度の低いタスクがなかなか実行できないスタベーション（starvation：飢餓状態）が起こりうる
- 動的優先度順方式：
  - 待ち時間が一定以上になったタスクの優先度を動的に上げて、実行できるようにする。スタベーションを避けられる
  - 優先度を上げて実行のチャンスを与えることをエージング（aging）というので、エージング方式ともいう
- リソーススタベーション：
  - 優先度の低いタスクが、必要なリソースを獲得できない状況
ラウンドロビン方式★：
- 実行可能待ち行列の先頭から順に、一定のCPU時間（タイムクウォンタム）を割り当てる。時間内に終わらなければ中断して待ち行列の末尾に回し、次のタスクにCPUを渡す
- インターバルタイマからのタイマ割込みで、一定時間ごとに強制的に切り替える
- タスクを平等に実行できるので、TSS（タイムシェアリングシステム）に向いている
- タイムクウォンタムの長さで性格が変わる
  - 長くする → 到着順方式に近づく
  - 短くする → 処理時間の短いタスクの応答が速くなり、処理時間順方式に近づく
TSS（Time Sharing System：タイムシェアリングシステム）：
- 複数のユーザが1台のコンピュータを、対話型で同時・平等に使えるようにしたシステム
フィードバック待ち行列方式：
- ラウンドロビン方式に優先度を加えたもの（多段のラウンドロビン方式）
- 優先度ごとに、タイムクウォンタムが違う待ち行列を持つので、多重待ち行列方式ともいう
- 最初は最も高い優先度を与え、終わらなければ優先度を順に下げていく（CPUを占有しがちなタスクの優先度をだんだん下げる）
- 優先度が低いほど、タイムクウォンタムは長くなる
- スタベーションが起きるので、エージングなどの対策が必要
処理時間順方式（SPT：Shortest Processing Time First）：
- 処理時間の短い順に実行する
- 処理時間は前もって予測できないので、実際にはフィードバック待ち行列方式として実現される
- SRPT（残余処理時間順）方式：
  - SPTの変形。残っている処理時間でSPTを適用する
例題（平均ターンアラウンドタイム）：
- 時刻0に、処理時間が A＝6秒、B＝3秒、C＝1秒のタスクがこの順に到着した（切替え時間は無視）
- 到着順（A → B → C）：
  - 終了時刻は A＝6、B＝9、C＝10 → 平均＝（6＋9＋10）÷3＝25÷3≒8.3秒
- 処理時間順（C → B → A）：
  - 終了時刻は C＝1、B＝4、A＝10 → 平均＝（1＋4＋10）÷3＝15÷3＝5秒
- ポイント：
  - 短いものを先にやると、全体の平均待ち時間は短くなる（最後に終わる時刻はどちらも10秒で同じ）
リアルタイムOS（RTOS）のスケジューリング
- RTOS：
  - リアルタイム処理の機能を実装したOS。非同期に起きる複数の要求に、決められた時間内に対応するタスクの処理を終わらせる必要がある制御系の組込みシステムで使う
- リアルタイム処理：
  - 即時処理ともいう。要求が起きたらすぐ処理し、応答時間が一定の範囲内にあることが求められる
- ほとんどのRTOSは、静的優先度ベースのイベントドリブン方式（イベントドリブンプリエンプション方式）を使う
- デッドラインスケジューリング方式：
  - 時間内に処理を終えるために、優先度を動的に決める方式。RTOSで使うこともある
- タスク実行のきっかけは割込み。割込みをトリガにタスク切替えが起きる（例：優先度がA＜Bなら、割込みBが来るとタスクAを中断してタスクBを実行する）
- 割込みハンドラ：
  - 割込み処理ルーチンともいう。割込み信号を受けたのをきっかけに起動されるプログラム
- ハードリアルタイムシステム：
  - 時間内に終わらないと致命的なダメージが出るシステム（例：エアバッグ制御、エンジン制御）

同期制御：他のタスクの合図を待ち合わせる

同期制御：
- 他のタスクと協調しながら処理を進める方法。言い換えると、他のタスクからの合図を待ち合わせる方法
イベントフラグ：
- 16ビットまたは32ビットのビットの集まり。1ビットで1つのイベントの有無（1か0）を表す
- 使うシステムコール：
  - SET（ビットをオン（1）にする）、CLEAR（オフ（0）にする）、WAIT（ビットがオンになるまでタスクを待たせる）
- 例：
  - タスクYとZが WAIT(5) で待つ → タスクXが SET(5) → YとZの待ちが同時に解除されて処理を再開し、次の同期のために CLEAR(5) しておく
- 特徴：
  - 条件が成立したタスクすべての待ち状態を、同時に解除できる
WAIT/POST命令：
- イベントごとに定義するECB（Event Control Block：イベント制御ブロック）を使って同期をとる
- イベントを待つタスクがWAIT命令、イベントの完了を知らせるタスクがPOST命令を出す
- ECBの構成：
  - Wビット：
    - イベント待ちの有無
  - Pビット：
    - イベント完了の有無
  - POSTコード：
    - イベントの詳細（リターンコード）を受け渡す領域
- 動き：
  - WAIT命令：
    - P＝0ならWを1にして待つ。P＝1なら待たずに続ける
  - POST命令：
    - W＝0ならPを1にする。W＝1なら待っているタスクの待ちを解除する
IPC（Inter-Process Communication：プロセス間通信）：
- タスク間でデータをやり取りする通信手段の総称

手段	やり方
共有メモリ	あるタスクが獲得した共有メモリを、他のタスクがマップ（アタッチ）して、両方から読み書きする
メッセージキュー	送信側は取得したキューにメッセージを送り、受信側はキューのIDを指定して受け取る
パイプ機構	ファイルやメモリを経由して、1つのタスクの出力を別のタスクの入力にする。パイプラインともいう

排他制御：共有資源を同時に触らせない

共有資源を同時に更新すると、データが矛盾する
- 例：
  - 在庫数S＝50 を、タスクXとYがそれぞれ「Sを読む → S−1 → Sを書く」で更新する。Xが読んだ直後にYに割り込まれると、Yが49を書き、再開したXも49を書く。正しくは 50−1−1＝48 なのに 49 になる
- 例え：
  - 1冊の共有ノートの残高を、2人が同時に見て、それぞれ書き直すと、片方の書き込みが消える
クリティカルセクション（危険領域）：
- 共有資源を同時に更新すると、データ不整合を起こしてしまう処理部分
排他制御（相互排除ともいう）：
- 「同時には1つのクリティカルセクションの実行しか許さない」仕組み
- 言い換えると、共有資源を使っているタスクにプリエンプションを起こさせない仕組み
割込みマスク（割込みの禁止）：
- プリエンプションを起こさせない一番簡単な方法
- ただし、マルチCPUで別々のCPUで動いているタスクには効かない
TSL（Test and Set Lock）：
- 特殊なハードウェア命令。共有メモリの1ビットをフラグにして、ビジーウェイト方式のロック／アンロックを実現する
- 動き：
  - フラグが0なら1にしてクリティカルセクションに入る。フラグが1なら、0になるまでフラグを繰り返しチェックして待つ
- 補足：
  - マルチCPUシステムでは、名前は違ってもTSLと同じ種類の仕組みが必ず用意されている
スピンロック：
- TSLのように、フラグを繰り返しチェックして待つ方式（"回転"しているように見えるため）
- 長所：
  - クリティカルセクションがごく短いときは有効
- 短所：
  - 待っているタスクが常にフラグをチェックするので、CPU時間を浪費する
セマフォ★：
- ビジーウェイトの問題を解決した排他制御の仕組み。セマフォ変数（フラグの役割）と、それを操作するP操作・V操作でできている
- セマフォ変数：
  - 共有メモリ内の非負整数の変数。1以上なら使える、1より小さい（0）なら使えない
- 待つタスクは待ち行列で眠るので、スピンロックと違ってCPUを浪費しない

操作	条件	動き
P(S)（借りる）	S ≧ 1	Sを1減らし、そのまま実行を続ける
P(S)（借りる）	S ＜ 1	P操作をしたタスクを待ち行列に入れる
V(S)（返す）	待ちタスク数 ≧ 1	待ち行列からタスクを1つ取り出し、実行可能状態にする（Sは増やさない）
V(S)（返す）	待ちタスク数＝ 0	Sを1増やし、そのまま実行を続ける

P操作は資源の専有使用要求（ロック）、V操作は資源の解放（アンロック）にあたる
2つのタスクで1つの資源を排他制御する例：
- セマフォ変数Sの初期値を1にする → クリティカルセクションに入れるのは1つだけ
- Aが P(S)（S：1 → 0）→ Bが P(S)（S＝0なので待ち行列へ）→ Aが V(S)（待ちが1なのでBを実行可能にする。Sは0のまま）→ Bが使い終わって V(S)（待ちが0なのでS：0 → 1）
2値セマフォ：
- 1つの共有資源の排他制御に使う、1か0の2値しかとらないセマフォ。2進セマフォ、バイナリセマフォともいう
ゼネラルセマフォ：
- 最大Nの値をとるセマフォ。計数型セマフォ、カウンティングセマフォともいう
- N個の共有資源を複数のタスクで使うとき、初期値を資源の総数Nにすると、最大N個のタスクが同時に使える
- 例：
  - プリンタが3台あるなら初期値3。3つのタスクがP操作するとS＝0になり、4つ目のタスクは待ち行列に入る
セマフォを使った同期制御
- 生産者／消費者問題（プロデューサ／コンシューマ問題）：
  - 共有メモリ内の有限のバッファでタスク間の通信をするとき、「バッファが空なら消費者は待つ」「バッファが満杯なら生産者は待つ」必要がある、という問題
- 解き方（N個の棚で、生産者タスクから消費者タスクへメッセージを送る）
  - S1＝空いている棚の数（初期値N）、S2＝処理すべきメッセージ数（初期値0）
  - 生産者：
    - メッセージを作る → P(S1)（空き棚を1つもらう）→ 棚に入れる → V(S2)（「1つ入れたよ」と知らせる）
  - 消費者：
    - P(S2)（メッセージを1つもらう。なければ待つ）→ 棚から取り出す → V(S1)（「1つ空いたよ」と知らせる）→ メッセージを処理する
  - この使い方では、V操作を事象の発生通知、P操作を事象の待合せに使っている
  - 次の棚番号：
    - 生産者は（i % N）＋1、消費者は（j % N）＋1（%は剰余演算子。Nの次は1に戻る）
デッドロック★：
- 互いに相手が専有している資源の解放を待ち合って、処理が先に進まなくなる状態
- 例：
  - T1は「R1 → R2」、T2は「R2 → R1」の順に資源を要求する。T1がR1を、T2がR2を確保した時点で、互いに相手の資源を待ち続ける
- 例え：
  - 細い道で2台の車が向かい合い、どちらも「相手が下がるまで動かない」状態
- タスクの実行に複数の共有資源が必要なときに起こりうる（データベースのロックでも起きる）
- ポイント：
  - 資源を要求する順序が同じなら、デッドロックは起きない
デッドロックへの対策
- ①静的防止法：
  - あらかじめ資源の割当て方法を決めておく
- ②動的防止法：
  - デッドロックが起きないよう、資源の割当て状況に応じて動的に割り当てる
- ③検出と回復：
  - デッドロックが起きた時点で該当するタスクを見つけ、そのうち1つを強制終了するなどの対処をする
資源グラフ：
- デッドロックの検出方法の1つ。資源とタスクの関係を有向グラフで表す（T → R は「TがRを要求」、R → T は「RをTが使用中」）
- 完全に簡約化できるかでデッドロックを判断する。簡約化できなければデッドロックがある
- 簡約化：
  - すべての要求を満たせるタスクについて、そのタスクを始点または終点とする辺をすべて消す操作
- 例：
  - ある資源が2つあれば、1つ目のタスクの要求は満たせるのでその辺を消せる → すると2つ目のタスクの要求も満たせる → 完全に簡約化できる（デッドロックなし）
待ちグラフ：
- データベースのトランザクション並行処理で、デッドロックを検出するのに使う
- 「X → Y」は「XはYがロックしている資源の解放を待っている」。グラフが閉路（ぐるっと一周する輪）を持てば、デッドロック状態

プロセスとスレッド：重い並行処理と、軽い並行処理

プロセス：
- タスクの同義語。主にUNIX系OSで使う用語。広い意味では「CPUが実行する1つの処理単位（プログラム）」
- これまでタスクとして説明したことは、プロセスにも当てはまる
- プロセスごとに、スタックとCPUレジスタ群を1セット持つ
スレッド：
- プロセスを細かく分けた並行処理単位
集合の関係：
- 「タスク ⊇ プロセス ⊇ スレッド」。ただし、リアルタイムOSでは「プロセス ⊇ タスク ≒ スレッド」
forkシステムコール：
- プロセスが自分自身をコピーして、子プロセスを作る
- 親プロセス：
  - もとのプロセス
- 子プロセス：
  - 生成されたプロセス
プロセスで並行処理する場合（親が処理A、子が処理B）
- 親と子はそれぞれ独立したアドレス空間で動くので、主記憶の利用効率が悪い
- 親子で協調させるには、同期制御やプロセス間通信が必要
- プロセスの生成には時間がかかる
スレッドで並行処理する場合（スレッド1が処理A、スレッド2が処理B）
- 1つのプロセスの中で、複数のスレッドを動かせる（マルチスレッド）
- スレッドにはCPU資源だけが割り当てられ、その他の資源は親プロセスから受け継いで、プロセス内の他のスレッドと共有する（プロセス内の資源は制限なく使える）
- そのため、軽量プロセスともいう
- スレッドは自分のレジスタとスタックを持ち、共有している1つのプログラムを互いに独立して実行できる
- 長所：
  - 主記憶の利用効率がよい。スレッド間のデータ交換が簡単。生成に時間がかからない（すでにあるプロセスから作るため）
- 注意：
  - スレッド間でも排他制御は必要（同じデータを共有しているから）
- 例え：
  - プロセスは「別々の台所を用意して2人で料理する」、スレッドは「1つの台所で2人が料理する」。台所（メモリ）の節約になるが、同じ包丁を同時に使わないよう譲り合いが要る

混同しやすいペア

ディスパッチ（実行可能 → 実行。CPUをもらう）／プリエンプション（実行 → 実行可能。CPUを取り上げられる）
実行可能状態（CPU待ち）／待ち状態（入出力や合図の待ち）
プリエンプティブ（OSが強制的に切り替えられる）／ノンプリエンプティブ（タスクが自分で返すまで切り替えられない。到着順方式）
イベントドリブン（出来事の割込みで切り替える）／タイムスライス（一定時間ごとに切り替える）
スタベーション（いつまでも実行されない）／エージング（待った分だけ優先度を上げて救う）
ラウンドロビン（全員同じ時間で平等に回す）／フィードバック待ち行列（終わらないたびに優先度を下げ、そのぶん時間は長くする）
SPT（処理時間が短い順）／SRPT（残りの処理時間が短い順）
同期制御（合図を待ち合わせる）／排他制御（同時に触らせない）
スピンロック（ぐるぐる確認して待つ。CPUを浪費）／セマフォ（待ち行列で眠って待つ）
P操作（Sを減らす・借りる・待つ）／V操作（Sを増やす・返す・知らせる）
2値セマフォ（1か0。資源1つ）／ゼネラルセマフォ（最大N。資源N個）
資源グラフ（簡約化できなければデッドロック）／待ちグラフ（閉路があればデッドロック。DB用）
TCB（タスクの情報）／PCB（プロセスの情報）／ECB（イベントの情報）
プロセス（アドレス空間ごと別。重い。fork）／スレッド（アドレス空間を共有。軽い。排他制御は必要）

← 05 ソフトウェアの目次に戻る