User Tools

Site Tools


sched_deadline

This is an old revision of the document!


SCHED_DEADLINE

Introduction

SCHED_DEADLINE is the name of a patch proposed to add a resource-reservation real-time CPU scheduler to the Linux kernel.

The Linux kernel contains different scheduler classes. By default the kernel uses a scheduler mechanism called Completely Fair Scheduler, introduced in the 2.6.23 version of the kernel. Internally this default-scheduler class is also known as SCHED_OTHER. The standard Linux kernel also contains two real-time scheduling classes named SCHED_FIFO (realtime first-in-first-out) and SCHED_RR (realtime round-robin) both of which take precedence over the default class. The SCHED_DEADLINE patch adds a new scheduling class to the modular Linux scheduler, and implements the well-known Earliest Deadline First (EDF) algorithm.

The project was initially financed by the European commission through the ACTORS FP7 project. The first version of the patch was called SCHED_EDF and [presented to the Linux kernel community in 2009. With this name was also presented to the Real-Time Linux Workshop after a few weeks. The name has been then changed to SCHED_DEADLINE after the request of the Linux kernel community.

The project is carried out jointly by the Real-Time Systems Laboratory of Scuola Superiore Sant'Anna and the company Evidence Srl.

Motivation

The need of an EDF scheduler in Linux has been for a long time in the mind of a part of the Linux community. The file Documentation/scheduler/sched-rt-group.txt, for example, says

“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_OTHER, 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 (otherwiise the RT-APP application can be used for similar tests). Using SCHED_FIFO/SCHED_RR, 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”.

  1. 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
  • On-going effort for integration with the cgroups filesystem, which will let to assign a reservation to a group of tasks and make hierarchical scheduling.

Releases

Academic conferences and events

Web pages

Download and usage

sched_deadline.1386682140.txt.gz · Last modified: 2013/12/10 13:29 by claudio_scordino