Help us understand the problem. What is going on with this article?

Deadline scheduler 覚書

More than 5 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 を補給
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away