1-rate monotonic

L’ordonnancement temps réel RM : rate monotonic:

L’ordonnancement temps réel RM : rate monotonic Réaliser par : Chinig abdessamad Echaoui abdellatif Encadré par: M.gourchane

plan:

plan Introduction a l’ordonnancement Notion de tâche Ordonnanceur : structure, fonctions Algorithmes classiques L’algorithme Rate Monotonic

Slide 3:

L'ordonnancement à taux monotone est un algorithme d' ordonnancement temps réel en ligne à priorité constante. Il attribue la priorité la plus forte à la tâche qui possède la plus petite période. RMS est optimal dans le cadre d'un système de tâches périodiques, synchrones, indépendantes et à échéance sur requête avec un ordonnanceur préemptif . De ce fait, il n'est généralement utilisé que pour ordonnancer des tâches vérifiant ces propriétés Introduction à l’ordonnancement

Slide 4:

Cet algorithme a été proposé la première fois dans un papier publié par Liu et Layland . Outre l'algorithme à taux monotone, ce papier décrit une modélisation des tâches basée sur un triplet ( C i , D i , T i ), ainsi qu'une méthode de calcul des pires temps de réponses pour des systèmes de tâches à échéance inférieure ou égale à la période. Ce papier est actuellement considéré comme étant une base de l'ordonnancement temps-réel.

Notion de tâche :

Notion de tâche Processeur = unique ressource partageable dans un système temps réel ⇒exécutif temps réel. Tâche : suite d’instructions + données + contexte d’exécution (état). Famille de tâches : Tâches indépendantes: partagent seulement l’unité centrale. Tâches dépendantes: partagent autres ressources et sont liées par des contraintes de précédence. Tâches répétitives : activations successives (tâches périodiques ou sporadiques) ⇒tâches critiques. Tâches non répétitives/apériodiques : une seule activation ⇒ tâches non critiques. tâches à contraintes strictes: Date de fin d'exécution au plus tard "dure " respect obligatoire. Tâches à contraintes relatives : Date de fin d'exécution au plus tard "molle" respect souhaitable

Slide 6:

Modèle de tâche Périodique strict Ti(r 0 , C, R, P) 0<= C <= R <= P Ti( t,C (t),R(t)) R=P, à échéance sur requête

Notion de tâche :

Notion de tâche Si est la date d'arrivée du premier travail de la tâche Ti, ce qui ne signifie pas que celui-ci s'exécutera à cette date. Pi est la période: la durée qui sépare deux arrivées successives de travaux. Le deuxième travail d'une tâche Ti ne pourra donc pas s'exécuter avant l'instant Si + Pi. Ri est l'échéance de la tâche Ti, qui dénote la limite supérieure de temps entre l'arrivée d'un travail et la fin de son exécution. Ci est le temps d'exécution.

Slide 8:

Modèle de tâche Apériodique strict Tap (r, C, R) Tap ( t,C (t),R(t))

Ordonnanceur : structure, fonctions (1):

Ordonnanceur : structure, fonctions (1) Trois traitements successifs : 1) Calcul d’informations d’ordonnancement : En ligne ou hors ligne. Calendrier : activation cyclique. Période : Rate Monotonic (RM). Echéance : Deadline Monotonic (DM), Earliest Deadline First (EDF). Laxité : Least Laxity First (LLF).

Ordonnanceur : structure, fonctions (2):

Ordonnanceur : structure, fonctions (2) (2) Gestion de la/les files d’attente : Une file par priorité/importance/classe d’applications. Application d’une politique (FIFO, Round-Robin). Exemple : POSIX 1003.1b, Chorus, Solaris, etc. (3) Phase d’élection : Election de la tâche en tête de file. HPF : plus haute priorité d’abord. EDF : plus courte échéance d’abord. LLF : plus petite laxité d’abord.

Slide 11:

Il existe plusieurs expressions qualifiant un système constitué de n tâches, on parle de systèmes: à échéance contrainte : signifie que l'échéance de toute tâche du système ne peut pas être supérieure à la période de celle-ci. à échéance sur requête : signifie que l'échéance de toute tâche du système coïncide avec la période de celle-ci (Di = Pi Vi E [1, n], chaque travail d'une tâche doit se terminer avant l'arrivée du travail suivant de cette même tâche. C'est donc un cas particulier de système à échéance contrainte. à échéance arbitraire : aucune contrainte n'est imposée entre l'échéance et la période. à départ simultané : l'instant d'arrivée du premier travail de chaque tâche coïncide avec les autres, on peut donc poser Si = 0 Vi E [1, n] .

Algorithmes classiques:

Algorithmes classiques Algorithme à priorités fixes : Rate Monotonic (RM,RMS, RMA). 2. Algorithme à priorités dynamiques : Earliest Deadline First (EDF).

L’algorithme Rate Monotonic :

L’algorithme Rate Monotonic • Caractéristiques : Priorités fixes ⇒analyse hors ligne ⇒applications statiques. Tâches périodiques uniquement. Pour cet exposé, pour RM, nous nous limitons à des tâches de type "Liu et Layland ". Complexité faible et mise en oeuvre facile dans un système d’exploitation. Algorithme optimal dans la classe des algorithmes à priorité fixe. • Fonctionnement : 1. Phase de calcul : priorité = inverse de la périodicité. 2. Phase d’élection : élection de la plus forte priorité.

Slide 15:

Evaluation de l’ ordonnançiabilité : 1. Période d’étude = [0, PPCM(Pi)]. Solution exacte. 2. Taux d’utilisation (cas préemptif) :

Slide 16:

Condition suffisante mais non nécessaire : solution pessimiste donc. . Temps de réponse ⇒délai entre l’activation d’une tâche et sa terminaison. Solution parfois exacte (selon les modèles de tâches).

Slide 17:

Calcul du temps de réponse : Hypothèses : cas préemptif. Principe : pour une tâche i, on cherche à évaluer, au pire cas, son temps d’exécution son temps d’attente lorsque des tâches plus prioritaires s’exécutent. Où encore :

Slide 18:

Où hp (i) est l’ensemble des tâches de plus forte priorité que i ; ⌈x⌉ est l’entier directement plus grand que x.

L’algorithme Rate Monotonic (5):

L’algorithme Rate Monotonic (5) Technique de calcul : on évalue de façon itérative ω i n par: On démarre avec : ω i 0 = C i Conditions d’arrêt : Echec si ω i n > P i Réussite si ω i n +1 = ω i n

L’algorithme Rate Monotonic (6):

L’algorithme Rate Monotonic (6) Exemple : P1=7 ; C1=3; P2=12 ; C2=2 ; P3=20 ; C3=5

L’algorithme Rate Monotonic (7):

L’algorithme Rate Monotonic (7) Comment faire cohabiter des tâches apériodiques dans un système ordonnancé avec Rate Monotonic : Les tâches apériodiques ne sont pas urgentes ⇒ priorités plus faible que les tâches périodiques. 2. Les tâches apériodiques sont urgentes ⇒utilisation de serveur de tâches apériodiques. un serveur est une tâche périodique créée spécialement pour veiller à l’ordonnancement des tâches apériodiques.

L’algorithme Rate Monotonic (8):

L’algorithme Rate Monotonic (8) Serveur de tâches apériodiques : tâche périodique dédiée à l’exécution des tâches apériodiques.

L’algorithme Rate Monotonic (9):

L’algorithme Rate Monotonic (9) Serveur par scrutation : exécution des tâches apériodiques arrivées avant le début de l’activation du serveur ; ne consomme pas de temps processeur si pas de tâche apériodique. Temps de scrutation considéré négligeable. Simple mais ressource gaspillée. Autres serveurs : serveur sporadique, différé, ...

Slide 24:

Merci pour votre attention