exo_04 Technique MULTILEVEL_QUEUE facultatif
Dans cet exercice
vous rajoutez la technique MULTILEVEL_QUEUE
au simulateur.
MULTILEVEL_QUEUE
Le système assez complexe qu'Unix utilise, consistant en une collection
de files chacune traitée comme un tourniquet. Un processus se voit
assigné dans une file plutôt qu'une autre suite à un recalcul
périodique de son utilisation du CPU. Plus il est gourmand, moins il
a la prioritè.
Une fois les files (re)remplies, l'ordonnanceur fait tourner celle la plus
prioritaire jusqu'à sa vidange complète. Après il passe
à la file voisine, etc.
Le recalcul des priorités se fait périodiquement : typiquement on
peut prendre un facteur de dix -- toutes les dix tranches de temps,
on réassigne les priorités.
La formule (simplifiée), récursive, à utiliser est
Priorite(moment i) = (Utilisation CPU(depuis i-1 jusqu'a i) + Priorite(moment i-1))/2
Dans les vrais systèmes on rajoute des termes comme la priorité
de base, ainsi que la valeur de nice.
Quoi de neuf
On doit se prendre une nouvelle donnée-membre de la
classe Scheduler. Il s'agit du
vector de deques mLevelQueue. De plus, dans la branche
correspondante du switch de electAProc() il faut également
prévoir le recalcul périodique des priorités, mais non pas
à chaque appel.
C'est toujours enQueueProc() qui s'occupe
de l'insertion dans la bonne file.
Pour simplifier, comme on l'a dit plus haut, le quantum de temps est constant.
Quand tout fonctionne, ça a
l'air à peu prés comme ça, où on l'a lancé
pour trois programmes.
-- Total 3 procs, now electing one among (0(2,1)) got # 2 prog2.sched ----------
+ prog0.sched+ prog1.sched * prog2.sched*
+io x 8 8 + cpu a 5 6 *cpu r 5 2 *
+*^^^^^^^^^^^+ *^^^^^^^^ *cpu a 3 4 *
+cpu x 7 7 + cpu r 7 4 **^^^^^^ *
+cpu a 5 6 + io x 8 8 *io a 8 9 *
+ + cpu x 4 4 *cpu r 9 8 *
+ + *io a 4 5 *
----------------------------------------------------------------------------------
+ io 0 + wait 0 * running 0 *
prog0.sched prog1.sched prog2.sched
io x 8 8 cpu a 5 6 cpu r 5 4
cpu x 7 7 *^^^^^^^^ cpu a 3 4
* cpu r 7 4 *
cpu a 5 6 io x 8 8 io a 8 9
cpu x 4 4 cpu r 9 6
io a 4 5
wait 0 wait 0 wait 0
----------------------------------------------------------------------------------
-- Total 3 procs, now electing one among (0(0) 1() 2(1,2)) got # 0 prog0.sched ---
* prog0.sched* prog1.sched prog2.sched
*io x 8 8 * cpu a 5 6 cpu r 5 4
*cpu x 7 7 * *^^^^^^^^ cpu a 3 4
**^^ * cpu r 7 4 *
*cpu a 5 6 * io x 8 8 io a 8 9
* * cpu x 4 4 cpu r 9 6
* * io a 4 5
* running 0 * wait 2 wait 2
Dans le premier instantané, deux sont sur la file d'attente (file zéro,
éléments 2 et 1), et un en train de "faire" des
entrées-sorties. On vient d'élire prog2.sched et donc il
passe en running priorité
zéro, et c'est sa deuxième instruction qui est en cours.
Ensuite il finit sa tranche de temps, et donc passe en attente, et entre temps,
l'entrés-sortie de prog0.sched est également
terminée. L'ordonnanceur décide également de recalculer
les priorités (on a choisi le bon moment du déroulement pour cet exemple) et c'est
prog0.sched qui est maintenant élu.
