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

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

スケジューリング活動は、スケジューラと呼ばれるメカニズムによって実行されます。スケジューラは、多くの場合、すべてのコンピュータリソースをビジー状態に保つ（負荷分散など）、複数のユーザーがシステムリソースを効率的に共有できるようにする、または目標とするサービス品質を達成するように設計されます。

スケジューリングは計算そのものの基礎であり、コンピュータ システムの実行モデルの本質的な部分です。スケジューリングの概念により、単一の中央処理装置(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スケジューリング機能に関与するもう一つのコンポーネントはディスパッチャです。ディスパッチャは、短期スケジューラによって選択されたプロセスにCPU制御を与えるモジュールです。ディスパッチャは、割り込みまたはシステムコールの結果としてカーネルモードで制御を受け取ります。ディスパッチャの機能は以下のとおりです。

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

ディスパッチャはプロセススイッチのたびに呼び出されるため、可能な限り高速である必要があります。コンテキストスイッチの間、プロセッサはほんのわずかな時間の間、事実上アイドル状態になるため、不要なコンテキストスイッチは避けるべきです。ディスパッチャが1つのプロセスを停止し、別のプロセスを開始するのにかかる時間は、ディスパッチレイテンシと呼ばれます。[ 7 ]：155

スケジューリングの分野

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

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

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

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

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

先着順

待機中のタスクのキュー (FIFO) (青) と完了したタスクのキュー (黄色) を含むサンプルスレッド プール(緑のボックス)

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

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

優先スケジュール

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

残り時間が短い順

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

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

固定優先度のプリエンプティブスケジューリング

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

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

ラウンドロビンスケジューリング

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

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

マルチレベルキュースケジューリング

これは、プロセスを容易に異なるグループに分割できる状況で使用されます。例えば、フォアグラウンド（対話型）プロセスとバックグラウンド（バッチ）プロセスという一般的なグループ分けが挙げられます。これら2種類のプロセスは応答時間要件が異なるため、スケジューリング要件も異なる可能性があります。これは共有メモリの問題に非常に役立ちます。

作業節約型スケジューラ

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

スケジューリング最適化問題

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

手動スケジュール

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

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

スケジューリングアルゴリズムの選択

オペレーティングシステムを設計する際には、プログラマーはシステムの用途に最適なスケジューリングアルゴリズムを検討する必要があります。普遍的に最適なスケジューリングアルゴリズムは存在せず、多くのオペレーティングシステムでは上記のスケジューリングアルゴリズムを拡張したり組み合わせたりして使用しています。

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

オペレーティングシステムのプロセススケジューラの実装

使用されるアルゴリズムは、循環リスト内の各プロセスに均等な時間（例えば1ミリ秒、通常は1ミリ秒から100ミリ秒の間）を与えるラウンドロビンのような単純なものになる場合があります。つまり、プロセスAが1ミリ秒実行され、次にプロセスB、プロセスC、そして再びプロセスAへと処理が移ります。

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

OS/360 および後継機種

IBM OS/360には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とmacOS

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

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

AIX

AIX バージョン 4 では、スレッド スケジューリング ポリシーに次の 3 つの値が可能です。

  • 先入先出（FIFO）: このポリシーが設定されたスレッドは、一度スケジュールされると、ブロックされるか、自発的に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 ]

リナックス

リナックス 1.2

Linux 1.2ではラウンドロビンスケジューリングポリシーが使用されていました。[ 17 ]

リナックス 2.2

Linux 2.2ではスケジューリングクラスと対称型マルチプロセッシング（SMP）のサポートが追加された。[ 17 ]

プロセス スケジューラ、I/O スケジューラ、パケット スケジューラを含む、Linux カーネルの非常に単純化された構造

リナックス 2.4

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 カーネル シリーズで保守) のバックポートに置き換えました。

Linux 2.6.0 から Linux 2.6.22

バージョン2.6.0から2.6.22まで、カーネルはLinux 2.5の開発中にIngo Molnarをはじめとする多くのカーネル開発者によって開発されたO(1)スケジューラを使用していました。この期間の多くのカーネルにおいて、 Con Kolivasはパッチセットを開発し、このスケジューラとのインタラビリティを改善したり、独自のスケジューラに置き換えたりしました。

Linux 2.6.23 から Linux 6.5

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 の代替手段です。

リナックス 6.6

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

リナックス 6.12

Linux 6.12では、ユーザー空間から追加できるスケジューラ拡張のサポートが追加されました。このメカニズムはsched_extとして知られています。eBPFプログラムをカーネルにロードすることで、スケジューリングポリシーを実装できます。[ 23 ]これらのスケジューラは、デフォルトのスケジューラを置き換えることができます。[ 24 ]

フリーBSD

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

ネットBSD

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リソースの権利を示します。CPUシェアは、プロジェクトと呼ばれる一連のプロセスに割り当てられます。[ 7 ]

まとめ

オペレーティング·システム 先取権 アルゴリズム
アミーガOSはい 優先順位付けされたラウンドロビンスケジューリング
フリーBSDはい 多段階フィードバックキュー
Linuxカーネル2.6.0以前 はい 多段階フィードバックキュー
Linuxカーネル2.6.0～2.6.23 はい O(1)スケジューラ
Linuxカーネル2.6.23～6.6 はい 完全に公平なスケジューラ
Linuxカーネル6.6以降 はい 最も早い適格仮想期限優先スケジュール（EEVDF）
クラシックMac OS 9以前 なし 協調スケジューラ
Mac OS 9いくつかの MPタスクのプリエンプティブスケジューラ、プロセスとスレッドの協調スケジューラ
macOSはい 多段階フィードバックキュー
ネットBSDはい 多段階フィードバックキュー
ソラリスはい 多段階フィードバックキュー
ウィンドウズ 3.1xなし 協調スケジューラ
Windows 95、98 、Me​半分 32 ビット プロセスではプリエンプティブ スケジューラ、16 ビット プロセスでは協調スケジューラ
Windows NT（2000、XP、Vista、7、Serverを含む） はい 多段階フィードバックキュー

参照

注記

  1. ^ CL, Liu; James W., Layland (1973年1月). 「ハードリアルタイム環境におけるマルチプログラミングのスケジューリングアルゴリズム」 . Journal of the ACM . 20 (1). ACM: 46– 61. doi : 10.1145/321738.321743 . S2CID  207669821.特定のタスクに対するリクエストの応答時間は、リクエストからそのリクエストへの応答が終了するまでの時間と定義します。
  2. ^クラインロック、レナード (1976).待ち行列システム 第2巻：コンピュータアプリケーション（第1版）. Wiley-Interscience. p.  171. ISBN 047149111Xx 秒のサービスを必要とする顧客の場合、応答時間はサービス時間と待機時間の合計になります。
  3. ^ Feitelson, Dror G. (2015).コンピュータシステム性能評価のためのワークロードモデリング. Cambridge University Press. 無料公開原稿バージョン1.03のセクション8.4（422ページ）. ISBN 9781107078239. 2015-10-17取得。ジョブがキュー内で待機する時間を t w、ジョブが実際に実行される時間を t rとすると、応答時間は r = t w + t rとなります。
  4. ^シルバーシャッツ、アブラハム、ガルビン、ピーター・ベア、ガニエ、グレッグ (2012). 『オペレーティングシステムの概念』（第9版）. Wiley Publishing. p. 187. ISBN 978-0470128725対話型システムでは、ターンアラウンドタイムは必ずしも最適な基準ではありません。多くの場合、プロセスはかなり早い段階で何らかの出力を生成し、以前の結果をユーザーに出力している間も新しい結果の計算を続けることができます。そのため、リクエストの送信から最初の応答が生成されるまでの時間を別の指標として用いることができます。この指標は応答時間と呼ばれ、応答の出力にかかる時間ではなく、応答を開始するまでの時間です。
  5. ^ Paul Krzyzanowski (2014年2月19日). 「プロセススケジューリング：次に実行するのは誰か？」 cs.rutgers.edu . 2023年6月19日閲覧。
  6. ^ラファエル・フィンケル(1988). 「第2章 時間管理」.オペレーティングシステム入門書. プレンティス・ホール. p. 27.
  7. ^ a b cアブラハム・シルバーシャッツ、ピーター・ベア・ガルビン、グレッグ・ガニエ (2013).オペレーティングシステムコンセプト. 第9巻. John Wiley & Sons, Inc. ISBN 978-1-118-06333-0。
  8. ^ Robert Kroeger (2004). 「独立して作成されたリアルタイムアプリケーションのためのアドミッションコントロール」 . UWSpace. http://hdl.handle.net/10012/1170 . セクション「2.6 アドミッションコントロール」. p. 33.
  9. ^ Guowang Miao、Jens Zander、Ki Won Sung、Ben Slimane (2016). 『モバイルデータネットワークの基礎』ケンブリッジ大学出版局. ISBN 978-1107143210。
  10. ^ Wayback Machineの初期の Windows (アーカイブ インデックス)
  11. ^ Sriram Krishnan. 「Windows NTとWindows CEの2つのスケジューラの物語」 。2012年7月22日時点のオリジナルよりアーカイブ。
  12. ^ 「Windows の管理: Windows Vista カーネルの内部: パート 1」 . Technet.microsoft.com . 2016 年 11 月 14 日. 2016 年 12 月 9 日閲覧。
  13. ^ 「アーカイブコピー」 . blog.gabefrost.com . 2008年2月19日時点のオリジナルよりアーカイブ。2022年1月15日閲覧。{{cite web}}: CS1 maint: アーカイブされたコピーをタイトルとして (リンク)
  14. ^ a b「テクニカルノートTN2028：スレッディングアーキテクチャ」 . developer.apple.com . 2019年1月15日閲覧。
  15. ^ 「Machスケジューリングとスレッドインターフェース」developer.apple.com。2019年1月15日閲覧。
  16. ^ [1] 2011年8月11日アーカイブ、 Wayback Machine
  17. ^ a b c Jones, M. (2018-09-18) [初版2009-12-14]. 「Linux 2.6 Completely Fair Scheduler の内側」 . developer.ibm.com . 2024年2月7日閲覧。
  18. ^ Molnár, Ingo (2007-04-13). 「[パッチ] モジュラースケジューラコアと完全に公平なスケジューラ [CFS]」 . linux-kernel (メーリングリスト).
  19. ^ Tong Li、Dan Baumberger、Scott Hahn. 「分散重み付けラウンドロビンを用いた効率的かつスケーラブルなマルチプロセッサ公平スケジューリング」（PDF） . Happyli.org . 2016年12月9日閲覧。
  20. ^ 「EEVDFスケジューラはLinux 6.6に搭載​​される予定」 Phoronix 2023年8月31日閲覧。
  21. ^ 「EEVDFスケジューラがLinux 6.6に統合され、Intelハイブリッドクラスタースケジューリングが再導入されました」 www.phoronix.com . 2024年2月7日閲覧。
  22. ^ 「Linux用EEVDF CPUスケジューラ [LWN.net]」 . LWN.net . 2023年8月31日閲覧。
  23. ^ 「Sched_extがLinux 6.12に統合 - スケジューリングポリシーをBPFプログラムとして」 www.phoronix.com 2025年2月10日閲覧。
  24. ^ 「プラグ可能なCPUスケジューラ - openSUSE Wiki」 . en.opensuse.org . 2025年2月10日閲覧。
  25. ^ a b「Solaris、Linux、FreeBSDカーネルの比較」(PDF)。 2008年8月7日時点のオリジナル(PDF)からのアーカイブ。

参考文献

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Scheduling_(computing)&oldid=1335245115#SCHEDULER」より取得