2014-12-02
Les systèmes d’exploitation modernes utilisent généralement les fonctionnalité de mémoire virtuelle des processeurs récents : cette fonctionnalité permet de découpler la mémoire physique, qui est limitée et dont les adresses sont fixées, et les espaces d’adressage virtuels, qui permettent de créer à la volée des layout pour la mémoire utilisée par les programmes.
La mémoire virtuelle fonctionne avec des tables de traduction : un espace virtuel est défini par une table de traduction, qui indique quelles portions de mémoire virtuelle correspondent à des portions de mémoire physique. Sur les systèmes x86, la mémoire physique et virtuelle est divisée en pages de 4ko : la correspondance virtuel-physique ne peut se faire que par blocs de 4ko. On appelle mapping le fait de faire correspondre une page physique à une page virtuelle.
L’avantage d’utiliser un tel mécanisme est que l’on peut avoir plusieurs tables de traduction pour chaque processus s’exécutant sur la machine : dans la table de traduction de chaque processus, on ne mappe de la mémoire que pour les portions dont le programme a réellement besoin, lui donnant ainsi l’impression de fonctionner seul sur la machine.
Dans cet article, nous allons discuter de l’allocation des pages de mémoire physique.
L’allocation d’un page physique peut avoir lieu pour plusieurs raisons :
Le troisième cas est plus problématique : en effet, les périphériques qui font du DMA n’accèdent pas à la mémoire virtuelle mais à la mémoire physique. En conséquence, si on veut réaliser un transfert de 16Ko de données par DMA, il faut pouvoir allouer 4 pages consécutives de mémoire physique, ou alors découper le transfert en morceaux de 4ko, ce qui fait perdre du temps inutilement.
Différents algorithmes permettent de réaliser cette allocation, avec à chaque fois un compromis entre simplicité, performances, et utilisation mémoire.
Cette solution peut permettre d’allouer plusieurs pages consécutives : il suffit de chercher k zéros consécutifs dans le bitmap. Cependant, dans le cas où la mémoire commence à bien se remplir, la fragmentation n’est pas forcément gérée de façon optimale, et le fait d’allouer et de libérer souvent des pages seules peut faire que l’on se retrouve avec beaucoup de petits trous (une seule page libre entre deux pages utilisées) et l’impossibilité d’allouer plusieurs pages consécutives.
Cette solution élémentaire est néanmoins optimale en terme d’espace mémoire utilisé, puisqu’elle ne nécessite que de stocker un bit d’information pour chaque page de mémoire physique.
Cette solution consiste à garder en mémoire une pile qui contient les pages libres du système : allouer une page consiste à prendre la page en haut de la pile, et libérer une page consiste à la remettre sur la pile.
La complexité algorithmique de cette méthode est optimale : toutes les opérations se font en temps O(1). Par contre, son empreinte mémoire est plus importante, puisque pour chaque page du système on a besoin d’enregistrer son numéro dans la pile, numéro qui prend naïvement 32 bits, et un peu moins avec optimisation (en effet, il y a au maximum 1M pages sur une machine 32 bits, ce qui peut être encodé sur 20 bits).
Une optimisation de l’utilisation mémoire pourrait être d’utiliser les pages libres elles-mêmes comme structure de donnée décrivant la liste des pages libres, vue comme une liste liée : l’empreinte mémoire de cette méthode devient ainsi nulle. Le problème est qu’il faut pouvoir mapper la première page libre quelque part dans le noyau afin de pouvoir lire dessus l’adresse physique de la prochaine page physique libre. Cela a l’inconvénient que pour l’allocation de plusieurs pages, on doit faire un nombre important de remappages dans l’espace noyau (un par page à allouer), chacun étant potentiellement cher en cycles processeur, puisqu’il faut à chaque fois invalider le cache de traduction (TLB), ainsi qu’aller lire des données dans une page qui n’est sans doute pas en cache. Dans le cas du bitmap, l’information sur les pages physiques est très localisée en mémoire, ce qui fait qu’un parcours du tableau peut se faire finalement assez rapidement.
Un autre désavantage de cette méthode est qu’elle ne permet pas d’allouer plusieurs pages consécutives. Pour palier à ce défaut, on peut décider par exemple de réserver un certain nombre de pages du systèmes pour être utilisées par groupe de 2, 4, 8 par exemples, et de maintenir une liste/pile de groupes de pages libres de toutes ces tailles différentes.
Cette solution se base sur la méthode bitmap, mais elle utilise plusieurs niveaux de bitmaps : il y a k bitmaps, et le bit i du bitmap k indique si le groupe de pages 2ki jusqu’à 2k(i+1)-1 est entièrement libre ou non. Il y a néanmoins une subtilité : si une page est marquée comme libre car utilisée dans un groupe de niveau k, alors elle est marquée occupée dans tous les niveaux k-1, k-2, …, ce qui fait que l’allocation de pages seules s’arrange pour détruire le moins possibles des groupes potentiels de plusieurs pages successives.
Cette méthode est détaillée dans cet article de l’excellent wiki du site OSDev.
Cette méthode a l’avantage d’être compacte en mémoire (une analyse rapide indique que l’on stocke un peu moins de deux bits d’information pour chaque page). Le temps d’allocation pose autant problème que dans le cas de l’algorithme bitmap, mais on n’a pas le problème de fragmentation. On perd en revanche la simplicité des deux méthodes précédentes : l’algorithmique de cette méthode est clairement un peu plus compliquée…
L’étape actuelle du développement de macrO.Scope est celle où l’on pose des fondations solides, sur lesquelles on préfèrerait ne pas avoir à revenir. Il reste à établir fermement le choix du système d’allocation que je vais utiliser, mais la première intuition est qu’il faut faire comme Linux. En tout cas l’option d’utiliser les pages libres elles-mêmes comme liste liée de pages libres me parait assez mauvaise et surtout ne peut pas être implémentée avant la pagination, ce que j’aimerais pouvoir faire.
Au boulot !