La table de pages
Chaque adresse émise par le processeur est traduite par le MMU et pour ne pas trop pénaliser les performances, cette opération doit être très rapide. Le MMU utilise une table de pages avec une entrée pour chaque page virtuelle. La traduction d’une page virtuelle en cadre de page est donc une simple lecture dans la table de pages à l’index correspondant au numéro de la page virtuelle.
En plus du cadre de page, chaque entrée de la table de pages contient en général les informations suivantes1:
- Un bit de présence qui indique si la page est mappée sur un cadre de page physique.
- Un (ou plusieurs) bit(s) de protection qui indique(nt) si la page est accessible en lecture et/ou en écriture.
- Un bit de modification qui indique si la page a été modifiée depuis sa dernière écriture en mémoire.
- Un bit qui indique si la page peut être mise en cache.
La figure ci-dessous illustre une telle entrée. La taille d’une entrée de la table de pages dépend du nombre de cadres de pages physiques.
Avec les premiers systèmes 16 bits, la table de pages était relativement petite (16 entrées) et elle était stockée dans une mémoire de type SRAM dans le MMU lui-même. Avec les systèmes 32 bits, la table de pages devient beaucoup plus grande (1 million d’entrées pour des pages de 4 KiB). Si une entrée de la table de pages occupe 4 octets, la table de pages occupe alors 4 MiB. Il n’est donc plus possible de la stocker dans le MMU lui-même et nous devons utiliser de la mémoire de type DRAM. Mais même dans ce cas, on me peut pas toujours se permettre d’utiliser autant de mémoire pour la table de pages. Surtout que nous n’avons pas seulement une table de pages, mais une table de pages par processus. Il faut donc trouver un moyen de réduire la taille de la table de pages.
Un gros défaut de la table de pages c’est qu’elle contient beaucoup d’entrées qui ne sont pas utilisées. En effet, seules les entrées utilisées (celles qui contiennent un cadre de page physique) sont utiles; les autres ne servent à rien. Mais il faut quand même les avoir pour permettre un accès rapide (indexé) à l’entrée correspondant à une page virtuelle donnée.
Avec un système embarqué de 32 bits, des pages de 4KiB, et 256KiB de mémoire physique, on n’utilise que 64 cadres de pages physiques sur le million possible. La table de page est donc à 99.9954% vide! Et de toute façon, une table de 4MiB n’a aucune chance de tenir dans 256KiB de mémoire!
Une solution possible consiste à utiliser des pages plus grandes que 4KiB. Le processeur ARM Cortex-A permet de définir des pages de 1MiB et la table de page ne doit alors contenir que 4096 entrées. La figureci-dessous illustre une telle table de pages.
Les tables de pages à plusieurs niveaux
Avec les pages de grande taille, on perd beaucoup en granularité et en flexibilité. Les pages de 4KiB ont démontré leur efficacité et on ne souhaite pas vraiment changer cette taille. La technique habituelle pour diminuer la taille des tables de pages consiste à utiliser des tables de pages sur plusieurs niveaux.
À la place de faire une grande table avec 1 million d’entrées, on fait une première table de premier niveau avec 1024 entrées et on fait encore 1024 tables de deuxième niveau avec 1024 entrées chacune. À première vue ça ne résout pas le problème, mais on peut maintenant ne créer que les tables de deuxième niveau qui sont effectivement utilisées. Toutes les pages de deuxième niveau qui ne sont pas utilisées n’existent simplement pas et on ne gaspille ainsi pas de mémoire.
La figure ci-dessous illustre une telle table de pages à deux niveaux.
La distribution des bits d’adresse entre les différents niveaux de la table de pages est arbitraire et dépend du système. Dans l’exemple de la figure ci-dessus, nous avons choisi d’utiliser les 10 premiers bits pour l’index dans la table de premier niveau et les 10 bits suivants pour l’index dans la table de deuxième niveau. Pour rappel, les 12 bits de poids faibles sont utilisés pour l’offset dans la page. On aurait aussi pu utiliser les 11 premiers bits pour l’index dans la table de premier et les 9 suivants pour l’index dans la table de deuxième niveau. Dans ce cas nous aurions eu 2048 entrées dans la table de premier niveau et 512 entrées dans les tables de deuxième niveau.
Pour le Cortex-A, la table de premier niveau utilise les 12 bits de poids forts de l’adresse virtuelle et la table de deuxième niveau utilise les 8 bits suivants. Ça nous donne donc 4096 entrées dans la table de premier niveau et 256 entrées dans celle de deuxième niveau. La figure ci-dessous illustre une telle table de pages.
Les entrées des tables de pages prennent 4 octets et la table de premier niveau contient utilise donc \(4 \cdot 4096 = 16'384 = \mathsf{16KiB}\) et les tables de deuxième niveau utilisent \(4 \cdot 256 = 1024 = \mathsf{1KiB}\).
-
Certains systèmes peuvent définir d’autres informations dans les entrées de la table de pages. ↩