SCHED_DEADLINE

 

Short introduction

 

This is the implementation of a new scheduling class called SCHED_DEADLINE for the Linux Kernelmade by Dario Faggioli and Jury Lelli. The scheduling class implements the real-time scheduling algorithm called Earliest Deadline First (EDF), one of the most common real-time scheduling algorithms.

 


 

Why do we need a further scheduling class ?

 

The need of an EDF scheduler in Linux was already highlighted in the Documentation/scheduler/sched-rt-group.txt file, which said

"The next project will be SCHED_EDF (Earliest Deadline First scheduling) to bring full deadline scheduling to the linux kernel."

The existing scheduling classes (i.e., sched_fair and sched_rt), in fact, perform very well in their own domain of application. However,

1. They cannot provide the guarantees a time-sensitive application may require.
Using sched_fair, no concept of timing constraint (e.g., deadline) can be associated to tasks. In fact, although it is possible to assign a share of the processor time to a task (or a group of tasks), there is no way to specify that a task must execute for 20msec within 100msec, unlike using a real-time scheduling algorithm, such as EDF.
As a proof of concept, we implemented a very simple test to run two tasks that need to execute for 20msec every 50msec. We scheduled them using CFS with the same CPU share, and we observed that even if there is enough spare CPU time (the system is idle), the tasks occasionally experience some deadline miss. The test is available here . 
Using sched_rt, instead, we can give that kind of guarantee only using a global period, with the constraint that "a subgroup must have a smaller or equal period to its parent".

2. The latency experienced by a task (i.e., the time between two consecutive executions of a task) is not deterministic and cannot be bound, since it  highly depends on the number of tasks running in the system at that time.
Using EDF, instead, this time is deterministic, bounded and known at any instant of time.

These issues are particularly critical when running time-sensitive or control applications. Without a real-time scheduler, in fact, it is not possible to make any feasibility study of the system under development, and developers cannot be sure that the timing requirements will be met under any circumstance. And we feel that this prevents the usage of Linux in industrial contexts.

A key feature of our scheduling class is that "temporal isolation" is ensured. This means 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 execution times than the amount it has been allocated.

Each task is characterized by a "budget" sched_runtime and a "period" sched_period, equal to its deadline.
At any instant of time, the system schedules the (ready) task having earliest deadline. During execution, task's budget is decreased by an amount equal to the time executed. When task's budget reaches zero (i.e., the task executed for a time equal to its budget), it is stopped until the time instant of its next deadline. At that time, the task is made runnable again, its budget is refilled and a new deadline is computed.
This means that the 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 throughput available on the system (i.e., 100% on uniprocessor systems), otherwise the system is overloaded and task deadlines cannot be guaranteed.

When a task tries to execute more than its budget, it is slowed down, by stopping it until the time instant of its next deadline. When, at that time, it is made runnable again, its budget is refilled and a new deadline is computed.
 

Some notes about the implementation:

  • It implements the well-known Earliest Deadline First (EDF) algorithm
  • It is aligned with the current mainstream kernel
  • It does not make any restrictive assumption about the characteristics of the tasks: it can handle periodic, sporadic or aperiodic tasks
  • O.going effort for integration with the cgroups filesystem; this will let to  assign a reservation to a group of tasks and make hierarchical scheduling.

 


 

Releases

 

1. The first version of the scheduler was submitted to LKML on September 22nd 2009. At that time, its name was still SCHED_EDF. The email containing the scheduler started a very productive thread of discussion composed by around 55 emails.

2. The first version of the scheduler after the name changed to SCHED_DEADLINE was submitted to LKML on October 16th 2009.

3. The second version of the scheduler has been submitted to LKML on February 28th 2010, and it had a first implementation of the Deadline Inheritance protocol.

4. The third version of the scheduler has been submitted to LKML on October 29th 2010, and it adds support for global/clustered multiprocessor scheduling through dynamic task migrations.

5. The fourth version of the scheduler has been submitted to LKML on April 6th 2012, and it improves and resolvers many open issues.

6. The fifth version of the scheduler has been submitted to LKML on May 22th 2012.

7. The sixth version of the scheduler has been submitted to LKML on October 24th 2012.

8. The seventh version of the scheduler has been submitted to LKML on February 11th 2013. Internal math has been restricted to microseconds resolution (to avoid overflows) and the RFC tag has been removed.

9. The eighth version of the scheduler has been submitted to LKML on October 14, 2013.

10. The ninth version of the scheduler has been submitted to LKML on November 7, 2013.   

The scheduler has been merged in the official Linux kernel and will be part of the next stable 3.14 kernel release.


 

Related papers

 

1. Dario Faggioli, Fabio Checconi, Michael Trimarchi, Claudio Scordino, An EDF scheduling class for the Linux kernel, 11th Real-Time Linux Workshop (RTLW), Dresden, Germany, September 2009.

2. Nicola Manica, Luca Abeni, Luigi Palopoli, Dario Faggioli, Claudio Scordino, Schedulable Device Drivers: Implementation and Experimental Results, International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Brussels, Belgium, July 2010.

3. Juri Lelli, Giuseppe Lipari, Dario Faggioli, Tommaso Cucinotta, An efficient and scalable implementation of global EDF in Linux,    International Workshop on Operating Systems Platforms for Embedded  Real-Time Applications (OSPERT), Porto (Portugal), July 2011.

4. Andrea Parri, Juri Lelli, Mauro Marinoni, Giuseppe Lipari, Design and Implementation of the Multiprocessor Bandwidth Inheritance Protocol on Linux, 15th Real-Time Linux Workshop (RTLWS), Lugano-Manno, Switzerland, October 2013.

The project has been also presented at the Kernel Summit in 2010 ([1] [2]), at the Linux Plumbers Conference 2012 ([1] [2]) and at the Embedded Linux Conference 2013.

 


Web pages that talked about the project

· OSNews:

· Slashdot:

· Linux Weekly News (LWN):

· Freshmeat:

· Ericsson:

· Page on Actors website:

· LinkedIn:

· Linux Today:

· Wikipedia:

· Youtube:

 


     

    Download and usage

     

    A public git repository is available at the following address:

    git clone git://github.org/jlelli/sched_deadline.git

    Information about download and usage is available here .