Skip to content

MOOC NSI - fondamentaux.

Transcription de la vidéo

4.2.2.3 : Ordonnancement de processus

[00:00:01] Parlons maintenant d'ordonnancement, ou alors de la manière dont le système d'exploitation arrive à lancer et à gérer l'exécution de plusieurs processus à la fois. C'est ce qui nous permet d'avoir plusieurs applications qui tournent sur notre machine.

Nous avons vu qu'un processus est un programme en exécution. Nous avons également compris que l'unité matérielle qui effectivement s'occupe de l'exécution est le processeur. Donc, les programmes qui s'exécutent in finé s'exécutent sur le processeur. Ce qu'on dit, c'est que les processus s'exécutent sur le processeur. Après, si nous avons un seul processeur, donc une seule unité qui peut exécuter physiquement quelque chose, nous ne pouvons exécuter plus d'un processus à la fois. Donc, si nous avons plusieurs processus, il y en a un qui va pouvoir s'exécuter et les autres devraient attendre.

Dans cet exemple, j'ai un seul processeur, un seul cœur. Si je lance Facebook, j'ai le processus qui correspond. Si je lance Word, j'ai un autre processus. Si je lance un jeu, j'ai un troisième processus. Vu que j'ai qu'un seul processeur, il va falloir que le système d'exploitation gère le fait qu'il y ait trois processus à exécuter. Il faudrait qu'il choisisse lequel exécuter, à quel moment et dans quel ordre les passer sur le processeur.

Déjà, pour s'exécuter sur un processeur, il faudrait que le processus soit prêt. En effet, dans plusieurs cas, un processus peut se retrouver bloqué parce que les conditions pour son exécution ne sont pas réunies. En effet, un processus peut attendre que l'utilisateur rentre une certaine information, un processus peut attendre une communication réseau,

[00:02:04] un processus peut attendre qu'un autre processus fasse quelque chose... et donc il peut être bloqué.

(Donc,) De manière générale, un processus peut avoir plusieurs états. Tout d'abord, quand on lance quelque chose, il est créé par le système d'exploitation. Ensuite, il passe dans un état prêt, c'est-à-dire qu'il est prêt à s'exécuter mais il faut qu'il ait accès au processeur donc il attend le processeur. À un moment donné, le système d'exploitation décide de donner le processeur à ce processus-là et donc d'exécuter ce processus-là, et là, on dit que le processus est élu. A un moment donné, d'élu, il peut revenir dans l'état prêt, s'il a occupé le processeur pendant longtemps, ou, s'il doit attendre que quelque chose se passe, donc il passe dans l'état endormi. Et si l'exécution se termine, il passe dans l'état terminé.

Pour voir les différents états d'un processus, nous pouvons utiliser la commande que nous connaissons déjà qui est la commande "ps". Si nous regardons le manuel du système d'exploitation sous UNIX, avec "man ps", si on cherche bien, nous trouvons ce type d'informations qui nous donne les différents flags qui décrivent différents états des processus. Donc, par exemple, nous avons R pour dire que le processus est en exécution ou alors nous avons un T pour dire qu'il est terminé. Si nous avançons, voici un terminal où j'exécute donc "ps -j" qui me donne des informations plus détaillées sur le numéro du processus, le numéro du père, le numéro du groupe.

[00:03:54] Nous voici ici avec les informations sur l'état et vous voyez que j'ai plusieurs processus qui sont en exécution et d'autres qui sont endormis et qui attendent une interaction pour être réveillés. La même chose peut être observée avec les autres formes de ps, ps -F ou pstree qui nous donnent donc des relations de père à fils, mais nous avons la même colonne ici qui nous donne l'information, donc la colonne STAT qui nous donne l'information sur l'état du processus.

Alors, au début de l'informatique, quand les machines étaient énormes et occupaient des salles entières pour une capacité de calcul et de stockage quand même, qui n'ont rien à voir avec les machines d'aujourd'hui, on pouvait exécuter un seul processus. Et en plus, le processus de charger le programme dans la machine et de récupérer le résultat était plus long que l'exécution en elle-même. Donc, en gros, la machine passait plus de temps en inactivité que en activité de calcul. C'est pour cela qu'aujourd'hui, les systèmes d'exploitation ont bien évolué et nous avons la multi-programmation, où nous pouvons avoir plusieurs processus qui sont lancés, qui sont prêts à être exécutés, et il faut choisir parmi cet ensemble de processus lequel exécuter, et quand on l'arrête, il faudrait choisir quel sera le suivant. Cette tâche là revient à une partie du système d'exploitation qui s'appelle l'ordonnanceur. Le processus qui s'occupe du choix du processus à exécuter, c'est l'ordonnancement. Ou alors en anglais, c'est le scheduling. Le mot scheduling et scheduler sont bien rentrés dans le langage français.

[00:05:49] Alors comment on alloue le processus, le processeur aux processus? Donc, quand on choisit un processus, déjà, il va falloir décider lequel choisir. Et puis ensuite, il faut décider pour combien de temps il faut le laisser s'exécuter sur le processeur. Ce qui est clair, c'est que si nous adoptons une approche simple où nous donnons le processeur à un processus et on attend qu'il se termine, il se peut qu'on se retrouve dans une situation où on est bloqué puisque le processus est trop long (il suffit d'une boucle infinie, si on s'est trompé), ou alors le processus, peut-être qu'il est bloqué, il attend quelque chose. Et donc là, typiquement, il faudrait enlever le processeur de ce processus là et le donner à un autre processus. Pour éviter les situations où un processus monopolise le processeur et donc l'occupe pendant trop longtemps et fait attendre les autres processus pendant trop longtemps, nous avons le concept de temps partagé. Cela veut dire que si nous représentons le temps du processeur, donc le temps CPU, nous allons décider d'une période de temps maximale pour allouer le processeur au processus. Donc, nous allons avoir le découpage du temps processeur avec cette période qui s'appelle le quantum de temps. Et puis, si, à la fin d'un quantum de temps, un processus n'a toujours pas terminé, il va quand même être interrompu pour donner la main à un autre processus et ainsi faire avancer globalement les processus dans le système. C'est ça, en effet, qui nous donne l'impression qu'il y a plein de choses qui se passent en même temps sur notre machine,

[00:07:36] c'est parce que le système d'exploitation découpe le temps du processeur ou des processeurs et partage le temps entre les différents processus.

Alors, voici un exemple d'ordonnancement: imaginons que nous avons trois processus P1, P2, P3, les lignes horizontales sont les lignes de d'avancement de temps, et les flèches rouges sont les interruptions matérielles qui sont les interruptions horloge qui nous permettent de tenir compte du quantum de temps. Donc, le premier processus à être ordonnancé, c'est à dire à être mis en état d'exécution et qui occupe le processeur, c'est P1. A la fin de la période de temps, nous avons donc l'interruption système qui va se traduire par un traitement qui va arrêter P1 et va devoir choisir un autre processus. Imaginons donc que le l'ordonnanceur choisisse P2. Ici, ce qu'il faut voir, c'est que le temps de passer de P1 à P2 n'est pas nul. Donc ce rectangle ici violet correspond au temps de changement de contexte, donc de passage de P1 à P2. En quoi consiste ce changement de contexte? Il consiste à sauvegarder l'état de P1, pour qu'on puisse reprendre là où P1 a été arrêté. Donc, on sauvegarde des informations qui sont relatives à P1. Il y a l'ordonnanceur qui tourne pour choisir le prochain processus à exécuter, et ensuite donc, il faut charger les informations d'exécution nécessaires pour pouvoir commencer l'exécution du processus élu, ici P2. P2 s'exécute. Il y a encore une interruption matérielle qui nous indique que la tranche allouée, la tranche de temps allouée est finie,

[00:09:48] nous allons interrompre P2, donc le système d'exploitation va interrompre P2, va sauvegarder le contexte de P2, va faire tourner l'ordonnanceur et va choisir ici P3. On va charger les informations de P3 ,P3 va s'exécuter pendant la tranche de temps prédéfinie, interruption matérielle, changement de contexte. On reprend avec P1, puis on se termine avant la fin de la tranche de temps. Il est clair que nous n'allons pas laisser le processeur inoccupé pendant le reste du temps, mais l'ordonnanceur va tout de suite choisir un autre processus ici P2, et ainsi de suite.

Un autre exemple d'ordonnancement qui se passe un peu différemment puisque nous avons ici des processus bloqués. Alors ça commence de la même manière, nous avons P1 qui commence par occuper le processeur, ensuite, il y a l'interruption matérielle qui dit que le temps est fini et donc nous avons l'ordonnanceur qui va arrêter donc le système qui va arrêter P1, va sauvegarder son contexte, va faire tourner l'ordonnanceur pour décider du prochain processus et charger les informations d'exécution du prochain processus, ici, P2. P2 commence à s'exécuter, mais à un moment donné, a besoin d'une entrée/sortie, typiquement d'une lecture disque. La lecture de disque prend du temps pendant ce temps là. P2 ne peut s'exécuter puisqu'il a besoin du résultat de cette lecture disque. Ici donc, le système d'exploitation va mettre ce processus en attente., il va être bloqué, il ne va pas laisser le processeur inoccupé et va ordonnancer

[00:11:44] un autre processus. L'autre processus s'exécute, à un moment donné, nous avons donc l'interruption d'horloge qui nous dit que le temps pour ce processus est fini, nous avons encore changement de contexte, on reprend P1 et à un moment donné, il y a la lecture de disques qui se termine. Donc nous avons une interruption d'un autre type. Là, l'ordonnanceur peut décider qu'effectivement, il l'interrompt P1 et il rend la main à P2 pour qu'il puisse continuer avec son exécution jusqu'à ce que son temps soit écoulé. Donc, vous voyez bien que l'ordonnanceur ici s'efforce à occuper au maximum le processeur et ne pas le laisser inoccupé. Et après nous avons la notion de combien de temps dure ce changement de contexte? Et combien de temps dure le quantum de temps? Il est clair que si nous avons une tranche de temps qui est trop petite, nous allons avoir trop souvent des changements de contexte et donc nous allons perdre trop de temps. Si l'exécution de l'ordonnanceur est lente, pareil, nous risquons de passer beaucoup trop de temps dans le changement de contexte et tout cela peut influencer de manière très négative les performances du système et donc la réactivité du système d'exploitation. Alors, ce qu'il faut comprendre, c'est que l'ordonnancement est une question qui est très difficile et en fonction des contextes de systèmes d'exploitation et d'application, on peut avoir différents objectifs, donc, par exemple l'équité ou nous voudrions que tous les processus aient un accès égal aux processeurs. Nous voudrions éviter la famine, c'est-à-dire les cas où les processus n'aient jamais accès aux processus.

[00:13:46] Mais en même temps, peut-être que nous voudrions avoir des processus prioritaires, c'est-à-dire qui s'exécutent plus rapidement et plus facilement que les autres processus. Mais si on a des priorités, on risque d'avoir de la famine. Donc ça, c'est un équilibre qu'il faudrait gérer. En termes de performance c'est une question vraiment très sensible, mais là pareil, on peut choisir différentes métriques de performance. On peut chercher un temps de réponse moyen, c'est-à-dire entre le moment où on a lancé le processus et le moment où il nous rend le résultat. On peut regarder le rendement, c'est-à-dire le nombre de choses qu'on peut exécuter pendant une unité de temps. On peut regarder le taux d'occupation de CPU, le temps d'attente moyenne des processus, etc. et ce qu'il faut savoir c'est donc que l'ordonnancement multi objectif, c'est à dire qui essaie d'optimiser plusieurs critères de performance, est un problème très difficile et que pour l'instant, c'est un domaine très actif en termes de recherche et les propositions sont des heuristiques dans la majorité des cas et donc qui changent,je le répète, en fonction du contexte applicatif.

Dans cette vidéo, nous avons parlé d'ordonnancement. Nous avons parlé du fait qu'un système d'exploitation doit gérer plusieurs et même plusieurs dizaines de processus en exécution. Il a une partie dédiée, l'ordonnanceur, qui décide quel processus sera en exécution et quels processus en attente de pouvoir s'exécuter sur le processeur. L'ordonnancement est une question cruciale qui impacte fortement les performances du système.