スケジューリング
コンピューター・システムがマルチプログラミングされている場合、通常、複数のプロセスやスレッドが同時にCPUを奪い合うことになり、2つ以上のプロセスが準備状態にあるたびにこのようなことが起こります。利用可能なCPUが1つしかない場合、次に実行するプロセスを選択しなければなりません。選択作業を行うOSの部分はスケジューラと呼ばれ、すべてのアルゴリズムによるスケジューリングアルゴリズムを変更します。
スケジューリング入門
ウェブサーバーでは、複数のプロセスがCPUを奪い合うことが多いため、スケジューリング機能が再び重要になります。モバイル機器ではバッテリーがボトルネックになります。
さらに、実行するプロセスを正しく選択するために、スケジューラはCPUの使用率も考慮しなければなりません。
プロセスの動作
ほとんどすべてのプロセスは、IO要求と計算を交互に繰り返します。通常、CPUは一定時間無停止で動作し、その後、ファイルを読み書きするためのシステムコールを発行します。システムコールの完了後、CPUは計算を続けます。
一般に、CPUが高速になるにつれて、プロセスはよりIO集約的になる傾向があります。
スケジューリングのタイミング
スケジューリング処理に関する最初の重要な問題は、いつスケジューリングを決定するかということです。スケジューリングを必要とするシナリオは様々です。
- 新しいプロセスを作成した後、子プロセスと親プロセスのどちらを先に実行するか。どちらのプロセスもレディ状態なので、これは通常のスケジューリングの決定です。つまり、スケジューラは親プロセスと子プロセスのどちらを先に実行するかを合法的に選択することができます。
- プロセスが終了すると、スケジューリングの決定をしなければなりません。プロセスはもはや実行されていないので、レディ・プロセスのセットから別のプロセスを選択しなければなりません。準備の整ったプロセスがない場合、システムは通常、システムが提供するアイド ル・プロセスを実行します。
- プロセスがIOやセマフォでブロックしたり、他の理由でブロックしたりする場合、 他のプロセスを選択して実行する必要があります。時には、ブロックの理由が選択に影響することもあります。
- IO割り込みでは、スケジューリングの決定をしなければなりません。IOデバイスからの割り込みで、そのデバイスの処理が終了している場合、そのIOを 待っているブロックされたプロセスが実行可能なプロセスになります。
ハードウェアクロックが50Hz、60Hz、またはその他の周波数で周期的な割り込みを提供する場合、スケジューリング決定はk回のクロック割り込みごとに行うことができます。クロック割り込みを扱う場合、スケジューリングアルゴリズムはノンプリエンプティブとプリエンプティブの2つに分類できます。
- ノンプリエンプティブなスケジューリングアルゴリズムは、プロセスを選択し、そのプロセスがブロックされるまで実行するか、プロセスが自動的にCPUを解放します。
- プリエンプティブ・スケジューリング・アルゴリズムは、あるプロセスを選択し、そのプロセスをある固定時間の最大値だけ実行させます。その期間が終了し、プロセスが実行を投げた場合、そのプロセスはハングし、スケジューラは実行する別のプロセスを選びます。
スケジューリングアルゴリズムの分類
異なる環境では、異なるスケジューリング・アルゴリズムが必要です。このような状況は、アプリケーションの領域が異なるために発生します。
- バッチ処理:バッチシステムでは、一般に、短いリクエストに対する迅速な応答を求めて端末のそばでせっかちに待っているユーザーはいません。したがって、各プロセスが長い先取り期間を持つノンプリエンプティブアルゴリズムは、通過しても構いません。
- Interactive:先取りは、あるプロセスがCPUを占有し、他のプロセスへのサービスを拒否することを避けるために必要です。たとえどのプロセスも永久に実行したくないとしても、プログラムのエラーによって、あるプロセスが他のすべてのプロセスを無制限に排除することは可能です。
スケジューリングアルゴリズムの目標
どのような状況においても公平性は重要です。同じようなプロセスは同じように処理されるべきです。もう1つの目標は、システムのすべての部分をできるだけ忙しくしておくことです。バッチシステムでは、CPUに負荷のかかるものとIOに負荷のかかるものを別々に走らせるよりも、両方を走らせた方がよい。
バッチジョブを実行するためのインジケータ。
- スループット・レート（1時間に完了するジョブ数
- ターンアラウンド・タイム（業務開始から完了までの平均時間
- CPU
双方向システムにとって最も重要なのは、応答時間です。
バッチシステムにおけるスケジューリング
早い者勝ち
すべてのスケジューリングアルゴリズムの中で最も単純なものは、ノンプリエンプティブな先着順です。このアルゴリズムでは、プロセスは要求された順番にCPUを使用します。 基本的に、時系列順に実行される準備完了プロセスの待ち行列は1つです。他のジョブが実行されると、それらはレディキューの最後尾に追いやられます。実行中のプロセスがブロックされると、レディキューの最初のプロセスが次に実行されます。ブロックされたプロセスが再開すると、あたかも新しく到着したジョブのように、レディキューの最後に置かれます。
利点:
つかみやすい
デメリット:
リカバリーでブロックされると、キューの最後尾に戻らなければならないため、計算集約型には適していますが、IO集約型には適していません。
最短ジョブ優先
最短CPU実行時間優先スケジューリングアルゴリズムで、レディキューをひとまとめにして、CPUの実行期間が最短のプロセスを選択し、CPUに割り当てます。
利点:
優れたスケジューリング性能、CPUのフル活用
デメリット:
CPUの次の実行サイクルを正確に知ることは難しく、各プロセスの実行履歴から予測するしかありません。
インタラクティブ・システムにおけるスケジューリング
ローテーションスケジューリング
公平性を保つために最もシンプルで広く使われているのが、ローテーション・スケジューリングです。各プロセスにはタイムスライスと呼ばれる時間帯が割り当てられます。タイムスライスが終了すると、CPU が奪われ、別のプロセスに割り当てられます。タイムスライスが終了する前にプロセスがブロックしたり終了したりすると、CPUは直ちに切り替わります。
タイムスライスの長さは適度であるべきで、長すぎても短すぎま す。短すぎるとプロセスの切り替えが多くなり、長すぎるとリクエストの回転が遅くなります。
利点:
真の意味での公平性
デメリット:
航空機システムのように、あるプロセスをすぐに実行する必要がある場合、航空機は着陸を行います。また、タイムスライスが割り当てられるのを待つ必要があります。
優先度スケジューリング
各プロセスには優先順位が与えられ、実行可能なプロセスの中で最も優先順位の高いものが最初に実行されます。
優先順位は動的に決定することができます。たとえば、あるプロセスがIOを多用し、IOの終了を待つのにほとんどの時間を費やすような場合です。そのようなプロセスが CPU を必要とする場合、次の IO 要求を開始するために、すぐに CPU を割り当てるべきです。
利点
優先順位の高い、または重要なプロセスが最初にCPUを使用することは可能です。
デメリット
優先度の低いプロセスが飢餓状態になる可能性
マルチレベルキュー
マルチレベルフィードバックキューアプローチは、システム内に複数のレディキューを設定し、それぞれのキューに異なる優先順位を与えるというものです。
優先度スケジューリングは、プロセスの切り替え回数を減らすために、シナリオごとに異なるタイムスライスを与えるように改良されました。しかし、優先順位の低いプロセス
戦略とメカニズム
上記のスケジューリングアルゴリズムは、いずれもユーザープロセスからスケジューリング決定に関する情報を受け取らないため、スケジューラが最適な選択をすることはほとんどありません。
この問題の解決策は、スケジューリング・メカニズムとスケジューリング・ポリシーを分離するという一貫した原則です。つまり、スケジューリングアルゴリズムを何らかの形でパラメータ化し、そのパラメータはユーザープロセスによって埋められるようにします。カーネルが優先度スケジューリングアルゴリズムを使用し、優先度を設定するために使用できるコールを提供するとします。この方法では、親プロセスはスケジューリングに関与しませんが、子プロセスのスケジューリング方法の詳細を制御することができます。ここでは、スケジューリングメカニズムはカーネルに存在し、スケジューリングポリシーはユーザープロセスによって決定されます。ポリシーとメカニズムの分離は重要なアイデアです。
スレッドスケジューリング
複数のプロセスが複数のスレッドを持つ場合、プロセスとスレッドという2つの並列レベルが存在します。このような場合、ユーザスレッドとカーネルレベルスレッドのどちらをサポートするかによって、スケジューリングの処理方法に根本的な違いがあります。
まず、ユーザーレベルのスレッドについて考えてみましょう。カーネルはスレッドの存在を知らないので、カーネルはこれまでと同じように、プロセスを選択し、それをAと仮定して、Aのタイムスライスの制御を与えます。このスレッドはプロセスのタイムスライス全体にわたって実行され、カーネルは実行する別のプロセスを選択します。
実行する特定のスレッドを選択するカーネルレベルのスレッド処理で、スレッドがどのプロセスに属するかを考慮する必要はありません。選択されたスレッドにはタイムスライスが与えられます。
ユーザーレベルのスレッドとカーネルレベルのスレッドの違いはパフォーマンスです。ユーザーレベルのスレッド切り替えは少数のマシン命令で済みますが、カーネルスレッドはコンテキストスライスを行い、メモリイメージを変更し、テルテールキャッシュを無効にする必要があり、その結果レイテンシが桁違いになります。
カーネル・プロセスの切り替えは、プロセス間の関係に基づいて考慮されます。例えば、プロセス A のスレッドからプロセス B のスレッドへの切り替えは、プロセス A の別のスレッドへの切り替えよりも効果的であってはなりません。
一般に、アプリケーション用にカスタマイズされたスレッドスケジューラは、カーネルよりも高いレベルでアプリケーションのニーズを満たすことができます。その主な理由は、カーネル自体が各スレッドのアプリケーションを理解していないからです。
LinuxLinuxのプロセススケジューラ
Linuxはカーネル2.6以降、プロセススケジューラとしてCFSを採用しています。CFSでは、O(1)とO(n)のスケジューリングアルゴリズムが使われています。どちらのアルゴリズムも、基本的な考え方は、一連の運用指標を通じてプロセスの優先度を決定し、プロセスの優先度に応じてスケジューリングするというものです。一方、CFS は優先度の計算を行わず、プロセスが消費する CPU 時間を計算することで、誰をスケジューリングするかを決定し、公平性を実現しています。
絶対的な公平性
cfsは、新しいモデルを定義し、基本的な考え方は非常に簡単です、彼はリソースとしてCPUを扱い、リソースを変更するには、各プロセスの使用を記録し、スケジューリングでは、スケジューラは常にプロトタイプに最小限のリソースを消費するプロセスを選択します。これは、いわゆる "完全な公平性 "ですが、この絶対的な公平性は、いくつかのプロセスが他のものよりも重要な作業なので、CPUリソースを割り当てるために重み付けする必要があるため、時には不公平です。
相対的公平性
優先度の異なるプロセスを区別するため、各プロセスの重みに応じて実行時間を割り当てます。プロセスに割り当てられるランタイム = スケジューリング期間 * プロセスの重み / 全プロセスの重みの合計
