Microsoft PowerPoint - No4.ppt

Transcription

1 プロセス(タスク) 管 理 目 的 :プロセス(プログラム)の 効 率 的 な 実 行 複 数 のプログラムを 連 続 して 実 行 させる 複 数 のプログラムを 同 時 に 実 行 させる 仕 事 の 進 め 方 仕 事 1: 報 告 書 作 成 仕 事 : 報 告 書 印 刷 仕 事 : 報 告 書 郵 送 仕 事 4: 伝 票 集 計 仕 事 : 企 画 作 成 (1) 単 一 処 理 仕 事 の 内 容 報 告 書 作 成 印 刷 ができるまで 待 つ 郵 送 伝 票 集 計 企 画 作 成 印 刷 機 印 刷 () 多 重 処 理 (マルチプログラミング,マルチタスク) 仕 事 の 内 容 報 告 書 作 成 伝 票 集 計 企 画 作 成 郵 送 印 刷 機 印 刷 郵 送 の 仕 事 は 待 たせておく 1

2 プログラムとプロセス プログラム : 処 理 手 順 の 静 的 な 記 述 プロセス : データを 伴 ったプログラムの 動 的 な 実 行 の 実 体 主 記 憶 静 的 な 実 体 (フ ロク ラム) は 同 じでも 動 的 な 実 体 は 異 なる フ ロセスP1 フ ロセスP フ ロク ラムの 実 行 の 実 体 フ ロク ラムの 実 行 の 実 体 プログラム プログラム フ ロセスP フ ロク ラムの 実 行 の 実 体 ディスク 装 置 プロセスP1,P,Pは 時 間 的 に 切 り 替 えら れながら 実 行 される プロセス 実 行 のイメージ 主 記 憶 仮 想 PU PSW レジスタ P SP プロセスP1 物 理 PU PSW レジスタ P SP PSW レジスタ P SP PSW レジスタ P SP プロセスP プロセスP プログラム プログラム ディスク 装 置

3 プロセスの 状 態 実 行 状 態 (run) : プロセッサによりプロセスが 実 行 されている 状 態 待 ち 状 態 (wait) : プロセスが 入 出 力 などを 要 求 し, 入 出 力 動 作 の 完 了 を 待 っている 状 態 ( = プロセスの 実 行 は 中 断 される) 実 行 可 能 状 態 (ready) : 資 源 としてのプロセッサが 割 り 当 てられれば, 中 断 しているプロセスをいつでも 再 開 できる 状 態 プロセスP1 P P 入 出 力 要 求 実 行 状 態 待 ち 状 態 入 出 力 要 求 入 出 力 完 了 ( 割 込 み) 実 行 可 能 状 態 入 出 力 要 求 P4 P 実 行 状 態 待 ち 状 態 実 行 可 能 状 態 コンテキストスイッチ

4 プロセスの 状 態 と 遷 移 終 了 プロセスの 消 滅 タイムアウト 優 先 度 の 高 いプロ セスの 実 行 要 求 実 行 状 態 (run) ディスパッチ 事 象 待 ち( 入 出 力 要 求 など) プロセスの 生 成 実 行 可 能 状 態 (ready) 事 象 発 生 ( 入 出 力 の 完 了 など) 待 ち 状 態 (wait) P1 P P P4 P ready queue( 待 ち 行 列 ) (1) 実 行 状 態 : プロセスが 実 行 されている 状 態 () 待 ち 状 態 : 事 象 ( 入 出 力 の 動 作 の 完 了 など) 待 ちの 状 態 () 実 行 可 能 状 態 : プロセッサの 割 当 を 待 っている 状 態 プロセスの 切 替 え 要 因 イベントドリブン(event driven; 事 象 駆 動 ) 事 象 (イベント;システムの 状 態 の 変 化 )が 発 生 したのを 契 機 に,プロセスのスケ ジューリングを 実 行 する 方 式 マルチプログラミングの 実 現 に 必 要 事 象 が 発 生 するタイミングの 例 入 出 力 の 要 求, 完 了 マウスのクリック,キーボード 入 力 タイムスライス(time slice; 時 分 割 / time sharing) システムの 状 態 変 化 とは 無 関 係 に, 設 定 した 短 い 時 間 (クオンタム)の 周 期 でプ ロセスを 切 り 替 える 方 式 一 定 時 間 ごとに 割 込 みを 発 生 させるインターバルタイ マが 必 要 4

5 プロセスの 切 替 え 方 式 ノンプリエンプション(non-preemption) 実 行 中 のプロセスが 入 出 力 を 要 求 する 場 合 など,PUの 使 用 権 をプロセ ス 自 身 が 自 主 的 にOSに 戻 す (Windows9,MacOS 9) プロセスP1 プロセスP プロセスP プロセスが 自 主 的 に PUの 使 用 権 を 戻 す プリエンプション(preemption) OSが 実 行 中 のプロセスを 強 制 的 に 取 り 上 げることにより,プロセス を 中 断 させる (WindowsXP,UNIX 系 OS,MacOS X) プロセスP1 プロセスP プロセスP プロセス 実 行 中 にエラーが 発 生 すると,システム 全 体 が 停 止 して しまう 可 能 性 が ある プロセスの 管 理 スケジューラ (scheduler) / ディスパッチャ(dispatcher) プロセスの 状 態 (run,wait,ready)の 管 理 実 行 可 能 状 態 にあるプロセスの 選 択 スケジューリングアルゴリズム 選 択 したプロセスを 実 行 させる プロセスはプロセス 制 御 ブロック(P:Process ontrol lock) と 呼 ばれるデータ 構 造 によって 管 理 される プロセス 番 号 プロセスの 優 先 度 現 在 のプロセスの 状 態 ( 実 行 状 態 / 待 ち 状 態 / 実 行 可 能 状 態 ) P, レジスタ PSW など OSの 管 理 領 域 ( 主 記 憶 内 ) 中 にプロセスごとに 格 納 される

6 スケジューリングアルゴリズム 実 行 可 能 状 態 にあるプロセスのどれを 実 行 させるか を 決 定 する 1. 到 着 順 (FFS:First ome First Served). 処 理 時 間 順 (SPTF:Shortest Processing Time First). 優 先 度 順 (PS:Priority Scheduling) 4. ラウンドロビン(Round Robin). 多 重 レベルスケジューリング 6. 多 重 レベルフィードバックスケジューリング 1. 到 着 順 先 に 到 着 したプロセスから 順 に 処 理 を 行 う (FFS : First ome First Served) 待 ち 行 列 (queue) プロセッサ 終 了 利 点 : 単 純, 公 平 到 着 順 に 並 ぶ 選 ばれたプロセスは 完 了 するまで 実 行 される 欠 点 : 長 時 間 実 行 するプロセスがあると,その 後 に 並 ぶプロセス は 長 時 間 待 たされる(ターンアラウンドタイムTTが 大 きくなる) 例 : 処 理 時 間 P1:1 秒,P:1 秒,P:1 秒,P4:0 秒 P1-P-P-P4の 順 にほぼ 同 時 に 到 着 したときの 平 均 TT: 7. 秒 P4-P-P-P1の 順 にほぼ 同 時 に 到 着 したときの 平 均 TT:1. 秒 6

7 到 着 順 プロセス 到 着 時 刻 0 PU 時 間 1 P U 到 着, ターンアラウンドタイム 平 均. 処 理 時 間 順 PU 使 用 時 間 の 短 いプロセスから 順 に 処 理 を 行 う 到 着 待 ち 行 列 (queue) プロセッサ 終 了 処 理 時 間 順 に 並 ぶ 利 点 :ターンアラウンドタイムの 平 均 時 間 が 最 小 になる 欠 点 : 実 現 が 困 難 (あらかじめプロセスの 実 行 時 間 を 知 ること は 困 難 ) あらかじめユーザに 実 行 時 間 を 登 録 させる 7

8 処 理 時 間 順 プロセス 到 着 時 刻 0 PU 時 間 1 P U 到 着, ターンアラウンドタイム 0 平 均 ソフトウェア 開 発 技 術 者 試 験 問 題 ( 平 成 18 年 度 秋 期 ) 問 : 五 つのプロセス~に 対 して,プロセスの 多 重 度 が1で, 処 理 時 間 順 方 式 のスケジューリングを 適 用 した 場 合, ジョブのターンアラウンドタイムは 何 秒 か ここで,OSの オーバヘッドは 考 慮 しないものとする プロセス 到 着 時 間 単 独 実 行 時 の 処 理 時 間 4 1 8

9 のターンアラウンドタイム:11 秒 ( 到 着 時 刻 1, 終 了 時 刻 1). 優 先 度 順 プロセスごとに 実 行 の 優 先 度 をあらかじめ 与 える 到 着 待 ち 行 列 (queue) プロセッサ 終 了 優 先 度 順 に 並 ぶ 優 先 度 の 高 いプロセスが 実 行 可 能 となると, 実 行 中 のプロセスが 中 断 される (プリエンプションの 場 合 ) 利 点 : 実 行 効 率 がよい 欠 点 : 優 先 度 の 低 いプロセスは 待 たされる( 飢 餓 状 態 ) 時 効 果 (aging): 待 ち 時 間 の 長 さによって 優 先 度 を 上 げる 9

10 優 先 度 順 (ノンプリエンプションの 場 合 ) 一 つのプロセスの 実 行 が 終 了 するまでPUを 割 り 当 てる プロセス 到 着 時 刻 0 PU 時 間 1 優 先 度 到 着, 1 P U 1 - 優 先 度 は 小 さい 値 ほ ど 優 先 度 が 高 いとする ターンアラウンドタイム 0 平 均 優 先 度 順 (プリエンプションの 場 合 ) 優 先 度 の 高 いプロセスが 到 着 したら, 優 先 度 の 高 いプ ロセスにPUを 割 り 当 てる プロセス 到 着 時 刻 0 PU 時 間 1 優 先 度 到 着, 1 P U 1 - 優 先 度 は 小 さい 値 ほ ど 優 先 度 が 高 いとする ターンアラウンドタイム 40 0 平 均 6

11 4. ラウンドロビン プロセスを 順 番 に 一 定 時 間 (クオンタム)ごとに 切 り 替 えて 実 行 する 到 着 待 ち 行 列 (queue) プロセッサ 終 了 クオンタム 内 に 終 了 しないプロセスは 待 ち 行 列 の 末 尾 に 回 される 利 点 :どのプロセスも 公 平 に 実 行 される 欠 点 : 実 行 切 替 えが 頻 繁 になると, オーバーヘッド(overhead: 本 来 の 処 理 以 外 のために 費 やされるコスト( 時 間 ))が 大 きい ラウンドロビン プロセス 到 着 時 刻 0 PU 時 間 1 クオンタム=とした 場 合 到 着, P U ターンアラウンドタイム 平 均 1 11

12 . 多 重 レベルスケジューリング プロセスの 種 類 をグループに 分 類 し,グループごとに 優 先 度 やスケジューリングアルゴリズムを 設 定 する 待 ち 行 列 1 到 着 待 ち 行 列 プロセッサ 待 ち 行 列 n 終 了 優 先 度 によって 振 分 け 各 待 ち 行 列 でスケ ジューリングを 行 う 多 重 レベルスケジューリング グループ 優 先 度 1 プロセス 1 1 到 着 時 間 40 PU 時 間 アルゴリズム 優 先 度 が 同 じ 場 合 は ラウンドロビン (クオンタム=) 到 着 順 到 着 ターンアラウンドタイム 40 平 均 1

13 6. 多 重 レベルフィードバックスケジューリング ある 待 ち 行 列 で 一 定 のプロセッサ 時 間 を 使 用 したプロ セスをより 優 先 度 の 低 い 待 ち 行 列 に 移 す 到 着 プロセッサ 終 了 各 待 ち 行 列 で 一 定 時 間 内 に 終 了 しないプロセスは 次 のレベルの 待 ち 行 列 の 末 尾 に 回 される プロセスとスレッド プロセス:OSから 見 た 処 理 の 実 行 単 位 スレッド( 軽 量 プロセス) :プロセスを 細 分 化 した 実 行 単 位 ブラウザソフトでの 例 画 像 ファイルの 受 信 音 楽 の 再 生 ユーザ 入 力 の 処 理 など 並 列 に 実 行 される それぞれの 処 理 が 一 つのスレッドに 対 応 する 1

14 プロセスとスレッド プロセス :プロセスごとに 独 立 した 主 記 憶 を 占 める スレッド( 軽 量 プロセス) :プログラム 部 は 主 記 憶 を 共 有 する 主 記 憶 主 記 憶 フ ロセスP1 フ ロク ラム スレッドS1 フ ロク ラム スレッドS フ ロセスP フ ロク ラム フ ロセスごと のデータ スレッドごと のデータ スレッドS フ ロセスP フ ロク ラム スレッドのイメージ 主 記 憶 仮 想 PU PSW レジスタ P SP PSW レジスタ P SP OS プロセス スレッド スレッド 一 つのプロセスが 複 数 の スレッドをもつ 場 合 もあれ ば(マルチスレッド), PSW レジスタ P SP プロセス スレッド 一 つのプロセスが 一 つ のスレッドに 対 応 する 場 合 もある(シングル スレッド) 14

15 基 本 情 報 技 術 者 試 験 問 題 ( 平 成 17 年 度 秋 期, 平 成 18 年 度 春 期 ) 問 : 並 行 処 理 の 単 位 として,プロセスのほかに,プロセス 内 に 複 数 存 在 するスレッドを 用 いることがある 一 つのプロセ ス 内 のすべてのスレッドが 共 有 するものはどれか ア 主 記 憶 空 間 イ スタック ウ プログラムカウンタの 値 エ レジスタセットの 値 基 本 情 報 技 術 者 試 験 問 題 ( 平 成 1 年 度 春 期 ) 問 :スレッドとは,プロセス 内 部 に 含 まれている 論 理 的 な 並 列 処 理 の 単 位 である スレッドごとに 用 意 されるものはどれか ア 主 記 憶 空 間 イ 開 いているファイル 識 別 子 ウ プロセス 間 の 通 信 ポート エ レジスタ 群 の 退 避 域 1