Podcast
Questions and Answers
Qu'est-ce que représente $D_i$ dans le modèle de tâche séquentielle ?
Qu'est-ce que représente $D_i$ dans le modèle de tâche séquentielle ?
- Le temps d'exécution maximum d'une tâche
- L'échéance relative de la tâche (correct)
- La période de la tâche
- L'offset de première activation de la tâche
Quel est le paramètre qui définit le temps maximum d'exécution requis pour chaque job d'une tâche $ au_i$?
Quel est le paramètre qui définit le temps maximum d'exécution requis pour chaque job d'une tâche $ au_i$?
- O_i
- T_i
- C_i (correct)
- G_i
Que signifie $T_i$ dans le contexte d'une tâche périodique ?
Que signifie $T_i$ dans le contexte d'une tâche périodique ?
- Le coût de la tâche
- La durée totale d'exécution
- La période d'activation entre deux tâches successives (correct)
- L'instant de première activation
Quel élément est décrit par le paramètre $O_i$ ?
Quel élément est décrit par le paramètre $O_i$ ?
Comment est défini un jeu de tâches composé de $n$ tâches ?
Comment est défini un jeu de tâches composé de $n$ tâches ?
Quel est la valeur de L4 selon les calculs présentés?
Quel est la valeur de L4 selon les calculs présentés?
Quel est le résultat de RBF (τ, 12) dans les étapes décrites?
Quel est le résultat de RBF (τ, 12) dans les étapes décrites?
Dans le jeu de tâches périodiques, quelle tâche a la plus grande durée de calcul?
Dans le jeu de tâches périodiques, quelle tâche a la plus grande durée de calcul?
Quel est le temps d'arrivée de la tâche τ2?
Quel est le temps d'arrivée de la tâche τ2?
Quelle est la durée de calcul de τ1?
Quelle est la durée de calcul de τ1?
Quel est le dernier temps de deadline pour τ3?
Quel est le dernier temps de deadline pour τ3?
Quelle est la formule utilisée pour RBF dans les calculs?
Quelle est la formule utilisée pour RBF dans les calculs?
Combien de tâches sont incluses dans le jeu de tâches périodiques?
Combien de tâches sont incluses dans le jeu de tâches périodiques?
Quel est l'intervalle de temps pour T2?
Quel est l'intervalle de temps pour T2?
Quel est le poids associé à RBF pour L2?
Quel est le poids associé à RBF pour L2?
Quel est l'objectif principal d'Audsley dans ses travaux sur l'ordonnancement ?
Quel est l'objectif principal d'Audsley dans ses travaux sur l'ordonnancement ?
À quel domaine d'application l'approche de Deadline-Monotonic se rapporte-t-elle principalement ?
À quel domaine d'application l'approche de Deadline-Monotonic se rapporte-t-elle principalement ?
Qui sont les auteurs du rapport technique sur l'ordonnancement optimal ?
Qui sont les auteurs du rapport technique sur l'ordonnancement optimal ?
Quel type de tâches est étudié par Baruah, Rosier, et Howell dans leur article de 1990 ?
Quel type de tâches est étudié par Baruah, Rosier, et Howell dans leur article de 1990 ?
Quel est le principal objectif de la fonction Request Bound Function (RBF) dans un intervalle d'étude préemptif ?
Quel est le principal objectif de la fonction Request Bound Function (RBF) dans un intervalle d'étude préemptif ?
Quel article présente l'analyse monométrique de taux ?
Quel article présente l'analyse monométrique de taux ?
Quelle condition doit être vérifiée pour que Lk+1 soit égal à Lk dans le calcul des intervalles d'étude ?
Quelle condition doit être vérifiée pour que Lk+1 soit égal à Lk dans le calcul des intervalles d'étude ?
Quelle est la principale contribution de la recherche de Fisher et al. ?
Quelle est la principale contribution de la recherche de Fisher et al. ?
Dans l'intervalle d'étude, que représente la variable L ?
Dans l'intervalle d'étude, que représente la variable L ?
Quel aspect est abordé dans les travaux d'Audsley et ses collaborateurs en 1993 ?
Quel aspect est abordé dans les travaux d'Audsley et ses collaborateurs en 1993 ?
Quel type de tâche est considéré dans l'exemple donné pour l'intervalle d'étude III ?
Quel type de tâche est considéré dans l'exemple donné pour l'intervalle d'étude III ?
Quel est le sujet principal de la conférences organisée par l'IEEE en 1991 ?
Quel est le sujet principal de la conférences organisée par l'IEEE en 1991 ?
Quelle opération résume le calcul de L0 dans le contexte des intervalles d'étude ?
Quelle opération résume le calcul de L0 dans le contexte des intervalles d'étude ?
Comment est défini le temps d'occupation d'une tâche dans le cadre de la fonction RBF?
Comment est défini le temps d'occupation d'une tâche dans le cadre de la fonction RBF?
Quel est le rôle de l'intervalle d'étude dans la gestion des tâches ?
Quel est le rôle de l'intervalle d'étude dans la gestion des tâches ?
Quelle méthode est utilisée pour la réduction de l'intervalle dans l'exemple fourni dans l'intervalle d'étude ?
Quelle méthode est utilisée pour la réduction de l'intervalle dans l'exemple fourni dans l'intervalle d'étude ?
Qu'est-ce que la laxité d'un job dans le contexte d'ordonnancement dynamique ?
Qu'est-ce que la laxité d'un job dans le contexte d'ordonnancement dynamique ?
Quel algorithme est associé à la stratégie de priorité dynamique au niveau des jobs ?
Quel algorithme est associé à la stratégie de priorité dynamique au niveau des jobs ?
Quelle condition doit être remplie pour qu'un algorithme d'ordonnancement soit considéré comme optimal ?
Quelle condition doit être remplie pour qu'un algorithme d'ordonnancement soit considéré comme optimal ?
Quel est le principal avantage de la priorité dynamique par rapport aux techniques d'ordonnancement statiques ?
Quel est le principal avantage de la priorité dynamique par rapport aux techniques d'ordonnancement statiques ?
Quelle est la formule utilisée pour calculer la laxité d'un job Jik ?
Quelle est la formule utilisée pour calculer la laxité d'un job Jik ?
Dans un système d'ordonnancement, que signifie le terme 'priorité' ?
Dans un système d'ordonnancement, que signifie le terme 'priorité' ?
Quelle assertion concernant la priorité dynamique est correcte ?
Quelle assertion concernant la priorité dynamique est correcte ?
Qu'est-ce que le terme 'deadline' signifie dans le contexte d'ordonnancement ?
Qu'est-ce que le terme 'deadline' signifie dans le contexte d'ordonnancement ?
Quelle équation représente la limite lorsque $n$ tend vers l'infini dans le contexte des tests d'ordonnançabilité ?
Quelle équation représente la limite lorsque $n$ tend vers l'infini dans le contexte des tests d'ordonnançabilité ?
Dans le cadre de FTP préemptif, quel test est utilisé pour les C-Deadlines ?
Dans le cadre de FTP préemptif, quel test est utilisé pour les C-Deadlines ?
Quel est le critère de l'NS-Test pour EDF avec I-Deadline ?
Quel est le critère de l'NS-Test pour EDF avec I-Deadline ?
Quel est le but de la fonction Demand Bound Function (DBF) dans les tests d'ordonnançabilité ?
Quel est le but de la fonction Demand Bound Function (DBF) dans les tests d'ordonnançabilité ?
Pour l'algorithme EDF avec une C-Deadline, quel test doit être appliqué ?
Pour l'algorithme EDF avec une C-Deadline, quel test doit être appliqué ?
Qu'est-ce que la charge ($Load(τ)$) dans le contexte d'ordonnancement ?
Qu'est-ce que la charge ($Load(τ)$) dans le contexte d'ordonnancement ?
Dans un système préemptif avec des I-Deadlines, quelle relation doit respecter l'utilisation totale des tâches ?
Dans un système préemptif avec des I-Deadlines, quelle relation doit respecter l'utilisation totale des tâches ?
Quel est le rôle du WCRT dans le contexte des systèmes d'ordonnancement ?
Quel est le rôle du WCRT dans le contexte des systèmes d'ordonnancement ?
Quel est le but du calcul de L dans l'intervalle [Dmin ; P] ?
Quel est le but du calcul de L dans l'intervalle [Dmin ; P] ?
Pour une tâche $ au_i$ donnée, quel critère de validation doit être analysé avec le WCRT ?
Pour une tâche $ au_i$ donnée, quel critère de validation doit être analysé avec le WCRT ?
Quel test d'ordonnançabilité est associé à l'algorithme EDF avec un A-Deadline ?
Quel test d'ordonnançabilité est associé à l'algorithme EDF avec un A-Deadline ?
Quelle condition doit être respectée pour le S-Test – Densité dans un système EDF ?
Quelle condition doit être respectée pour le S-Test – Densité dans un système EDF ?
Quel est l'effet d'un $RTF$ (Response Time Factor) élevé sur l'ordonnancement ?
Quel est l'effet d'un $RTF$ (Response Time Factor) élevé sur l'ordonnancement ?
Quel composant est essentiel pour la définition de la période dans les algorithmes d'ordonnancement ?
Quel composant est essentiel pour la définition de la période dans les algorithmes d'ordonnancement ?
Flashcards
WCET (Worst Case Execution Time)
WCET (Worst Case Execution Time)
Le temps maximum d'exécution requis pour chaque instance de la tâche. Il représente la durée maximale que la tâche peut prendre pour s'exécuter.
Premier instant d'arrivée (Oi)
Premier instant d'arrivée (Oi)
Le moment de la première activation d'une tâche depuis le démarrage du système.
Période ou inter-arrivée (Ti)
Période ou inter-arrivée (Ti)
La période (pour les tâches périodiques) ou l'inter-arrivée minimale (pour les tâches sporadiques) entre deux activations consécutives d'une tâche.
Deadline relative (Di)
Deadline relative (Di)
Signup and view all the flashcards
Jeu de tâches (τ)
Jeu de tâches (τ)
Signup and view all the flashcards
Priorité dynamique au niveau des jobs
Priorité dynamique au niveau des jobs
Signup and view all the flashcards
LLF (Least Laxity First)
LLF (Least Laxity First)
Signup and view all the flashcards
Laxité d'un job
Laxité d'un job
Signup and view all the flashcards
DJP (Dynamic Job Priority)
DJP (Dynamic Job Priority)
Signup and view all the flashcards
Optimalité d'un algorithme
Optimalité d'un algorithme
Signup and view all the flashcards
Intervalle d'étude
Intervalle d'étude
Signup and view all the flashcards
Ordonnancement préemptif
Ordonnancement préemptif
Signup and view all the flashcards
Ordonnancement sporadique
Ordonnancement sporadique
Signup and view all the flashcards
Fonction à Temps d’exécution Bornée (RBF)
Fonction à Temps d’exécution Bornée (RBF)
Signup and view all the flashcards
Scénario synchrone
Scénario synchrone
Signup and view all the flashcards
Ordonnançabilité
Ordonnançabilité
Signup and view all the flashcards
Intervalle d'étude préemptif
Intervalle d'étude préemptif
Signup and view all the flashcards
Intervalle d'étude sporadique
Intervalle d'étude sporadique
Signup and view all the flashcards
Tâche périodique
Tâche périodique
Signup and view all the flashcards
Jeu de tâches périodique
Jeu de tâches périodique
Signup and view all the flashcards
Délai (D)
Délai (D)
Signup and view all the flashcards
Période (T)
Période (T)
Signup and view all the flashcards
Temps d'exécution (C)
Temps d'exécution (C)
Signup and view all the flashcards
Décalage temporel (O)
Décalage temporel (O)
Signup and view all the flashcards
Ordonnancement
Ordonnancement
Signup and view all the flashcards
Ordonnancement à priorité fixe
Ordonnancement à priorité fixe
Signup and view all the flashcards
Fonctionnement des algorithmes d'ordonnancement à priorité fixe
Fonctionnement des algorithmes d'ordonnancement à priorité fixe
Signup and view all the flashcards
Contribution d'Audsley à l'ordonnancement à priorité fixe
Contribution d'Audsley à l'ordonnancement à priorité fixe
Signup and view all the flashcards
Approche du Délai-Monotone
Approche du Délai-Monotone
Signup and view all the flashcards
Analyse du Taux Monotone
Analyse du Taux Monotone
Signup and view all the flashcards
Importance de l'ordonnancement à priorité fixe
Importance de l'ordonnancement à priorité fixe
Signup and view all the flashcards
Perspectives pour l'ordonnancement à priorité fixe
Perspectives pour l'ordonnancement à priorité fixe
Signup and view all the flashcards
S-Test
S-Test
Signup and view all the flashcards
Utilisation du processeur (U)
Utilisation du processeur (U)
Signup and view all the flashcards
S-Test - Borne hyperbolique
S-Test - Borne hyperbolique
Signup and view all the flashcards
NS-Test
NS-Test
Signup and view all the flashcards
WCRT (Worst-Case Response Time)
WCRT (Worst-Case Response Time)
Signup and view all the flashcards
Fonction RBF (Release Bound Function)
Fonction RBF (Release Bound Function)
Signup and view all the flashcards
NS-Test - Utilisation
NS-Test - Utilisation
Signup and view all the flashcards
Densité du processeur (Lambda)
Densité du processeur (Lambda)
Signup and view all the flashcards
S-Test - Densité
S-Test - Densité
Signup and view all the flashcards
Fonction DBF (Demand Bound Function)
Fonction DBF (Demand Bound Function)
Signup and view all the flashcards
Load(τ)
Load(τ)
Signup and view all the flashcards
NS-Test - DBF amélioré
NS-Test - DBF amélioré
Signup and view all the flashcards
Ensemble S
Ensemble S
Signup and view all the flashcards
PPCM (Plus Petit Commun Multiple)
PPCM (Plus Petit Commun Multiple)
Signup and view all the flashcards
Study Notes
Présentation générale
- Le document porte sur l'ordonnancement temps réel et le dimensionnement pire cas.
- L'auteur est Pierre Courbin, un ingénieur d'ESIea.
- Le document est basé sur des cours de M. Laurent George.
Contexte
- Les domaines d'application incluent l'automobile, l'avionique, les réseaux de capteurs, la défense militaire, les villes intelligentes, les télécommunications et les multimédia.
- Le concept central de temps réel (TR) est détaillé.
Contenu
- Le document est structuré en plusieurs sections principales, comprenant les concepts de temps réel, les algorithmes d'ordonnancement, les conditions d'ordonnançabilité, les conclusions et les perspectives, ainsi que les références et un index des acronymes.
- Un sous-titre "Introduction" détaille le sujet du cours : l'ordonnancement de tâches séquentielles dans un système temps réel (TR) incluant des tâches préemptives ou non préemptives sur une plate-forme mono-processeur.
Faire la vaisselle/Voter
- Le document fournit des exemples concrets, comme les tâches répétées "faire la vaisselle" et "voter" pour illustrer les concepts d'ordonnancement TR durs ou souples.
- Chaque exemple indique les deadlines, les temps d'exécution et d'autres paramètres à considérer lors de la simulation des scénarios.
- Les concepts de I-Deadline (temps souple) et C-Deadline (temps dur) sont identifiés dans les exemples.
Ordonnanceur
- Un ordonnanceur est un algorithme qui décide de l’instance de tâche à exécuter à chaque instant.
- L'algorithme assigne des priorités aux tâches et sélectionne l'instance de tâche avec la priorité la plus haute.
- Les exemples d'ordonnanceurs mentionnés sont EDF et DM.
Autre analogie
- L'ordonnancement temps réel est comparé à une politique gouvernementale qui doit gérer les demandes des citoyens.
Exemple
- Une illustration de jeu de tâches est décrite, comprenant les temps d'arrivée, les temps d'exécution et les deadlines pour chaque tâche.
Principe fondamental
- Le temps réel n'est pas explicitement lié à la rapidité mais à la garantie de respecter les spécifications pendant toute la durée de vie du système de temps réel.
- Pour garantir le déterminisme, il est nécessaire d'exprimer les conditions de faisabilité du système et d'utiliser l'approche pire cas.
Méthode classique de résolution d'un système temps réel
- L'approche pire cas est une méthode courante pour résoudre les problèmes d'ordonnancement TR.
- Elle implique de modéliser les tâches et les contraintes temporelles, et d'identifier la classe de problème d'ordonnancement.
Modèle de tâche séquentielle
- Une tâche génère des travaux (jobs).
- Chaque tâche a une durée d'exécution (Worst Case Execution Time - WCET).
- Il existe des lois d'activation (périodiques et sporadiques) et des contraintes temporelles (deadlines).
Paramètre générique d'un jeu de tâches
- Le jeu de tâches est défini par un ensemble de tâches avec des paramètres comme les temps d'arrivée (Oi), les WCET (Ci), les périodes (Ti) et les deadlines (Di).
Concepts supplémentaires
- Les offsets d’activation des tâches et leur gigue sont importants.
- L’ordonnanceur peut fixer librement ces paramètres dans certains cas.
- Il y a des instants critiques où toutes les tâches sont activées simultanément.
Ordonnanceurs
- Les modèles d'ordonnanceurs incluent les Event-Driven et Time-Driven.
- Les ordonnanceurs non oisifs (Work Conserving) ne laissent aucun travail en attente s’il y a du travail à faire.
Priorité fixe au niveau des tâches
- Chaque tâche reçoit une priorité fixe.
- L'algorithme RM (Rate Monotonic) attribue des priorités en fonction de la période.
- L'algorithme DM (Deadline Monotonic) attribue des priorités en fonction de la période et de la deadline.
- L'algorithme OPA (Optimal Priority Assignment) est décrit.
- Les algorithmes incluent des instructions pour l'attribuation de priorités aux tâches.
Priorité fixe au niveau des jobs
- Les algorithmes FJP (Fixed Job Priority) assignent des priorités uniques à chaque job.
- Les algorithmes EDF (Earliest Deadline First) fixent des priorités sur la base de la deadline absolue la plus proche.
Priorité dynamique au niveau des jobs
- Le DJP (Dynamic Job Priority) dynamise les priorités des jobs à chaque instant.
- Les algorithmes LLF (Least Laxity First) sont décrits.
- La laxité est la marge temporelle restante avant la deadline.
Notion d'optimalité
- Un algorithme optimal trouve toujours une solution valide lorsqu’une solution existe pour un problème donné.
- L'optimalité d'un algorithme est conditionnelle au contexte, incluant le modèle des tâches et le modèle d'ordonnancement.
Optimalité pour ordonnanceurs
- Des tableaux indiquant l'optimalité (ou non) pour divers ordonnanceurs (RM, DM, OPA, Audsley, etc.), et différents types d'échéances (I-deadline, C-deadline, A-deadline), dans différentes configurations (non-concret, asynchrone, offset free, préemptif) sont présentés.
Conditions d'ordonnançabilité
- Les tests d'ordonnançabilité définissent des méthodes pour déterminer si un ensemble de tâches peut être ordonnancé sans manquer ses deadlines.
- Les méthodes incluent des tests nécessaires (N-Tests), suffisants (S-Tests), et nécessaires et suffisants (NS-Tests) pour vérifier l’ordonnançabilité.
Intervalle d'étude
- L’intervalle d’étude (synchrone) est lié au PPCM des périodes des tâches.
Tests d'ordonnançabilité
- Les tests N-test, S-test et NS-test sont expliqués pour déterminer l'ordonnançabilité d'un jeu de tâches.
- L'utilisation du jeu de tâches (U) est un critère important pour ces tests.
- La pire durée de réponse (WCRT) est définie et utilisée pour les tests d'ordonnançabilité.
Ordonnanceurs FJP - EDF
- Les tests nécessaires (N-Test) et suffisants (S-Test) sont définis selon les configurations préemptives ou non préemptives.
- Des conditions spécifiques pour divers ordonnancements sont indiquées dans les exemples.
Conclusions et perspectives
- Le document résume les méthodes pour vérifier l'ordonnancement.
- Il aborde les perspectives pour des systèmes plus complexes et sensibles, incluant la prise en compte des coûts de préemption, le temps réel probabiliste et les systèmes multi-critères.
Références et acronymes
- Une liste de références est fournie.
- Un glossaire d'acronymes complète le document.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Ce quiz explore les concepts d'ordonnancement temps réel et de dimensionnement pire cas, basés sur des cours de M. Laurent George. Les étudiants découvriront les algorithmes d'ordonnancement, les conditions d'ordonnançabilité et l'application dans divers domaines tels que l'automobile et les télécommunications.
