Least Slack Time
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2009/09/16 05:52 UTC 版)
Least Slack Time(LST)は、スケジューリングアルゴリズムの一種。プロセスの slack time (余裕時間)に基づいて優先度を設定する。Least Laxity First(LLF)とも呼ばれる。一般に組み込みシステム、特にマルチプロセッサシステムで使用されている。LSTを使用する場合、各プロセッサ上の各プロセスは同じ実行時間を備え、プロセスが特定のプロセッサにアフィニティ(Affinity)を持つことがないという制約がある。この制約によって組み込みシステムへの適合性が高くなっている。
Slack time
このスケジューリングアルゴリズムは、slack timeが最小なプロセスを選択して実行する。slack timeとは、デッドラインまでの時間、実行可能となるまでの時間、実行時間の一時的な差と定義される。
より形式的に slack time を定義すれば、以下の式で表される:
(d − t) − c'
ここで d はプロセスのデッドライン、すなわち現時点から d までの間にそのプロセスの処理をしなければならないことを意味する。t は現時点から実行サイクルが開始されるまでの時間であり、プロセスはそれより先に実行することができない。c' は実行にかかる時間である。従って、slack time とは、そのプロセスを可能な限り早く実行するとしたときのデッドラインまでの余裕時間である。すなわち、このアルゴリズムは可能な限りプロセスの実行を後回しにしようとする。
適用分野
LSTスケジューリングは、イベント発生頻度に事前の仮定を置かないので、非周期的タスクから構成されるシステムで使い易い。LSTの主な弱点は、現在のシステム状態のみを見ていてその先どうなるかを全く考慮していない点である。従って、一時的なシステムリソースの過負荷が発生するとLSTは最適な方式とは言えなくなる。また、割り込み不可能なプロセスがある環境でも最適な動作を保証できない。しかし、Earliest Deadline Firstと同様(そしてレートモノトニックスケジューリングとは違って)、このアルゴリズムはプロセッサ使用率100%まで機能する。
関連項目
「Least Slack Time」の例文・使い方・用例・文例
- The Malay Times に掲載されていた、非常勤の下級アナリストの職に関する広告についてご連絡を差し上げています。
- 彼女の15 冊の出版物のうち10 冊が、Brooklyn Timesのベストセラーリストの首位を占めたという事実は、多くの人々が彼女のことを、肥満に苦しむ国の救済者だと考えている証拠である。
- 最近着の London Times に曰く
- オックスフォード運動の創設者の原則で、『Tracts for the Times』と呼ばれるパンフレットで提唱された
固有名詞の分類
- Least_Slack_Timeのページへのリンク
