Loading article…
コンピューティングにおいて、スケジューリングとは、タスクを実行するためにリソースを割り当てる処理のことである。リソースには、プロセッサ、ネットワークリンク、拡張カードなどが含まれる。タスクには、スレッド、プロセス、データフローなどが含まれる。
スケジューリング処理は、スケジューラと呼ばれるメカニズムによって実行されます。スケジューラは、コンピュータのすべてのリソースを常に稼働状態に保つ（負荷分散など）、複数のユーザーがシステムリソースを効率的に共有できるようにする、または目標とするサービス品質を達成するなど、様々な目的で設計されています。
スケジューリングは計算そのものの基礎であり、コンピュータシステムの実行モデルの本質的な部分です。スケジューリングの概念によって、単一の中央処理装置（CPU）でコンピュータのマルチタスク処理が可能になります。
スケジューラは、例えば以下のような1つまたは複数の目標を目指すことができます。
実際には、これらの目標はしばしば相反するため（例えば、スループットとレイテンシ）、スケジューラは適切な妥協点を見出すように設計します。優先順位は、ユーザーのニーズと目的に応じて、上述の懸念事項のいずれかに基づいて決定されます。
産業用自動制御組み込みシステム（例えばロボット工学）のようなリアルタイム環境では、スケジューラはプロセスが期限内に完了することを保証する必要があります。これはシステムの安定性を維持するために不可欠です。スケジュールされたタスクは、ネットワークを介してリモートデバイスに分散され、管理バックエンドを通じて管理されます。
スケジューラは、オペレーティングシステムのモジュールの一つで、システムに受け入れる次のジョブと実行する次のプロセスを選択します。オペレーティングシステムには、長期スケジューラ（アドミッションスケジューラまたは高レベルスケジューラとも呼ばれる）、中期スケジューラ、短期スケジューラの3種類のスケジューラが存在する場合があります。これらの名称は、それぞれの機能が実行される頻度を示しています。
プロセススケジューラは、特定の時点でどのプロセスを実行するかを決定するオペレーティングシステムの一部です。通常、実行中のプロセスを一時停止し、実行キューの最後尾に移動して新しいプロセスを開始する機能があります。このようなスケジューラはプリエンプティブスケジューラと呼ばれます。スケジューラが実行中のプロセスを一時停止して新しいプロセスを開始できない場合、そのスケジューラは協調スケジューラです。[ 5 ]
意思決定の頻度に基づいて、長期スケジューリング、中期スケジューリング、短期スケジューリングを区別します。 [ 6 ]
長期スケジューラ、またはアドミッションスケジューラは、どのジョブまたはプロセスをレディキュー（メインメモリ内）に受け入れるかを決定します。つまり、プログラムの実行が試みられると、現在実行中のプロセス群へのそのプログラムの受け入れは、長期スケジューラによって承認されるか、遅延されます。このように、このスケジューラは、システム上でどのプロセスを実行するか、同時にサポートされる並行性の度合い（多数のプロセスを同時に実行するか、少数のプロセスを同時に実行するか）、およびI/O集約型プロセスとCPU集約型プロセスの分割をどのように処理するかを決定します。長期スケジューラは、マルチプログラミングの度合いを制御する役割を担っています。
一般的に、ほとんどのプロセスはI/OバウンドまたはCPUバウンドのいずれかに分類できます。I/Oバウンドプロセスとは、計算よりもI/Oに多くの時間を費やすプロセスです。一方、CPUバウンドプロセスは、I/O要求をあまり生成せず、計算に多くの時間を費やします。長期スケジューラでは、I/OバウンドプロセスとCPUバウンドプロセスの適切な組み合わせを選択することが重要です。すべてのプロセスがI/Oバウンドの場合、準備完了キューはほぼ常に空になり、短期スケジューラはほとんど何もすることがなくなります。一方、すべてのプロセスがCPUバウンドの場合、I/O待機キューはほぼ常に空になり、デバイスは使用されずに、システムは再びアンバランスになります。したがって、最高のパフォーマンスを発揮するシステムは、CPUバウンドプロセスとI/Oバウンドプロセスの組み合わせを持つことになります。最新のオペレーティングシステムでは、リアルタイムプロセスがタスクを完了するのに十分なCPU時間を確保できるようにするために、この仕組みが使用されています。[ 7 ]
バッチ処理システム、コンピュータクラスタ、スーパーコンピュータ、レンダリングファームなどの大規模システムでは、長期的なスケジューリングも重要です。例えば、並行システムでは、相互作用するプロセスが互いに待機状態になることによるブロックを防ぐために、プロセスの同時スケジューリングが必要となることがよくあります。このような場合、オペレーティングシステムの基盤となるアドミッションスケジューリング機能に加えて、専用のジョブスケジューラソフトウェアがこれらの機能を支援するために一般的に使用されます。
一部のオペレーティングシステムでは、すべてのリアルタイムの期限が確実に守れる場合にのみ、新しいタスクの追加が許可されます。オペレーティングシステムが新しいタスクを受け入れるか拒否するかを決定するために使用する特定のヒューリスティックアルゴリズムは、アドミッションコントロールメカニズムです。[ 8 ]
中期スケジューラは、プロセスを一時的にメインメモリから削除して二次記憶装置（ハードディスクドライブなど）に配置したり、その逆を行ったりします。これは一般的にスワップアウトまたはスワップイン（ページアウトまたはページインと誤って呼ばれることもあります）と呼ばれます。中期スケジューラは、しばらくアクティブになっていないプロセス、優先度の低いプロセス、ページフォルトを頻繁に発生させているプロセス、または大量のメモリを消費しているプロセスをスワップアウトして、他のプロセスのためにメインメモリを解放し、後でより多くのメモリが利用可能になったとき、またはプロセスがブロック解除されてリソースを待機しなくなったときに、そのプロセスをスワップインに戻すことがあります。
今日の多くのシステム（仮想アドレス空間をスワップファイル以外の二次記憶装置にマッピングするシステム）では、中期スケジューラが、バイナリの実行時にスワップアウトされたプロセスとして扱うことで、長期スケジューラの役割を果たすことがあります。このようにして、バイナリの一部が必要になったときに、オンデマンドでスワップイン（遅延ロード、またはデマンドページングとも呼ばれる）することができます。
短期スケジューラ（ CPUスケジューラとも呼ばれる）は、クロック割り込み、I/O割り込み、オペレーティングシステムコール、またはその他の形式のシグナルの後に、メモリ上に準備完了状態のプロセスのうちどれを実行するか（CPUを割り当てるか）を決定します。したがって、短期スケジューラは、長期または中期スケジューラよりもはるかに頻繁にスケジューリングの決定を行います。スケジューリングの決定は、少なくとも各タイムスライスの後に行われる必要があり、これらのタイムスライスは非常に短いものです。このスケジューラは、プリエンプティブである場合と、非プリエンプティブ（任意または協調的とも呼ばれる）である場合があり、プリエンプティブである場合は、CPUからプロセスを強制的に削除することができます。非プリエンプティブの場合は、スケジューラはCPUからプロセスを強制的に削除することはできません。
CPUスケジューリング機能に関わるもう1つのコンポーネントはディスパッチャです。ディスパッチャは、短期スケジューラによって選択されたプロセスにCPUの制御権を与えるモジュールです。ディスパッチャは、割り込みまたはシステムコールの結果としてカーネルモードで制御権を受け取ります。ディスパッチャの機能は以下のとおりです。
ディスパッチャはプロセス切り替えのたびに呼び出されるため、可能な限り高速であるべきです。コンテキストスイッチの間、プロセッサはごくわずかな時間だけ事実上アイドル状態になるため、不要なコンテキストスイッチは避けるべきです。ディスパッチャが1つのプロセスを停止して別のプロセスを開始するのにかかる時間は、ディスパッチレイテンシと呼ばれます。[ 7 ] : 155
スケジューリング規律（スケジューリングポリシーまたはスケジューリングアルゴリズムとも呼ばれる）とは、同時かつ非同期的にリソースを要求する関係者間でリソースを分配するために使用されるアルゴリズムです。スケジューリング規律は、ルーター（パケットトラフィックの処理）、オペレーティングシステム（スレッドとプロセスの両方でCPU時間を共有）、ディスクドライブ（I/Oスケジューリング）、プリンター（プリントスプーラー）、ほとんどの組み込みシステムなどで使用されています。
スケジューリングアルゴリズムの主な目的は、リソース不足を最小限に抑え、リソースを利用する関係者間の公平性を確保することです。スケジューリングとは、未処理の要求のうちどれにリソースを割り当てるかを決定する問題です。スケジューリングアルゴリズムには様々な種類があります。このセクションでは、そのうちのいくつかを紹介します。
パケット交換型コンピュータネットワークやその他の統計的多重化方式では、データパケットの先着順キューイングの代替手段として、スケジューリングアルゴリズムの概念が用いられる。
最も単純なベストエフォート型スケジューリングアルゴリズムとしては、ラウンドロビン、フェアキューイング（最大最小フェアスケジューリングアルゴリズム）、比例フェアスケジューリング、最大スループットなどがあります。ベストエフォート型の通信とは異なり、差別化された、あるいは保証されたサービス品質が提供される場合は、加重フェアキューイングが利用されることがあります。
HSDPA（高速ダウンリンクパケットアクセス）3.5Gセルラーシステムなどの高度なパケット無線無線ネットワークでは、チャネル状態情報を活用するためにチャネル依存スケジューリングが使用されることがあります。チャネル状態が良好な場合、スループットとシステムスペクトル効率が向上する可能性があります。LTEなどのさらに高度なシステムでは、チャネル依存のパケットごとの動的チャネル割り当て、またはOFDMAマルチキャリアやその他の周波数領域等化コンポーネントを最も有効に活用できるユーザーに割り当てることによってスケジューリングが組み合わされます。[ 9 ]
先入れ先出し( FIFO ) は、先着順(FCFS)とも呼ばれ、最も単純なスケジューリング アルゴリズムです。FIFO は、準備完了キューに到着した順にプロセスをキューに入れます。これは一般的に、タスクキューは、例えばこのセクションで説明されているようなものです。
最早期限優先（EDF）または最小残り時間優先は、リアルタイムオペレーティングシステムで使用される動的スケジューリングアルゴリズムで、プロセスを優先度キューに配置するために使用されます。スケジューリングイベント（タスクの完了、新しいタスクのリリースなど）が発生するたびに、キュー内で期限に最も近いプロセスが検索され、それが次に実行されるプロセスとしてスケジュールされます。
最短ジョブ優先（SJF）と同様の方式です。この方式では、スケジューラは処理時間の残り推定値が最も少ないプロセスをキューの次の位置に配置します。そのため、プロセスの完了に必要な時間に関する高度な知識または推定値が必要となります。
オペレーティングシステムはすべてのプロセスに固定の優先度ランクを割り当て、スケジューラはそれらの優先度順にプロセスを準備完了キューに並べます。優先度の低いプロセスは、優先度の高いプロセスが到着すると中断されます。
スケジューラはプロセスごとに固定の時間単位を割り当て、それらを順番に処理します。プロセスがその時間内に完了すれば終了し、そうでなければ他のすべてのプロセスに実行機会を与えた後、再スケジュールされます。
これは、プロセスを容易に異なるグループに分割できる状況で使用されます。例えば、フォアグラウンド（対話型）プロセスとバックグラウンド（バッチ）プロセスという一般的な区分が挙げられます。これら2種類のプロセスは応答時間の要件が異なるため、スケジューリングのニーズも異なる場合があります。共有メモリの問題に非常に有効です。
作業効率化スケジューラとは、スケジューリング可能なジョブが存在する場合、常にスケジューリングされたリソースを稼働させようとするスケジューラです。一方、非作業効率化スケジューラとは、スケジューリング可能なジョブが存在する場合でも、場合によってはスケジューリングされたリソースをアイドル状態にしてしまうスケジューラです。
スケジューリング問題には、総完了時間を最小化するように、どのジョブをどのステーションにどの時間で送るかを決定することが目的となるものがいくつかある。
組み込みシステムでは、ジョブを手動でスケジュールする方法が非常に一般的です。これは、例えば時分割多重方式で行うことができます。カーネルは、手動スケジューリング、プリエンプティブ、割り込みレベルなど、3つ以上の部分に分割される場合もあります。ジョブをスケジュールするための具体的な方法は、多くの場合、企業秘密となっています。
オペレーティングシステムを設計する際、プログラマーは、システムが想定する用途において、どのスケジューリングアルゴリズムが最も優れたパフォーマンスを発揮するかを検討する必要があります。万能な最適なスケジューリングアルゴリズムは存在せず、多くのオペレーティングシステムは、上記のスケジューリングアルゴリズムを拡張したり、組み合わせたりして使用しています。
例えば、Windows NT /XP/Vistaでは、固定優先度のプリエンプティブ スケジューリング、ラウンドロビン、先入れ先出し (FIFO) アルゴリズムを組み合わせたマルチレベル フィードバック キューが使用されています。このシステムでは、スレッドは既に処理されたか、長時間待機しているかに応じて、優先度が動的に増減します。各優先度レベルは独自のキューで表され、優先度の高いスレッド間ではラウンドロビン スケジューリングが、優先度の低いスレッド間ではFIFO が採用されています。このため、ほとんどのスレッドの応答時間は短く、短時間で重要なシステム スレッドも非常に迅速に完了します。スレッドは最高優先度キューのラウンドロビンのタイム ユニットを 1 つしか使用できないため、優先度の高い長時間のスレッドでは、リソース不足が問題となる可能性があります。
使用されるアルゴリズムは、各プロセスに均等な時間（例えば1ミリ秒、通常は1ミリ秒から100ミリ秒の間）を循環リストで割り当てるラウンドロビン方式のような単純なものになる場合があります。つまり、プロセスAが1ミリ秒実行され、次にプロセスB、次にプロセスCが実行され、最後にプロセスAに戻ります。
より高度なアルゴリズムでは、プロセスの優先度、つまりプロセスの重要度を考慮します。これにより、一部のプロセスは他のプロセスよりも多くの時間を使用できるようになります。カーネルは常にシステムの適切な動作を確保するために必要なリソースを使用するため、優先度は無限であると言えます。SMPシステムでは、プロセッサアフィニティは、プロセス自体の実行速度が低下する可能性がある場合でも、システム全体のパフォーマンスを向上させると考えられています。これは一般的に、キャッシュスラッシングを減らすことでパフォーマンスを向上させます。
IBM OS/360には3種類の異なるスケジューラが用意されていた。その違いは非常に大きく、これらのバリアントはしばしば3つの異なるオペレーティングシステムとみなされた。
MVSの後の仮想ストレージバージョンでは、スケジューラにワークロードマネージャ機能が追加され、インストール時に定義された詳細な計画に従ってプロセッサリソースをスケジュールするようになりました。
初期のMS-DOSおよびMicrosoft Windowsシステムはマルチタスクに対応しておらず、スケジューラも搭載していませんでした。Windows 3.1xは非プリエンプティブスケジューラを使用しており、プログラムを中断しませんでした。プログラムが終了するか、プロセッサが不要になったことをOSに通知することで、別のプロセスに進むことができました。これは通常、協調型マルチタスクと呼ばれます。Windows 95では基本的なプリエンプティブスケジューラが導入されましたが、レガシーサポートのために16ビットアプリケーションはプリエンプションなしで実行できるようにしました。[ 10 ]
Windows NTベースのオペレーティングシステムは、マルチレベルフィードバックキューを使用します。優先度レベルは 0 から 31 まで 32 段階定義されており、優先度 0 から 15 は通常の優先度、優先度 16 から 31 はソフトリアルタイム優先度で、割り当てには権限が必要です。優先度 0 はオペレーティングシステム用に予約されています。ユーザー インターフェイスと API は、プロセスおよびプロセス内のスレッドの優先度クラスを使用して動作し、システムはそれらを組み合わせて絶対優先度レベルを決定します。
カーネルは、スレッドの I/O と CPU の使用状況、および対話型であるかどうか (つまり、人間からの入力を受け入れて応答するかどうか) に応じてスレッドの優先度レベルを変更することがあります。対話型で I/O がバウンドなプロセスの優先度を上げ、CPU がバウンドなプロセスの優先度を下げることで、対話型アプリケーションの応答性を向上させます。[ 11 ]スケジューラは、 Windows Vistaで変更され、単にインターバル タイマー割り込みルーチンを使用するのではなく、最新のプロセッサのサイクル カウンタ レジスタを使用して、スレッドが実行した CPU サイクル数を正確に追跡するようになりました。[ 12 ] Vista では、ディスク デフラグツールなどのプログラムがフォアグラウンド操作に干渉しないように、I/O キューに優先度スケジューラも使用しています。[ 13 ]
Mac OS 9 は、スレッドに対して協調スケジューリングを使用しており、1 つのプロセスが複数の協調スレッドを制御します。また、マルチプロセッシング タスクに対してはプリエンプティブ スケジューリングも提供しています。カーネルは、プリエンプティブ スケジューリング アルゴリズムを使用してマルチプロセッシング タスクをスケジュールします。すべてのプロセスマネージャ プロセスは、ブルー タスクと呼ばれる特別なマルチプロセッシング タスク内で実行されます。これらのプロセスは、ラウンド ロビン スケジューリングアルゴリズムを使用して協調的にスケジュールされます。プロセスは、などのブロッキング関数を明示的に呼び出すことにより、プロセッサの制御を別のプロセスに譲渡します。各プロセスは、そのプロセスのスレッドを協調的にスケジュールするスレッドマネージャWaitNextEventの独自のコピーを持っています。スレッドは、またはを呼び出すことにより、プロセッサの制御を別のスレッドに譲渡します。[ 14 ]YieldToAnyThreadYieldToThread
macOS はマルチレベルフィードバックキューを使用し、スレッドには通常、システム高優先度、カーネルモードのみ、リアルタイムの 4 つの優先度バンドがあります。 [ 15 ]スレッドはプリエンプティブにスケジュールされます。macOS はCarbonのスレッドマネージャの実装で協調的にスケジュールされたスレッドもサポートしています。[ 14 ]
AIXバージョン4では、スレッドスケジューリングポリシーに3つの値を指定できます。
スレッドは、現在複数の非同期プロセスで構成されているアプリケーションにとって特に重要です。これらのアプリケーションをマルチスレッド構造に変換することで、システムへの負荷を軽減できる可能性があります。
AIX 5 では、FIFO、ラウンドロビン、フェアラウンドロビンというスケジューリング ポリシーが実装されています。FIFO ポリシーには、FIFO、FIFO2、FIFO3 の 3 つの実装があります。ラウンドロビン ポリシーは AIX では SCHED_RR と呼ばれ、フェアラウンドロビンは SCHED_OTHER と呼ばれます。[ 16 ]
Linux 1.2 はラウンドロビン方式のスケジューリングポリシーを採用していた。[ 17 ]
Linux 2.2ではスケジューリングクラスと対称型マルチプロセッシング（SMP）のサポートが追加されました。[ 17 ]
Linux 2.4 [ 17 ]では、優先度レベルが 0 から 140 までの範囲のマルチレベルフィードバックキューを備えたO (n) スケジューラが使用されました。0 ～ 99 はリアルタイムタスク用に予約されており、100 ～ 140 はナイスタスクレベルと見なされます。リアルタイムタスクの場合、プロセス切り替えのタイムクォンタムは約 200 ms、ナイスタスクの場合は約 10 ms でした。スケジューラは、準備完了したすべてのプロセスの実行キューを順に処理し、優先度が最も高いプロセスを最初に実行してタイムスライスを処理させた後、期限切れキューに配置します。アクティブキューが空になると、期限切れキューがアクティブキューになり、その逆も同様です。
しかし、SUSE Linux Enterprise Serverなどの一部のエンタープライズLinuxディストリビューションでは、このスケジューラを、ディストリビューションで使用されているLinux 2.4カーネルにバックポートされたO(1)スケジューラ（Alan CoxがLinux 2.4-ac Kernelシリーズでメンテナンスしていたもの）に置き換えました。
バージョン2.6.0から2.6.22では、カーネルはLinux 2.5の開発中にIngo Molnar氏をはじめとする多くのカーネル開発者によって開発されたO(1)スケジューラを使用していました。この期間の多くのカーネルにおいて、Con Kolivas氏は、このスケジューラとの対話性を向上させたり、独自のスケジューラに置き換えたりするパッチセットを開発しました。
Con Kolivas の研究、特にRotating Staircase Deadline (RSDL)と呼ばれる公平スケジューリングの実装は、Ingo Molnárが以前のO(1) スケジューラに代わるものとしてCompletely Fair Scheduler (CFS) を開発するきっかけとなり、Molnár は発表の中で Kolivas に謝意を表した。[ 18 ] CFS は、汎用オペレーティングシステムで広く使用されている 公平キューイングプロセススケジューラの最初の実装である。 [ 19 ]
CFSは、パケットネットワーク向けに考案されたフェアキューイングと呼ばれる、よく研究された古典的なスケジューリングアルゴリズムを使用しています。フェアキューイングは、以前はストライドスケジューリングという名前でCPUスケジューリングに適用されていました。フェアキューイングCFSスケジューラのスケジューリング複雑度はここで、Nは実行キュー内のタスク数です。タスクの選択は定数時間で行えますが、実行後にタスクを再挿入するには、実行キューは赤黒木として実装されているため、操作が行われます。
Con Kolivas氏が作成したBrain Fuck Schedulerは、CFSの代替となるツールです。
2023年、ピーター・ジールストラはCFSを最も早い適格仮想期限優先スケジューリング（EEVDF）プロセススケジューラに置き換えることを提案した。[ 20 ] [ 21 ]その目的は、CFSレイテンシーナイスパッチの必要性をなくすことだった。[ 22 ]
Linux 6.12 では、ユーザー空間から追加できるスケジューラ拡張機能のサポートが追加されました。このメカニズムは sched_ext として知られています。eBPFプログラムをカーネルにロードしてスケジューリング ポリシーを実装できます。[ 23 ]これらのスケジューラは、デフォルトのスケジューラを置き換えることができます。[ 24 ]
FreeBSD は、0 ～ 255 の優先度を持つマルチレベルフィードバックキューを使用します。0 ～ 63 は割り込み用に予約されており、64 ～ 127 はカーネルの上位半分、128 ～ 159 はリアルタイムユーザー スレッド、160 ～ 223 はタイムシェアリング ユーザー スレッド、224 ～ 255 はアイドル ユーザー スレッド用です。また、Linux と同様にアクティブ キュー セットアップを使用しますが、アイドル キューも備えています。[ 25 ]
NetBSD は、0 ～ 223 の優先度を持つマルチレベルフィードバックキューを使用します。0 ～ 63 はタイムシェアリングスレッド (デフォルト、SCHED_OTHER ポリシー) 用に予約されており、64 ～ 95 はカーネル空間に入ったユーザー スレッド用、96 ～ 128 はカーネル スレッド用、128 ～ 191 はユーザーリアルタイム スレッド (SCHED_FIFO および SCHED_RR ポリシー) 用、192 ～ 223 はソフトウェア割り込み用です。
Solaris は、優先度が 0 ～ 169 の範囲にあるマルチレベルフィードバックキューを使用します。優先度 0 ～ 59 はタイムシェアスレッド用に予約され、60 ～ 99 はシステムスレッド用、100 ～ 159 はリアルタイムスレッド用、160 ～ 169 は低優先度割り込み用です。Linux とは異なり、[ 25 ]プロセスがタイムクォンタムを使用して終了すると、新しい優先度が与えられ、キューに戻されます。Solaris 9 では、固定優先度クラスとフェアシェアクラスという 2 つの新しいスケジューリングクラスが導入されました。固定優先度のスレッドはタイムシェアクラスと同じ優先度範囲を持ちますが、優先度は動的に調整されません。フェアスケジューリングクラスは、CPUシェアを使用してスケジューリング決定のためのスレッドの優先順位を決定します。CPU シェアは、CPU リソースの権利を示します。これらは、プロジェクトとして総称される一連のプロセスに割り当てられます。[ 7 ]
要求からその要求に対する応答の終了までの時間間隔と定義します。
顧客がx秒のサービスを必要とする場合、応答時間はサービス時間xに待ち時間を加えた値になります。
ジョブがキューで待機する時間を t w、実際に実行される時間を t rとすると、応答時間は r = t w + t rとなります。
多くの場合、処理は比較的早い段階で何らかの出力を生成し、以前の結果をユーザーに出力している間にも新しい結果の計算を継続できます。そのため、別の指標として、リクエストの送信から最初の応答が生成されるまでの時間が挙げられます。この指標は応答時間と呼ばれ、応答の出力にかかる時間ではなく、応答を開始するまでの時間です。
{{cite web}}: CS1 maint: タイトルとしてアーカイブされたコピー (リンク)