TP9 : Mémoire virtuelle paginée

1. Objectifs

Dans les architectures manycore à espace d'adressage partagé, mais physiquement distribué (architectures NUMA), telle que l'architecture TSAR, ou les serveurs de calcul à base de processeurs Intel, 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.

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.

2. 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 peut utiliser une technique de radix-tree pour réduire son encombrement.

3. 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.

4. 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 ?

5. Questions sur la politique de réplication & distribution

1. Comment 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 un radix-tree à 2 niveaux. La table des pages des processeurs Intel64 est un radix tree à 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 ?