OSのおはなし #2 スケジュール

前回は並列処理の基本、プロセスやスレッドについてまとめましたが、今回はどのようにCPUがプロセスやスレッドのReadyキューを効率的に並び替えるかについてまとめていきます。

スケジューラー＆ディスパッチャー

スケジューラーは様々な手法を使い、処理待ちのプロセスのキュー、Readyキューを定期的（≈40ms毎）に並び替えます。ディスパッチャーはキューの一番前にあるプロセスをCPUで処理するために運びます。

スケジュールを組む際、目標とする項目は、①CPUは常に何かを処理しるようにする。②時間内にできるだけ多くのプロセスを処理する。③1つ1つのプロセスの全ての処理ができるだけ早く終わるようにする。④プロセスがキューで待つ時間を最小にする。⑤キューから初めて処理されるまでの時間を最小にする。などがあるが、状況によって何を優先するかは変わる。

例えば、とにかく高速で処理を終わらせたいバッチシステムは③を重要視し、スマホなどの反応速度が重要となるデバイスでは⑤を重要視する。

色々なスケジュール方法

■ First Come First Served

単純にキューに入った順番で処理していく。長く時間がかかるプロセスほど得をしてしまい、待ち時間にばらつきがある。

■ ラウンドロビン

小さい単位q(≈100ms)を設定し、プロセスの処理時間がこれを過ぎると強制的に次のプロセスに交代しキューの最後に戻る。qの値が小さ過ぎるとコンテキストスイッチが頻繁に起きすぎて時間がかかり過ぎる。短いプロセスが得をする仕組み。

■ Shortest Job First

短いプロセスから処理していく。新しく追加されたプロセスが処理中のプロセスよりも短い場合はプリエンプト（強制交代）する。しかし、プロセスの長さは実際に処理するまで分からないため、過去の処理時間から予想する。

■ 優先度スケジュール

プロセスごとに優先度が割り当てられ、優先度別に別のキューに入れられる。CPUは優先度の高いキューにあるプロセスから処理していくが、これでは優先度の低いプロセスが全く処理されない恐れがあるので、全てのキューが少なくともx％の時間は割り当てられるようにする。さらに一定時間を超えてたプロセスの優先度を下げ、I/O待ち（CPUを必要としない）処理が多いプロセスの優先度を上げることで公平性を目指す。

マルチプロセッサーでのスケジュール

 CPUが複数ある場合、一度あるCPUで処理されたプロセスが他のCPUで処理されるとキャッシュがないのでメモリに取りにいく時間がかかる。このためマルチプロセッサーであってもそれぞれのプロセスが処理されるCPUは限られる。

今回はCPUのスケジュールの手法についてまとめました。次回はセキュリティーについてまとめてみます。