- kernel2.6では、"O(1)スケジューラ"というスケジューラが採用されている
- kernel2.4まで使用されていたスケジューラでは、process数の増加に伴ってスケジューラ自身のオーバーヘッドなどによりパフォーマンスの低下が発生することが指摘されていた
O(1)スケジューラの"特徴"
- O(1)スケジューラは、優先度スケジューリングアルゴリズムの改良版
- O(1)スケジューラでは、タイムスライスを使用してprocessのステータスを詳細に管理している
- active：実行待ち状態のprocessのうち、タイムスライスが残っているprocess群
- expired：実行待ち状態のprocessのうち、タイムスライスを使い果たしているprocess群
- active processに対して、スケジューラはCPUリソースを割り当て処理を実行していく
- 割り当てられているタイムスライスを使い果たしたprocessはactiveからexpiredに移行する
- activeからexpiredに移行する際に、processにはタイムスライスが再度割り当てられる
- expired processに対してはスケジューラはCPUリソースの割り当てを行わない
- すべてのactive processがタイムスライスを使い果たし、active processがない状態となると、スケジューラはすべてのexpired processをactive processに変更する
- activeとexpiredを切り替えることによって、特定のprocessだけがCPUリソースを占有的に割り当てられる状況が発生することを防止する
O(1)スケジューラの"構造"
- 実行待ちprocessは"run queue"により管理され、run queueは"active queue"と"expired queue"に分類される
- active queue、expired queueそれぞれには、さらに複数の優先度ごとのqueueに分けられている
- スケジューラは単純にactive queueのなかの優先度の高いqueueの先頭から処理を実行していけばよい
- 実行されているprocessが増加しても、実行processの選択に必要な処理時間に増加は発生しない構造になっている
- queueはCPUごとに用意され、CPUごとにprocessのスケジューリングが行われる
