Load-Balancing for a Real-Time System Based on
Asymmetric Multi-Processing∗Éric P IEL

Philippe M ARQUET
Julien S OULA
Jean-Luc D EKEYSER
www.lifl.fr/west/artis
Laboratoire d’informatique fondamentale de Lille
Université des sciences et technologies de Lille
FranceAbstract
ARTiS is a project that aims at enhancing the Linux kernel
with better real-time properties. It allows to retain the flexibility and ease of development of a normal application for
the real-time applications while keeping the whole powerof SMP (Symmetric Multi-Processors) systems for their execution.
Based on the introduction of an asymmetry between
the processors, distinguishing real-time and non real-timeprocessors, the system can insure low interrupt latencies
to real-time tasks. Furthermore, every processor can execute all the tasks, excepted when they request real-timeendangering functions. In this case the task is moved before continuing to be executed. A first version of ARTiS
has demonstrated this is technically possible. Unfortunately, the original load-balancing mechanism of Linux is
not aware of this enhanced design.
We have studied all the types of migration possible between the combinations of a real-time specialized processor and a general one. From the deducted requirements,
we have specified special mechanisms and policies taking
into account both performances and real-time specificities.
We are currently working on implementing those particular load-balancing functions within the ARTiS system.

1

Real-Time andLoad-Balancing on SMP

There exists two types of approach to obtain realtime properties from the Linux kernel. One consists
in running the RT tasks in a special designed kernel running in parallel, this is what does RTAI [2].
∗ This work is partially supported by the ITEA project 01010,
HYADES

The drawback is that the programming model andconfiguration methods are different from the usual
one: Linux tasks are not real-time tasks and realtime activities can not benefit of the Linux services.
The second approach relies on the shielded processors or asymmetric multi-processing principle. On a
multi-processor machine, the processors are specialized to real-time or not. Concurrent Computer Corporation RedHawk Linux variant [1] and SGI REACT IRIX variant [5] follow this principle. However,since only RT tasks are allowed to run on shieldedCPUs, if those tasks are not consuming all the available power then there is free CPU time which is lost.
ARTiS extends this second approach by also allowing normal tasks to be executed on those processors
as long as they are not endangering the real-timeproperties.
ARTiS insures a possible processor preemption
when the system has to schedule a real-time process [4]. The main principle is to distinguish two
kinds of CPUs in the multi-processor system: specialized CPUs, a part oriented toward real-time (theso-called RT CPUs) and another part serving all
the other tasks (the so-called non real-time CPUs,NRT CPUs). Two types of RT tasks are characterized, the RT0 which have the highest priority andare binded to a processor and the RT1+ which havelower priority and may migrate between processors.
Every task is allowed to run on an RT CPU but
tasks which are not RT0 will not be allowed to perform real-time endangering functions on this particular CPU. We have implemented ARTiS in the 2.6
Linux kernel and tested it on x86 and IA-64 plat-forms. The implementation of the ARTiS system relies on the fact that any call to preemt disable()or local irq disable() from a task without thehighest RT priority leads systematically to the migration of this task to an NRT CPU. Thus the RT
CPUs remain able to face to real-time activities without long latency.
Nevertheless, the system has to insure a migration mechanism: a NRT task must leave a RT CPU
if it jeopardizes the real-time response time on thisRT CPU. Furthermore, to maximize the utilizationof the whole of the CPU, those NRT tasks may haveto come back on the RT CPU latter. The standardLinux kernel already provides a migration mechanism. Unfortunately, this standard mechanism is not
sufficient because it is not aware of the specializationof the different processors and also because it holds
in the same time locks of two different CPUs (possibly one being a RT CPU) to insure the task migration: the RT CPU may have to wait after the completion of an operation on a NRT CPU which is unacceptable. In order to address those issues we have todesign a specialized load-balancing mechanism.
Usually, the load-balancing mechanism aim is to
move the running tasks across the CPUs in order toinsure that no CPU is idle while some tasks are waiting to be scheduled on other CPUs. It should minimize the total running time by a set of tasks. The
characteristics of a load-balancing can be enumerated as follow:• information update policy: how to renew statistics about the entire system,• trigger policy: how to decide it is time to redistribute the tasks,• selection policy: method to select imbalanced
nodes,• local designation policy: method to select thetasks that will move,• pairing policy: method to select the destination
node for a given task.
The trigger policy can be either of type “pull” –the low loaded CPUs initiate the load-balancing andpull the tasks from another CPU– or “push” –overloaded CPUs initiate the load-balancing in order topush some of their tasks– or a mix of both.

2ARTiS Migrations

In order to specify a more advanced load-balancing
mechanism it is necessary to distinguish the different types of migration according to the specialization of the CPUs involved: RT and NRT CPUs. Theremay be several mechanisms associated to a given
kind of migration in order to fit all the scenarii involving this migration.
NRT CPU to NRT CPU This migration is used forload-balancing between non real-time CPUs. As noRT CPU is involved there is not particular requirement to take care. The original Linux mechanism [3]can be kept for this kind of load-balancing.
RT CPU to NRT CPU This type of migration ismainly called when a task on a RT CPU tries to disable the preemption (endangering the RT properties). This is the core mechanism of ARTiS and it isalready implemented. There is also a load-balancing
mechanism related to this migration. When a NRT
CPU has less load than a RT CPU, some of the NRTtasks should be moved to the NRT CPU. RT tasks
should not be moved as there is better response timeon the RT CPUs. In practice, most of the tasks trigger
preemption disabling code often enough so that thisload-balancing is usually not needed. Still, it is necessary to handle this case in order to guaranty thebest use of all the CPUs in every configuration (forinstance with tasks doing only computational work).
In this kind of migration it is important that the RT
CPU does not take a lock shared with the NRT CPU.
NRT CPU to RT CPU This migration is employedin two different contexts. First, it is used to moveback as soon as possible to a RT CPU the RT tasks
which have reenabled the preemption. In the ARTiS
model, the highest priority RT tasks are always ona RT CPU but other RT tasks may migrate to a NRTCPU. Therefore, to provide the smallest latencies tothem it is necessary to bring them back to any RT
CPU as soon as they are allowed to. However, as
the migration process costs some time it is also important not to move back a task that may need soon
to migrate again. Although it is obviously impossible to exactly know in advance the future behavior of a given task, the local designation part of theload-balancing algorithm has to approximately predict the next time of migration.
Second, this migration is required to load-balance
the NRT tasks if a RT CPU has free time available.
Even if the most important point is to keep the RTproperties on the RT CPUs, this load-balancing represent a major advantage of ARTiS and so it mustnot be neglected.
Both moves between the CPUs implies the modification of the runqueue of each processor. If the NRT
CPU locks the runqueue of the RT CPU (which is thestandard mechanism) then the RT properties of thislatter cannot be guaranteed. It is therefore necessary
to find a transfer mechanism which is lock-free atleast on the RT CPU side.

reader, it is possible to access it without lock, as described in [6]. We are not expecting machines withmore than 32 CPUs, so even if there are two queues
per couple of CPUs, the size of these data structure
should never be excessive.

Trigger policy By default, the Linux kernel [3] uses
a “pull” policy for the load-balancing. However,with the FIFO mechanism which is required to avoid
the locks, this policy has a more complex implementation (leading to longer delays) than the “push”
policy. The use of a queue with this second policy
is straightforward. Consequently, for the new loadbalancing functions, we invert the default policy. ACPU will look for the less busy CPU and then selecttasks to send from its own runqueue to the second
RT CPU to RT CPU The migration between two CPU. In order to lower the latency between the moRT CPUs is solely used to balance their load. The ment a task is inserted and the moment the second
algorithm can be very similar to the NRT to NRT al- CPU reads the FIFO, a signal (an IPI - Inter-Processor
gorithm with the exception that it has to avoid locks Interrupt) is sent, warning about a new task in thebetween two CPUs that will possibly lead to a jitter queue. In addition, concerning the RT tasks on aNRT CPU, the time spent on this processor must beon the expected latencies.
minimized so this special load-balancing function istriggered more often than the other functions, at ev3 Migration Implementation
ery scheduling (typically every millisecond).
Starting from the specific requirements described
Local designation criteria The designation mechabove, we have defined the algorithms and impleanism of the load-balancing which is charged to dementations of the dedicated load-balancing mechacide which task is better to migrate has to be adaptednisms in ARTiS.
to each type of load-balancing. For the symmetric
Lock-free queues One of the main change which load-balancing (NRT to NRT and RT to RT) the origis required from the original load-balancing mecha- inal criteria can be kept as the requirements are thenism is the removal of inter-CPU locks. In order to same than in a normal configuration. For the RT tobe able to insure the RT properties of the RT CPUs, NRT CPUs the only additional criterion is to avoid
there should not be locks that can be taken both by RT tasks (it is better to let them on the RT CPU). ConNRT and RT CPUs. If a RT CPU tries to take a lock cerning the NRT to RT CPUs migrations, there are
already taken by a NRT CPU it will have to wait af- two kinds of load-balancing. One is to move backter it. To avoid this particular sequence we decided as soon as possible the RT tasks and a second is toto avoid taking shared locks. The only shared lock is use the free cycles of the RT CPUs. Both functions
on the runqueue which has to be modified from the have to predict if a task will soon have to migrateother CPU when inserting a migrating task. This is again to a NRT CPU because it requires preemption
why this mechanism has to be changed to an indirect disabled. We propose to estimate the likelihood ofone. Instead of removing the task from a runqueue another migration by the frequency of the previous
and adding it to another runqueue, we insert it to a migration attempts: we suppose a task that has not
special FIFO connecting the two CPUs. The task is disabled preemption for a long time is less likely todequeued later and asynchronously by the second disable it in a close future. The implementation ofCPU. Because this FIFO has only one writer and one this prediction can be done by saving the time of thelast two migration attempts of each task. From thosetimes, we obtain the time weighted mean of the time
elapsed between two attempts. Then the selection
criterion do not move tasks if the time since theirlast migration attempt multiplied by a constant K
is smaller than the mean. K has to be specified later
following the results of experiments, it is expected
to be between 2 and 100.

ever, this standard load-balancing from NRT to RT
CPUs is still active (otherwise, tasks would nevercome back to the RT CPUs) and leads to high latencies. In the same time, measurements have been
done on a simulated ARTiS system with a static configuration (tasks attached by hand to the processors). A huge improvement of the latencies could
be noticed over a normal kernel: all the latencies ofa RT0 task were under 30µs [4].
The future work will first consist of the full implementation of the proposed algorithms. The existing version of ARTiS will be the starting point fora version including the implementation of the loadbalancing functions. Then the major part of the work
will be spent on designing measurement and verification procedures. They will first be used to checkand fine-tune the implemented code and later to perform comparisons with other kernels and configurations.

Pairing policy The original kernel mechanism
compares the load of processors simply by using
the number of tasks ready to run on each processor(runqueue length). Although this method is sufficient for a system executing nearly exclusively NRTtasks, it gives unexpected results if real-time tasks
consume a significant amount of time because they
do not share time with lower priority tasks. Therefore, the pairing policy has to be enhanced to take
into account, in addition to the runqueue length, thetime consumed by RT tasks. In the pairing proce1
dure, we ponderate the runqueue length by (1−RT) , Referenceswhere RT is the ratio of CPU time used by the RT[1] Steve Brosky and Steve Rotolo. Shielded processors:tasks.

4ConclusionIn this paper, we have described the specific migration types and their requirements for a real-timesystem based on an asymmetry of the processors.
We distinguish load-balancing strategies according
to RT and NRT tasks. We have also pointed outthat inter-CPU locks must be avoided. We have thenpresented the techniques on which our solution arebased. Using lock-free FIFOs and an trigger policyof type “push”, it is possible to implement lock-freeload-balancing functions. The real-time aware behavior is achieved via the introduction of new running statistics (elapsed time between two migration
attempts, CPU time consumed by RT tasks) and thespecialization of the functions according to the migration type.
For now, a first version of ARTiS has been developed. It integrates the migration of the tasks which
disable preemption from an RT to NRT CPU via
lock-free queues. The normal load-balancing fromthe RT to NRT CPUs has been deactivated. How-Guaranteeing sub-millisecond response in standard
Linux. In Workshop on Parallel and Distributed Real-Time
Systems, WPDRTS’03, Nice, France, April 2003.

[2] Pierre Cloutier, Paolo Montegazza, Steve Papacharalambous, Ian Soanes, Stuart Hughes, and KarimYaghmour. DIAPM-RTAI position paper. In Second
Real Time Linux Workshop, Orlando, FL, November
2000.
[3] Robert Love. Linux Kernel Development. Sams Publishing, August 2003.
[4] Philippe Marquet, Julien Soula, Éric Piel, and JeanLuc Dekeyser. An asymmetric model for real-timeand load-balancing on Linux SMP. Research Report
2004-04, Laboratoire d’informatique fondamentale deLille, Université des sciences et technologies de Lille,France, April 2004.
[5] Sillicon Graphics, Inc. REACT: Real-time in IRIX.
Technical report, Sillicon Graphics, Inc., Mountain
View, CA, 1997.
[6] John D. Valois. Implementing lock-free queues. In Proceedings of the Seventh International Conference on Parallel and Distributed Computing Systems, Las Vegas, NV,October 1994.