What is Deadline Scheduling in Linux?

Real-time operating systems are ubiquitous in industries such as automotive and aerospace where systems are required to operate under strict timing constraints with possible catastrophic consequences for failure.

In real-time systems, tasks must be executed both with the correct behaviour and within precise timing constraints. In other words, a task is only executed correctly if it produces the correct logical result before some deadline. In a multi-tasking operating system such as Linux, a scheduler is responsible for coordinating access to hardware resources, such as the CPU. The Linux scheduler supports different scheduling policies depending on the workload, and for non-real-time workloads, scheduling policies such as SCHED_OTHER and SCHED_NORMAL are sufficient. For real-time workloads, the Linux scheduler supports some additional policies and adds support for pre-emption: temporarily pausing a running task to allow a high priority one to run instead.

Due to the industry demands for real-time systems, this article explores Linux's capabilities to meet real-time schediuling constraints. This article details how real-time scheduling works in Linux, specifically deadline scheduling, including its limitations and how to mitigate those limitations.

To schedule real-time tasks Linux provides two schedulers: the POSIX real-time scheduler, and the deadline scheduler.

The POSIX real-time scheduler, which provides the first-in-first-out (FIFO) and round-robin (RR) scheduling policies, schedules each task according to its priority. The task with the highest priority is scheduled first. These scheduling policies differ only when tasks have the same priority. The FIFO scheduler will schedule the task which arrived first running it till completion or until it yields. The RR scheduler will schedule tasks in a round-robin fashion, executing each task up until a maximum amount of time, at which point the next task execution is started and the current task is moved to the back of the queue.

Deadline scheduling works very differently; it instead schedules each task according to the task’s deadline. The task with the promptest deadline will be served first. This means that when a task is requesting to be scheduled, it is required to provide parameters about its deadline and execution. These parameters are provided to the scheduler via the sched_setattr syscall:

Period: the time between providing the task it's runtime again, and the last time it was provided, in nanoseconds.

Deadline: the time from the start of the period by which the thread must have finished its execution for that period, in nanoseconds.

Runtime: the thread’s expected worst-case execution time in each period, in nanoseconds.

Reclaim (optional): whether the kernel should provide the thread with unused CPU time in a period if the thread hadn’t finished its execution

For example a process scheduled with:

#define SCHED_DEADLINE 6

struct sched_attr attr = {0}; attr.size = sizeof(attr);
attr.sched_policy = SCHED_DEADLINE;

/* Configure time parameters in nanoseconds */
attr.sched_runtime = 10 * 1000 * 1000;  /* 10 ms CPU runtime */ attr.sched_deadline = 20 * 1000 * 1000; /* 20 ms relative deadline */ attr.sched_period = 30 * 1000 * 1000;   /* 30 ms period */

Would repeat every 30 milliseconds, and would be finished by the 20th millisecond in each of those 30 millisecond blocks. The process would be allowed to run for 10 milliseconds. This can be visualised as:

Although the deadline schedulers parameters look complex, they attempt to remove the complexity from the calling process. The scheduler hides the complexity of deciding task priority and fitting the task’s execution around other scheduled tasks.

Because the deadline scheduler knows the required CPU time for each deadline task, it is able to stop the system becoming overloaded by implementing a check for each new schedule. This acceptance test by default works to keep the utilisation of a core at less than 95%, therefore allowing some CPU time for system tasks to run. This acceptance test is controlled by kernel.sched_rt_runtime_us and kernel.sched_rt_period_us sysctl configs, which default to 950000 and 1000000 respectively.

This is sufficient for a single-core system, however for a multi-core system this is not. Dhall’s effect shows how the global deadline scheduler acceptance test is unable to schedule a task even though there is sufficient CPU time.

This limitation can be avoided by manual partitioning of the system into ‘cpusets’ each containing one CPU. This is advantageous as it allows for deadline scheduling in a multicore system to have a higher overall utilisation, however it pushes the responsibility of managing this configuration onto the user.

Common questions at this point are: how do these different schedulers interface with each other? Should the user manage the interface between deadline scheduled tasks and other tasks?

The deadline scheduled tasks have a higher priority than any other tasks, including other real-time tasks such as FIFO or RR scheduled tasks. Therefore, for deadline scheduled tasks, there is no need to consider the current state of real-time or normal scheduled tasks. However, there is the risk of non-deadline tasks being pushed aside.

This concern can also be addressed using ‘cpusets’ and solid system architecture, by dividing the CPUs into different sets depending on the systems requirements. For an 8-core machine, that needs to run deadline, round-robin and normal tasks the cores could be divided as:

Core 1: Deadline tasks
Core 2: Deadline tasks
Core 3 and 4: RR tasks
Core 5 to 8: All other tasks

The deadline scheduler is heavily associated with the PREEMPT_RT patch set, which was a separate patch set but has since merged into the mainline Linux kernel. The aim of this patch set was to reduce the time that a lower priority task could block access to a core, while a higher priority task(s) waited in the wings. It works by reducing the time a task can run with IRQs and preemption disabled.

Overall this article has outlined Linux scheduling, specifically Linux deadline scheduling, some common pitfalls with it, and how it relates to the PREEMPT_RT patch set.