プロセス（タスク）管理
• 複数のプログラムを連続して実行させる • 複数のプログラムを同時に実行させる目的：プロセス（プログラム）の効率的な実行
仕事の進め方
仕事1：報告書作成 仕事2：報告書印刷 仕事3：報告書郵送 仕事4：伝票集計 仕事5：企画作成 仕事の内容 印刷機 報告書作成 印刷 郵送 印刷ができるまで待つ 伝票集計 企画作成 仕事の内容 印刷機 報告書作成 印刷 伝票集計 企画作成 郵送 郵送の仕事は待たせておく （1） 単一処理 （2） 多重処理（マルチプログラミング，マルチタスク）プログラムとプロセス
■ プログラム ： 処理手順の静的な記述 ■ プロセス ： データを伴ったプログラムの動的な実行の実体 プログラムA プログラムB ディスク装置 主記憶 ﾌﾟﾛｸﾞﾗﾑBの実行の実体 ﾌﾟﾛｸﾞﾗﾑBの実行の実体 静的な実体（ﾌﾟﾛｸﾞﾗﾑ） は同じでも動的な実体 は異なる ﾌﾟﾛｸﾞﾗﾑAの実行の実体 ﾌﾟﾛｾｽP1 ﾌﾟﾛｾｽP2 ﾌﾟﾛｾｽP3 主記憶 プロセスP1 プロセスP2 プロセスP3 プログラムA プログラムB ディスク装置 PSW レジスタ PC SP PSW レジスタ PC SP PSW レジスタ PC SP PSW レジスタ PC SP 物理CPU 仮想CPUプロセス実行のイメージ
プロセスP1,P2,P3は 時間的に切り替えら れながら実行されるプロセスの状態
■ 実行状態（run） ： プロセッサによりプロセスが実行されている状態 ■ 待ち状態（wait） ： プロセスが入出力などを要求し，入出力動作の 完了を待っている状態 （ ＝ プロセスの実行は中断される） ■ 実行可能状態（ready） ： 資源としてのプロセッサが割り当てられれば， 中断しているプロセスをいつでも再開できる状態 プロセスP1 P2 P3 P4 P5 実行状態 入出力要求 待ち状態 実行可能状態 入出力完了（割込み） 入出力要求 入出力要求 実行状態 待ち状態 実行可能状態 コンテキストスイッチ(1) 実行状態 ： プロセスが実行されている状態 (2) 待ち状態 ： 事象（入出力の動作の完了など）待ちの状態 (3) 実行可能状態 ： プロセッサの割当を待っている状態
プロセスの状態と遷移
実行可能状態 (ready) 実行状態 (run) 待ち状態 (wait) プロセスの生成 ディスパッチ • タイムアウト • 優先度の高いプロ セスの実行要求 事象待ち（入出力要求など） 事象発生 （入出力の完了など） プロセスの消滅 終了 ready queue（待ち行列） P5 P4 P3 P2 P1プロセスの切替え要因
◆ イベントドリブン（event driven；事象駆動） 事象（イベント；システムの状態の変化）が発生したのを契機に，プロセスのスケ ジューリングを実行する方式。マルチプログラミングの実現に必要。 事象が発生するタイミングの例 • 入出力の要求，完了 • マウスのクリック，キーボード入力◆ タイムスライス（time slice；時分割 / time sharing）
システムの状態変化とは無関係に，設定した短い時間（クオンタム）の周期でプ ロセスを切り替える方式。一定時間ごとに割込みを発生させるインターバルタイ マが必要。
プロセスの切替え方式
◆ プリエンプション（preemption） OSが実行中のプロセスを強制的に取り上げることにより，プロセス を中断させる。（WindowsXP,UNIX系OS,MacOS X） ◆ ノンプリエンプション（non-preemption） 実行中のプロセスが入出力を要求する場合など，CPUの使用権をプロセ ス自身が自主的にOSに戻す。（Windows95,MacOS 9） プロセスP1 プロセスP2 プロセスP3 プロセスが自主的に CPUの使用権を戻す プロセスP1 プロセスP2 プロセスP3 プロセス実行中 にエラーが発生 すると，システム 全体が停止して しまう可能性が ある • スケジューラ（scheduler） / ディスパッチャ（dispatcher） • プロセスの状態（run，wait，ready）の管理 • 実行可能状態にあるプロセスの選択 → スケジューリングアルゴリズム • 選択したプロセスを実行させる• プロセスはプロセス制御ブロック（PCB：Process Control Block） と呼ばれるデータ構造によって管理される • プロセス番号 • プロセスの優先度 • 現在のプロセスの状態（実行状態 / 待ち状態 / 実行可能状態） • PC, レジスタ • PSW など
プロセスの管理
OSの管理領域（主記憶内）中 にプロセスごとに格納される1. 到着順（FCFS：First Come First Served）
2. 処理時間順（SPTF：Shortest Processing Time First）
3. 優先度順（PS：Priority Scheduling） 4. ラウンドロビン（Round Robin） 5. 多重レベルスケジューリング 6. 多重レベルフィードバックスケジューリング
◆ 実行可能状態にあるプロセスのどれを実行させるか
を決定する
スケジューリングアルゴリズム
1. 到着順
z 先に到着したプロセスから順に処理を行う（FCFS ： First Come First Served）
・・・ プロセッサ 終了 待ち行列 （queue） 到着順に並ぶ 利点：単純，公平 欠点：長時間実行するプロセスがあると，その後に並ぶプロセス は長時間待たされる（ターンアラウンドタイムTATが大きくなる） 選ばれたプロセスは完了 するまで実行される 例：処理時間 P1:1秒，P2：1秒，P3：1秒，P4：100秒 P1-P2-P3-P4の順にほぼ同時に到着したときの平均TAT：27.25秒 P4-P3-P2-P1の順にほぼ同時に到着したときの平均TAT：101.5秒
到着順
10 5 20 15 10 0 5 10 10 20 A B C D E CPU 時間 到着時刻 プロセス C P U ■-A-B-C-D-E 10 10 25 40 40 ターンアラウンドタイム 到着 A B C D E 10 20 30 40 50 60 A B C,D E 平均 252. 処理時間順
z CPU使用時間の短いプロセスから順に処理を行う ・・・ プロセッサ 終了 待ち行列（queue） 処理時間順に並ぶ 利点：ターンアラウンドタイムの平均時間が最小になる 欠点：実現が困難（あらかじめプロセスの実行時間を知ること は困難） 到着 ⇒ あらかじめユーザに実行時間を登録させる処理時間順
10 5 20 15 10 0 5 10 10 20 A B C D E CPU 時間 到着時刻 プロセス C P U ■-A-B-D-E-C 10 10 50 20 20 ターンアラウンドタイム 到着 A B C D E 10 20 30 40 50 60 A B C,D E 平均 22 ソフトウェア開発技術者試験問題（平成18年度秋期） 問：五つのプロセスA~Eに対して，プロセスの多重度が1で， 処理時間順方式のスケジューリングを適用した場合， ジョブBのターンアラウンドタイムは何秒か。ここで，OSの オーバヘッドは考慮しないものとする。 1 4 E 2 3 D 3 2 C 4 1 B 2 0 A 単独実行時の処理時間 到着時間 プロセス0 1 2 3 4 5 6 7 8 9 10 11 12 A B C D E Bのターンアラウンドタイム：11秒 （到着時刻 1， 終了時刻 12）
3. 優先度順
z プロセスごとに実行の優先度をあらかじめ与える ・・・ プロセッサ 終了 待ち行列（queue） 優先度順に並ぶ 利点：実行効率がよい 欠点：優先度の低いプロセスは待たされる（飢餓状態） →時効果（aging）：待ち時間の長さによって優先度を上げる 優先度の高いプロセスが実行可能となると，実行中 のプロセスが中断される。（プリエンプションの場合） 到着3 2 3 2 1 優先度 10 5 20 15 10 0 5 10 10 20 A B C D E CPU 時間 到着時刻 プロセス 10 10 50 20 20 ターンアラウンドタイム A B C D E 到着 10 20 30 40 50 60 A B C,D E 平均 22
優先度順（ノンプリエンプションの場合）
z 一つのプロセスの実行が終了するまでCPUを割り当てる ※ 優先度は小さい値ほ ど優先度が高いとする C P U 1 ■-E 2 ■-B-D 3 ■-A-C 3 2 3 2 1 優先度 10 5 20 15 10 0 5 10 10 20 A B C D E CPU 時間 到着時刻 プロセス 40 5 50 25 10 ターンアラウンドタイム A B C D E 到着 10 20 30 40 50 60 A B C,D E 平均 26優先度順（プリエンプションの場合）
z 優先度の高いプロセスが到着したら，優先度の高いプ ロセスにCPUを割り当てる ※ 優先度は小さい値ほ ど優先度が高いとする C P U 1 ■-E 2 ■-B-D 3 ■-A-C4. ラウンドロビン
z プロセスを順番に一定時間（クオンタム）ごとに 切り替えて実行する ・・・ プロセッサ 終了 待ち行列（queue） 利点：どのプロセスも公平に実行される 欠点：実行切替えが頻繁になると， オーバーヘッド（overhead：本来の処理以外のために 費やされるコスト（時間））が大きい クオンタム内に終了しないプロセスは待ち 行列の末尾に回される。 到着ラウンドロビン
10 5 20 15 10 0 5 10 10 20 A B C D E CPU 時間 到着時刻 プロセス C P U ■-A-B-C-D-E クオンタム=5とした場合 30 5 50 45 25 ターンアラウンドタイム 到着 A B C D E 10 20 30 40 50 60 A B C,D E 平均 315. 多重レベルスケジューリング
z プロセスの種類をグループに分類し，グループごとに 優先度やスケジューリングアルゴリズムを設定する ・・ ・ プロセッサ 終了 待ち行列1 到着 ・・ ・ 待ち行列2 ・・ ・ 待ち行列n 優先度によって 振分け 各待ち行列でスケジューリングを行う ・・ ・多重レベルスケジューリング
到着順 15 20 0 20 C1 C2 3 C 5 10 40 5 B1 B2 2 B 優先度が同じ場合は ラウンドロビン （クオンタム=5） 10 10 A1 1 A アルゴリズム CPU時間 到着時間 プロセス 優先度 グループ 10 5 20 35 40 ターンアラウンドタイム A1 B1 B2 C1 C2 到着 10 20 30 40 50 60 C1 B2A1 C2 B1 平均 226. 多重レベルフィードバックスケジューリング
• ある待ち行列で一定のプロセッサ時間を使用したプロ セスをより優先度の低い待ち行列に移す ・・ ・ プロセッサ 終了 到着 ・・ ・ ・・ ・ 各待ち行列で一定時間内に終了しないプロセスは 次のレベルの待ち行列の末尾に回される ・・ ・プロセスとスレッド
■ プロセス ：OSから見た処理の実行単位 ■ スレッド（軽量プロセス） ：プロセスを細分化した実行単位 ブラウザソフトでの例 z画像ファイルの受信 z音楽の再生 zユーザ入力の処理 など… 並列に実行される それぞれの処理が一つのスレッドに対応するプロセスとスレッド
■ プロセス ：プロセスごとに独立した主記憶を占める ■ スレッド（軽量プロセス） ：プログラム部は主記憶を共有する 主記憶 ﾌﾟﾛｸﾞﾗﾑA ﾌﾟﾛｸﾞﾗﾑA ﾌﾟﾛｸﾞﾗﾑA ﾌﾟﾛｾｽP1 ﾌﾟﾛｾｽP2 ﾌﾟﾛｾｽP3 ﾌﾟﾛｾｽごと のデータ 主記憶 ﾌﾟﾛｸﾞﾗﾑA スレッドS1 スレッドごと のデータ スレッドS2 スレッドS3 主記憶 OS プロセスA プロセスC PSW レジスタ PC SP PSW レジスタ PC SP PSW レジスタ PC SP 仮想CPUスレッドのイメージ
スレッド スレッド 一つのプロセスが複数の スレッドをもつ場合もあれ ば（マルチスレッド）， 一つのプロセスが一つ のスレッドに対応する 場合もある（シングル スレッド） スレッド基本情報技術者試験問題（平成17年度秋期，平成18年度春期） 問：並行処理の単位として，プロセスのほかに，プロセス内に 複数存在するスレッドを用いることがある。一つのプロセ ス内のすべてのスレッドが共有するものはどれか。 ア 主記憶空間 イ スタック ウ プログラムカウンタの値 エ レジスタセットの値 基本情報技術者試験問題（平成15年度春期） 問：スレッドとは，プロセス内部に含まれている論理的な並列処 理の単位である。スレッドごとに用意されるものはどれか。 ア 主記憶空間 イ 開いているファイル識別子 ウ プロセス間の通信ポート エ レジスタ群の退避域
