[OS]La pagination

Il y a déjà un petit moment que je voulais sorti cet article mais bon vous savez ce que c'est, les cours, les devoirs, la flaime et vla quoi.
Donc je me décide à prendre ma patience en main et à me décider à prendre un peu de temps pour écrire cet article qui sera surement le début d'une série d'article concernant les mécanismes des OS modernes.
Ces articles se baseront sur mes recherches, car comme je l'avais annoncé il y a un petit moment je me suis lancé dans la conception d'un kernel minimaliste.

Ce premier article va parler de la pagination qui est au cœur de tout les systèmes de swap et de partages de la mémoire, elle est donc omniprésente dans tout les OS modernes à savoir pour les plus connus Windows, Linux, Mac OS, Solaris, freebsd et bien d'autres encore.

La pagination est une technique basé sur une double indirection ( je reviendrais sur ce terme plus tard ) qui sert à étendre la mémoire virtuelle jusqu'à un maximum de 4Go quelque soit la RAM disponible, c'est donc un mécanisme extrêmement performant implanté directement dans la MMU ( Memory Management Unit ) qui est elle même généralement inclus dans les microprocesseurs récents, et c'est donc pour cela qu'elle est très largement utilisé dans tout les OS modernes.
Elle permet aussi selon sa configuration de séparer différentes parties de la mémoire notamment le cloisonnement des processus et pourra donc être utilisé pour détecter des tentatives de violation d'accès.

Dans les années 60 la mémoire physique ( RAM ) était très limitée de part son prix élevé, c'est pour cela que des mécanismes de mémoire virtuelle ont été inventé. Parmi ces mécanismes ont retrouve la segmentation ( que je présenterais surement pas car elle n'est pas très intéressante ) et la pagination ( qui est le sujet du présent article ).

Les adresses manipulés par le CPU sont entièrement fictives, c'est la MMU qui se charge de savoir si l'adresse fictive correspond à une adresse physique, si tel est le cas alors il donne l'accès au CPU à cette adresse sinon il demande à l'OS de trouver l'emplacement mémoire correspondant, si l'OS ne trouve pas de correspondance alors il le signale au CPU ( segfault, violation d'accès ) sinon il swape l'emplacement mémoire en RAM et donne l'accès à cet emplacement au CPU, si aucune place en RAM n'est disponible l'OS va alors swaper un morceau de la RAM peu utilisé vers une mémoire de masse généralement le disque dur.
Cette action est appelée traduction d'adresse car la MMU traduit des adresses fictives en adresses physiques.

Ceci laisse donc penser que la MMU dispose de tables de traductions faisant la correspondance adresses fictive --> adresses physique pour chaque adresse fictive de la mémoire virtuelle. Ceci demanderai beaucoup trop de mémoire, c'est donc pour cela que la mémoire est partagée en page de 4Ko ou 4Mo selon la configuration de la pagination, il suffit ensuite de connaitre l'offset pour retrouver l'adresse physique.

Revenons maintenant sur le terme de double indirection qui est au coeur de toute la puissance de la pagination avec un petit shéma ( tiré de la doc intel ).




On peut voir sur ce schéma que l'adresse fictive est découpé en trois parties égales :
* bit 31-22 : l'index de la PDE ( Page Directory Entry )
* bit 21-12 : l'index de la PTE ( Page Table Entry )
* bit 11-0 : l'offset de la page

Ces trois parties de l'adresse fictive représente chacune 11 bits soit exactement soit exactement 4Ko adressables pour chacune des parties.

La première indirection concerne la PD ( le registre cr3 conserve son adresse ), la première partie de l'adresse fictive sert donc à repérer le PDE correspondant à l'adresse fictive, ce PDE est en fait un pointeur sur la PT correspond à l'adresse avec en plus quelques données sur les privilèges requis et quelques autres petites choses, c'est à ce moment que survient la seconde indirection avec la deuxième partie de l'adresse fictive qui sert elle à repérer le PTE correspondant qui est elle même un pointeur sur une page physique avec les mêmes données que pour la PDE, enfin la traduction se finit grâce à l'offset qu'on ajoute à l'adresse de la page physique.

Comme le montre ce schéma la PD a exactement 1024 PDE, chaque PDE correspond à une PT, chaque PT a 1024 PTE et chaque PTE correspond a une page physique.
Ce qui fait 1024*1024 pages physiques adressables, comme chaque pages physiques correspond à 4Ko il y a 1024*1024*(1024*4) soit 4Go.

Certains processeurs implémente des mécanismes avec 3 indirections ce qui augmente encore la mémoire physique, il est aussi possible de travailler avec des pages de 4Mo et d'utiliser seulement un PD ce qui revient au même étant donner qu'il y aura 1024 pages de 4Mo ce qui fait bien 4Go et les 22 bits de l'offset corresponde bien au 4Mo adressables de la page.

Les informaticiens se sont rendu compte que certains espace mémoire étaient plus sollicité que d'autre, ils ont donc décidé de mettre en place un cache de traductions d'adresses ( le TLB pour Translation Lookaside Buffer ). Ce cache conserve un certains nombres de traductions d'adresses et il permet d'accélérer la phase de traduction d'adresse car si on regarde un peu mieux le schéma on se rend compte qu'il faut 3 accès à la RAM pour chaque accès à la mémoire virtuelle.


C'est la fin de cet article, je pense que mon prochain article portera sur une technique très particulière de pagination que j'ai moi même utilisé et que je trouve très intéressante car extrêmement simple mais aussi très ingénieuse.

* http://fr.wikipedia.org/wiki/Pagination_%28informatique%29
* Doc Intel Vol 3 --> Chap 3.6 Paging ( Virtual memory )
* http://sos.enix.org/wiki-fr/upload/SOSDownload/sos-texte-art4.pdf
( article très intéressant sur la pagination et sa mise en place )