22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
ORDONNANCEMENT DES PROCESSUS
ORDONNANCEMENT DES PROCESSUS
I-Définition
1.Processus
Un processus se définit comme étant un programme en cours
d'exécution. La notion de processus est dynamique : un
processus naît (commence) lors du chargement d’un
programme et meurt (se termine) à la fin de l’exécution du
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 1/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
programme. Dans les
systèmes multi-programmés et temps-partagé, un processus
peut se trouver dans l’un des états suivants :
1. Élu : si le processus est en cours d'exécution.
2. Bloqué : si le processus est en attente qu’un événement
se produit ou bien d’une ressource pour pouvoir
continuer.
3. Prêt : si le processus dispose de toutes les ressources
nécessaires à son exécution à l'exception du processeur.
2.Ordonnancement
En informatique, l'ordonnancement est le fait d'ordonner
des tâches à exécuter selon certaines contraintes. Les
contraintes peuvent être temporelles ou dimensionnelles.
Dans les systèmes d'exploitation, l’ordonnanceur désigne le
composant du noyau du système d'exploitation choisissant
l'ordre d'exécution des processus sur les processeurs d'un
ordinateur.
À un instant donné, il y a souvent davantage de processus à
exécuter que de processeurs.
Un des rôles de l'ordonnanceur du noyau,
est de permettre à tous ces processus de s'exécuter à un
moment ou un autre et d'utiliser au mieux le processeur pour
l'utilisateur.
II-Les différents types d’ordonnancement
1.Dispatcheur
Il s’occupe de l’allocation du processeur à un processus
sélectionné par l’Ordonnanceur du processeur. Une fois
alloué, le processeur doit réaliser les tâches suivantes :
Commutation de contexte : sauvegarder le contexte du
processus qui doit relâcher le processeur et charger le
contexte de celui qui aura le prochain cycle processeur
Commutation du mode d’exécution : basculer du mode
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 2/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
Maître (mode d’exécution du dispatcheur) en mode
utilisateur (mode d’exécution du processeur utilisateur)
Branchement : se brancher au bon emplacement dans le
processus utilisateur pour le faire démarrer.
2.Scheduleur(ordonnanceur)
Certains systèmes d’exploitation utilisent une technique
d’ordonnancement à deux niveaux qui intègre deux types
d’Ordonnanceurs :
Ordonnanceur du processeur : c’est un Ordonnanceur court
terme opère sur une ensemble du processus présents en
mémoire. Il s’occupe de la sélection du processus qui aura le
prochain cycle processeur, à partir de la file d’attente des
processus prêts.
Ordonnanceur de travail : ou Ordonnanceur long terme,
utilisé en cas d’insuffisance de mémoire, son rôle est de
sélectionné le sous ensemble de processus stockés sur un
disque et qui vont être chargés en mémoire. Ensuite, il
retire périodiquement de la mémoire les processus qui sont
restés assez longtemps et les remplace par des processus
qui sont sur le disque depuis trop de temps.
Nous distinguons plusieurs algorithmes d’ordonnancement,
les plus répandus sont :
Ordonnancement Premier Arrivé Premier Servi (FIFO)
Ordonnancement du plus court d’abord (SJF)
Ordonnancement circulaire : Tourniquet (Round-Robin)
Ordonnancement circulaire à plusieurs niveaux
Ordonnancement avec priorité
III-Critère de scheduling
L'utilisation intensive du processeur : Le système perd
son efficacité si le processeur passe trop de temps à
attendre des E/S
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 3/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
.Capacité de traitement : C’est la quantité de
processus terminé par unité de temps.
Temps de restitution : C’est le temps s’écroulant entre
la soumission du travail et sa terminaison.
Temps de réponse ou temps de séjour : C’est le temps
passer dans la file d’attente des processus prêts avant
la première exécution. Pour calculer le temps de réponse
moyen (TRM) d’exécution des processus on utilise la
formule suivante :
Avec TRi= temps fin d'exécution - date d'arrivée
Temps d'attente : C'est le temps moyen qu'un
processus passe à attendre.Le temps d’attente moyen
d’exécution des processus (TAM) est calculé comme suit
:
Avec TAi= TRi - temps d'exécution
Les algorithmes d’ordonnancement peuvent être classes en
deux grandes catégories :
Ordonnanceur non préemptif : dans un système à
ordonnancement non préemptif ou sans réquisition le
système d’exploitation choisi le prochain processus à
exécuter et lui alloue le processeur jusqu’à ce qu’il se
termine ou qu’il se bloque. Il n’y a pas de réquisition
même si le processus s’exécuter pendant des heures.
Ordonnanceur préemptif : dans un schéma
d’ordonnanceur préemptif ou avec réquisition le
système d’exploitation peut retirer à n’importe quel
moment le processeur à un processus même si ce
dernier est en cours d’exécution. Au niveau des
algorithmes d’ordonnancement préemptif lorsqu’un
processus est sélectionné il s’exécute pendant un délai
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 4/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
déterminé après ce délai il est remplacé par un autre
processus.
Remarque
Pour représenter schématiquement l’évolution dans le temps des
processus, on recourt habituellement à des diagrammes de Gantt
IV-Les algorithmes d'ordonnancement
1.Ordonnancement FIFO ou FCFS
1.1-Principe
Quand un processus est prêt à s’exécuter, il est mis en
queue de la file d’attente des processus
prêts
Quand le processeur devient libre, il est alloué au
processus se trouvant en tête de file d’attente des
processus prêts.
Le processus élu relâche le processeur s’il se termine ou
s’il demande une entrée sortie.
Cet algorithme est classe dans la catégorie des
ordonnanceurs non préemptifs ou sans réquisitions. Ce qui
veut dire que si un processus est élu, il ne relâche le
processeur que lorsqu'il a fini son exécution.
1.2-Exemple d'algorithme FIFO
Considérons 5 travaux A, B, C, D, E dont le temps
d’exécution respectifs et leur arrivage respectifs sont
données dans le tableau suivant :
Processus Temps d’exécution Temps d’arrivée
A 3 0
B 6 1
C 4 4
D 2 6
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 5/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
E 1 7
En utilisant un algorithme d’ordonnancement FCFS (Fifo)
donnez :
1. le diagramme de Gantt,
2. le temps de séjour de chaque processus,
3. le temps moyen de séjour des processus,
4. le temps d’attente de chaque processus,
5. le temps moyen d’attente des processus
1.3-Résolution
1-diagramme de Gantt
Situation explicative (adaptation de l’énoncé à une
boulangerie) : considérons 5 clients venant acheter des
pains dans une boulangerie dont leur arrivage respectif et le
nombre de pains voulus par chacun sont donnés dans un
tableau (on reprend le tableau précédent et le temps
d'exécution est aussi le nombre de pains(on considère que
pour servir un pain il faut un seconde)).
-A arrive à 0s donc il est servi en premier car étant le
premier arrivé. Il est servi en 3 secondes. Donc son temps
fin "de service" est 3 secondes.
-B arrive à 1s, mais c'est à 3s qu'il se fait servir (principe
fifo). Il est servi en 6s. Donc son temps fin "de service" est
9s.
-C arrive à 4s, mais est servi à 9s. Il est servi en 4s. Donc
son temps fin "de service" est 13s.
On procède de même pour les suivants.
Remarque
on a considéré le temps en seconde (s)
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 6/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
le temps fin "de service" (ou d'exécution dans le cas des
processus) s'obtient en additionnant le temps début "de
service"(correspondant au temps fin du précédent) au
temps "de service"(ou temps d’exécution)
Donc le diagramme est le suivant :
2-temps de séjour de chaque processus
Temps de séjour = temps fin d'exécution - temps d'arrivée
3-temps moyen de séjour
Temps moyen de séjour = somme des temps de séjour de
chaque processus divisée par le nombre de processus.
TMS= (3+8+9+9+9) / 5 = 7.6
4-temps d’attente de chaque processus
Temps d'attente = temps de séjour - temps d'exécution
processus Temps d’attente
A 3-3=0
B 8-6=2
C 9-4=5
D 9-2=7
E 9-1=8
5-temps moyen d'attente
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 7/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
Temps moyen d'attente = somme des temps d'attente
divisée par le nombre de processus
TMA = 22/5 = 4.4
2-Ordonnancement SJF
2.1-Principe
SJF ou SRTF (Shortest Remaining Time first) (plus court
temps d’exécution restant PCTER) choisit de façon
prioritaire les processus ayant le plus court temps
d’exécution sans réellement tenir compte de leur date
d’arrivée.
Les règles régissant cet ordonnancement sont :
Quand un processus est prêt à s’exécuter, il est inséré
dans la file d’attente des processus prêts à sa position
approprie.
Quand le processeur devient libre, il est assigné au
processus se trouvant en tête de la file d’attente des
processus prêts (ce processus possède le plus petit
cycle processeur.). Si deux processus ont la même
longueur de cycle, on applique dans ce cas l’algorithme
FIFO.
Si le système ne met pas en œuvre la réquisition, le
processus élu relâche le processeur s’il se termine ou s’il
demande une entrée sortie. Dans le cas contraire(avec
réquisition), le processus élu perd le processeur
également. Quand un processus ayant un cycle
d’exécution inférieur au temps processeur restant du
processus élu, vient d’entrer dans la file d’attente des
prêts. Le processus élu dans ce cas sera mis dans la file
d’attente des éligibles, et le processeur est alloué au
processus qui vient d’entrer.
Cet Ordonnanceur peut être avec ou sans réquisition
2.2-Exemple d'ordonnancement SJF
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 8/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
Considérons 5 travaux A, B, C, D, E dont le temps
d’exécution respectifs et leur arrivage respectifs sont
données dans le tableau suivant :
Processus Temps Temps
d’exécution d’arrivée
A 3 0
B 6 1
C 4 4
D 2 6
E 1 7
En utilisant un algorithme d’ordonnancement
SJF en mode non préemptif donnez :
1- le diagramme de Gantt
2-le temps de séjour de chaque processus
3-le temps moyen de séjour des processus
4-le temps d'attente de chaque processus
5-le temps moyen d'attente des processus
2.3-Résolution
1-diagramme de Gantt
Situation explicative : on reprend la situation précédente.
-à 0s, A est le seul présent à la boulangerie donc il sera
servi immédiatement. Il est servi en 3s donc son temps fin
"de service" est de 3s.
-à 3s, B est le seul présent à la boulangerie donc il sera servi
immédiatement. Il est servi en 6s donc son temps fin "de
service" est de 9s.
-lorsque B finit à 9s, on constate que C, D et E sont tous
présents à la boulangerie. Ils seront servis dans l'ordre du
nombre de pains (principe SJF), c'est-à-dire d'abord E
(servi en 1s), ensuite D (servi en 2s) et pour finir C (servi en
4s).
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 9/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
Donc le diagramme de Gantt est le suivant :
Pour le reste des questions, on applique juste les formules
comme dans l'exercice précédent.
2.4- En utilisant un algorithme d’ordonnancement SJF en
mode préemptif (avec requisition) donnez :
1- le diagramme de Gantt
2-le temps de séjour de chaque processus
3-le temps moyen de séjour des processus
4-le temps d'attente de chaque processus
5-le temps moyen d'attente des processus
2.5-Résolution
Situation explicative : on reprend toujours la même situation
-à 0s, A est le seul présent à la boulangerie donc il sera
servi immédiatement. Au bout d'une seconde, on constate
que B est aussi présent. Pour savoir qui exécuter, on se
réfère au nombre de pains. A a moins de pains à acheter que
B donc il va continuer d'être servi et fini à 3s.
-à 3s, B est le seul présent donc il sera servi, mais au bout
de 4s on constate la présence de C. En se référant au
nombre de pains, C à moins de pains à acheter que B. Le servi
de B est alors interrompu(pour le moment) et C est servi. B
s'interrompt après 1s (mais n'a pas fini d'être servi) donc C
commence à 4s.
-C est servi, mais après 2s D est présent. En se référant au
nombres de pains, on constate qu'ils sont à égalité (C a pu
avoir 2 pains avant l'arrivée de D donc il lui reste 2 pains)
alors C continue d'être servi (principe SJF) et finit en 4s.
Son temps fin est 8s.
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 10/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
-à 8s, D, E et B (ah oui! B est en attente car il lui reste 5
pains) sont présents. Ils sont servis en fonction du nombre
croissant de pains. Donc E est d'abord servi et finit à 9s,
ensuite D qui finit à 11s et enfin B qui finit à 16s.
Le diagramme de Gantt est le suivant :
Pour le reste des questions, on applique juste les formules
comme dans l'exercice précédent.
3-Ordonnancement basé sur les priorités
3.1-Principe
L’ordonnancement dans ce cas est régi par les règles
suivantes :
Quand un processus est admis par le système il est
insérer dans la file d’attente des processus prêts à sa
position appropries (selon la valeur de priorité)
Quand le processeur devient libre il est alloue au
processus se trouvant en tête de file d’attente des
processus prêts
Dans un cas de non préemption un processus élu relâche
le processeur que s’il se termine ou se bloque.
Cet Ordonnanceur peut être avec ou sans
réquisition.
Si le système met en œuvre la réquisition, quand un
processus de priorité supérieure à celle du processus élu
entre dans l’état prêt ; le processus élu sera mis dans la file
d’attente des éligibles à la position approprie, et le
processeur est alloué au processus qui vient d’entrer.
3.2-Application : il se fera en exercice. L'exercice sera
donner à la fin du cours.
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 11/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
4-Ordonnancement Round-Robin
4.1-Principe
Cet Ordonnancement est régit par les règles suivantes :
Un processus qui rentre dans l’état éligible est mis en
queue de la file d'attente des prêts.
Si un processus élu se termine ou se bloque avant de
consommer son quantum de temps, le processeur est
immédiatement alloué au prochain processus se trouvant
en tête de la file d'attente des prêts.
Si le processus élu continue de s'exécuter au bout de
son quantum, dans ce cas le processus sera interrompu
et mis en queue de la file d'attente des prêts et le
processeur est réquisitionné pour être ré-alloué au
prochain processus en tête de cette même file
d’attente.
Il est uniquement avec réquisition.
4.2-Application : il se fera en exercice. L'exercice sera
donner à la fin du cours.
Exercices
Considérons 5 travaux A, B, C, D, E dont le temps
d’exécution respectifs et leur arrivage respectifs sont
données dans le tableau suivant :
Processus Temps Temps
d’exécution d’arrivée
A 3 0
B 6 1
C 4 4
D 2 6
E 1 7
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 12/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
1) En utilisant un algorithme d’ordonnancement basé sur des
priorités en mode non préemptif et en mode préemptif
donnez :
1- le diagramme de Gantt
2-le temps de séjour de chaque processus
3-le temps moyen de séjour des processus
4-le temps d'attente de chaque processus
5-le temps moyen d'attente des processus
2) En utilisant un algorithme d’ordonnancement circulaire de
quantum Q = 2 donnez :
1- le diagramme de Gantt
2-le temps de séjour de chaque processus
3-le temps moyen de séjour des processus
4-le temps d'attente de chaque processus
5-le temps moyen d'attente des processus
Correction
la correction se fera en ligne au près des contacts suivants :
-Jean Luc: 07 46 69 96 ou 53 65 65 52
-Touré Lamagnigui: 09 41 64 02
-Qouddouss: 59 99 66 99 ou 53 65 65 95
NB: Essayez vous-même de faire les exercices en vous
inspirant de la logique présentée dans les applications qui ont
été corrigées.
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 13/14
22/03/2024 04:13 ORDONNANCEMENT DES PROCESSUS
infofacile.over-blog.com/2017/10/ordonnancement-des-processus.html 14/14
