Upload
others
View
8
Download
0
Embed Size (px)
Citation preview
NSY103 - 2011-2012 J. Delacroix 1
Systèmes temps réel - Ordonnancement
NSY103 - 2011-2012 J. Delacroix 2
Application temps réel
• Contexte applicatif
MesuresEvénements
Fonction de suivi
CommandesFonction de
pilotage
Contraintes de temps
Application de contrôlemultitâches
Exécutif temps réel
NSY103 - 2011-2012 J. Delacroix 3
Application temps réel
� Les tâches – processus composant une application temps réel peuvent être, en fonction de leurs caractéristiques, répertoriées sous différents types. Deux critères interviennent principalement :
� la façon dont la tâche survient dans la vie du système temps réel. – tâches périodiques, à intervalles réguliers (typiquement des mesures
ou commandes de systèmes asservis échantillonnés) – tâches apériodiques qui surviennent aléatoirement (typiquement une
alarme) ;� le degré de flexibilité de la tâche vis-à-vis de l'application temps réel
– les tâches à contraintes strictes (tâches critiques), – tâches à contraintes relatives (tâches essentielles),
� Chaque tâche possède un délai critique : temps maximal pour s'exécuter depuis sa date de réveil. La date butoir résultante est appelée échéance. Le dépassement d'une échéance est appelé faute temporelle.
réveil échéance
Délai critique
Exécution non terminée :faute temporelle
NSY103 - 2011-2012 J. Delacroix 4
Tâches périodiques
• Elles correspondent aux mesures sur le procédé ; elles se réveillent régulièrement (toutes les P unités de temps)�périodiques strictes : contraintes temporelles à respecter absolument�périodiques relatives : contraintes temporelles qui peuvent être non respectées de temps à autre �périodiques à échéance sur requête (délai critique R = période P)
tr0 d0
C max
R
r0 + P
P
• r0, date de premier réveil• P, période• rk, date de réveil de la kèmerequête
rk = r0 + kP• C, temps d'exécution• R, délai critique• dk, échéance = rk + R
Tp (r 0, C, R, P)
0 ≤ ≤ ≤ ≤ C ≤ ≤ ≤ ≤ R ≤ ≤ ≤ ≤ P
NSY103 - 2011-2012 J. Delacroix 5
Tâches apériodiques
• Elles correspondent aux événements ; elles se réveillent de manière aléatoire� apériodiques strictes : contraintes temporelles dures à respecter absolument�apériodiques relatives : contraintes temporelles molles qui peuvent être non respectées de temps à autre (sans échéance)
r d
C max
• r, date aléatoire de réveil• C, temps d'exécution• R, délai critique• d, échéance = r + R
Tap (r, C, R)
0 <<<< C ≤ ≤ ≤ ≤ R
NSY103 - 2011-2012 J. Delacroix 6
EXÉCUTIF ET ORDONNANCEMENT TEMPS RÉEL
• L ’application temps réel est gérée par un système d’exploitation qualifié d’exécutif temps réel. Cet exécutif possède les services classiques d’un système d’exploitation, mais plus particulièrement :� - une gestion du temps avec une
résolution accrue ;� - une gestion mémoire simplifiée;� - une allocation des ressources sans
interblocage et inversion de priorité ;� - un ordonnancement spécifique et
certifiable.
Il est nécessaire de vérifier avant le lancement de l'application (hors ligne) le respect des contraintes temporelles. Cette certification s'effectue à l'aide de tests d'acceptabilité qui prennent en compte les paramètres temporels des tâches (temps d'exécutions des tâches) .
NSY103 - 2011-2012 J. Delacroix 7
CARACTÉRISTIQUES DE L'ORDONNANCEMENT TEMPS RÉEL
• Test d'acceptabilité
Complexité de l’ensemble de n tâches
Condition suffisante
Conditionnécessaire
Condition exacte
(rarement)
FausseEnsemble de n tâches
non ordonnançable
VraieEnsemble de n tâches
ordonnançable
)12( /1
1
−≤∑=
nn
i i
i nP
C
Un exécutif déterministe est un exécutif pour lequel les temps de certaines opérations système et matérielles élémentaires peuvent être bornés : temps de commutation, temps de prise en compte des interruptions, etc…
NSY103 - 2011-2012 J. Delacroix 8
ALGORITHMES D'ORDONNANCEMENT POUR LES TÂCHES PÉRIODIQUES INDÉPENDANTES
• Algorithmes en ligne et préemptifs avec un test d'acceptabilitéévaluable hors ligne
• Nous ordonnançons un ensemble de tâches périodiques Les priorités affectées aux tâches sont soit constantes (évaluées hors ligne et fixes par la suite), soit dynamiques (elles changent dans la vie de la tâche)
• L'ordonnancement d'un ensemble de tâches périodiques est cyclique et la séquence se répète de manière similaire sur ce que l'on appelle la période d'étude.
• Pour un ensemble de tâches périodiques à départ simultané (t = 0), la période d'étude est : [0, PPCM(Pi)]
NSY103 - 2011-2012 J. Delacroix 9
Rate Monotonic
• Priorité de la tâche fonction de sa période. Priorité constante
• La tâche de plus petite période est la tâche la plus prioritaire
• Pour un ensemble de n tâches périodiques à échéance sur requêteTpi (r0, Ci, Pi), un test d'acceptabilité est (condition suffisante) :
)12( /1
1
−≤∑=
nn
i i
i nP
C
Algorithmes d'ordonnancement pour les tâches périodiqu es indépendantes
NSY103 - 2011-2012 J. Delacroix 10
Rate Monotonic
Algorithmes d'ordonnancement pour les tâches périodiqu es indépendantes
(3/20 + 2/5 + 2/10) ≤ 0, 779 est vrai
NSY103 - 2011-2012 J. Delacroix 11
Inverse Deadline
• Priorité de la tâche fonction de son délai critique. Priorité constante
• La tâche de plus petit délai critique est la tâche la plus prioritaire
• Pour un ensemble de n tâches périodiques Tpi (r0, Ci, Ri, Pi), un test d'acceptabilité est (condition suffisante) :
)12( /1
1
−≤∑=
nn
i i
i nR
C
ALGORITHMES D'ORDONNANCEMENT POUR LES TÂCHES PÉRIODIQUES INDÉPENDANTES
NSY103 - 2011-2012 J. Delacroix 12
Inverse Deadline
ALGORITHMES D'ORDONNANCEMENT POUR LES TÂCHES PÉRIODIQUES INDÉPENDANTES
(3/15 + 1/4 + 2/9) ≤ 0,779 est vrai
NSY103 - 2011-2012 J. Delacroix 13
Earliest Deadline
• Priorité de la tâche dynamique
• A l’instant t, la tâche de plus proche échéance est la tâche la plus prioritaire (la plus urgente)
• Pour un ensemble de n tâches périodiques Tpi (r0, Ci, Ri, Pi), un test d'acceptabilité est (condition suffisante) :
11
≤∑=
n
i i
i
R
C
ALGORITHMES D'ORDONNANCEMENT POUR LES TÂCHES PÉRIODIQUES INDÉPENDANTES
NSY103 - 2011-2012 J. Delacroix 14
Earliest Deadline
ALGORITHMES D'ORDONNANCEMENT POUR LES TÂCHES PÉRIODIQUES INDÉPENDANTES
(3/8 + 1/4 + 2/7) ≤ 1 est vrai
NSY103 - 2011-2012 J. Delacroix 15
ORDONNANCEMENT POUR LES TÂCHES PÉRIODIQUES AVEC CONTRAINTES DE RESSOURCES
On considère trois taches périodiques P1, P2, P3 à échéance sur requête dont les caractéristiques sont les suivantes
12
6
18
période
24 unités3P3
14 unités2P2
35 unités0P1
priorité (plus petite valeur =
plus grande priorité)
Temps d'exécution
Date d’arrivée
Les trois processus sont ordonnancés selon Rate Monotonic.On suppose à présent que les tâchess P1 et P2 utilisent une même ressource critique R1, protégée par un sémaphore Sem1 initialisé à 1. P3 ne fait que du calcul.Les étapes des deux tâches P1 et P2 sont les suivantes :
Calcul durant 1 unitéP(Sem1)
Faire calcul en utilisant R1 durant 2 unitésV (Sem1)
Calcul durant 1 unité
Calcul durant 1 unitéP (Sem1)
Faire calcul en utilisant R1 durant 2 unités
V (Sem1)Calcul durant 2 unités
P2P1
NSY103 - 2011-2012 J. Delacroix 16
ORDONNANCEMENT POUR LES TÂCHES PÉRIODIQUES AVEC CONTRAINTES DE RESSOURCES : inversion de priorité
12
6
18
période
24 unités3P3
14 unités2P2
35 unités0P1
priorité(plus petite
valeur = plus grande
priorité)
Temps d'exécution
Date d’arrivée
Calcul durant 1 unitéP(Sem1)
Faire calcul en utilisant R1 durant 2 unités
V (Sem1)Calcul durant 1 unité
Calcul durant 1 unitéP (Sem1)
Faire calcul en utilisant R1 durant 2 unités
V (Sem1)Calcul durant 2 unités
P2P1
NSY103 - 2011-2012 J. Delacroix 17
ORDONNANCEMENT POUR LES TÂCHES PÉRIODIQUES AVEC CONTRAINTES DE RESSOURCES : protocole de la priorité
plafonnée
12
6
18
période
24 unités3P3
14 unités2P2
35 unités0P1
priorité(plus petite
valeur = plus grande
priorité)
Temps d'exécution
Date d’arrivée
Calcul durant 1 unitéP(Sem1)
Faire calcul en utilisant R1 durant 2 unités
V (Sem1)Calcul durant 1 unité
Calcul durant 1 unitéP (Sem1)
Faire calcul en utilisant R1 durant 2 unités
V (Sem1)Calcul durant 2 unités
P2P1
Le protocole de la priorité plafonnée vise à résoudre le problème de l’inversion de priorité.Il fonctionne selon le principe suivant :• chaque ressource R possède une priorité qui est celle de la tâche de plus haute prioritépouvant demander son utilisation ;• une tâche T hérite de la priorité de cette ressource R lorsqu’elle l’obtient et la garde jusqu’à ce qu’elle la libère;• cependant, la tâche T ne peut obtenir la ressource R que si la priorité de R est strictement supérieure à celles de toutes les ressources déjà possédées par les autres tâches Tx. Par ce biais, on prévient l’interblocage.
NSY103 - 2011-2012 J. Delacroix 18
ORDONNANCEMENT POUR LES TÂCHES PÉRIODIQUES AVEC CONTRAINTES DE RESSOURCES : protocole de la priorité
plafonnée
12
6
18
période
24 unités3P3
14 unités2P2
35 unités0P1
priorité(plus petite
valeur = plus grande
priorité)
Temps d'exécution
Date d’arrivée
Calcul durant 1 unitéP(Sem1)
Faire calcul en utilisant R1 durant 2 unités
V (Sem1)Calcul durant 1 unité
Calcul durant 1 unitéP (Sem1)
Faire calcul en utilisant R1 durant 2 unités
V (Sem1)Calcul durant 2 unités
P2P1
R1 a une priorité de 1
NSY103 - 2011-2012 J. Delacroix 19
Linux et le temps réel
NSY103 - 2011-2012 J. Delacroix 20
Linux est-il adapté aux contraintes temps réel ?
• Le système Linux est un système d'exploitation conçu pour offrir un service équitable aux processus. Quatre points sont problématiques.� l'ordonnancement des processus est un ordonnancement de
type temps partagé. Les politiques SCHED_RR et SCHED_FIFO qualifiées de temps réel n’offrent aucune garantie de respect des contraintes temporelles ;
� le noyau est non préemptif, c'est-à-dire que lorsqu'un processus s'exécute en mode noyau, ce processus ne peut être préempté, même si un processus plus prioritaire a besoin du processeur ;
� les sections critiques du noyau sont réalisées en masquant les interruptions. Ainsi, la prise en compte d'une interruption destinée à un processus temps réel peut être retardée jusqu'à ce qu'une section critique du noyau soit libérée ;
� la fréquence de l’horloge système est de l’ordre de 100 Hz.
NSY103 - 2011-2012 J. Delacroix 21
Modifier Linux pour l’adapter au temps réel
• modifier l’exécution du système Linux afin de rendre le noyau préemptif. Le noyau devient réentrant et que les fonctions le composant subissent des appels multiples et concurrents ;
• verrouiller en mémoire centrale les pages de l’espace d’adressage des tâches temps réel afin d’éviter les défauts de pages ;
• améliorer la résolution temporelle de l’horloge du système ;• utiliser un micronoyau temps réel cohabitant avec le noyau
Linux. Ce micronoyau exécute les tâches temps réel. Le noyau Linux est considéré par ce micronoyau comme la tâche de plus faible priorité. Elle n’est exécutée que lorsqu’aucune autre tâche temps réel n’est prête
� exemple RTLINUX.
NSY103 - 2011-2012 J. Delacroix 22
RT- Linux
NSY103 - 2011-2012 J. Delacroix 23
RT-LINUX
•
GESTIONNAIRE IT
IRQ 7
Thread apériodique réveillé par IRQ7Ecrit 0 sur la port parallèleAffichage de l’heure d’écriture
Thread périodique de période 1000Écrit 5 sur le port parallèleAffichage de l’heure d’écriture
Thread linux classique ; lit les RT-FIFOSEt affiche les heures d’écritures sur le port parallèle
RT-FIFOS
Module temps réel contenant deux threads
Ordonnanceur RT_LINUX
Ordonnanceur_LINUXESPACE NOYAU
ESPACE USER