タスクスケジューリング

概要

解説 OSがプログラム実行のスケジュールを立て、各プログラムにシステム資源を割り当てたり、剥奪して別のプログラムに切り替えたりする仕組みを指す。広義には、プログラムの起動や終了を制御する長期スケジューリング、仮想記憶のページ入れ替えを制御する中期スケジューリング、CPU実行時間を割り振る短期スケジューリングなどの種類があるが、通常は最後のCPU時間の制御を指すことが多い。

短期スケジューリングはCPUスケジューリングとも呼ばれ、マルチタスクOSに実装されている。同時に実行状態にある複数のプログラム（タスクやプロセスと呼ばれる）に対して、CPUの実行時間を割り当て、実行プログラムを順繰りに切り替えていくことにより、あたかも並列に実行しているかのように制御する。

どのような方針や基準に基づいて割り当てや切り替えを行うかを「スケジューリングアルゴリズム」と呼び、様々な方式が考案されている。基本的な方式として「ラウンドロビン方式」「先着順方式」「優先度準方式」があり、マルチプロセッサやマルチコアプロセッサの場合にはどのプロセッサに割り当てるか（アフィニティ）も加味した方式が用いられる。

先着順方式 (FCFS：First-Come First-Served)

最も単純な方式で、実行待ちプロセスの待ち行列（キュー）を用意し、最初に登録したプロセスから順に実行していく方式である。キューの処理方式を表すFIFO（First-In First-Out）方式とも呼ばれる。切り替えにかかるオーバーヘッドが小さく公平に処理を進められるが、処理の長いプロセスがあると性能が悪化する。

ラウンドロビン方式

CPUの実行時間を均等な長さの「タイムスライス」（タイムクォンタム）に分割し、実行待ちプロセスに対して順繰りに割り当てていく方式である。各プロセスは決まった時間だけCPUを利用すると処理が中断され、処理が終わっていなれければ待ち行列の最後尾に並び直して次回の割り当てを待つ。処理時間を公平に割り当てられるが、タイムスライスが短いとプロセス切り替えが頻繁に生じオーバーヘッドが大きくなる。

優先度順方式

各プロセスに優先度を設定し、優先度の高いプロセスは待ち行列内での順位を他のプロセスより優遇する割り当て方式である。重要な処理を優先的に進めることができるが、単純な実装の場合、高優先度のプロセスが途切れずに処理を行うと低優先度のプロセスがまったく実行されないリソーススタベーションを引き起こすことがあるため、優先度に関わらす最低限の割り当てを行う工夫が求められる。