Posted at

Deadline scheduler 覚書

More than 3 years have passed since last update.

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 を補給