Home

Introduction

This is the implementation of a new scheduling class called SCHED_DEADLINE for the Linux kernel. The scheduling class implements the real-time scheduling algorithm called Earliest Deadline First (EDF), one of the most common real-time scheduling algorithms.

The project has been started by Evidence srl within the FP7 European project called ACTORS (now completed) the which the company was participating with, among the others, Ericsson AB, AKatech SA, Xilinx, and others (full list here).

Real-time scheduling techniques, such as EDF, allows for the possibility of analyzing the system and enforcing, either statically (off-line) or dynamically (on-line) determinism for the running tasks. We feel that this might be particularly beneficial for time-sensitive workloads, such as multimedia and/or control applications, where it may be important to be guaranteed that some timing requirements will be met under any circumstance.

We feel that this prevents will improve the potentialities of Linux for many industrial contexts, including some of the ones addressed by the partners of the ACTORS project. Official information about SCHED_DEADLINE and the ACTORS project can be found at Evidence srl SCHED_DEADLINE page.

Key Features

The existing Linux scheduling policies cannot provide the guarantees a time-sensitive application may require. For example, although it is possible to assign a fair share of the processor to (a group of) task(s), no concept of actual timing constraints, e.g., deadlines, can be associated to it (them).

Moreover, the the time between two consecutive executions of a task is not deterministic, and no bound can be found for it, as this is easy to calculate under EDF (if the system is not overloaded!).

Finally, SCHED_DEADLINE also provides “temporal isolation”, meaning that the temporal behavior of each task (i.e., its ability to meet its deadlines) is not affected by the behavior of any other task in the system. In other words, even if a task misbehaves, it is not able to exploit larger CPU share than the amount it has been allocated, with its own —strictly enforced— periodicity.

Algorithm Basics

Each task is characterized by a “budget” (sched_runtime) and a “period” (sched_period, equal to its deadline). At any time, the system schedules the ready task(s) having the earliest deadline(s). During execution, the budget is decreased by an amount equal to the time executed. When a task’s budget reaches zero (i.e., the task executed for a time interval equal to its budget), the task is stopped until the time instant of its next deadline. At that point, the task is resumed, its budget is refilled and a new deadline is computed.

This means that each task is guaranteed a share of processor time equal to sched_runtime/sched_period every sched_period. Of course, the sum of sched_runtime/sched_period of all tasks cannot be higher than the total bandwidth available in the system (usually equal to the number of CPUs), uniprocessor systems), otherwise deadlines cannot be guaranteed any longer.

Additional infos

Check out our TODOs list.