作業節約スケジューラ

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

たとえば、ネットワークとパケットのスケジューリングを扱う場合、作業節約型スケジューラ^{[1] [2]は、送信するパケットがない場合にのみチャネルをアイドル状態のままにします。対照的に、非作業節約型スケジューラは、}送信待ちのパケットがある状態でチャネルをアイドル状態のままにすることがあります。

同様に、 CPUスケジューリング、つまり1つ以上の利用可能なプロセッサまたはコアにスケジュールされたスレッドまたはプロセスについて言えば、作業節約型スケジューラ^[3]は、実行準備ができているプロセス/スレッドがある場合にプロセッサ/コアがアイドル状態にならないようにします。

作業保存型スケジューラは、クラインロックの保存則に従うことでも有名です。^{[4] [5]}

ポアソン分布の到着率を持つパケットが単位時間あたりにそれぞれスケジュール時間を競い合う接続がある場合、レナード・クラインロックは次の保存則を確立しました。 ${\displaystyle N}$${\displaystyle \lambda_{n}}$

${\displaystyle \sum \limits _{n=1}^{N}\rho _{n}q_{n}=C}$どこ${\displaystyle \rho _{n}={\frac {\lambda _{n}}{\mu _{n}}}}$

• ${\displaystyle \lambda_{n}}$: 単位時間あたりのパケット数で表した接続の平均パケットレート。${\displaystyle n}$
• ${\displaystyle \mu_{n}}$: システム全体が単位時間あたりに送信できる接続パケットの数（パケット単位）。フローのパケット サイズが異なる場合、フロー間で異なる場合があります。${\displaystyle n}$
• ${\displaystyle \rho_{n}}$: 特定のフローによって寄与されたリンク使用率。
• ${\displaystyle q_{n}}$: スケジューラがパケットを処理する前に、接続からのパケットがバッファ内に留まると予想される時間 (単位: 時間)。${\displaystyle n}$
• ${\displaystyle C}$: 定数 - パケットが中断なく最大サービス レートで送信される場合、任意の時点ですべてのフローからバッファリングされたすべてのパケットをクリアするのに予想される時間。理由を理解するには、 に注目してください。はフローからバッファリングされるパケットの予想される数であり、したがって、バッファからパケットをクリアするのに予想される時間は、これをサービス レートで割った値であることに注意してください。${\displaystyle \rho _{n}q_{n}={\frac {\lambda _{n}q_{n}}{\mu _{n}}}$${\displaystyle \lambda_{n}q_{n}}$${\displaystyle n}$${\displaystyle \mu_{n}}$

(一部の情報源では、 を特定のパケットを処理する時間をパケットあたりの単位時間で表すために使用し、 を使用します。式は同じですが、唯一の違いは、 が上記の式の逆数であることです。) ${\displaystyle \mu_{n}}$${\displaystyle \rho _{n}=\lambda _{n}\mu _{n}}$${\displaystyle \mu_{n}}$

非作業節約型スケジューラは、コンピューティングおよび通信システムによって実行されるアクティビティの予測可能性を高め、終了ジッタを減らすのに役立つ場合があります。マルチプロセッサシステムでは、いくつかのシナリオでパフォーマンスを向上させるのに役立ちます。^{[6] [7]} 非作業節約型スケジューラは、システムの安定性を高めるのに役立つ場合があります。たとえば、実行可能なすべてのプロセスのワーキングセットの合計が使用可能なメモリを超え、非線形のページスラッシングオーバーヘッドにつながることが懸念される場合、プロセススケジューラはプロセスを実行キューに入れないように選択する場合があります。このように実行キューを制限すると、スラッシングのためにシステムが使用できなくなる状況を回避することを目的として、使用可能なプロセッサが十分に活用されない可能性があります（したがって、非作業節約型になります）。