Les systèmes d'exploitation/La multiprogrammation

Les tout premiers OS datent des années 1950, et ceux-ci ont commencé à devenir de plus en plus utilisés à partir des années 60-70. Évidemment, ces OS étaient simples, au point de ne pas pouvoir exécuter plusieurs programmes en même temps. Il était ainsi impossible de démarrer à la fois un navigateur internet, tout en écoutant de la musique. Dit autrement, ces systèmes d'exploitation ne permettaient de ne démarrer qu'un seul programme à la fois. On appelait ces OS des OS mono-programmés ou mono-tâche.

Mais cette approche avait un problème. Lors de l'accès à un périphérique, le processeur doit attendre que le transfert avec le périphérique ait cessé avant de pouvoir faire quoique ce soit d'autre. Durant toute la durée de la communication avec le périphérique, le processeur est inutilisé. Pour certains programmes qui accèdent beaucoup aux périphériques, il est possible que le processeur ne soit utilisé que 20% du temps, voire moins. Une solution possible est d’exécuter un autre programme pendant que le programme principal accède aux périphériques. Un OS qui permet cela est un OS multi-programmé. Le nombre de programmes pouvant être chargés en mémoire simultanément est appelé le taux de multiprogrammation. Plus celui-ci est élevé, plus l'OS utilisera le processeur à ses capacités maximales.

Les OS actuels vont plus loin et permettent d’exécuter plusieurs programmes "simultanément", même si aucun programme n'accède aux périphériques. Les OS de ce genre sont des OS multi-tâche. L'apparition de la multiprogrammation a posé de nombreux problèmes, notamment au niveau du partage de la mémoire et du processeur. Dans ce qui va suivre, nous allons voir comment ces OS gèrent la mémoire et les commutations entre programmes (appelés processus sur ces OS).

Dans ce qui va suivre, nous utiliserons le terme processus pour parler d'un programme, quelqu'il soit. En réalité, les deux termes ne sont pas synonymes, comme nous le verrons vers la fin du chapitre. Mais nous ferons la confusion pour le moment.

L'allocation du processeur

Le système d'exploitation utilise une technique très simple pour permettre la multiprogrammation sur les ordinateurs à un seul processeur : l'ordonnancement. Cela consiste à constamment alterner entre les différents programmes à exécuter : en alternant assez vite, on peut donner l'illusion que plusieurs processus s'exécutent en même temps.

Ordonnanceur noyau os

Diagramme d'état des processus, version détaillée.

Avec cette technique, chaque processus peut être dans (au moins) trois états :

• Élu : un processus en état élu est en train de s'exécuter sur le processeur.
• Prêt : celui-ci a besoin de s'exécuter sur le processeur et attend son tour.
• Bloqué : celui-ci n'a pas besoin de s'exécuter (par exemple, parce qu'il attend une donnée en provenance d'une entrée-sortie).

Suivant le système d'exploitation, d'autres états sont possibles, comme un état terminé (le programme a fini de s’exécuter), un état "en cours d'initialisation", et bien d'autres.

États d'un processus

Les processus en état prêt sont placés dans une file d'attente, le nombre de programme dans cette liste a une limite fixée par le système d'exploitation. Lorsque l'OS décide de changer de processus, il choisit un processus dans la file d'attente et le lance sur le processeur. Pour comprendre comment faire, il faut se souvenir qu'un processus manipule un ensemble de registres processeur, aussi appelé contexte d'exécution du processus. Pour qu'un processus puisse reprendre où il en était, il faut que son contexte d’exécution redevienne ce qu'il était. Pour cela, le contexte d’exécution est sauvegardé quand le processus est interrompu et restauré lors de son redémarrage. On appelle cela une commutation de contexte. Le système d'exploitation doit évidemment mémoriser tous les contextes des processus dans une liste appelée table des processus, elle-même très liée à la file d'attente.

L'ordonnancement sur un seul processeur

Reste que pour utiliser le processeur au mieux, il faut faire en sorte que tous les processus aient leur part du gâteau. C'est ce qu'on appelle l'ordonnancement. Il existe deux grandes formes d'ordonnancement : l'ordonnancement collaboratif, et l'ordonnancement préemptif. Dans le premier cas, c'est le processus lui-même qui décide de passer de l'état élu à l'état bloqué ou prêt, par l'intermédiaire d'un appel système. Dans le second, c'est le système d’exploitation qui stoppe l’exécution d'un processus. L'avantage du dernier cas est que les processus ne peuvent plus monopoliser le processeur.

L'ordonnancement collaboratif

Tout d'abord, on va commencer par un système d'exploitation qui exécute des programmes qui s’exécutent les uns après les autres. Ces programmes sont exécutés jusqu’à ce qu'ils finissent leur travail ou décident eux-mêmes de stopper leur exécution, soit pour accéder à un périphérique, soit pour laisser la place à un autre programme.

Avec l'algorithme First Input First Output (FIFO), les programmes à exécuter sont ajoutés dans la file d'attente quand on les démarre. Ceux-ci sont alors stockés dans la file d'attente dans l'ordre dans lesquels on les a fait démarrer. L'ordonnanceur décide alors d’exécuter le programme entré dans la file d'attente avant tous les autres en premier. En clair, les programmes sont exécutés dans l'ordre dans lequel ils sont rentrés dans la file d'attente.

Avec l'algorithme Last Input First Output (LIFO), les programmes à exécuter sont ajoutés dans la file d'attente quand on les démarre. Ceux-ci sont alors stockés dans la file d'attente dans l'ordre dans lesquels on les a fait démarrer. Mais contrairement à l'algorithme FIFO, l'ordonnanceur exécute le programme entré en dernier dans la file d'attente, et non le premier. Si vous ajoutez un programme dans une file d'attente contenant déjà des programmes en attente, ce sera lui le prochain à être exécuté, vu qu'il a été ajouté en dernier. Cet algorithme peut souffrir d'un phénomène assez particulier : dans certains cas, un programme peut très bien mettre énormément de temps avant d'être exécuté. Si vous exécutez beaucoup de programme, ceux-ci seront rentrés dans la file d'attente avant les tout premiers programmes exécutés en premier. Ceux-ci doivent alors attendre la fin de l’exécution de tous les programmes rentrés après eux.

L'algorithme Shortest Job First est basé sur une logique simple. Les programmes à exécuter sont placés dans la file d'attente et l’ordonnanceur va alors décider d’exécuter d'abord les processus qui se termineront le plus rapidement. Pour appliquer cet algorithme, on suppose que les temps d’exécution des différents programmes sont connus à l'avance et sont parfaitement bornés. Cette contrainte peut sembler absurde, mais elle a un sens dans certains cas assez rares dans lesquels on connait à l'avance le temps mit par un programme pour s’exécuter. Dans ce cas, l'algorithme est simple : on exécute le programme qui met le moins de temps à s’exécuter en premier. Une fois celui-ci terminé, on le retire de la file d'attente et on recommence.

L'ordonnancement préemptif

L'ordonnancement préemptif se base souvent sur la technique du quantum de temps : chaque programme s’exécute durant un temps fixé une bonne fois pour toutes. En clair, toutes les « x » millisecondes, le programme en cours d’exécution est interrompu et l'ordonnanceur exécuté. Ainsi, il est presque impossible qu'un processus un peu trop égoïste puisse monopoliser le processeur aux dépens des autres processus. La durée du quantum de temps doit être grande devant le temps mis pour changer de programme. En même temps, on doit avoir un temps suffisamment petit pour le cas où un grand nombre de programmes s'exécutent simultanément. Généralement, selon la rapidité du matériel, un quantum de temps entre 10 et 100 millisecondes donne de bons résultats. Pour information, Windows utilise un quantum de 15ms, et Linux un quantum de 10ms.

Voyons maintenant les algorithmes préemptifs qui permettent de choisir quel programme faire passer de l'état prêt à l'état élu. Pour faire simple, nous allons en voir quelques-uns, relativement importants et très proches de ceux utilisés dans les OS actuels.

L'algorithme Shortest Remaining Time Next est une variante préemptive de l'algorithme Shortest Job First vu au-dessus. Dans cette version, si un programme est ajouté dans la file d'attente, on regarde le temps que ce nouveau venu mettrait à s’exécuter, et on compare avec le temps qu'il reste au processus en cours d’exécution avant que celui-ci finisse son travail. Si le temps mit par le nouveau programme est plus faible que le temps d’exécution du programme en train de s’exécuter, on change et on exécute le nouveau venu à la place.

L'algorithme du tourniquet exécute chaque programme l'un après l'autre, dans l'ordre. Cet algorithme est redoutablement efficace et des OS comme Windows ou Linux l'ont utilisé durant longtemps. Mais cet algorithme a un défaut : le choix du quantum de temps doit être calibré au mieux et n'être ni trop court, ni trop long.

Algorithme du tourniquet (Round-robin)

L'algorithme des files d'attentes multiple niveau donne la priorité aux programmes rapides ou qui accèdent souvent aux périphériques. Cet algorithme utilise plusieurs files d'attentes, auxquelles on donne des quantums de temps différents. Tout programme démarre dans la file d'attente avec le plus petit quantum de temps, et change de file d'attente suivant son utilisation du quantum. Si un programme utilise la totalité de son quantum de temps, c'est le signe qu'il a besoin d'un quantum plus gros et doit donc changer de file. La seule façon pour lui de remonter d'un niveau est de ne plus utiliser complètement son quantum de temps. Ainsi, un programme va se stabiliser dans la file dont le quantum de temps est optimal (ou presque).

L'ordonnancement par loterie repose sur un ordonnancement aléatoire. Chaque processus se voit attribuer des tickets de loterie : pour chaque ticket, le processus a droit à un quantum de temps. À chaque fois que le processeur change de processus, il tire un ticket de loterie et le programme qui a ce ticket est alors élu. Évidemment, certains processus peuvent être prioritaires sur les autres : ils disposent alors de plus de tickets de loterie que les autres. Dans le même genre, des processus qui collaborent entre eux peuvent échanger des tickets. Comme quoi, il y a même moyen de tricher avec de l'aléatoire…

L’ordonnancement sur plusieurs processeurs

Les algorithmes ci-dessus marchent quand plusieurs processus doivent s’exécuter un seul processeur. Mais les ordinateurs actuels sont très complexes et beaucoup n'ont pas qu'un seul processeur. Soit ils ont effectivement plusieurs processeurs connectés à la carte mère, soit ils ont un processeur dit multicœurs. Pour rappel, les processeurs multicœurs peuvent être vus comme un regroupement de plusieurs processeurs sur la même puce de silicium. Pour être plus précis, ils contiennent plusieurs cœurs, chaque cœur pouvant exécuter un programme tout seul. Chaque cœur dispose de toute la machinerie électronique pour exécuter un programme, que ce soit un séquenceur d'instruction, des registres, une unité de calcul. Par contre, certains circuits d'un processeur ne sont présents qu'en un seul exemplaire dans un processeur multicœurs, comme les circuits de communication avec la mémoire ou les circuits d’interfaçage avec la carte mère.

Dans ce qui suit, nous utiliserons le terme cœurs pour désigner soit les cœurs d'un processeur multicœurs, soit les différents processeurs d'un système multiprocesseur.

Pour profiter de plusieurs cœurs, les algorithmes d'ordonnancement doivent être revus, ou tout du moins adaptés à la présence de plusieurs cœurs. Le point principal est que le système d'exploitation doit décider de répartir les programmes sur les différents cœurs, sans compter qu'il doit le faire de manière optimale. Le cas le plus simple est celui où il y a autant de cœurs que de processus, mais ce cas est rare en pratique. Il arrive souvent qu'il y aie plus de processus à exécuter que de cœurs, ce qui fait qu'il faut alors ordonnancer plusieurs programmes sur un même cœur.

Globalement, il existe deux méthodes pures pour l'ordonnancement multicœurs : soit on gère les deux problèmes précédents séparément, soit on les gère avec un seul algorithme. Le premier cas consiste à répartir les programmes sur les différents cœurs, avant d'appliquer les algorithmes de la section précédente dans le cas où il y a plusieurs programmes sur un seul cœur. L'autre solution consiste à utiliser un seul algorithme qui résout les deux problèmes en même temps. On parle alors d'ordonnancement partitionné dans le premier cas, et d'ordonnancement global dans le second. Il existe aussi des méthodes hybride, qui font un peu des deux.

L'avantage de l'ordonnancement partitionné est sa simplicité et sa facilité de programmation. Les algorithmes précédents peuvent être réutilisés sans problème et il suffit de rajouter un algorithme de répartition des programmes sur les différents cœurs. Mais l'inconvénient est que les performances sont généralement mauvaises. La raison est qu'un processus est attribué à un cœur sans pouvoir en changer. Imaginez par exemple que je lance 6 processus différents : deux cœurs recevront un processus, les deux autres en recevront deux. Maintenant, imaginons que le ferme les deux processus sur les deux premiers cœurs : on aura alors deux cœurs inutilisés et deux cœurs qui exécutent chacun deux processus. Alors que la solution idéale est de migrer des processus pour remplir les deux cœurs inutilisés. De plus, les algorithmes pour répartir les programmes sur les différents cœurs peuvent être assez complexe. L'ordonnancement global n'a pas ce problème, car il permet de migrer des processus d'un cœur à un autre. La migration en elle-même a des couts, mais le gain en vaut très souvent la peine.

Notons que l'ordonnancement, peu importe qu'il soit partitionné ou global ou hybride, est très compliqué sur les processeurs multicœurs dits asymétriques, c'est-à-dire quand les différents cœurs ne sont pas identiques, à savoir que certains sont plus puissants que d'autres, ou que certains cœurs disposent de fonctionnalités que les autres n'ont pas. Certaines applications bénéficient à s’exécuter sur un type de cœur plutôt qu'un autre, que ce soit car elles demandent plus de puissance ou sont programmées pour utiliser les fonctionnalités de certains cœurs. Dans ce cas, la répartition est diablement complexe et les algorithmes conçus pour ce genre d'architectures sont particulièrement compliqués à programmer.

La création et destruction de processus

Les processus peuvent naître et mourir. La plupart des processus démarrent quand l'utilisateur demande l’exécution d'un programme, n'importe quel double-clic sur une icône d’exécutable en est un bon exemple. Mais, le démarrage de la machine en est un autre exemple. En effet, il faut bien lancer le système d'exploitation, ce qui demande de démarrer un certain nombre de processus. Après tout, vous avez toujours un certain nombre de services qui se lancent avec le système d'exploitation et qui tournent en arrière-plan. À l'exception du premier processus, lancé par le noyau, les processus sont toujours créés par un autre processus. On dit que le processus qui les a créés est le processus parent. Les processus créés par le parent sont appelés processus enfants. On parle aussi de père et de fils. Certains systèmes d'exploitation conservent des informations sur qui a démarré quoi et mémorisent ainsi qui est le père ou le fils pour chaque processus. L'ensemble forme alors une hiérarchie de processus.

Sur la majorité des systèmes d'exploitation, un appel système suffit pour créer un processus. Mais certains systèmes d'exploitation (les dérivés d’Unix, notamment) ne fonctionnent pas comme cela. Sur ces systèmes, la création d'un nouveau processus est indirecte : on doit d'abord copier un processus existant avant de remplacer son code par celui d'un autre programme. Ces deux étapes correspondent à deux appels systèmes différents. Dans la réalité, le système d'exploitation ne copie pas vraiment le processus, mais utilise des optimisations pour faire comme si tout se passait ainsi.

Si les processus peuvent être créés, il est aussi possible de les détruire quand ils ont terminé leur travail ou s'ils commettent une erreur/faute lors de leur exécution. Dans tous les cas, le processus père est informé de la terminaison du processus fils par le système d'exploitation. Le processus fils passe alors dans un mode appelé mode zombie : il attend que son père prenne connaissance de sa terminaison. Lorsque le processus se termine, le système récupère tout ce qu'il a attribué au processus (PCB, espaces mémoire, etc.), mais garde une trace du processus dans sa table des processus. C'est seulement lorsque le père prend connaissance de la mort de son fils qu'il supprime l'entrée du fils dans la table des processus. Si un processus père est terminé avant son fils, le processus qui est le père de tous qui « adopte » le processus qui a perdu son père et qui se chargera alors de le « tuer ».

La communication inter-processus

Les processus sont chargés dans des espaces mémoire dédiés où seuls eux peuvent écrire. On parle d'isolation des processus. Il faut cependant noter que tous les systèmes d'exploitation n'implémentent pas cette isolation des processus, MS-DOS en étant un exemple. Faire communiquer des processus entre eux demande d'utiliser des mécanismes de communication inter-processus. Les méthodes les plus simples consistent soit à partager un bout de mémoire entre processus, soit à communiquer par l’intermédiaire d'un fichier partagé. Mais ces méthodes rudimentaires ne sont pas très pratiques et il existe d'autres méthodes plus élaborées, que nous allons aborder maintenant.

L'échange de messages

La première méthode de communication inter-processus est appelée l'échange de messages. Il permet aux processus de s'échanger des messages, des blocs de données de taille variable ou fixe selon l'implémentation. Mais le contenu n'est pas standardisé et chaque processus peut mettre ce qu'il veut dans un message. Le tout est que le processus qui reçoit le message sache l’interpréter. Pour cela, le format des données, le type du message, ainsi que la taille totale du message, est souvent envoyé en même temps que le message.

Dans le cas le plus simple, il n'y a pas de mise en attente des messages dans un espace de stockage partagé entre processus. On parle alors de passage de message. Cela fonctionne bien quand les deux processus ne sont pas sur le même ordinateur et communiquent entre eux via un réseau local ou par Internet. Mais certains OS permettent de mettre en attente les messages envoyés d'un processus à un autre, le processus récepteur pouvant consulter les messages en attente quand celui-ci est disponible. Les messages sont alors mis en attente dans diverses structures de mémoire partagée. Celles-ci sont appelées, suivant leur fonctionnement, des tubes ou des files de messages. Ces structures stockent les messages dans l'ordre dans lequel ils ont été envoyés (fonctionnement en file ou FIFO). La différence entre les deux est que les tubes sont partagés entre deux processus, un pouvant lire et un autre écrire, alors qu'une file de message peut être partagée entre plusieurs processus qui peuvent aussi bien lire qu'écrire.

Les threads et fibers

Une autre méthode est de regrouper plusieurs programmes dans un seul processus, afin qu'ils partagent le même morceau de mémoire. Les programmes portent alors le nom de threads. Les threads d'un même processus partagent le même espace d'adressage. Ils partagent généralement certains segments : ils se partagent le code, le tas et les données statiques. Par contre, chaque thread dispose de sa propre pile d'appel.

Ces threads doivent aussi être ordonnancés. On fait ainsi la distinction entre threads proprement dits, gérés par un ordonnancement préemptif, et les fibers, gérés par un ordonnancement collaboratif. Le changement de contexte entre deux threads est beaucoup plus rapide que pour les processus, vu que cela évite de devoir faire certaines manipulations obligatoires avec les processus. Par exemple, on n'est pas obligé de vider le contenu des mémoires caches sur certains processeurs.

Distinction entre processus mono et multi-thread.

Les threads utilisateurs sont des threads qui ne sont pas liés au système d'exploitation. Ceux-ci sont gérés à l'intérieur d'un processus, par une bibliothèque logicielle. Celle-ci s'occupe de la création et la suppression des threads, ainsi que de leur ordonnancement. Le système d'exploitation ne peut pas les ordonnancer et n'a donc pas besoin de mémoriser les informations des threads. Par contre, chaque thread doit se partager le temps alloué au processus lors de l'ordonnancement : c'est dans un quantum de temps que ces threads peuvent s'exécuter.

Les threads noyaux sont gérés par le système d'exploitation, qui peut les créer, les détruire ou les ordonnancer. L'ordonnancement est donc plus efficace, vu que chaque thread est ordonnancé tel quel. Il est donc nécessaire de disposer d'une table des threads pour mémoriser les contextes d'exécution et les informations de chaque thread.

Threads utilisateurs

Threads noyaux