3- Programmes temps réel

3.4- Limitations de l’ordonnancement en ligne

3.4- Limitations de l’ordonnancement en ligne

3- Programmes temps réel
3.4- Limitations de l’ordonnancement en ligne

Ordonnancement en ligne vs hors-ligne

Ordonnancement hors ligne

� Généralement pour ordonnancement contrôlé par le temps, temps réel dur
� Peut générer des cédules complexes, avec optimisation sophistiquée et exigeante en calcul
� Exige de connaître à l’avance toutes les tâches et leurs contraintes
� Manque manifeste de flexibilité
� Ne gère pas situations où nouvelle tâche imprévue doit être créée
� Ajustements difficiles face aux variations du déroulement
Ordonnancement en ligne
� Décisions prises sans connaître tâches futures
� Prise de décisions myope
� Ne fait pas nécessairement le meilleur usage des ressources
� Utilisé pour ordonnancement contrôlé par les évènements, souvent pour temps réel doux
� Seule option possible lorsque charge de travail future n’est pas prévisible
� Gère bien les variabilités dans le déroulement des opérations
� Algorithmes utilisés usuellement sont assez légers en traitement
3- Programmes temps réel
3.4- Limitations de l’ordonnancement en ligne

Exemples d’anomalies

Exemple illustrant anomalies avec ordonnancement en ligne

� Deux processeurs
� Tâches peuvent être assignées à n’importe quel processeur
� Tâches préemptibles
� Une fois assignées, tâches ne migrent pas (système statique)
� Tâche de durée déterminée, sauf J2 avec temps d’exécution variant entre 2 et 6
ri di ei
J1 0 10 5
J2 0 10 [2, 6]
J3 4 15 8
J4 0 20 10
3- Programmes temps réel
3.4- Limitations de l’ordonnancement en ligne

Exemples d’anomalies

Pour J2 = 6, ordonnancement optimal

Pour J2 = 2, ordonnancement sous-optimal

� Tâche J3 arrive après lancement de J4

Inspiré de Jane W.S. Liu. Real-time systems. Prentice-Hall, 2000.

3- Programmes temps réel
3.4- Limitations de l’ordonnancement en ligne

Exemples d’anomalies

Pour J2 = 3, ordonnancement toujours sous-optimal

Pour J2 = 5, ordonnancement optimal

Tiré de Jane W.S. Liu. Real-time systems. Prentice-Hall, 2000.

Pour identifier pire et meilleur cas, simulations exhaustives nécessaires

3- Programmes temps réel
3.4- Limitations de l’ordonnancement en ligne

Manquement des échéances

Parfois, on peut manquer l’échéance d’une tâche
� Temps réel dur : impact peut être catastrophique (ex. centrale nucléaire, cardiostimu-
lateur)
� Temps réel doux : impact moins important (ex. manquement frame video)
Valeur d’une tâche lorsque échéance est manquée dépend de l’application et du
retard encouru

Tiré de Jane W.S. Liu. Real-time systems. Prentice-Hall, 2000.

3- Programmes temps réel
3.4- Limitations de l’ordonnancement en ligne

Gérer manquement des échéances

Quoi faire lors de manquement d’échéance ?

� Arrêter la tâche pour laquelle il y a manquement
� Tâche courante n’a pas ou peu de valeur (ex. frame vidéo)
� Reprendre le contrôle pour poursuivre l’exécution
� Laisser la tâche se compléter avant de lancer la prochaine
� Tâche courante a une certaine valeur
� Tâches suivantes dépendent de la tâche actuelle
� Risque de perte de contrôle par effet domino
� Ne pas lancer la prochaine itération de la tâche
� Pertinence limitée, seulement pour certains contextes spécifiques de tâches périodiques
3- Programmes temps réel
3.4- Limitations de l’ordonnancement en ligne

Utilisation des tâches

Utilisation
� Utilisation ui d’une tâche temps réel périodique :
ei
i u =pi
� ei : durée d’exécution de la tâche i (valeur maximale possible, pire cas)
� pi : période d’exécution de la tâche i , c’est-à-dire délai minimum entre deux lancements
� Utilisation totale :
U= ui
�

� Supposons M, le nombre de processeurs

� Si U > M, il n’existe pas de cédule faisable, qui respecte toutes les échéances
� Si U < M, il existe une cédule faisable (assumant préemption et migration)
3- Programmes temps réel
3.4- Limitations de l’ordonnancement en ligne

Densité des tâches

Densité d’une tâche :
ei
ρi =
Δi − p i
� Δi = di − ri : échéance relative d’une tâche (différence en échéance absolue et temps
de lancement)
Densité de toutes les tâches :
ρ=
�
ρi
i
Pour un processeur (M = 1), cédule faisable si ρ ≤ 1
� EDF est capable trouver une telle cédule
� Condition suffisante mais non nécessaire, il peut exister des cédules faisables avec ρ > 1
Pour plus d’un processeur (M > 1)
� Si Δi = pi , une condition suffisante est :
ei
ρ ≤ M − (M − 1)Umax , oùUmax = max
i pi
3- Programmes temps réel
3.5- Tâches périodiques, apériodiques et sporadiques

3.5- Tâches périodiques, apériodiques et sporadiques

3- Programmes temps réel
3.5- Tâches périodiques, apériodiques et sporadiques

Acceptation de tâches apériodiques et sporadiques

Tâches apériodiques vs sporadiques

� Tâche apériodique : sans échéancier ou manquement d’échéancier toléré
� Faire un meilleur effort pour exécuter la tâche
� Tâche sporadique : éhéancier ferme, à respecter
� Si tâche sporadique est acceptée, on doit respecter les contraintes
Peut-on accepter de nouvelles tâches sporadiques ?
� Avant d’accepter, il faut vérifier si l’on peut faire le travail
� Définir un test d’acceptation peut établir si une tâche sporadique peut être traitée
� Acceptation peut être assez simple
1 Est-ce que l’on a des trous dans la planification actuelle suffisants pour exécuter tâche
avant son échéance ?
2 Si oui, est-ce qu’accepter nouvelle tâche sporadique n’empêchera pas d’autres tâches
sporadiques déjà acceptées de respecter leurs échéances ?
� Si durée d’exécution des tâches en cours peut varier, accepter selon le pire cas
3- Programmes temps réel
3.5- Tâches périodiques, apériodiques et sporadiques

Cédule de tâches périodiques, apériodiques et sporadiques

3- Programmes temps réel
3.5- Tâches périodiques, apériodiques et sporadiques

Tâches non planifiées dans ordonnancement hors ligne

Comment gérer tâches non planifiées (apériodiques ou sporadiques) dans ordon-

nancement hors ligne ?
� Cédule des tâches déjà calculées
� Tâche cédulées généralement d’une durée fixe et connue
� Pas nécessaire d’exécuter ces tâches à l’avance, seul respect des échéances importe
Slack stealing
� Insérer les tâches imprévues dans les « trous » de la cédule
� Test d’acceptation : s’assurer que les trous sont suffisants pour compléter la tâche à
temps
� Si test d’acceptation positif, réordonnancer tâches prévues et imprévues avec EDF
3- Programmes temps réel
3.5- Tâches périodiques, apériodiques et sporadiques

Exemple de slack stealing

3- Programmes temps réel
3.6- Ordonnancement et priorités dans Linux

3.6- Ordonnancement et priorités dans Linux

3- Programmes temps réel
3.6- Ordonnancement et priorités dans Linux

Ordonnancement dans Linux

Historique de l’ordonnancement dans Linux

� Ordonnanceur O(N) (avant version 2.6 du noyau, 1990-2004)
� Modèle simple et facile à comprendre
� Gère mal plusieurs processus et plusieurs processeurs
� Ordonnanceur O(1) (versions 2.6.1 à 2.6.23, 2004-2007)
� Ordonnancement en temps constant
� Fonctionne bien avec serveurs où charge est élevée
� Difficulté à identifier processus interactifs
� Ordonnanceur CFS (Completely Fair Scheduler) (depuis version 2.6.23, 2007)
� Ordonnancement O(logN)
� Assigne une part du temps processeur à chaque processus, selon la priorité
� Cédule processus afin de respecter autant que possible cette part de temps
� Le quantum n’est pas fixe, mais calculé à chaque fois pour chaque processus
3- Programmes temps réel
3.6- Ordonnancement et priorités dans Linux

Priorités dans Unix

Nice : priorité assignée aux processus dans Unix
� Nice variant entre -20 (plus élevée) et 19 (plus faible)
� Valeur par défaut de 0, hérité par les processus enfants
� Seul root peut réduire valeurs de nice
Modifier valeur de nice du processus courant

� inc : incrément à la valeur de nice actuelle

� Retourne nouvelle valeur de nice du processus
Autres fonctions pertinentes

� Voir le manuel pour détails d’utilisation

3- Programmes temps réel
3.6- Ordonnancement et priorités dans Linux

Commandes nice et renice

Commandes nice et renice
� nice -n PRIORITE COMMANDE : exécute programme COMMANDE avec valeur PRIORITE
ajoutée à la priorité par défaut
� renice -n PRIORITE PID : change priorité du processus PID en ajoutant valeur PRIORITE
à la priorité actuelle
� Seul root peut réduire valeurs de nice
Commande ps permet d’obtenir état des processus, incluant priorité
� Lister état des processus de l’utilisateur
$ ps -l
F S UID PID PPID C PRI NI ADDR SZ WCHAN TTY TIME CMD
0 S 1000 955 953 0 80 0 - 1523 wait pts/0 00 :00 :00 bash
0 R 1000 1174 955 0 80 0 - 1071 - pts/0 00 :00 :00 ps
� Changer priorité du processus
$ nice -n 5 ps -l
F S UID PID PPID C PRI NI ADDR SZ WCHAN TTY TIME CMD
0 S 1000 955 953 0 80 0 - 1523 wait pts/0 00 :00 :00 bash
0 R 1000 1175 955 0 85 5 - 1071 - pts/0 00 :00 :00 ps
Autre commande utile : top
� Moniteur textuel interactif des activités
3- Programmes temps réel
3.6- Ordonnancement et priorités dans Linux

Priorités dans Linux

Approche de Linux pour gérer les priorités : quantum variable
� Processus de plus haute priorité aura quantum plus grand qu’un processus de basse priorité
Gestion des priorités avec CFS
� Valeur du nice utilisée pour pondérer la part relative du processeur
� Différence de priorité de 5 donne une pondération 1 pour 3
� Ex. processus A (nice 0) s’exécute pour 15ms alors que processus B (nice de 5) s’exécute
pour 5ms
� CFS utilise une latence cible pour déterminer quanta
� Latence cible : temps désiré entre deux exécutions d’un processus (paramètre ajustable)
� Ex. latence cible de 20ms, deux processus actifs de priorité égale, quantum de 10ms
chacun
� Latence cible établie selon niveau de réponse désiré
� Granularité minimale : valeur plancher de latence cible (1ms par défaut), pour réduire
impact changement de contexte
Prochain processus choisi selon différence plus élevée entre quantum et temps d’exé-
cution jusqu’à présent
� CFS utilise arbre bicolore à l’interne pour choisir ce processus
3- Programmes temps réel
3.7- Ordonnancement temps réel dans Linux

3.7- Ordonnancement temps réel dans Linux

3- Programmes temps réel
3.7- Ordonnancement temps réel dans Linux

Algorithmes d’ordonnancement temps réel

CFS est algorithme d’ordonnancement générique
� Pas particulièrement adapté au temps réel
Ordonnanceurs temps réel de Linux
� Premier arrivé, premier servi (SCHED_FIFO)
� Exécute processus temps réel prioritaire jusqu’à interruption par le processus (céder
volontairement, attente sur E/S ou autre processus plus prioritaire disponible)
� Risques de famine pour autres processus de priorité égale ou inférieure
� Round robin (SCHED_RR)
� Alterne entre processus temps réel de même priorité, pour un quantum fixe
� Plus juste pour processus de même priorité, risque de famine pour processus moins
prioritaires
Processus désigné comme étant temps réel avec priorité plus basse
� Processus réguliers ont priorité entre 100 et 139
� Priorité spécifiée par le nice
� Valeur de priorité corresponds à valeur du nice + 120
� Processus temps réel ont priorité entre 0 et 99 sur Linux
3- Programmes temps réel
3.7- Ordonnancement temps réel dans Linux

Modifier algorithme d’ordonnancement

Modifier algorithme d’ordonnancement d’un processus

� pid : ID processus dont algorithme change, 0 si processus courant

� policy : algorithme d’ordonnancement à utiliser
� SCHED_NORMAL : CFS
� SCHED_FIFO : premier arrivé, premier servi (temps réel)
� SCHED_RR : round robin (temps réel)
� param : dénir paramètre, pour l’instant seul param->sched_priority est défini
Pour connaître algorithme d’ordonnancement actuel d’un processus

Pour EDF, il faut préciser ordonnanceur SCHED_DEADLINE en appelant la fonc-

tion sched_setattr (présentée plus loin)
3- Programmes temps réel
3.7- Ordonnancement temps réel dans Linux

Priorité temps réel des processus

Valeurs de priorités temps réel

� Interval de valeur n’est pas portable
� Pour connaître intervalle de la plateforme courante

� Retourne priorité max/min de l’algorithme d’ordonnancement policy

Assigner priorité lors ajout du processus à l’ordonnanceur temps réel
� Assigner priorité du processus à la variable sched_priority de l’argument param (struct
sched_param*) lors appel à fonction sched_setscheduler ou sched_setparam
Priorités héritées par processus enfants
3- Programmes temps réel
3.7- Ordonnancement temps réel dans Linux

Changer priorités temps réel

Appels système pertinents

� pid : ID du processus pour lequel on change paramètre, 0 pour processus courant

� param : paramètres modifiés
Pour SCHED_FIFO et SCHED_RR, seule priorité des processus est pertinente
3- Programmes temps réel
3.7- Ordonnancement temps réel dans Linux

Obtenir priorités temps réel

Obtenir priorité des processus temps réel

$ ps -eo pid, class, pri, nice, rtprio, comm
———————————————————————
PID CLS PRI NI RTPRIO COMMAND
1 TS 19 0 - systemd
2 TS 19 0 - kthreadd
3 TS 19 0 - ksoftirqd/0
4 FF 41 - 1 ktimersoftd/0
6 TS 39 -20 - kworker/0 :0H
———————————————————————
...
3- Programmes temps réel
3.7- Ordonnancement temps réel dans Linux

Attributs de processus temps réel

Fonctions lire et modifier attributs de processus

� pid : ID du processus, 0 si processus courant

� attr : pointeur à structure des attributs
� flags : doit âtre égal à 0 (pour expansion future)
� size : taille (en octet) de la structure pointée par attr
� Peut être calculé simplement par sizeof(*attr)
Si ordonnancement de tâches n’est pas possible, fonction retourne EBUSY
� Peut être assez commun selon tâches temps réel et politique (ex. EDF)
3- Programmes temps réel
3.7- Ordonnancement temps réel dans Linux

Struct sched_attr

Éléments de la struct sched_attr

3- Programmes temps réel
3.8- Ordonnanceur SCHED_DEADLINE

3.8- Ordonnanceur SCHED_DEADLINE

3- Programmes temps réel
3.8- Ordonnanceur SCHED_DEADLINE

Ordonnanceur SCHED_DEADLINE

Ordonnanceur SCHED_DEADLINE implanté depuis Linux 3.14 (2014)

� Implémente ordonnanceur EDF vu précédemment
N’implémente pas de dépendances entre processus
� Calculer préalablement temps de lancement et échéance effectifs, comme présenté
précédemment
Paramètres tâches EDF spécifiés par fonction sched_setattr
� sched_runtime : durée d’exécution (pire cas pour temps réel dur ou valeur moyenne
pour temps réel doux)
� sched_deadline : échéance relative relativement au temps de lancement
� sched_period : période à laquelle la tâche se répète
Variables définies comme entiers non signées sur 64 bits (uint64, typiquement un-
signed long)
� Unité des variables : 1ns (sched_period=10000 équivaut à période de 10µs)
3- Programmes temps réel
3.8- Ordonnanceur SCHED_DEADLINE

Paramètres tâches avec SCHED_DEADLINE

3- Programmes temps réel
3.8- Ordonnanceur SCHED_DEADLINE

Exécution d’une tâche avec SCHED_DEADLINE

État d’une tâche
� Échéance planifiée : échéance absolue du cycle courant
� Durée d’exécution restante : temps restant pour compléter tâche dans cycle courant
Tâche non faisable au cycle courant si :

temps courant + durée d’exécution restante < échéance planifiée

ou
durée d’exécution restante durée d’exécution
>
échéance planifiée − temps courant période
Dans ce cas, on réinitialise le cycle :

échéance planifiée = temps courant + échéance relative

durée d’exécution restante = durée d’exécution

3- Programmes temps réel
3.8- Ordonnanceur SCHED_DEADLINE

Exécution d’une tâche avec SCHED_DEADLINE

Lorsque tâche s’exécute pour une durée t et ensuite cède la main, alors

durée d’exécution restante = durée d’exécution restante − t

Lorsque durée d’exécution restant ≤ 0, alors la tâche est mise de côté jusqu’au
prochain cycle
Au début d’un nouveau cycle :

échéance planifiée = échéance planifiée + période

durée d’exécution restante = durée d’exécution restante + période

3- Programmes temps réel
3.9- Gestion de l’ordonnancement temps réel

3.9- Gestion de l’ordonnancement temps réel

3- Programmes temps réel
3.9- Gestion de l’ordonnancement temps réel

Cohabitation des processus

Assignation des ressources selon ordonnanceur

� Différents processus s’exécutant avec différents ordonnanceurs, qu’est-ce qui se passe ?
� Ordre de traitement
1 SCHED_DEADLINE : EDF
2 SCHED_RR : round robin
3 SCHED_FIFO : premier arrivé, premier servi
4 SCHED_NORMAL : CFS
� Famine pour processus réguliers si toutes ressources consommées par processus temps
réel
Faire cohabiter processus réguliers et temps réel est important
� Maintenance et traitement de base (ex. répondre à la ligne de commande)
3- Programmes temps réel
3.9- Gestion de l’ordonnancement temps réel

Ajustement du débit

Ajustement du débit des processus temps réel (real-time throttling)

� Assigner part du CPU au processus réguliers (ordonnanceur CFS)
� Valeurs configurées via « fichiers » dans /proc
� /proc/sys/kernel/sched_rt_period_us : valeur d’une période de référence en µs (par
défaut, 1000000µs = 1s)
� /proc/sys/kernel/sched_rt_runtime_us : débit pour processus temps réel en µs (par
défaut 950000µs = 0, 95s)
� Donc, par défaut, jusqu’à 95% des processeurs assignés aux processus temps réel, au
minimum 5% aux processus réguliers
3- Programmes temps réel
3.9- Gestion de l’ordonnancement temps réel

Association de processus à processeurs

Dans Linux, processus peuvent migrer entre processeurs

� Système dynamique sur multiprocesseur, selon nomenclature vue auparavant
Fonctions de l’API

� pid : ID du processus, si 0 processus courant

� cpusetsize : taille en octet de variable mask
� mask : masque (vecteur de bits) donnant l’affinité entre le processus et les processeurs
3- Programmes temps réel
3.9- Gestion de l’ordonnancement temps réel

Céder l’exécution
Lorsque processus temps réel a terminé sa tâche temps réel, il devrait céder la main
d’exécution
Appel système pour céder la main

Fonction très importante pour assurer bon fonctionnement

� Libérer ressources pour les autres processus
� Éviter famine
� Comportement lorsque sched_yield est appelé :
� SCHED_FIFO et SCHED_RR : processus placé en fin de file
� SCHED_DEADLINE : ordonnanceur considère cycle d’exécution terminé, tâche sera
lancée seulement à prochaine période, assigne 0 à durée d’exécution restante
Appels E/S bloquants (ex. read/write) cèdent également main d’exécution
� Faire attention à ce point pour éviter des surprises
3- Programmes temps réel
3.9- Gestion de l’ordonnancement temps réel

Fin de Séance
Vos Questions ?