CPUスケジューリング

Transcription

1 5-6 プロセス管理と CPU スケジューリング 1

2 多重プログラミングの概念 CPU を無駄なく使いたい ジョブ A ジョブ B 開始遊休状態 : 入力 開始遊休状態 : 入力 遊休状態 : 入力 遊休状態 : 入力 停止 停止 図 4.1 二つの上部 A,B の実行 2

3 多重プログラミングの概念 ジョブ A 開始遊休状態 : 入力 遊休状態 : 入力 停止 ジョブ B 待ち 開始遊休状態 : 入力 遊休状態 : 入力 停止 図 4.2 多重プログラミング機構のない場合のジョブ実行 ジョブ A 開始 遊休状態 : 入力 遊休状態 : 入力 停止 ジョブ B 開始遊休状態 : 入力 遊休状態 : 入力 停止 図 4.3 多重プログラミング機構のある場合のジョブ実行 3

4 プロセスとは? 厳密な概念はない! 定義は困難 あえて言うと, プロセスとは下記の 2 つの定義? あり 1) 実行しているプログラム 2) 疑似プロセッサプログラムを実行するための器 その他, ユーザの代理という概念? もあり. OS が管理するための単位 プロセスのことをタスクとも言う. 4

5 プロセスの状態 新規 活動中 停止 待機中 図 4.6 プロセス状態遷移図 新規 実行待ち 実行中 停止 待機中 図 4.7 プロセス状態遷移詳細図 5

6 プロセス制御ブロック (PCB: Process Control Block) プロセスに関する情報を格納しておく器 必要な情報 ( 詳細は OS, ハードウェアによって異なる ) プロセスの状態 新規, 実行待ち, 実行中,... プログラムカウンタ レジスタの内容 レジスタの種類はプロセッサによって異なる. メモリ管理情報 上限 / 下限レジスタ, ページ表 ( ページングシステム ),.. 課金情報 CPU 使用時間, 実使用時間, 課金番号, ジョブ番号,.. 入出力情報 未完了の入出力要求, 割当てられている入出力装置, オープンされているファイル,.. CPU スケジューリング情報 プロセスの優先度, レディキューへのポインタ,... ポインタ プロセス状態 プロセス番号 プログラムカウンタ レジスタ類 記憶範囲 開かれたファイルのリスト 図 4.8 プロセス制御ブロック 6

7 コンテキスト (context) とは? 準備中 7

8 コンテキストスイッチ : プログラムの切り替え 利用者プログラム A オペレーティングシステム 割込みまたはスーパバイザコール 利用者プログラム B 実行状態 レジスタ退避 レジスタ復元 遊休状態 遊休状態 実行状態 実行状態 レジスタ退避 レジスタ復元 割込みまたはスーパバイザコール 遊休状態 図 4.9 利用者間での CPU の切り替え 8

9 スケジューリングのためのキュー (1/2) レディキュー (Ready queue, 実行待ち列 ) 実行可能状態のプロセスをつないでおくキュー デバイスのためのキュー ( デバイスキュー, 装置待ち列 ) 装置が空くのを待っているプロセスのキュー 図 4.10 実行待ち列と種々の入出力装置待ち列 ( 図 : 準備中 ) 9

10 スケジューリングのためのキュー (2/2) 図 4.11 CPU スケジューリングの待ち列図式表現 ( 図 : 準備中 ) 図 4.12 単純化した待ち列図式 ( 図 : 準備中 ) 10

11 スケジューラースケジューラの種類ー 長期スケジューラ (Long term scheduler, ジョブスケジューラ ) システムで処理すべきジョブを選択 複数 ( 多重度 ) のジョブを選択 メモリにロード 短期スケジューラ (short term scheduler,cpu スケジューラ ) 実際に CPU に割当てるジョブを選択 選択するのは 1 つのみ 中期スケジューラ (medium term scheduler)( ない OS もある ) 多重度の制御 プロセスをシステムから取り除く. 図 4.13 中期スケジューリングを加えた待ち列図式 ( 図 : 準備中 ) 11

12 ディスパッチャ (dispatcher) CPU スケジューラで選択されたプロセスに CPU を実際に割当てるプログラムのこと.OS の一部. 仕事 プログラムカウンタの設定, レジスタ内容のロード, ユーザモードへの切り替え,... 12

13 スケジューリングアルゴリズム 評価基準 : 何を目標にするか? CPU 使用率 スループット (throughput) 単位時間当りに完了したジョブ数 ターンアラウンド時間 (turnaround time) ジョブ投入からジョブ完了までにかかった時間 待ち時間 (waiting time) レディキューにいる時間 応答時間 (response time) 会話型システム : コマンド投入からプロンプトが帰ってくるまでの時間 理想 CPU 使用率, スループット 最大 ターンアラウンド時間, 待ち時間, 応答時間 最小 最小値, 最大値, 平均値か? 13

14 スケジューリングアルゴリズムの分類 横取りのない (non-preemptive) アルゴリズム 先着順サービス方式 (FCFS, First-Come-First-Served) 最短ジョブ優先方式 優先度方式 横取りのある (preemtive) アルゴリズム ラウンドロビン (Round-Robin, 巡回方式 ) 多重レベル待ち列 (Multi-queue scheduling) 多重レベルフィードバック列 (Multi-level feedback queue) 14

15 横取りのない (non-preemptive) アルゴリズム 先着順サービス方式 (FCFS, First-Come-First-Served) 最短ジョブ優先方式 優先度方式 15

16 先着順サービス方式 (FCFS, First-Come-First-Served) 到着した順番に実行する. 例 ジョブ バースト時間 時刻 0 でほとんど同時にジョブ 1,2,3 が到着したが, ジョブ 1, ジョブ 2, ジョブ 3 の順で到着した場合 : ガント図 ジョブ1 ジョブ2 ジョブ 平均ターンアラウンド時間 =( )/3 = 27 時刻 0 でほとんど同時にジョブ 1,2,3 が到着したが, ジョブ 2, ジョブ 3, ジョブ 1 の順で到着した場合 : ガント図 ジョブ2 ジョブ3 ジョブ 平均ターンアラウンド時間 =(30+3+6)/3 = 13 16

17 最短ジョブ優先方式 実行時間の短い順に実行する. 理論的に最小の待ち時間を与える. 仮定 : 横取りがない. 例 ジョブ バースト時間 時刻 0 でほとんど同時にジョブ 1,2,3,4 が到着した場合. ガント図 ジョブ2 ジョブ1 ジョブ4 ジョブ 平均ターンアラウンド時間 =( )/4 = 13 17

18 優先度方式 (priority scheduling) プロセスに優先度を付けて, 優先度順に実行する. 18

19 横取りのある (preemtive) アルゴリズム 横取りのある最短ジョブ優先方式 ラウンドロビン (Round-Robin, 巡回方式 ) 多重レベル待ち列 (Multi-queue scheduling) 多重レベルフィードバック列 (Multi-level feedback queue) 19

20 ジョブ 1 横取りのある最短ジョブ優先方式 最小残り時間優先方式 (Shortest-Remaining- Time-First) とも言う. 横取り 例 ジョブ到着時刻バースト時間 ガント図ジョブ2 ジョブ4 ジョブ1 ジョブ 平均ターンアラウンド時間 =((17-0)+(5-1)+(26-2)+(10-3))/4 = 13 横取りのない最短ジョブ優先方式の場合 : 平均ターンアラウンド時間 = 57/4 =

21 ラウンドロビン (Round-Robin, 巡回スケジューリング )(1/3) 一定時間 CPU を割り当てる. 一定時間 : タイムスライス (time-slice, 量子時間 ) 終了しなければ, 次に回す ( レディキューの最後尾につなぐ ) 下記は, タイムスライス =4 の場合のガント図 仮定 : 時刻 0 で, ジョブ 1,2,3 の順で到着 例ジョブ バースト時間 ガント図 ジョブ 2 ジョブ 1 ジョブ 3 ジョブ 1 ジョブ 1 ジョブ 1 ジョブ 1 ジョブ 平均ターンアラウンド時間 =47/3 = 16 タイムスライスについて タイムスライス : FCFS( 先着順サービス ) 0: Processor scharing( プロセッサシェアアリング, プロセッサ共有 ) 21

22 ラウンドロビン (Round-Robin, 巡回スケジューリング )(2/3) 例の追加 ( 右表 ) 下記は, タイムスライス =4 の場合のガント図 仮定 : 時刻 0 で, ジョブ 1,2,3 の順で到着 例ジョブ バースト時間 ガント図 ジョブ1 ジョブ2 ジョブ3 ジョブ1 2 ジョブ3 ジョブ1 ジョブ 平均ターンアラウンド時間 =( )/3 = 77/3 22

23 ラウンドロビン (Round-Robin, 巡回スケジューリング )(3/3) タイムスライスの終了時の処理 プロセスの入れ替え : コンテキストスイッチング (Context switching) コンテキストの入れ替え 古い ( 今実行していた ) プロセスのレジスタ内容を退避 新しいプロセスのレジスタ内容をレジスタにロード オーバヘッドが生じる タイムスライスを短くするとコンテキストのオーバヘッドが大 図 4.16 状態切換えを増加させるより小さな量子時間 ( タイムスライス ) 値 ( 図 : 準備中 ) 23

24 多重レベル待ち列 タイプの異なるジョブ フォアグランドジョブ (foreground, 会話的ジョブ等 ) バックグランドジョブ (background, バッチ等 ) キュー毎に異なるスケジューリングアルゴリズム CPU の割当方法 : 優先度, 時間配分 最高優先度 システムタスク 会話型 編集 バッチ 最高優先度 学生バッチ 図 4.18 多重待ち列スケジューリング方式 24

25 多重レベルフィードバック列 キュー間の移動を許す. 自由度の高いスケジューリング パラメータ キューの数 各キューのスケジューリングアルゴリズム 移動の決定方策 最初に入れるキューの決定方法 パラメータの決定が困難 キュー 0 タイムスライス =8 キュー 1 キュー 2 タイムスライス =16 FCFS 図 4.19 多重レベルフィードバック列 25

26 アルゴリズムの評価手法 解析的評価 決定性モデル ジョブの振る舞いが決定的 確率的モデル ジョブの振る舞いが確率的 待ち行列理論 (Queueing theory) シミュレーション 26