Université de la Manouba

Examen « Systèmes d’exploitation temps réel »

Ecole Nationale des Sciences de l’Informatique

Enseignants : C. Jerad, M. Masmoudi, M. A. Abid Groupes : II2 SLE - RSR Documents : Non autorisés

Nom et prénom :…………………………………………………………………..

Durée : 2 H Date : 30/05/2014 Nbr de pages : 8 Groupe : ………………………

CIN : …………………………….……………………………………………………….. CE : …………..…………………. -------------------------------------------------------------------------------------------------------------------------------------------------------

Exercice 1 (4 points) :

Considérons un système composé de quatre tâches périodiques indépendantes préemptables qui tournent sur un seul processeur :

T1 = (4, 1), T2 = (5, 1), T3 = (10, 2), T4 = (20, 3)

Construire un ordonnancement cyclique des quatre tâches à implémenter sur un ordonnanceur par horloge et prouvez que les tâches respectent leurs délais.

….……………………………………………………………………………………………………………………………………………………………

Lors de l’implémentation d’un ordonnancement par horloge, il est plus approprié d’utiliser un ordonnancement autour d’un frame de taille fixe, plutôt que les durées d’exécution des tâches.

a. Expliquer pourquoi l’ordonnancement cyclique structuré est plus approprié.

….……………………………………………………………………………………………………………………………………………………………

….…………………………………………………………………………………………………………………………………………………………..

b. Donner les contraintes que doit satisfaire la taille du frame.

….……………………………………………………………………………………………………………………………………………………………

….…………………………………………………………………………………………………………………………………………………………..

Exercice 2 (4 points) :

En procédant à l’analyse de demande en temps, conclure sur l’ordonnançabilité selon RM des tâches T1(4, 1.5), T2(6, 1) et T3(10, 0.5) ainsi que le serveur différé Ss(3, 0.5).

1/8

Université de la Manouba

Examen « Systèmes d’exploitation temps réel »

Ecole Nationale des Sciences de l’Informatique

Enseignants : C. Jerad, M. Masmoudi, M. A. Abid Groupes : II2 SLE - RSR Documents : Non autorisés

Nom et prénom :…………………………………………………………………..

Durée : 2 H Date : 30/05/2014 Nbr de pages : 8 Groupe : ………………………

….……………………………………………………………………………………………………………………………………………………………

2. Augmenter le budget d’exécution du serveur tout en préservant son ordonnançabilité selon

RM.

….……………………………………………………………………………………………………………………………………………………………

….…………………………………………………………………………………………………………………………………………………………..

2/8

Université de la Manouba

Examen « Systèmes d’exploitation temps réel »

Ecole Nationale des Sciences de l’Informatique

Enseignants : C. Jerad, M. Masmoudi, M. A. Abid Groupes : II2 SLE - RSR Documents : Non autorisés

Nom et prénom :…………………………………………………………………..

Durée : 2 H Date : 30/05/2014 Nbr de pages : 8 Groupe : ………………………

Exercice 3 (4 points) :

Nous rappelons dans l’annexe quelques définitions et règles.

Expliquer (de préférence via des schémas) les règles de réapprovisionnement R2 et R3.b.

….………………………………………………………………………………………………………………………………………………

……………….…………………………………………………………………………………………………………………………………

…………………………….……………………………………………………………………………………………………………………

……………………………………..…………………………….……………………………………………………………………………

….………………………………………………………………………………………………………………………………………………

Simuler sur la grille ci-dessous l’ordonnancement selon RM du système composé des tâches T1, T2 et T3 et d’un serveur SpSL Tss. Les tâches A1,…, A4 sont des tâches apériodiques. T1=(3, 0.5) T2=(4, 1.0) T3=(19, 4.5) Tss=(5, 1.5) A1 = (r=3, e=1) A2 = (r=7 , e=2) A3 = (r=15.5, e=2) A4 = (r=6.5, e=0.5)

Indiquez

lorsque

nécessaire

nombre

portions

considérées.

3/8

Université de la Manouba

Examen « Systèmes d’exploitation temps réel »

Ecole Nationale des Sciences de l’Informatique

Enseignants : C. Jerad, M. Masmoudi, M. A. Abid Groupes : II2 SLE - RSR Documents : Non autorisés

Nom et prénom :…………………………………………………………………..

Durée : 2 H Date : 30/05/2014 Nbr de pages : 8 Groupe : ………………………

Problème (8 points) :

Considérons qu’une secrétaire soit affectée dans un service scolaire. Nous nous proposons d’organiser sa journée de travail qui commence à 13h et se termine à 19h. La secrétaire doit réaliser un certain nombre de tâches dans sa journée :

 Elle doit trier et distribuer le courrier. Le courrier arrive à 13h et à 16h. Le courrier de 13h doit être distribué avant 16h et celui de 16h doit être distribué avant 19h. Cette tâche lui demande 30 minutes à chaque fois.

 Elle a pour charge la réalisation de l’emploi du temps ; cela lui demande 2.5h de travail.  Elle doit gérer l’accueil des étudiants et répondre, tant que possible, à leur demande

administrative.

 Son contrat de travail lui octroie des pauses tout au long de la journée. Pour chaque période de 2h de travail, elle peut stopper le travail pendant 15 minutes. Le service disposant d’une badgeuse, elle peut fractionner ses pauses de 15 minutes comme bon lui semble du moment où elle ne dépasse pas 15 minutes toutes les 2 heures.

La secrétaire est assimilée à un processeur. L’algorithme d’ordonnancement utilisé est EDF.

Pour commencer, on ne tient pas compte du travail que nécessite l’accueil des étudiants. Nous considérons que la secrétaire est capable d’interrompre la réalisation d’une tâche si une autre plus prioritaire intervient.

a. Identifier les différentes tâches ainsi que leurs caractéristiques.

….………………………………………………………………………………………………………………………………………………

……………….…………………………………………………………………………………………………………………………………

…………………………….……………………………………………………………………………………………………………………

……………………………………..…………………………….……………………………………………………………………………

……………………………………………………………………………..…………………………….……………………………………

…………………………………………………………………………………………………………………………………………………

……………….…………………………………………………………………………………………………………………………………

b. Est-ce que la secrétaire peut effectuer sa charge de travail tout en respectant les

contraintes temporelles ?

….………………………………………………………………………………………………………………………………………………

……………….…………………………………………………………………………………………………………………………………

4/8

Université de la Manouba

Examen « Systèmes d’exploitation temps réel »

Ecole Nationale des Sciences de l’Informatique

Enseignants : C. Jerad, M. Masmoudi, M. A. Abid Groupes : II2 SLE - RSR Documents : Non autorisés

Nom et prénom :…………………………………………………………………..

Durée : 2 H Date : 30/05/2014 Nbr de pages : 8 Groupe : ………………………

c. Donner son emploi du temps.

13h

19h

Pour améliorer ses performances, son supérieur hiérarchique lui propose de ne plus s’interrompre, lorsqu’elle a déjà démarré une tâche, pour exécuter une autre plus prioritaire. Si l’on considère que le temps pour passer d’un traitement à un autre est négligeable, peut-on affirmer que le conseil du supérieur est bien fondé ?

13h

19h

….………………………………………………………………………………………………………………………………………………

……………….…………………………………………………………………………………………………………………………………

…………………………….……………………………………………………………………………………………………………………

….………………………………………………………………………………………………………………………………………………

……………….…………………………………………………………………………………………………………………………………

Prenons maintenant en compte l’accueil des étudiants. Les moments d’arrivée des étudiants, leur temps de service et le délai au-delà duquel ils s’impatientent sont données dans le tableau ci-dessous.

Nom de l’étudiant Tâches apériodiques

Temps de service nécessaire (mn)

Capacité

Etudiant1 Etudiant2 Etudiant3 Etudiant4

15 75 30 15

Heure d’arrivée

Durée après laquelle l’étudiant s’impatiente (mn)

Réveil

14h30 14h45 15h15 15h30

Deadline

30 90 45 30

Trouver un ordonnancement (ordonnancement préemptif avec temps de commutation négligeable) qui permet à la secrétaire de respecter ses différentes contraintes de temps tout

5/8

Université de la Manouba

Examen « Systèmes d’exploitation temps réel »

Ecole Nationale des Sciences de l’Informatique

Enseignants : C. Jerad, M. Masmoudi, M. A. Abid Groupes : II2 SLE - RSR Documents : Non autorisés

Nom et prénom :…………………………………………………………………..

Durée : 2 H Date : 30/05/2014 Nbr de pages : 8 Groupe : ………………………

en servant les étudiants avant qu’ils ne s’impatientent. Notons bien que si la secrétaire ne peut pas garantir que l’étudiant soit servi, elle lui demandera dès son arrivée de revenir une autre fois. La solution doit absolument garantir le respect des contraintes de temps pour la distribution du courrier, l’élaboration des emplois du temps et les pauses de la secrétaire, quitte le cas échéant à ne pas pouvoir servir les étudiants à temps (et ce, quel que soit la loi d’arrivée des étudiants). Justifier la réponse.

13h

19h

…………….……………………………………………………………………………………………………………………………………

………………………….………………………………………………………………………………………………………………………

.…………………………………………………………………………………………………………………………………………………

…………….……………………………………………………………………………………………………………………………………

………………………….………………………………………………………………………………………………………………………

.…………………………………………………………………………………………………………………………………………………

6/8

ANNEXE

-------------------------------------------------------------------------------------------------------------------------------------------------------

 tr est définit comme étant le dernier instant durant lequel le budget a été réapprovisionné

 tf est définit comme étant le premier instant après tr auquel le serveur commence son exécution

 À tout moment t :

 BEGIN est le commencement de l’intervalle occupé le plus proche dans la plus récente

séquence contiguë d’intervalles occupés de TH, commençant avant t

 END est la fin de l’intervalle occupé le plus proche dans cette séquence si cet intervalle finit

avant t, END =  si l’intervalle finit après t

 Division du budget d’exécution en portions :

 B1 : initialement, le budget = eS et tr = 0. Il y a une seule portion d’exécution  B2 : lorsque le serveur est suspendu, la dernière portion consommée juste avant la suspension,

si non consommée, est divisée en deux portions

• la première portion : celle consommée lorsque le serveur était occupé. Elle hérite le

prochain temps de réapprovisionnement de la portion originale

• La deuxième portion : le reste. Elle hérite le dernier temps de réapprovisionnement de la

portion originale

 Règles de consommation :

 C1 :

le serveur consomme

les portions dans

l’ordre de

leurs derniers

instants de

réapprovisionnement

 C2 : le serveur consomme son budget uniquement lorsqu’il s’exécute

 Règles de réapprovisionnement :

 Le prochain instant de réapprovisionnement de chaque portion du budget est fixée selon les règles R2 et R3 du serveur sporadique simple, les portions sont consolidés en un lorsqu’elles sont réapprovisionnées au même instant

 R2 : lorsque le serveur commence son exécution (définit comme étant tf)

Si END = tf alors te = max(tr, BEGEIN) Sinon si END < tf alors te = tf te est le temps effectif de réapprovisionnement le prochain instant de réapprovisionnement est te + pS

 R3 : le réapprovisionnement suivant a lieu au prochain instant de réapprovisionnement (=te +

pS), à l’exception des conditions suivantes:

a. Si te + pS est avant tf, le budget est réapprovisionné lorsqu’il est épuisé b. Si T passe au repos avant te + pS et devient occupé à nouveau à tb, le budget est

réapprovisionné à min(tb, te + pS )

7/8

ANNEXE

-------------------------------------------------------------------------------------------------------------------------------------------------------

 Contrôle d’admission des tâches sporadiques/EDF

 À un instant t, il y a n tâches sporadiques actives dans le système  L’ordonnanceur EDF maintient une liste de ces tâches, dans un ordre croissant des délais

 Les délais partitionnent le temps à partir de l’instant t jusqu’à ∞ en n+1 intervalles

discrets : I1, I2, …, In+1

•

I1commence à l’instant t et fini au délai le plus proche parmi les délais des tâches sporadiques

• Pour chaque k tel que 1 ≤ k ≤ n, chaque intervalle Ik+1 commence lorsque

l’intervalle Ik fini et fini au prochain délai dans la liste (ou bien ∞ pour In+1)

 L’ordonnanceur maintient la densité totale Δs,k de chaque intervalle Ik

 Soit Il l’intervalle contenant le délai d de la nouvelle tâche sporadique S(t, d, e)

 L’ordonnanceur accepte la tâche S si pour tout k=1, 2, …, l (Il est l’intervalle qui contient

 p est la densité de toutes les tâches périodiques  C’est-à-dire : accepter la nouvelle tâche sporadique si elle peut être ajoutée sans

augmenter la densité d’aucun des intervalles antérieurs

8/8