Linuxカーネル解読室(11日目)

1. プロセススケジューラの実装
   • カーネル2.4までのプロセススケジューラの構造は単純だった。単一のキューに実行プロセスを突っ込んで、再スケジューリング時に全部の登録キューを検索していた。
     • システムが大規模に鳴るに連れて、オーバーヘッドが大きくなるため、2.6では別の方法が使われている。
   • カーネル2.6では次の通り。
     • 実行優先度ごとにRUNキューを持たせ、プロセスが存在する最も優先度が高いキューの戦闘からプロセスを選択するだけ。計算量はO(1)なので「O(1)スケジューラ」と呼ばれる。
     • RUNキューを2種類もたせている。それぞれactiveキューとexpiredキューと呼ばれる。activeキューは実行可能な実行割り当て時間が残っているプロセスを登録。expiredキューには、実行可能だが割り当て時間を使い切ったものを登録。activeキューを全て使い果たしたら、activeキューとexpiredキューを入れ替える。
     • マルチプロセッサシステムでは、RUNキューはCPU毎に持たせる。

集中力ないなぁ。