Linux 2.6.23 以降
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/18 04:28 UTC 版)
「スケジューリング」の記事における「Linux 2.6.23 以降」の解説
コン・コリバス（英語版）が実装したフェア・シェア・スケジューリング（英語版）方式の "Rotating Staircase Deadline" に触発され、インゴ・モルナーがO(1)スケジューラ（英語版）の代替として Completely Fair Scheduler を開発した。Completely Fair Scheduler (CFS) はパケット通信用に発明された均等化キューイング（英語版）という古典的なスケジューリングアルゴリズムをベースにしている。均等化キューイングはかつて stride scheduling の名でCPUスケジューリング方式として使われたことがある。 CFSスケジューラのスケジューリング複雑性は O(log N) で、この N はランキュー上のタスク数である。タスクの選択は一定時間で行われるが、タスク実行後に再びランキューに挿入する際に O(log N) 回の操作を必要とする。これはランキュー（英語版）が赤黒木で実装されているためである。 汎用OSで均等化キューイングをスケジューラとして実装したのはCFSが最初である。
※この「Linux 2.6.23 以降」の解説は、「スケジューリング」の解説の一部です。
「Linux 2.6.23 以降」を含む「スケジューリング」の記事については、「スケジューリング」の概要を参照ください。
ウィキペディア小見出し辞書の「Linux 2.6.23 以降」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- Linux 2.6.23 以降のページへのリンク
