 Bonjour à tous, bienvenue dans la suite de ce cours sur l'ordonnancement.
 Dans le cours précédent, on a vu les ordonnancements en mode batch,
 c'est-à-dire sans notion de quantum.
 Aujourd'hui, on va voir les ordonnancements à base de temps partagé.
 Le temps partagé repose sur la notion de quantum qu'on a vu la dernière fois.
 Comment les systèmes d'exploitation implémentent le quantum ?
 Pour ça, ils ont besoin d'une aide du matériel,
 ils ont besoin d'un petit composant externe au processeur central qu'on appelle l'horloge.
 Ici, vous avez un exemple d'horloge.
 C'est un composant comme une sorte de contrôleur
 qui fonctionne en parallèle du CPU, de l'unité centrale, de votre Intel ou de votre AMD,
 et dont le but est de générer à intervalle de temps régulier une interruption horloge.
 Ce composant fonctionne avec son propre quartz,
 il fonctionne à une certaine fréquence qui est différente de la fréquence du processeur.
 Typiquement, une horloge fonctionne à une fréquence de 1 MHz.
 C'est activé 1 million de fois par seconde,
 toutes les 10 puissances, toutes les microsecondes,
 tandis qu'un processeur fonctionne à des fréquences de l'ordre du gigahertz.
 Ce composant qui fonctionne en parallèle du processeur central
 manipule un registre spécifique qu'on appelle le registre horloge,
 qu'on appellera dans la suite RH ou RTempo en TD.
 Que fait l'algorithme de ce petit composant matériel ?
 A chaque fois qu'il est activé, toutes les 10 -6 secondes, toutes les microsecondes,
 il décrémente ce registre horloge.
 Si jamais ce registre passe à la valeur 0,
 à ce moment-là, il lève l'interruption horloge.
 C'est tout ce que ça fait.
 C'est une boucle infinie.
 A chaque fois que le circuit est activé, je déclenche l'interruption horloge.
 Je vous rappelle, les interruptions sont systématiquement traitées par le système d'exploitation.
 Ça entraîne un traitement en mode système.
 Un point important, c'est que ce fameux registre horloge,
 c'est un registre qui est modifiable uniquement en mode privilégié du processeur.
 Seul le système d'exploitation peut positionner une valeur dans ce registre horloge.
 Cette valeur sera ensuite décrémentée par le composant matériel.
 L'astuce pour implémenter un quantum, c'est que le système va mettre une valeur dans ce registre horloge
 pour pouvoir générer une interruption dans tant de microsecondes.
 Si vous voulez être interrompu toutes les 100 millisecondes,
 pour pouvoir commuter, pour pouvoir basculer d'une tâche T1 à une tâche T2,
 il suffit de mettre dans le registre horloge la valeur du quantum exprimée en microsecondes.
 C'est-à-dire que vous mettez la valeur 100 000 ici.
 Dans 100 000 microsecondes, vous serez interrompu.
 Ça veut dire que 100 000 microsecondes, c'est égal à 100 millisecondes.
 C'est l'astuce que fait le système.
 Le système d'exploitation, à chaque fois qu'il va lire une nouvelle tâche, par exemple la tâche T1,
 il veut être sûr de reprendre la main.
 Ce qu'il faut avoir en tête, c'est que quand une tâche s'exécute en mode utilisateur,
 pendant le temps où la tâche s'exécute, le système ne s'exécute pas.
 Si on tente de faire une boucle sans faire d'appel système,
 sans demander temps de ressortie, en faisant uniquement du calcul,
 pendant l'exécution, on n'a qu'un seul cœur.
 Pendant l'exécution de la tâche, Linux ne s'exécute pas.
 C'est votre tâche qui s'exécute sur le processeur.
 Pour que le système reprenne la main au bout d'un certain temps,
 au moment où il donne la main, il restaure les rejets de la tâche du processeur,
 il va positionner également le registre horloge en mettant la valeur du quantum.
 Comme ça, il est sûr qu'au bout de N microsecondes, il sera interrompu.
 Ça, c'est matériel.
 Donc au bout de 100 000 microsecondes, le registre horloge va passer à 0.
 Le composeur horloge va à ce moment-là déclencher une interruption,
 l'interruption horloge, qui est l'interruption la plus prioritaire,
 qui va vous faire basculer automatiquement en mode système.
 À ce moment-là, le système d'exploitation en boîte Linux reprend la main,
 il peut sauvegarder les registres de T1, restaurer les registres de T2,
 et réinitialiser le registre horloge de nouveau à la valeur du quantum.
 Il remet 100 000 dans le registre horloge.
 De nouveau, dans 100 000 microsecondes, je serai interrompu,
 je pourrai rebasculer sur T1, et ainsi de suite.
 C'est comme ça que les systèmes implémentent les quantum.
 Grâce au registre horloge, ils mettent des valeurs dans le registre horloge
 pour pouvoir être interrompus dans le futur, de manière sûre.
 Et donc là, c'est un mécanisme qui est sûr,
 parce que T1, lui, n'a pas le droit, lorsque vous êtes en mode système,
 vous n'avez pas le droit de toucher au registre horloge.
 Du coup, le système est sûr, à partir du moment où il met une valeur dans le quantum,
 il est sûr qu'au pire, dans tant de microsecondes,
 il sera interrompu, il aura l'interruption horloge, et reprendra la main.
 Donc si on détaille un petit peu ce qui est fait lorsqu'une interruption horloge arrive,
 l'interruption horloge va être traitée par le système d'exploitation,
 en mode S, en mode privilégié du processeur.
 On sauvegarde les registres d'un processus courant, par exemple de M1 à T1, tout à l'heure.
 Et donc là, je vais profiter de l'interruption horloge
 pour traiter tout ce qui est lié au temps, dans le système d'exploitation.
 Notamment, je vais gérer les alarmes.
 Les alarmes, c'est un mécanisme qu'offrent les systèmes
 pour pouvoir déclencher une action au bout de temps de millisecondes, par exemple.
 Typiquement, dans les réseaux, si j'ai un acquittement qui n'est pas arrivé à temps,
 je veux faire un traitement.
 Donc il y a beaucoup d'alarmes qui sont utilisées par pas mal de logiciels,
 et donc c'est à ce moment-là qu'on va les traiter.
 Lorsqu'une interruption horloge a lieu, je regarde si des alarmes n'ont pas expiré,
 ont expiré ou pas.
 J'en profite également pour mettre à jour l'heure de la machine.
 L'heure, c'est une variable globale qui est maintenue dans le système d'exploitation,
 par le système d'exploitation.
 Donc à chaque fois qu'une interruption horloge arrive, je rajoute un quantum à mon heure.
 Il vient de s'écouler un quantum de temps.
 Donc une fois que j'ai géré tous les aspects temporels,
 j'ai mis à jour tous les traitements et les alarmes, mis à jour mon heure,
 je vais choisir une nouvelle tâche,
 donc là par exemple je vais choisir T2,
 je vais restaurer ce registre,
 puis avant de rebasculer, de quitter le mode système,
 c'est-à-dire faire le retour d'interruption,
 je vais réinitialiser le registre horloge
 pour le repositionner à la valeur du quantum exprimé en microsecondes.
 Donc là, c'est ici que je remettrai RH = 100 000 par exemple.
 Si j'ai une fréquence de mégahertz au niveau de l'horloge.
 Donc ça, c'était fait comme ça pendant longtemps dans les systèmes.
 Alors ce petit mécanisme pour implémenter le quantum avait un petit défaut.
 Notamment dans tout ce qui est gestion du temps,
 on avait une gestion du temps assez peu précise.
 Le fait de mettre à jour l'heure uniquement à chaque fin de quantum,
 c'est-à-dire en gros toutes les 100 millisecondes,
 de même j'ai géré les alarmes avec une précision de 100 millisecondes,
 ça a resté assez rudimentaire.
 On ne pouvait pas avoir des alarmes très précises.
 Donc c'est pour ça que maintenant, dans tous les systèmes récents,
 on a un peu adapté ce schéma pour introduire la notion de tic.
 Donc un tic, c'est la valeur entre deux interrupts sur horloge.
 L'astuce c'est de se dire, j'ai envie d'être interrompu beaucoup plus souvent,
 que je n'ai pas envie d'être interrompu uniquement à chaque fin de quantum,
 mais de manière plus fréquente,
 pour pouvoir mettre à jour plus souvent mes alarmes et mon heure.
 Par contre, je n'ai pas envie de commuter systématiquement à chaque fois que je suis interrompu.
 Donc le quantum va maintenant s'exprimer en un certain nombre de tics.
 Et donc le tic, c'est vraiment la fréquence à laquelle je vais être interrompu par l'interrupt sur horloge.
 Donc typiquement, si je reprends le schéma de tout à l'heure,
 donc ma tâche T s'exprime en un certain nombre de tics, une dizaine de tics.
 Imaginons que je veux avoir un quantum de 100 ms toujours,
 mais j'ai envie de mettre à jour mon heure et gérer mes alarmes toutes les 10 ms.
 Donc comment je vais faire ?
 Donc ici, à chaque fois que je vais élire une tâche, dans l'enregistre horloge,
 plutôt que de mettre la valeur du quantum, je mets la valeur du tic.
 Donc plutôt que de mettre par exemple 100 000, je vais mettre 10 000.
 C'est-à-dire qu'au bout de 10 ms, je vais être interrompu par l'interrupt sur horloge.
 Et lorsque je suis interrompu, je ne vais pas commuter,
 parce que ça serait trop coûteux de passer de T1 à T2, ça coûte trop cher de faire ça.
 Donc là ici, je ne commute pas.
 Par contre, je vais juste mettre à jour mes alarmes,
 je vais traiter mes alarmes et mettre à jour l'heure.
 Et c'est tout. Je me contente de faire ça.
 Donc je fais ça pendant 10 tics, et au bout du 10e tic,
 bon là, n=10 par exemple, au bout du 10e tic,
 là ici, en plus de mettre à jour l'heure et traiter les alarmes,
 j'en profite pour commuter. Donc tous les 10 tics, je commute.
 Donc l'avantage de ça, c'est qu'on maintient un quantum de taille raisonnable,
 une centaine de millisecondes, ce qui est raisonnable, on ne commute pas trop souvent.
 Par contre, je mets à jour l'heure beaucoup plus souvent à chaque tic.
 Donc maintenant, tous les systèmes ont cette notion de tic.
 Une notion de tic qu'on appelle aussi le JIFI dans le monde de Linux.
 Donc maintenant, on a vu comment implémenter le temps partagé
 grâce aux composants matériels horloge, qui génèrent les interrupteurs horloge.
 Quelles sont les stratégies ? Comment je choisis ma tâche T2 ?
 Donc le premier algorithme qu'on va voir, c'est l'algorithme le plus simple,
 qu'on appelle l'algorithme du tourniquet, ou round-robin en anglais, RR.
 C'est un peu l'équivalent du FIFO, mais avec la notion de quantum.
 Donc l'idée du tourniquet, c'est l'algorithme le plus simple qu'on puisse imaginer,
 c'est qu'on va allouer les tâches à tour de rôle sur le processeur.
 Par exemple, ici au départ j'ai trois tâches, T1, T2, T3.
 Je vais donner la main à T1 pour un quantum, puis à T2 pour un quantum, puis à T3 pour un quantum,
 et je recommence T1, T2, T3, T1, T2, T3, donc ça tourne.
 C'est pour ça qu'on fait l'analogie avec un tourniquet.
 Donc plus concrètement, on a une file d'attente.
 Les tâches se mettent dans une file d'attente pour accéder au processeur.
 Lorsque je vais créer une tâche, je me mets en queue de la file d'attente.
 L'élection consiste à choisir la tâche prête qui est en tête de la file d'attente.
 Et enfin, lorsqu'il y a une fin de quantum, la tâche qui était en tête va de nouveau se retrouver en queue
 pour faire ce mouvement circulaire.
 Pour illustrer ça sur un petit exemple,
 imaginons que j'ai un quantum petit de 40 millisecondes.
 On va négliger les temps de commutation,
 on néglige le temps pour basculer de T1 à T2,
 ce qui est raisonnable,
 puisque les quantums, c'est plusieurs dizaines de millisecondes,
 ou en général une centaine de millisecondes,
 et les temps de commutation, ça vous prend quelques centaines de microsecondes.
 En général, on néglige les temps de commutation.
 Ici, on suppose qu'on a trois tâches, T1, T2 et T3,
 qui ont été créées dans cet ordre-là à l'instant T=0.
 Dans la file d'attente, j'ai d'abord T1 en tête, puis j'ai T2, puis j'ai T3.
 T1 dure 200 millisecondes, T2 30 millisecondes, et T3 100 millisecondes.
 Si je représente mon diagramme de quanta,
 ici, à l'instant 0, vous avez l'état courant de la file des tâches,
 j'ai T1 en tête, T2, T3, c'est T1 qui est élu.
 À partir de maintenant, on oublie la notion de tic,
 ce qui est plus un détail d'implémentation.
 Là, on parle uniquement de quantum.
 T1 va être élu, elle s'exécute,
 elle ne fait que du CPU, on va voir après comment on gère les entrées sorties.
 T1 s'exécute pendant tout son quantum.
 Lorsque la fin de quantum arrive, il y a une interruption horloge.
 À ce moment-là, T1 qui était en tête va être inséré en queue de la file d'attente,
 et c'est T2 qui est élu.
 T2 est élu, donc le système A40 élit T2, et lui donne un quantum.
 Elle va s'exécuter jusqu'en 80.
 Mais, comme T2 ne dure que 30 ms, elle va se terminer avant la fin de son quantum.
 En 70, T2 se termine.
 Dès qu'une tâche se termine, on n'attend pas la fin de son quantum.
 Dès qu'une tâche se termine, le système d'exploitation reprend la main,
 on rebascule le système, et le système va directement redonner la main à T3
 et réinitialiser le registre horloge.
 C'est pour ça qu'on n'attend pas 80 pour élire T3.
 Lorsque T2 est terminée, elle disparaît de la file d'attente,
 et la tâche qui est maintenant en tête de la file d'attente, c'est T3.
 On donne à T3 un quantum.
 T3 va consommer tout son quantum de temps.
 Il va s'exécuter pendant 40 ms.
 Au bout de 40 ms, interruption horloge.
 Je bascule en mode système.
 T3 est injecté en queue de la file d'attente.
 Il était en tête, il bascule en queue.
 C'est maintenant T1 qui est élu.
 T1, on lui donne un quantum.
 Fin de quantum, il est réinjecté en queue.
 Maintenant c'est T3.
 T1, T3, T1, T3.
 Au bout d'un moment, T3...
 La troisième fois que T3 est élu, il s'est déjà exécuté deux quantum.
 Il s'est exécuté une première fois à 40 ms, une deuxième fois à 40 ms.
 Il s'est exécuté en tout 80 ms.
 Il ne reste plus que 20 ms d'exécution avant de se terminer.
 C'est pour ça que la troisième fois que T3 est élu,
 au bout de 20 ms, il est élu en 230 à 250 ms, il se termine.
 Même mécanisme que tout à l'heure.
 On n'attend pas la fin de quantum.
 On redonne directement la main à T2
 et réinitialise l'enregistreur horloge.
 Du coup, T2 va s'exécuter un quantum.
 Ici, en 290 ms, T1 a besoin de quatre quantum.
 On redonne la main à T1 qui s'exécute pendant 40 ms.
 Au bout de 40 ms, fin de quantum.
 T1 est seul dans la file d'attente.
 C'est T1 qui va être élu.
 Il y a une fin de quantum, mais on va réélire la même tâche.
 Et enfin, en 230, la tâche T1 se termine et la file de nouveau est élu.
 Voilà un petit exemple.
 Si on calcule maintenant le temps de réponse associé,
 c'est les métriques qu'on avait vues la dernière fois.
 Pour calculer le temps de réponse, je vous rappelle,
 c'est la date de fin moins la date de création.
 Le temps de réponse de ces trois tâches,
 ici, sont de 130, 140 et 150 ms.
 Pour l'instant, je ne vous ai pas parlé d'entrée/sortie
 au niveau de cet algorithme-là.
 Je vous rappelle que lorsqu'une tâche fait une entrée/sortie,
 elle passe à l'état bloqué.
 Donc, elle est hors jeu pour l'ordonnanceur.
 Elle ne peut pas être choisie.
 Il y a plusieurs choix possibles.
 Dans le tourniquet de base, dans la stratégie RR de base,
 lorsqu'une tâche fait une entrée/sortie,
 c'était la tâche qui était en tête, en fait.
 T1 est en tête, elle fait une entrée/sortie.
 Elle va être mise hors jeu,
 elle va être insérée dans une liste des tâches bloquées.
 Elle est complètement éjectée du système.
 Et lorsque l'entrée/sortie est terminée,
 on la réinjecte en queue de la file d'attente.
 Cette stratégie-là, elle n'est pas très efficace.
 On la plémente assez peu.
 Pourquoi ? Parce que ce n'est pas très logique.
 Si une tâche T1 fait une entrée/sortie,
 au moment où elle fait son entrée/sortie,
 c'est la tâche la plus prioritaire, c'est celle qui est élue.
 Donc, elle va être pénalisée parce qu'elle va faire une entrée/sortie.
 L'entrée/sortie, ça prend du temps, ça prend quelques dizaines de millisecondes.
 Donc, elle va déjà être pénalisée parce qu'elle fait une entrée/sortie.
 Et en plus, on lui fait refaire un tour complet dans la file d'attente.
 Ce n'est pas très équitable.
 Ça entraîne des systèmes avec assez peu de réactivité.
 Dès qu'une tâche fait une entrée/sortie, elle est pénalisée pour son entrée/sortie.
 Et en plus, elle est obligée de refaire un tour complet,
 de se mettre en queue de la file d'attente.
 C'est pour ça qu'en général, maintenant, on fait une variante du rond de robine,
 qui est un peu plus efficace, qui permet une meilleure réactivité en cas d'entrée/sortie.
 Là, on va avoir une seule file d'attente.
 Ici, une file d'attente des tâches.
 Donc lorsqu'une tâche T1, on va l'illustrer juste après par un petit exemple,
 lorsqu'une tâche T1 fait une entrée/sortie,
 on va la maintenir dans sa position dans la file d'attente.
 Donc, elle reste en tête de la file d'attente,
 mais parce qu'elle est à bloquer, donc elle est hors jeu.
 Donc, elle va se faire doubler par les tâches prêtes qui sont derrière elle.
 Par contre, dès que la fin d'entrée/sortie arrive,
 elle est rebasculée à l'étape "prêt",
 et elle va être élue plus rapidement,
 parce qu'elle n'est pas en queue de file d'attente.
 On a maintenu sa position dans la file d'attente.
 Elle s'est juste fait doubler par la tâche suivante.
 Donc, elle s'est mise juste derrière la tâche suivante,
 mais dès que l'entrée/sortie est terminée,
 de nouveau, elle est prête à s'exécuter,
 elle va être élue beaucoup plus rapidement.
 Par contre, pour éviter qu'une tâche ne profite de ce mécanisme-là,
 on évite de faire un détour complet dans la file d'attente.
 On va lui allouer uniquement le quantum restant.
 Donc, le plus simple, c'est d'illustrer ça par un petit exemple.
 Donc, imaginons, on reprend la config de tout à l'heure.
 Donc là, j'ai une seule file d'attente,
 dans laquelle je représente mes trois tâches,
 T1, T2, T3, avec l'état "prêt".
 Donc, j'ai mes trois tâches qui ont été créées,
 parmi les tâches prêtes, j'ai T1 qui est élue.
 Donc, T1 est élue, le temps s'écoule comme ça.
 Au bout d'un moment, T1 fait une entrée/sortie.
 Donc, à ce moment-là, on la maintient.
 On la bascule à l'état "bloqué", donc elle passe à B,
 mais on ne la sert pas en que de file d'attente.
 Donc, elle est maintenue dans sa position,
 elle est juste doublée par la tâche qui est derrière elle,
 dans la file d'attente.
 Donc, T1 se bloque, par contre, elle reste devant T3.
 Donc, juste T2 est élue à ce moment-là,
 et dès qu'à la fin de notre...
 Donc, T2, c'est la tâche élue.
 Dès qu'à la fin de notre sortie, on rebascule T1 à l'état "prêt",
 et donc, dès que la tâche qui m'avait doublée
 termine son quantum, de nouveau ma tâche est réélue.
 Donc là, du coup, la tâche qui a fait notre sortie n'est pas pénalisée.
 Elle reprend la main très rapidement.
 Donc là, ce qui est important, c'est que lorsque la tâche va être réélue,
 on ne va pas lui redonner un quantum entier.
 Pourquoi ? Parce que ce serait très simple,
 sinon, si on me donnait un quantum entier,
 lorsque je suis réélu à la suite de mon entrée-sortie,
 je pourrais mettre un peu en défaut le système.
 Il suffirait, par exemple, imaginons que j'ai des quantum de 100 millisecondes.
 À 99 millisecondes, juste avant la fin de mon quantum,
 je fais une petite entrée-sortie.
 Je demande à transférer un bloc depuis le disque,
 juste pour être maintenu en tête de fil d'attente.
 Et du coup, systématiquement, je pourrais doubler T3 ici.
 T1 pourrait doubler T3 en faisant cette petite astuce.
 Vous voyez bien, T1, là, il est resté devant T3,
 parce qu'il a fait son entrée-sortie.
 Donc, pour éviter ce phénomène,
 qui pourrait entraîner une famine dans le système,
 on donne à la tâche élue,
 donc la tâche qui a fait une entrée-sortie va être réélue beaucoup plus rapidement,
 grâce à ce mécanisme, parce qu'elle évite de refaire un tour complet.
 Par contre, on ne lui donne que le quantum qui lui reste.
 Donc, si par exemple, ma tâche T1 faisait une entrée-sortie au bout de 99 millisecondes,
 elle serait de nouveau réélue très rapidement, dès que son entrée-sortie est terminée,
 mais on ne lui donnerait qu'une milliseconde de temps d'exécution.
 Donc, elle n'a aucun intérêt à faire ça.
 Donc, c'est important de lui donner...
 On la maintient très prioritaire, on la maintient en tête de file d'attente,
 mais on lui donne, la prochaine fois,
 le temps qui lui restait qu'elle n'avait pas consommé.
 Donc, ça pareil, on verra en TD, on fera des petits exemples autour de ça.
 Donc, la stratégie Ron Robbins,
 c'est une stratégie qu'on trouve dans beaucoup de systèmes.
 Donc, l'avantage de la stratégie du tournéquin, c'est que c'est une stratégie équitable.
 On répartit équitablement le temps entre les différentes tâches.
 Elle est simple, c'est l'équivalent un peu du FIFO,
 mais à la version temps partagé en rajoutant des quantums.
 Il n'y a pas de famine, donc ça c'est une propriété intéressante de cet algorithme-là.
 Par exemple, si une tâche est prête,
 alors qu'il y a N tâches dans la file d'attente,
 on est sûr qu'au pire, dans N-1 quantum, elle sera élue.
 Par exemple, imaginons qu'une tâche devient prête.
 Dans le pire, elle est en queue de file d'attente.
 Donc, devant elle, s'il y a N-1 tâche, en tout il y a N tâches dans mon système,
 dans le pire des cas, qu'est-ce qui va se passer ?
 Toutes les tâches vont utiliser tout leur quantum de temps.
 Elles utilisent leur quantum en entier.
 Au pire cas, dans N-1 quantum de temps, je suis sûr que ma tâche T sera élue.
 Ce n'est pas possible qu'une tâche se fasse doubler.
 Parce que de nouvelles tâches sont créées derrière.
 Si une tâche fait une entrée-sortie, elle va rester dans la file d'attente,
 mais lorsque l'entrée-sortie sera terminée, on lui donne le quantum restant.
 Donc, au pire, le pire scénario, c'est que toutes les tâches utilisent tout leur quantum de temps.
 À ce moment-là, une fois qu'elles ont utilisé tout leur quantum de temps,
 ce sera forcément à moi de m'exécuter.
 Par contre, le désinconvénient de cette stratégie,
 c'est que le côté équitable n'est pas forcément toujours bien dans les systèmes.
 On a envie que certaines tâches soient plus prioritaires que d'autres.
 Typiquement, j'aimerais bien qu'une tâche à un gros calcul matriciel
 soit moins prioritaire qu'une commande LS.
 Donc, c'est important d'avoir cette notion de priorité au niveau des tâches.
 Toutes les tâches n'ont pas la même priorité.
 On va introduire cette notion de priorité.
 On va voir un premier algorithme dans lequel on va rajouter des priorités de manière fixe.
 À chaque tâche, on va associer un niveau de priorité fixe
 qu'elle va garder tout au long de son exécution.
 Plutôt qu'avoir une seule file, comme on a vu jusqu'à présent,
 on va avoir une file d'attente avec une file par niveau de priorité.
 Lorsque je crée une tâche, on m'attribue une priorité
 et je vais m'insérer en queue de la file correspondante.
 L'élection consiste à aller voir les différentes files
 et à choisir la tâche prête en tête dans la file la plus prioritaire.
 Ensuite, lorsque j'ai une fin de quantum,
 je suis réinséré en queue de la file d'où je viens.
 Pour illustrer ça, un petit schéma pour illustrer ça,
 lorsque je crée une tâche, en fonction de ma priorité,
 je suis inséré dans ma file.
 Imaginons que j'ai trois files qui correspondent à des niveaux de priorité différents.
 Ici, j'ai des tâches contre des contraintes de temps fortes,
 ici j'ai des tâches système,
 ici j'ai des tâches utilisateur.
 Une classification comme ça.
 À la création, on m'attribue en fonction de mon type
 dans quelle priorité je m'insère.
 Donc là, ma tâche, je suis inséré dans une tâche
 dans le niveau de ma file, je suis élu,
 et à la fin de quantum, je vais être réinjecté en queue de ma file.
 Toutes les tâches temps réels sont réinjectées en queue de la file temps réel,
 toutes les tâches système sont réinjectées en queue de la tâche système,
 et toutes les tâches utilisateur sont réinsérées en queue de la tâche utilisateur.
 Donc là, on voit ici qu'une tâche utilisateur ne pourrait être élu que si
 les tâches, les files temps réels et systèmes ne contiennent plus aucune tâche prête,
 elles sont vides.
 Par exemple, si ici il n'y a aucune tâche prête,
 et ici il n'y a aucune tâche prête,
 à ce moment là, une tâche utilisateur peut être élu.
 Donc l'avantage de cette stratégie,
 ça prend en compte la priorité, c'est ce qu'on voulait.
 Par contre, il y a un inconvénient,
 dès que vous rajoutez cette notion de priorité,
 il y a des risques de famine.
 Une tâche utilisateur peut se faire doubler en permanence
 par des tâches temps réelles ou des tâches système.
 De même, un autre inconvénient de cette stratégie là,
 c'est que c'est compliqué.
 Lorsque je crée une tâche, de savoir dans quelle file je vais la mettre.
 Ce n'est pas très souple.
 Donc il y a une stratégie qui est très utilisée dans les systèmes,
 c'est une stratégie dans laquelle on va donner une priorité dynamique.
 Donc là, le principe ressemble un petit peu aux priorités fixes,
 c'est-à-dire que lorsque je vais affecter aux tâches des priorités,
 mais qui vont changer au cours du temps.
 Pareil, comme avant, on va avoir N files,
 donc différentes files, une file par niveau de priorité.
 Donc imaginons que j'ai N priorités possibles,
 je vais avoir N files, F0, Fn-1.
 On suppose que F0 est la file la plus prioritaire.
 Alors là, à la création, je ne me pose pas le problème
 de savoir à quel niveau de priorité je vais être créé.
 Par défaut, à la création, on me donne la priorité la plus forte.
 Quand je suis créé, je suis très prioritaire.
 Donc on m'insère en queue de la file F0, la file la plus prioritaire.
 L'élection, c'est comme avant,
 on va choisir parmi les files de F0 à Fn,
 je parcours les files dans cet ordre-là,
 et je choisis la tâche en tête de la file la plus prioritaire.
 Donc je vais d'abord voir s'il y a des tâches dans F0 prêtes.
 À ce moment-là, s'il y a une tâche en F0 prête,
 je prends celle qui se trouve en tête.
 S'il n'y a aucune tâche en F0 prête,
 je vais aller voir dans F1 et ainsi de suite jusqu'à Fn-1.
 Donc ça, ça ne change pas, c'est comme avant.
 Par contre, lorsqu'il y a une fin de quantum,
 on ne va pas me réinjecter en queue de la file d'où je viens,
 mais en queue de la file suivante.
 Donc à chaque fois que je m'exécute, je baisse d'un cran de priorité.
 Et ainsi de suite.
 Donc une fois qu'une tâche qui a été créée, qui était dans F0, s'est exécutée,
 elle va se retrouver dans F1, puis dans F2, puis dans F3, et ainsi de suite.
 Et donc jusqu'à Fn-1.
 Par contre, une fois que je suis dans Fn-1,
 les tâches qui sont issues de Fn-1 repartent pour un tour et sont injectées dans F0.
 Le plus simple, c'est de voir ça sur le petit schéma.
 Donc là, le schéma suivant, il est proche de ce qu'on avait avant,
 sauf que là, on voit bien qu'à la création,
 je suis systématiquement inséré dans la file la plus prioritaire F0.
 Donc imaginons que j'ai une tâche qui est créée ici en F0,
 et lorsqu'elle va s'exécuter, elle va migrer dans F1.
 Donc à chaque fin de quantum, vous voyez que votre tâche baisse d'un cran.
 Donc l'impact de ça, ça veut dire que si j'ai une tâche T' qui arrive,
 elle va me doubler.
 Et ainsi de suite.
 Donc là, les tâches vont migrer au fur et à mesure, jusqu'à Fn-1, à chaque fois exécutée.
 Donc là, ça veut dire qu'elle s'est exécutée N quantum de temps,
 et la prochaine fois qu'elle s'exécutera, elle repartira en F0.
 Donc pourquoi on s'amuse à faire ça ?
 Donc pareil, par contre, on voit bien que si j'ai une tâche nouvelle qui arrive,
 elle, elle double les tâches qui se sont déjà exécutées.
 Et c'est ça l'avantage ici.
 En fait, le gros avantage de ces stratégies-là,
 c'est qu'on va donner la priorité aux tâches nouvelles.
 Donc plus une tâche s'exécute, vous voyez bien ici ma tâche T,
 donc T c'est une tâche vieille, parce qu'elle s'est exécutée pendant N quantum.
 Donc les tâches anciennes sont moins prioritaires que les tâches nouvelles.
 Et c'est pour ça qu'on implémente ça.
 Donc ça, ça permet d'implémenter une stratégie dans laquelle on va favoriser les tâches courtes,
 les tâches qui viennent d'être créées, par rapport aux tâches longues qui se sont exécutées longtemps.
 Donc l'avantage, c'est fait pour ça, cette stratégie,
 c'est de pouvoir privilégier les tâches les plus courtes.
 Si à partir du moment où vous exécutez, on baisse votre priorité,
 ça veut dire que les tâches les plus anciennes sont moins prioritaires,
 et donc les tâches les plus courtes sont plus prioritaires.
 Et donc ça, c'est une façon rusée d'implémenter une stratégie qu'on avait vue en batch,
 du shortest job first, de la plus courte tâche d'abord.
 On avait vu que c'était une stratégie qui était bonne en mode batch,
 qui avait des meilleurs temps de réponse.
 Par contre, le gros inconvénient que je vous avais dit,
 c'est que dans la vraie vie, comment je ne connais pas à l'avance la durée des tâches.
 Donc c'est pratiquement impossible d'implémenter une stratégie SJF dans un vrai système.
 De choisir la tâche la plus courte, le système ne sait pas quelles sont les tâches,
 quand il voit T1, T2, T3, il ne sait pas que c'est T3 la plus courte.
 Il n'a aucun moyen de le savoir.
 Donc là, avec cette astuce, on peut implémenter une stratégie qui se rapproche de ça,
 à partir du moment où dès que vous exécutez, vous baissez votre priorité,
 l'effet de bourse avec les tâches les plus courtes est le plus prioritaire.
 Un gros calcul matriciel, lui, va se retrouver dans le fil F10, par exemple,
 il va se faire doubler par toutes les petites commandes LS.
 C'est ce qui se passe dans Linux.
 Dans Linux, si vous lancez 10 calculs matriciels,
 vous allez voir que votre commande LS, elle les double tous.
 Pourquoi ? Parce qu'elle va être élue beaucoup plus rapidement,
 tandis que les autres sont beaucoup moins prioritaires.
 Par contre, cette stratégie est intéressante pour ça,
 ça permet d'implémenter une sorte de SJF avec les notions de quantum,
 sans connaître à l'avance le temps d'exécution des tâches.
 Par contre, il y a un risque de famine, comme avant, comme avec les priorités fixes.
 Par exemple, si j'ai un calcul matriciel qui est dans la file F10,
 il peut se faire doubler en permanence par des commandes LS qui arrivent dans la file F0.
 Donc si vous avez un flux continu de création de petites tâches,
 là vous avez un risque de famine.
 Ce n'est pas trop gênant, parce que c'est facile à résoudre.
 Pour résoudre la famine, il suffit régulièrement de prendre toutes les tâches de votre système,
 de considérer toutes les files, et de remonter régulièrement,
 c'est-à-dire tous les X quantum, toutes les secondes, tous les D quantum,
 je vais prendre toutes les tâches et je vais les remonter dans un certain cran.
 Par exemple, toutes les tâches qui sont dans la file F10,
 je les remonte dans la file F5, et ainsi de suite.
 Il y a un algorithme dans lequel on régulièrement prend toutes les tâches prêtes,
 on les remonte, on remonte leurs priorités.
 Donc on les remonte dans les files.
 L'idée, c'est qu'à chaque fois qu'une tâche s'exécute, elle baisse, elle baisse, elle baisse dans les files.
 Par contre, régulièrement, le système les remonte pour éviter la famine.
 À force d'être remonté, par exemple, mon calcul matriciel qui se retrouvait dans la file F10,
 il va être remonté par exemple à F5, puis de F5 à F0.
 Une fois qu'il est dans F0, une fois que vous êtes dans la file la plus prioritaire,
 là, vous êtes sûr de passer. Pourquoi ?
 Parce que même si j'ai une nouvelle tâche à nouveau LS qui arrive,
 une tâche courte, il passera derrière vous,
 puisque une nouvelle tâche ne sert que de F0, pas en tête.
 Donc une fois que votre tâche a été remontée régulièrement,
 vu que le système les remonte régulièrement,
 une fois que votre tâche est remontée dans la file la plus prioritaire,
 elle est sûre de passer.
 Elle ne pourra plus se faire doubler par des nouvelles tâches.
 Donc là, on a vu à peu près les trois grands types d'algorithmes qui existent
 en termes de temps partagé.
 Vous avez les algorithmes de type round-robin,
 dans lesquels il n'y a pas de notion de priorité,
 donc à tour de rôle.
 Les algorithmes à priorité fixe, dans lesquels on attribue une priorité fixe
 et on le fait en round-robin entre chaque niveau de priorité.
 Et enfin, les CE à priorité dynamique, ce qu'on vient de voir là,
 qui permet, grâce à ce mécanisme de vieillissement de tâches,
 de favoriser les tâches courtes.
 Concrètement, dans un système, tous les ordinateurs qu'on a vus
 cohabitent au sein d'un même système.
 C'est même normalisé par POSIX.
 Par exemple, dans un système classique, dans Windows ou dans Linux,
 il y a différentes types d'ordinateurs.
 Donc typiquement, qui correspondent à différentes classes de tâches.
 Dans un système, ce qui est le plus prioritaire,
 c'est ce qu'on appelle les tâches temps réelles.
 Donc on a une file pour les tâches temps réelles.
 Donc ça, c'est ce qu'il y a de plus prioritaire.
 C'est plus prioritaire que les tâches de système.
 Dans les tâches temps réelles, ici, elles sont tellement prioritaires
 qu'on ne veut même pas partager le temps entre elles.
 Donc si vous créez une tâche de type temps réel,
 ce qu'on appelle une tâche FIFO,
 à ce moment-là, le temps partagé est désactivé.
 C'est-à-dire que la tâche temps réelle, dès qu'elle est prête,
 elle s'exécute sur le processeur jusqu'à ce qu'elle se termine
 ou qu'elle se bloque.
 Donc bien sûr, pour créer des tâches de type temps réel,
 il faut être super utilisateur.
 Donc il y a des interfaces qui permettent,
 lorsque vous créez une tâche, de dire
 "je veux que ce soit une tâche temps réelle".
 De même, dans Windows, vous pouvez, grâce au gestionnaire de tâches,
 dire que cette tâche veut qu'elle soit temps réelle.
 Mais le danger, bien sûr, si vous créez des tâches temps réelles,
 c'est qu'elles ne partagent pas le temps.
 Donc là, vous n'avez plus de quantum qui sont activés.
 Donc si la tâche temps réelle se met à boucler
 et vous avez un seul cœur,
 votre système est complètement gelé.
 Donc c'est dangereux.
 C'est pour ça qu'il faut être super utilisateur
 pour pouvoir créer des tâches temps réelles.
 Les ordonnancements FIFO existent,
 mais on ne le fait que pour des tâches très particulières,
 qu'on appelle des tâches temps réelles.
 Donc c'est des ordonnancements vraiment de type FIFO,
 tel qu'on l'a vu.
 Ensuite, généralement, cette file-là,
 la plupart du temps, elle est vide.
 On ne crée pas de tâches temps réelles comme ça.
 Ensuite, vous avez une autre file d'attente
 dans laquelle on va regrouper les tâches système.
 Donc, débutement, le système d'exploitation,
 il a besoin d'un certain nombre de tâches,
 qu'on appelle des démons,
 qui s'exécutent en permanence en mode système
 et qui aident le système d'exploitation,
 par exemple, pour réguler l'activité mémoire.
 On reverra ça lorsqu'on verra la mémoire virtuelle.
 Donc, ce sont des tâches qui sont réveillées régulièrement.
 La plupart du temps, elles sont bloquées,
 mais dès qu'elles sont réveillées, dès qu'elles sont prêtes,
 on veut qu'elles soient rapidement élues.
 Donc, ici, ce sont des tâches qui sont prioritaires,
 moins prioritaires que les tâches temps réelles,
 parce qu'elles n'ont pas de contraintes de temps fortes,
 mais qui sont quand même plus prioritaires
 que les tâches utilisateurs normales.
 Donc, ces tâches-là, la plupart du temps,
 elles sont bloquées, mais par contre,
 dès qu'une tâche système est prête,
 il faut qu'elle soit élue rapidement sur le processeur.
 Donc là, on peut partager le temps
 entre les tâches système,
 mais on ne veut pas qu'elles vieillissent.
 Donc, même les tâches système,
 elles sont généralement créées au démarrage de la machine,
 et on ne veut pas qu'à chaque fois qu'elles exécutent un quantum,
 elles baissent en priorité.
 Donc, c'est pour ça qu'on fait un round-robin
 sans notion de priorité ici.
 Et enfin, ensuite,
 ça c'est pour les tâches utilisateurs,
 c'est-à-dire que lorsque vous créez une tâche,
 lorsque vous créez un appel système fork
 pour créer une tâche, par exemple,
 lorsque vous lancez une commande,
 par défaut, toutes les tâches qui sont lancées
 sont dans ce niveau-là,
 ce qu'on appelle les niveaux de priorité dynamique.
 Donc là, c'est l'algorithme qu'on a vu.
 Donc, à chaque fois par défaut,
 lorsque le shell lance une commande,
 ou lorsque vous lancez, vous créez une tâche,
 via l'appel système fork qu'on va voir dans la course suivante,
 les tâches par défaut sont créées dans ce niveau de priorité.
 Et donc là, on active le phénomène de vieillissement,
 c'est-à-dire par défaut,
 vos tâches sont ici,
 elles vont migrer au fur et à mesure qu'elles s'exécutent
 dans les niveaux de priorité inférieurs.
 Voilà.
 Donc, on s'arrête.
 Et donc, la prochaine fois, dans le prochain cours,
 on verra la programmation des processus.
