![](https://csdnimg.cn/release/download_crawler_static/88173521/bg1.jpg)
An Evaluation of Adaptive Partitioning of
Real-Time Workloads on Linux
Andrea Stevanato, Tommaso Cucinotta, Luca Abeni
Scuola Superiore Sant’Anna , Pisa, Italy
{a.stevanato,t.cucinotta,l.abeni}@santannapisa.it
Daniel Bristot De Oliveira
Red Hat, Inc., Pisa, Italy
bristot@redhat.com
Abstract—This paper provides an open implementation and
an experimental evaluation of an adaptive partitioning approach
for scheduling real-time tasks on symmetric multicore systems.
The proposed technique is based on combining partitioned EDF
scheduling with an adaptive migration policy that moves tasks
across processors only when strictly needed to respect their tem-
poral constraints. The implementation of the technique within the
Linux kernel, via modifications to the SCHED
DEADLINE code base,
is presented. An extensive experimentation has been conducted
by applying the technique on a real multi-core platform with
several randomly generated synthetic task sets. The obtained
experimental results highlight that the approach exhibits a
promising performance to schedule real-time workloads on a real
system, with a greatly reduced number of migrations compared
to the original global EDF available in SCHED
DEADLINE.
Index Terms—Real-Time Scheduling, Real-Time Operating
Systems, Linux Kern el
I. INTRODUCTION
Nowa days, proc e ssing platforms stopped evolving towards
higher and higher frequencies, taking a tight turn towards
multi-core and multi-processor a rchitectures. This allowed
manufacturers to keep deploying hardware with consistently
higher and higher computing capabilities, overcoming the
thermal and heat dissipation problems which led to the non-
practicality of releasing microproc essors with frequency be -
yond 5 GHz for the genera l public [1].
Parallel computing platforms are not only taking off
in personal and general-purpose compu ting (beside s high-
performance co mputing, wh e re they have be en th e standard
for decades). They are also becom ing increasingly adopted and
playing a key role in embed ded and real-time systems, where
the growing richness of the required features implies the use of
more and more powerful processing platforms [2], often made
available through multi-core architectures, GPU and FPGA
acceleration [3]. He nce, it is becoming increasingly importa nt
to design efficient and practical scheduling techniques for real-
time applications on multi-core and multi-processor platforms.
However, this is known to be a non-trivial problem [4].
Multi-core real-time sched ulers are gen erally descr ibed [5]
as global or partitioned schedulers. In the former case, tasks
can be migr ated among cores to respect some scheduling
invariant, whilst in the latter one tasks are statically partitioned
This project has received funding from the European Union’s Horizon
2020 research and innovation programme under grant agreement No. 871669
AMPERE – “A Model-driven development framework for highly Parallel and
EneRgy-Efficient computation supporting multi-criteria optimisation”.
among the available CPU cores, a nd a single-processor sched-
uler can be used on each core. A useful trade- off betwee n
these two extremes is the one of clustered schedulers, where
cores ar e partitioned in clusters, tasks are statically assigned
to c lusters and scheduled globally within each cluster.
An interesting new approach that tries to reconcile these
different scheduling a pproaches exploiting their advantages is
represented by adaptive partitioning EDF (apEDF) [6], [7].
This technique consists in combining an EDF-based parti-
tioned r eal-time scheduler, with a policy for dynamic migration
of tasks among cores until a schedulable task partition ing is
reached, if possible. At such point, migrations stop and the
scheduler converges to a partitioned scheduler. This happens
for example if a first-fit allocation policy is used, and the task-
set satisfies well-known conditions on its tota l utilization [8],
[9], making the technique viable for hard real-time workloads.
Even when said conditions are not verified, if a schedulable
tasks partitioning doe s not exist, adaptive partitioning falls
back to approximatin g global EDF [6], so that interesting p rop-
erties of such an approach can be preserved, like the bounded
tardiness, making it suitable for soft real-time workloads.
However, although the adaptive partitioning approach seems
to have promising properties, it has not been implem ented
in a real scheduler yet, having only been evaluated through
simulations, to the best of our knowledge.
In this paper, we present the first implementation of an
adaptively partitioned EDF scheduler, based on Linux, an
increasingly attractive operating system (OS) for real-tim e
workloads. Currently, Linux supp orts glo bal EDF scheduling
via the SCHED
DEADLINE policy [10]
1
. Motivated by th e results
found by simulation in [6], [7], where apEDF has been shown
to possess a distinguishe d advantage over a global schedul-
ing approach, we implemented apEDF in Linux modifying
SCHED
DEADLINE, re placing its migration mechanism (which
implements global EDF by default) with a new mechanism
based on ap EDF. The new scheduler, which is made available
as an open-sourc e patch to SCHED
DEADLINE for the commu-
nity, is thoroughly evaluate d by running synthetic randomly
generated task sets, as co mmon in the real-time scheduling
community, in the simplifying scenario of independent (non-
interacting) pe riodic real-time tasks. The obtained results show
that the modified scheduling policy performs better than the
1
More information about the SCHED
DEADLINE can be
found in the official Linux kernel documentation at
https://www.kernel.org/doc/Documentation/scheduler/sched-deadline.txt