Ordonnancement du CPU
Concepts de Base
Critères d’Ordonnancement
Algorithmes d’Ordonnancement
Ordonnancement Multi-Processeur
Ordonnancement Temps Réel
Ordonnancement de Threads
Exemples d’OSs
Ordonnancement de Threads Java
Evaluation d’Algorithmes
Systèmes d’exploitation 6.1 URD L2 2005
Concepts de Base
Utilisation CPU maximale obtenue avec la multiprogrammation
Cycle CPU–E/S – Le déroulement d’un processus consiste en
une suite de cycles d’exécution CPU et d’attente d’E/S
Distribution cycles CPU
Systèmes d’exploitation 6.2 URD L2 2005
Séquence d’Alternance de Cycles CPU et E/S
Systèmes d’exploitation 6.3 URD L2 2005
Histogramme des Temps de Cycles CPU
Systèmes d’exploitation 6.4 URD L2 2005
Ordonnanceur CPU
Choisit parmi les processus prêts en mémoire, et alloue la CPU
à l’un d’eux
Les décisions d’ordonnancement de la CPU sont pris lors:
1. Du changement d’état “exécution” à “en attente”
2. Du changement d’état de “exécution” à “prêt”
3. Du changement d’état de “en attente” à “prêt”
4. De la terminaison d’un processus
L’ordonnancement dans les cas 1 et 4 est non préemptif
Pour les autres cas, c’est préemptif
Systèmes d’exploitation 6.5 URD L2 2005
Dispatcheur
Le dispatcheur donne le contrôle de la CPU au processus choisi
par l’ordonnanceur à court terme; ceci comprend:
Commutation de contexte
Passer en mode utilisateur
Sauter au bon endroit dans le programme pour le relancer
Latence du Dispatcheur – temps pris par le dispatcheur pour
stopper un processus et (re)lancer un autre
Systèmes d’exploitation 6.6 URD L2 2005
Critères d’Ordonnancement
Utilisation de la CPU – utiliser la CPU le maximum
possible
Débit (Throughput) – # de processus qui terminent leur
exécution par unité de temps
Temps de rotation (Turnaround time) – le temps depuis le
lancement du processus jusqu’à sa terminaison (les
attentes incluses)
Temps d’attente – temps d’un processus dans la file
d’attente des processus prêts
Temps de réponse – temps mis entre une requête émise
et la première réponse, pas la sortie (pour les
environnements à temps partagé)
Systèmes d’exploitation 6.7 URD L2 2005
Critères d’Optimisation
Utilisation maximale du CPU
Débit maximum
Temps de rotation minimal
Temps d’attente minimal
Temps de réponse minimal
Systèmes d’exploitation 6.8 URD L2 2005
Ordonnancement First-Come, First-Served
(FCFS)
Processus Tps CPU
P1 24
P2 3
P3 3
Supposons que les processus arrivent dans l’ordre suivant: P ,
1
P2 , P3 Le diagramme de Gantt correspondant est:
P1 P2 P3
0 24 27 30
Temps d‘attente de P = 0; P = 24; P = 27
1 2 3
Temps d’attente moyen: (0 + 24 + 27)/3 = 17
Systèmes d’exploitation 6.9 URD L2 2005
Ordonnancement FCFS (Cont.)
Supposons que les processus arrivent dans l’ordre suivant
P2 , P3 , P1
Le diagramme de Gantt serait alors:
P2 P3 P1
0 3 6 30
Temps d’attente de P1 = 6; P2 = 0; P3 = 3
Temps d’attente moyen: (6 + 0 + 3)/3 = 3
Meilleur résultat que le cas précédent
Effet convoi un processus court derrière un processus long
Systèmes d’exploitation 6.10 URD L2 2005
Ordonnancement Shortest-Job-First (SJF)
Associer à chaque processus son prochain temps d’utilisation du
CPU. Utiliser ces temps pour choisir le processus avec le
temps le plus petit
Deux schémas:
Non préemptif – dès que le CPU est donné à un processus, ce
dernier ne peut être interrompu avant la fin de son temps CPU
préemptif – si un nouveau processus débarque avec un temps CPU
plus petit que le reste du temps CPU du processus courant, on
commute vers le nouveau processus. Ce schéma est connu sous le
nom de Shortest-Remaining-Time-First (SRTF)
SJF est optimal – donne un temps moyen minimal pour un
ensemble de processus donnés
Systèmes d’exploitation 6.11 URD L2 2005
Exemple de SJF Non-Préemptif
ProcessusTps d’ArrivéeTps CPU
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (non préemptif)
P1 P3 P2 P4
0 3 7 8 12 16
Temps moyen d’attente = (0 + 6 + 3 + 7)/4 = 4
Systèmes d’exploitation 6.12 URD L2 2005
Exemple de SJF Préemptif
ProcessusTps d’ArrivéeTps CPU
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (préemptif)
P1 P2 P3 P2 P4 P1
0 2 4 5 7 11 16
Temps d’Attente Moyen = (9 + 1 + 0 +2)/4 = 3
Systèmes d’exploitation 6.13 URD L2 2005
Déterminer la Longueur du Prochain Temps
CPU
On peut juste estimer le temps
Peut être fait à partir des temps d’exécution précédents, utilisant
une moyenne exponentielle
1. t n actual lenght of n th CPU burst
2. n 1 predicted value for the next CPU burst
3. , 0 1
4. Define : n 1 t n 1 n .
Systèmes d’exploitation 6.14 URD L2 2005
Prédiction de la Longueur du Prochain Temps
CPU
Systèmes d’exploitation 6.15 URD L2 2005
Exemples d’une Moyenne Exponentielle
=0
n+1 = n
Passé récent ne compte pas
=1
n+1 = tn
Seulement le dernier temps CPU compte
L’expansion de la formule donne:
n+1 = tn+(1 - ) tn -1 + …
+(1 - )j tn -1 + …
+(1 - )n=1 tn 0
Comme et (1 - ) sont plus petits ou égaux que 1, chaque
terme successif a un poids plus petit que son prédécesseur
Systèmes d’exploitation 6.16 URD L2 2005
Ordonnancement avec Priorité
Une priorité (nombre entier) est associée à chaque processus
Le CPU est alloué au processus à la priorité la plus grande (le
plus petit entier la plus grande priorité)
Préemptif
Non préemptif
SJF est un ordonnancement à priorité où la priorité correspond
au temps CPU suivant
Problème Famine – processus à faible priorité peuvent ne
jamais s’exécuter
Solution Vieillissement – avec le temps, incrémenter la priorité
des processus en attente
Systèmes d’exploitation 6.17 URD L2 2005
Tourniquet/Round Robin (RR)
Chaque processus se voit alloué le CPU pour un temps limité
(quantum), en général 10-100 milliseconds. A la fin de ce
temps, le processus est arrêté et ajouté à la fin de la file
d’attente des processus prêts.
Si n processus sont dans la file d’attente des processus prêts et
le quantum est q, alors chaque processus reçoit 1/n du temps
CPU en parties de q unités. Aucun processus attend plus de (n-
1)q.
Performance
q large FIFO
q petit q doit être large comparé au temps de commutation de
tâche, sinon l’overhead est trop grand
Systèmes d’exploitation 6.18 URD L2 2005
Exemple de RR avec Q = 20
ProcessusTemps CPU
P1 53
P2 17
P3 68
P4 24
Le diagramme de Gantt est:
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
Typiquement, une moyenne de temps de rotation plus grande
que SJF, mais un meilleur temps de réponse
Systèmes d’exploitation 6.19 URD L2 2005
Quantum et Temps de Commutation de
Contexte
Systèmes d’exploitation 6.20 URD L2 2005
Temps de Rotation Varie avec le Quantum
Systèmes d’exploitation 6.21 URD L2 2005
File Multiniveaux
La file d’attente est partagée en files séparées:
premier plan/foreground (interactif)
arrière plan/background (batch)
Chaque file a sa propre politique d’ordonnancement
foreground – RR
background – FCFS
Un ordonnancement inter-files doit exister
Ordonnancement à priorité fixe; (i.e., servir tous les processus de la
file foreground puis ceux de la file background). Possibilité de
famine.
Time slice – chaque file obtient une partie du temps CPU qu’elle
utilise pour ordonnancer ces processus en attente; i.e., 80% pour la
file foreground en RR et 20% pour la file background en FCFS
Systèmes d’exploitation 6.22 URD L2 2005
Ordonnancement à Files Multiniveau
Systèmes d’exploitation 6.23 URD L2 2005
Ordonnancement avec Files Multiniveau à
Retour
Un processus peut changer de file; le vieillissement peut être
implémenté de la sorte
Un ordonnanceur de files multiniveaux à retour est défini suivant
les paramètres suivants:
Nombre de files
Politique d’ordonnancement pour chaque file
Méthode déterminant la promotion d’un processus vers une file
d’attente plus prioritaire
Méthode déterminant le passage d’un processus dans une file
moins prioritaire
Méthode déterminant dans quelle file placer un nouveau service
Systèmes d’exploitation 6.24 URD L2 2005
Exemple de File Multiniveaux à Retour
Trois files:
Q0 – quantum de 8 millisecondes
Q1 – quantum de 16 millisecondes
Q2 – FCFS
Ordonnancement
Un nouveau processus est placé dans Q0 au début; à sa première
exécution, il reçoit 8 millisecondes. S’il ne termine pas son
exécution, il est replacé dans Q1.
Si un processus de la file Q1 est servi (16 msec) et ne se termine
pas, il est replacé dans Q2.
Systèmes d’exploitation 6.25 URD L2 2005
Files avec Multiniveaux à Retour
Systèmes d’exploitation 6.26 URD L2 2005
Ordonnancement Multiprocesseur
L’ordonnancement CPU est plus complexe
Processeurs homogènes dans un multiprocesseur
Partage de charge
Multitraîtement asymétrique – seulement un processeur accède
aux structures de données systèmes, supprimant le besoin de
partage de données
Systèmes d’exploitation 6.27 URD L2 2005
Ordonnancement Temps Réel
Systèmes temps réel durs – exige la garantie qu’un processus
soit terminée au bout d’un temps bien défini
Systèmes temps réel souples – exige que les processus plus
prioritaires soient traîtés avant ceux de moins haute priorité
Systèmes d’exploitation 6.28 URD L2 2005
Latence du Dispatcheur
Systèmes d’exploitation 6.29 URD L2 2005
Evaluation des Algorithmes
Modèles déterministes – prennent un échantillon et définissent
les performances pour cet échantillon
Modèles de files d’attente
Implémentation
Systèmes d’exploitation 6.30 URD L2 2005
Evaluation des Ordonnanceurs de CPU par
Simulation
Systèmes d’exploitation 6.31 URD L2 2005
Ordonnancement Solaris 2
Systèmes d’exploitation 6.32 URD L2 2005
Priorités Windows XP
Systèmes d’exploitation 6.33 URD L2 2005
Ordonnancement Linux
Deux algorithmes: temps partagé et temps réel
Temps partagé
Priorité basée sur des crédits – le processus avec le plus de crédits
est choisi
Crédit soustrait à l’occurrence de l’interruption horloge
Quand crédit = 0, un autre processus est choisi
Quand tous les processus ont un crédit = 0, on les créédite
Basé sur des facteurs de priorité et de leur histoire
Temps Réel
Temps réel souple
Posix.1b – deux classes
FCFS and RR
Le processus à la priorité la plus haute s’exécute en premier
Systèmes d’exploitation 6.34 URD L2 2005
Ordonnancement de Thread
Ordonnancement Local – Comment les bibliothèques de threads
décident quel thread associé à un LWP disponible
Ordonnancement Global – Comment le noyau décide quel
thread exécuter
Systèmes d’exploitation 6.35 URD L2 2005
API d’Ordonnancement de Pthread
#include <pthread.h>
#include <stdio.h>
#define NUM THREADS 5
int main(int argc, char *argv[])
{
int i;
pthread t tid[NUM THREADS];
pthread attr t attr;
/* get the default attributes */
pthread attr init(&attr);
/* set the scheduling algorithm to PROCESS or SYSTEM */
pthread attr setscope(&attr, PTHREAD SCOPE SYSTEM);
/* set the scheduling policy - FIFO, RT, or OTHER */
pthread attr setschedpolicy(&attr, SCHED OTHER);
/* create the threads */
for (i = 0; i < NUM THREADS; i++)
pthread create(&tid[i],&attr,runner,NULL);
Systèmes d’exploitation 6.36 URD L2 2005
Pthread Scheduling API
/* now join on each thread */
for (i = 0; i < NUM THREADS; i++)
pthread join(tid[i], NULL);
}
/* Each thread will begin control in this function
*/
void *runner(void *param)
{
printf("I am a thread\n");
pthread exit(0);
}
Systèmes d’exploitation 6.37 URD L2 2005
Ordonnancement des Java Threads
JVM utilise un algorithme d’ordonnancement préemptif, à base
de priorités
La file FIFO est utilisée en cas de plusieurs threads à priorités
égales
Systèmes d’exploitation 6.38 URD L2 2005
Ordonnanacement Java Thread (cont)
JVM ordonnance un thread à exécuter quand:
1. Le thread actuel en exécution sort de l’état Exécutable
2. Un thread à priorité supérieure entre dans l’état Exécutable
* Note – la JVM ne spécifie pas si les threads recoivent des
tranches de temps ou pas
Systèmes d’exploitation 6.39 URD L2 2005
Tranches de Temps
Comme la JVM ne garantit pas des tranches de temps, la méthode
yield() peut-être utilisée:
while (true) {
// exécuter des instructions CPU
...
[Link]();
}
Le thread actuel donne la main à un autre thread à priorité égale
Systèmes d’exploitation 6.40 URD L2 2005
Priorités Threads
Priorité Commentaire
Thread.MIN_PRIORITY Priorité de Thread
Minimale
Thread.MAX_PRIORITY Priorité de Thread Maximale
Thread.NORM_PRIORITY Priorité de Thread par défaut
Les priorités peuvent être modifiées avec la méthode
setPriority():
setPriority(Thread.NORM_PRIORITY + 2);
Systèmes d’exploitation 6.41 URD L2 2005
