ENSI 2012/2013
S.E & Prog Conc
M.Nasri
TD Ordonnancement
de processus
Exercice 1 : On considère les cinq exécutions de processus suivants (la durée est exprimée
en seconde) :
1. Donner les diagrammes de Gantt et les temps de traitement moyen obtenus à l'aide des
algorithmes d'ordonnancement FIFO (Premier arrivée - Premier servi), PCTER (plus court
temps d'exécution restant et Tourniquet (avec un quantum de 1) en supposant un temps de
commutation de contexte négligeable.
2. Si le temps de commutation est de 0,5 seconde, quel est alors le temps moyen de
traitement dans le cas d'un ordonnancement PCTER et d'un ordonnancement tourniquet.
Qu'en déduisez-vous ?
ENSI 2012/2013
S.E & Prog Conc
M.Nasri
Exercice 2 :
Avec les processus répertoriés dans le tableau ci-dessous,
Publicité
dessinez un schéma illustrant leur exécution à l'aide de :
(a) L'algorithme FCFS
(b) L'algorithme SJF
(c) L'algorithme SRT
(d) L'algorithme à tourniquet (quantum = 2)
(e) L'algorithme à tourniquet (quantum = 1 )
ENSI 2012/2013
S.E & Prog Conc
M.Nasri
Solution 1 :
1.
2.
Cas PCTER : il y a 5 commutations de contexte (changement de
processus élu). Le tmt est alors le suivant :
((18,5 - 0) + (12 - 1) + (3, 5 - 1) + (7,5 - 2) + (5 - 3))=5 = 7, 9
Cas Tourniquet : il y a 13 commutations de contexte (changement de
processus élu). Le tmt est alors le suivant :
((22,5 - 0) + (19 - 1) + (11, 5 - 1) + (14, 5 - 2) + (10- 3))=5 = 14,1
Tenir compte des commutations ne change pas le fait que le protocole
Publicité
PCTER soit meilleure que les autres (et en particulier que le protocole
tourniquet). Le temps dû aux commutations est toutefois sensible sur le
ENSI 2012/2013
S.E & Prog Conc
M.Nasri
tmt avec le protocole tourniquet, celui-ci doit donc rester à un niveau
modéré.
Solution 2 :
(a) L'algorithme FCFS. Les processus sont exécutés dans l'ordre de leur arrivée.
(b) L'algorithme SJF. Le processus A commence son exécution ; il s'agit du seul
choix à la date 0. À la date 3, B est le seul processus de la file. À la date 9,
lorsque B s'achève, c'est le processus D qui s'exécute, car il est plus court que le
processus C.
(c) L'algorithme SRT. Le processus A commence son exécution ; il s'agit du seul
choix possible à la date 0. Il poursuit son exécution lorsque B arrive, car son
temps restant est plus court. À la date 3, le processus B est le seul processus de la
file. À la date 4,001, le processus C arrive et commence son exécution, car son
temps restant (4) est inférieur à celui du processus B (4,999). À la date 6,001,
le processus C poursuit son exécution, car son temps restant (1,999) est inférieur
Publicité
à celui de D(2). Lorsque le processus C prend fin, c'est le processus D qui
s'exécute, car son temps restant est inférieur à celui de B.
(d) L'algorithme à tourniquet (quantum = 2). À l'expiration du premier quantum de
temps de A, le processus B est exécuté. À la date 4, le processus A est relancé
et le processus B revient dans la file des processus prêts. À la date 4,001, le
processus C entre dans la file des processus prêts après le processus B. À la date
5, le processus A prend fin et le processus B s'exécute. A la date 6,001, le
processus D entre dans la file des prêts derrière le processus C. A partir de la
date 7, les processus C, D, B et C s'exécutent tour à tour.
ENSI 2012/2013
S.E & Prog Conc
M.Nasri
(e) L'algorithme à tourniquet (quantum = 1). Le processus A s'exécute pendant deux tranches de
temps, étant donné que le processus B n'arrive pas avant 1,001. Le processus B s'exécute à la date
4, puisque le processus C n'arrive qu'à 4,001. Le processus B s'exécute à nouveau à la date 6, le
processus J2 arrivant à 6,001. Le processus D entre dans la file des processus prêts derrière le
processus C. À partir de la date 7, l'exécution tourne en boucle à travers les processus C, D et B.