TP9 : Gestion des processus, des threads et de la mémoire virtuelle

Objectifs

Dans les architectures manycore à espace d'adressage partagé, mais physiquement distribué (architectures NUMA),telle que l'architecture TSAR, on cherche à résoudre deux problèmes :

• réduire la latence et la consommation énergétique, en plaçant les données (et les instructions) utilisées par un thread dans le cluster contenant le coeur qui exécute ce thread.
• éviter les points de contention en répliquant dans plusieurs clusters les informations accédées par un grand nombre the threads, pour éliminer les goulots d'étranglement.

La technique la plus naturelle permettant au système d'exploitation de contrôler le placement et la réplication des données et des instructions est le mécanisme de mémoire virtuelle fourni par le composant matériel MMU, qui permet à l'OS d'associer une adresse physique (dans un cluster particulier) à une adresse virtuelle.

Almos-mkh est un OS multi-kernel. Chaque cluster de l'architecture dispose d'un noyau avec ses données globales, allouées à la compilation ou créées dynamiquement, dans lesquels sont définies les structures permettant de gérer les ressources du cluster. Les structures représentant les processus et les threads sont donc nécessairement distribuées et/ou répliquées dans tous les clusters.

Ce TP vise donc a présenter les mécanismes permettant à Almos-mkh d'utiliser la MMU des processeurs pour contrôler le placement, la distribution et la réplication des données et des instructions en mémoire physique, puis de présenter les mécanismes de création et de destruction d'un processus utilisateur.

Mémoire virtuelle

Principes Généraux

Comme pratiquement tous les systèmes d'exploitation de type UNIX, le système d'exploitation almos-mkh supporte une mémoire virtuelle paginée, et utilise des pages de 4 Koctets.

On rappelle que le mécanisme de mémoire virtuelle permet à plusieurs applications de co-exister sans conflits , et de s'exécuter simultanément sur une même machine, alors qu'au moment de la compilation, chaque application a été compilée comme si elle était seule dans l'espace adressage de la machine. Pour éviter les conflits, il faut que le matériel - au moment de l'exécution - déplace les segments virtuels (définis au moment de la compilation), et traduise donc chaque adresse virtuelle (instruction ou donnée) en une adresse physique contenue dans un certain cluster.

On rappelle que chaque application possède son propre espace virtuel dans lequel sont définis - au moment de la compilation - les quelques segments auxquels elle peut accéder (code, data stack, heap). Le système d'exploitation possède également son propre espace virtuel dans lequel sont définis ses propre segments. La seule contrainte est que les adresses des segments d'une application doivent être disjointes des adresses des segments système, puisqu'une application doit pouvoir accéder à la fois à ses propres segments et aux segments système (quand elle fait un appel système).

On rappelle que, dans chaque coeur, c'est le composant matériel MMU (Memory Management Unit) qui effectue cette traduction entre l'adresse virtuelle et l'adresse physique (appartenant à un certain cluster). Ce composant matériel MMU est placé entre le coeur et les caches L1, et utilise une table de traduction, dont le contenu est entièrement défini par l'OS. Puisque le but est d'éviter les conflits entre applications, l'OS doit évidemment construire une Table des Pages pour chaque application, et cette table est une des principales structures enregistrées dans le descripteur d'un processus UNIX. Cette table est indexée par le numéro de page virtuelle VPN (codé sur 20 bits pour un processeur 32 bits), et chaque entrée de la table contient un numéro de page physique PPN (codé sur 28 bits dans le cas de TSAR). Remarquez que l'encombrement de cette table, sans optimisation, est de 4 Moctets. Heureusement, cette table est très creuse et on utilise une représentation multi-niveaux (2 TSAR 40 bits, 4 pour les architectures 64 bits) pour réduire son encombrement.

Mémoire Virtuelle dans Almos-mkh

La mémoire virtuelle paginée est une composante essentielle d'almos-mkh, puisque l'objectif de cet OS est précisément d'automatiser ces mécanismes de réplication et de distribution, pour permettre le passage à l'échelle des applications parallèles multi-threads quand le nombre de coeurs augmente au-delà de quelques dizaines.

Amos-mkh s'appuie sur les deux principes suivants:

1. Pour placer un certain segment virtuel d'une application ou du noyau lui-même dans un certain cluster [cxy], il suffit d'assigner aux pages de ce segment des adresses physiques appartenant au cluster [cxy]. Almos-mkh utilise cette technique pour distribuer certaines grosses structures de données du noyau comme la DQDT ou le VFS (Virtual File System). Cette distribution permet de réduire la contention.
2. Si en plus on permet que la traduction d'une même adresse virtuelle puisse dépendre du cluster dans lequel est réalisée la traduction, ceci permet de répliquer certains segments virtuels dans tous les clusters. Par exemple, Almos-mkh réplique le segment de code de chaque application dans tous les clusters contenant au moins un thread de cette application. Suivant le cluster, la même adresse virtuelle d'instruction sera traduite en des adresses physiques différentes, mais toujours locales, ce qui permet à la fois de supprimer la contention et de réduire la latence.

Almos-mkh appelle VSL (Virtual Segment List) la structure de données permettant d'enregistrer la liste des segments virtuels accessibles pour une certaine application, et utilise cette structure pour vérifier qu'une adresse émise par une application est légale.

Almos-mkh appelle GPT (Generic Page Table) la structure de données définissant la table des pages pour une certaine application. L'implémentation de cette structure dépend des caractéristiques de la MMU matérielle et elle fait donc partie de la HAL (Hardware Abstraction Layer).

Vous devez lire les documents suivants pour répondre aux questions ci-dessous.

La MMU de l'architecture TSAR est décrite ​ici.

La politique générale d' almos-mkh concernant la distribution et la réplication des segments mémoire suivant leur type est décrite ​ici.

Questions sur la MMU de TSAR

1. Comment est découpée l'adresse virtuelle 32 bits ? Quelle structure le composant MMU de l'architecture TSAR impose-t-il pour la table des pages que doit construire l'OS ?
2. Chaque entrée valide de la table des page (PTE = Page Table Entry) contient une valeur de PPN et quelques flags. Combien faut-il de bits pour représenter un PPN ? Quels sont les flags enregistrés dans chaque entrée de la table ?
3. quel est le nom du registre de la MMU contenant l'adresse de base de la table de page ? À quoi sert ce registre ?
4. quel est le nom du registre de la MMU permettant d'activer ou de désactiver la MMU ? Comment l'OS peut-il utiliser ce registre ?
5. Quel est le nom du registre permettant de construire une adresse data de 40 bits quand la MMU-DATA est désactivée.
6. En cas de MISS sur la TLB, l'automate de la MMU accède à la tables pages pour obtenir le PTE manquant. Lorsque ce PTE est invalide (indiquant que la page n'est pas mappée), comment la MMU signale-t-elle le défaut de page au système d'exploitation ?
7. Quels registres de la MMU doivent être sauvegardés et restaurés lors d'un changement de contexte ?

Questions sur la politique de réplication & distribution

1. Comment le kernel d'Almos-mkh représente-t-il l'ensemble des segments accessibles dans l'espace virtuel d'une application (c'est-à-dire d'un processus) ? À quoi sert cette structure ?
2. La table des pages du processeur TSAR_MIPS32 est une table à 2 niveaux. La table des pages des processeurs Intel64 est une table à 4 niveaux. Quelle est l'abstraction définie par Almos-mkh pour représenter une table des pages indépendante de l'architecture matérielle cible ? À quoi sert cette structure ?
3. Pourquoi faut-il absolument que le descripteur d'un processus soit répliqué dans chaque cluster contenant au moins un thread de ce processus ?
4. Quelle est la politique implémentée par almos-mkh pour minimiser la contention lors de l'accès au segment user CODE contenant le code, pour une application parallèle multi-threads ?
5. Quelle est la politique implémentée par almos-mkh pour maximiser la localité lors de l'accès au segment user STACK ?
6. Quelle est la politique implémentée par almos-mkh pour minimiser la contention lors de l'accès au segment user DATA contenant les données globales définies à la compilation, pour une application parallèle multi-threads ?
7. Pourquoi les segments kernel KCODE, KDATA, KHEAP doivent-ils pouvoir être accédés localement par n'importe quel thread de n'importe quel processus utilisateur?
8. Pourquoi les N segments kernel KDATA et les N segments kernel KHEAP distribués dans tous les clusters doivent-ils pouvoir être accédés par n'importe quel thread de n'importe quel processus utilisateur? Quelle abstraction Almos-mkh définit-il pour permettre ces accès distants ?
9. Comment almos-mkh implémente-t-il ces accès distants dans le cas des architectures contenant des processeurs 32 bits telles que TSAR-MIPS32?
10. Comment almos-mkh implémente-t-il ces accès distants dans le cas des architectures contenant des processeurs 64 bits telles que les serveurs Intel64 ?

Création / destruction des Processus et des Threads

Principes Généraux

Un processus est le conteneur des ressources nécessaires à l'exécution d'une application. Parmi ces ressources, il y a l'espace d'adressage virtuel, les fichiers ouverts et l'ensemble des threads contenus dans ce processus. Un processus mono-thread est un cas particulier du cas général d'un processus multi-threads. Par conséquent, tout processus contient au moins un thread appelé main thread.

Nous avons déjà vu que l'espace d'adressage virtuel est défini par un ensemble de segments dans l'espace virtuel du processus (VSL) et d'une table de pages (GPT) qui contient le mapping des pages virtuelles dans l'espace physique. Nous avons vu également qu'il existe plusieurs types de segments en fonction de leur usage (code, piles, data, etc.) et que chaque type (privé ou public ; localisé ou distribué) suit une politique spécifique pour son mapping. Nous avons vu aussi que lorsqu'un processus s'étend sur plusieurs clusters, chaque cluster contient une partie des structures qui décrivent la mémoire du processus (VSL et GPT). Les structures sont fondamentalement distribuées (comme les segments de piles) mais certaines parties sont identiques dans tous les clusters, et donc sont plutôt répliquées (comme les segments de codes).

Un processus (père) peut créer un nouveau processus (fils) par clonage, en utilisant l'appel système fork(), qui duplique le descripteur de processus père (structure process_t) pour créer un descripteur de processus fils identique (ou presque). Le processus fils est généralement créé dans un autre cluster, pour distribuer la charge. Puis, le processus fils peut (ou pas) se transformer pour exécuter une nouvelle application, en utilisant l'appel système exec() .

Lors de la création d'un processus P, Almos-mkh crée systématiquement un thread main, représenté par un descripteur de thread (structure thread_t), dans le même cluster que le descripteur de processus P. Lorsqu'il s'exécute, ce thread main peut créer d'autres threads, dans le même cluster ou dans des clusters différents, en utilisant l'appel système pthread_create(). Ceci peut entraîner la création de copies des descripteurs du process P dans ces nouveaux clusters, si elle n'existaient pas encore.

Cette création des threads et des processus n'est déjà pas une opération triviale sur un système normal, mais elle est particulièrement délicate pour almos-mkh, en raison de la distribution/réplication des structures dans plusieurs clusters.

Questions

Pour répondre aux questions qui suivent, il faut commencer par lire la documentation décrivant les structures process_t et thread_t, ainsi que les opérations de création et de destruction, que vous trouverez ​ici.

La description des appels de commandes à distance (appelées RPC pour Remote Procedure Call) utilisés pour la création et la destruction des threads et des processus est décrite ​ici.

On rappelle que le typage des segments de mémoire virtuelle, et la politique de réplication/distribution, sont décrits ​ici.

1. Comment est construit le PID identifiant un processus ? Quel est l'utilité de ce type d'encodage du PID ?
2. Pour un processus P s'étalant sur plusieurs clusters, il existe un descripteur de processus dans chaque cluster contenant au moins un thread de P. Parmi toutes ces copies, on distingue le cluster owner, le cluster reference et des clusters copy. Quel est le rôle de chacun ?
3. À part le cas (non implémenté actuellement) de la migration complète d'un processus mono-thread, Almos-mkh ne supporte pas la migration des threads dans le cas général ? En quoi ce choix simplifie-t-il l'ordonnancement des threads ? En quoi la migration de thread peut-elle dégrader les performances ? Dans Almos-mkh, quel problème - plus grave - interdit en pratique la migration des threads ?
4. Combien y a-t-il de types de thread ? A quoi correspondent ces différents types ?
5. Qu'est-ce que la VSL ? Quels sont les différents types de VSEG d'un processus utilisateur (autres que les VSEGS permettant l'accès au code et aux données du noyau lors des appels système) ? Qu'y a-t-il dans une GPT ?
6. Quand un process est sur plusieurs clusters, pourquoi chaque copie de La VSL, dans chaque cluster, n'est-il pas une simple copie (éventuellement incomplète) du contenu de la VSL du cluster de référence ?
7. Pourquoi a-t-on un problème de cohérence entre les différentes copies de la VSL d'un même processus dans différents clusters ?
8. Dans la création d'un nouveau process, quel est le rôle de fork() et quel est le rôle d'exec() ?
9. Ou se trouve le bit COW (Copy On Write) ? A quoi sert-il ? Est-il toujours utilisé ? A quel moment est-il modifié ?
10. Soit un process P avec 3 threads T0, T1 et T2. T1 exécute fork() mais pas exec(). Combien aura-t-on de process et de threads par process ?
11. Qu'est-ce qu'une RPC ?
12. Quelle différence y a-t-il entre une RPC simple et une RPC parallèle ?
13. Il existe deux modes de terminaison d'un thread, par suicide ou meurtre. Quel appel système correspond à un suicide ? Quel appel système correspond à un meurtre ? Quelle est la fonction système appelée dans ces deux cas ? Pourquoi est-il plus simple de terminer un thread s'exécutant en mode détaché ?

Travaux pratiques

Remarques préliminaires

1. Pour faciliter le parcours du code, vous pouvez utiliser Visual Studio Code et ouvrir le répertoire Almos-mkh. Tous les fichiers d'Almos-mkh apparaissent alors dans la colonne de gauche. Vous pouvez par exemple ouvrir kernel/kern/process.c et ensuite parcourir le code en hyper-texte.

2. L'application idbg.elf est lancée par load /bin/user/idbg.elf. Cette application permet d'afficher dans la fenêtre term0 l'état de certaines structures du noyau.
   • La commande h permet d'obtenir de l'aide.
   • La commande p, affiche le nombre de processus sur le cluster 0.
   • La commande s, affiche le nombre de threads alluoués au core 0 du cluster 0.

3. Pour modifier la plateforme, vous devez éditer le fichier almos-mkh/params-hard.mk, par exemple pour passer de 1 à 2 clusters, changez l'état de la variable Y_SIZE. Puis vous devez suivre les étapes ci-après:
   • Recompiler Almos-mkh pour produire le disque,
   • Puis recompiler le preloader (dans tsar/softs/tsar_boot/) pour produire la rom.
   • Puis recompiler le simulateur,
   • Puis exécuter le simulateur avec ./simul -THREADS N. THREADS est le nombre de threads d’OpenMP. Avec 2 clusters, on demande 2 threads d'OpenMP sur 2 cores du PC (votre PC a 6 cores et N doit être inférieur ou égal à 6).

Vous allez exécuter une application sur une plateforme à 1 puis 2 clusters, en utilisant l'instrumentation proposée par Almos-mkh pour afficher les événements concernant les processus et les threads grâce aux variables DEBUG_PROCESS_xxx et DEBUG_THREAD_xxx présentes dans ​kernel/kernel_config.h. Rappelez-vous que quand vous modifiez le code du noyau, vous devez recompiler avec make clean ; make pour régénérer le disque, mais vous n’êtes pas obliger de recompiler le preloader et le simulateur.

Commençons par une plateforme de 1 cluster de 1 core.

• Démarrer le simulateur et exécuter l'application hello.elf et l'application idbg.elf. Chaque application doit être lancée dans un terminal différent. Commencez toujours par démarrer idbg.elf avant hello.elf (à cause de la vitesse du simulateur). Les étapes de fork() et exec() des process ksh s'affichent dans term0,
• Commentez les messages affiché sur le terminal 0 concernant le ksh [n°1] (vous pouvez vous aider du code des fonctions sys_fork() et sys_exec() (dans le noyau) qui se trouve ici : ​kernel/kern/process.h et ​kernel/kern/process.c).
• Notez les dates de création des process et des threads.
• Afficher l'état de l'espace d'adressage du process hello.elf.

Vous allez maintenant utiliser 2 clusters de 1 cores. Vous allez suivre la création du process hello.elf grâce aux messages écrits par le noyau et en regardant le code du noyau.

• Modifiez l'état des variables DEBUG_RPC_PROCESS_MAKE_FORK et DEBUG_RPC_THREAD_KERNEL_CREATE du fichier kernel/kernel_config.h pour voir les commandes RPC.
• Comme il y a 2 clusters, il y a de la réplication pendant la phase de boot (avant l'affichage de la bannière). Notez ce qui est répliqué et à quel moment.
• Avec idbg.elf (ou juste avec les messages du noyau) dîtes comment sont répartis les threads de l'application hello.elf.
• Représenter le graphe d'appel des fonctions sys_fork(), sys_exec() et sys_thread_create(). Dans ce graphe, vous ne faites pas figurer les arguments (c'est pour savoir quelles sont les fonctions appelées), vous ne mettez pas non plus le code de DEBUG.
• Représenter en pseudo-code la trace d'exécution du lancement de l'application hello.elf.