LES ALGORITMES D'ORDONNACEMENT
ROUND-ROBIN
Dans ce document nous allons effectuer l’algorithme de Round-Robin dans trois (3) situations différentes :
- Round-Robin, premier arrivé le premier servi
- Round-Robin priorité
- Round-Robin priorité avec traitement du phénomène de famine
Pour effectuer ces algorithmes nous aurons besoins :
- d’une liste de processus en attente d’exécution
- des fonctions et des procédures qu’on ne détaillera pas
-des variables
La liste
La liste se présentera sous forme de tableau dans lequel on trouvera le nom du processus, son temps d’exécution en milliseconde (ms) et de sa priorité.
|
Nom du processus |
Temps d’exécution (ms) |
Priorité |
|
processus1 |
10 |
3 |
|
processus2 |
1 |
1 |
|
processus3 |
2 |
3 |
|
processus4 |
1 |
4 |
|
processus5 |
5 |
2 |
Les processus à forte priorité sont les processus qui ont les plus petits chiffres. Comme toute liste, elle utilise des observateurs, des transformateurs et des prédicats.
Prédicat : on utilisera le prédicat liste_vide(L) qui nous informe si la liste est vide où L est une
liste
Observateur : premier_élément(L) qui nous donne le premier élément de la liste où L est une
liste
Transformateur : - ordonner_par_arrivé (L) qui ordonne la liste par ordre d’arrivée
- ordonner_par_priorité (L) qui ordonne la liste par priorité i.e. de la
priorité la plus haute à la priorité la plus basse. Dans cet algorithme, si
deux ou plusieurs processus ont la même priorité, on les classe par ordre
d’arrivée.
- mettre_en_fin_liste (L, P) qui met un processus en fin de liste
Dans cette liste chaque processus sera relié à son temps d’exécution et à sa priorité.
Fonctions et procédures
1- charger_sur_processeur (P) qui charge un processus P sur le processeur
2- enregistrer_paramètre (P) qui enregistre les paramètres d’un processus arrêté.
3- charger_paramètre (P) qui charge les paramètres d’un processus qui a été mis en attente ou d’un nouveau paramètre.
4- exécuter (P) qui exécute un processus
5- arrêter_exécution (P) qui arrête le processus P en cours d’exécution
6- augmenter_priorité_processus(L) qui augmente la priorité des processus présentent dans la liste.
7- supprimer (L, P) qui supprime un processus de la liste des processus.
Les variables
temps_exécution : Temps /* elle nous informe sur le temps que ce processus a besoin pour
terminer son exécution sans être interrompue */
temps_utilisé : Temps /* elle nous donne le temps utilisé par le processus */
liste_processus : Liste /* elle nous donne la liste des processus en attente */
processus : Processus
nombre_quantum : Entier /* elle nous renseigne sur le nombre de quantum déjà utilisé */
Nous aurons aussi besoin d’une constante quantum : Temps qui nous donne le temps alloué à chaque processus par le système pour s’exécuter.
Algorithme Round-Robin : premier arrivée, premier servi
Début
Tant que liste_vide (liste_processus) == NON faire
liste_processus := ordonner_par_arrivée (liste_processus) ;
processus := premier_élément (liste_processus) ;
charger_sur_processeur (processus) ;
charger_paramètre (processus) ;
temps_utilisé := 0 ;
Répéter
exécuter (processus) ;
processus.temps_exécution := processus.temps_exécution – 1 ;
temps_utilisé := temps_utilisé + 1
jusqu’à processus.temps_exécution == 0 ou temps_utilisé == quantum
arrêter_exécution (processus) ;
Si processus.temps_exécution != 0 alors
enregistrer_paramètre (processus) ;
metter_en_fin_liste (liste_processus, processus) ;
sinon
supprimer (liste_processus, processus) ;
fin si
fin tant que
Fin
Algorithme Round-Robin avec priorité
C’est le même algorithme que celui de Round-Robin premier arrivé premier servi, avec la différence qu’au lieu d’ordonner par arrivée, on va ordonner par priorité.
Début
Tant que liste_vide (liste_processus) == NON faire
liste_processus := ordonner_par_priorité (liste_processus) ;
processus := premier_élément (liste_processus) ;
charger_sur_processeur (processus) ;
charger_paramètre (processus) ;
temps_utilisé := 0 ;
Répéter
exécuter (processus) ;
processus.temps_exécution := processus.temps_exécution – 1 ;
temps_utilisé := temps_utilisé + 1
jusqu’à processus.temps_exécution == 0 ou temps_utilisé == quantum
arrêter_exécution (processus) ;
Si processus.temps_exécution != 0 alors
enregistrer_paramètre (processus) ;
metter_en_fin_liste (liste_processus, processus) ;
sinon
supprimer (liste_processus, processus) ;
fin si
fin tant que
Fin
Algorithme Round-Robin priorité avec traitement du phénomène de famine
Pour résoudre le phénomène de famine, nous allons augmenter la priorité des processus en attente après deux quantums de temps. Les processus de faible priorité vont leur priorité d’un pas et les processus dont la priorité est maximale resteront inchangés i.e. leur priorité ne changera pas.
Début
nombre_quantum := 0 ;
Tant que liste_vide (liste_processus) == NON faire
liste_processus := ordonner_par_arrivée (liste_processus) ;
processus := premier_élément (liste_processus) ;
charger_sur_processeur (processus) ;
charger_paramètre (processus) ;
temps_utilisé := 0 ;
Répéter
exécuter (processus) ;
processus.temps_exécution := processus.temps_exécution – 1 ;
temps_utilisé := temps_utilisé + 1
jusqu’à processus.temps_exécution == 0 ou temps_utilisé == quantum
arrêter_exécution (processus) ;
nombre_quantum := nombre_quantum + 1 ;
Si nombre_quantum == 2 alors
augmenter_priorité_processus (liste_processus) ;
nombre_quantum := 0 ;
fin si
Si processus.temps_exécution != 0 alors
enregistrer_paramètre (processus) ;
metter_en_fin_liste (liste_processus, processus) ;
sinon
supprimer (liste_processus, processus) ;
fin si
fin tant que
Fin