Systèmes temps réel Programmation multitâche

cours_STR_2_efrei_2011_12 [Mode de compatibilité]Systèmes temps réel
Contenu du cours
réel
– Définitions et stratégies d’ordonnancement pour certains modèles de tâches
Contenu du cours
Ordonnancement monoprocesseur
Définitions et stratégies d’ordonnancement pour certains modèles de tâches
Programmation multitâche
Système – Dispose :
– Afin de remplir : • Plusieurs fonctionnalités • Application = une ou plusieurs tâches (une ou plusieurs fonctions)
Programmation multitâche et ordonnancement
• Application = une ou plusieurs tâches (une ou plusieurs fonctions) » Indépendantes ou non » Rythmes d’activation différents ou pas entièrement définis
Besoin de partager les ressources entre différentes tâches afin de profiter du parallélisme
Chacune capable d’assurer une fonction à la fois
Application = une ou plusieurs tâches (une ou plusieurs fonctions)
Programmation multitâche et ordonnancement – EFREI 2011 3
Application = une ou plusieurs tâches (une ou plusieurs fonctions)
Rythmes d’activation différents ou pas entièrement définis
les ressources entre différentes tâches afin de profiter du parallélisme
• Ensemble de tâches (programmes) à exécuter de manière concurrente
– Architecture matérielle • Ensemble limité de ressources de traitements (CPUs)
interconnectées » Architecture mono / multiprocesseur » Architecture répartie ou distribuée
Ensemble limité de ressources de traitements (CPUs)
Architecture mono / multiprocesseur Architecture répartie ou distribuée
Mise en œuvre d’un système – Cela suppose une allocation des tâches
ressources au cours du tempsressources au cours du temps • Faire cette allocation au cours du temps c’est ordonnancer les tâches • Contexte temps réel l’ordonnancement doit satisfaire les
contraintes temporelles de l’ensembles des tâches
– Terminologie • L’ordonnancement est l’organisation de l’exécution des tâches sur
les ressources du système
• La politique d’ordonnancement l’exécution des tâches
Mise en œuvre d’un système allocation des tâches sur les diverses
au cours du tempsau cours du temps Faire cette allocation au cours du temps c’est ordonnancer les tâches
l’ordonnancement doit satisfaire les contraintes temporelles de l’ensembles des tâches
est l’organisation de l’exécution des tâches sur
Séquencement , entrelacement…
Monoprogramming – Un ordinateur :
• 1 processeur, de la mémoire et d’autres ressources• 1 processeur, de la mémoire et d’autres ressources
– Tout faire en une tâche (programmation en boucle) • Programmation cyclique : activation périodique de la tâche
– Avantage : • Simple à mettre en œuvre • Vérification simple (déterministe)
1 processeur, de la mémoire et d’autres ressources1 processeur, de la mémoire et d’autres ressources
(programmation en boucle) Programmation cyclique : activation périodique de la tâche
Vérification simple (déterministe)
Vérification simple (déterministe)
Multiprogramming – Un programme a besoin
• D’un ou plusieurs processeur virtuel (process/thread)• D’un ou plusieurs processeur virtuel (process/thread) • D’une mémoire virtuelle (espace d’adressage) • De ressources virtuelles
• Exemple du processus UNIX » 1 processus = 1 « processeur virtuel
– Faire fonctionner plusieurs programmes en parallèle
– Faire fonctionner plusieurs programmes en parallèle – L’OS est le programme en charge de la multi
programmation • Isolation entre les programmes • Partage des ressources
Un programme a besoin D’un ou plusieurs processeur virtuel (process/thread)D’un ou plusieurs processeur virtuel (process/thread) D’une mémoire virtuelle (espace d’adressage)
Exemple du processus UNIX processeur virtuel »
Faire fonctionner plusieurs programmes en parallèle
Faire fonctionner plusieurs programmes en parallèle est le programme en charge de la multi -
Isolation entre les programmes
Isolation des programmes – Se prémunir d’éventuel programme défaillant– Se prémunir d’éventuel programme défaillant
• Isolation accès mémoire (MMU) • Accès aux ressources sécurisé
» Services système (noyau) » Assure une utilisation correcte des ressources
• Programmation défensive » Vérifications de viol de quotas, hypothèses sur les interruptions…
Isolation des programmes Se prémunir d’éventuel programme défaillantSe prémunir d’éventuel programme défaillant
Isolation accès mémoire (MMU) Accès aux ressources sécurisé
Services système (noyau) Assure une utilisation correcte des ressources
Vérifications de viol de quotas, hypothèses sur les interruptions…
conception similaire Sûreté de fonctionnement ≠ zéro défaut
• Possible si plusieurs ressources » CPUs, Mémoire…
– Allocation « temporelle » • Au cours du temps • Obligatoire si une seule ressource
» D’un CPU, accès du disque, accès du port série…
Ordonnancement CPU(s) : organisation de l’exécution des tâches par le(s) processeur(s) du système
»
Obligatoire si une seule ressource D’un CPU, accès du disque, accès du port série…
Ordonnancement CPU(s) : organisation de l’exécution des tâches par le(s) processeur(s) du système
Besoins primordiaux – La communication entre les tâches
• Transfert de données
• Transfert de données
– La synchronisation entre les tâches • ordonnancement des traitements les uns par rapport aux autres
Propriétés souvent assurées – La cohérence des données – Le déterminisme de l’exécution
La communication entre les tâches
La synchronisation entre les tâches ordonnancement des traitements les uns par rapport aux autres
Propriétés souvent assurées La cohérence des données Le déterminisme de l’exécution
Le déterminisme de l’exécution indépendant du parallélisme
Sources d’incohérences – Ne sont pas dû au parallélisme…
– Ne sont pas dû au parallélisme… – … mais aux interactions entre des programmes
déroulant en parallèle • Mémoire commune • Ressources partagées • Communications (ordres des)…
Ne sont pas dû au parallélisme… … mais aux interactions entre des programmes se
Communications (ordres des)…
Définition : section critique – Portion de code dans laquelle une tâche utilise des
– Portion de code dans laquelle une tâche utilise des ressources qui peuvent être utilisées par d’autres tâches, mais qui ne peuvent pas être utilisées par celles même moment
• Un exemple commun de ressource partagée est un ensemble de blocs mémoire
• Permet de s’assurer qu’une portion de code est exécutée de manière séquentielle
• il faut donc (essayer de) les minimiser
section critique Portion de code dans laquelle une tâche utilise des
Portion de code dans laquelle une tâche utilise des ressources qui peuvent être utilisées par d’autres tâches, mais qui ne peuvent pas être utilisées par celles -ci au
Un exemple commun de ressource partagée est un ensemble de
Permet de s’assurer qu’une portion de code est exécutée de
Attention, les sections critiques diminuent le taux de
il faut donc (essayer de) les minimiser
Pourquoi synchroniser ? (rappel) – Résoudre les problèmes de cohérence mémoire sur la
communication de données (en mémoire partagée)
communication de données (en mémoire partagée) – Spécifier les dépendances entre les traitements
• Contrôler l’ordre d’exécution des tâches » Permet à un thread de contrôler quand un autre s’exécute » Ex : sémaphore privé (ceux qui font P sont différent de ceux qui font V ) producteur / consommateur
• Exécution de section critique » Ex: commandes de périphérique / du matériel
» Ex: commandes de périphérique / du matériel » S’assurer qu’on envoie pas deux commandes disques contraires
– En général : régler les problèmes de concurrence su r l’accès à une ressource partagée
• logicielle ou matérielle
Pourquoi synchroniser ? (rappel) Résoudre les problèmes de cohérence mémoire sur la communication de données (en mémoire partagée)
communication de données (en mémoire partagée) Spécifier les dépendances entre les traitements
Contrôler l’ordre d’exécution des tâches Permet à un thread de contrôler quand un autre s’exécute Ex : sémaphore privé (ceux qui font P sont différent de ceux qui font V )
producteur / consommateur
Exécution de section critique Ex: commandes de périphérique / du matériel
Ex: commandes de périphérique / du matériel S’assurer qu’on envoie pas deux commandes disques contraires
En général : régler les problèmes de concurrence su r l’accès à une ressource partagée
Mécanismes de communication – Mémoire partagée, tubes FIFO, boites aux lettres
– Mémoire partagée, tubes FIFO, boites aux lettres asynchrones, buffer circulaires…
– Toute communication entre deux tâches utilise à un moment de la mémoire partagée
• Éventuellement cachée par le noyau » Mécanisme principal à maîtriser
– Attention aux problèmes «
– Attention aux problèmes « • Une instructions C = plusieurs instructions assembleur !
» Exemple cours n°1: une variable, deux tâches l’une incrémente, l’autre décrémente
Mécanismes de communication Mémoire partagée, tubes FIFO, boites aux lettres
Mémoire partagée, tubes FIFO, boites aux lettres asynchrones, buffer circulaires…
Toute communication entre deux tâches utilise à un moment de la mémoire partagée
Éventuellement cachée par le noyau Mécanisme principal à maîtriser
Attention aux problèmes « cachés »
Attention aux problèmes « cachés » Une instructions C = plusieurs instructions assembleur !
1: une variable, deux tâches l’une incrémente, l’autre décrémente
Définitions – A et B sont deux tâches (traitements)
– Sériabilité • A // B indépendant de l’ordonnancement • A // B = A,B = B,A
– Atomicité • A est atomique par rapport à B si
» A ne peut pas être mis en // avec B » A ne peut pas être préempté au profit de B
» A ne peut pas être préempté au profit de B » B ne peut pas observer d’états intermédiaires dans A pendant l’exécution
de A » A dure un temps nul pour B
A et B sont deux tâches (traitements)
A // B indépendant de l’ordonnancement
A est atomique par rapport à B si A ne peut pas être mis en // avec B A ne peut pas être préempté au profit de B
A ne peut pas être préempté au profit de B B ne peut pas observer d’états intermédiaires dans A pendant l’exécution
A dure un temps nul pour B
Remarques – Les périodes d’atomicité diminuent le taux de
– Les périodes d’atomicité diminuent le taux de parallélisme
• Elles ne doivent pas faire rater les échéances • Elles doivent être brèves en multiprocesseur
– L’atomicité évite certaines interactions • Ne résout pas A,B = B,A • Exemple : Décodage parallèle de code Morse
Les périodes d’atomicité diminuent le taux de
Les périodes d’atomicité diminuent le taux de
Elles ne doivent pas faire rater les échéances Elles doivent être brèves en multiprocesseur
L’atomicité évite certaines interactions
Exemple : Décodage parallèle de code Morse
Exemple : Décodage parallèle de code Morse
Remarques – Exemple : codage parallèle de code Morse
• Sans précautions : « ….- • Respect de l’atomicité : «
…---
• Respect de l’ordre: « …---
Section critique (mutex) résout l’atomicité mais pas les problèmes d’ordre
Exemple : codage parallèle de code Morse
-.--. »
……--- »
---…
---… »
Section critique (mutex) résout l’atomicité mais pas les
Attitude face aux risques d’incohérence – A et B doivent être atomiques l’un vis
– A et B doivent être atomiques l’un vis • Synchronisation pessimiste : Prévention (section critique)
» Atomicité : on empêche le problème de survenir
• Synchronisation optimiste : Guérison (estampilles) » On détecte le problème (données incohérente
• Dépend de la possibilité (probabilité) d’avoir A et B actifs ensembles ?
» estampilles : peuvent ne pas finir
» estampilles : peuvent ne pas finir
Attitude face aux risques d’incohérence A et B doivent être atomiques l’un vis -à-vis de l’autre
A et B doivent être atomiques l’un vis -à-vis de l’autre Synchronisation pessimiste : Prévention (section critique)
Atomicité : on empêche le problème de survenir
Synchronisation optimiste : Guérison (estampilles) On détecte le problème (données incohérente cohérentes)
Dépend de la possibilité (probabilité) d’avoir A et B actifs
estampilles : peuvent ne pas finir
estampilles : peuvent ne pas finir
Attitude face aux risques d’incohérence – Guérir :
– Guérir : • Copier la date (l’estampille) • Copier les données • Calculer les nouvelles valeurs
** Début atomicité ** • Copier la date actuelle
» Est-ce que quelqu’un a rechangé l’estampille ?
• Si elle est inchangée modifier les données et augmenter la date
** Fin atomicité ** Sinon recommencer
(l’estampille)
modifier les données et augmenter la date
Problème avec les sémaphores – Deux tâches A et B et deux sémaphores S1 et S2
avec M(S1) = M(S2) = 1
avec M(S1) = M(S2) = 1 – La chronologie suivante
• A : P(S1) • B : P(S2) • A : P(S2) /* A est bloquée dans P */ • B : P(S1) /* B est bloquée dans P */
– Remarque • C’est un problème global
• C’est un problème global » A est bloquée et c’est B qui peut faire évoluer la situation » B est bloquée et c’est A qui peut faire évoluer la situation
La situation ne peut plus évoluer
• On peut s’interbloquer avec un seul sémaphore (interrupt handler =>TP)
Problème avec les sémaphores Deux tâches A et B et deux sémaphores S1 et S2
La chronologie suivante
A : P(S2) /* A est bloquée dans P */ B : P(S1) /* B est bloquée dans P */
A est bloquée et c’est B qui peut faire évoluer la situation B est bloquée et c’est A qui peut faire évoluer la situation
La situation ne peut plus évoluer
On peut s’interbloquer avec un seul sémaphore (interrupt
Solutions – Remède
• Annuler l’un des appels à P • Il faut faire remonter la tâche dans son code • Il faut pouvoir restaurer les données de la tâche • Annuler toutes les opérations qu’elle a faite • En pratique : détection, et destruction des tâches concernées • Même problème qu’avec les estampilles…
– Prévention
– Prévention • Problème compliqué mais dans des cas particuliers, il y a des
solutions simples • Annonces des besoins
» La tâche demande en une seule fois toutes les ressources dont elle a besoin
Annuler l’un des appels à P
Annuler l’un des appels à P Il faut faire remonter la tâche dans son code Il faut pouvoir restaurer les données de la tâche Annuler toutes les opérations qu’elle a faite En pratique : détection, et destruction des tâches concernées Même problème qu’avec les estampilles…
Problème compliqué mais dans des cas particuliers, il y a des
La tâche demande en une seule fois toutes les ressources dont elle a
Ressources ordonnées partiellement – La tâche peut faire des demandes successives pourvu
– La tâche peut faire des demandes successives pourvu qu’elles portent sur des ressources comparables
– Qu’elles soient faites en suivant une relation d’or dre
– Démonstration • La tâche qui occupe la ressource de plus grand rang ne peut être
bloquée
» A : P(m1) , P(m2) , P(m3) » B : P(m1) , P(m3) , P(m2)
Ressources ordonnées partiellement La tâche peut faire des demandes successives pourvu
La tâche peut faire des demandes successives pourvu qu’elles portent sur des ressources comparables Qu’elles soient faites en suivant une relation d’or dre
La tâche qui occupe la ressource de plus grand rang ne peut être
La condition n’est pas nécessaire A : P(m1) , P(m2) , P(m3) B : P(m1) , P(m3) , P(m2)
Sémaphore privé – Quand chaque tâche n’est autorisée qu’à faire une s eule
– Quand chaque tâche n’est autorisée qu’à faire une s eule des primitives P ou V
• Le sémaphore est dit privé (emploi particulier)
– Interprétation • Le(s) processus qui fait P attend un signal du(des) processus qui
fait V
– Propriétés • Si le processus récepteur est en avance il est bloqué • Si le signal est émis en avance il est mémorisé
Quand chaque tâche n’est autorisée qu’à faire une s eule
Quand chaque tâche n’est autorisée qu’à faire une s eule
Le sémaphore est dit privé (emploi particulier)
Le(s) processus qui fait P attend un signal du(des) processus qui
Si le processus récepteur est en avance il est bloqué Si le signal est émis en avance il est mémorisé
Les interruptions – Indique à l’OS l’occurrence d’un évènement interne ou
externe, attendu ou non
externe, attendu ou non • Interruption hiérarchisée ( différent niveau de priorité)
– Les instructions machines s’exécutent séquentiellem ent • Saut • Exception (instruction invalide) • Trap (interruption demandée) • Interruption (évènement matériel)
– Les interruptions sont le seul moyen pour le systèm e
– Les interruptions sont le seul moyen pour le systèm e d’exploitation de reprendre la main de manière forc ée sur le processeur
• Implémente la préemption via timer (qu’on utilisera en TP)
Indique à l’OS l’occurrence d’un évènement interne ou
Les instructions machines s’exécutent séquentiellem ent
Exception (instruction invalide) Trap (interruption demandée) Interruption (évènement matériel)
Les interruptions sont le seul moyen pour le systèm e
Les interruptions sont le seul moyen pour le systèm e d’exploitation de reprendre la main de manière forc ée sur
Implémente la préemption via timer (qu’on utilisera en TP)
Atomicité des instructions – Point interruptible
• Le CPU possède un état observable (donc mémorisable) seulement à des instants précis où les valeurs des registres (registre d’état, compteur ordinal…) sont valides (stables)
– Une instruction assembleur s’exécute atomiquement • Une interruption ne peut survenir qu’entre deux instructions
» Attention, l’exécution d’une instruction se fait en plusieurs cycles
» Attention, l’exécution d’une instruction se fait en plusieurs cycles » Atomicité des instructions garantie entre tâches ordonnancés
préemptivement
Le CPU possède un état observable (donc mémorisable) seulement à des instants précis où les valeurs des registres (registre d’état, compteur ordinal…) sont valides (stables)
Une instruction assembleur s’exécute atomiquement Une interruption ne peut survenir qu’entre deux instructions
Attention, l’exécution d’une instruction se fait en plusieurs cycles
Attention, l’exécution d’une instruction se fait en plusieurs cycles Atomicité des instructions garantie entre tâches ordonnancés
Gestion d’interruption – Gestionnaire
– Gestionnaire • Programme appelé par le processeur lorsque l’interruption est
rencontrée • Chargé de gérer les conséquences de l’occurrence de l’interruption • Responsable de sauvegarder le contexte d’exécution avant le
traitement (routine d’interruption) puis de le rétablir » On ne doit pas perturber l’exécution du programme interrompu
– Changement de contexte • Opération provoquée par le système à chaque fois que le
processeur doit être affecté à une tâche autre que celle qu’il exécutait avant ce changement
Programme appelé par le processeur lorsque l’interruption est
Chargé de gérer les conséquences de l’occurrence de l’interruption Responsable de sauvegarder le contexte d’exécution avant le traitement (routine d’interruption) puis de le rétablir
On ne doit pas perturber l’exécution du programme interrompu
Changement de contexte ou commutation de tâche Opération provoquée par le système à chaque fois que le processeur doit être affecté à une tâche autre que celle qu’il exécutait avant ce changement
Etapes de la gestion des interruptions – Arrivé d’une interruption non masquée
– Arrivé d’une interruption non masquée – Sauvegarde du contexte d’exécution de la tâche
courante – Activation du gestionnaire d’interruptions – Traitement de l’interruption
• En fonction de la nature de l’interruption et des priorités entre interruptions
interruptions
– Reprendre la tâche interrompue (ou élire une nouvel le tâche commutation)
Etapes de la gestion des interruptions Arrivé d’une interruption non masquée
Arrivé d’une interruption non masquée Sauvegarde du contexte d’exécution de la tâche
Activation du gestionnaire d’interruptions Traitement de l’interruption
En fonction de la nature de l’interruption et des priorités entre
Reprendre la tâche interrompue (ou élire une nouvel le
Condition de prise en compte
Condition de prise en compte – Une demande d’interruption n’est pas
automatiquement traitée dès qu’elle survient • Interruption incidente n’est pas masquée • CPU est à un point interruptible • Pas de niveau d’interruption plus prioritaire en attente ou en
cours de traitement
Condition de prise en compte Une demande d’interruption n’est pas automatiquement traitée dès qu’elle survient
Interruption incidente n’est pas masquée CPU est à un point interruptible Pas de niveau d’interruption plus prioritaire en attente ou en
Caractéristiques des tâches – Tâche non- préemptible
qui ne peut pas être interrompue
qui ne peut pas être interrompue – Tâche préemptible : tâche en cours d’exécution qui
peut être interrompue (au profit d’une autre tâche)
Contraintes sur certaines ressources de calcul • Ressources multiples ou non
• Ressources réquisitionnables
Caractéristiques des tâches préemptible : tâche en cours d’exécution
qui ne peut pas être interrompue
qui ne peut pas être interrompue : tâche en cours d’exécution qui
peut être interrompue (au profit d’une autre tâche)
Contraintes sur certaines ressources de calcul Ressources multiples ou non
réquisitionnables (CPU)
réquisitionnables (CPU) Signifie que la ressource est préemptible
réquisitionnables (DSP) préemptible, le traitement peut être abandonné
Interruptions sous UNIX – Un « signal » désigne une interruption ou un
– Un « signal » désigne une interruption ou un déroutement
• Soit un évènement externe au process/thread (tâche) » frappe au clavier, signal émis par un autre thread à l’aide de la primitive
Kill, signal d’horloge…
• Soit un évènement interne au process/thread (tâche) » Correspond à une erreur (erreur virgule flottante, protection mémoire…)
– Possible de masquer ces signaux
– Possible de masquer ces signaux – Signal en attente d’être pris en compte
• Bit associé dans le registre des signaux en attente est à 1 Si un autre signal du même type arrive il est perdu ! (voir TP)
Interruptions sous UNIX » désigne une interruption ou un
» désigne une interruption ou un
Soit un évènement externe au process/thread (tâche) frappe au clavier, signal émis par un autre thread à l’aide de la primitive
Soit un évènement interne au process/thread (tâche) Correspond à une erreur (erreur virgule flottante, protection mémoire…)
Possible de masquer ces signaux
Possible de masquer ces signaux Signal en attente d’être pris en compte
Bit associé dans le registre des signaux en attente est à 1 Si un autre signal du même type arrive il est perdu ! (voir TP)
Interruptions sous UNIX – Prise en compte d’un signal = exécution d’une fonct ion
– Prise en compte d’un signal = exécution d’une fonct ion spécifique appelé « handler
• Routine prédéfinie dans le système » Traitement standard ou par défaut
• Routine mise en place par l’utilisateur pour personnaliser le traitement de ce signal
» TP n°2
Interruptions sous UNIX Prise en compte d’un signal = exécution d’une fonct ion
Prise en compte d’un signal = exécution d’une fonct ion handler »
Routine prédéfinie dans le système Traitement standard ou par défaut
Routine mise en place par l’utilisateur pour personnaliser le
Système multitâche – Objectif général (système classique)
• Optimisation de l’emploi des ressources
• Optimisation de l’emploi des ressources
– Objectifs temps réel • Produire des résultats (justes) à des dates données • Gérer des échelles de temps différentes
» Imposée par la cohabitation de périodes différentes
– Rôle de l’OS • Interface avec le matériel
» Partage du CPU, du disque…
Objectif général (système classique) Optimisation de l’emploi des ressources
Optimisation de l’emploi des ressources
Produire des résultats (justes) à des dates données Gérer des échelles de temps différentes
Imposée par la cohabitation de périodes différentes
Interface avec le matériel
Interface avec le matériel Ordonnancement des différentes tâches Communication entre les tâches (au sens large) Cohabitation de tâches devant s’ignorer
Partage du CPU, du disque…
Intérêt d’une conception multitâche – Initialement : optimiser l’utilisation du matériel– Initialement : optimiser l’utilisation du matériel
• Plusieurs fonctionnalités sur un même ordinateur • Paralléliser les I / O avec le CPU
Optimisation des temps d’exécution moyen des diverses tâches à accomplir
– Profiter des multiples ressources de calcul • Architectures multiprocesseur
– Simplifier la conception – Traiter des événements asynchrones
• Interruptions à des instants pas entièrement déterminés Notion d’importance ou d’échéance
Intérêt d’une conception multitâche l’utilisation du matériell’utilisation du matériel
Plusieurs fonctionnalités sur un même ordinateur Paralléliser les I / O avec le CPU
Optimisation des temps d’exécution moyen des diverses
Profiter des multiples ressources de calcul Architectures multiprocesseur
Traiter des événements asynchrones Interruptions à des instants pas entièrement déterminés
Notion d’importance ou d’échéance
Intérêt d’une conception multitâche – Gérer un objectif temps -– Gérer un objectif temps -
• Des échelles de temps différentes » Traitements courts passent avant les longs
• Des degrés de criticité différents » Les traitements critiques passent en premier (si on ne peut pas faire
autrement)
Intérêt d’une conception multitâche -réel global-réel global
Des échelles de temps différentes Traitements courts passent avant les longs
Des degrés de criticité différents Les traitements critiques passent en premier (si on ne peut pas faire
Objectifs souvent contradictoires
Objectifs souvent contradictoires Maximiser le nombre de fonctionnalités correctement acquittées
dimensionnement)
Autres caractéristiques des tâches – Niveau d’urgence
• Exprime l’urgence des données produites par la tâche• Exprime l’urgence des données produites par la tâche • Définie par l’échéance de la tâche
– Niveau d’importance • Permet d’introduire, pour un ensemble de tâches, la capacité de
résister aux fautes temporelles de certaines d’entre elles (défaillance)
• Le système doit pouvoir supprimer l’exécution de certaines tâches
tâches » Continuer à exécuter les tâches primordiales (mode dégradé)
– Permet de distinguer deux tâches de même importance ou de même urgence
Autres caractéristiques des tâches
Exprime l’urgence des données produites par la tâcheExprime l’urgence des données produites par la tâche Définie par l’échéance de la tâche
Permet d’introduire, pour un ensemble de tâches, la capacité de résister aux fautes temporelles de certaines d’entre elles
Le système doit pouvoir supprimer l’exécution de certaines
Continuer à exécuter les tâches primordiales (mode dégradé)
Permet de distinguer deux tâches de même importance ou de même urgence
• Doivent toujours être assurées (garantir des propriétés de
– Essentielles– Essentielles • Doivent être assurées autant que possible
» i.e. au moins de temps en temps (garantir des propriétés de
Dans tous les cas, pour un systèmes temps assurer la ponctualité de tous les traitements
– Sûreté
– Sûreté • Montrer qu’une chose ne peut pas se produire
– Vivacité • Montrer qu’une chose se produira au bout d’un certain temps
– Ponctualité • Montrer que les traitements se terminent à temps
être assurées (garantir des propriétés de sûreté)
Doivent être assurées autant que possible i.e. au moins de temps en temps (garantir des propriétés de vivacité)
Dans tous les cas, pour un systèmes temps -réel, il faut de tous les traitements
Montrer qu’une chose ne peut pas se produire
Montrer qu’une chose se produira au bout d’un certain temps
Montrer que les traitements se terminent à temps
T2
Niveau d’urgence
Ordonnancer correctement un système temps réel multitâche – 100% des tâches critiques doivent respecter leurs – 100% des tâches critiques doivent respecter leurs
contraintes (temporelles) • preuve
– Différence entre système temps réel dur et mou
– Différence entre système temps réel dur et mou • Dur : aucune faute temporelle acceptée
» Dégâts catastrophiques
• Mou : une faute temporelle est acceptable » Dégâts dont le coût est estimée tolérable rapportée à sa
probabilité d’occurence
Ordonnancer correctement un système temps réel
100% des tâches critiques doivent respecter leurs 100% des tâches critiques doivent respecter leurs contraintes (temporelles)
Pour les tâches essentielles faire au mieux (best effort)
Différence entre système temps réel dur et mou
Différence entre système temps réel dur et mou Dur : aucune faute temporelle acceptée
Mou : une faute temporelle est acceptable Dégâts dont le coût est estimée tolérable rapportée à sa
Ordonnancement
Introduction – L’application est un ensemble de n tâches qu’on app elle
système de tâchessystème de tâches • Départ simultané (même 1
– Terminologie (rappel) • L’ordonnancement est l’organisation de l’exécution des tâches
sur le(s) CPU(s) du système » Séquencement , entrelacement…
• La politique d’ordonnancement l’exécution des tâches sur les CPU(s) du système
Ordonnancement
L’application est un ensemble de n tâches qu’on app elle
Départ simultané (même 1er date de réveil) ou échelonné
est l’organisation de l’exécution des tâches sur le(s) CPU(s) du système
Séquencement , entrelacement…
Programmation multitâche et ordonnancement – EFREI 2011
politique d’ordonnancement est la règle d’organisation de l’exécution des tâches sur les CPU(s) du système
Ordonnancement
Introduction – Deux travaux à exécuter
• Travail A : Durée = 270 , Échéance = 320• Travail A : Durée = 270 , Échéance = 320 • Travail B : Durée = 15 , Échéance = 21
– Deux ressources différentes • P1 : vitesse = 1 , durée commutation = 1 , priorité = à l’échéance • P2 : vitesse = 10 , durée commutation = 0 , priorité = au premier
TA arrive avant TB à t = 0…
TATBP1
P2
Ordonnancement
Deux travaux à exécuter : Durée = 270 , Échéance = 320: Durée = 270 , Échéance = 320 : Durée = 15 , Échéance = 21
Deux ressources différentes : vitesse = 1 , durée commutation = 1 , priorité = à l’échéance : vitesse = 10 , durée commutation = 0 , priorité = au premier
t320
TA
Ordonnancement
Durée d’exécution ( noté C ) – Temps nécessaire à un processeur pour exécuter le c ode
d’un travail sans interruptiond’un travail sans interruption • La durée d’exécution dépend de la vitesse du processeur • La durée d’exécution est théorique (non constante en pratique)
» Durée maximale d’exécution (worst case execution time ou » Durée minimale d’exécution (best case execution time)
En général, le temps d’exécution d’un travail correspond au WCET
– Mode d’évaluation de la durée d’exécution
– Mode d’évaluation de la durée d’exécution • Mesure en-ligne, analyse hors
– Difficultés • Complexité et multitude des chemins d’exécution • Complexité des processeurs
Ordonnancement
Durée d’exécution ( noté C ) Temps nécessaire à un processeur pour exécuter le c ode d’un travail sans interruptiond’un travail sans interruption
La durée d’exécution dépend de la vitesse du processeur La durée d’exécution est théorique (non constante en pratique)
Durée maximale d’exécution (worst case execution time ou WCET) Durée minimale d’exécution (best case execution time)
En général, le temps d’exécution d’un travail correspond au WCET
Mode d’évaluation de la durée d’exécution
Mode d’évaluation de la durée d’exécution ligne, analyse hors-ligne
Complexité et multitude des chemins d’exécution Complexité des processeurs
Ordonnancement
Attributs temporels d’un travail (job) – Date de début au plus tôt (demande) : Td
• Instant où un travail devient prêt (arrival time ou release time)• Instant où un travail devient prêt (arrival time ou release time) – Date de fin au plus tard ( échéance
• Date avant laquelle l’exécution d’un travail doit être terminé (deadline) – Durée d’exécution d’un travail i (besoin) : Ci
Paramètres dérivés – Délai critique (fenêtre temporelle)
• Délai maximum acceptable pour l’exécution d’une tâche – Date de début au plus tard
– Date de début au plus tard – Durée jusqu’à la date de début au plus tard (laxité ) – Date de fin au plus tôt – Date de début et de fin d’exécution du travail
• Préemptions possibles
Ordonnancement
Attributs temporels d’un travail (job) Date de début au plus tôt (demande) : Td
Instant où un travail devient prêt (arrival time ou release time)Instant où un travail devient prêt (arrival time ou release time) échéance ) : Tf
Date avant laquelle l’exécution d’un travail doit être terminé (deadline) Durée d’exécution d’un travail i (besoin) : Ci
Délai critique (fenêtre temporelle) Délai maximum acceptable pour l’exécution d’une tâche
Durée jusqu’à la date de début au plus tard (laxité )
Date de début et de fin d’exécution du travail
Ordonnancement
Cas non-préemptif – Marge statique : Ms = (Tf – Marge statique : Ms = (Tf
• Ms ≥ 0 • Si Ms = 0, pas de choix
Ci
Ordonnancement
Marge statique : Ms = (Tf - Td) - CiMarge statique : Ms = (Tf - Td) - Ci
Ordonnancement
Cas préemptif – Marge dynamique ou laxité : Md = (Tf – Marge dynamique ou laxité : Md = (Tf
• Tc = instant courant • Ri = durée d’exécution restante du travail i • Md n’évolue pas pour le travail actif • Md évolue dynamiquement pour les travaux non actifs
i
i
Ordonnancement
Marge dynamique ou laxité : Md = (Tf – Tc) – RiMarge dynamique ou laxité : Md = (Tf – Tc) – Ri
Ri = durée d’exécution restante du travail i Md n’évolue pas pour le travail actif Md évolue dynamiquement pour les travaux non actifs
Ordonnancement
Notion de tâche – Une tâche est une entité qui crée des travaux (job
release)release) • La tâche s’active et doit exécuter un travail (job)
– Trois classes majeures • Périodique : Crée un travail toutes les périodes T ( > 0 )
» Échéance implicite : Échéance = période » Échéance contrainte : Échéance
• Sporadiques : créations de travaux séparées par un intervalle de temps minimal (connue)
• Apériodique : Modèle le plus général, les créations de travaux doivent quand même être connues
Ordonnancement
Une tâche est une entité qui crée des travaux (job
a tâche s’active et doit exécuter un travail (job)
: Crée un travail toutes les périodes T ( > 0 ) Échéance implicite : Échéance = période Échéance contrainte : Échéance ≤ période
: créations de travaux séparées par un intervalle de temps minimal (connue)
: Modèle le plus général, les créations de travaux doivent quand même être connues
Ordonnancement
Période d’étude (cas périodique) – L’exécution dure indéfiniment mais le comportement de – L’exécution dure indéfiniment mais le comportement de
la configuration est périodique
– Période d’étude est l’intervalle [ 0 , PPCM ( Pi ) ] • Pi = période de toutes les tâches • Uniquement pour le cas périodique à départ simultané
Ordonnancement
Période d’étude (cas périodique) L’exécution dure indéfiniment mais le comportement de L’exécution dure indéfiniment mais le comportement de la configuration est périodique
est l’intervalle [ 0 , PPCM ( Pi ) ] Pi = période de toutes les tâches Uniquement pour le cas périodique à départ simultané
Ordonnancement
Plan d’ordonnancement – C’est une méthode de prévision– C’est une méthode de prévision
ressources (phase de conception) – Un ordonnancement est dit
contraintes temporelles sont
Ordonnancement
prévision pour l’allocation des prévision pour l’allocation des ressources (phase de conception) Un ordonnancement est dit optimal si toutes les contraintes temporelles sont respectées
Ordonnancement
Plan d’ordonnancement – Il y a surcharge lorsque le volume des tâches à – Il y a surcharge lorsque le volume des tâches à
ordonnancer est tel que tous les ordonnancements conduisent au non respect d’au moins une tâche
• Il n’existe pas d’ordonnancement optimal
– Un algorithme d’ordonnancement est dit pour une classe de problème donnée, il produit des ordonnancements optimaux
Ordonnancement
lorsque le volume des tâches à lorsque le volume des tâches à ordonnancer est tel que tous les ordonnancements
au non respect d’au moins une tâche Il n’existe pas d’ordonnancement optimal
d’ordonnancement est dit optimal , si pour une classe de problème donnée, il produit des ordonnancements optimaux
ordonnancements optimaux
Types d’algorithmes d’ordonnancement – Statique– Statique
• Le plan d’ordonnancement est décidé avant exécution ( » La séquence d’ordonnancement est pré
caractéristiques temporelles des tâches
– Dynamique • Le plan d’ordonnancement varie pendant l’exécution (
» Les décisions d’ordonnancement sont prises au fil de l’exécution de l’application par l’ordonnanceur
• Non préemptifs ou préemptifs • Priorité fixe (statique ou dynamique)
Ordonnancement
Types d’algorithmes d’ordonnancement
Le plan d’ordonnancement est décidé avant exécution (hors-ligne) La séquence d’ordonnancement est pré-calculée sur la base de toutes les caractéristiques temporelles des tâches
Le plan d’ordonnancement varie pendant l’exécution (en-ligne) Les décisions d’ordonnancement sont prises au fil de l’exécution de l’application par l’ordonnanceur
l’application par l’ordonnanceur
Non préemptifs ou préemptifs Priorité fixe (statique ou dynamique)
Ordonnancement Avantages / inconvénients – Hors ligne
• Nécessite la connaissance a priori du système et de ses caractéristiques temporelles (dates de réveil figés)caractéristiques temporelles (dates de réveil figés)
» Manque de flexibilité mais grande prédictibilité (flot d’instruction unique)
• Adapté à un modèle périodique » Calcul de l’ordonnancement sur un cycle (ppcm des périodes des tâches)
ordonnanceur cyclique (programmation en boucle)
• Simplicité de l’ordonnanceur » faibles overheads d’exécution (surcoût d’exécution)
• Efficacité calculatoire non demandée pour le calcul de la séquence
• Efficacité calculatoire non demandée pour le calcul de la séquence d’ordonnancement
» Mise en œuvre d’algorithmes optimaux + des contraintes additionnelles peuvent être prises en compte (précédence entre tâches, synchronisation entre tâches, réveils à des dates arbitraires, etc.)
• Régularité d’exécution » Rigide (ne peut s’adapter à l’environnement)
Ordonnancement Avantages / inconvénients
Nécessite la connaissance a priori du système et de ses caractéristiques temporelles (dates de réveil figés)caractéristiques temporelles (dates de réveil figés)
Manque de flexibilité mais grande prédictibilité (flot d’instruction unique)
Adapté à un modèle périodique Calcul de l’ordonnancement sur un cycle (ppcm des périodes des tâches) ordonnanceur cyclique (programmation en boucle)
Simplicité de l’ordonnanceur faibles overheads d’exécution (surcoût d’exécution)
Efficacité calculatoire non demandée pour le calcul de la séquence
Efficacité calculatoire non demandée pour le calcul de la séquence
Mise en œuvre d’algorithmes optimaux + des contraintes additionnelles peuvent être prises en compte (précédence entre tâches, synchronisation entre tâches, réveils à des dates arbitraires, etc.)
Rigide (ne peut s’adapter à l’environnement)
Ordonnancement Avantages / inconvénients – En ligne
• Flexible » Adapté aux systèmes dynamiques et évolutifs (capable de prendre une
décision à un instant t)
• Efficacité calculatoire requise » Politiques d’ordonnancement simples
• Difficulté à prendre en compte des contraintes variées » Analyse délicate et souvent pessimiste » A priori moins sûr besoin d’une preuve
• Non oisif
• Non oisif » Le processeur est toujours utilisé s’il y a au moins une tâche prête
Ordonnancement Avantages / inconvénients
Adapté aux systèmes dynamiques et évolutifs (capable de prendre une
Efficacité calculatoire requise Politiques d’ordonnancement simples
Difficulté à prendre en compte des contraintes variées Analyse délicate et souvent pessimiste
besoin d’une preuve
Le processeur est toujours utilisé s’il y a au moins une tâche prête
Ordonnancement
• Types : séquentielles, parallèles• Types : séquentielles, parallèles • Relations : mutuellement dépendantes, indépendantes • Valeurs : identiques / différentes, constantes / dépendantes de
l’instant de terminaison • Abandon : si violation de contraintes exigée, autorisée, interdite
– Sur les ressources • Multiplicité : une ou plusieurs (équivalentes ou non) • Mode d’accès : centralisé ou distribué (ressources mémoires)
» Toujours possible (avec ou sans perte) » Possible par moment » Impossible
Ordonnancement
Abandon : si violation de contraintes exigée, autorisée, interdite
Multiplicité : une ou plusieurs (équivalentes ou non) Mode d’accès : centralisé ou distribué (ressources mémoires)
Mode d’accès : centralisé ou distribué (ressources mémoires)
Toujours possible (avec ou sans perte)
Ordonnancement
Modèles – hypothèses – Sur les lois évènementielles– Sur les lois évènementielles
• Connues totalement ou partiellement (non temps • Prédéterminées ou statistiques
– Sur les lois d’activations des tâches • Instants d’activations des tâches • Instants d’accès aux ressources • Instants délimitant les fenêtres de réquisitions possibles /
Ordonnancement
Sur les lois évènementiellesSur les lois évènementielles Connues totalement ou partiellement (non temps-réel) Prédéterminées ou statistiques
Sur les lois d’activations des tâches Instants d’activations des tâches Instants d’accès aux ressources Instants délimitant les fenêtres de réquisitions possibles /
Instants délimitant les fenêtres de réquisitions possibles /
Ordonnancement
Modèles – hypothèses – Un énoncé de problème = un choix parmi toutes ces – Un énoncé de problème = un choix parmi toutes ces
hypothèses • Présentation de diverses classes de problème avec des solutions
connues, souvent optimales (cadre hypothèse / contraintes)
• Dans la suite : » H1 = hypothèses issues de l’énoncé du problème : identifie la classe du
problème
problème » H2 = condition sur les données quantitatives du problème Hypothèses de faisabilité à vérifier
Ordonnancement
Un énoncé de problème = un choix parmi toutes ces Un énoncé de problème = un choix parmi toutes ces
Présentation de diverses classes de problème avec des solutions connues, souvent optimales (cadre hypothèse / contraintes)
H1 = hypothèses issues de l’énoncé du problème : identifie la classe du
H2 = condition sur les données quantitatives du problème Hypothèses de faisabilité à vérifier
Algorithmes d’ordonnancement
Algorithmes connus – Algorithmes de bases– Algorithmes de bases
• Les autres sont pour la plupart une combinaison d’entre eux
– Statiques • FP (priorité fixe) • RMS
– Dynamiques • FCFS (Premier arrivé / premier Servi)
• FCFS (Premier arrivé / premier Servi) • RR (tourniquet) • EDF (priorité à l’échéance la plus proche) • LLF (priorité à la plus petite laxité)
Algorithmes d’ordonnancement
Les autres sont pour la plupart une combinaison d’entre eux
FCFS (Premier arrivé / premier Servi)
FCFS (Premier arrivé / premier Servi)
EDF (priorité à l’échéance la plus proche) LLF (priorité à la plus petite laxité)
Algorithmes d’ordonnancement statique
Ordonnancement préemptif à priorité fixe (FP) – Les tâches ont une priorité fixe – La tâche de plus haute priorité prend la main– La tâche de plus haute priorité prend la main
• Doit être en mesure de s’exécuter • Préemption possible
– Exemple
Ordonnancement préemptif à priorité fixe (FP) Les tâches ont une priorité fixe La tâche de plus haute priorité prend la mainLa tâche de plus haute priorité prend la main
Doit être en mesure de s’exécuter
a : Priorité 1
b : Priorité 2
b : Priorité 2
Ordonnancement préemptif à priorité fixe (FP) – Très proche du HW ( E/S asynchrones )
• Ordonnancement peut être fait au niveau matériel
– Ponctualité pour une tâche • Pour les autres ?
– Peu de sûreté – Peu de vivacité
• Si beaucoup de tâches de haute priorité risque de famine
• Amélioration des défauts » Changement possible des priorités en ligne (Unix / Windows)
– Les analyses restent compliquées pour exercer des contrôles sur les temps de traitements
• => système classique car pas de notion d’urgence
Ordonnancement préemptif à priorité fixe (FP) Très proche du HW ( E/S asynchrones )
Ordonnancement peut être fait au niveau matériel
Ponctualité pour une tâche
Si beaucoup de tâches de haute priorité risque de famine
Changement possible des priorités en ligne (Unix / Windows)
Les analyses restent compliquées pour exercer des contrôles sur les temps de traitements
=> système classique car pas de notion d’urgence
RMS (Rate Monotonic Scheduling) – Inventé par Liu & Layland– Inventé par Liu & Layland – Hypothèse du modèle (H1)
• Algorithme à priorité fixe (constante au cours du temps) • Préemption possible • Chaque tâche est périodique • Pas de dépendances entre les tâches • L’échéance est la période
– Hypothèse de faisabilité (H2) • Existe une condition suffisante (CS)
» Borne théorique correspondant au pire des cas
• Ordonnancement sûr si critère vérifié
RMS (Rate Monotonic Scheduling) Inventé par Liu & LaylandInventé par Liu & Layland Hypothèse du modèle (H1)
Algorithme à priorité fixe (constante au cours du temps)
Chaque tâche est périodique Pas de dépendances entre les tâches
La priorité est l’inverse de la période
Hypothèse de faisabilité (H2) Existe une condition suffisante (CS)
Borne théorique correspondant au pire des cas
Ordonnancement sûr si critère vérifié
RMS (Rate Monotonic Scheduling) – Critère théorique
• n tâches• n tâches • Ci = durée d’exécution • Ti = période = échéance de chaque travail
• Analyse du taux d’occupation du CPU (W) : • Si W ≤ U(n) , RMS est optimal
RMS (Rate Monotonic Scheduling)
Ti = période = échéance de chaque travail
Analyse du taux d’occupation du CPU (W) : U(n) , RMS est optimal
– Pour W entre CS et CN : impossible de savoir s’il y a une solution ou non
• Il faut réaliser un plan d’ordonnancement sur une période d’étude « à la main »
Condition nécessaire : W ≤ 1 (sinon surcharge) Condition suffisante : W ≤ U(n)
Pour W entre CS et CN : impossible de savoir s’il y a
Il faut réaliser un plan d’ordonnancement sur une période
Conclusion RMS – Avantages– Avantages
• Peut être étendu à une tâche apériodique • Peut être étendu à la surcharge
» Les tâches de priorité haute ne sont pas impactées par les tâches de priorité basse
• Simple à implémenter » Très proche de la programmation en boucle
– Inconvénients
– Inconvénients • Hypothèses très simples (rarement rencontrées) • Famine si bug dans une tâche de haute priorité
» Vérifier le temps pris par chaque tâche
Peut être étendu à une tâche apériodique Peut être étendu à la surcharge
Les tâches de priorité haute ne sont pas impactées par les tâches de
Très proche de la programmation en boucle
Hypothèses très simples (rarement rencontrées) Famine si bug dans une tâche de haute priorité
Vérifier le temps pris par chaque tâche
Priorité et synchronisation – Possibilité d’inter -blocage– Possibilité d’inter -blocage
• Si une tâche moins prioritaire prend un mutex et qu’une tâche plus prioritaire le demande ensuite
– Solution : héritage de priorité • Le détenteur du verrou hérite de la priorité du demandeur jusqu’à
ce qu’il libère le verrou • Dans un système important : toutes les tâches finissent souvent
à la même priorité
Priorité et synchronisation blocageblocage
Si une tâche moins prioritaire prend un mutex et qu’une tâche plus prioritaire le demande ensuite
Solution : héritage de priorité Le détenteur du verrou hérite de la priorité du demandeur jusqu’à
Dans un système important : toutes les tâches finissent souvent
Complexifie l’analyse d’ordonnancement
Algorithmes d’ordonnancement dynamique
Premier arrivé / premier Servi (First Come/First Se rved) – Avantages
• Très simple et très rudimentaire• Très simple et très rudimentaire » Non préemptif
• Vivacité (si les tâches se terminent bien sûr…)
– Inconvénients • Ponctualité (=> système classique)
» peut pénaliser les tâches courtes si une tâche longue les précède
• Sécurité
– Utile pour garder un ordre de traitement implicite ( pour les E/S)
• Spooler d’impression
– FCFS est souvent la stratégie « beaucoup de ressources (mémoire, ports TCP/IP…)
Très simple et très rudimentaireTrès simple et très rudimentaire
Vivacité (si les tâches se terminent bien sûr…)
Ponctualité (=> système classique) peut pénaliser les tâches courtes si une tâche longue les précède
Utile pour garder un ordre de traitement implicite ( pour
FCFS est souvent la stratégie « par défaut » pour beaucoup de ressources (mémoire, ports TCP/IP…)
Plus court d’abord – Avantages
• Très simple et très rudimentaire (Non préemptif)• Très simple et très rudimentaire (Non préemptif) • Vivacité (si les tâches se terminent bien sûr…)
– Inconvénients • Ponctualité (=> système classique)
• Sécurité • Impose de connaître la durée des tâches
• Impose de connaître la durée des tâches » Ce qu’on ne connait pas forcément (système classique)
– Temps le plus court d’abord • Version du « plus court d’abord • Préemption lorsqu’une tâche de temps d’exécution inférieur
devient prête
Très simple et très rudimentaire (Non préemptif)Très simple et très rudimentaire (Non préemptif) Vivacité (si les tâches se terminent bien sûr…)
Ponctualité (=> système classique) Les tâches longues sont pénalisées
Impose de connaître la durée des tâches
Impose de connaître la durée des tâches Ce qu’on ne connait pas forcément (système classique)
Temps le plus court d’abord plus court d’abord » avec préemption
Préemption lorsqu’une tâche de temps d’exécution inférieur
Round Robin (tourniquet) – On partage le temps de façon «
les tâches en mesure de s’exécuter – On partage le temps de façon «
les tâches en mesure de s’exécuter • On donne la main à une tâche pour (au plus) «
temps (quantum) • Après consommation de son quantum de temps, la tâche est
placée en fin de la file d’attente des tâches prêtes
– Avantages • Vivacité • Paralléliser les I/O et les traitements
Round Robin (tourniquet) On partage le temps de façon « équitable » entre toutes les tâches en mesure de s’exécuter On partage le temps de façon « équitable » entre toutes les tâches en mesure de s’exécuter
On donne la main à une tâche pour (au plus) « K » unités de
Après consommation de son quantum de temps, la tâche est placée en fin de la file d’attente des tâches prêtes
Paralléliser les I/O et les traitements
Paralléliser les I/O et les traitements
• Ponctualité (=> système classique) • Les performances dépendent de la taille du quantum de temps
» Trop grand une tâche peut attendre longtemps pour avoir le processeur (temps de réponse)
» Trop petit multiplie les commutations de contexte jusqu’à les rendre non négligeables
– En pratique, RR est couplé avec priorité fixe
Ponctualité (=> système classique) Les performances dépendent de la taille du quantum de temps
ne tâche peut attendre longtemps pour avoir le processeur (temps de réponse)
multiplie les commutations de contexte jusqu’à les rendre non négligeables
En pratique, RR est couplé avec priorité fixe
En pratique, RR est couplé avec priorité fixe
EDF (Earliest Deadline First) – Hypothèse de modèle– Hypothèse de modèle
• Dynamique • Tâche apériodique
» Inclus les problèmes périodiques
• Pas de dépendance entre tâche • Échéances connues • Durées inconnues • La priorité est l’inverse de l’échéance relative
• La priorité est l’inverse de l’échéance relative • Préemption
– Hypothèse de faisabilité • Optimal si pas de surcharge ( W
EDF (Earliest Deadline First)
Inclus les problèmes périodiques
La priorité est l’inverse de l’échéance relative
La priorité est l’inverse de l’échéance relative
Hypothèse de faisabilité Optimal si pas de surcharge ( W ≤ 1 )
• Dynamique• Dynamique • Tâche apériodique
» Inclus les problèmes périodiques
• Pas de dépendance entre tâche • Échéances connues • Durées d’exécution connues • La priorité est l’inverse de la laxité
» En ligne, l’ordonnanceur calcule la laxité et exécute celle avec la plus petite
• Préemption
Inclus les problèmes périodiques
Pas de dépendance entre tâche
Durées d’exécution connues La priorité est l’inverse de la laxité
En ligne, l’ordonnanceur calcule la laxité et exécute celle avec la plus petite
Optimal si pas de surcharge ( W ≤ 1 )
Différence entre EDF et LLF – si les valeurs de laxité utilisées sont celles qui sont – si les valeurs de laxité utilisées sont celles qui sont
calculées aux dates de réveil des tâches • Ordonnancement équivalent
– si les valeurs de laxité sont calculées à chaque in stant • LLF entraine beaucoup plus de changement de contexte
» Laxité de la tâche qui s’exécute demeure constante alors que celles des tâches prêtes diminuent
Différence entre EDF et LLF si les valeurs de laxité utilisées sont celles qui sont si les valeurs de laxité utilisées sont celles qui sont calculées aux dates de réveil des tâches
Ordonnancement équivalent
si les valeurs de laxité sont calculées à chaque in stant LLF entraine beaucoup plus de changement de contexte
Laxité de la tâche qui s’exécute demeure constante alors que celles des tâches prêtes diminuent
presque jamais vérifiées • Préemption
» Prends un certain temps
• Intégration de tâches critiques / non critiques » Souvent surcharge
• L’indépendance des traitements » Partage de ressources dont l’utilisation n’est possible qu’en exclusion
» Partage de ressources dont l’utilisation n’est possible qu’en exclusion mutuelle : ressources critiques
» Contraintes de précédence qui expriment les relations de synchronisation et de communication entre les tâches
graphes de dépendances
Intégration de tâches critiques / non critiques
L’indépendance des traitements Partage de ressources dont l’utilisation n’est possible qu’en exclusion
Partage de ressources dont l’utilisation n’est possible qu’en exclusion mutuelle : ressources critiques Contraintes de précédence qui expriment les relations de synchronisation et de communication entre les tâches
raphes de dépendances
Ordonnancement multiprocesseur
Ordonnancement sur multiprocesseur – A tout moment t– A tout moment t
• Un travail est exécuté par au plus un processeur • Un processeur exécute au plus un travail
– Ordonnancement non- accumulatif • Cela complexifie énormément le problème par rapport au
monoprocesseur
Ordonnancement sur multiprocesseur
Un travail est exécuté par au plus un processeur Un processeur exécute au plus un travail
accumulatif Cela complexifie énormément le problème par rapport au
Ordonnancement sur multiprocesseur – Les latences ne sont plus négligeables– Les latences ne sont plus négligeables
• Communication, migrations
– En multiprocesseur • Nécessité de « connaître le futur
• Nécessité de « connaître le futur optimaux… (Global EDF non optimal)
• Différentes stratégies » Partitionnement (migrations interdites) » Algorithmes globaux
Communication, migrations
connaître le futur » pour ordonnancements optimaux… (Global EDF non optimal)
Partitionnement (migrations interdites)
Relations entre les travaux – Travaux peuvent être reliés par un graphe de – Travaux peuvent être reliés par un graphe de
dépendance (ou graphe de précédence) • Exprime précédence et concurrence • Accès concurrents aux ressources, sérialisations
Relations entre les travaux Travaux peuvent être reliés par un graphe de Travaux peuvent être reliés par un

Documents

Systèmes temps réel Programmation multitâche