Plan Ordonnancement Obtention des tests de faisabilité entre processus Analyse de l'interaction entre processus Inclusion de processus apériodiques

Plan

Ordonnancement

Obtention des tests de faisabilité entre processus

Analyse de l'interaction entre processus

Inclusion de processus apériodiques

Vers une meilleure maîtrise du temps

Objectifs :

Nous présentons les mécanismes spécifiques qui permettent de prévoir avec plus d'exactitude le comportement temporel d'un système.

Nous étudions les méthodes d'ordonnancement temps réel.

Ordonnancement /définitions

C'est lors de l'ordonnancement que l'on choisit la tâche qui devient la tâche courante.

Dans les systèmes temps réel, on espère collecter des informations a priori pour pouvoir prédire le comportement de l'application.

C'est pourquoi des ordonnancements hors fonctionnement (off line) prennent les décisions avant l'exécution du système.

Si cela est possible, on a recourt à des algorithmes en ligne (on line) qui prennent les décisions durant l'exécution du système.

Ordonnancement hors-ligne

La séquence d'ordonnancement est donc pré-calculée avant l'exécution.

A l'exécution, l'ordonnanceur est un simple séquenceur : on parle de cyclic scheduler

Le séquenceur lit un tableau "modulo la longeur" : pas besoin d'exécutif multitâche

La mise en œuvre est simple

La surcharge est facilement détectable

Rigidité du séquenceur est une limitation.

1

T1

2

T1

3

Nop

4

T2

5

T3

6

T1

7

T2

t=19 (19mod7)=5

Ordonnancement en ligne

L'ordonnanceur implante un algorithme permettant de savoir à tout instant quel tâche exécuter

L'ordonnancement est un exécutif multitâche conduits par priorité

Les politiques sont importantes et flexibles

Un surcoût en temps et en ressource lors de la mise en œuvre

Les surcharge sont difficile à détecter

Ordonnancement /définitions

Un algorithme est dit statique s'il sait déterminer a priori les ordonnancements possibles de son système.

Un algorithme est dit dynamique si l'ordonnancement est déterminé lors de l'exécution. Il permet la prise en compte d'événements « non » prévus.

La faisabilité

Des études ont été menées pour trouver des critères associés aux tâches pouvant conduire à une politique d'ordonnancement optimale dans certains cas.

S'il existe un ordonnancement d'un ensemble de tâches qui respecte les contraintes temporelles associées à ces tâches, alors l'ensemble des tâches est dit faisable.

Un ordonnancement optimal est un ordonnancement qui peut produire un ordonnancement pour tout ensemble faisable de tâches.

Critères liés aux tâches

Les tâches périodiques sont celles qui doivent être activées à intervalles réguliers. Les instants de début d'exécution peuvent varier d'une instance à l'autre.

Capacité

Deadline

T : période

Exemple :

20 l de fluide 1 versé toutes les 100 ms.

40 l de fluide 2 versé toutes les 150 ms.

Sachant que pour verser un litre de fluide, il faut 1 ms.

100 ms pour une prise de température toutes les 350 ms.

Réacteur

Fluide 1Fluide 2

Modélisation du problème :

La gestion des 2 fluides et de la température est représentée par 3 tâches indépendants nommées P1, P2 et P3.

Ces 3 tâches s’effectuent périodiquement avec des temps d’activation différents (resp. 100, 150 et 350).

Et chacune exige un certain temps d’exécution ( resp. 20, 40 et 100).

Exemple introductif :

T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Réacteur

Fluide 1Fluide 2


T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Réacteur

Fluide 1


T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Réacteur

Fluide 2


T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Réacteur


T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Réacteur

Fluide 1


T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Réacteur

Fluide 2

P1

P2

P3

0 100 200 300 400 temps


T C P1 100 20P2 150 40

P3 350 100Réacteur


T C P1 100 20P2 150 40

P3 350 100!

P1

P2

P3

0 100 200 300 400 temps

Critères liés aux tâches

Les tâches sporadiques ne sont pas activées de façon régulière, mais on peut définir un temps minimal d'apparition entre deux activations d'instances successives. Elles ont des contraintes de temps fortes.

Les tâches apériodiques sont activées également à des instants irréguliers mais avec des échéances plus lâches et sans temps minimal entre deux activations.

Capacité

Deadline

A A + ?

Les algorithmes

Les algorithmes d'ordonnancement

statiques pilotés par tables

statiques préemptifs sur les priorités

dynamiques basés sur une planification à l'exécution

dynamiques basés sur la notion de meilleurs efforts

Les ordonnancements cycliques

On cherche à découper a priori une application en séquences élémentaires qui ne seront jamais interrompues.

Le modèle d'application est le suivant

Une séquence est une procédure définie par l'utilisateur

Un processus est une suite ordonnée de séquences ; qui s'exécutent consécutivement, dans l'ordre de la déclaration.

L'ordonnancement des processus est régi par un calendrier, c'est une table spécifiant la liste des processus à activer ; elle est de longueur arbitraire et exploitée cycliquement.

Le découpage en séquences élémentaires non interruptibles assure la protection des données partagées entre les processus.

Exemple

T C DP1: 25 10 25P2: 25 8 25P3: 50 5 50P4: 50 4 50P5: 100 2 100

Définir :un cycle majeur PPCM = (25,50,100)=100un cycle mineur qui correspond au rythme des interruptions d'horloge.

Pendant le cycle mineur l'application ne peut être interrompue.Ils définissent des points de contrôle permettant de contrôler que les traitementsapplicatifs ont bien respecté leurs échéances.

Exemple

T C DP1: 25 10 25P2: 25 8 25P3: 50 5 50P4: 50 4 50P5: 100 2 100

P1 P2 P3P510 8 5 2

P1 P2 P4 - 10 8 4 3

P1 P2 P3 - 10 8 5 2

P1 P2 P4 -10 8 4 3

IT horloge IT horloge IT horloge IT horloge

25

IT horloge = interruption possible

Les inconvénients

Comment prendre en compte des traitements qui ne sont pas périodiques ?

Comment ajouter un traitement supplémentaire sans modifier tout le système ?

Difficile si le nombre de processus augmente.

Il n'existe pas de solution optimale dont la complexité soit polynomiale en fonction du nombre de processus.

Mais, il est très utilisé dans les systèmes critiques, en particulier les systèmes aéronautiques ou les systèmes de défenses.

Les algorithmes de décisions en ligne

Les prise de décision s'effectuent à partir de critères qui peuvent être

statiques (valeur d'une priorité)

dynamique (dépend du temps)

Dans les modèles statiques, on utilise une transformation hors ligne des contraintes temporelles en entiers fixes représentant les priorités.

Dans les modèles dynamiques, la priorité évoluera en fonction du temps.

Plan

Ordonnancement




Obtention de tests de faisabilité d'ordonnancement

Existe-t-il des tests qui permettent de prévoir si un ensemble de tâches va respecter ses contraintes temporelles ?

Ordonnancement Rate-Monotonic (monotone par taux)

Il désigne la méthode d'affectation hors ligne de priorités statiques à un ensemble de tâches.

Les critères retenus pour les tâches sont

les tâches sont périodiques et sont à l'état PRÊT au début de chaque période.

Leur échéance se situe à la fin de la période.

Les tâches peuvent être préemptées.

Les tâches sont indépendantes les unes des autres.

Le temps d'exécution est connu.

L'affectation des priorités aux tâches se fait en fonction de la fréquence des tâches.

Si Ti désigne la période de la tâche i, sa priorité est égale à 1/Ti

Conditions suffisantes de l'analyse Rate Monotonic

Dans le cas où Di=Ti, n tâches respectent toutes les échéances si :

n

U = durée i / Période i i=1

n

Ui = C i / T i i(2 1/i -1) i=1

i, 1 i n

Principe de l'obtention

Cas simplifié de deux tâches.

But :

Atteindre une utilisation maximale du processeur en toute sécurité. On cherche donc une borne d'utilisation maximale pour tout ensemble de tâches qui utilisent le processeur au maximum de ses capacités.

Démarche :

Pour un C1 donné on cherche C2 de façon à utiliser un maximum le processeur.

Taux d'utilisation

0,7000,7300,7600,7900,8200,8500,8800,9100,9400,9701,000

Nombre de tâches

Ta

ux

d'u

tilis

ati

on

Û 1,000 0,828 0,780 0,757 0,743 0,735 0,729 0,724 0,721 0,718

1 2 3 4 5 6 7 8 9 10

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

n

1i TiCiiU

n

1i TiCiiU

753.0350100

15040

10020iU

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

1iiU 2 i1

1iiU 2 i1

779,013Ui 2 31

L’application numérique pour n = 3 donne :

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

On a bien,

La condition de faisabilité est satisfaite

On peut appliquer l'algorithme RM.

779,0753,0Ui

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

Préemption de P3 par P1!!!

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100 60

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100 60

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100 60

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100 30

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100 30


P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100 30

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100 20


P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

T C P1 100 20P2 150 40

P3 350 100

P1

P2

P3

0 100 200 300 400 temps

Exemple pour RM :

P1

P2

P3

0 100 200 300 400 500 600 700

0 20

20

60

60

80

Exemple pour RM :

P1

P2

P3

0 100 200 300 400 500 600 700

Utilisation du modulo.

Remarques :

La condition de faisabilité est très restrictive puisque dans l'exemple précédent, nous étions limités à utiliser le processeur à 77,9 % de sa capacité totale.

Mais notre but est de l’utiliser au maximum de ses capacités et cela en toute sécurité.

Quelques précisions :

On néglige le temps de communication et d'ordonnancement.Elles sont indépendants les unes des autres.

La capacité de chaque tâche est connue.

Leur échéance se situe à la fin de la période.

Les tâches sont périodiques et sont à l’état prêt au début de chaque période.

Elles ne se suspendent pas elles-mêmes en cours d'exécution.

Exemple

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19T2 T2 T3 T3 T1 T2 T2 T1 T1 nop T2 T2 T3 T3 nop T2 T2 nop nop nop

T1 T1 T1 T1T2 T2 T2 T2 T2 T2 T2 T2 T2T3 T3 T3 T3 T3

ID Depart C TT1 3 20T2 2 5T3 2 10

RM Cas d'échec

1 2T1 T2 T3

T1 T1T2 T2T3 T3

0 : T1 est déclenchée pour la :1 fois1 : T1 Finie son exécution N°12 : T2 Finie son exécution N°10 : T2 est déclenchée pour la :1 fois1 : T2 s'exécute2 : T3 DEADLINE DEPASSEE de2

ID Depart C T DT1 1 3 3T2 1 4 4T3 2 6 3

Il existe une solution

Théorème de la zone critique

La condition de l'analyse RM est très restrictive.

Théorème : Si toutes les tâches arrivent initialement dans le système simultanément et si elles respectent leur première échéance, alors toutes les échéances seront respectées par la suite, quel que soit l'instant d'arrivée des tâches.

Remarques : C'est une condition nécessaire et suffisante si toutes les tâches du système sont initialement prêtes au même instant. C'est uniquement une condition suffisante dans le cas contraire.

Test de terminaison (completion time test)

i

min C j / t *t / T j 10<t<Di j=1

i, 1 i n

Si l'échéance Di est égale à la période Ti, le test est le suivant.

Avec l'indice le plus faible à la tâche la plus prioritaire.

Méthode itérative pour le théorème de la zone critique

On recherche le temps t tel que :

i

t = C j *t / T j j=1

i, 1 i n, t Di,

i

Soit W i(t) = C j *t / T j j=1

Wi(t) représente la demande cumulée de temps processeur de toutesles tâches jusqu'à la tâche i dans l'intervalle [0,t].

On recherche Wi(t) / Wi(t)=t par itérations successives et ce pour toutes les tâches i

i

On part de t0 = Cj, si l'instant t ne respecte pas la condition, on j=1 itère en prenant comme nouveau temps t = Wi(t)

Exemple

100 200 300

P1

P2

P3

3 = 300/1003 = 300/100

Soit W i(t) = C j *t / T j=40*3

Exemple

Pi T CP1 100 40P2 150 40P3 350 100

U = 0.779,Mais on va montrer que l'exemplerépond au théorème de la zone critique.

Pour i=1 t0 = C1 = 40 = W1(40) StopPour i=2 t0 = C1+C2 = 80 = W2(80) StopPour i=3 t0 = C1+C2+C3 = 180 (>100 et 150)

W 3(180)= 2C1+2C2+C3 = 260W 3(260)= 3C1+2C2+C3 = 300W 3(300)= 3C1+2C2+C3 = 300 c'est la condition recherchée

Les trois tâches sont donc ordonnançables selon le théorème de lazone critique. La troisième tâche terminera l'exécution de sa premièreinstance au temps 300.

simulation du comportement

0

100

200

300

400

500

600

1 30 59 88 117 146 175 204 233 262 291 320 349 378

Série1

Série2

Série3

Série4

Autre algorithme : inverse deadline

Algorithme avec comme critère l'inverse de la deadline D

Inverse deadline

ID Depart C T DT1 3 20 7T2 2 5 4T3 2 10 9

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

T2 T2 T1 T1 T1 T2 T2 T3 T3 nop T2 T2 T3 T3 nop T2 T2 nop nop nop

T1 T1 T1 T1

T2 T2 T2 T2 T2 T2 T2 T2 T2

T3 T3 T3 T3 T3

Ordonnancements dynamiques

Les ordonnancements sont dits dynamiques car l'allocation de priorité aux tâches se fait lorsque le système est en fonctionnement.

Ils utilisent l'un des critères suivant à fin de prendre les décisions :

Échéances la plus proche d'abord (Earliest Deadline First) prend en compte l'urgence du travail à accomplir.

Marge la plus courte d'abord (Least Laxity Fisrt) prend également en compte l'urgence du travail à accomplir mais lui rajoute la notion de durée du travail.

Exemple EDF

T CP1 6 2P2 8 2P3 12 3

6 8 12 16 18 24

Exemple LLF

T CP1 6 2P2 8 2P3 12 3

6 8 12 16 18 24

La marge = Échéance - durée restante de traitement - temps courant

Least Laxity Fisrt

Exemple

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19T3 T1 T3 T2 T1 T2 T3 T1 T3 T1 T2 nop T3 T1 T3 T2 T1 T2 T3 T1

T1 T1 T1 T1 T1 T1 T1 T1T2 T2 T2 T2 T2 T2T3 T3 T3 T3 T3 T3 T3 T3

T D C MLT1 3 3 1 =Deadline-C_restanteT2 4 4 1T3 6 3 2

Ici T3 peut être aussi ordonnancé

Critère de l'ordonnançabilité EDF et LLF

Si l'on applique les algorithmes EDF et LLF à des tâches indépendantes périodiques le critère de faisabilité est donné par :

n

Ui = C i / T i 1 i=1

Optimalité de l'algorithme d'ordonnancement EDF

L'algorithme EDF est dit optimal car si un algorithme arrive à ordonnancer un ensemble de tâches possédant des échéances et des temps de traitement arbitraires, alors EDF saura également le faire.

Plan

Ordonnancement




Rappels

la communication et la synchronisation


Prise ne compte des cas de blocage : inversion de priorité

Héritage de priorité

Prise en compte des cas de blocage dans l'analyse RM.


Prise en compte des cas de blocage : inversion de priorité.

Hypothèse supplémentaire : Les tâches accèdent en exclusion mutuelle à des ressources communes. Ceci rend les tâches potentiellement dépendantes les unes des autres.

Problème : une tâche de plus faible priorité peut bloquer une autre tâche de priorité plus forte quand elle est en section critique = Problème de l'inversion de priorité.

j3 démarre à tps=0 j3 démarre à tps=0

4 6 8 14 16

j3

j2

j1

S

+ Prioritaire

0 1

S

S

S

5 7

t0 Rés

j1 2 S(2)j2 7 j3 0 S(5)

12 15

fin

Inversion de Priorité

10

j3 demande S à tps=1 j3 demande S à tps=1

4 6 8 14 16

j3

j2

j1

S

+ Prioritaire

20 1

S

S

S

5 7

t0 Rés

j1 2 S(2)j2 7 j3 0 S(5)

1210 15

fin


j1 démarre à tps=2 j1 démarre à tps=2

4 6 8 14 16

j3

j2

j1

S

+ Prioritaire

20 1

S

S

S

5 7

t0 Rés

j1 2 S(2)j2 7 j3 0 S(5)

1210 15

fin


4 6 8 14 16

j3

j2

j1

S

+ Prioritaire

20 1

S

S

S

j1 demande S qui est pris par j3 donc il est bloqué et redonne la main à j3


5 7

t0 Rés

j1 2 S(2)j2 7 j3 0 S(5)

1210 15

fin


4 6 8 14 16

j3

j2

j1

S

+ Prioritaire

0 1

S

S

S

5

À t=7, j2 démarre son exécution et finit à t=10

7

t0 Rés

j1 2 S(2)j2 7 j3 0 S(5)

10 15

fin


2 12

À t=10, j2 finit son exécution et redonne la main à j3

4 6 8 14 16

j3

j2

j1

S

+ Prioritaire

20 1

S

S

S

5 7

t0 Rés

j1 2 S(2)j2 7 j3 0 S(5)

1210 15

fin


A t=12, j3 relâche S etj1 profite pour récupérer S qu'elle avait demandé

4 6 8 14 16

j3

j2

j1

S

+ Prioritaire

0 1

S

S

S

5 7

t0 Rés

j1 2 S(2)j2 7 j3 0 S(5)

1210 15

fin


2

À t=15, j1finit son exécution et laissej3 finir elle aussi.


4 6 8 14 16

j3

j2

j1

S

+ Prioritaire

20 1

S

S

S

5 7

t0 Rés

j1 2 S(2)j2 7 j3 0 S(5)

1210 15

fin


4 6 8 14 16

j3

j2

j1

S

+ Prioritaire

20 1

S

S

S

5

Inversion de priorité7

t0 Rés

j1 2 S(2)j2 7 j3 0 S(5)

1210 15

fin

Durée ?Durée ?

Solutions à l'inversion de priorité

Une tâche ne doit pas être préemptée systématiquement si elle est en section critique.

Cette solution est acceptable pour des accès courts. Sinon le système créera des situations d'inversion de priorité fréquentes et inutilement longues.

Méthode de l'héritage de priorité (priority inherance).Le système effectue une gestion dynamique de priorité. L'idée est de rajouter aux sémaphores la notion de possesseurs.

Héritage de priorité

Le possesseur d'un sémaphore est la tâche qui a demandé et obtenu le droit de rentrer dans la zone d'exclusion mutuelle protégé par le sémaphore.

Dans l'héritage de priorité simple, les sémaphores gèrent leur file d'attente en tenant compte des priorités des tâches qui désirent prendre le sémaphore.

Lorsqu'une tâche détient un sémaphore et qu'une autre le réclame, la priorité de la tâche qui possède le sémaphore est augmentée au niveau de la priorité de la tâche qui le réclame.

Exemple

T3 demande et obtient S

T1 demande S

Fin T2

Fin T1

+ PrioritaireT3 hérite de la prioritéde T1

Fin T3T3 relâche S

Comparaison

?

Autre exemple

les tâches 1 et 2 ne partagent aucune ressource. Déroulement normale jusqu’à la fin. j4 demande V j4 demande S donc j5 bloque j4 qui bloque j1,donc j1 est bloqué par j5 qui hérite sa priorité (phénomène de Transitivité).

j5 prend la main puis libère S à tps=11.

j1 demande V qui est pris par j4.j4 bloque donc j1 et hérite sa priorité. j2 demande S qui est pris par j5. j5 bloque j2 et hérite sa priorité.

13

j5 demande S j5 démarre.

0 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22

5

4

3

2

1

taches ri ei pi Sections critiques

j1

j2

j3j4

j5

7

5

4

2

0

3

3

2

6

6

1

2

3

4

5

[V;1]

[S;1]

[V;2,5[S;1,5]]

[S;4]

Partage de plusieurs ressources : les inter-blocages possibles

Lorsqu'une tâche peut utiliser plusieurs sémaphores des cas d'inter-blocage peuvent apparaître.

L'inter-blocage n'est pas dû à une inversion de priorité mais à l'entrelacement des accès aux sémaphores.

Exemple

T2 démarre

T1 démarre

P(S2)

P(S1) P(S2) T1 bloquée

P(S1)

T2 bloquée

Solutions

1 Demander l'accès aux sémaphores dans le même ordre.

2 Exécuter en exclusion mutuelle toutes les sections correspondant aux sections critiques imbriquées. On garantit qu'une tâche ne peut commencer l'exécution d'une section critique qu'à condition de s'exécuter à un niveau de priorité supérieur aux niveaux de priorité des sections critiques préemptées.

Solution : Héritage par la méthode du verrou le plus haut

Dans la technique du verrou le plus haut (highest lock) la tâche qui utilise un sémaphore hérite d'une priorité qui est supérieure au plafond de priorité du sémaphore.

Le plafond de priorité (priority celling) d'un sémaphore est égal à la priorité maximale des tâches pouvant prendre le sémaphore.Cela consiste à maintenir une valeur qui représente la valeur maximale du plafond courant.

Priorité(verrou)= priorité_max(tâches qui prennent le verrou).Plafond=Max(priorités des verrous pris).

Exemple

T2 démarre

T1 Prêt

P(S2) P(S1) V(S1) V(S2)

P(S2)P(S1) V(S2) V(S1)

Solution : Héritage par la méthode du plafond de priorité

Dans la méthode du plafond de priorité (priority ceilling protocol) l'OS maintient une valeur qui représente la valeur maximale du plafond courant.

Lorsqu'une tâche essaye d'exécuter une section critique, elle est suspendue sauf si sa priorité est supérieure au plafond de priorité de tous les sémaphores pris par les autres tâches.

Exemple

T2 démarre

T1 démarre

P(S2)Plafond = Max(T1,T2)=T1

P(S2)

P(S1) V(S2)

P(S1) V(S1) V(S2)

P(S1) refuséT1<=Plafond

V(S1)

héritage

Exemple

0 2 4 6 8 10 12 14 16 18 20

?

2=П(t)

1

2

3

4

5

P4< P1>

1

1

3

45

Comparaison

0 2 4 6 8 10 12 14 16 18 20

1

2

3

4

5

5

4

3

2

1

Plan

Ordonnancement





On peut penser à interrompre les tâches périodiques pour faire passer les tâches apériodiques jusqu'à ce que celles ci se terminent. Mais on peut mettre en péril l'ordonnancement.

On peut affecter la priorité la plus basse aux tâches apériodiques. Cette solution n'offre qu'un temps de réponse moyen aux tâches apériodiques.

Les serveurs

On affecte un processus périodique en charge de contrôler les taches apériodiques en leur offrant la possibilité d'exécuter leur activité au niveau de priorité requis.Les méthodes existantes

Le serveur par scrutation (polling server)le serveur différé (deferabe serveur)

Serveur par scrutation

Le serveur de scrutation a la priorité la plus forte. On définit une capacité Cm pour cette tâche en fonction du profil d'arrivée des événements apériodiques à servir.

Le serveur est divisé en deux parties

La première regarde périodiquement s'il y a des événements périodiques à traiter

La deuxième partie est déclenchée s'il y a au moins un événement en attente d'être traité.

Exemple

T CP1 10 2P2 15 6S 5 2

t Ce1 2 1.5e2 6 2

e1

2 5 6 10 11.5 13.5

e2

Scrutatione1 sera pris en compte en 5

Prise en comptee2 prise en compte immédiate

0.5

Serveurs d'événements apériodiques

On fournit une ressource privée (une tâche fictive) à l'usage exclusif des tâches apériodiques.

On crée une tâche périodique DS, de capacité Cds et de période Tds qui servent à définir sa priorité selon la méthode RM.

Si toutes les tâches apériodiques sont traitées avec moins de capacité, on abandonne plus tôt la tâche DS (la capacité non utilisée est alors perdue).

Exemple

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19T2 T2 T1 T1 T1 Ta1 Ta1 nop nop nop Ta2 Ta3 T2 T2 nop Ta3 nop nop nop nop

T1 T1 T1 T1T2 T2 T2 T2 T2Ta1 Ta1 Ta1Ta2 Ta2Ta3 Ta3 Ta3serveur

ID Depart C T DT1 3 20 20T2 2 10 10Ta1 4 2Ta2 10 1Ta3 11 2

serveur 2 5 5

Exemple

T CP1 6 2P2 8 3Ds 5 1

t Ce1 1 .5e2 7 2e3 14 1

Épuisement de DS

Renouvellementde DS

e1 e2 e3

5 7 10 15

Serveur périodique et ordonnancement dynamique EDF

Les ordonnancements dynamiques permettent a priori, une meilleure utilisation du processeur. L'idée est de servir les tâches aux contraintes plus lâches au moyen de serveurs périodiques.

Exemple

T CP1 6 2P2 8 3Ds 4 1

t Ce1 1.5 .5e2 6 2

Épuisement de DS

Renouvelementde DS

e1 e2Arrive e2 et EDF plus gd

E2 est là mais P1 plus urgentEDFP1=12-9 EDFe2=3

Serveur sporadique

ID Depart C T DT1 3 20 20T2 2 10 10Ta1 4 2Ta2 10 1Ta3 11 2

serveur 2 5 5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19T2 T2 T1 T1 Ta1 Ta1 T1 nop nop nop Ta2 Ta3 T2 T2 nop Ta3 nop nop nop nop

T1 T1 T1 T1T2 T2 T2 T2 T2Ta1 Ta1 Ta1Ta2 Ta2Ta3 Ta3 Ta3serveur

Résumé : Rate Monotonic

Algorithme statique d'assignation de priorité

Test : charge totale sous la contrainte n(2 1/n-1)

Analyse exacte par le théorème de la zone critique

RM peut être augmenté pour prendre en compte les situations de blocage et les événements apériodiques.

Optimal car si un autre algorithme statique arrive à produire un ordonnancement alors RM y arrive aussi.

Résumé : Earliest Dealine First

Dynamique

Test : charge totale < 100%

Entraîne le moins de changements de contexte

EDF est optimal car on peut transformer tout ordonnancement arbitraire en ordonnancement EDF.

EDF peut être augmenté pour prendre en compte les situations de blocage et les événements apériodiques.

Meilleur algorithme quand la loi d'arrivée des tâches est quelconque et quand on ne connaît par leur capacité.

Exercice 1

On considère un système constitué de deux tâches périodiques indépendantes s'exécutant sur un processeur. Ces deux tâches sont définies par :

Ces deux tâches sont elles ordonnançables par l'analyse Rate Monotonic ?

Sont elles ordonnaçables par EDF ?

Pi T CT1 4 2P2 10 5

Exercice 2

On considère un système constitué de trois tâches périodiques définies par :

On applique d'abord l'analyse Rate Monotonic sur les tâches. Grâce au test de terminaison, calculer l'instant auquel la tâche3 termine sa première exécution. Respecte-t-elle son échéance ?On classe maintenant les trois tâches en fonction de leurs échéances (analyse deadline Monotonic). Utiliser le test suffisant de l'analyse RM pour prouver que les tâches 1,3 sont ordonnançables ( on considère que la tâche C subit un blocage E3 égal à T3-D3.

Pi T C DT1 100 20 100P2 150 78 150P3 160 30 145

Plan :

Introduction

I) De la théorie à la pratique

II) Mise en œuvre du simulateur1) Modélisation des tâches 2) Gestion des priorités Java3) Problèmes engendrés par l’OS 4) Démonstration du simulateur.

Conclusion

Le cœur du scheduler :

Comment gérer les priorités des threads pour qu’un ordonnancement tel que Rate Monotonic soit

respecté ?

Gestion de priorité (1) :

1ère idée :

Attribuer un niveau de priorité à chaque tâche à ordonnancer.


Problème :

Si le nombre de tâches est supérieur au nombre de priorités…

!


2 ème idée : Utiliser 3 niveaux de priorités.

1 niveau pour le scheduler : priorité maximum

1 autre pour la tâche courante : priorité intermédiaire

1 autre pour les autres tâches : priorité minimum.


Java

virtuel

machine

scheduler

T1 T2 T3 T4

Max

Middle

Min

priorité


Java

virtuel

machine

scheduler

T1 T2 T3 T4

Max

Middle

Min

priorité


Java

virtuel

machine

scheduler

T1

T2

T3 T4

Max

Middle

Min

priorité


Java

virtuel

machine

scheduler

T1

T2

T3 T4

Max

Middle

Min

priorité

Sleep

60 ns


Max

Middle

Min

priorité

Java

virtuel

machine

scheduler

T1

T2

T3 T4


Java

virtuel

machine

scheduler

T1

T2

T3 T4

Max

Middle

Min

priorité


Java

virtuel

machine

scheduler

T1 T2 T3 T4

Max

Middle

Min

priorité



À t=10,j2 finit son exécution et redonne la main à j3 j3 demande S à tps=1 j3 demande S à tps=1 j1 démarre à tps=2 j1 démarre à tps=2 j3 démarre à tps=0 j3 démarre à tps=0

A t=12, j3 relâche S etj1 profite pour récupérer S qu'elle avait demandé

4 6 8 14 16

j3

j2

j1

S

+ Prioritaire

20 1

S

S

S



5

À t=7, j2 démarre son exécution et finit à t=10

7

t0 Rés

j1 2 S(2)j2 7 j3 0 S(5)

1210 15

fin

Annexe Inversion de Priorité

Documents

Plan Ordonnancement Obtention des tests de faisabilité entre processus Analyse de l'interaction entre processus Inclusion de processus apériodiques