Utilisateur:Topeil/Principes des systèmes d'exploitation/Ordonnanceur

Ordonnanceur

Fonction

Pour que différents programmes puissent cohabiter sur un ou plusieurs processeurs, il existe plusieurs solutions:

soit ils coopèrent pour s'exécuter, on parle alors de multitâche coopératif. Cette solution ne peut cependant pas être mise en œuvre si l'un des programmes est potentiellement malicieux, par exemple si plusieurs utilisateurs sont autorisés.
soit un programme central décide de l’ordre et du temps de leurs accès au processeur. On parle alors de multitâche préemptif. C'est la solution retenue dans presque tous les systèmes modernes. Ce programme est appelé l'ordonnanceur — "scheduler" en Anglais.

Il a pour fonction de laisser tour à tour chaque programme avoir accès au processeur. On a besoin qu’il soit suffisamment rapide, de manière à ce que l'ordinateur fasse toujours quelque chose d'utile plutôt que d'ordonnancer les processus, et que le ou les processeurs soient les plus utilisés possible — pour ne pas perdre de temps.

Selon l’utilisation de l'ordinateur, les contraintes seront très variables : on recherche de la réactivité pour un ordinateur personnel, et donc des commutations fréquentes entre processus ; pour un serveur, de la rapidité, donc moins de commutations ; pour du calcul intensif, on réduira encore leur nombre, car tout ce qui importe est le résultat final.

Implémentation

Selon les systèmes, il est possible de trouver de multiples implémentations, de la plus simple à la plus complexe. Généralement, on maintient plusieurs ensembles de processus :

Ceux qui sont en cours d'exécution sur le/les processeurs
Ceux qui sont bloqués ou attendent une information

Des algorithmes basiques

Pour un système mono-processeur, on peut imaginer une méthode naïve, utilisant une file : les processus sont simplement autorisés à se lancer tour à tour pour un temps déterminé, en prenant à chaque fois le premier processus de la file, puis en le plaçant à la fin une fois son tour terminé : c’est l'algorithme Round Robin. On peut aussi lui laisser l'usage du processeur jusqu'à ce qu’il ait terminé : c’est l'algorithme FIFO.

Ces algorithmes ont un inconvénient majeur : ils n'attribuent pas de priorité aux processus. Un utilisateur lançant beaucoup de processus, ou un processus se dupliquant, pourra monopoliser le processeur. Dans le cas de l'ordonnancement en FIFO, un unique processus peut même y suffire s'il ne se termine pas.
En revanche, ils sont simples à implémenter, rapides, et peuvent donc être utilisés dans des systèmes devant s'exécuter en temps réel.

Exécuter les tâches les plus courtes en premier

L'ordonnanceur doit faire en sorte que les tâches paraissent les plus rapides possibles : une technique efficace est donc d'exécuter en premier celles qui sont supposées être les plus courtes. Cela concernera les aussi bien des processus lancés depuis peu, supposés se terminer vite, que ceux faisant beaucoup d'entrées/sorties et qui passent donc la majeure partie de leur temps à attendre que des données leur parviennent. Pour cela, on peut utiliser plusieurs groupes de processus, selon la probabilité qu’ils s'arrêtent rapidement ou non : tous les processus commencent dans le premier groupe, puis passent au groupe suivant s'ils se sont exécutés suffisamment longtemps sans s'arrêter.

Répartir équitablement le temps d'exécution

De nombreux systèmes sont capables d'accueillir plusieurs utilisateurs. Pour éviter que l'un deux monopolise le processeur, un partage équitable est nécessaire. Une solution simple est d’utiliser un ordonnancement classique en "round-robin" entre les utilisateurs, puis une méthode quelconque entre les processus d'un même utilisateur.

Le problème des ordinateurs multiprocesseurs

Jusqu'ici, on a considéré qu’il n'y avait qu'un seul processeur, qui exécutait une seule série d'instructions à la fois. Malheureusement, les ordinateurs actuels ne sont pas si simples : les ordinateurs grand public peuvent compter plusieurs processeurs depuis déjà quelques années, et des calculateurs spécialisés peuvent en compter des milliers. Pour en tirer parti efficacement, les algorithmes du système doivent être modifiés en profondeur, entre autres l'ordonnanceur. Lorsqu’il y a plusieurs processeurs, il devient possible d'exécuter plusieurs processus en même temps. Cependant, on rencontre d'autres problèmes, entre autres concernant la mémoire, et l'ordonnanceur doit en tenir compte pour être efficace. Ce sujet est traité dans la partie sur les systèmes multiprocesseurs.

Caractéristiques d'un ordonnanceur avancé

Des ordonnanceurs plus complexes peuvent être capables :

De gérer des priorités
De créer des groupes de processus (par exemple selon l'utilisateur)
Impacter le moins possible le temps d'exécution, bien sûr.