05-scheduling.ppt

Size: px

Start display at page:

Download "05-scheduling.ppt"

しょうこますはら
4 years ago
Views:

1 オペレーティングシステム ~ スケジューリング ~ 山田浩史 cc.tuat.ac.jp 2014/06/01 復習 : プロセス実行状態にあるプログラムのことプログラムの実行に必要なものをひっくるめて指すテキスト領域データ領域スタック領域 CPU のレジスタ値プログラムカウンタなど OS はプロセス単位で管理するメモリ Hard Disk CPU プロセス execute Excel load EXCEL.EXE プログラム 1

2 復習 : プロセスとスレッドプロセス : 実行状態にあるプログラム最低 1 つのスレッドと, メモリ領域, プロセス制御ブロックスレッド : プログラムの実行の流れスタック, レジスタ,PC 1 スレッドのプロセス複数スレッドのプロセス text data PCB text data PCB registers stack registers registers registers stack stack stack AGENDA スケジューリングについて学ぶスケジューリングとはスケジューリング例スケジューリングの尺度プロセスの状態 2

3 スケジューリング (Scheduling) プロセスやスレッドに CPU 時間を割り当てること CPU 時間を割り当てる = プロセスやスレッドを CPU 上で動作させる CPU < プロセス数スレッド数なので,CPU 時間の割り当て方を考える必要があるスケジューリングを行うコンポーネントをスケジューラ (scheduler) と呼ぶ OS の重要な構成要素のひとつ CPU 時間を割り当てる方針 (policy) をスケジューリングポリシーと呼ぶコンピュータの用途に応じて変える必要があるスケジューラに求められることプロセスやスレッドに適切に CPU 時間を割り当てることアプリケーションを効率良く動作させる例 : ウェブブラウザとウィルススキャンを動かすウェブブラウザ ( 対話的なアプリケーション ) を操作するときに迅速に CPU 時間を割り当てて欲しいすぐに反応しないとイライラするハードウェアを効率良く使う例 : 演算処理をよく行う (CPU-bound) プロセスと I/O をよく発行する (I/O-bound) プロセスを動かす CPU と I/O デバイスをなるべく同時に使いたい両プロセスの仕事が完了する時間が早い 3

4 Question どんな尺度でスケジューリングをしていけばいいのか自然言語ではいくらでも要求は言えるスケジューリングの尺度 (Criteria) ターンアラウンド (Turn around) 時間プロセスを実行してから終了するまでの時間スループット (Throughput) 単位時間あたりにこなせる仕事量 1 時間あたり 10 プロセスの処理を完了 10 プロセス / 時応答性 (Response) 対話的な操作に対する反応時間資源使用率 (Utilization) コンピュータの資源効率どれを重要視しどれを犠牲にするかを適切に決める必要あり万能なスケジューラは存在しない 4

5 FCFS スケジューリング First-Come First-Served スケジューリング来た順スケジューリング実行を依頼された順にプロセスをスケジューリング P1, P2, P3 の順番で実行を依頼されたとするとラーンアラウンド時間がよくない P2, P3 を先に実行すれば平均ターンアラウンド時間は良くなる応答性や資源使用率もよくないけど FCFS スケジューリング P1 CPU: 24 P2 CPU: 3 P3 CPU: 3 P1 P2 P SJF スケジューリング Shortest-job-first スケジューリング実行時間が短い順スケジューリングこの例だと P2,P3 を先に実行した後に P1 を実行ターンアラウンド時間の問題を解消実現が難しいプロセスの挙動を予め知る必要があるプロセスの先の挙動を知るのは不可能予測する手法と組み合わせて使用する SJF スケジューリング P2 P1 CPU: 24 P2 CPU: 3 P3 CPU: 3 P P1 5

6 優先度付き (Priority) スケジューリング優先度の高いもの順スケジューリングプロセスに優先度を付加する e.g. Linux では nice 値優先度を適切にふればうまくいきそうだがもしあるプロセスより常に優先度の高いプロセスがあったら同じ優先度のものはどうするのか優先度スケジューリング P1,CPU: 10, 優先度 :3 P2,CPU: 1, 優先度 :1 P3,CPU: 2, 優先度 :4 P4,CPU: 1, 優先度 :5 P5,CPU: 5, 優先度 :2 P2 P5 P1 P3 P 飢餓状態 (starvation) とエイジング (aging) 飢餓状態 (starvation): あるプロセスに CPU 時間がいつまでも割り当てられないこと実行できるのに永遠と実行されない状況優先度付きスケジューリングでは飢餓状態が起こり得る次々と優先度の高いプロセスが来ると, 優先度の低いプロセスは実行されないエイジング (Aging): 飢餓状態を回避する手法長い間 CPU 時間を割り当てられていないプロセスの優先度を徐々に上げるいつかは優先度が最高になり実行される 6

7 Round-Robin スケジューリング変わりばんこスケジューリング各プロセスを一定時間 ( タイムスライスと呼ぶ ) ずつ実行タイマ割り込みを利用する第 3 回の授業参照タイムスライスが過ぎたら, 実行しているプロセスから CPU を横取り (Preemption) するプロセス A プロセス B コンテキストスイッチコンテキストスイッチコンテキストスイッチプロセス C 時間スケジューリングを実現するために OS はプロセスの状態を把握する必要があるどのプロセスを実行しているのかどのプロセスが CPU 時間を割り当て可能かどのプロセスが CPU 時間を割り当てても無駄か 7

8 プロセスの状態と状態遷移プロセスの生成実行可能 (ready) schedule yield, preempt 実行中 (running) CPU の数中断からの復帰 (resume, unblock) ブロック状態 (blocked, suspended) 中断 (suspend, block) Running Blocked Ready ブロック状態 : CPU を割り当てられてもプロセスが先に進めない状態 I/O の処理を待っている自主的休眠 (sleep) 他のプロセスとの同期 ( 次週の話 ) などブロック状態が解消されたら Ready 状態へ I/O 完了休眠時間経過同期成立など 8

9 Ready Running スケジューラが切り替える Ready 状態のプロセスは待ち行列 (queue) に入っているランキュー, 実行可能キューなどと呼ばれるランキューからプロセスを一つ選択して実行する CPU 時間を割り当て,Running 状態にするスケジューラランキュー ( ただの queue) 実行可能プロセスの PCB へのポインタが入っているどのプロセスを実行するのか決める CPU Running Ready まだ実行を継続できるのに CPU 時間を手放すとき自主的に CPU を手放す場合他のプロセスやスレッドに自主的に譲る Linux には sched_yield() というシステムコールがあるスケジューラの都合で強制的に行う場合あるプロセスが十分長い間, 実行されたと判断したとき, 強制的に他のプロセスに CPU を譲らせるタイムスライスを使い切ったプロセスから, 次のプロセスに CPU を切り替えるとき 9

10 優先度付き Round-Robin スケジューリング Windows や Linux で使われているそれぞれのプロセスは優先度を持つ優先度の高いプロセスが優先的に実行される優先度の高いものから Round-Robin でスケジューリング優先度ごとにキューを設ける優先度高優先度の高いキューにあるプロセスから Round- Robin で実行する優先度中優先度低 CPU まとめスケジューリングについて学んだスケジューリングとはスケジューリングの尺度ターンアラウンド時間スループット応答性資源使用率スケジューリングアルゴリズム FCFS,SJF,Priority,Round-Robin, 優先度付き Round-Robin プロセスの状態 Ready 状態,Block 状態,Running 状態 10

CPUスケジューリング

CPUスケジューリング 5-6 プロセス管理と CPU スケジューリング 1 多重プログラミングの概念 CPU を無駄なく使いたいジョブ A ジョブ B 開始遊休状態 : 入力開始遊休状態 : 入力遊休状態 : 入力遊休状態 : 入力停止停止図 4.1 二つの上部 A,B の実行 2 多重プログラミングの概念ジョブ A 開始遊休状態 : 入力遊休状態 : 入力停止ジョブ B 待ち開始遊休状態 : 入力