図1 O（1）スケジューラの仕組み。プロセスが登録されているアクティブ・キューの中で最も高い優先度のキューの先頭から，実行するプロセスを選択します。
[画像のクリックで拡大表示]
カーネル2.6で実装されたプロセス・スケジューラ（プロセスの実行順序を決めるための仕組み）です。
Linuxでは，同時に実行しなければならないプロセスを「アクティブ・キュー」に登録します。そして，登録したプロセスの中から，優先度の高い順に実行します。
カーネル2.4では，アクティブ・キューを1つしか持たず，すべてのプロセスをそのキューに登録していました。そのため，最も優先度の高いプロセスを見つけ出すにはキュー内をすべて調べなければならず，キュー内にプロセスが数多く存在すれば，それだけ処理時間が多くかかります。結果として，プロセスの実行速度が遅くなるわけです。
カーネル2.6では，優先度によって分けられたアクティブ・キューを複数持ちます。プロセスは優先度によって分けられてキューに登録されるため，最も優先度の高いプロセスを見つけ出すことは簡単です。優先度の高いアクティブ・キューから登録されているプロセスを選ぶだけです（図1）。
このような仕組みなら，同時に実行しなければならないプロセスが数多く存在しても処理性能は変わりません。ちなみに，実行するプロセスが必ず一つに決まるので処理時間がいつも一定なことから，O記法に基づいて，「O（1）」（Order One）と呼ばれています。
