Les systèmes d'exploitation/La multiprogrammation

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

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 relativement simples. Notamment, ceux-ci ne pouvaient pas 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 solution 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 aie cessé et est inutilisé durant tout ce temps. 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 à cela 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). Pour manipuler plusieurs processus, l'OS doit mémoriser des informations sur eux. Ces informations sont stockées dans ce qu'on appelle un Process Control Block, une portion de la mémoire.

Allocation du processeur[modifier | modifier le wikicode]

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 switcher entre les différents programmes qui doivent être exécutés : en switchant assez vite, on peut donner l'illusion que plusieurs processus s'exécutent en même temps.

Ordonnanceur noyau os

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 que que celui-ci attend une donnée en provenance d'une entrée-sortie).
Etats 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 switcher de processus, il doit choisir un processus dans la file d'attente et le lancer 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, ce contexte d’exécution est sauvegardé quand il est interrompu et restauré lors de l’ordonnancement. On appelle cela une commutation de contexte. Avec cette méthode de sauvegarde du contexte, le système d'exploitation doit fatalement 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.

Reste que pour utiliser notre 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.

Ordonnancement collaboratif[modifier | modifier le wikicode]

Tout d'abord, on va commencer par un systéme d'exploitation qui exécute des programmes qui s’exécute 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, 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, 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 First Input First Output, 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 peu 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.

Ordonnancement préemptif[modifier | modifier le wikicode]

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 toute. 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 au dépend 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 rapdité 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 quelque 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 ont 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…

Création et destruction de processus[modifier | modifier le wikicode]

Les processus peuvent naître et mourir. La plupart des processus démarre 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 unixoïdes, 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 ».

Communication inter-processus[modifier | modifier le wikicode]

Comme on l'a vu plus haut, 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. La méthode la plus simple consiste à partager un bout de mémoire entre processus, mais il existe d'autres méthodes que nous allons aborder.

Avec isolation des processus[modifier | modifier le wikicode]

La première méthode 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és 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.

Sans isolation des processus[modifier | modifier le wikicode]

Il est possible de rassembler plusieurs programmes dans un seul processus. Ces programmes n'étant pas isolés, ils se partagent le même morceau de mémoire et peuvent ainsi communiquer entre eux via une mémoire partagée. Les programmes portent alors le nom de threads. 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. Généralement, les threads sont gérés en utilisant un ordonnancement préemptif, mais certains threads utilisent l'ordonnancement collaboratif (on parle alors de fibers). Les threads et fibers 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.

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