Optimizing utilization with the EDF scheduler

Mr. Efficient

Linux kernel 3.14 added an optional scheduling method known as Earliest Deadline First (EDF). EDF scheduling uses a scheme where the process closest to its deadline is the next process scheduled for execution.

EDF is mainly used in systems that need to meet time requirements, and it has been known to handle tasks on time even in cases for which common priority-driven scheduling fails (see Figure 1 and the "Utilization" box).

Utilization

The utilization of a single-core system may usually only be at a maximum of 69 percent for priority-driven scheduling and still process tasks on time. The Earliest Deadline First scheduler, on the other hand, allows almost 100 percent utilization of the system.

Utilization is a measure of whether the tasks of a real-time system comply with time limits in all circumstances. Utilization is similar to load, but it is calculated according to a slightly different formula,

where the numerator is the maximum processing time (Worst Case Execution Time, WCET) of task j , t _{Dmax ,j } is its maximum completion time (maximum deadline), and t _{Pmin ,j } is its minimum time interval before waking the same task (period).

If, with priority-controlled scheduling, utilization is smaller or equal as a function of the number of

...

Use Express-Checkout link below to read the full article (PDF).