スケジューリング（コンピューティング）

コンピューティングにおいて、スケジューリングとは、タスクを実行するためにリソースを割り当てるアクションです。リソースには、プロセッサ、ネットワーク リンク、拡張カードなどがあり、タスクには、スレッド、プロセス、データフローなどがあります。

スケジューリング アクティビティは、スケジューラと呼ばれるプロセスによって実行されます。スケジューラは、多くの場合、すべてのコンピュータ リソースをビジー状態に保つ (負荷分散など)、複数のユーザーがシステム リソースを効率的に共有できるようにする、または目標のサービス品質を実現するように設計されます。

スケジューリングは計算そのものの基本であり、コンピュータ システムの実行モデルの本質的な部分です。スケジューリングの概念により、単一の中央処理装置(CPU) でコンピュータのマルチタスクが可能になります。

スケジューラは、たとえば次のような 1 つ以上の目標を目指すことができます。

• スループット（時間単位あたりに完了する作業の総量）を最大化する。
• 待機時間（作業の準備が整ってから実行が開始されるまでの時間）を最小限に抑える 。
• 待ち時間または応答時間（バッチアクティビティの場合は作業の準備が整うまでの時間、^{[1] [2] [3] 、またはインタラクティブアクティビティの場合はシステムが応答して最初}の出力をユーザーに渡すまでの時間）を最小限に抑える。^[4]
• 公平性を最大化します(各プロセスに均等な CPU 時間を割り当てる、またはより一般的には各プロセスの優先度と作業負荷に応じて適切な時間を割り当てる)。

実際には、これらの目標はしばしば矛盾します (例: スループットとレイテンシ)。そのため、スケジューラは適切な妥協案を実装します。優先順位は、ユーザーのニーズと目的に応じて、上記のいずれかの考慮事項によって測定されます。

産業用自動制御用の組み込みシステム（ロボット工学など）などのリアルタイム環境では、スケジューラはプロセスが期限に間に合うようにする必要もあります。これは、システムを安定させるために重要です。スケジュールされたタスクは、ネットワークを介してリモート デバイスに配布し、管理バックエンドを通じて 管理することもできます。

スケジューラは、システムに許可される次のジョブと実行される次のプロセスを選択するオペレーティング システム モジュールです。オペレーティング システムには、長期スケジューラ(許可スケジューラまたは高レベル スケジューラとも呼ばれます)、中期または中期スケジューラ、短期スケジューラという最大 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]

中期スケジューラは、プロセスを一時的にメイン メモリから削除して 2 次メモリ (ハード ディスク ドライブなど) に配置するか、その逆を行います。これは通常、スワップ アウトまたはスワップ イン(誤ってページアウトまたはページ インと呼ばれることもあります) と呼ばれます。中期スケジューラは、しばらくアクティブでないプロセス、優先度の低いプロセス、頻繁にページ フォールトが発生するプロセス、または大量のメモリを占有しているプロセスをスワップ アウトして、他のプロセス用にメイン メモリを解放し、後でメモリがさらに使用可能になったとき、またはプロセスのブロックが解除されてリソースを待機しなくなったときに、プロセスをスワップ インすることを決定する場合があります。

今日の多くのシステム (スワップ ファイル以外の二次ストレージへの仮想アドレス空間のマッピングをサポートするシステム) では、中期スケジューラが、バイナリを実行時にスワップアウトされたプロセスとして扱うことで、実際に長期スケジューラの役割を果たすことがあります。このように、バイナリのセグメントが必要な場合、オンデマンドでスワップインするか、遅延ロード(デマンド ページングとも呼ばれます)することができます。

短期スケジューラ( CPU スケジューラとも呼ばれる) は、クロック割り込み、I/O 割り込み、オペレーティングシステム コール、またはその他の形式のシグナルの後に、準備完了のメモリ内プロセスのうちどれを実行するか (CPU を割り当てるか) を決定します。したがって、短期スケジューラは、長期スケジューラや中期スケジューラよりもはるかに頻繁にスケジューリングの決定を行います。少なくとも、各タイム スライスの後にスケジューリングの決定を行う必要があり、これらは非常に短いものです。このスケジューラはプリエンプティブにすることも、非プリエンプティブにすることもできます。つまり、その CPU を別のプロセスに割り当てることを決定したときに、プロセスを CPU から強制的に削除することができます。また、非プリエンプティブ (自発的または協調的とも呼ばれる) にすることもできます。この場合、スケジューラはプロセスを CPU から 強制的に削除することはできません。

プリエンプティブ スケジューラは、カーネル モードで実行され、スケジューリング機能を実装する 割り込みハンドラを呼び出すプログラム可能な間隔タイマーに依存します。

CPU スケジューリング機能に関係するもう 1 つのコンポーネントはディスパッチャです。ディスパッチャは、短期スケジューラによって選択されたプロセスに CPU の制御を与えるモジュールです。ディスパッチャは、割り込みまたはシステム コールの結果としてカーネル モードで制御を受け取ります。ディスパッチャの機能は次のとおりです。

• コンテキスト スイッチでは、ディスパッチャは、以前実行されていたプロセスまたはスレッドの状態(コンテキストとも呼ばれる)を保存し、その後、新しいプロセスの初期状態または以前に保存された状態を読み込みます。
• ユーザーモードに切り替えます。
• ユーザー プログラム内の適切な場所にジャンプして、新しい状態によって示されるプログラムを再起動します。

ディスパッチャはプロセス切り替えのたびに呼び出されるため、できるだけ高速に動作する必要があります。コンテキスト切り替え中、プロセッサは事実上アイドル状態になるため、不要なコンテキスト切り替えは避ける必要があります。ディスパッチャが1つのプロセスを停止して別のプロセスを開始するのにかかる時間は、ディスパッチ待ち時間と呼ばれます。^{[7] : 155}

スケジューリング規則(スケジューリング ポリシーまたはスケジューリング アルゴリズムとも呼ばれる) は、同時に非同期的にリソースを要求するパーティ間でリソースを分配するために使用されるアルゴリズムです。スケジューリング規則は、ルーター(パケット トラフィックを処理するため) だけでなく、オペレーティング システム(スレッドとプロセスの両方でCPU 時間を共有するため)、ディスク ドライブ ( I/O スケジューリング)、プリンター (印刷スプーラー)、ほとんどの組み込みシステムなど で使用されます。

スケジューリング アルゴリズムの主な目的は、リソース不足を最小限に抑え、リソースを利用する当事者間の公平性を確保することです。スケジューリングは、未処理の要求のどれにリソースを割り当てるかを決定する問題を扱います。さまざまなスケジューリング アルゴリズムがあります。このセクションでは、そのうちのいくつかを紹介します。

パケット交換 コンピュータ ネットワークやその他の統計的多重化では、データ パケットの先着順キューイングの代替として、スケジューリング アルゴリズムの概念が使用されます。

最も単純なベストエフォート スケジューリング アルゴリズムは、ラウンドロビン、フェア キューイング(最大最小フェアスケジューリング アルゴリズム)、比例フェア スケジューリング、および最大スループットです。ベストエフォート通信ではなく、差別化された、または保証されたサービス品質が提供される場合は、加重フェア キューイングを利用できます。

HSDPA（高速ダウンリンクパケットアクセス）3.5Gセルラーシステムなどの高度なパケット無線ネットワークでは、チャネル依存のスケジューリングを使用してチャネル状態情報を活用することができます。チャネル状態が良好であれば、スループットとシステムのスペクトル効率が向上します。LTEなどのさらに高度なシステムでは、スケジューリングは、チャネルに依存するパケットごとの動的チャネル割り当てと組み合わせるか、OFDMAマルチキャリアやその他の周波数領域イコライゼーションコンポーネントを最も効果的に利用できるユーザーに割り当てることによって行われます。^[9]

先入先出法（FIFO ）は、先着順（FCFS）とも呼ばれ、最も単純なスケジューリングアルゴリズムです。FIFOは、単にプロセスを準備完了キューに到着した順にキューに入れます。これは、タスク キュー(このセクションに示されている例)。

• コンテキスト スイッチはプロセスの終了時にのみ発生し、プロセス キューの再編成は必要ないため、スケジューリングのオーバーヘッドは最小限に抑えられます。
• 長いプロセスが CPU を占有し、短いプロセスが長時間待機することになるため、スループットが低下する可能性があります (コンボイ効果として知られています)。
• 各プロセスは一定時間後に実行される機会を得るため、飢餓状態は発生しません。
• 処理時間、待ち時間、応答時間は到着順によって異なり、上記と同じ理由で長くなる場合があります。
• 優先順位付けが行われないため、このシステムではプロセスの期限を満たすことが困難になります。
• 優先順位付けがないということは、すべてのプロセスが最終的に完了する限り、リソース不足は発生しないことを意味します。一部のプロセスが完了しない可能性がある環境では、リソース不足が発生する可能性があります。
• キューイングに基づいています。

EDF (Earliest Deadline First) またはLeast Time To Go は、リアルタイム オペレーティング システムでプロセスを優先キューに配置するために使用される動的スケジューリング アルゴリズムです。スケジューリング イベント (タスクの終了、新しいタスクのリリースなど) が発生するたびに、キュー内で期限に最も近いプロセスが検索され、次に実行がスケジュールされます。

最短ジョブ優先(SJF)に似ています。この戦略では、スケジューラは、残りの処理時間が最も短いと推定されるプロセスをキューの次の位置に配置します。これには、プロセスが完了するのに必要な時間に関する高度な知識または推定が必要です。

• 別のプロセスの実行中に短いプロセスが到着すると、現在実行中のプロセスが中断され (プリエンプションと呼ばれます)、そのプロセスは 2 つの別々のコンピューティング ブロックに分割されます。これにより、追加のコンテキスト切り替えによって余分なオーバーヘッドが発生します。また、スケジューラは各着信プロセスをキュー内の特定の場所に配置する必要があり、追加のオーバーヘッドが発生します。
• このアルゴリズムは、ほとんどのシナリオで最大のスループットを実現するように設計されています。
• プロセスの計算要件が増加すると、待機時間と応答時間が増加します。ターンアラウンド時間は待機時間と処理時間の合計に基づいているため、長いプロセスはこれに大きく影響されます。ただし、最長プロセスの終了を待つ必要がないため、全体的な待機時間は FIFO よりも短くなります。
• 期限については特に注意が払われず、プログラマーは期限のあるプロセスをできるだけ短くすることしかできません。
• 特に、多数の小さなプロセスが実行されているビジーなシステムでは、リソース不足が発生する可能性があります。
• このポリシーを使用するには、少なくとも2つの異なる優先度のプロセスが必要です。

オペレーティング システムはすべてのプロセスに固定の優先度ランクを割り当て、スケジューラはプロセスを優先度順に準備キューに配置します。優先度の低いプロセスは、優先度の高いプロセスによって中断されます。

• オーバーヘッドは最小限ではなく、またそれほど大きくもありません。
• FPPS には、スループットの点では FIFO スケジューリングに比べて特別な利点はありません。
• 順位付けの数が制限されている場合、優先順位ごとに 1 つずつ FIFO キューの集合として特徴付けることができます。優先順位の低いキューのプロセスは、優先順位の高いキューがすべて空の場合にのみ選択されます。
• 待機時間と応答時間は、プロセスの優先度によって異なります。優先度の高いプロセスでは、待機時間と応答時間が短くなります。
• 期限のあるプロセスに高い優先順位を与えることで、期限を守ることができます。
• 多数の高優先度プロセスが CPU 時間のキューに入ると、低優先度プロセスが不足する可能性があります。

スケジューラはプロセスごとに固定の時間単位を割り当て、それらを循環させます。プロセスがその時間スライス内で完了した場合は終了され、それ以外の場合は他のすべてのプロセスに機会を与えた後で再スケジュールされます。

• RR スケジューリングでは、特に時間単位が小さい場合は、大きなオーバーヘッドが発生します。
• FCFS/FIFO と SJF/SRTF 間のスループットのバランスが取れており、短いジョブは FIFO よりも速く完了し、長いプロセスは SJF よりも速く完了します。
• 平均応答時間は良好で、待機時間はプロセス数に依存し、平均プロセスの長さには依存しません。
• 待機時間が長いため、純粋な RR システムでは期限が守られることはほとんどありません。
• 優先順位が与えられていないため、飢餓状態が発生することはありません。時間単位の割り当て順序は、FIFO と同様に、プロセス到着時間に基づいています。
• タイムスライスが大きい場合は FCFS/FIFO になり、短い場合は SJF/SRTF になります。

これは、プロセスが簡単に異なるグループに分割される状況で使用されます。たとえば、フォアグラウンド (対話型) プロセスとバックグラウンド (バッチ) プロセスの間で一般的な分割が行われます。これら 2 種類のプロセスには異なる応答時間要件があるため、異なるスケジュール要件が必要になる場合があります。これは、共有メモリの問題に非常に役立ちます。

作業節約型スケジューラは、スケジュール可能なジョブが送信されている場合、スケジュールされたリソースを常にビジー状態に維持しようとするスケジューラです。対照的に、非作業節約型スケジューラは、スケジュール可能なジョブが存在するにもかかわらず、スケジュールされたリソースをアイドル状態のままにしておく可能性があるスケジューラです。

総メイクスパンが最小になるように、どのジョブがどのステーションにいつ行くかを決定することを目的とするスケジューリング問題がいくつかあります。

• ジョブショップ スケジューリング- n 個のジョブとm 個の同一ステーション があります。各ジョブは 1 台のマシンで実行する必要があります。これは通常、オンライン問題と見なされます。
• オープンショップ スケジューリング- n 個のジョブとm 個の異なるステーション があります。各ジョブは、自由な順序で各ステーションで一定の時間を費やす必要があります。
• フローショップ スケジューリング- n 個のジョブとm 個の異なるステーション があります。各ジョブは、事前に決められた順序で、各ステーションで一定の時間を費やす必要があります。

組み込みシステムでは非常に一般的な方法は、ジョブを手動でスケジュールすることです。これは、たとえば、時間多重化方式で実行できます。カーネルは、手動スケジュール、プリエンプティブ、割り込みレベルの 3 つ以上の部分に分割されることがあります。ジョブをスケジュールするための正確な方法は、多くの場合、独自のものです。

• リソース不足の問題はありません
• 非常に高い予測可能性。ハードリアルタイムシステムの実装が可能
• オーバーヘッドはほとんどなし
• すべてのアプリケーションに最適ではない可能性があります
• 効果は実装に完全に依存します

オペレーティング システムを設計する場合、プログラマーは、システムの使用状況に応じてどのスケジューリング アルゴリズムが最もパフォーマンスを発揮するかを考慮する必要があります。普遍的に最適なスケジューリング アルゴリズムは存在せず、多くのオペレーティング システムでは、上記のスケジューリング アルゴリズムを拡張したものや組み合わせたものが使用されています。

たとえば、Windows NT /XP/Vistaでは、固定優先度のプリエンプティブ スケジューリング、ラウンドロビン、先入れ先出しアルゴリズムを組み合わせたマルチレベル フィードバック キューが使用されています。このシステムでは、スレッドは、すでに処理されているか、長時間待機しているかに応じて、優先度を動的に上げたり下げたりすることができます。各優先度レベルは独自のキューで表され、優先度の高いスレッド間ではラウンドロビン スケジューリングが使用され、優先度の低いスレッド間ではFIFO が使用されます。この意味で、ほとんどのスレッドの応答時間は短く、短いながらも重要なシステム スレッドは非常に速く完了します。スレッドは、最高優先度のキューのラウンドロビンの 1 つの時間単位しか使用できないため、優先度の高い長いスレッドでは、スタベーションが問題になることがあります。

使用されるアルゴリズムは、循環リスト内の各プロセスに等しい時間 (たとえば 1 ミリ秒、通常は 1 ミリ秒から 100 ミリ秒の間) が与えられるラウンドロビンのように単純な場合があります。つまり、プロセス A が 1 ミリ秒実行され、次にプロセス B、プロセス C が実行され、最後にプロセス A に戻ります。

より高度なアルゴリズムでは、プロセスの優先度、つまりプロセスの重要性が考慮されます。これにより、一部のプロセスは他のプロセスよりも多くの時間を使用できます。カーネルは、システムの適切な機能を確保するために必要なリソースを常に使用するため、優先度は無限であると言えます。SMP システムでは、プロセッサ アフィニティによって、プロセス自体の実行速度が低下する可能性はあるものの、全体的なシステムパフォーマンスが向上すると考えられています。これにより、一般にキャッシュ スラッシングが軽減され、パフォーマンスが向上します。

IBM OS/360には、3 つの異なるスケジューラが用意されていました。その違いは大きく、3 つの異なるオペレーティング システムと見なされることもよくありました。

• プライマリ コントロール プログラム (PCP)とも呼ばれるシングル シーケンシャル スケジューラ オプションは、単一のジョブ ストリームを順次実行します。
• 固定数のタスクによるマルチプログラミング (MFT)として知られる、複数のシーケンシャル スケジューラオプションは、複数の同時ジョブの実行を可能にしました。実行は、各ストリームにデフォルトがある優先度によって制御されるか、または各ジョブごとに個別に要求できます。MFT バージョン II では、親ジョブの優先度に基づいて実行されるサブタスク (スレッド) が追加されました。各ジョブ ストリームは、そのストリーム内のジョブが使用できるメモリの最大量を定義しました。
• 複数優先度スケジューラオプション、または可変数のタスクによるマルチプログラミング (MVT) では、最初からサブタスクが使用され、各ジョブは実行前に必要な優先度とメモリを要求しました。

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 つのプロセスが複数の協調スレッドを制御します。また、マルチプロセスタスクに対してはプリエンプティブスケジューリングも提供します。カーネルは、プリエンプティブスケジューリングアルゴリズムを使用してマルチプロセスタスクをスケジュールします。すべての Process Manager プロセスは、ブルータスクと呼ばれる特別なマルチプロセスタスク内で実行されます。これらのプロセスは、ラウンドロビンスケジューリングアルゴリズムを使用して協調的にスケジュールされます。プロセスは、などのブロッキング関数を明示的に呼び出すことでWaitNextEvent、プロセッサの制御を別のプロセスに譲ります。各プロセスには、そのプロセスのスレッドを協調的にスケジュールするスレッドマネージャのコピーがあります。スレッドは、YieldToAnyThreadまたはを呼び出すことで、プロセッサの制御を別のスレッドに譲りますYieldToThread。^[14]

macOSはマルチレベルフィードバックキューを使用しており、スレッドには4つの優先度帯（通常、システム高優先度、カーネルモードのみ、リアルタイム）があります。^[15]スレッドはプリエンプティブにスケジュールされます。macOSはCarbonのスレッドマネージャーの実装で協調的にスケジュールされたスレッドもサポートしています。^[14]

AIX バージョン 4 では、スレッド スケジューリング ポリシーに次の 3 つの値を指定できます。

• 先入先出: このポリシーを持つスレッドがスケジュールされると、ブロックされるか、CPU の制御を自発的に譲渡するか、またはより優先度の高いスレッドがディスパッチ可能になる場合を除き、完了するまで実行されます。固定優先度のスレッドのみが FIFO スケジューリング ポリシーを持つことができます。
• ラウンド ロビン: これは、10 ミリ秒のタイム スライスに基づく AIX バージョン 3 スケジューラー ラウンド ロビン スキームに似ています。タイム スライスの終了時に RR スレッドが制御権を持つと、その優先順位のディスパッチ可能なスレッドのキューの末尾に移動します。ラウンド ロビン スケジューリング ポリシーを持つことができるのは、固定優先順位のスレッドだけです。
• その他: このポリシーは、POSIX1003.4a によって実装定義として定義されています。AIX バージョン 4 では、このポリシーは RR と同等と定義されていますが、固定されていない優先順位を持つスレッドに適用されます。実行中のスレッドの優先順位値がクロック割り込みごとに再計算されるということは、優先順位値が別のディスパッチ可能なスレッドの優先順位値を上回るため、スレッドが制御を失う可能性があることを意味します。これは、AIX バージョン 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はniceタスクレベルと見なされます。リアルタイムタスクの場合、プロセス切り替えのタイムクォンタムは約200ミリ秒で、niceタスクの場合は約10ミリ秒でした。^[要出典]スケジューラは準備完了プロセスの実行キューをすべて実行し、最も優先度の高いプロセスを最初に実行してタイムスライスを実行した後、期限切れキューに配置します。アクティブキューが空になると、期限切れキューがアクティブキューになり、その逆も同様です。

ただし、SUSE Linux Enterprise Serverなどの一部のエンタープライズLinux ディストリビューションでは、このスケジューラを、ディストリビューションで使用される Linux 2.4 カーネルへのO(1) スケジューラ( Alan Coxが Linux 2.4-ac カーネル シリーズで保守していた) のバックポートに置き換えました。

バージョン 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)を開発し、発表の中でKolivasに功績を称えました。^[18] CFSは、汎用オペレーティングシステムで広く使用されている公平なキューイングプロセススケジューラ の最初の実装です。 ^[19]

CFS は、もともとパケット ネットワーク用に発明されたフェアキューイングと呼ばれる、十分に研究された古典的なスケジューリング アルゴリズムを使用します。フェア キューイングは、以前はストライド スケジューリングという名前で CPU スケジューリングに適用されていました。フェア キューイング CFS スケジューラのスケジューリング複雑度はで、Nは実行キュー内のタスク数です。タスクの選択は定数時間で実行できますが、実行後のタスクの再挿入には操作が必要です。これは、実行キューが赤黒木として実装されているためです。 ${\displaystyle O(\log N)}$${\displaystyle O(\log N)}$

同じく Con Kolivas によって作成されたBrain Fuck Scheduler は、CFS の代替手段です。

2023年にピーター・ジールストラはCFSをEEVDF（earliest qualified virtual deadline first scheduling ）プロセススケジューラに置き換えることを提案した。 ^{[20] [21]その目的はCFS}レイテンシniceパッチの必要性をなくすことだった。 ^[22]

FreeBSD は、 0～255 の優先度を持つマルチレベルフィードバックキューを使用します。0～63 は割り込み用に、64～127 はカーネルの上位半分用に、128～159 はリアルタイムユーザースレッド用に、160～223 はタイムシェアユーザースレッド用に、224～255 はアイドルユーザースレッド用に予約されています。また、Linux と同様にアクティブキュー設定を使用しますが、アイドルキューも備えています。^[23]

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 とは異なり、^[23]プロセスがタイム クォンタムの使用を完了すると、新しい優先度が与えられ、キューに戻されます。Solaris 9 では、固定優先度クラスとフェア シェア クラスという 2 つの新しいスケジューリング クラスが導入されました。固定優先度のスレッドは、タイム シェア クラスと同じ優先度範囲を持ちますが、優先度は動的に調整されません。フェア スケジューリング クラスは、CPUシェアを使用して、スケジューリング決定のためにスレッドに優先順位を付けます。CPU シェアは、CPU リソースの権利を示します。これらは、総称してプロジェクトと呼ばれる一連のプロセスに割り当てられます。^[7]

• オペレーティング システム: 3 つの簡単な部分 (Remzi H. Arpaci-Dusseau および Andrea C. Arpaci-Dusseau 著)。Arpaci-Dusseau Books、2014 年。関連章: スケジューリング: 概要 マルチレベル フィードバック キュー 比例共有スケジューリング マルチプロセッサ スケジューリング
• ジョブスケジューリングアルゴリズムの簡単な説明
• Linux カーネルを理解する: 第 10 章 プロセス スケジューリング
• Kerneltrap: Linux カーネル スケジューラに関する記事
• AIX CPU の監視とチューニング
• Josh Aas による Linux 2.6.8.1 CPU スケジューラ実装の紹介
• ピーター・ブルッカー、シグリッド・クヌスト。スケジューリング問題における計算量結果 [2]
• TORSCHE Scheduling Toolbox for Matlab は、スケジューリングおよびグラフ アルゴリズムのツールボックスです。
• 携帯電話ネットワークのパケットスケジューリングに関する調査
• Borg を使用した Google の大規模クラスタ管理