Deadline scheduler 覚書

Earliest Deadline First (EDF)

• runtime … 実行可能時間
• period / deadline … 次の実行までのサイクルタイム（データが到着する感覚とか）

プロセスは period マイクロ秒毎に runtime マイクロ秒だけ実行できる。

runtime は period から deadline 内の線分上にある。

ただし EDF だけでは runtime が長いプロセスがいるときに deadline を守れないケースが出てくる。

そこで Linux の deadline スケジューラでは Constant Bandwidth Server (CVS) を利用している。

CBS では runtime, deadline, period に加えて scheduling deadline と current runtime を用いる。

• scheduling deadline … プロセスを実行させなければならない絶対時間の deadline
• current runtime … プロセスが実行できる残り時間

動作は次のようになる。

1. プロセス生成時に scheduling deadline, current runtime を 0 に設定
2. プロセスが ready になったとき次の条件判断
   • scheduling deadline が現在時刻より前である（既に過ぎてしまった）
   • current runtime / (scheduling deadline - current time) > runtime / period
     • 現状の runtime 比率 > period で実行されるべき runtime 比率
     • 右辺の定義を超えてしまうと scheduling deadline に間に合わない
3. 条件式が真であれば scheduling deadline を延長すると共に current runtime もフルにする
   • scheduling deadline = 現在時刻 + deadline; current runtime = runtime;
   • 間に合わないので猶予を持たせる
4. current runtime がプロセスを実際に実行した時間分減らされる
5. current runtime が 0 以下になったらプロセスを throttle した後、replenishment time（現在の schedule deadline）までプロセスは実行されなくなる
6. replenishment time になると current runtime が正になるまで次の式を実行
   • scheduling deadline += period; current runtime += runtime;
   • scheduling deadline を更新して runtime を補給