26
F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 1 TD 1 Ordonnancement

TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

  • Upload
    ngotruc

  • View
    284

  • Download
    9

Embed Size (px)

Citation preview

Page 1: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 1

TD 1Ordonnancement

Page 2: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 2

Ordonnancement EDFOn considère 3 tâches périodiques :

● Tp1 : (r0 = 0, C = 5, D = 25, P = 30)

● Tp2 : (r0 = 0, C = 10, D = 40, P = 50)

● Tp3 : (r0 = 0, C = 20, D = 55, P = 75)

1) quelle est la période d’étude ?2) cette configuration est-elle ordonnançable par EDF3) tracer le chronogramme. Identifier les temps creux.

Page 3: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 3

Ordonnancement● période d'étude :

➢ PPCM(30, 50, 75) = 150● Ordonnançabilité par EDF

➢ condition suffisante :

● CH = 5/25 + 10/40 + 20/55 = 0,81

CH =∑i=1

n Ci

Di

≤ 1

Page 4: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 4

Ordonnancement EDF

0

0

0

30 60 90 120 150

Tp1

Tp2

Tp3

25 55 85 115 145

5040 90 150140

55 75 150130

● Tp1 : (r0 = 0, C = 5, D = 25, P = 30)

● Tp2 : (r0 = 0, C = 10, D = 40, P = 50)

● Tp3 : (r0 = 0, C = 20, D = 55, P = 75)

5

5 15

15 30 35

35 40

60

65

90

95

95 100

5040 7565 120110 125 1500 5 15 60 9590 100

125

100 110

Page 5: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 5

Ordonnancement EDF

0

0

0

30 60 90 120 150

Tp1

Tp2

Tp3

25 55 85 115 145

5040 90 150140

55 75 150130

5

5 15

15 30 35

35 40

60

65

90

95

95 100

5040 7565 120110 125 1500 5 15 60 9590 100

125

100 110

● temps creux : ➢ [40, 50], [65, 75], [110, 120], [125, 150]

Page 6: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 6

Ordonnancement EDF

● temps creux : ➢ [40, 50], [65, 75], [110, 120], [125, 150]

0

0

0

30 60 90 120 150

Tp1

Tp2

Tp3

25 55 85 115 145

5040 90 100 150140

55 75 150130

5040 7565 120110 125 1500

Page 7: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard      Cours Temps Réel      ESIL Département d'Informatique   3ème année  2009­2010                                                                                                                7   

Ordonnancement EDF

● On introduit 5 tâches apériodiques :● Tap1 : (r0 = 40, C = 10, D = 15)

● Tap2 : (r0 = 70, C = 15, D = 35)

● Tap3 : (r0 = 100, C = 20, D = 40)

● Tap4 : (r0 = 105, C = 5, D = 25)

● Tap5 : (r0 = 120, C = 5, D = 15)

● Quelles sont les tâches qui peuvent être ordonnancées dans les temps creux des tâches périodiques ?

Page 8: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 8

Ordonnancement EDF

● Tap1 (r=40, C=10, D=15)

➢ acceptée dans le temps creux [40, 50]

0

0

0

30 60

90 120 150

Tp1

Tp2

Tp3

25 55 85 115 145

5040 90 100 150140

55 75 150130

5040 7565 120110 125 150

Tap1

Tap140 55

Page 9: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 9

Ordonnancement EDF

● Tap2 (r=70, C=15, D=35)

➢ n'est pas acceptée car il n'y a pas de temps creux suffisant pour l'exécuter avant son échéance à t=105

0

0

0

30 60

90 120 150

Tp1

Tp2

Tp3

25 55 85 115 145

5040 90 100 150140

55 75 150130

5040 7565 120110 125 150

Tap1

Tap2

75 105

Page 10: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 10

Ordonnancement EDF

● Tap3 (r=100, C=20, D=40)

➢ est acceptée car elle peut s'exécuter dans les temps creux [110, 120] et [125, 150] et se terminer avant son échéance à t=140

0

0

0

30 60

90 120 150

Tp1

Tp2

Tp3

25 55 85 115 145

5040 90 100 150140

55 75 150130

5040 7565 120110 125 150

Tap1Tap3

110 135

Tap3

100 140

Page 11: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 11

Ordonnancement EDF

● Tap4 (r=105, C=5, D=25)

➢ peut être acceptée car son exécution retarde la terminaison de Tap

3 sans remettre en cause le respect de l'échéance

0

0

0

30 60

90 120 150

Tp1

Tp2

Tp3

25 55 85 115 145

5040 90 100 150140

55 75 150130

5040 7565 120110 125 150

Tap1 Tap3

Tap3Tap4Tap1

140

Tap4

105 130

140

Page 12: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 12

Ordonnancement EDF

● Tap5 (r=120, C=5, D=15)

➢ ne peut être acceptée car son exécution retarderait la terminaison de Tap

3 et remettrait en cause le respect de

l'échéance

0

0

0

30 60

90 120 150

Tp1

Tp2

Tp3

25 55 85 115 145

5040 90 100 150140

55 75 150130

5040 7565 120110 125 150

Tap1 Tap3

Tap1 Tap3Tap4

Tap5

Page 13: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 13

Serveur sporadique● 2 tâches périodiques + 1 serveur sporadique

➢ J1 : t

1 = 0, C

1 = 1, T

1 = 5

➢ J2 : t

2 = 0, C

2 = 4, T

2 = 15

➢ SS : Cs = 5, T

s = 10

● tâches apériodiques :➢ A

1 : t

a1 = 4, C

a1 = 2

➢ A2 : t

a2 = 8, C

a2 = 2

● ordonnancement :

J1

J2

SSactive

tâchesapériodiques

CS

0 2 20 2 2

Page 14: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 14

La mission Pathfinder sur Mars

Page 15: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 15

La mission Pathfinder● sonde sur Mars, arrivée le 4 juillet 1997● robot mobile Sojourner chargé de différentes tâches

➢ photos➢ relevés météo➢ prélèvements

● poids : 11.5kg● vitesse : 24m/h● puissance totale : 30W● liaison UHF avec la sonde

Pathfinder

● bug dans la gestion des ressources critiques ⇒ perte de données importantes

Page 16: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 16

● monoprocesseur RS6000 (architecture RISC de IBM)(+ un processeur Intel 8085 pour les automatismes de base du robot)

Architecture

Processeur MémoiresInterfacecaméra

Interfaceradio

Interfacealtimètre

Interfaceaccéléromètre

Interfaceenregistreur

Interface bus

Interfacecapteur

Interfacevannes

Interfacemoteurs

Interfaceanalyseur

caméraémetteur

radio

enregistreurmétéo

accéléromètrealtimètrealtimètre

moteurs vannes capteurs solaires

analyseurd'étoiles

bus VME

bus 1553

bus 1553

Sonde Pathfinder

Robot Sojourner

Coupleur

Coupleur

Page 17: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 17

Spécification fonctionnelle

● le système de gestion de la sonde communique avec l'extérieur par➢ la carte radio pour les liaisons avec la terre➢ la carte de liaison avec la caméra➢ l'interface avec le bus 1553 pour les autres

capteurs/actionneurs

Gestionsonde

Pathfinder

Carteradio

Cartecaméra

Réception

Emission

Images

Commandescaméra

Donnéesmesurées

Commandes

Interfacebus 1553

Page 18: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 18

Architecture logicielle

● multitâche gérée par le noyau Vxworks (Wind River)● 25 tâches

➢ périodiques (ex. : gestion du bus 1553)➢ apériodiques (ex. : analyse des erreurs)➢ communication et synchronisation par des files de

messages● suivant les phases de la mission (vol interplanétaire,

aterrissage, exploration par le robot), toutes les tâches ne sont pas utiles

Page 19: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 19

Architecture logicielle

● Liste des tâches et priorités relatives

Priorité Tâche Nature de la tâche

Maximum ORDO_BUS ordonnanceur du bus 1553

↑ DISTRIBUTION_DONNEES distribution des données du bus1553

↑ TÂCHE_PILOTAGE pilotage de l'application (robot)

↑ TÂCHE_RADIO gestion des communications radio

↑ TÂCHE_CAMÉRA gestion de la caméra

↑ TÂCHE_MESURES mesures

Minimum TÂCHE_METEO gestion des données météo

Page 20: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 20

Architecture logicielle

● Architecture en tâches

ORDO_BUS

HTR

commandes

TÂCHE_CAMÉRA

HTR

commandecaméra

TÂCHE_RADIO

HTR

émission

images

réception

DISTRIBUTION_DONNÉES

HTR

TÂCHE_PILOTAGE

HTR

TÂCHE_MESURE

HTR

TÂCHE-MÉTÉO

HTR

LIRE

ÉCRIRE

Tampon_données

données mesurées

(HTR : horloge temps réel)

Page 21: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 21

Utilisation du bus 1553

● la gestion du bus est pilotée par une horloge à 8 Hz (125ms)

● 2 tâches pour réguler le transfert des données➢ ORDO_BUS

✔ priorité maximale✔ vérifie que le transfert des données a été correctement

effectué et prépare le transfert suivant➢ DISTRIBUTION_DONNÉES

✔ 2 ème priorité✔ collecte les données sur le bus et les place dans la mémoire

tampon

Page 22: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 22

Caractéristiques des tâches

● pour CMÉTÉO

= 2, U=0.72 et pour CMÉTÉO

= 3, U=0.725

● analyse Rate Monotonic pourrait s'appliquer (URMA

=0.729),● mais partage de la ressource MÉMOIRE_TAMPON⇒ analyse détaillée

Paramètres (ms) Paramètresréduits

Tâche Priorité Ci Pi Ci Pi

Tempsutilisationressource

ORDO_BUS 7 25 125 1 5 ­

DISTRIBUTION_

DONNÉES 6 25 125 1 5 1

TÂCHE_PILOTAGE 5 25 250 1 10 1

TÂCHE_RADIO 4 25 250 1 10 ­

TÂCHE_CAMÉRA 3 25 250 1 10 ­

TÂCHE_MESURES 2 50 5000 2 200 2

TÂCHE_MÉTÉO 1 [50, 75] 5000 [2, 3] 200 [2, 3]

Page 23: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 23

recherche d'ordonnancement

● période d'étude théorique : 5000ms➢ mais on va se contenter d'étudier sur 250ms en

considérant que les tâches MESURES et MÉTÉO viennent de se terminer et en se mettant sur la période suivante

● étudier les cas CMÉTÉO

= 2 et CMÉTÉO

= 3➢ remplir les chronogrammes dans le cas où l’héritage de

priorité n’est pas activé

Page 24: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 24

diagramme d'exécution pour C=2

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

ORDO_BUS

TÂCHE_RADIO

TÂCHE_CAMÉRA

TÂCHE_MESURES

TÂCHE_MÉTÉO

RR R

R R

DISTRIBUTION_DONNÉES

TÂCHE_PILOTAGE

R R

R R

R

R

Inversion de priorité

Inversion de priorité

R

R R R R

R R

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

Page 25: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 25

diagramme d'exécution pour C=3ORDO_BUS

DISTRIBUTION_DONNÉES

TÂCHE_PILOTAGE

TÂCHE_RADIO

TÂCHE_CAMÉRA

TÂCHE_MESURES

TÂCHE_MÉTÉO R R

Inversion de priorité

Inversion de priorité

R R

RR R R R

R R R

ResetALARME

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

Page 26: TD 1 Ordonnancement - Polytech Marseillefrancois.touchard.perso.luminy.univ-amu.fr/ECM/TD1/TD1-ordo... · F. Touchard Introduction aux systèmes temps réels TD Ordonnancement

F. Touchard Introduction aux systèmes temps réels TD Ordonnancement 26

C=3 avec héritage de prioritéORDO_BUS

TÂCHE_RADIO

TÂCHE_CAMÉRA

TÂCHE_MESURES

TÂCHE_MÉTÉO

RDISTRIBUTION_DONNÉES

TÂCHE_PILOTAGE R

R

R

R R R R

R

R R

R R

R R

R

R

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 80 19 20 21 22 23 24 25

R

Héritage de priorité