オペレーティングシステム ~ スケジューリング ~ 山田浩史 hiroshiy @ cc.tuat.ac.jp 2014/06/01 復習 : プロセス 実行状態にあるプログラムのこと プログラムの実行に必要なものをひっくるめて指す テキスト領域 データ領域 スタック領域 CPU のレジスタ値 プログラムカウンタ など OS はプロセス単位で管理する メモリ Hard Disk CPU プロセス execute Excel load EXCEL.EXE プログラム 1
復習 : プロセスとスレッド プロセス : 実行状態にあるプログラム 最低 1 つのスレッドと, メモリ領域, プロセス制御ブロック スレッド : プログラムの実行の流れ スタック, レジスタ,PC 1 スレッドのプロセス複数スレッドのプロセス text data PCB text data PCB registers stack registers registers registers stack stack stack AGENDA スケジューリングについて学ぶ スケジューリングとは スケジューリング例 スケジューリングの尺度 プロセスの状態 2
スケジューリング (Scheduling) プロセスやスレッドに CPU 時間を割り当てること CPU 時間を割り当てる = プロセスやスレッドを CPU 上で動作させる CPU < プロセス数 スレッド数なので,CPU 時間の割り当て方を考える必要がある スケジューリングを行うコンポーネントをスケジューラ (scheduler) と呼ぶ OS の重要な構成要素のひとつ CPU 時間を割り当てる方針 (policy) をスケジューリングポリシーと呼ぶ コンピュータの用途に応じて変える必要がある スケジューラに求められること プロセスやスレッドに 適切 に CPU 時間を割り当てること アプリケーションを効率良く動作させる例 : ウェブブラウザとウィルススキャンを動かす ウェブブラウザ ( 対話的なアプリケーション ) を操作するときに迅速に CPU 時間を割り当てて欲しい すぐに反応しないとイライラする ハードウェアを効率良く使う例 : 演算処理をよく行う (CPU-bound) プロセスと I/O をよく発行する (I/O-bound) プロセスを動かす CPU と I/O デバイスをなるべく同時に使いたい 両プロセスの仕事が完了する時間が早い 3
Question どんな尺度でスケジューリングをしていけばいいのか 自然言語ではいくらでも要求は言える スケジューリングの尺度 (Criteria) ターンアラウンド (Turn around) 時間 プロセスを実行してから終了するまでの時間 スループット (Throughput) 単位時間あたりにこなせる仕事量 1 時間あたり 10 プロセスの処理を完了 10 プロセス / 時 応答性 (Response) 対話的な操作に対する反応時間 資源使用率 (Utilization) コンピュータの資源効率 どれを重要視し どれを犠牲にするかを適切に決める必要あり 万能なスケジューラは存在しない 4
FCFS スケジューリング First-Come First-Served スケジューリング 来た順スケジューリング 実行を依頼された順にプロセスをスケジューリング P1, P2, P3 の順番で実行を依頼されたとすると ラーンアラウンド時間がよくない P2, P3 を先に実行すれば平均ターンアラウンド時間は良くなる 応答性や資源使用率もよくないけど FCFS スケジューリング P1 CPU: 24 P2 CPU: 3 P3 CPU: 3 P1 P2 P3 0 24 27 30 SJF スケジューリング Shortest-job-first スケジューリング 実行時間が短い順スケジューリング この例だと P2,P3 を先に実行した後に P1 を実行 ターンアラウンド時間の問題を解消 実現が難しい プロセスの挙動を予め知る必要がある プロセスの先の挙動を知るのは不可能 予測する手法と組み合わせて使用する SJF スケジューリング P2 P1 CPU: 24 P2 CPU: 3 P3 CPU: 3 P3 0 3 6 30 P1 5
優先度付き (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 P4 0 1 6 16 18 19 飢餓状態 (starvation) とエイジング (aging) 飢餓状態 (starvation): あるプロセスに CPU 時間がいつまでも割り当てられないこと 実行できるのに永遠と実行されない状況 優先度付きスケジューリングでは飢餓状態が起こり得る 次々と優先度の高いプロセスが来ると, 優先度の低いプロセスは実行されない エイジング (Aging): 飢餓状態を回避する手法 長い間 CPU 時間を割り当てられていないプロセスの優先度を徐々に上げる いつかは優先度が最高になり実行される 6
Round-Robin スケジューリング 変わりばんこスケジューリング 各プロセスを一定時間 ( タイムスライスと呼ぶ ) ずつ実行 タイマ割り込みを利用する 第 3 回の授業参照 タイムスライスが過ぎたら, 実行しているプロセスから CPU を横取り (Preemption) する プロセス A プロセス B コンテキストスイッチ コンテキストスイッチ コンテキストスイッチ プロセス C 時間 スケジューリングを実現するために OS はプロセスの 状態 を把握する必要がある どのプロセスを実行しているのか どのプロセスが CPU 時間を割り当て可能か どのプロセスが CPU 時間を割り当てても無駄か 7
プロセスの状態と状態遷移 プロセスの生成 実行可能 (ready) schedule yield, preempt 実行中 (running) CPU の数 中断からの復帰 (resume, unblock) ブロック状態 (blocked, suspended) 中断 (suspend, block) Running Blocked Ready ブロック状態 : CPU を割り当てられてもプロセスが先に進めない状態 I/O の処理を待っている 自主的休眠 (sleep) 他のプロセスとの同期 ( 次週の話 ) など ブロック状態が解消されたら Ready 状態へ I/O 完了 休眠時間経過 同期成立 など 8
Ready Running スケジューラが切り替える Ready 状態のプロセスは待ち行列 (queue) に入っている ランキュー, 実行可能キューなどと呼ばれる ランキューからプロセスを一つ選択して実行する CPU 時間を割り当て,Running 状態にする スケジューラ ランキュー ( ただの queue) 実行可能プロセスの PCB へのポインタが入っている どのプロセスを実行するのか決める CPU Running Ready まだ実行を継続できるのに CPU 時間を手放すとき 自主的に CPU を手放す場合 他のプロセスやスレッドに自主的に譲る Linux には sched_yield() というシステムコールがある スケジューラの都合で強制的に行う場合 あるプロセスが十分長い間, 実行されたと判断したとき, 強制的に他のプロセスに CPU を譲らせる タイムスライスを使い切ったプロセスから, 次のプロセスに CPU を切り替えるとき 9
優先度付き Round-Robin スケジューリング Windows や Linux で使われている それぞれのプロセスは優先度を持つ 優先度の高いプロセスが優先的に実行される 優先度の高いものから Round-Robin でスケジューリング 優先度ごとにキューを設ける 優先度高 優先度の高いキューにあるプロセスから Round- Robin で実行する 優先度中 優先度低 CPU まとめ スケジューリングについて学んだ スケジューリングとは スケジューリングの尺度 ターンアラウンド時間 スループット 応答性 資源使用率 スケジューリングアルゴリズム FCFS,SJF,Priority,Round-Robin, 優先度付き Round-Robin プロセスの状態 Ready 状態,Block 状態,Running 状態 10