スケジューリング

プロセスやスレッドは極めて短い時間で切り替えながら
実行される。切り替えのタイミングをスケジューラが決める.

プロセスの状態

実行状態

プロセスがまさに実行されている状態である。

ブロック状態

プロセスがI/O待ちなどで実行を中断している状態である。

実行可能状態

同じくプロセスが実行を中断している状態であるが、CPU資源が割り当て
られればすぐに再開することができる状態である。

カーネル内部でプロセスを待機させておくキューをレディキューと呼ぶ

スケジューリングの評価基準

ターンアラウンドザ時間

プロセスの開始から終了までの合計時間

スループット

一般に単位時間あたりの仕事量のこと

応答性

キー入力やクリックといった動作に対する対応

資源の利用効率

スケジューリングの行われるタイミング

• プロセスが自主的にCPUを解放
• 強制的にCPUを横取り

ラウンドロビンスケジューリング

もっと広く用いられているアルゴリズムである。
各プロセスを一定時間連続して実行する。
連続して実行する時間のことをタイムスライスという。
タイムスライスは適切に設定する必要がある。

タイムスライスが小さすぎる場合

コンテキストスイッチが頻繁に起こりすぎるために
スループットおよびターンアラウンドザタイムが悪化する。

タイムスライスが大きすぎる場合

対話的なプロセスが素早く反応しない。

優先度つきスケジューリング

優先度の高いプロセスが実行可能になると優先度の低い
プロセスは実行を停止しする。同じ優先度に対しては
ラウンドロビンを行う。この方法では優先度の高いプロセス
ばかりが実行され、優先度の低いプロセスはスタベーションに
陥りがちである。これを避けるためにエイジングと呼ばれる
手法がある。エイジングは長い間CPUを割り当てられていない
プロセスの優先度を上げていく。

スケジューリングアルゴリズムのメリット・デメリット

• ラウンドロビン

スタベーションが発生しない、実装が容易、レスポンスに問題がある場合も

• 多段フィードバックキュー

UNIXにおけるスケジューリングアルゴリズム
複数のFIFOで構成される。プロセスが自ら資源を明け渡す場合は同じ優先度のキューで再開。
プロセスが終了すれば削除される。タイムクオンタムを使い果たした場合はひとつしたのキューに
つなぎなおされる。最低レベルのプロセスはラウンドロビンで処理される。

• SJF

蓄積実行時間がもっとも長いプロセスが優先される。I/Oバウンドのプロセスの優先度が高くなることになる。