Luca Abeni, University of Trento
Claudio Scordino, Evidence Srl
Juri Lelli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa, Italy
Luigi Palopoli, University of Trento

The SCHED_DEADLINE scheduling policy (implementing a reservation-based CPU scheduler based on the Constant Bandwidth Server algorithm) has just been merged in the mainline Linux kernel. Such a scheduling policy allows to associate (Q,T) pairs to real-time tasks, meaning that a task is reserved an amount of execution time Q (the task's runtime, or maximum budget) every reservation period T. In this way, it is possible to provide guaranteed real-time performance by properly dimensioning the runtime Q and the period T based on the task parameters (execution time and activation pattern). However, if a task exhibits relevant variations in its execution or inter-activation times, a pure reservation-based scheduler such as SCHED_DEADLINE can cause system underutilisation or resource waste, because the CPU time reserved to the task can often be left unused (especially when considering hard real-time tasks and dimensioning the scheduler parameters on the worst-case task's parameters). This problem can be solved by using a proper CPU reclaiming algorithm; however, while many different reclaiming algorithms have been proposed in literature none of them has been implemented in Linux yet.

This paper describes the implementation of the GRUB reclaiming algorithm based on Linux/SCHED_DEADLINE, and presents some experimental results showing the effectiveness and usefulness of the presented modifications to SCHED_DEADLINE.