Earliest Deadline First Scheduling

linux/Documentation/scheduler/sched-rt-group.txtを見たところ、EDFスケジューリングというものについて記述があったので調べてみた。

Earliest deadline first scheduling - Wikipedia, the free encyclopedia

考え方は単純で、最も早くデッドラインが来るタスクを優先的に実行するというものである。これにより、CPU消費率が100%になるまではデッドラインを必ず守ることが出来る。

ただ、実装面では優先順位が動的に変わる（デッドラインが短いタスクが実行された場合、それの優先順位が高くなり、実行中だったタスクの優先順位が下がる）ので大変であったり、マルチプロセッサ環境ではこれが最適ではなくなったりするようである。

ここで、sched-rt-group.txtに書いてあった記述を引用してみる

CPU time is divided by means of specifying how much time can be spent running

in a given period. We allocate this "run time" for each realtime group which

the other realtime groups will not be permitted to use.

Any time not allocated to a realtime group will be used to run normal priority

tasks (SCHED_OTHER). Any allocated run time not used will also be picked up by

SCHED_OTHER.

Let's consider an example: a frame fixed realtime renderer must deliver 25

frames a second, which yields a period of 0.04s per frame. Now say it will also

have to play some music and respond to input, leaving it with around 80% CPU

time dedicated for the graphics. We can then give this group a run time of 0.8

* 0.04s = 0.032s.

This way the graphics group will have a 0.04s period with a 0.032s run time

limit. Now if the audio thread needs to refill the DMA buffer every 0.005s, but

needs only about 3% CPU time to do so, it can do with a 0.03 * 0.005s =

0.00015s. So this group can be scheduled with a period of 0.005s and a run time

of 0.00015s.

The remaining CPU time will be used for user input and other tasks. Because

realtime tasks have explicitly allocated the CPU time they need to perform

their tasks, buffer underruns in the graphics or audio can be eliminated.

NOTE: the above example is not fully implemented yet. We still

lack an EDF scheduler to make non-uniform periods usable.

NOTEを見ると、一定周期ではないものに関してEDFスケジューラとして正しく動作しないようである。

また、同ファイルの3. Future plansには

The next project will be SCHED_EDF (Earliest Deadline First scheduling) to bring

full deadline scheduling to the linux kernel. Deadline scheduling the above

groups and treating end of the period as a deadline will ensure that they both

get their allocated time.

Implementing SCHED_EDF might take a while to complete. Priority Inheritance is

the biggest challenge as the current linux PI infrastructure is geared towards

the limited static priority levels 0-99. With deadline scheduling you need to

do deadline inheritance (since priority is inversely proportional to the

deadline delta (deadline - now)).

とあり、サブグループへの優先度の継承が難しいようだ。