Towards Transparent CPU Scheduling by Joseph T. Meehean

マルチプロセサのスケジューラを扱った博士論文をオンラインで読んだ。

https://research.cs.wisc.edu/adsl/Publications/meehean-thesis11.pdf

OSTEP の第十章の文献リストにあったことに興味を惹かれて、序章を読んだ。全体を読むにはいたっていないが、いつか読むだろうという気がする。皮算用になろうとここに掲げておく。

プロセサの速度が 2003 年にピークを迎えたあと、ハードウェアの関心はプロセサの数を増やすことに向かった。アプリケーションが並列化したのと同様に、 CPU スケジューラも並列化することになった。このときアプリケーションが依存するスケジューラの方針は、必ずしも明らかでないという。既存の文献はシングルプロセッサ時代の知識へと偏る傾向があって、ユーザーも開発者も研究者も、低レイヤのスケジューラにまつわる理解は一様に低い状態にあるのだそうだ。

論文は Linux のもつ 3 つのスケジューラ、 O(1) Scheduler と CFS (Completely Fair Scheduler) と BFS (Brain Fuck Scheduler) について、長所と短所のサマリを提出しているようだ。

大雑把に分類すると、 O(1) と CFS は分散キューを使ういっぽう、 BFS はグローバルキューを使う。

O(1) は Multi-Level Feedback Queue に似た優先度ベースのロジックで、キャッシュとの親和性を強く打ち出す。 CFS はその名のとおり公平性を尊重して、キャッシュの最適化は捨象してランダムにプロセサを割り当てる。 BFS は CFS よりもいっそう公平性を高めているが、キャッシュとの親和性はいちじるしく低い。