Un article de LaPageDuJour.

Sommaire 1 Introduction 2 Analyse de cas 2.1 Noyau Linux 2.1.1 Priorité de processus 2.1.2 Charge d'un système 2.1.3 L'attente des E/S 2.2 Noyaux Microsoft 2.3 La notion de temps-réel 2.4 Système de fichier XFS 2.5 Limitation de temps CPU (cpulimit) 3 Derrière tout ça 3.1 L'idée du multi-tâche 3.2 Alternative 4 La clé de l'ordonnancement 4.1 Connaitre ses besoins globaux 4.2 Déterminer les goulots d'étranglements 4.3 Découper les tâches 4.4 Choisir une méthode de gestion des priorité 4.5 Dans un système d'exploitation 5 Méthodes concrètes d'ordonnancement 5.1 Programme multi-threadé 5.1.1 Vision générale 5.1.2 Risques 5.2 Processus 5.3 Ordonnancement des systèmes "maison"

[modifier] Introduction

Quand on pense à l'ordonnancement de tâche, on pense systématiquement aux systèmes multi-taches. C'est en effet la plus grande et la meilleur applications. Mais ce n'est pas la seule.

Le but final de l'ordonnancement est : Faire plus avec moins, traiter de lourdes tâches et garder une bonne disponibilité pour d'autres tâches.

[modifier] Analyse de cas

[modifier] Noyau Linux

C'est un exemple qui illustre des problématiques multi-tâches et les méthodes utilisées pour les résoudres.

[modifier] Priorité de processus

Depuis sa version 2.4 Linux a traitement des priorité entre processus simple et efficace. Chaque processus se voit attribué une priorité allant de 0 à 99 ainsi qu'un nombre représentant sa priorité ponctuelle dans la file d'attente des processus. Celui qui a le plus petit nombre de priorité ponctuelle est exécuté pendant un certain temps (0.250 à 10ms) et se voit ensuite incrémenté de sa priorité.

Ainsi, un processus ayant une priorité "0" est un processus temps-réel. A chaque fois qu'il sera exécuté, s'il ne rend pas la main au processeur (dans le cas d'un accès E/S par exemple) ou qu'il ne se met pas à dormir "sleep( <secondes> )", sa priorité ne sera pas incrémenté. Donc il sera le seul processus toujours en tête de liste pour l'accès au processeur.

Ce type d'ordonnancement permet au processeur de répartir son travail selon les besoins que l'on a de lui.

[modifier] Charge d'un système

La charge d'un système Linux est un paramètre souvent mal compris. Elle représente la moyenne du nombre de processus qui sont éxécutés ou en attente du processeur à un moment donné.

Une charge de 1 signifie donc qu'à priori le processeur est utilisé à 100% par un processus. Si c'est le cas et que d'autres processus souhaitent accèder au processeur, la charge augmentera ponctuellement à 2, on aura donc une charge légèrement supérieure à 1.

Un système peut toujours être considéré comme sain lorsque sa charge est inférieure à 1. Par contre, il n'est pas forcément surchargé si sa charge est supérieure à 1. En effet, tout dépend de la façon dont est organisée le système.

Si par exemple vous avez décidé de mettre en place deux processus à la suite reliés par un tube (pipe) pour faire du traitement de données, s'ils ont à peu près la même consommation de CPU, ils se retrouveront souvent à nécessiter le processeur. Votre charge devrait donc dépasser 2 car vous avez en continu 2 processus qui souhaitent accèder au processeur. Pourtant, on ne peut pas dire que votre système soit surchargé, il tourne juste à pleine vitesse.

Dans ce cas ci, changer la priorité d'un processus par rapport à un autre ne diminuerait pas non plus la charge car dans le cas d'un tube, les processus sont entièrement reliés, le traitement de l'un attend et fait attendre le traitement de l'autre.

[modifier] L'attente des E/S

Les entrées sorties prennent toujours du temps. La meilleure solution pour tirer parti à 100% du CPU est d'exécuter d'autres processus lorsqu'un processus est en attente du disque dur. C'est ce que font tous les systèmes multi-tâches. Ainsi, même un processus temps-réel donne l'accès au CPU aux autres processus lorsqu'il accède au disque dur.

Mais ceci pose une nouvelle problématique : Si vous avez un processus en haute-priorité qui souhaite accèder de façon fréquente mais rapide au disque dur et que vous avez un processus en faible priorité qui va accèder fréquemment au disque dur (par exemple pour faire une copie), vous allez vous trouver dans une situation gênante. En effet, le processus en faible priorité va accaparer le disque dur et le processus haute priorité va donc se retrouver à attendre le disque dur. Et comme le processus haute priorité attend le disque dur il va laisser d'autant plus de temps au processus faible priorité pour accaparer ce même disque dur. Le processus haute-priorité sera donc largement ralenti.

Pour régler ce genre de problème, depuis les noyau de 2.6.18, Linux intègre un "ordonnanceur d'entrée sortie" basé sur la priorité des processus, c'est à dire un système de gestion des priorités d'accès au disque dur qui se calque sur le fonctionnement du noyau. C'est à dire qu'un processus de priorité 0 aura un accès immédiat au disque dur alors qu'un processus de priorité 99 se retrouvera en fin de queue d'attente. Dans ce cas ci, les processus réalisant de fréquentes opérations sur le disque dur ne ralentissent presque pas les processus temps réel (un peu quand même car les têtes du disque dur vont passer d'un endroit à un autre régulièrement).

Notez que cette option n'est pas activée par défaut, elle peut l'être au moyen de la commande :

echo cfq > /sys/block/sda/queue/scheduler

[modifier] Noyaux Microsoft

Il exite maintenant une ribanbelles de noyaux Microsoft. Deux sont particulièrement intéressants :

• Windows CE car il permet de faire du temps réel, mais il ne gère pas les priorité E/S. Cependant ce système fonctionne généralement sur de la mémoire vive donc les temps d'accès sont négligeables.
• Windows NT 6 (Vista), car il intègre une gestion des priorité d'accès aux processus, aux entrées/sorties (disque dur), et à la mémoire vive (RAM).

Il faut relativiser l'évolution de l'accès à la RAM, en effet, ce n'est que très rarement un facteur bloquant. D'ailleurs, dans Vista, cette gestion de priorité se fait (seulement) sur 3 niveau.

[modifier] La notion de temps-réel

Un système temps-réel est un système qui est capable de réaliser un traitement dans une intervalle de temps défini (sans dépasser). La notion de temps-réel ne doit donc pas être limitée à la définition classique d'un système d'exploitation, c'est à dire comme étant capable d'exécuter un seul programme par dessus tous les autres.

Un système (éventuellement d'exploitation) temps-réel est en fait un système qui prend en compte ses délais et qui offre un moyen de les maîtriser. Windows Mobile (qui repose sur Windows CE) appliqué aux smartphones est un parfait exemple de système temps-réel (il utilise une gestion de priorité fixe), quoi qu'il arrive, si vous recevez un appel, l'application de gestion du téléphone fonctionnement.

[modifier] Système de fichier XFS

Le système de fichier XFS permet aux applications de se réserver une bande passante. Ceci signifie que lorsque le système sera surchargé, les applications critiques pourront fonctionner normalement : Leur exécution est garantie par une bonne gestion des priorité, leur accès au disque est garantie à hauteur de la réservation de leur bande passante.

[modifier] Limitation de temps CPU (cpulimit)

On peut forcer les applications à se limiter dans leur utilisation du CPU. En fait, on le simule.

Sur tous les systèmes, le noyau garde des trace de l'utilisation du CPU en temps processeur (secondes d'utilisations du CPU). Certaines applications, comme cpulimit, permettent de mettre en pause une application quand elles estiment qu'elle a utilisé trop de temps processeur.

Ce genre d'application sert avant tout pour faire des tests de performance, on peut ainsi tester une application qui doit tourner sur une machine 10x moins puissance que celle de développement assez facilement. Pour régir un environnement de logiciels, ça ne sert à rien.

[modifier] Derrière tout ça

[modifier] L'idée du multi-tâche

Derrière tout ça il se cache une idée simple, dans un même système, sur un même ordinateur, nous n'avons pas tous les même besoins. Si on compare un système à une entreprise, la secrétaire doit répondre immédiatement aux appels, le commercial doit préparer rapidement des powerpoints et l'ingénieur doit fait évoluer l'existant. Si maintenant on souhaite réduire les effectifs de cette entreprise pour remplacer ces trois personnes par une seule, nous devront fixer des priorité à chaque tâche de ce nouveau super-employé :

• Répondre rapidement au téléphone (priorité 0, on ne fait rien d'autre ne même temps)
• Faire des powerpoints (priorité 4, ça urge)
• Faire évoluer l'existant (priorité 99, on a le temps)

Ce qui signifie que lorsque l'employé prend son rôle de secrétaire, il ne fait rien d'autre. Pour le reste des tâche, s'il a à faire beaucoup de choses en temps que commercial ET ingénieur, pour 20 minutes passées à travaillé sur le powerpoint, il passera [ (4+1)/(99+1) ] * 20 = 1 minute à faire du travail d'ingénieur.

Bien sur l'inconvénient, c'est que si on a beaucoup de client et donc beaucoup de coups de fils et beaucoup de présentation à gérer, on fera peur de recherche et développement. Mais est-ce bien grave ?

[modifier] Alternative

La principal alternative consiste à répartir les tâches entre plusieurs éléments du systèmes : entre plusieurs ordinateurs dans un système informatique. Un se chargera de récupérer les données en temps réel, un autre se chargement de répondre aux requêtes des clients immédiatement et un troisième de traiter les données.

Le réel avantage de la répartition entre plusieurs machines est l'indépendance. Une panne d'une machine ne créera pas a panne de tout le système. Parfois cela peut aussi régler de vrais problèmes de surcharges.

[modifier] La clé de l'ordonnancement

Disons que je suis un restaurateur.

Pour bien ordonnancer des tâches, il faut :

[modifier] Connaitre ses besoins globaux

Il faut être clair avec soit même...

1. Je veux servir tout le monde de la même façon ?
2. Je veux servir les riches d'abord (ce sont eux qui rapportent le plus, c'est normal) ?
3. Je veux servir les riches d'abord tout en gardant une bonne qualité de service pour les pauvres (histoire qu'ils restent quand même) ?

[modifier] Déterminer les goulots d'étranglements

Il faut bien connaitre ses problèmes...

• Sur quoi je passe le plus de temps ?

1. L'accueil ?
2. Le service ?
3. Les cuisines ?

[modifier] Découper les tâches

• Comment puis-je découper les tâches de façon simple et logique ?

1. Servir table par table ?
2. Servir couvert par couvert ?
3. Servir plat par plat ?

[modifier] Choisir une méthode de gestion des priorité

A partir du découpage des tâches, des goulots d'étranglement constatés et de notre désir final (faire plus d'argent), on choisit une méthode de répartition :

1. Les riches sont reçus en premier, servis en premier, débarrassés en premier ?
2. Les riches sont reçus en premier, servis en premier mais débarrassés normalement ?

[modifier] Dans un système d'exploitation

Dans un système d'exploitation, on veut offrir la possibilité d'accèder à plusieurs programmes en même temps.

Les goulots d'étranglements sont le processeur, le disque dur et éventuellement la RAM (ça se complique encore avec la swap).

Comme on n'arrive pas à trouver un meilleur découpage, on découpe en instructions exécutées (le plus petit ensemble) par intervalle de temps pour le processeur.

[modifier] Méthodes concrètes d'ordonnancement

[modifier] Programme multi-threadé

[modifier] Vision générale

Dans un programme multi-threadé, vous allez répartir les priorité de processus en fonction de vos besoins.

Si vous avez un programme organisé avec :

• Un thread pour stocker les données sur une base de données
• Un thread pour stocker les données dans des fichiers logs
• Un thread de réception de données sur une connexion TCP de la part de clients
• Un thread d'appel de pages web

• Pour les données stockées en logs et en base de données, vous allez faire lire à ces threads des FIFO, et vous pouvez les faire travailler en faible priorité.
• Pour les données reçues de la part des clients, vous allez faire en sorte que le serveur réponde aussi vite que possible (on veut être réactif).
• Pour les appels faites sur des pages webs (avec ou sans WebService), la priorité ne compte pas vraiment puisqu'on va attendre le serveur distant.

[modifier] Risques

Il ne faut cependant pas risquer, avec les mécanismes de synchronisation utilisé dans des threads avec basse priorité, de vérouiller des threads haute-priorité. Vous mettez alors tout votre système à plat. Pour éviter cela il n'y a pas de recette magique :

• Vous pouvez par exemple ne définir que deux niveaux de priorité différents. Comme ça, un processus basse priorité qui bloquerait un processus haute priorité ne risquerait pas d'être bloqué par un processus de moyenne priorité tournant à fond.
• Si vous estimez que certains threads sont beaucoup plus important que d'autres, vous pouvez utiliser les "yield" d'attente ( Thread::yield() en java et Thread::Sleep(0) en C# .Net et un paquet d'autres langages). Cela permet notamment de soulager certains environnement "pas trop multitâches" (du genre plateforme J2ME légère). On apppelle ça du multitâche collaboratif ("je m'arrête et je continu quand tu t'arrêtes").

[modifier] Processus

Avoir plusieurs processus permet :

• D'utiliser des applications que l'on n'a pas développé (mysqld sera par exemple le processus de gestion de BDD)
• D'utiliser des environnement de développement différents (C/C++/Java/C#/PHP)
• De redémarrer les processus lors de mise à jour par exemple
• D'analyser des données (comme le temps CPU ou la consommation de RAM) par processus
• De définir des niveaux de priorité propre au système, donc bien gérés. Ce à l'exception de certains systèmes embarqués comme Windows CE où les priorités sont gérés thread par thread.

Mais cela complique :

• La communication inter-processus
  • UNIX/Linux et Windows (en C# .Net en tout cas) supportent les "tubes" de communications inter-processus et la mémoire partagée (mais ça devient plus complexe)
  • Les flux réseaux permettent non seulement d'assurer une communication inter-processus simple, mais ils permettent aussi de transférer les processus d'une machines à une autre. Si le système devient sur-utilisé, on le découpe (petite dédicace à WCF, introduit dans le framework .Net 3.0, qui permet de virtualiser ces échanges à l'image des WebServices mais en mieux).

[modifier] Ordonnancement des systèmes "maison"

On a parfois besoin d'ordonnancer des tâches de traitement de systèmes de maison. Il peut s'agir par exemple de l'analyse de fichiers de logs, ou de traitement de données issues d'une base de données.