SYSTÈME D’EXPLOTATION
Ordonnancement des processus
Mlle Ikram Boursas
19 Juin 2022
Département d’informatique, Université Saad Dahlab blida 1
Introduction
❖ Dans un système multi-utilisateurs à temps partagé, plusieurs processus peuvent être présents en
mémoire centrale en attente d'exécution.
❖ Si plusieurs processus sont prêts, le système d'exploitation doit gérer l'allocation du processeur aux
différents processus à exécuter.
❖ C'est l'ordonnanceur qui s'acquitte de cette tâche.
❖ Un ordonnanceur fait face à deux problème :
❖le choix du processus à exécuter.
❖le temps d'allocation du processeur au processus choisi.
S.E préemptif
❖Un système d'exploitation multitâche est préemptif
➢lorsque celui-ci peut arrêter (réquisition) à tout moment n'importe quelle application pour passer la
main à la suivante.
❖ Dans les systèmes d'exploitation préemptifs on peut lancer plusieurs applications à la fois et passer de
l'une à l'autre, voire lancer une application pendant qu'une autre effectue un travail.
❖ le noyau garde toujours le contrôle
➢ se réserve le droit de fermer les applications qui monopolisent les ressources du système. Ainsi les
blocages du système sont inexistants.
S.E coopératif
❖Un système d'exploitation multitâche est coopératif
➢Lorsqu'il permet à plusieurs applications de fonctionner
➢et d'occuper des plages mémoire, laissant le soin à ces applications de gérer cette occupation,
➢au risque de bloquer tout le système.
❖ Par contre, avec un « multi-tâche préemptif », le noyau garde toujours le contrôle (qui fait quoi, quand
et comment), et se réserve le droit de fermer les applications qui monopolisent les ressources du système.
Ainsi les blocages du système sont inexistants.
L’ordonnancement
❖ L’ordonnancement (scheduling) est un ensemble de règles définissant l'ordre d'exécution des processus
en tenant compte de la disponibilité des ressources nécessaires (processeurs), de manière à optimiser un
ou plusieurs critères.
❖ On peut dire, également, que l'ordonnancement consiste à allouer une ou plusieurs tranches de temps
processeur à chaque processus existant dans le système.
Files D’attentes de l’ordonnancement
❖Pour gérer les processus durant leur séjour, le SE maintient plusieurs files d’attente :
➢ Files d’attente des processus prêts : peuvent être représentées par une ou plusieurs files : une file par
classe de processus (processus système, processus temps réel, processus temps partagé) ou une file par
priorité.
➢ Files d’attente des processus bloqués : peuvent être présentées par plusieurs files: une file par
événement, signal ou ressource attendu (file des processus en attente de l'imprimante, file des
processus en attente de fin d'E/S sur le disque,...)
Files D’attentes de l’ordonnancement
❖ Un nouveau processus est initialement placé dans la file d’attente des processus prêts. Il attend dans
cette file jusqu’à ce qu’il soit sélectionné pour son exécution et qu’on lui accorde le processeur.
❖ Une fois qu’on a alloué le processeur au processus et que celui-ci est en cours d’exécution, il pourrait se
produire l’un des événements suivants :
➢Le processus pourrait se terminer.
➢Le processus pourrait consommer le temps qui a été alloué par le processeur (système à temps
partagé). Dans ce cas, le processus est remis dans la file d’attente des processus prêts.
➢ Le processus pourrait attendre un évènement (signal) arrivant d’un autre processus.
Files D’attentes de l’ordonnancement
➢ Le processus pourrait émettre une requête d’E/S et ensuite placé dans une file d’attente d’E/S.
❖ Les différents états de transition du processus entre les files d’attente sont résumés comme suit :
L’ ordonnanceur
❖ L’ordonnanceur (scheduler) est un programme du SE qui s’occupe de choisir, selon une politique
d’ordonnancement donnée, un processus parmi les processus prêts pour lui affecter le processeur.
❖Les principaux objectifs assignés à un ordonnanceur sont:
➢Occuper au maximum le processeur, (Utiliser le processeur à 100%.)
➢S'assurer que chaque processus en attente d'exécution reçoive sa part de temps processeur.
➢Minimiser le temps de réponse pour les utilisateurs en mode interactif,
➢Satisfaire le maximum de processus des utilisateurs en respectant certaines contraintes telles que la
priorité, l'échéance (dans les systèmes temps réel), etc…
Critères D’ordonnancement
❖ Les divers algorithmes d’ordonnancement du processeur possèdent des propriétés différentes
et peuvent favoriser une classe de processus plutôt qu’une autre.
❖ Pour choisir quel algorithme utiliser dans une situation particulière, nous devons tenir compte
des propriétés des divers algorithmes.
❖ Plusieurs critères ont été proposés pour comparer et évaluer les performances des
algorithmes d’ordonnancement du processeur. Les critères les plus souvent utilisés sont :
Critères D’ordonnancement
❖ Les critères les plus souvent utilisés sont :
➢Capacité de traitement : est la quantité de processus terminés par unité de temps
➢Temps de résidence : est le temps passé par le processus dans le système. C'est la somme du temps
d'exécution (temps CPU consommé) et du temps passé dans les différentes files (file des processus prêts, files
des processus bloqués). Soient te: le temps d'entrée du processus dans le système et ts: le temps de sortie du
processus.
Temps de résidence = ts – te
➢Temps d’attente : est le temps passé à attendre dans les différentes files d’attente (prêts et bloqués). Soient
tattCPU : le temps d’attente dans les files prêts et tbloqués: le temps d’attente dans les files bloqués.
Temps d’attente = tattCPU + tbloqués
Critères D’ordonnancement
❖ Les critères les plus souvent utilisés sont:
➢Temps de réponse : est le temps passé dans la file d’attente des processus prêts avant la première
exécution. Soient : te: le temps d’entrée (instant d’arrivé) à la file et tdex: le temps de début
d’exécution.
Temps de réponse = tdex – t
➢ Le taux d'utilisation du processeur : doit être le plus élevé possible (100%) pour éviter les moments
où le processeur ne fait rien alors qu’il existe dans le système des processus qui n’ont pas terminé
leur travaux. Il est calculé comme suit:
Critères D’ordonnancement
❖ Les critères les plus souvent utilisés sont:
➢ tCPUi: le temps CPU consommé par le processus i,
➢ tep: temps d’entrée (instant d’arrivé) du premier processus,
➢ tsd: temps sortie du dernier processus.
Stratégies D’ordonnancement
❖On peut classer les politiques ou stratégies d'ordonnancement en deux classes:
➢ Non-préemptif (Sans réquisition) : L'exécution du processus en cours ne peut jamais être interrompue
au profit d'un autre processus. Ce sont les algorithmes utilisés dans les premiers systèmes BATCH.
➢ Préemptif (Avec réquisition) : L'exécution du processus en cours peut être interrompue au profit d'un
autre processus plus prioritaire (ou plus urgent) ou de même priorité. Ce type d'algorithmes favorise les
processus courts et assure, dans les systèmes interactifs, un temps de réponse assez bref.
Algorithmes D’ordonnancement
L’algorithme du Premier Arrivé Premier Servi (First Come First Served, FCFS) :
❖ C’est un algorithme sans réquisition qui permet d’allouer le processeur au premier processus qui le
demande. Le processeur ne peut être retiré au processus que s’il le libère volontairement.
❖ L’implémentation de la politique FCFS est facilement gérée avec une file d’attente FIFO (First In First Out).
Quand un processus entre dans la file d’attente des processus prêts, son bloc de contrôle (PCB) est
enchaînée à la queue de la file d’attente. Quand le processeur devient libre, il est alloué au processus en
tête de la file d’attente.
Algorithmes D’ordonnancement
L’algorithme du Premier Arrivé Premier Servi (First Come First Served, FCFS) :
Exemple : Trois processus P1, P2 et P3 arrivent dans cet ordre au système. Leurs durées d’exécution sont
respectivement : 24, 3, 3 unités de temps. Calculer le temps moyen d’attente.
❖ Le temps d’attente est égal à 0 pour le processus P1, 24 pour le processus P2 et 27 pour le processus P3.
Le temps d’attente moyen est égal à : (0+24+27)/3, soit 17 unités de temps.
Algorithmes D’ordonnancement
L’algorithme du Premier Arrivé Premier Servi (First Come First Served, FCFS) :
Exemple : Si les processus étaient arrivés dans l’ordre P2, P3 et P1, les résultats seraient
différents :
❖ Le temps moyen d’attente serait : (0+3+6)/3=3 unités.
❖Ainsi le temps moyen d’attente avec une politique FCFS n’est généralement pas minimal et peut varier
substantiellement si les durées d’exécution des processus varient beaucoup.
Algorithmes D’ordonnancement
L’algorithme du Premier Arrivé Premier Servi (First Come First Served, FCFS) :
❖L’algorithme FCFS tend à pénaliser les travaux courts : il n’effectue pas de réquisition; c’est à dire qu’une
fois que le processeur a été alloué à un processus, celui-ci le réquisitionne jusqu’à ce qu’il termine ou qu’il
se bloque (attente d’un évènement ou d’E/S).
❖ L’algorithme FCFS n’est pas recommandé pour les systèmes à temps partagé, où il est important que
l’utilisateur obtienne le processeur à des intervalles réguliers. Il peut paraître désastreux de permettre
qu’un processus garde le processeur pendant une période étendue.
Algorithmes D’ordonnancement
L’algorithme du Plus Court d’abord (Shortest Job First, SJF) :
❖ Cet algorithme affecte le processeur au processus possédant le temps d’exécution le plus court. Si
plusieurs processus ont la même durée, une politique FIFO sera alors utilisée pour les départager.
➢ Exemple: On soumet au système quatre processus P1, P2, P3 et P4 dont les durées d’exécution sont
données par le tableau suivant.
Algorithmes D’ordonnancement
L’algorithme du Plus Court d’abord (Shortest Job First, SJF) :
➢Le temps moyen d’attente est = (0+3+9+16)/4=7. Alors que si on avait choisi une politique FCFS, le
temps moyen serait de : 10.25 unités de temps.
➢ Il a été prouvé que l’algorithme SJF est optimal dans le temps dans le sens qu’il obtient le temps
d’attente le plus court pour un ensemble de processus donné. Toutefois, cet algorithme est difficile à
implémenter pour une raison simple : Comment peut-on connaître le temps d’exécution d’un processus
à l’avance ?
Algorithmes D’ordonnancement
L’algorithme du Tourniquet (Round Robin, RR) :
❖ Cet algorithme a été conçu pour des systèmes à temps partagé. Il alloue le processeur aux processus à tour de
rôle, pendant une tranche de temps appelée quantum.
❖ Le processeur est alloué au premier processus de la file des processus prêts pendant un quantum de temps;
❖ Si le processus n'a pas terminé son exécution, il est recyclé dans la file des processus prêts.
❖ Le processeur est alloué à un autre processus :
➢ A la fin du quantum de temps interruption horloge,
➢ Si le processus actif se bloque attente de ressource physique ou logique,
➢ Fin d’exécution du processus (fin normale ou erreur ).
Algorithmes D’ordonnancement
L’algorithme du Tourniquet (Round Robin, RR) :
Exemple : On dispose de 3 processus P1, P2 et P3 ayant comme durée d’exécution, respectivement 24, 3
et 3 ms. Calculer le temps moyen d’attente en utilisant un algorithme Round Robin, avec un quantum de 4
ms.
➢ Le temps moyen d’attente est de : (6+4+7)/3 = 17/3 = 5.66 m.
Algorithmes D’ordonnancement
L’algorithme du Tourniquet (Round Robin, RR) :
❖ La performance de l’algorithme de RR dépend largement de la taille du quantum:
➢ Si le quantum est très grand, la politique RR serait similaire à celle du FCFS.
➢ Si le quantum est très petit, la méthode RR surchargerait le système par de fréquentes commutations
de contexte.
❖Cependant, le quantum doit être choisi pour permettre un bon partage du processeur (entre 10 à 50 ms):
Chacun des utilisateurs aurait l’impression.
Algorithmes D’ordonnancement
L’algorithme du Tourniquet (Round Robin, RR) :
Exemple : On dispose d’un processus P dont le temps d’exécution est de 10 ms. Calculer le
nombre de commutations de contexte nécessaires pour un quantum égal respectivement à : 12,
6 et 1.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec priorité :
❖ La priorité est une valeur numérique (positive ou négative) associée à un processus et permettant de le
classer selon son importance dans le système.
❖Les priorités des processus peuvent être définies en fonction de plusieurs paramètres : type de processus,
limites de temps, limites mémoires …..
❖Deux types de priorités :
➢ Priorité statique: attribuée au processus à sa création et reste jusqu’à la fin de l’exécution du processus.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec priorité :
➢Priorité dynamique: à la création d’un processus , on attribut une priorité initiale; ensuite cette
priorité peut évoluer, par exemple, en fonction du temps d’exécution, du nombre d’E/S, du nombre de
ressources consommées, …
❖ Cet algorithme associe à chaque processus une priorité, et le processeur sera affecté au processus de plus
haute priorité.
❖L'exécution du processus en cours peut être interrompue au profit d'un autre processus plus prioritaire
(c’est un algorithme préemptif ou avec réquisition).
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec priorité :
Exemple : On dispose de 5 processus ayant des priorités différentes (les priorités varient de 0 à 255; (0 la
plus faible priorité et 255 la plus forte priorité), comme le montre ce tableau :
Le temps moyen d’attente est = (0+1+6+16+18)/5=8.2 unités de temps.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec priorité :
❖ Une situation de blocage (famine) peut survenir si les processus de basse priorité attendent indéfiniment
le processeur, alors que des processus de haute priorité continuent à affluer.
❖ Pour éviter une telle situation, on peut utiliser la technique dite du vieillissement. Elle consiste à
incrémenter graduellement la priorité des processus attendant dans le système pendant longtemps. Par
exemple, nous pourrions incrémenter de 1 la priorité d’un processus en attente toutes les 15 minutes. En
fin de compte, même un processus ayant une priorité initiale égale à 0 aurait la plus haute priorité dans le
système et serait exécuté.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec priorité :
❖ L’implémentation de cette politique peut être gérée avec une seule file d’attente avec priorité (Le
processus le plus prioritaire est en tête de la file) ou avec plusieurs files d’attente des processus prêts.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveau :
❖Une autre classe d’algorithmes d’ordonnancement a été développée pour des situations où on peut
facilement classer les processus dans des groupes différents.
❖ Cet algorithme découpe la file d’attente des processus prêts en plusieurs files d’attentes séparées.
1. Définir des classes de processus.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveau :
2. Associer à chaque classe son propre algorithme d’ordonnancement.
3. Définir un algorithme d’ordonnancement entre les classes.
➢ Cas 1: Affecter des tranches de temps aux classes. Chaque file d’attente obtient une certaine partie du
temps processeur, lequel doit s’ordonnancer entre les différents processus qui la composent.
➢ Cas 2: Chaque classe est absolument prioritaire par rapport aux autres classes de niveau inférieur (C1
plus prioritaire, Cn moins prioritaire). Le processeur est alloué aux processus de la classe la plus
prioritaire; On ne change de classe que si la classe la plus prioritaire est vide.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveau :
Exemple 1: On peut diviser les processus en deux classes: les processus de premier plan (interactifs) et les
processus d’arrière plan qui possèdent des besoins différents en ce qui concerne le temps de réponse et ils
pourraient donc devoir être ordonnancé différemment:
➢ les processus de premier plan peuvent être prioritaires par rapport aux processus d’arrière plan.
➢ Ou bien, on peut attribuer 80% du temps processeur aux processus de premier plan et 20% aux
processus d’arrière plan.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveau :
Exemple 2: On peut aussi diviser les processus en quatre classes (des processus les plus prioritaires aux
processus les moins prioritaires): les processus systèmes, interactifs, batch et utilisateurs.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveau :
Exemple 2: aucun processus de la file d’attente des processus batch ne pourra s’exécuter à
moins que les files d’attente des processus système et interactifs ne soient toutes vides. De plus,
si un processus interactif arrive au système, alors qu’un processus batch est en train de
s’exécuter, celui-ci doit être interrompu.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux :
❖ Normalement, dans un algorithme avec des files d’attente multiniveaux, les processus sont assignés en
permanence à une file d’attente dès qu’ils rentrent dans le système. Les processus ne se déplacent pas
entre les files d’attente. Cette organisation possède l’avantage d’une basse surcharge due à
l’ordonnancement, mais elle manque de souplesse.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
❖ Avec cet algorithme (appelé aussi avec plusieurs niveaux dépendants), un processus peut basculer entre
des files. Ceci est réalisé dans le but d'isoler les processus longs d'une part, et de relancer les processus de
faible priorité d'autre part.
❖ Cet algorithme utilise N files d’attente avec des règles suivantes:
➢ Un processus qui entre dans le système est mis dans la première file.
➢ Après avoir reçu une tranche de temps, il est mis dans la deuxième file.
➢ Après chaque tranche reçue, il passe dans la file suivante.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
➢ L’algorithme choisit le premier processus de la première file non vide ([Link] processus de la file « i »
n’est servi que si toutes les files de rang inférieur à « i » sont vides).
➢ Les processus de la dernière file sont recyclés dans la même file.
❖ Il permet de favoriser les petits travaux, sans avoir besoin de savoir à l’avance combien de temps CPU
ceux-ci vont utiliser.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
Exemple 1 :
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
Exemple 1 :
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
L’algorithme avec quantum variable :
❖ Pour éviter qu'il y ait beaucoup de commutations pour les processus longs, il est préférable d'allouer un
plus grand quantum à ces processus. Lorsqu'un processus passe à l'état élu : Pour la première fois, le
processeur lui est alloué pendant un quantum. Pour la seconde fois, le processeur lui est alloué pendant 2
quantum... Pour la 𝑛𝑖è𝑚𝑒 fois, le processeur lui est alloué pendant 2(𝑛−1) quantum.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
L’algorithme avec quantum variable :
➢ Chaque processus a une priorité. Cette dernière dépend du nombre de quantum qui lui sera
alloué lors de sa prochaine activation. Les processus dont le nombre de quantum est le plus
petit sont les plus prioritaires. Les processus prêts sont répartis selon leur priorité dans des files
(FIFO). D'abord on fait l'élection du processus le plus prioritaire qui se trouve en tête de file.
Lorsque l'exécution d'un processus est suspendue pour la nième fois, sa priorité est recalculée
2𝑛 puis il est inséré à la queue de la file appropriée.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
L’algorithme avec quantum variable :
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
Exemple 02 : L’algorithme avec quantum variable :
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
Exemple 02 : L’algorithme avec quantum variable :
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
L’algorithme avec quantum variable :
❖ Un processus qui descend de plus en plus dans les files à priorité s'exécute de moins en moins
fréquemment et favorise ainsi les processus courts en mode interactif. Pour ne pas défavoriser
un processus qui s'était exécuté pendant assez longtemps avant de devenir interactif, on peut lui
attribuer la plus haute priorité en le réinsérant dans la première file.
Algorithmes D’ordonnancement
L’algorithme d’ordonnancement avec files d’attente multiniveaux rétroactives :
L’algorithme avec quantum variable :
Algorithmes D’ordonnancement