リアルタイムシステム LDF

リアルタイムシステム
2006/11/24
LDF
• スケジュールを後ろから作る
• 最も遅いデッドラインを持つタスクを最初に選ぶ
• 計算量O(n^2)で最大遅れ時間を最小化するスケ
ジュールを作成可能
• 制約
– 全てのタスクの起動時刻を同じにする必要がある
• 利点
– タスクの実行順序が決められている場合でもスケジューリ
ングができる
1
実行順序つきEDF
• プリエンプトを許すことにより，タスクに実行順
序がある場合でもEDFでスケジューリングで
きるようにしたもの
• タスクの起動時間とデッドラインを変換するこ
とにより，実行順序を作り出す
Rate Monotonic（RM)
•
•
起動周期の短いタスクほど優先度を高くする
静的スケジューリング
•
制限
– タスク間が独立であること
– 周期的タスクを対象とする
– デッドライン(Di)=周期(Ti)であること
•
利点
– （静的スケジューリングの中では）RMを使用してもスケジュールできない周期
的タスクをスケジュールできるアルゴリズムはない
– 短周期タスクのジッタがない
– デッドライン違反が起こるときは必ず長周期タスクから起こる
•
欠点
– CPU利用効率が悪くなることがある
2
LLFとESF
• LLF（Least Laxity Frist)
– タスクの余裕時間(Di-Ci)の最も小さいタスクに最
高のプライオリティを与える
• ESF(Earliest Start time First)
– 実行可能なタスクから実行する
– リソース制約の解消に重点を置く動的スケジュー
リング方式
最適化・経験的スケジューリング法
• 最適化スケジューリング法
– EDF,LLF,RMなど
– 目的とするスケジュール評価関数の最適値を見つけることができる
• 経験的スケジューリング法
– EDFとESFを合体させたものなど
– 最適値を見つけられない
– おおむね実行可能なスケジュールを見つけることが可能
– EDFとESFを合体させたもの
• Di + W × esti の小さいタスクほど高い優先度を与える
– esti：スタート可能時刻 W：経験的定数（3~6が使われる）
• マルチプロセッサ 環境でも使用できる
3
Deadline Monotonic（
DM）
• RM法をTi≧Diに拡張したもの
• デッドラインの早いものがプライオリティが高
くなる
• 最大遅れ時間に対して最適
4