前文：
- O（1）スケジューラ -要するに、スケジューラポリシーは非常に単純でした。各CPUには2つのキューがありました。1つには間もなく起動されるタスクがあり、もう1つにはスリープタスクがあります。 最初のステージが空になったとき、2番目のステージでそれぞれ場所を変更しました。2番目のステージでは、すべてのスリーププロセスが「起動」し、最初の段階では使い果たされたプロセスとスリーププロセスのキューとして機能しました。 したがって、アルゴリズムの実行時間は、第一に、プロセスのクラスに依存せず、第二に、常にO（1）です。
- 完全に公平なスケジューラ - 赤黒ツリーを使用してプロセスを保存します。 キーは各プロセスのwait_runtimeです 。 wait_runtimeは、特定のプロセスが失敗またはリワークしたナノ秒数です。 つまり <0の場合は処理され、> 0の場合は処理されません。 この方法により、「理想的なケース」からアウトオブバランスを検出できます。 wait_runtimeの値に応じて、プロセスはツリー内でその位置を占めます。 wait_runtime <0の場合、プロセスは0よりも大きい場合はより低いレベルに、その後は最上部に近いレベルにとどまると思います。 したがって、CFSはO（1）スケジューラーではなく、 O（logN）です。
アンブル：
bsdのULEスケジューラの作成者であるJeff Roberson が CFSについてどのようにコメントしているかについて、誰かがスラッシュドットに関する記事を見たかもしれません。
| 数百または数千の実行中のスレッドで作業していると想像してください。lognバイパスの場合のキャッシュミスは非常に高価になる可能性があります。 特に、非常に多くのスレッドを使用してはるかに多くのスケジューリングイベントが発生するため |
実際、次のプロセスをツリーから抽出するには、再調整が必要になる場合があります。プロセスをツリーに挿入するには、単一のポリラインと再調整が必要になる場合があります。 しかし、この欠点は、 非常に大きな nでのみ現れます。これは、デスクトップではほとんど見られませんが、大きなワークステーションでは見られます。 ここから結論づけることができます：多数の同時実行プロセス/スレッドで動作するように設計された、ロードされたサーバー/ワークステーションおよび他のマシンにこのスケジューラをインストールすることは価値がありません。
しかし、この欠陥は次のように現れます。
| Ingoによれば、実行中のタスク（タスク-プロセスまたはスレッド）が1000個あるため、システムはコンテキストスイッチング （ コンテキストスイッチング ）のコストを20％増加させます。 これは10レベルのツリーです。 最悪の場合、さらに5つのレベルが追加され、値が30％増加する可能性があります。 致命的ではありませんが、良い行動とも呼ばれません。 |
O（1）スケジューラーの短所は、不十分で適切な「公平な」コアリバランスに起因します。 Ingo自身がこのコメントで言っていることは次のとおりです。
| これを説明する最も簡単な方法は、簡単な例を使用することです。glxgearsを自分で実行すると、CPUの正確に50％を使用します。 SDスケジューラー（別名O（1）スケジューラー）を使用し、glxgearsとともにCPUホグを実行すると、両方のタスクがCPUリソースを共有します。 CPUホグはプロセッサ時間の約60％を取得し、glxgearsは40％を取得します。 CFSを使用すると、両方のタスクにプロセッサ時間の50％が割り当てられます。 |
CFSは、CPU時間をより適切に割り当て、コアの周りにタスクを分散します（個人的な実践によって証明されています）。
また、CFSの利点には、O（1）よりも応答時間が大幅に短いことが含まれます。 これは、Michael Piatrowskiによるテストで確認されています。 ここで結果を参照してください 。 したがって、CFSはデスクトップ上に安全にインストールでき、同時に実行されるプロセスの数は膨大です。
CFSの配置方法：
まず、CFSはバージョン2.6.20以降のカーネルで使用できます。
カーネルバージョン> = 2.6.20のパッチはこちらから入手できます 。
次に、Linuxソースがあるディレクトリに移動して、パッチを適用します。
| ＃patch -p1 <sched-cfs-v2.6.2x.1-x.patch |
また、CFSスケジューラーの開発用に別のgitリポジトリーが割り当てられています。 ここからリポジトリのクローンを取得できます 。
ULEについてのfw：
各CPUには、優先度によってインデックスが付けられた3つのキューがあります。 2つのキューは、割り込み、リアルタイム、タイムシェアリングなどのスケジューリングクラスを実装するために使用されます。 最後のキューは、アイドルクラスに使用されます。
キュースイッチングポリシーはO（1）shcedulerに似ています。 1つの行が空の場合、すぐに別の行に置き換えられます。 したがって、切り替え時間はプロセスのクラスに依存しません。
Jeffによると、ULEはSMPシステム上で柔軟かつ効果的なポリシーを使用し、CPU間でタスクを分散しています（cit。）「少なくとも完全に公平なスケジューラよりも公平です」。
ULEの詳細： ULE.pdfおよびこちら 。
実際、それはこのブログの最初のテストノートでした。 ここから読む人のためのいくつかの質問があります：CFSの実装についてもっと（もっと）もっと詳しく知りたいですか？将来英語のメモの文脈に挿入された引用を翻訳する価値がありますか？
ご清聴ありがとうございました。