オペレーティングシステム 第 回の管理とスケジューリング http://www.info.kindai.ac.jp/os 8 号館 4 階 N-4 内線 5459 takasi-i@info.kindai.ac.jp オペレーティングシステムの主要概念 (process), タスク (task) 実行中のプログラムプログラム実行に必要な情報 プログラムコード, データ, スタック, プログラムカウンタ, スタックポインタ, 汎用レジスタ, 開いているファイル 実行 停止 実行の繰り返し再開時に以前の状況を引き継ぐ必要がある ( タスク ) (Process) CPUのスケジューリング対象となる基本単位 実行中のプログラム : プログラムの活性化された実態 動的な概念 ( 時々刻々と変化するもの ) として把握 = プログラム か? プログラム B 呼び出し プログラム A プログラム B プログラム C プログラムと プログラム A プログラム B プログラム Aを つのまとまりとして見た方が便利左のプログラム B と右のプログラム B は違うものと見た方が便利 の並行処理 並行処理 (concurrent processing) 複数のを ( 見かけ上 ) 同時に実行 一時中断 ユーザにとっては つのが同時に実行されている の並列処理 並列処理 (parallel processing) を分轄して複数ので同時に実行分割 結合 A B C 複数ので高速実行並行処理 並列処理
メモリ の構造 コード領域 ( テキスト領域 ) データ領域 ヒープ スタック ( 駆動レコード ) 共有ライブラリ の構造 コード領域 (code segment), テキスト領域 (text segment) プログラム命令のコード ( 歴史的な理由からテキストと呼ばれている ) データ領域 (data segment) 初期化されたデータ 初期化されていないデータ の構造 の状態 (processor state) ヒープ (heap) プログラム実行時に確保されるメモリ領域 スタック (stack) スタックフレーム (stack frame) 駆動レコード, 活性レコード (activation record) 関数の引数, 関数の局所変数, 前フレームへのポインタ, 関数呼び出しの戻り番地 の状態はレジスタが保持 レジスタ (register) 中央演算装置との間で高速にデータ転送を行うことができる記憶装置 サイズは小さいが非常に高速 プログラムカウンタ フラグレジスタ アキュムレータ スタックレジスタ 割り込みレジスタ の状態 の状態 メモリ 実行中 レジスタ のプログラムカウンタ, フラグレジスタ等 実行中ではない, の状態も保持しておく必要あり 中断時 : レジスタの値を保存再開時 : レジスタの値を復帰メモリ レジスタの退避領域 保存 復帰 レジスタの退避領域 レジスタ 実行中のの状態
レジスタ プログラムカウンタ (program counter) 次に実行する命令の位置 プログラムカウンタ 4 プログラム ( コード領域 ) 0 PUSH PUSH 0 ASSGN REMOVE 4 PUSHI 0 5 COPY 6 LOAD : レジスタ スタックレジスタ (stack register) スタックトップの位置スタック スタックレジスタ 0 0 4 4 no data 5 no data 6 no data : レジスタ フラグレジスタ (flag register) 特定の命令を実行した後に自動的に付与 OF(overflow flag) : 桁あふれ発生 ZF(zero flag) : 演算結果がゼロ SF(sign flag) : 演算結果がマイナスアキュムレータ (accumulator) 論理演算, 四則演算の入力と結果を保持 割り込みレジスタ (interrupt register) 割り込みに必要なデータを保持 記述子 (process descriptor) 制御ブロック (process control block) 記述子 (process descriptor), 制御ブロック (process control block) の状態を格納 記述子 識別子状態スケジューリング情報資源利用情報 記述子 (PCB) 識別子 (process ID) 生成時に付けられる一意な番号の状態 各種レジスタの値スケジューリング情報 の優先度資源利用情報 使用しているメモリ領域へのポインタ 開いているファイルへのポインタ 記述子 (PCB). 次のPCBへのポインタ. 識別子. の状態 4. の優先度 スケジューリング情報 5. コード領域へのポインタ 資源利用情報 6. データ領域へのポインタ 7. スタックへのポインタ 8. プログラムカウンタの退避領域 9. レジスタの退避領域 0. メモリ管理情報. 入出力情報
次のPCBへのポインタ識別子 記述子 (PCB) 記述子 状態スケジューリング情報資源コード領域へのポインタ利用データ領域へのポインタ情報スタックへのポインタ カーネル領域 プログラムコード領域 ( テキスト領域 ) データ領域 ヒープ スタック ( 活性レコード ) 共有ライブラリユーザ領域 記述子 (PCB) 記述子はキューに格納 次のPCBへのポインタ識別子 次のPCBへのポインタ識別子 次のPCBへのポインタ識別子 キューの先頭のから実行される の状態 の状態 実行中 (running) を使用している タイムアウト (timeout) で実行可能へ移行実行可能 (ready) が空くのを待っている ディスパッチ (dispatch) により実行中へ移行ブロック (blocked), 待ち (waiting) ただちにを使うことはできない 入出力待ち, イベント待ち等 起動中の テキストエディタ メーラ ウェブブラウザ 現在ウェブブラウザを使用中 ウェブブラウザ : 実行中テキストエディタ, メーラ : 実行可能 の状態 類似例 : プリンタの場合 実行中 (running) = 印刷中 実行可能 (ready) = 印刷待ち ブロック (blocked) = 紙切れ ディスパッチャ の状態遷移 タイムアウト 実行中 実行可能 実行可能 各の状態を頻繁に遷移することにより見かけ上同時に複数のを実行できる 4
生成 の状態遷移 実行中 実行可能 タイムアウト ( スケジューラ ) ディスパッチ ( スケジューラ ) 終了 IO 完了イベント完了 ( 外部イベント ) ブロック IO 待ちイベント待ち ( 自身 or 外部イベント ) の状態遷移 実行中から実行可能への移行. レジスタの値をメモリの退避領域にコピー. で退避された値を記述子の退避領 域にコピー. 割込みに対応した処理 割込みハンドラ 4. 次に実行するを決定 スケジューラ 5. 5で選択した記述子のレジスタ退避 領域の値をレジスタにコピー 6. プログラムカウンタの示す行からの 実行開始 ディスパッチャ 割込み処理 レジスタ の状態遷移 メモリユーザ領域カーネル領域 5 退避領域 退避領域 4 PCB レジスタの値を退避領域にコピー 退避領域の値を記述子にコピー 割込み処理 の選択 記述子の値をレジスタにコピー (ready queue) 待ちキュー (waiting queue) (ready queue) 実行可能状態ののキュー キューの先頭のから順に実行 優先順位別に複数キューの場合もある待ちキュー (waiting queue) ブロック状態ののキュー 待ち状態が解消されるとへ 実行 先頭 先頭 先頭, 待ちキュー 最後 最後 最後 高優先度 5 7 低優先度 4 待ちキュー 8 6 9 高優先度の先頭のから実行 の先頭のから実行 ディスパッチ 5 7 9 5
の先頭のから実行 の先頭のから実行 5 7 9 5 7 9 には一定時間が割り当てられる タイムアウト タイムアウトしたは再びに加えられる スケジューリング (scheduling) スケジューリング (scheduling) 次にどのを実行するかを決定実行可能状態のこの中のどれを次に実行する? スケジューリングスケジューリングアルゴリズム選択の指標 CPU 利用率 (CPU utilization) CPUの動作時間 / システム稼働時間 スループット (throughput) CPU が単位時間当たりに完了する数 ターンアラウンド時間 (turnarround time) 実行要求から完了するまでの時間 待ち時間 (waiting time) が完了するまでにで待つ時間 応答時間 (response time) 実行要求から応答開始までの時間 スケジューリング 良いスケジューリングアルゴリズム CPU 利用率 最大 スループット 最大 ターンアラウンド時間 最小 待ち時間 最小 応答時間 最小 しかしこれら全てを同時に満たすのは難しい スケジューリングアルゴリズム 実行するの決定の仕方 (first come first service) ラウンドロビン (round robin) 処理時間順 (shortest processing time first) 残余処理時間順 (shortest remaining time first) 優先度順 (priority dispatching) 多重フィードバック (multiple feedback) 6
スケジューリングアルゴリズム (FCFS) (first come first service, FCFS) のに処理 処理中のが終わるまで実行 短所 処理に時間のかかるが他のの実行を妨げる 優先度の高いが先に実行されない スケジューリングアルゴリズム (FCFS) 位 処理時間 0 5 0 0 0 5 5 スケジューリングアルゴリズムラウンドロビン (RR) ラウンドロビン (round robin, RR) のに処理 一定時間が過ぎると処理中のはタイムアウト, キューの末尾へタイムスライス (time slice), 定時間 (time quantum) 多くの場合 /60 sec (6.7ms) 長所 各に公平に時間が割り当てられる短所 が入力待ち等でブロック状態になってもが開放されない スケジューリングアルゴリズム ラウンドロビン (RR) 位 処理時間 ( タイムスライス : 4) 0 5 0 0 4 8 67 7 5 長所 スケジューリングアルゴリズム処理時間順 (SPT) 処理時間順 (shortest processing time first, SPT) の処理時間の短い順に処理 実行可能のと処理時間を比較 処理時間の短いのターンアラウンド時間が改善される短所 処理時間の予測が必要 に割り当てられる時間が不公平 スケジューリングアルゴリズム処理時間順 (SPT) 位 処理時間 0 5 0 0 5 0 5 7
スケジューリングアルゴリズム処理時間順 (SPT) 0 スケジューリングアルゴリズム処理時間順 (SPT) 5 7 9 処理時間 : 0 5 7 9 処理時間 : 5 残り処理時間 : 7 0 5 処理時間 : 5 残り処理時間 : 7 0 新しいが来ると処理時間順に並ぶようにに加える 5 スケジューリングアルゴリズム残余処理時間順 (SRT) 残余処理時間順 (shortest remaining time first, SRT) の残り処理時間の短い順に処理 実行中のと処理時間を比較 長所 処理時間の短いのターンアラウンド時間が改善される短所 処理時間, 残り処理時間の予測が必要 に割り当てられる時間が不公平 処理時間 : 5 残り処理時間 : スケジューリングアルゴリズム残余処理時間順 (SRT) 5 7 9 7 0 5 0 処理時間 : 0 スケジューリングアルゴリズム残余処理時間順 (SRT) 5 7 9 スケジューリングアルゴリズム処理時間順と残余処理時間順 位 到着時刻 処理時間 0 5 5 5 0 5 処理時間 : 残り処理時間 : 7 0 5 新しいが実行中のよりも処理時間が短いならば実行中のと入れ替える 0 5 0 5 SPT SRT 到着 到着 到着 0 5 0 5 8
スケジューリングアルゴリズム優先度順 優先度順 (priority dispatching) 各に優先度を割り当て 優先度の高いものから処理 デバイスハンドラ, 処理時間の短い, 重要なの優先度を高くする長所 優先度の高いが先に処理される短所 優先度の低いが無限に待たされる可能性 に割り当てられる時間が不公平 スケジューリングアルゴリズム優先度順 位 処理時間 優先順位 0 5 5 0 9 0 0 5 5 スケジューリングアルゴリズム優先度順 0 スケジューリングアルゴリズム優先度順 5 7 9 優先度 : 5 0 5 7 9 優先度 : 8 0 8 優先度 : 8 5 0 新しいが来ると優先度順に並ぶようにに加える 8 ( 実行中のと入れ替える場合もある ) スケジューリングアルゴリズム多重フィードバック多重フィードバック (multiple feedback) キューを多重化し 優先度の高いキューから先に実行する 新しく到着した 優先度の高いキューに 一度処理してタイムアウトした 優先度の低いキューに長所 優先度の高いが先に処理される短所 優先度の低いが無限に待たされる可能性 タイムアウト スケジューリングアルゴリズム 多重フィードバック 高優先度 中優先度 低優先度 新しいは高優先度キューへ タイムアウトしたは優先度の低いキューへ 9
スケジューリングアルゴリズム多重フィードバック 高優先度 タイムスライス : 短 中優先度 タイムスライス : 中 低優先度 タイムスライス : 長 優先度の低いキューほどタイムスライスが長い スケジューリング例 スケジューリングの例 処理時間 0 5 0 は以下の6 通り このをで処理すると? 処理時間 0 5 0 スケジューリングの例の場合 処理時間 0 5 0 スケジューリングの例の場合,,,,,,,,,,,, 番目 番目 番目 TA プロ 開 終 プロ 開 終 プロ 開 終 セス 始 了セス 始 了セス 始 了 平均 0 0 0 5 5 5 0 0 0 0 0 0 5 5 0 5 5 5 5 5 8 0 5 5 5 5 5 0 0 0 0 0 0 0 5 0 5 5 5 8 7 TA 平均,, 0,, 5,, 8,,,, 8,, 7 は 処理時間が短いが先に来ると TA 時間が短くなるが 処理時間が長いが先に来るとTA 時間が長くなる 処理時間 0 5 0,,,,,,,,,,,, スケジューリングの例処理時間順の場合 番目 番目 番目 TA プロ 開 終 プロ 開 終 プロ 開 終 セス 始 了セス 始 了セス 始 了 0 5 5 5 5 5 平均 8 処理時間 0 5 0 スケジューリングの例ラウンドロビンの場合 の順で到着した場合 ( タイムスライス : 4) 平均 TA 時間 : 5 0 4 8 67 7 7 5 の順で到着した場合 0 4 8 6 0 57 平均 TA 時間 : 8 5 0
処理時間 0 5 0 スケジューリングの例 平均 TA 時間 処理時間順ラウンドロビンン,, 0 8 5,, 5 8 6,, 8 8 4,, 8 5,, 8 8 8,, 7 8 6 スケジューリング横取り (preemption) 横取り (preemption) を他のから奪い取ること横取り可能 (preemptive) が実行中のを中断して他のを実行できる横取り不可能 (non-preemptive) が終了するまで他のは実行できない スケジューリング横取り (preemption) スケジューリング法横取り 横取り不可能 ラウンドロビン 横取り可能 処理時間順 横取り不可能 残余処理時間順 横取り可能 優先度順 どちらも可 多重フィードバック 横取り可能 まとめ記述子 記述子 の管理を行う 識別子 の状態 スケジューリング情報 資源利用情報 カーネル領域に置かれる 処理順にキューに格納される 生成 で処理中 まとめの状態遷移 の空き待ち 実行可能タイムアウト ( スケジューラ ) IO 完了 ディスパッチ ( スケジューラ ) イベント完了 ( 外部イベント ) まとめスケジューリング スケジューリング法長所短所横取り 公平簡単 処理時間を無視優先順位を無視 ラウンドロビン公平優先順位を無視 処理時間順 残余処理時間順 平均処理時間が短い 処理時間の予測が必要長い処理は待たされる 終了 実行中 ブロック IO 待ちイベント待ち実行不可 ( 自身 or 外部イベント ) 優先度順高優先度は早く処理低優先度は待たされる 多重フィードバック高優先度は早く処理低優先度は待たされる