Programmation Temps Réel

Ordonnancement de tâches apériodiques

Yann Thoma

Reconfigurable and Embedded Digital Systems Institute

Haute Ecole d’Ingénierie et de Gestion du Canton de Vaud

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License

Septembre 2017

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 1 / 26

Plan

Période d’étude

Périodicité des tâches ⇒ Ordonnancement cyclique

L’algorithme d’ordonnancement consistera à trouver une
séquence de tâches caractérisée par une périodicité de longueur
L
La période de longueur L est appelée période d’étude ou période
de base.
Ce qui signifie que si l’échéance de chacune des tâches est
respectée dans la période d’étude, toutes les autres occurrences
le seront. La séquence ainsi déterminée peut être reproduite à
l’infini.
Evaluation
Valide quel que soit l’algorithme d’ordonnancement
La période d’étude peut s’avérer très longue selon les relations
entre périodes.
Adapté aux ordonnancements hors-ligne (simulation)
Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 2 / 26
 Plan

Période d’étude

Si les tâches sont synchrones (débutent au même instant)

L = [0, PPCM(Pi )]
Si les tâches sont asynchrones (ne débutent pas au même
instant)
L = [min{ri,0 }, 2 × PPCM(Pi ) + max{ri,0 , rj + Dj }]
Où ri,0 est la date d’activation de la première occurence de la tâche
périodique Ti
Et rj est la date d’activation de la tâche apériodique Tj

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 3 / 26

Introduction

Introduction

Tâches périodiques
Facile de prévoir un ordonnancement
Possible de garantir l’ordonnançabilité
Tâches apériodiques
Peuvent arriver n’importe quand
Difficile de prévoir un ordonnancement
Impossible de garantir l’ordonnançabilité
Tâches sporadiques
Temps minimal entre 2 événements borné
Difficile de prévoir un ordonnancement
Possible de garantir l’ordonnançabilité

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 4 / 26

 Introduction

Introduction

Tâches sporadiques
L’ordonnancement peut être garanti off-line
Pour des tâches à échéance stricte
Tâches apériodiques
L’ordonnancement peut être garanti on-line
Pour des tâches à échéance ferme
A l’arrivée d’une tâche, elle est acceptée ou rejetée
Impossible pour des tâches à échéance stricte

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 5 / 26

Introduction

Hypothèses

Les tâches périodiques sont:

Agencées par RM
A échéance sur requête
Lancées au temps t = 0 (déphasage nul)
Les temps d’arrivée des tâches apériodiques ne sont pas connus
Le temps minimal d’activation d’une tâche sporadique est égal à
son échéance
Préemption
single CPU

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 6 / 26

 Traitement en arrière plan

Traitement en arrière plan

En anglais: background scheduling ou background processing

Concept: Les tâches apériodiques sont exécutées lorsque le
processeur est oisif
Le temps de réponse peut être long
Possible si les contraintes de temps ne sont pas strictes
Et si les tâches périodiques ne chargent pas trop le processeur
Avantage: grande simplicité d’implémentation

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 7 / 26

Traitement en arrière plan

Traitement en arrière plan: exemple

Tâche périodique Coût Période

T1 2 6
T2 4 10

T2

T1
Re3 Re4
Ap.
0 5 10 15 20 25 30

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 8 / 26

 Traitement en arrière plan

Files d’ordonnancement

Implémentation grâce à deux files d’attente

Les tâches de basse priorité sont servies si aucune tâche de
haute priorité n’est prête

Tâches périodiques RM
Haute priorité

CPU

Tâches apériodiques FIFO

Basse priorité

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 9 / 26

Traitement en arrière plan

Traitement vs. serveur

Un serveur est une tâche périodique

Rôle:
servir les tâches apériodiques
Implémentations:
Serveur à scrutation
Serveur ajournable
Serveur à échanges de priorité
Serveur sporadique
Serveur "Slack stealer"

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 10 / 26

 Serveur à scrutation

Serveur à scrutation

Le serveur est une tâche périodique

Il est caractérisé par:
Une période Ps
Un temps d’exécution Cs
Appelé capacité du serveur
Ordonnancé selon le même algorithme que les tâches périodiques
L’ordonnancement des tâches apériodiques peut être géré
différemment

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 11 / 26

Serveur à scrutation

Gestion des tâches apériodiques

A chaque activation du serveur, il vérifie s’il y a des tâches

apériodiques prêtes
Si non, il s’endort
Si oui, il les sert
Si une tâche apériodique arrive pendant le temps réservé au
serveur, elle est servie au tour suivant

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 12 / 26

 Serveur à scrutation

Serveur à scrutation: exemple

Tâche Coût Période

T1 2 6
T2 1 4
Ts 2 5

T2

T1
Re2 Re1 Re2 Re1
ap
0 5 10 15 20

Cs

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 13 / 26

Serveur à scrutation

Serveur à scrutation: ordonnançabilité

Le serveur est une tâche périodique, donc nous pouvons
appliquer la règle de RM

Condition suffisante d’ordonnançabilité

n
X Ci Cs 1
+ ≤ UlubRM (n + 1) = (n + 1)(2 n+1 − 1) (1)
Pi Ps
i=1

Il est possible d’avoir plusieurs serveurs, avec chacun une priorité

différente
Pour m serveurs, nous avons:

Condition suffisante d’ordonnançabilité

n m
X Ci X Cs i
1
+ ≤ UlubRM (n + m) = (n + m)(2 n+m − 1) (2)
Pi Psi
i=1 i=1

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 14 / 26

 Serveur à scrutation

Serveur à scrutation: garanties apériodiques

L’échéance d’une tâche apériodique peut-elle être garantie?

Si Ca ≤ Cs alors:
La tâche doit attendre au plus une période pour commencer
La condition est donc:
2Ps ≤ Da (3)
Dans le cas général, la condition est:
 
Ca
Ps + Ps ≤ Da (4)
Cs

Ceci n’est valable que pour une tâche unique (calcul plus délicat
pour des tâches multiples)

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 15 / 26

Serveur ajournable

Serveur ajournable

Problèmes du serveur à scrutation:

S’il n’y a pas de tâche apériodique à traiter, le temps du serveur est
perdu
Si une tâche apériodique arrive pendant la période de traitement,
elle n’est pas directement exécutée
Serveur ajournable (deferrable server)
La capacité est sauvegardée si non utilisée
Permet un meilleur temps de réponse

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 16 / 26

 Serveur ajournable

Serveur ajournable: exemple

Tâche Coût Période

T1 2 6
T2 1 4
Ts 2 5

T2

T1
Re2 Re1 Re2 Re1
ap
0 5 10 15 20

Cs

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 17 / 26

Serveur ajournable

Serveur ajournable: problème

Tâche Coût Période

T1 2 5
Ts 2 4

T1
2 2 2 2 2 2
ap
0 5 10 15 20

Cs

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 18 / 26

 Serveur ajournable

Serveur ajournable: ordonnançabilité

Problème: l’ajournement du traitement peut compromettre
l’exécution d’une tâche périodique
La condition d’ordonnançabilité devient donc:

Condition suffisante d’ordonnançabilité

n
X Ci Us + 2
≤ ln( ) (5)
Pi 2Us + 1
i=1

Et:

Ulub ' 0.652

Pour U = Up + Us , et obtenu avec:
√
33 − 5
Us = ' 0.186
4
Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 19 / 26

Serveur ajournable

Least Upper Bound

Ulub(Us )
1

ln(2)
0.652

Us
0 .1 .2 .3 .4 .5 .6 .7 .8 .9 1

Valable pour
n
X Ci
U= + Us < Ulub
Pi
i=1

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 20 / 26

 Serveur ajournable

Serveur ajournable: autre exemple

Tâche Coût Période

T1 1 5
Ts 2 4
Ordonnançable?

T1
2 2 2 2 2 2
Ts
0 5 10 15 20

Cs

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 21 / 26

Serveur sporadique

Serveur sporadique

But: améliorer le temps de réponse des tâches apériodiques

La politique de recharge du serveur et différente des deux
versions précédentes
Il possède une capacité Cs et une période Ps
Le serveur consiste en une tâche qui s’exécute lorsqu’il y a
conjointement:
Des tâches apériodiques à servir
Sa capacité courante est non nulle
Sa priorité est éligible

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 22 / 26

 Serveur sporadique

Serveur sporadique

Soit:
Pexe la priorité de la tâche actuellement en cours d’exécution
Ps la priorité du serveur sporadique
Alors:
Le serveur est dit actif lorsque Pexe ≥ Ps
Le serveur est dit au repos (idle) lorsque Pexe < Ps
Lorsqu’il s’exécute, sa capacité diminue
Sa capacité est restituée un temps Ps après le début de son
activation
La quantité restituée est égale à la capacité consommée entre
son activation et la fin de sa période d’activation

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 23 / 26

Serveur sporadique

Serveur sporadique: exemple

Tâche Coût Période

T1 1 5
T2 4 15
Ts 5 10

T2

T1
2 2
Tap
0 5 10 15 20

Cs

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 24 / 26

 Comparaisons

Comparaison: scrutation vs. sporadique

Serveur à scrutation de tâches

Facile à implémenter
Ordonnançable avec RM
Le serveur est une tâche périodique à priorité fixe.
Gaspillage du temps CPU
La capacité non utilisée est perdue.
Fonctionne bien si peu de tâches apériodiques (la capacité peu être
déterminée de manière optimale).
Serveur sporadique
Meilleure utilisation du CPU
Bien adapté si beaucoup de tâches apériodiques
Plus difficile à implémenter

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 25 / 26

Comparaisons

Comparaison (2)

Algorithme Perf. Complex. Mémoire Complex.

comput. d’impl.
Background
Scrutation
Ajournable
Sporadique
Priority exchange
Slack stealer

Y. Thoma (HES-SO / HEIG-VD / REDS) Programmation Temps Réel Septembre 2017 26 / 26