Universit de la Manouba
Examen Syst mes dexploitation temps r el
Ecole Nationale des
Sciences de lInformatique
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)
1.
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.
2
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
2.
Lors de limpl mentation dun ordonnancement par horloge, il est plus appropri dutiliser un
ordonnancement autour dun frame de taille fixe, plut t que les dur es dex cution des t ches.
a. Expliquer pourquoi lordonnancement cyclique structur est plus appropri .
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&..
b. Donner les contraintes que doit satisfaire la taille du frame.
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&..
Exercice 2 (4 points) :
1.
En proc dant lanalyse de demande en temps, conclure sur lordonnan 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
1
1/8
Universit de la Manouba
Examen Syst mes dexploitation temps r el
Ecole Nationale des
Sciences de lInformatique
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 : &&&&..&&&&&&&.
-------------------------------------------------------------------------------------------------------------------------------------------------------
2
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
2. Augmenter le budget dex cution du serveur tout en pr servant son ordonnan abilit selon
2
Publicité
RM.
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&..
2/8
Universit de la Manouba
Examen Syst mes dexploitation temps r el
Ecole Nationale des
Sciences de lInformatique
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 3 (4 points) :
Nous rappelons dans lannexe quelques d finitions et r gles.
1.
Expliquer (de pr f rence via des sch mas) les r gles de r approvisionnement R2 et R3.b.
1
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&..&&&&&&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
2.
Simuler sur la grille ci-dessous lordonnancement selon RM du syst me compos des t ches
T1, T2 et T3 et dun 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)
3
Indiquez
lorsque
n cessaire
le
nombre
de
portions
consid r es.
3/8
Universit de la Manouba
Examen Syst mes dexploitation temps r el
Ecole Nationale des
Sciences de lInformatique
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 : &&&&..&&&&&&&.
-------------------------------------------------------------------------------------------------------------------------------------------------------
Probl me (8 points) :
Consid rons quune secr taire soit affect e dans un service scolaire. Nous nous proposons
dorganiser 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
Publicité
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 lemploi du temps ; cela lui demande 2.5h de travail.
Elle doit g rer laccueil 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 dune 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. Lalgorithme dordonnancement utilis est EDF.
1.
Pour commencer, on ne tient pas compte du travail que n cessite laccueil des tudiants.
Nous consid rons que la secr taire est capable dinterrompre la r alisation dune 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 ?
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
1
1
1
4/8
Universit de la Manouba
Examen Syst mes dexploitation temps r el
Ecole Nationale des
Sciences de lInformatique
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 : &&&&..&&&&&&&.
-------------------------------------------------------------------------------------------------------------------------------------------------------
c. Donner son emploi du temps.
13h
19h
2.
Pour am liorer ses performances, son sup rieur hi rarchique lui propose de ne plus
sinterrompre, lorsquelle a d j d marr une t che, pour ex cuter une autre plus prioritaire.
Si lon consid re que le temps pour passer dun traitement un autre est n gligeable, peut-on
affirmer que le conseil du sup rieur est bien fond ?
13h
2
19h
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
3.
Prenons maintenant en compte laccueil des tudiants. Les moments darriv e des tudiants,
leur temps de service et le d lai au-del duquel ils simpatientent sont donn es dans le
Publicité
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 darriv e
Dur e apr s laquelle
l tudiant simpatiente (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 dexploitation temps r el
Ecole Nationale des
Sciences de lInformatique
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 : &&&&..&&&&&&&.
-------------------------------------------------------------------------------------------------------------------------------------------------------
en servant les tudiants avant quils ne simpatientent. 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 darriv e des
tudiants). Justifier la r ponse.
13h
19h
&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
3
Publicité
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 lintervalle occup le plus proche dans la plus r cente
s quence contigu dintervalles occup s de TH, commen ant avant t
END est la fin de lintervalle occup le plus proche dans cette s quence si cet intervalle finit
avant t, END = si lintervalle finit apr s t
Division du budget dex cution en portions :
B1 : initialement, le budget = eS et tr = 0. Il y a une seule portion dex 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
lordre de
leurs derniers
instants de
r approvisionnement
C2 : le serveur consomme son budget uniquement lorsquil sex 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 lorsquelles
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), lexception des conditions suivantes:
a. Si te + pS est avant tf, le budget est r approvisionn lorsquil 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 dadmission des t ches sporadiques/EDF
un instant t, il y a n t ches sporadiques actives dans le syst me
Lordonnanceur EDF maintient une liste de ces t ches, dans un ordre croissant des d lais
Les d lais partitionnent le temps partir de linstant t jusqu en n+1 intervalles
discrets : I1, I2, &, In+1
"
I1commence linstant t et fini au d lai le plus proche parmi les d lais des t ches
sporadiques
" Pour chaque k tel que 1 d k d n, chaque intervalle Ik+1 commence lorsque
lintervalle Ik fini et fini au prochain d lai dans la liste (ou bien pour In+1)
Lordonnanceur maintient la densit totale s,k de chaque intervalle Ik
Soit Il lintervalle contenant le d lai d de la nouvelle t che sporadique S(t, d, e)
Lordonnanceur accepte la t che S si pour tout k=1, 2, &, l (Il est lintervalle qui contient
d)
Dp est la densit de toutes les t ches p riodiques
Cest- -dire : accepter la nouvelle t che sporadique si elle peut tre ajout e sans
augmenter la densit daucun des intervalles ant rieurs
8/8