Least Slack Time

このスケジューリングアルゴリズムは、slack timeが最小なプロセスを選択して実行する。slack timeとは、デッドラインまでの時間、実行可能となるまでの時間、実行時間の一時的な差と定義される。

より形式的に slack time を定義すれば、以下の式で表される:

${\displaystyle (d-t)-c'}$

ここで ${\displaystyle d}$ はプロセスのデッドライン、すなわち現時点から ${\displaystyle d}$ までの間にそのプロセスの処理をしなければならないことを意味する。${\displaystyle t}$ は現時点から実行サイクルが開始されるまでの時間であり、プロセスはそれより先に実行することができない。${\displaystyle c'}$ は実行にかかる時間である。従って、slack time とは、そのプロセスを可能な限り早く実行するとしたときのデッドラインまでの余裕時間である。すなわち、このアルゴリズムは可能な限りプロセスの実行を後回しにしようとする。

LSTスケジューリングは、イベント発生頻度に事前の仮定を置かないので、非周期的タスクから構成されるシステムで使い易い。LSTの主な弱点は、現在のシステム状態のみを見ていてその先どうなるかを全く考慮していない点である。従って、一時的なシステムリソースの過負荷が発生するとLSTは最適な方式とは言えなくなる。また、割り込み不可能なプロセスがある環境でも最適な動作を保証できない。しかし、Earliest Deadline Firstと同様(そしてレートモノトニックスケジューリングとは違って)、このアルゴリズムはプロセッサ使用率100%まで機能する。

• スケジューリング
• Earliest Deadline First