Portail informatique Année 2018 – 2019

PAAM – Programmation avancée des architectures multicoeurs

Ce TP a pour but :
  • de vous faire manipuler les interruptions,
  • de vous faire comprendre la gestion du temps dans un noyau,
  • et de vous montrer comment fonctionne un ordonnanceur.
Avant de modifier le noyau, nous commençons par créer un programme de test. Commencez par cloner xv6 : git clone https://stark2.int-evry.fr/csc4508_xv6/ Dans le noyau xv6, positionnez-vous sur la branche scheduler avec : git checkout scheduler Cette branche doit contenir le fichier source stest.c. Ce fichier contient des #pragma (c'est-à-dire des directives pour le compilateur) permettant d'éviter que gcc effectue des optimisations (option -O0 de gcc). Ces optimisations doivent être évitées car le code que nous allons exécuter dans stest est tellement simple que gcc arrive à entièrement l'éliminer s'il effectue des passes d'optimisation. Modifiez le Makefile de façon à compiler stest en ajoutant _stest à la variable UPROGS. Lancez xv6 (avec make qemu) et vérifiez que vous pouvez bien appeler cette nouvelle commande. Cette commande doit terminer sans rien faire. Modifiez stest.c de façon à ce qu'il crée 3 fils avec fork. Chaque fils doit afficher PID start puis PID termine, où PID est le PID du processus. Vérifiez que votre programme se comporte correctement. Si vous voyez que xv6 se met à vous parler de zombie, ne vous inquiétez pas : nous nous débarasserons de ces méchants zombies à la question suivante.

Si vous êtes curieux, n'hésitez pas à lire le code de fork dans proc.c. Ce code est instructif et montre comment on peut dupliquer un processus, c'est-à-dire, à haut niveau, copier sa mémoire et sa structure proc. N'hésitez pas à demander à vos enseignants si vous voulez avoir plus de détails sur ce code que nous n'étudierons pas plus dans ce module.
Dans la plupart des systèmes, lorsqu'un processus se termine, il passe à l'état zombie. Cet état intermédiaire entre la vie et la mort permet au père du processus de pouvoir consulter le code de retour de son fils tout en évitant que le fils ne soit élu. Dès que le père a récupéré ce code de retour, le zombie est détruit, c'est-à-dire que la structure proc utilisée par le zombie est définitivement libérée.

En général, un utilisateur ne croise que rarement des zombies car :
  • un shell détruit tout seul ses enfants zombies,
  • lorsque le père d'un zombie meurt, le zombie, comme n'importe quel autre processus, est adopté par un processus adoptant (le processus 1, un processus nommé systemd ou parfois un processus avec un autre nom spécialisé dans ce rôle). Lorsqu'il adopte un zombie, le processus adoptant le détruit.

Dans xv6, le processus init est le processus adoptant et il affiche un message quand il croise un zombie. En vous inspirant du code de init.c, faîtes en sorte que stest détruise ses fils zombies. Si vous lisez l'ensemble du code de init, vous pouvez comprendre ce que fait ce processus initial :
  • init crée les descripteurs de fichiers 0, 1 et 2, et les associent à la console. Ce sont les flux d'entrée, de sortie et d'erreur de init. Ces fichiers ouverts étant hérités lors d'un fork (voir le code de fork dans proc.c), vous devriez comprendre comment un père et son fils partagent leurs flux d'entrée, d'erreur ou de sortie.
  • init crée ensuite un shell, c'est celui avec lequel vous pouvez interagir avec xv6.
Modifiez stest pour que chaque processus (le père et ses trois fils) effectue 3 boucles de 2<<28 itérations ne faisant rien. Si vous lancez votre programme, il devrait maintenant mettre quelques secondes à s'exécuter. Lorsqu'il optimise le code, gcc s'aperçoit que les boucles n'ont aucun effet, sauf sur les variables locales d'itérations. Comme ces variables ne sont pas utilisées, c'est-à-dire qu'elles ne sont pas lues, gcc arrive donc à éliminer entièrement le code des boucles lorsqu'il optimise. C'est pour cette raison que les optimisations sont désactivées dans le programme.
Si vous lancez stest, vous devriez remarquer que, de façon inattendue, xv6 exécute deux processus entièrement avant d'exécuter les deux autres entièrement. C'est normal : l'un de vos enseignants distrait a oublié de mettre le code la gestion du temps dans xv6. Comme le Makefile est configuré pour utiliser deux cœurs, une fois qu'un des deux cœurs exécute un processus, le processus s'exécute entièrement sans rendre la main au système puisqu'il n'effectue aucun appel système et qu'il n'y a aucune réception d'interruption. Nous commençons par réactiver les interruptions horloges. Techniquement, xv6 n'utilise qu'une source de temps locale pour gérer le tick sur chaque CPU, et, au lieu d'utiliser une source externe, utilise aussi cette source locale pour gérer le jiffies.

Dans la fonction lapicinit de lapic.c, ajoutez le code permettant de configurer l'horloge locale du lapic. Pour cela, il faut recopier le code suivant dans la fonction : lapicw(TDCR, X1); lapicw(TIMER, PERIODIC | (T_IRQ0 + IRQ_TIMER)); lapicw(TICR, 200*10000000); Dans ce code :
  • la seconde ligne demande à lancer l'horloge locale dans le mode périodique, c'est-à-dire demande à recevoir régulièrement une interruption sur l'IDT numéro T_IRQ0 + IRQ_TIMER (remarque : il n'est pas nécessaire ici d'indiquer sur quel cœur doit être reçue l'interruption puisque le LAPIC génère l'interruption sur son cœur local) ;
  • la dernière ligne règle la fréquence du tick: tous les 200*10000000/(TDCR * HZ) secondes, où HZ est la fréquence du bus mémoire, et TDCR est un diviseur configuré à la première ligne.

Lancez xv6, si votre code est correct, vous devriez régulièrement voir un message vous signalant que xv6 est vivant. Si vous jetez un coup d'œil à lapicw qui s'occupe d'envoyer des données dans le lapic, vous devriez remarquer que ce code n'effectue que des écritures en mémoire. Techniquement, lapic pointe vers une zone de mémoire MMIO, et c'est donc le lapic qui reçoit les requêtes d'écritures, pas la mémoire.
Nous avons régler le tick a une fréquence relativement faible de façon à ne pas avoir trop d'affichages de messages. Faîtes en sorte de multiplier par 200 la fréquence de réception du tick. Supprimez aussi le code affichant que xv6 est en vie dans trap.c. Si vous observez les quelques lignes de code qui se trouve au dessus de la ligne que vous venez de supprimer, vous pouvez observer le code qui s'occupe de gérer le jiffies :
  • seul le cœur 0 gère le jiffies, et cette variable s'appelle tick dans xv6 (l'utilisation du nom tick ici n'est pas idéale : en général, cette variable s'appelle jiffies et le tick est local à un cœur) ;
  • vous pouvez aussi remarquer l'appel à wakeup qui réveille les processus qui attendent sur la variable jiffies. C'est avec ce mécanisme de synchronisation que xv6 met en œuvre l'appel système sleep (voir le code de sys_sleep dans sysproc.c).

Notez aussi que la fonction trap dans lequel se trouve le code que vous observez est le point d'entrée de xv6 : le début du code gère le cas spécial d'un appel système ; la suite gère les autres interruptions.
Dans cet exercice, vous concevez un ordonnanceur dans xv6. Modifiez le code de trap de façon à ce que le processus courant lâche le processeur à chaque fois que le noyau reçoit un tick. Pour cela, il suffit d'ajouter le code suivant if(myproc()) yield(), à chaque réception de tick(). Cette fonction permet de lâcher le processeur, ce qui a pour effet d'activer l'ordonnanceur (fonction elect()). Expliquez la différence entre l'état RUNNING et l'état RUNNABLE. Ces deux constantes sont définies dans proc.h et une utilisation est faite dans la méthode yield().

L'état RUNNABLE signifie que le processus est prêt à s'exécuter mais qu'il n'est pas élu. L'état RUNNING signifie que le processus s'exécute sur un cœur.

Sachant que xv6 peut s'exécuter sur plusieurs cœurs, expliquez pourquoi il faut protéger l'accès au champ state des processus (celui qui indique si un processus est à l'état RUNNING ou RUNNABLE). On ne vous demande pas de lire le code, mais de trouver un exemple avec un pseudo-code.

L'incohérence pourrait venir du fait qu'un processus soit élu sur deux cœurs simultanément.

Expliquez comment, à partir de yield(), le code arrive jusqu'à la fonction scheduler().

La fonction yield() commence par acquérir le verrou ptable.lock et à passer le processus à l'état RUNNABLE puisque ce dernier n'est plus élu. Ensuite, yield() appelle sched().

La fonction sched commence par vérifier que l'état du noyau est cohérent avant d'appeler la fonction swtch. Cette fonction magique en assembleur permet de passer du processus courant au processus nommé scheduler que nous décrirons plus tard. En détail, la fonction swtch s'occupe simplement de sauvegarder les registres du processeur et de restaurer ceux du processus scheduler. En particulier, swtch sauve le pointeur de code du processeur (qui se trouve dans sched) et active celui du processus scheduler (qui se trouve dans la fonction scheduler).

La fonction scheduler est le processus scheduler. Ce processus spécial s'exécute une boucle infinie dans le noyau qui s'occupe de trouver un processus à élire (avec elect()) et de passer à ce processus à l'aide de la fonction swtch qu'on vient de décrire.

Cherchez dans le noyau où est appelé la fonction scheduler. Expliquez.

Techniquement, scheduler est la dernière fonction appelée dans mpmain elle-même appelée par main. Cette fonction main est le point d'entrée dans le noyau lors du démarrage (voir TP précédent). On peut donc en conclure que le scheduler est simplement le processus initial de démarrage.

Vous devriez remarquer que, malgré nos changements, l'ordonnanceur continue à exécuter entièrement deux processus avant d'exécuter les deux autres. En lisant le code de elect(), expliquez pourquoi.

La fonction elect choisit le premier processus prêt du tableau proc, ce qui finalement revient à systématiquement élire le même processus.

Modifiez la fonction elect() pour éviter le problème de famine que vous observez (en d'autres termes pour garantir que tous les processus sont élus régulièrement). Cette question est longue et devrait vous occuper jusqu'à la fin du TP. Vous avez plusieurs solutions. Pour les étudiants les plus à l'aise, nous leur conseillons la politique à priorité variable et pour les autres étudiants, la politique FIFO. Pour les dieux, ils peuvent directement se lancer dans la politique de PetitLinux :

  • [FIFO] : vous pouvez vous servir du paramètre old qui indique quel était le dernier processus élu pour passer au suivant dans le tableau. Dans Linux, cette politique s'appelle SCHED_RR (round-robin).
  • [Priorité fixe] : vous pouvez ajouter une priorité statique prio à un processus (dans la structure proc) que vous fixerez manuellement (par exemple avec prio = pid/2) ; puis appliquer un algorithme FIFO sur les processus les plus prioritaires (solution commençant à se rapprocher de ce que l'on fait en temps réel) ;
  • [LRU] : vous pouvez ajouter un timestamp à la structure proc indiquant quel est le processus qui a été le moins récemment élu. Pour cela, il suffit de comprendre ce qu'est la variable tick (solution relativement réaliste) ;
  • [Priorité variable] : vous pouvez ajouter une variable prio à la structure proc. Ensuite, vous pouvez faire en sorte que cette variable augmente à chaque tick pour les processus non élus et diminue fortement à chaque tick pour le processus élu indiqué par la variable old. La politique SCHED_OTHER de Linux se rapproche un peu de cette solution mais est plus équitable ;
  • [PetitLinux] : Vous pouvez donner un type aux processus et appliquer la politique suivante :
    • Si old a le type FIFO, vous le laissez élu. Avec cette politique, dès qu'un processus est élu, il a la garantie de rester élu, sauf s'il s'endort. C'est la politique que vous aviez en début de séance ;
    • Sinon, si il existe un processus avec l'attribut SCHED_FIFO, vous l'élisez ;
    • Sinon, si le processus old a le type SCHED_RR, vous élisez le processus SCHED_RR en appliquant une politique FIFO,
    • Sinon, s'il existe un processus de type SCHED_RR, vous l'élisez ;
    • Sinon, vous appliquez un algorithme à priorité variable ou un LRU.
Depuis 2007, lorsqu'un processus est de type SCHED_OTHER, Linux utilise en fait la politique CFS (Completly Fair Scheduler). Vous pouvez en trouver une description de haut niveau ici. En dehors de cette variation, l'algorithme PetitLinux est exactement celui que nous vous avons décrit. Notez que l'algorithme d'ordonnancement de Linux fait environ 20.000 lignes de code. Vous pouvez trouver une ébauche de correction dans la branche scheduler-soluce : git checkout scheduler-soluce git diff scheduler