Ordonnancement

Système Temps Réel 2020/2021
Ordonnancement des processus
L’un des rôles primordiaux des systèmes d’exploitation multitâches (c’est le cas aujourd’hui de
la quasi-totalité des systèmes d’exploitation) est d’assurer l’exécution de plusieurs programmes
en parallèle. Plusieurs processus peuvent être présents en mémoire centrale en attente
d’exécution. Si plusieurs processus sont prêts, le système d’exploitation doit gérer l’allocation
du processeur aux différents processus à exécuter. C’est l’ordonnanceur qui s’acquitte de cette
tâche.
Tâches (Tasks)
Une tâche est une unité d’exécution dite aussi unité de travail. En fait, une application temps
réel qui utilise un RTOS peut être structurée comme un ensemble de tâches. Il existe trois types
de tâches :
Tâches périodiques (Periodic tasks) Les tâches périodiques sont répétées une fois par période,
par exemple, 200 millisecondes. Les tâches périodiques résultent généralement de l'acquisition
de données sensorielles, du contrôle des opérations, de la planification des actions et de la
surveillance du système. Ces activités doivent être exécutées de manière cyclique à des
intervalles spécifiques, qui peuvent être déterminés en fonction des exigences de chaque
application. Les tâches périodiques ont des délais stricts, car chaque instance d'une tâche
périodique doit être exécutée avant que l'instance suivante ne soit lancée. Sinon, les instances
de tâches s’empileront.
Tâches apériodiques (Aperiodic tasks) Les tâches apériodiques sont des tâches de type "one-
shot". Elles sont déclenchées par un événement. En ce qui concerne les tâches dites
apériodiques, le seul paramètre connu est la durée d’exécution de la tâche. La date de réveil ou
demande processeur est aléatoire car elle dépend du contexte d’évolution du procédé et ne peut
donc pas être connue a priori.
Tâches sporadiques (Sporadic tasks) Les tâches sporadiques sont également liées à des
événements. Le temps d'arrivée des instances de tâches sporadiques n'est pas connu a priori,
mais il y a un délai critique conduit à des dates d’échéance stricte pour chaque instance
d’exécution.
Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Dr. SID AHMED Soumia
Par exemple, lorsque le conducteur d'un véhicule voit une situation dangereuse devant lui et
pousse le frein pour arrêter le véhicule, le système de contrôle de la vitesse doit réagir à
l'événement (un pas dur sur le frein) dans un délai très court.
Spécification des tâches
Dans un système temps réel, une tâche peut être spécifiée par les paramètres temporels suivants
:
Date de réveil (en anglais Release time), c’est-à-dire la première date à laquelle la tâche
demande le processeur ; c’est le moment où une tâche devient disponible pour être exécutée.
L'exécution de la tâche peut être ordonnée à tout moment à date de réveil ou après celle-ci. Elle
peut ne pas être exécutée immédiatement, parce que, par exemple, une tâche de priorité
supérieure ou égale utilise le processeur. La date de réveil d'une tâche 𝑇𝑖 est désignée par 𝑟𝑖 .
L’échéance (en anglais Deadline), est l'instant où l'exécution d'une tâche doit être terminée.
L’échéance de 𝑇𝑖 est indiquée par 𝑑𝑖 .
Délai critique (en anglais Relative deadline), c’est-à-dire le délai au bout duquel la tâche doit
être terminée par rapport à la date de réveil de l’instance en cours. Par exemple, si la date de
réveil d’une tâche est 𝑡 et que son échéance est 𝑡 + 200 millisecondes, alors son délai critique
est de 200 millisecondes. Le délai critique de 𝑇𝑖 est désignée par 𝐷𝑖 .
Temps d’exécution (en anglais Execution time), c’est le temps nécessaire pour compléter
l'exécution de la tâche lorsqu'elle s'exécute de manière autonome et dispose de toutes les
ressources nécessaires. Le temps d'exécution d'une tâche dépend principalement de la
complexité de la tâche et de la vitesse du processeur. Le temps d'exécution de 𝑇𝑖 est désigné par
𝑒𝑖 .
Le temps de réponse (en anglais Response time), c’est le temps qui s'écoule entre le moment
où la tâche est lancée et celui où son exécution est terminée. Pour une tâche dont l'échéance est
stricte, le temps de réponse maximum autorisé est le délai critique de la tâche.

La figure 1 illustre ces paramètres temporels.
Figure 1. Spécification des tâches
En plus des paramètres susmentionnés, une tâche périodique a les deux paramètres suivants :
Période d’exécution (en anglais Period), c’est-à-dire la fréquence de renouvellement de la

demande d’exécution de la tâche. La période de 𝑇𝑖 est désignée par 𝑝𝑖 .
Phase. La phase d'une tâche périodique est la date de réveil de sa première instance. La phase
de 𝑇𝑖 est désignée par 𝜙𝑖 .
L'utilisation (en anglais Utilization) d'une tâche périodique est le rapport de son temps
d'exécution sur sa période, dénoté par 𝑢𝑖 .
𝑢𝑖 = 𝑒𝑖 /𝑝𝑖 .
Pour une tâche périodique, le temps d'exécution de la tâche, la date de réveil, L’échéance, le
délai critique et le temps de réponse font tous référence à ses instances. Nous définissons une
tâche périodique comme suit :
𝑇𝑖 = ( 𝜙𝑖 , 𝑝𝑖 , 𝑒𝑖 , 𝐷𝑖 )
Par exemple, une tâche avec des paramètres (2, 10, 3, 9) signifie que la première instance de la
tâche est lancée au moment 2, les instances suivantes arriveront à 12, 22, 32, et ainsi de suite.
Le temps d'exécution de chaque instance est de 3 unités de temps. Lorsqu'une instance est
lancée, elle doit être exécutée dans un délai de 9 unités de temps.
Si la phase de la tâche est 0, alors nous la spécifions avec :
𝑇𝑖 = ( 𝑝𝑖 , 𝑒𝑖 , 𝐷𝑖 )

Si le délai critique de la tâche est le même que sa période, alors nous le spécifions avec deux
paramètres seulement :
𝑇𝑖 = ( 𝑝𝑖 , 𝑒𝑖 )
En plus des paramètres de temps, les tâches possèdent des paramètres fonctionnels qui sont
importants dans l’ordonnancement des tâches.
Criticité (en anglais Criticality), les tâches dans un système ont une importance différente. Les
priorités relatives des tâches sont déterminées par la nature des tâches elles-mêmes et l'état
actuel du processus contrôlé. La priorité d'une tâche indique son caractère critique par rapport
aux autres tâches.
Préemption (en anglais Preemptivity), L'exécution des tâches peut être entrelacée. Le
planificateur peut suspendre l'exécution d'une tâche et donner au processeur une tâche plus
urgente. La tâche suspendue peut reprendre son exécution lorsque la tâche plus urgente est
terminée. Une telle interruption de l'exécution d'une tâche est appelée une préemption. Une
tâche est préemptible si elle peut reprendre son exécution à partir du point d'interruption. En
d'autres termes, elle n'a pas besoin de recommencer. Un exemple est une tâche de calcul sur le
CPU. D'autre part, une tâche est non préemptible si elle doit être exécutée du début à la fin
sans interruption. Si elles sont interrompues en cours d'exécution, elles doivent être exécutées
à nouveau dès le début, c’est-à-dire que lorsque certains services s’exécutent, un processus
utilisateur, ou même un autre service, ne peut pas être exécuté.
Une tâche peut être partiellement préemptive. Par exemple, si une partie d'une tâche accède
exclusivement à des ressources partagées, alors la section critique est non préemptible, mais le
reste de la tâche peut être préemptible.
États de la tâche
Dans les systèmes temps réel, une tâche peut se trouver dans l'un des trois états suivants :
Exécuté (en anglais Running), lorsqu'une tâche est effectivement en cours d'exécution, on dit
qu'elle est en état exécuté. Elle utilise actuellement le processeur. Dans un système
monoprocesseur, seulement une tâche peut être en cours d'exécution à un moment donné.

Prêt (en anglais Ready), les tâches à l'état prêt sont celles qui peuvent être exécutées mais qui
ne le sont pas actuellement parce qu'une autre tâche de priorité égale ou supérieure est en cours
d'exécution. Les tâches prêtes disposent de toutes les ressources nécessaires à l'exécution, à
l'exception du processeur. Dans cet état, une tâche est capable de s'exécuter lorsqu'elle devient
la tâche ayant la plus haute priorité parmi toutes les tâches dans cet état et que le processeur est
libéré. Cela signifie qu’elle attend de pouvoir s’exécuter sur le processeur. Un nombre illimité
de tâches peuvent être dans cet état.
Bloqué (en anglais Blocked), une tâche est dite bloquée si elle est en attente d'un événement
temporel ou externe. Par exemple, si une tâche appelle 𝑡𝑎𝑠𝑘𝐷𝑒𝑙𝑎𝑦(), elle se bloquera jusqu'à
l'expiration du délai -événement temporel. Une tâche qui est responsable du traiter les entrées
de l'utilisateur n'a rien à faire jusqu'à ce que l'utilisateur entre quelque chose -événement
externe. Les tâches à l'état bloqué ne sont pas disponibles pour l’ordonnancement. Un nombre
illimité de tâches peut également être dans cet état.
Lorsqu'une nouvelle tâche est créée, elle est placée dans la file d'attente de l'état prêt (cela
signifie qu’il attend de pouvoir s’exécuter sur le processeur). La tâche peut être ordonnancée
pour être exécutée immédiatement ou plus tard, en fonction de sa priorité et de la priorité des
autres tâches à l'état prêt. Toutes les tâches dans cet état sont complètes pour que le processeur
puisse les exécuter. Lorsqu'une tâche de la plus haute priorité est dispatchée pour l'exécution
sur le processeur, elle passe à l'état exécuté. La commutation de contexte est réalisée par une
routine spécifique du système d’exploitation appelée dispatcher. Souvent, dans les
microprocesseurs, le dispatcher est implémenté de façon matérielle.
Si la tâche est préemptible et que l’ordonnanceur ordonner les taches par priorité, une tâche en
cours d'exécution peut être préemptée par une tâche de priorité plus élevée. Lorsqu'elle est
préemptée, le noyau du RTOS la place dans la file d'attente des tâches prêtes.
Une tâche en état exécuté peut également entrer dans l'état bloqué pour plusieurs raisons.
Expliquons le cas de blocage qui provoque ici une inversion de priorité. Supposons que deux
tâches, à savoir A et B, partagent un fragment de mémoire commune conçu pour être utilisé
exclusivement. A a une priorité plus élevée que B. Pendant que B s'exécute et accède à la
mémoire partagée, A est lancé et préempte B. Lorsque A commence à exécuter son code qui
accède à la mémoire partagée, elle est bloquée parce que la mémoire partagée n'est pas
disponible. Maintenant, B, à l'état prêt, est dispatché pour s'exécuter. C'est la situation dans

laquelle une tâche de moindre priorité est en cours d'exécution alors qu'une tâche de plus haute
priorité est en attente.
Une tâche est bloquée parce que toutes les conditions autres que le processeur pour son
exécution ne sont pas encore satisfaites. Ces conditions sont, par exemple, attente d’un délai
(time delay) et les ressources nécessaires. Lorsque toutes les conditions sont satisfaites, la tâche
est placée dans l'état prêt. Dans l'exemple d'inversion de priorité, lorsque la tâche B quitte l'accès
à la mémoire partagée, elle signale au noyau RTOS que la tâche A préemptera B immédiatement
et reprendra son exécution.
Les états d’exécution d’un processus sont représentés sur la figure 2. Notez que certains noyaux
RTOS définissent plus d'états pour les tâches. Par exemple, le T-Kernel RTOS a défini cinq
états pour les tâches : running, ready, waiting, suspended, et waiting-suspended. En plus des
états "running" et "ready", une tâche dans VxWorks peut être dans l'état "pending",
"suspended", "delayed", ou une combinaison de ces états.
Figure 2. États de la tâche
Contrainte de précédence
En plus des contraintes de temps sur les tâches dans une application temps réel, il peut y avoir
des contraintes de priorité entre les tâches. Une contrainte de précédence spécifie l'ordre
d'exécution de deux ou plusieurs tâches. Elle reflète les dépendances de données et/ou de
contrôle entre les tâches. Par exemple, dans un système de contrôle temps réel, la tâche de calcul
de la loi de contrôle (control law computation task) doit attendre les résultats de la tâche de
collecte des données des capteurs (data polling task), c'est pourquoi la tâche de collecte des

données des capteurs doit être exécutée avant la tâche de calcul de la loi de contrôle dans chaque
cycle de contrôle.
Si une tâche A est un prédécesseur immédiat d'une tâche B, nous utilisons 𝐴 < 𝐵 pour
représenter leur relation de précédence. Pour être plus intuitif, nous pouvons utiliser un
graphique de tâches pour montrer les contraintes de priorité entre un ensemble de tâches. Les
nœuds du graphe sont des tâches, et un arc dirigé du nœud A vers le nœud B indique que la
tâche A précède B.
Exemple -Graphe de précédence
La figure 3 présente sept tâches. Les contraintes de dépendance entre elles sont comme suit :
T1 < T3, T2 < T3, T3 < T6, T4 < T5, T5 < T6 et T6 < T7.
Figure 3. Graphe de précédence
Assignation et ordonnancement des tâches
Le développement des algorithmes d’ordonnancement dans les systèmes multiprocesseur se

déroule normalement en deux étapes : nous assignons d'abord des tâches aux processeurs, puis
nous faisons un ordonnancement monoprocesseur pour les tâches assignées à chaque
processeur.
Si un ou plusieurs de ces ordonnancements sont infaisables, alors soit nous refaisons les
assignations de tâches, soit nous utilisons un algorithme différent pour effectuer
l'ordonnancement. Il est possible qu'il n'y ait pas d'assignation/ordonnancement faisable pour
un problème particulier.

Chaque tâche s'exécute en fonction de son propre contexte. Une seule tâche dans l'application
peut être exécutée sur un processeur à tout moment. L’ordonnanceur d'un RTOS est un module
qui implémente les algorithmes d'assignation (scheduling) des tâches.
Un algorithme d’ordonnancement étant défini comme un algorithme capable de donner une

description (séquence) du travail à effectuer par le ou les processeurs, une séquence est dite
Valide si les échéances des tâches sont respectées.
On dit qu'un ordonnanceur est faisable (en anglais feasible schedule) si chaque tâche
ordonnancée se termine avant son échéance.
Un système (un ensemble de tâches) est dit ordonnançable s'il existe un ordonnanceur faisable
pour le système.
Nous utilisons une condition suffisante d’ordonnançabilité (SU pour schedulable utilization)
pour mesurer la performance d'un algorithme d'ordonnancement. SU est l'utilisation totale
maximale des tâches qui peuvent être ordonnancées par l'algorithme. Plus l'US est élevé,
meilleur est l'algorithme d'ordonnancement.
Les Algorithme d’ordonnancement :
Les Algorithme classiques d’ordonnancement :
Premier Entré Premier Sorti (en anglais First-in-first-out « FIFO »)
Premier arrivé premier servi, l’un des algorithmes les plus simples, puisqu’il exécute les
processus dans leur ordre d’arrivée. Dans le cas où les processus ne se suspendent pas et
n’attendent pas, cet algorithme ne nécessite aucune préemption, car lorsqu’un processus
commence son exécution, il n’est pas interrompu jusqu’à sa terminaison.

Travail plus court d'abord (en anglais Short Job First « SJF »)
Il s’agit d’un algorithme d'ordonnancement, c'est-à-dire d’un algorithme servant à choisir

lequel de plusieurs processus sera traité en premier par le processeur. Le choix se fait en
fonction du temps d’exécution estimé du processus. Ainsi, l’ordonnanceur va laisser passer
d'abord le plus court des processus de la file d’attente1.
Exemple
r e
T1 0 7
T2 2 4
T3 4 1
T4 5 4
Algorithme du tourniquet (en anglais « round robin », RR)
Les processus prêts ont droit chacun leur tour à un quantum. Lorsqu’un cycle d’attribution du
processeur aux processus est terminé, un autre cycle du tourniquet commence. La performance
de RR dépend largement de la taille du quantum. Un quantum trop grand augmente les temps
de réponse alors qu'un quantum trop petit multiplie les commutations de contexte jusqu'à les
rendre non négligeables.
1
https://fr.wikipedia.org/wiki/Shortest_job_first (05/12/2020)

Ordonnancement piloté par horloge (Clock-Driven Scheduling)
Dans le cadre d’ordonnancement piloté par horloge, les décisions d’ordonnancement sont prises
à des instants précis, qui sont généralement choisis a priori avant que le système ne commence
son exécution. Cela fonctionne généralement pour les systèmes déterministes où les tâches ont
des échéances strictes et tous les paramètres des tâches ne changent pas pendant le
fonctionnement du système. La séquence d’exécution peut être calculé hors ligne et stockés
pour être utilisés au moment de l'exécution, ce qui permet de réduire considérablement le
surcoût processeur ou overhead (est le pourcentage du temps processeur utilisé par le système
d’exploitation pour gérer les processus). Pour un ensemble de tâches périodiques avec des
paramètres donnés, il est assez simple de dessiner l’ordonnancement des tâches basées sur
l'approche clock-driven.
Exemple-La figure 4 montre l’ordonnancement de trois tâches périodiques :
T1 = (4, 1), T2 = (6, 1), T3 = (12, 2).
Les temps d'exécution se situent dans l'intervalle de 0 à 12 unités de temps, première

hyperpériode du système. Il peut être prouvé que, quelle que soit la phase de chaque tâche, leur
cycle majeur (hyperpériode) est toujours leur abrégé PPCM (le plus petit commun multiple).
Au cours de cette période, il y a trois instances de T1, deux instances de T2 et une instance de
T3.
Analysons le premier ordonnancement et voyons pourquoi il est faisable.
Considérez d'abord T1. Au temps 0, T1 lance sa première instance avec une échéance 4. Son
exécution est ordonnancée au temps 0 et terminée au temps 1. Elle respecte donc son échéance.
Au temps 4, la deuxième instance de T1 est lancée avec une échéance 8. Son exécution est
ordonnancée au temps 4 et terminée au temps 5. Elle respecte son échéance.
Au temps 8, la troisième instance de T1 est lancée avec une échéance 12. Son exécution est
Considérons maintenant T2. La première instance de T2 est lancée au temps 0 et son échéance
est fixée au temps 6. Son exécution est ordonnancée au temps 1 et terminée au temps 2. Donc,
elle respecte son échéance.

Au temps 6, la deuxième instance de T2 est lancée avec une échéance 12. Son exécution est
La seule instance de T3 est lancée au temps 0 avec une échéance au temps 12. Son exécution
est ordonnancée au temps 2 et terminée au temps 4. Elle respecte donc son échéance.
Figure 4. L’ordonnancement de trois tâches périodiques.
Étant donné que toutes les instances de tâches lancées dans la première hyperpériode du système
respectent leurs échéances, l’ordonnancement est faisable (the schedule is feasible). Nous
pouvons utiliser un tableau d’ordonnancement :
Ensuite, en se basant sur le tableau, un ordonnanceur peut être conçu en fonction du pseudo-
code indiqué dans la figure 5.

Ordonnancement Structuré
Bien que les ordonnancements de l'exemple d’ordonnancement piloté par horloge soient
faisables, les points de décision de l’ordonnancement sont dispersés de manière aléatoire. En
d'autres termes, il n'y a pas de modèle dans les points temporels auxquels les nouvelles tâches
sont sélectionnées pour être exécutées. L'idée de l'approche structurée de la programmation par
horloge est que les décisions de programmation sont prises à des moments périodiques, plutôt
qu'arbitraires. De cette façon, un Timer qui expire périodiquement avec une durée fixe peut être
utilisé pour les temps de décision.
Frame
Dans un ordonnancement structuré, les temps de décision d’ordonnancement divisent la ligne

de temps en intervalles appelés frames. Chaque frame est d'une longueur f, qui est appelée la
taille du frame (frame size). Il n'y a pas de préemption à l'intérieur d’un frame, car les décisions
d’ordonnancement ne sont prises qu'au début de chaque frame.
Pour faciliter l’ordonnancement, la phase de chaque tâche périodique est un multiple non
négatif de la taille du frame. En d'autres termes, la première instance de chaque tâche
périodique est lancée au début d'un frame.
Nous venons de mentionner qu'il ne devrait pas y avoir de préemption dans un frame (sinon, il
ne s'agit pas d'ordonnancement structurée). Comme la préemption implique des changements
de contexte, il est souhaitable d'éviter la préemption, c'est pourquoi, lorsque nous sélectionnons
une taille du frame, celle-ci doit être suffisamment grande pour permettre à chaque tâche de
s'exécuter à l'intérieur du frame. Supposons qu'il y ait 𝑛 tâches périodiques dans un système.
Cette contrainte peut être exprimée mathématiquement comme :
𝒇 ≥ 𝒎𝒂𝒙{𝒆𝒊 , 𝒊 = 𝟏, 𝟐, … , 𝒏}
Pour minimiser le nombre d'entrées dans un tableau d’ordonnancement afin d'économiser de

l'espace de stockage, la taille du frame choisie doit diviser la taille maximale. Sinon, il ne suffira
pas de stocker l’ordonnancement d'un seul cycle (major cycle), car l’ordonnancement ne se
répétera pas simplement d'un cycle à l'autre, et il faudra donc un tableau d’ordonnancement
plus important.
𝑯 𝒎𝒐𝒅 𝒇 = 𝟎

Puisque 𝐻 est un multiple de la période de chaque tâche, si 𝑓 peut diviser 𝐻, alors 𝑓 doit
également diviser la période d'au moins une tâche dans le système, c'est-à-dire,
𝒑𝒊 𝒎𝒐𝒅 𝒇 = 𝟎, ∃𝒊 ∈ {𝟏, 𝟐, … , 𝒏}
Notez que cette contrainte est importante, car le volume de stockage est limité pour la plupart
des systèmes embarqués.
Lorsque nous choisissons la taille du frame, nous devons également vérifier qu'elle permet à
chaque instance de tâche de respecter son échéance. Cette contrainte impose qu'il y ait au moins
un frame complet entre l'arrivée d'une instance de tâche et son échéance. Car si une instance de
tâche arrive juste après le début d’un frame, elle ne sera pas ordonnancée jusqu'au début du
frame suivant. Cependant, la taille du frame peut aller jusqu'au temps d'exécution d'une tâche.
Cela peut entraîner que l'instance ne respecte pas son échéance.
La figure 6 illustre cette situation.
Figure 6. Une instance de tâche lancée juste après le démarrage du frame.
Dans la figure X, une instance de tâche arrive au temps 𝑘𝑓 + 𝛥𝑡, où 𝛥𝑡 < 𝑓 . Son échéance 𝑑
est compris entre (𝑘 + 1)𝑓 et (𝑘 + 2)𝑓 . Cette instance de tâche sera ordonnancée pour être
exécutée au plus tôt (𝑘 + 1)𝑓 , au début du frame suivant après son arrivée. Avant son
échéance, elle ne peut être exécuté que pour 𝑑 − (𝑘 + 1)𝑓 unités de temps, ce qui est inférieur
à la taille du frame. Si le temps d'exécution est proche ou égal à la taille du frame, alors l'instance
de la tâche ne peut pas terminer l'exécution avant son échéance.
La contrainte selon laquelle il doit y avoir un frame complet entre l'arrivée d'une instance de
tâche et son échéance est formulée comme :
𝑑𝑖 − (𝑘𝑓 + 𝛥𝑡) ≥ 𝑓 + (𝑓 − 𝛥𝑡)

Parce que
𝑑𝑖 − (𝑘𝑓 + 𝛥𝑡) = 𝐷𝑖
Par conséquent,
2𝑓 − 𝛥𝑡 ≤ 𝐷𝑖
Étant donné que la première instance de la tâche est lancée au début du frame, le minimum de
𝛥𝑡 est le plus grand concepteur commun (GCD) de 𝑝 𝑖 et 𝑓.
Le minimum de 𝛥𝑡 correspond au cas le plus défavorable, c'est-à-dire que l'instance a le plus

de chances de ne pas respecter son échéance. Ainsi, la troisième contrainte peut s'écrire comme
suit
2𝑓 − 𝐺𝐶𝐷(𝑝𝑖 , 𝑓 ) ≤ 𝐷𝑖 , 𝑖 = 1,2, … , 𝑛.
Example
Considérez un système de trois tâches périodiques :
𝑇1 = (4, 1), 𝑇2 = (5, 1), 𝑇3 = (10, 2).
Nous voulons développer un ordonnanceur cyclique pour le système. Tout d'abord, nous devons
sélectionner une taille du frame appropriée.
Selon la première contrainte, nous avons 𝑓 ≥ 2. Le grand cycle des trois tâches est 𝐻 = 20.
Selon la deuxième contrainte, f doit diviser 20. Les tailles du frame possibles sont 2, 4, 5 et 10.
Nous n'avons pas besoin de considérer 1, car il ne respecte pas la première contrainte.
Nous devons maintenant tester 2, 4, 5 et 10 avec la troisième contrainte 2𝑓 − 𝐺𝐶𝐷(𝑝𝑖 , 𝑓 ) ≤

𝐷𝑖 pour chaque tâche. Considérez d'abord 𝑓 = 2. Pour T1 = (4, 1),
2𝑓 − 𝐺𝐶𝐷(𝑝1 , 𝑓) = 2 ∗ 2 − 𝐺𝐶𝐷(4, 2) = 4 − 2 = 2,
Alors que D1 = 4 (2 ≤ 4). Par conséquent, la contrainte est satisfaite par T1.
Pour T2 = (5, 1),
2𝑓 − 𝐺𝐶𝐷(𝑝2 , 𝑓) = 2 ∗ 2 − 𝐺𝐶𝐷(5, 2) = 4 − 1 = 3,
Alors que D2 = 5. Par conséquent, la contrainte est satisfaite par T2.

Pour T3 = (10, 2),
2𝑓 − 𝐺𝐶𝐷(𝑝3 , 𝑓) = 2 ∗ 2 − 𝐺𝐶𝐷(10, 2) = 4 − 2 = 2,
Par conséquent, la contrainte est satisfaite par T3.
Ainsi, la troisième contrainte est satisfaite par toutes les tâches lorsque 𝑓 = 2. Ceci conclut
également qu'un choix de la taille du frame est 2.
Examinons maintenant f =4. Pour T1 = (4, 1),
2𝑓 − 𝐺𝐶𝐷(𝑝1 , 𝑓) = 2 ∗ 4 − 𝐺𝐶𝐷(4, 4) = 8 − 4 = 4,
Alors que D1 = 4, la contrainte est satisfaite par T1.
Pour T2 = (5, 1),
2𝑓 − 𝐺𝐶𝐷(𝑝2 , 𝑓) = 2 ∗ 4 − 𝐺𝐶𝐷(5, 4) = 8 − 1 = 7,
Alors que D2 = 5. L'inégalité n'est pas satisfaite par T2, il n'est pas nécessaire de tester T3 à
nouveau.
Considérons f = 5. Pour T1 = (4, 1),
2𝑓 − 𝐺𝐶𝐷(𝑝1 , 𝑓) = 2 ∗ 5 − 𝐺𝐶𝐷(4, 5) = 10 − 1 = 9,
Alors que D1 = 4. L'inégalité n'est pas satisfaite par T1.
Considérons f = 10. Pour T1 =(4, 1),
2𝑓 − 𝐺𝐶𝐷(𝑝1 , 𝑓) = 2 ∗ 10 − 𝐺𝐶𝐷(4, 10) = 20 − 2 = 18,
Alors que D1 = 4. L'inégalité n'est pas satisfaite par T1.
Ainsi, la seule taille du frame faisable pour l’ordonnancement cyclique est 2. La figure 7 montre
un ordonnancement faisable avec une taille du frame 2.
Figure 7. Un ordonnancement faisable avec une taille du frame 2.

Le tableau suivant représente l’ordonnancement cyclique illustré à la figure 7. L'entrée 7 est un

I, qui signifie "inactif" (en anglais Idle).
Dans l’ordonnancement cyclique illustré à la figure 7, l'ordonnancement dans un frame est

appelé bloc d’ordonnancement. Chaque entrée dans le tableau d'ordonnancement est un bloc.
Le k-ième bloc est désigné par L(k), k =0, 1, 2, ..., F -1, où F est le nombre du frame dans un
cycle majeur. L'horloge interrompt périodiquement chaque f unités de temps.
Algorithmes d’ordonnancement par priorité (Priority-Driven Scheduling Algorithms)
Contrairement aux algorithmes d’ordonnancement piloté par horloge qui ordonnance les tâches
à des points temporels spécifiques, hors ligne, dans un algorithme d’ordonnancement par
priorité, Les décisions d’ordonnancement sont prises lorsqu'une nouvelle tâche (instance) est
lancée ou lorsqu’une tâche (instance) est terminée. Il s'agit d’ordonnancement en ligne, et les
décisions sont prises au temps d'exécution. Une priorité est attribuée à chaque tâche.
L'attribution des priorités peut se faire de manière statique ou dynamique pendant que le
système est en cours d'exécution. Un algorithme d’ordonnancement qui attribue la priorité aux
tâches de manière statique est appelé algorithme à priorité statique ou à priorité fixe, et un
algorithme qui attribue la priorité aux tâches de manière dynamique est dit algorithme à priorité
dynamique. L’ordonnancement par priorité est facile à implémenter. Elle ne nécessite pas
l'information sur la date de réveil et d'exécution des tâches a priori. Les paramètres de chaque
tâche sont connus à l’ordonnanceur en ligne qu'après son lancement. L’ordonnancement en
ligne est la seule option dans un système dont la charge de travail future (future workload) est
imprévisible.
Algorithmes d’ordonnancement à priorités fixes
Dans cette section, nous supposons ce qui suit :
1) Il n'y a que des tâches périodiques dans le système considéré.
2) le délai critique de chaque tâche est le même que sa période.
3) Toutes les tâches sont indépendantes ; il n'y a pas de contraintes de précédence.
4) Toutes les tâches sont préemptible, et le coût des changements de contexte est négligeable.
5) Seules les demandes de processus sont importantes. Les besoins en mémoire, en E/S et tout
autre besoin en ressources sont négligeables.
• Algorithme d’ordonnancement « Rate Monotonic »
L'algorithme à priorité fixe le plus connu est l'algorithme d’ordonnancement « Rate Monotonic
». L'algorithme assigne des priorités en fonction de la période des tâches. Plus la période de la
tâche est petite, plus la priorité de la tâche est grande. La tâche conserve cette priorité pendant
toute son exécution. Étant donné deux tâches 𝑇𝑖 = (𝑝𝑖 , 𝑒𝑖 ) et Tj = (𝑝𝑗 , 𝑒𝑗 ), si 𝑝𝑖 < 𝑝𝑗 , alors 𝑇𝑖
a une priorité plus élevée que 𝑇𝑗 .
L’ordonnancement de tâches périodiques basée sur l'algorithme RM est relativement facile :

lorsqu'une nouvelle instance de tâche est lancée, si le processeur est inactif, il exécute la tâche
; si le processeur exécute une autre tâche, alors l’ordonnancement compare leurs priorités. Si la
priorité de la nouvelle tâche est plus élevée, il préempte la tâche en cours d'exécution et l'exécute
sur le processeur ; la tâche préemptée est placée dans la file d'attente des tâches prêtes.
Exemple

La figure 8 montre un ordonnancement de trois tâches périodiques basée sur l'algorithme RM :

𝑇1 = (4, 1), 𝑇2 = (5, 1), 𝑇3 = (10, 3).
Parce que p1 <p2 <p3, T1 a la priorité la plus élevée et T3 a la priorité la plus faible.
Chaque fois qu'une instance de T1 est lancée, elle préempte tout ce qui s'exécute sur le
processeur et est immédiatement exécutée. Les instances de T2 sont exécutées en "arrière-plan"
de T1. La tâche T3, en revanche, ne peut pas s'exécuter lorsque T1 ou T2 ne sont pas terminées.
Examinons maintenant l’ordonnancement et voyons si une instance de tâche n'a pas dépassé
son échéance. Nous n'avons pas besoin d'examiner T1, car chaque fois qu'une instance est
lancée, elle est exécutée immédiatement sur le processeur. Pour le T2, il y a quatre instances et
ils sont tous exécutés avant leurs échéances. Pour T3, la première instance est terminée à 7,
c'est-à-dire avant son échéance à 10. La deuxième instance est lancée à 10 et terminée à 15, ce
qui est également avant son échéance 20. Par conséquent, les trois tâches périodiques sont
ordonnancées selon l’algorithme RM.
Figure 8. Trois tâches périodiques sont ordonnancées par RM.
Exemple
La figure 9 montre que lorsque nous ordonnons trois tâches périodiques 𝑇1 = (4, 1), 𝑇2 =
(5, 2), 𝑇3 = (10, 3.1). Selon l'algorithme RM, la première instance de T3 manque son
échéance - il lui reste 0,1 unité de temps d'exécution qui n'est pas terminée à son échéance 10.

Figure 9. Exemple de tâche dont les échéances ne sont pas respectées dans l’ordonnancement RM.
Vous vous demandez peut-être comment tester si un système peut être ordonnancé par
l'algorithme RM ou non.
Commençons par introduire un test simple : Si l'utilisation totale d'un ensemble de tâches
périodiques n'est pas supérieure à :
𝑈𝑅𝑀 (𝑛) = 𝑛(21∕𝑛 − 1),
Où n est le nombre de tâches, alors l'algorithme RM peut ordonnancer toutes les tâches pour
respecter leurs échéances.
Pour n=3, nous avons 𝑈𝑅𝑀 (3) = 0,78. Dans l'exemple 1, l'utilisation totale est de 0,75. Étant
donné que 0,75 < 0,78, les trois tâches sont ordonnançables comme nous l'avons prouvé à la
figure d’exemple 1.
Dans l'exemple 2, l'utilisation totale est de 0,96. Comme 0,96>0,78, nous ne pouvons pas tirer
de conclusion. Une chose que nous pouvons affirmer à partir de cet exemple est que l'algorithme
de RM n'est pas optimal, car, comme nous l'avons déjà mentionné, le SU d'un algorithme
optimal est de 1.
• Algorithme d’ordonnancement « Deadline Monotonic »
Outre l'algorithme RM, un autre algorithme d’ordonnancement à priorité fixe bien connu est
''deadline-monotonic (DM)'', qui attribue des priorités aux tâches en fonction de leurs
échéances. Une tâche avec un délai critique plus courte a une priorité plus élevée que ceux dont
les délais critiques sont plus longs.
Par exemple,

Pour un système comportant trois tâches T1 = (50, 50, 25, 100), T2 = (0, 62,5, 10, 20), et T3 =
(0, 125, 25, 50), T2 a la priorité la plus élevée tandis que T1 a la priorité la plus faible. Si, dans
un système, l’échéance de chaque tâche est égale à sa période, alors RM et DM produiront le
même ordonnancement.
Algorithmes d’ordonnancement à priorités variables
Nous avons jusqu’à présent considéré que la priorité affectée à une tâche restait constante
pendant toute la durée de l’application. Nous allons nous intéresser à une autre catégorie
d’algorithme d’ordonnancement pour laquelle la priorité des tâches varie au cours de
l’exécution d’une tâche. Cette priorité est fonction d’une caractéristique temporelle dynamique
de la tâche.
• Algorithme d’ordonnancement « Earliest Deadline First »
Dans le cas de l’algorithme « Earliest Deadline First » ou EDF, la priorité des tâches est variable
au cours de leur exécution et fonction de la prochaine échéance.
Exemple
Exemple d’une configuration de trois tâches périodiques pour l’étude de l’ordonnancement

EDF.
𝑷 𝒆 𝑫
T1 2 0.5 2
T2 4 1 4
T3 5 1.5 5
Figure 10. Séquence d’exécution d’une configuration de trois tâches données dans l’exemple et traitée
avec l’algorithme EDF : ordonnançable.

Ordonnancement des tâches apériodiques et sporadiques par priorité
Ordonnancement des tâches apériodiques
Les tâches apériodiques sont des tâches imprévisibles qui peuvent arriver à tout moment, par
exemple lorsqu'un utilisateur appuie sur un bouton pour modifier une configuration du système,
ou lorsqu'un paquet de données arrive de manière aléatoire et doit être traité. Les tâches
apériodiques ont soit des échéances souples, soit aucune échéance.
L'algorithme le plus simple pour l’ordonnancement des tâches apériodiques consiste à les
exécuter en arrière-plan des tâches périodiques, c'est-à-dire aux moments dans la séquence
d’exécution des tâches périodiques.
L'algorithme attribue la priorité la plus faible aux tâches apériodiques. Par conséquent,
l'ordonnancement des tâches périodiques ne sera pas affecté, mais il n'y a aucune garantie
concernant le temps de réponse des tâches apériodiques.
Figure 11. L'algorithme le plus simple pour l’ordonnancement des tâches apériodiques
Exemple- tâche apériodique A1(2,1)
▪ La tâche A1 arrive au moment 2

▪ Le temps d’exécution 1
▪ Le temps de réponse après
l’ordonnancement est 5.
Nous pouvons appliquer la technique du slack stealing pour améliorer les performances de
l'ordonnanceur en ce qui concerne la réponse aux tâches apériodiques. La théorie qui sous-tend

le slack stealing est que pour les tâches périodiques, l'objectif de l’ordonnancement est de
respecter leurs échéances ; il n'y a aucun avantage à terminer leur exécution plus tôt. Nous
pouvons donc retarder leur exécution autant que possible, dans la mesure où leurs échéances
sont respectées. De cette façon, nous pouvons exécuter des tâches apériodiques le plus tôt
possible.
Exemple- supposons que l’échéance de T1 est 7,
Le Slack stealing peut être facilement implémenté dans un système d’ordonnancement piloté
par horloge. Le Slack stealing peut être facilement implémenté dans un système
d’ordonnancement piloté par horloge, car l’ordonnancement est calculé hors ligne, et nous
savons exactement quand le processeur est disponible pour les tâches apériodiques, combien de
temps de slack est dans chaque frame. Cependant, implanter le Slack stealing dans un système
d’ordonnancement par priorité est beaucoup plus compliqué, parce que les décisions
d’ordonnancement sont prises au moment de l'exécution.
Algorithme d’ordonnancement « Latest Release Time (LRT) »
LRT ordonnance la dernière tâche lancée le plus tard possible, et il ordonnancé la deuxième
tâche la plus tardive (avant la dernière tâche lancée) le plus tard possible en tenant compte du
fait que la dernière tâche a déjà été ordonnancée. LRT est comme l’algorithme de EDF,
entièrement dynamique. En utilisant des méthodes comme celle-ci, nous pouvons réduire le
temps de réponse pour les tâches apériodiques.
Dans l'algorithme LRT :
Les dates de réveil (release times) des tâches sont traitées comme des échéances (deadlines).
Les échéances sont traitées comme des dates de réveil.
Exemple- Toutes les tâches pourront-elles être terminées avant leur échéance ?

Considérer la configuration suivante :
• Ordonnancement par LRT

• Préemptive
Effectuer un ordonnancement des tâches J1, J2 et J3 dans l'intervalle [0 8] ; sachant que J2

dépend de J1, mais que J3 ne dépend d'aucune tâche
Solution
Ordonnancement des tâches sporadiques par priorité
Lorsqu'une tâche sporadique arrive, l’ordonnanceur doit décider d'accepter ou de rejeter la

tâche, car il ne sert à rien d'accepter une tâche sporadique si cela a pour conséquence que les
tâches périodiques manquent leur échéance.
Le test d'ordonnancement pour valider une tâche sporadique est basé sur la division de la
timeline en frames, Nous vérifierons si une tâche sporadique peut être ordonnancée dans un
frame. Vous devez également prendre en considération l'ordre des tâches sporadiques prévues,
car elles ne peuvent pas non plus être retardées par des tâches sporadiques entrantes.

Supposons que nous ayons un système avec quelques tâches périodiques ordonnancées. Une
tâche sporadique arrive au moment t=x, nous supposons que nous avons une échéance 𝐷𝑆1 = 𝑑
et un temps d'exécution 𝑒𝑆1 = 𝐸 définis pour la tâche sporadique.
Déterminer si le système est faisable, même en ajoutant cette tâche. Si ce n'est pas le cas, les
autres tâches peuvent-elles être réorganisées, ou est-il impossible de faire l’ordonnancement
d’une tâche sporadique ?
Définitions
𝑖
▪ Le frame i appartient à un cycle majeur (hyperpériode) 𝑋(𝑖) = [𝐹].
▪ Le nombre de frame dans l’hyperpériode est 𝜑(𝑖) = 𝑖%𝐹

▪ Et afin de savoir si une tâche sporadique S (d, e) peut être acceptée au temps t, le slack
𝜎𝑐 (𝑖, 𝑖 ′ ) doit être calculé. Cet espace correspond en fait à la place qu'il reste pour
ordonnance des tâches sporadique dans le cycle majeur.
𝑡 𝑑
▪ Et le premier frame est 𝑖 = [𝐹] et 𝑘 = [𝑓 ] − 1 et le dernier frame dans lequel les tâches
peuvent être placées.
Test
▪ Nous stockons les « slack » 𝜎𝑓 (𝑖, 𝑖 ′ ) pour 0 ≤ 𝑖 ≤ 𝑘 ≤ 𝐹 ces valeurs sont obtenues à
partir de l’ordonnancement.
▪ Considérer un intervalle allant du frame i dans l’hyperpériode j au frame k dans
l’hyperpériode 𝑗 ′
▪ Le nombre total des slack (le vide total) :
𝜎(𝑖 + (𝑗 − 1))𝐹, 𝑘 + ( 𝑗 ′ − 1)𝐹 = 𝜎(𝑖, 𝐹) + 𝜎(1, 𝑘) + (𝑗 ′ − 𝑗 − 1)𝜎(1, 𝐹)

Exemple
Calculer les vides (slack) du frame 3 au frame 14. Nous avons donc une séquence déjà établi
pour la première tâche T1 et nous voulons déterminer le slack avec un frame de taille 4. Nous
commençons alors à partir du temps 8, où commence le frame 3. Et nous terminons au temps
56, où le frame 14 se termine.
Pour ce faire, nous prenons la formule précédemment définie :
𝜎(𝑖 + (𝑗 − 1))𝐹, 𝑘 + ( 𝑗 ′ − 1)𝐹 = 𝜎(𝑖, 𝐹) + 𝜎(1, 𝑘) + (𝑗 ′ − 𝑗 − 1)𝜎(1, 𝐹)
Avec
𝜎(𝑖, 𝐹) : le slack totale depuis le frame dans lequel nous intervenons (frame 3)
𝜎(1, 𝑘) : le slack totale depuis le début du dernier cycle majeur jusqu'au le frame prévu (frame
14)
(𝑗 ′ − 𝑗 − 1)𝜎(1, 𝐹) : le slack totale dans tous les cycles majeur intermédiaires
Nous avons donc les paramètres suivants :
𝐹 = 4 , 𝑗 = 1, 𝑗 ′ = 3 , 𝑖 = 3, 𝑘 = 4
Donc :
𝜎(3,14) = 𝜎(3, 4) + 𝜎(1, 4) + (3 − 1 − 1)𝜎(1,4) = 4 + 4.5 + (3 − 1 − 1) ∗ 5.5 = 14

Références
Prof. Yann Thoma, INTRODUCTION À LA PROGRAMMATION TEMPS RÉEL,2010.
COTTET, Francis et GROLLEAU, Emmanuel. Systèmes temps réel de contrôle-commande:

conception et implémentation. Dunod, 2005.
LI, Qing et YAO, Caroline. Real-time concepts for embedded systems. CRC Press, 2003.
WANG, Jiacun. Real-time embedded systems. John Wiley & Sons, 2017.


Ordonnancement

Transféré par

Droits d'auteur :

Formats disponibles

Ordonnancement

Transféré par

Informations du document

Description originale:

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Ordonnancement

Transféré par

Droits d'auteur :

Formats disponibles

Système Temps Réel 2020/2021

Ordonnancement des processus

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Spécification des tâches

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

La figure 1 illustre ces paramètres temporels.

Figure 1. Spécification des tâches

Période d’exécution (en anglais Period), c’est-à-dire la fréquence de renouvellement de la

Si la phase de la tâche est 0, alors nous la spécifions avec :

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Figure 2. États de la tâche

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Exemple -Graphe de précédence

Figure 3. Graphe de précédence

Assignation et ordonnancement des tâches

Le développement des algorithmes d’ordonnancement dans les systèmes multiprocesseur se

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Un algorithme d’ordonnancement étant défini comme un algorithme capable de donner une

Les Algorithme d’ordonnancement :

Les Algorithme classiques d’ordonnancement :

Premier Entré Premier Sorti (en anglais First-in-first-out « FIFO »)

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Il s’agit d’un algorithme d'ordonnancement, c'est-à-dire d’un algorithme servant à choisir

Algorithme du tourniquet (en anglais « round robin », RR)

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Ordonnancement piloté par horloge (Clock-Driven Scheduling)

Exemple-La figure 4 montre l’ordonnancement de trois tâches périodiques :

T1 = (4, 1), T2 = (6, 1), T3 = (12, 2).

Les temps d'exécution se situent dans l'intervalle de 0 à 12 unités de temps, première

Analysons le premier ordonnancement et voyons pourquoi il est faisable.

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Figure 4. L’ordonnancement de trois tâches périodiques.

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Dans un ordonnancement structuré, les temps de décision d’ordonnancement divisent la ligne

Pour minimiser le nombre d'entrées dans un tableau d’ordonnancement afin d'économiser de

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

La figure 6 illustre cette situation.

Figure 6. Une instance de tâche lancée juste après le démarrage du frame.

𝑑𝑖 − (𝑘𝑓 + 𝛥𝑡) ≥ 𝑓 + (𝑓 − 𝛥𝑡)

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Le minimum de 𝛥𝑡 correspond au cas le plus défavorable, c'est-à-dire que l'instance a le plus

Considérez un système de trois tâches périodiques :

𝑇1 = (4, 1), 𝑇2 = (5, 1), 𝑇3 = (10, 2).

Nous devons maintenant tester 2, 4, 5 et 10 avec la troisième contrainte 2𝑓 − 𝐺𝐶𝐷(𝑝𝑖 , 𝑓 ) ≤

Pour T2 = (5, 1),

Alors que D2 = 5. Par conséquent, la contrainte est satisfaite par T2.

Université Mohamed El Bachir El Ibrahimi Département d’Electronique

Pour T3 = (10, 2),

Par conséquent, la contrainte est satisfaite par T3.

Examinons maintenant f =4. Pour T1 = (4, 1),

Alors que D1 = 4, la contrainte est satisfaite par T1.

Pour T2 = (5, 1),

Considérons f = 5. Pour T1 = (4, 1),

Alors que D1 = 4. L'inégalité n'est pas satisfaite par T1.

Considérons f = 10. Pour T1 =(4, 1),

2𝑓 − 𝐺𝐶𝐷(𝑝1 , 𝑓) = 2 ∗ 10 − 𝐺𝐶𝐷(4, 10) = 20 − 2 = 18,

Alors que D1 = 4. L'inégalité n'est pas satisfaite par T1.