Embed Size (px)
Citation preview
Des systèmes classiques aux systèmes temps réelsDes systèmes classiques aux systèmes temps réels
Objectif :
Nous revenons sur les principaux mécanismes mis en œuvre dans un système classique. Certains sont utilisés par les systèmes temps réels ; d'autres doivent être abandonnés car ils ne permettent pas la prise en compte de contraintes temporelles.
PlanPlan
Services d'un système élémentaire
Services multitâches
Gestion du processeur
Gestion des interruptions et multitâches
Partage des ressources et exclusion mutuelle
Vue d'un ordinateur classiqueVue d'un ordinateur classique
CPUCPUMémoireprincipale
Mémoireprincipale
StockageSecondaire
StockageSecondaire
PériphériqueE/S
PériphériqueE/S
Bus
Unité de
contrôle
Registres
UnitéArithmétique et Logique
Les services de base qu'un OS offre : Les services de base qu'un OS offre :
Exécution d'un programme dans le processeur
Échange avec l'extérieur
Gestion mémoire
Partage des ressources
Gestion du temps
Nous allons étudier ces services en étudiants leurs limites vis à vis de la prise en compte des contraintes de temps réel.
Dans la suite, nous détaillons uniquement l'exécution du programme dans le processeur en étudiant les limites vis à vis de la prise en compte de contraintes temps réel.
Services d'un système élémentaireServices d'un système élémentaire
Interaction par scrutation cyclique
Interaction par Interruption
Limites des approches précédentes
Nous allons voir l'interaction entre le programme et le monde extérieur. C'est à dire comment le programme réagit à un événement à des instants qu'il ne maîtrise pas.
Les interaction par scrutation cycliqueLes interaction par scrutation cyclique
Le programme va interroger (ou scruter) ses périphériques régulièrement.
fairefaire
vérifier capteurtant que (données non disponibles)lire capteurstraiter les donnéesdémarrer les réactionsfaire
vérifier les actionneurstant que actions effectuées
jusqu'à arrêt du système
Les interactions par interruptionsLes interactions par interruptions
Le programme est averti de la survenue d'un événement. Une interruption interrompt le cours du programme et lui permet de reprendre le programme là où il a été interrompu.
Programme de scrutation : traitement différéfaire
faire vérifier les capteurstant que (état = données disponibles)
lire données mémoriséesremettre à zéro état des capteurs
Jusqu’à arrêt du système
Gestionnaire d'interruption : Prise en compte immédiateInterruption :
lire et mémoriser les donnéespositionner (état capteur = données disponibles)acquitter l’interruption
Les interactionsLes interactions
Avantages :
Simple à programmer s'il y a peu des périphériques
Le temps de réaction d'un système est simple à déterminer. Il s'agit du temps de traitement d'une boucle. On peut s'avoir si le système satisfait les contraintes de temps.
Limitations des approches précédentesLimitations des approches précédentes
Inconvénients :
Va à l'encontre des pratiques du génie logiciel. Le programme mal structuré devient rapidement illisible et impossible à maintenir.
Un nouveau périphérique demande la remise en cause de l'existant.
Une grande partie du temps processeur est consacrée à autre chose qu'à l'application.
Exemple : Exemple :
Soit un programme émettant des caractères sur une liaison série à 9600 bauds via un UART. Il possède 2 séries de registres pour transférer et recevoir des caractères. L'UART cause des interruptions différentes pour l'émission et l'arrivée des caractères.
L'UART émet un caractère tout les millisecondes environ. L'ordinateur ne peut émettre le caractère suivant que quand l'UART est prêt.
Il perd donc beaucoup de temps à tester par scrutation s'il est autorisé à émettre le caractère suivant ou pas.
Exemple suiteExemple suite
Pour émettre un caractère, le programme se bloque en faisant appel à l'opération (Attendre). L'UART répond par une interruption (TxReady) lorsqu'il est prêt. Le gestionnaire d'interruption effectue l'opération (Signaler) et le programme suspendu peut rependre le processeur et réémettre un caractère immédiatement.
Il faut noter que pendant la milli-seconde qui s'est écoulée entre (Attendre) et l'interruption, d'autres programmes pourraient effectuer un travail utile.
C'est pour mieux répondre à ce besoin qu'on a introduit la notion de tâche.
PlanPlan
Services d'un système élémentaire
Services multitâches
Gestion du processeur
Partage des ressources et exclusion mutuelle
Introduction à la notion de tâchesIntroduction à la notion de tâches
Le traitement d'un événement externe est partagé entre un traitement immédiat effectué par le gestionnaire d'interruption et le traitement différé confié à une tâche (c'est à dire un code séquentiel dédié à une tâche).
Plusieurs tâches peuvent s'exécuter concurremment, on peut donc récupérer les temps morts. C'est cette récupération qui fait tout l'intérêt des modèles multitâches.
Système MultitâchesSystème Multitâches
Un programme seul n'occupe pas la capacité totale d'un processeur en particulier lors des E/S.
L'idée : une exécution concurrente pour récupérer les temps morts.
Le système d'exploitation va gérer l'exécution concurrente des programmes.
PlanPlan
Services d'un système élémentaire
Services multitâches
Gestion du processeur
Partage des ressources et exclusion mutuelle
La gestion du processeurLa gestion du processeur
Tâches
Gestion multitâches
Politiques d'ordonnancement classiques
Limites de ces mécanismes pour le temps réel
Les tâches : DéfinitionsLes tâches : Définitions
Un programme est composé d'une suite d'instructions qui agissent sur un ensemble de données : objet statique
Processus : lorsque l'on déclenche l'exécution d'un programme, il devient un objet dynamique géré par l'OS.
Le contexte d'un processus est l'ensemble des informations qui caractérisent son exécution (Registres, son nom, état …)
Un processus est dit lourd lorsque le contexte est volumineux.
Un processus est légers lorsqu'il s'exécutent avec d'autre processus au sein d'un même contexte.
États d'une tâche opérationnelleÉtats d'une tâche opérationnelle
CourantCourant En_attenteEn_attente
PrêtPrêt
Blocage
RéveilPréemption
Allocation
Tâche Active
Etat pour un noyau temps réelEtat pour un noyau temps réel
Prête
Exécutée
Bloquée
Endormie
Créée
Existante
Existante non initialilsée
Suppression
Suppression
Suppression
Suppression
Initialisation
Attente blocante
Préemption
Election
Attente d'une durée
Réveil
Arrivée evt
L'ordonnancementL'ordonnancement
La partie du système qui fait évoluer les états des tâches et qui alloue le processeur aux tâches s'appelle l'ordonnanceur (Scheduler).
L'OS manipule les tâches aux travers de structures de données appelées descripteurs de tâches (task control block).
L'ordonnancementL'ordonnancement
Liste des tâches prêtes
Liste des tâches en attente
Tâche courante
Liste des tâches prêtes
Liste des tâches en attente
Tâche courante
Contexte T1
état = PRET
Contexte T1
état = PRET
Contexte T2
état = PRET
Contexte T2
état = PRET
Contexte T3
état = PRET
Contexte T3
état = PRET
Code T1 Code T2 Code T3
T4
état = Attente
T4
état = Attente
T6état=Courant
T6état=Courant
T5
état= Attente
T5
état= Attente
Les politiques d'ordonnancement classiquesLes politiques d'ordonnancement classiques
Ordonnancement préemptifUn ordonnancement est dit « avec réquisition » ou préemptif si le processus courant peut être désalloué par décision de l'ordonnanceur.
Dans le cas d'un système préemptif, une interruption peut survenir en n'importe quel point du déroulement d'une tâche et provoquer une préemption.
Modèle de tâchesModèle de tâches
ID Depart C D T Etat C_restante P Deadline
T1 2 3 5 5
Période d'activation T Borne sur le temps d'exécution C Arrivée Depart Délai critique relatif à T D
1 2 3 4 5 6 7 8 9 10 11 12nop nop T1 T1 T1 nop nop T1 T1 T1 nop nop T1
T1 T1 T1 T1 T1 T1 T1 T1
Modèle de tâchesModèle de tâches
ID Depart C D T Etat C_restante P Deadline
T1 2 3 4 5
1 2 3 4 5 6 7 8 9 10 11 12nop nop T1 T1 T1 nop nop T1 T1 T1 nop nop T1
T1 T1 T1 T1 T1 T1 T1 T1
2 : T1 est déclenchée pour la :1 fois3 : T1 s'exécute4 : T1 DEADLINE DEPASSEE de15 : T1 Finie son exécution N°27 : T1 est déclenchée pour la :2 fois8 : T1 s'exécute9 : T1 DEADLINE DEPASSEE de110 : T1 Finie son exécution N°312 : T1 est déclenchée pour la :3 fois
Lois d'ordonnancement classiqueLois d'ordonnancement classique
Premier arrivé, premier servi
Le tour de rôle ou tourniquet
L’ordonnancement par priorité
Exemple : FIFOExemple : FIFO
1 2 3 4 5 6 7 8 9 10 11 12 13 14
T1 T1 T1 T1 T1 T1 T2 T2 T2 T3 T3 T3 T3 nop nop
T1 T1 T1 T1 T1 T1 T1
T2 T2 T2 T2
T3 T3 T3 T3 T3
ID Pr C Depart Critère ID croissantT1 2 6 0T2 1 3 0T3 2 4 0
RobinRobin
ID Robin C Depart Critère RR croissantT1 1 6 0T2 1 3 0T3 1 4 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14
T1 T2 T3 T1 T2 T3 T1 T2 T3 T1 T3 T1 T1 nop nop
T1 T1 T1 T1 T1 T1 T1
T2 T2 T2 T2
T3 T3 T3 T3 T3
Robin avec prioritéRobin avec priorité
1 2 3 4 5 6 7 8 9 10 11 12T2 T1 T1 T1 T3 T2 T3 T2 T3 nop nop nop nop
T1 T1 T1 T1T2 T2 T2 T2T3 T3 T3 T3
ID Robin C Depart Critère Robin et 2 critère RRT1 1 3 1T2 2 3 0T3 2 3 0
Robin + incrément de prioritéRobin + incrément de priorité
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29T1 T2 T1 T2 T1 T2 T1 T2 T1 T2 T1 T2 T1 T2 T1 T2 T1 T2 T1 T2 T2 T3 T3 T4 T5 T4 T5 nop nop nop
T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1T2 T2 T2 T2 T2 T2 T2 T2 T2 T2 T2 T2T3 T3 T3T4 T4 T4T5 T5 T5
T1 T2 T1 T2 T1 T2 T1 T2 T1 T2 T1 T2 T3 T1 T2 T3 T1 T2 T1 T2 T1 T2 T4 T5 T2 T4 T5 nop nop nopT1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1T2 T2 T2 T2 T2 T2 T2 T2 T2 T2 T2 T2T3 T3 T3T4 T4 T4T5 T5 T5
ID Depart C Robin
T1 10 1
T2 11 1
T3 2 2
T4 2 3
T5 2 3
Exemple : PrioritéExemple : Priorité
ID Pr C Depart Critère Pr croissantT1 2 6 0T2 1 3 0T3 2 4 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14
T2 T2 T2 T1 T1 T1 T1 T1 T1 T3 T3 T3 T3 nop nop
T1 T1 T1 T1 T1 T1 T1
T2 T2 T2 T2
T3 T3 T3 T3 T3
Ordonnancement avec interactions entre les tâchesOrdonnancement avec interactions entre les tâches
Tâche 1 (prio=2)
T1.1
Attendre1s
T1.2
Signaler (tache2,evt)
T1.3
Tâche 2 (prio=1)
T2.1
Attendre(evt)
T2.2
Tâche1
Tâche2
Tâche de fond*
T1.1 T1.2 T1.3
T2.2T2.1
1s
Attendre evt
* fournit le minimum d'exécution sous forme d'une boucle infinie.
Limitations de ces mécanismes pour le temps réelLimitations de ces mécanismes pour le temps réel
Un exécutif temps réel multitâches offre une politique d'ordonnancement préemptive basée sur les priorités.
L’application est testée pour contrôler le bon respect des contraintes temporelles.
Limites :
Affecter des priorités n'est pas toujours une garantie de maîtrise des contraintes temporelles (variables partagées).
PlanPlan
Services d'un système élémentaire
Services multitâches
Gestion du processeur
Partage des ressources et exclusion mutuelle
Partages des ressources et exclusion mutuelle.Partages des ressources et exclusion mutuelle.
Une application temps réel est découpée en tâches. Ces tâches mettent en œuvre des algorithmes portant sur un ensemble de ressources qui peuvent être partagées.
Problème
T1LireAA=A+10EcrireA
T1LireAA=A+10EcrireA
T2LireAA=A+30EcrireA
T2LireAA=A+30EcrireA
Si T2 préempte T1 suite à une interruption :
LireALireAA=A+30EcrireA
A=A+10EcrireA
Des solutionsDes solutions
Les problèmes viennent du fait que l'exécution des séquences est intérrompue
On appelle séquence atomique, une suite d'opérations exécutées par un système qui permet de passer d'un état cohérent du système à un autre état cohérent sans possibilité d'interruption.
On appelle section critique, une séquence d'opérations qu'il faut effectuer de façon atomique.
Les sections critiques portant sur des ressources communes doivent être exécutées en exclusion mutuelle.
Solutions : Masquage et sémaphore.
Les sémaphores binairesLes sémaphores binaires
Un sémaphore est une entité logique gérée par le système d'exploitation associé de manière univoque à une ressource.
Deux primitives P et V permettent de manipuler le sémaphore
P : Compteur = Compteur-1si compteur<0 mettre la T en fille d'attentesinon accorder la ressource
V :Compteur = Compteur+1si compteur <=0 sortir une tâche de la fille d'attente
ExempleExemple
T1P(s)I=I+J;V(s)
T2P(s)I=I-k;V(s)
Lire I dans R1Lire J dans R2additionner R1 à R2…
Le sémaphore S est initialisé à 1.
Listes des mécanismes sémaphores pour le temps réelListes des mécanismes sémaphores pour le temps réel
A partir du moment où une tâche a acquis une ressource (passé le P), toutes les tâches parvenant à un P sur le même sémaphore resteront bloquées, quelle que soit leur priorité.
Ces cas de blocage posent un problème car il existe des cas où l'on ne sait pas donner de bornes temporelles à ce type de situation.
ConclusionConclusion
L'exclusion mutuelle, la communication et la synchronisation sont des problèmes généraux à prendre en compte dès que plusieurs tâches s'exécutent concurremment dans un système.
Le maintien de la cohérence des données et des codes du système conduit les tâches à utiliser des services qui génèrent des mises en file d'attente.
Un système qui attribue des priorités aux tâches, ne peut plus assurer qu'une tâche de plus faible priorité ne bloque pas une tâche de plus forte priorité.
Nous allons identifier et présenter les mécanismes spécifiques qui permettent de prévoir avec plus d'exactitude le comportement temporel d'un système.
Nous allons identifier et présenter les mécanismes spécifiques qui permettent de prévoir avec plus d'exactitude le comportement temporel d'un système.
