Gestion des processus dans les systèmes d’exploitation temps réel

 Sauvegarde de la planification pré-calculé dans une table Le système crée toutes les tâches qui seront exécutées : Alloue la mémoire pour le code et les données de chaque tâche Apporte le code exécuté par la tâche dans la mémoire

L’ordonnanceur configure le timer matériel pour générer des interruptions à la première décision, tk=0 À chaque interruption du timer à l’instant tk : L’ordonnanceur configure l’interruption du timer pour expirer à tk+1 Si T(tk) = I et une tâche apériodique est en attente, alors démarrer la tâche apériodique Sinon, démarrer la prochaine tâche du processus T(tk) 7

<!-- Slide number: 8 --> # Implémentation d’un ordonnancement cyclique

 8

<!-- Slide number: 9 --> # Ordonnancement cyclique structuré L’ordonnancement cyclique arbitraire table driven est flexibles, mais inefficace Nécessite des interruptions précises du timer basée sur le temps d'exécution des tâches En imposant une structure, l’implémentation devient plus facile les décisions de planification sont réalisées à des intervalles périodiques (frames) de longueur f Exécution d’une liste fixe de tâches à chaque frame, la préemption n’est prise en compte qu’aux limites des frames la phase de chaque tâche périodique doit être un multiple non négatif du frame La première tâche de chaque processus est libérée au début d'un frame Deux avantages : L’ordonnanceur peut facilement vérifier les dépassements et les délais manqués à la fin de chaque frame Il est possible d’utiliser des interruptions périodiques d'horloge, plutôt qu’un timer programmable 9

<!-- Slide number: 10 --> # Ordonnancement cyclique structuré Décision d'ordonnancement prise périodiquement

De façon périodique Choisir la tâche à exécuter Effectuer les opération de contrôle et de suivi

Cycle principal: étendues durant une hyper-période

 frame f Points de décision

 10

Notes:

<!-- Slide number: 11 --> # Contraintes de la taille du frame Soit f la longueur de l'étendue.

Comment choisir f ? Chaque tâche doit pouvoir commencer et terminer son exécution durant le frame :

 évite la préemption

f divise l'hyper-période (lcm(p1, .. , pn)). Donc, f doit diviser la période d'au moins une tâche :

 réduit au minimum le nombre des entrées de l’ordonnancement cyclique

11

<!-- Slide number: 12 --> # Contraintes de la taille du frame Pour permettre à l’ordonnanceur de vérifier que les tâches finissent à leurs délais, il doit y avoir au moins une limite dans le frame entre le temps d’arrivée d’une tâche et son délai.  Il y a au moins une étendue entre l'arrivée et le délai de chaque tâche


 12

<!-- Slide number: 13 --> # Contraintes de la taille du frame Les trois contraintes doivent être satisfaites

13

Notes:

<!-- Slide number: 14 --> # Exemple 1 :




 14

Notes:

<!-- Slide number: 15 --> # Exemple 2 : Tâche Période Délai Temps d'exécution τi Ti Di Ci ------------------------------------------------------------ τ1 15 14 1 τ2 20 26 2 τ3 22 22 3

Première contrainte => f est au moins 3. Deuxième contrainte => f est 3, 4, 5, 10, 11, 15, 20 ou 22. Troisième contrainte => f est 3, 4, 5, 10 ou 11. 15

Notes:

<!-- Slide number: 16 --> # Découpage de tâches



 Découper T3

 16

Notes:

<!-- Slide number: 17 --> # Noyau cyclique (cyclic executive)

 17

Notes:

<!-- Slide number: 18 --> # Planification des tâches apériodiques Pour le moment, les tâches apériodiques sont planifiées à la fin des frames, après que toutes les tâches avec délais durs programmées dans le frame soient accomplies Ceci retarde l'exécution des tâches apériodiques en faveur des tâches périodiques Cependant, généralement, il n'y a pas d’avantage à accomplir une tâche temps réel dure tôt, et puisqu'une tâche apériodique est réactive à un événement particulier, le plus tôt cette tâche fini, meilleur est la réponse du système

Par conséquent, réduire le temps de réponse du système pour les tâches apériodiques est typiquement un but inhérent à l’ordonnancement temps réel 18

<!-- Slide number: 19 --> # Exemple :


 Trep moyen = 4.5

 Trep moyen = 2.5 19

<!-- Slide number: 20 --> # Planification des tâches apériodiques : Slack Stealing Les tâches périodiques sont ordonnancées dans les frames qui complètent avant leurs délais ; il peut y avoir du temps perdu (slack time) dans le frame après la fin d’exécution des tâches périodiques

Puisqu’on connait à l’avance le temps d'exécution des tâches périodiques, on peut déplacer ce temps perdu au début du frame, exécutant les tâches périodiques juste à temps pour satisfaire leurs délais

Exécution des tâches apériodiques pendant le temps perdu, avant les tâches périodiques: Le noyau cyclique garde le temps perdu de chaque frame pour l’exécution des tâches apériodiques, les préempte pour lancer les tâches périodiques lorsque le temps perdu est fini Tant qu’il reste du temps perdu, dans le frame, le noyau cyclique revoie la file des tâches apériodiques après la fin de chaque slice (unité)

Ceci permet de réduire le temps de réponse des tâches apériodiques, mais nécessite des timers très précis. 20

<!-- Slide number: 21 --> # Ordonnancement des tâches sporadiques Que faire si on veut prendre en considérations les tâches sporadiques ? Les tâches sporadiques ont des délais durs, le temps d’arrivée et le temps d’exécution ne sont pas connus à l’avance: Par conséquent, l’ordonnancement par horloge ne peut pas garantir a priori que les tâches sporadiques s’accomplissent dans les délais Cependant, le planificateur peut déterminer si une tâche sporadique est planifiable quand elle arrive Réalise un « test d’acceptation » pour vérifier si la nouvelle tâche sporadique peut être planifiée avec toutes les tâches dans le système S'il y a suffisant de temps perdu dans les frames avant le délai de la nouvelle tâche, cette dernière est acceptée, sinon rejetée Si plusieurs tâches sporadique arrivent en même temps, elles doivent être mises dans une file d’attente dans l’ordre EDF pour le test d’acceptation 21

<!-- Slide number: 22 --> # Considérations pratiques Prise en compte des dépassements : Les tâches sont planifiées selon leur temps d’exécution maximum, mais des échecs pourraient causer des dépassements Un système robuste tiendra compte de cela par Soit arrêter la tâche qui dépasse et générer une tâche de récupération Ou bien préempte la tâche et la planifie comme étant une tâche apériodique. Ceci dépend de l’utilité des résultats en retard, les dépendances entre les tâches, etc...

Des processeurs multiples Peut être réalisé, mais la génération de la table de planification off-line est plus complexe 22

<!-- Slide number: 23 --> # Avantages de l’ordonnancement par horloge Simplicité de la conception Il est possible de considérer des dépendances complexes, des délais de communication, des conflits sur les ressources lors de la construction de l’ordonnancement statique, tout en garantissant l’absence de blocage et les délais imprédictibles L’ordonnancement entier est retenu dans une table statique Des modes de fonctionnement différents peuvent être représentés par différentes tables Il n’y a pas besoin de contrôle de concurrence ou de synchronisation

Lorsque la charge de travail est la plupart du temps périodique et l’ordonnancement est cyclique, les contraintes de temps peuvent être vérifiées à chaque limite de frame

Le choix de la taille du frame peut minimiser les dépassements dus aux changements de contexte et les dépassements de communications

L’ ordonnancement réalisé est relativement facile à valider, tester et certifier 23

<!-- Slide number: 24 --> # Inconvénients de l’ordonnancement par horloge Non flexible Toute modification du matériel cause la re-génération de la table Convient aux systèmes qui sont rarement modifiés une fois construits

Autres inconvénients : Le temps d’arrivée de toutes les tâches doit être fixé Toutes les combinaisons possibles des tâches périodiques qui s’exécutent en même temps doivent être connus à l’avance, ainsi l’ordonnancement combiné peut être pré-calculé

Le traitement des tâches apériodiques est très primitif 24