Dario Faggioli, Scuola Superiore Sant'Anna, Pisa, Italy
Michael Trimarchi, Evidence Srl, Pisa, Italy
Fabio Checconi, Scuola Superiore Sant'Anna, Pisa, Italy
Claudio Scordino, Evidence Srl, Pisa, Italy

Linux is a General Purpose Operating System (GPOS) originally designed to be used in server or desktop environments. Since then, Linux has evolved and grown to be used in almost all computer areas.

An important part of Linux is the process scheduler (or simply the scheduler). This component of the kernel selects which process to execute at any instant of time, and is responsible of dividing the finite resource of processor time between all runnable processes on the system.

During the last years, there has been a considerable interest in using Linux also for real-time control systems, from both academic institutions and companies. The main reason for this raising interest is the free availability of the source code, under the terms of the GPL license. The free availability implies that using Linux in industrial devices is more convenient than using other commercial operating systems (which are typically very expensive or subject to royalties). The availability of the source code, moreover, allows software developers to further improve the already excellent performance of Linux by customizing the source code according to their specific needs.

Unfortunately, Linux has not been designed to be a Real-Time Operating System (RTOS), thus not much attention has been given to real-time issues. The default scheduling policies of Linux (i.e., SCHED_NORMAL and SCHED_BATCH) perform very well in their own domains of application, but cannot provide any guarantee to time-sensitive tasks. To make an example, there is no way of specifying that a task must execute for 20msec every 100msec. In addition, the time between two consecutive executions of a task is not deterministic and highly depends on the number of tasks running in the system at that time.

Linux also provides some POSIX-compliant fixed-priority scheduling policies (i.e., SCHED_RR and SCHED_FIFO). These policies, however, are not much sophisticated and often do not suit the specific application requirements. No concept of time is associated to these policies, therefore it is not possible to set any deadline for the tasks. Moreover, it is known from the real-time literature that, on uniprocessor systems, fixed-priority policies cannot guarantee real-time constraints when the processor is fully loaded: schedulability analysis for fixed-priority algorithms, in fact, can guarantee real-time constraints only for processor utilizations below a certain threshold, which depends on the characteristics of the task set and that can be as lower as 69% for uniprocessors.

These issues are particularly critical when designing time-sensitive or control applications (e.g., MPEG players) for embedded devices like smart-phones. These devices, in fact, are characterized by constraints on size, power consumption and cost.  Embedded system designers, therefore, need to obtain the maximum performance from the embedded processor, in order to meet the timing constraints of the application even with not powerful hardware. Fixed-priority policies cannot ensure real-time constraints when the processor utilization is above a certain threshold, therefore they do not allow to fully exploit the performance of embedded systems. On the other hand, without a deterministic real-time policy, it is not possible to make a feasibility study of the system under development, and developers cannot be sure that the timing requirements of tasks will be met under any circumstance. These issues are among the ones that prevent the usage of Linux in real industrial contexts.

To overcome these problems, some companies operating in the industrial market started selling modified versions of the Linux kernel with some kind of support for real-time scheduling. However, these non-standard versions of Linux often are not free, vanishing the main reason for using Linux in industrial contexts. Moreover, they do not have the support of the huge development community of the standard kernel.

Real-time institutions and independent developers, on the other hand, have proposed some real-time extensions to the Linux scheduler during the last years. Unfortunately, none of these extensions eventually became part of the official Linux kernel. In the meantime, the Linux scheduler has been rewritten from scratch more than once. Very recently, the addition of further scheduling policies has been made easier through the integration of some mechanisms inside the standard scheduler itself. The latest Linux scheduler (i.e., CFS), in fact, is a modular scheduler: It allows to define further scheduling policies and to add new schedulers to handle the policies introduced. The binding between the new policy and the new scheduler is done through a set of "hooks'' (i.e., function pointers) at kernel level.

We believe that to be very "general'', Linux should also provide enhanced real-time scheduling support, still allowing to schedule non-real-time tasks in the usual way. In this paper, thus, we propose an implementation of the Earliest Deadline First (EDF) algorithm. This is a dynamic-priority algorithm well-known in the real-time literature. One interesting feature of this algorithm is that, on single processor systems, it can guarantee real-time constraints even when the processor is fully utilized (i.e., utilization equal to 100%). The new scheduling policy introduced by our implementation has been called SCHED_EDF.

With respect to similar work proposed in the past, our implementation takes advantage of the modularity offered by the new Linux scheduler, leaving the current behavior of existing policies unchanged. The new scheduling class is integrated with the latest Linux scheduler, and relies on standard Linux mechanisms (e.g., control groups), thus it natively supports multicore platforms and provides hierarchical scheduling through a standard API. Our implementation does not make any restrictive assumption on the characteristics of the task. Thus, unlike other schedulers, it can handle both periodic and aperiodic tasks.

A very interesting feature of this scheduling class is the "temporal isolation'' among the tasks handled. The temporal behavior of each task (i.e., its ability to meet its deadlines) is not affected by the behavior of the other tasks: if a task misbehaves and requires a large execution time, it cannot monopolize the processor. Thanks to the temporal isolation property, each task executes as it were on a slower dedicated processor, so that it is possible to provide real-time guarantees on a per-task basis. Such property is particularly useful when mixing hard and soft real-time tasks on the same system.

The paper is organized as follows. At the beginning we introduce definitions and characteristics concerning real-time systems as well as the scheduling model that will be used throughout the rest of the paper. Then, a brief overview of most notable approaches and implementations proposed in the last decade is provided. The current Linux scheduler (i.e., CFS) is explained, focusing on the modular facilities that it offers. We then describe the internals of the proposed implementation (i.e., SCHED_EDF), and we show how it has been integrated with existing mechanisms available on Linux (e.g., control groups). A full description of the API available at user-level is provided. Last but not least, our implementation is evaluated and validated through a set of tests and experiments on real hardware that will help understanding the main differences between SCHED_EDF and the existing scheduling policies already available on Linux.