PAGINATION
PAGINATION
La technique de pagination (paging) est l’un des mécanismes d’allocation de la mémoire à un processus. Elle consiste à diviser la mémoire physique (RAM) en cases ou cadres de page (page frame) et la mémoire virtuelle en pages de même taille que les cadres de page.
Sur les systèmes à mémoire virtuelle, les adresses manipulées par les programmes sont des adresses virtuelles et ne peuvent pas immédiatement être placées sur le bus d’adresse mémoire (pour lecture ou écriture) comme c’est le cas pour les systèmes sans mémoire virtuelle. Il se pose donc un premier problème : comment est faite la correspondance entre les adresses virtuelles fournies par les programmes et les adresses physiques manipulées par le processeur ?
La pagination consiste à diviser l'adressage de la mémoire en deux couches :
• La couche logicielle utilise un espace d'adressage plus grand que la mémoire physique effectivement disponible (l'espace des adresses linéaires, autrement appelé mémoire virtuelle ou mémoire linéaire). Par exemple l'allocateur de mémoire attribue aux processus ou aux segments de la mémoire virtuelle.
• La mémoire linéaire est divisée en pages. A un moment donné, certaines pages sont en mémoire physique, d'autres sont sauvegardées sur disque. Une couche matérielle pilotée par le SE (grâce aux tables de pages) est chargée de lire les données qui sont en mémoire, charger en mémoire les pages demandées absentes, décharger les pages inutilisées pour faire de la place.
Mécanisme de pagination Principes généraux
Nous allons maintenant évoquer un fonctionnement plus complexe qui permet une grande souplesse dans le chargement des programmes. Il devient possible d'exécuter des processus dont la taille est très largement supérieure à celle de la mémoire physique. L'image d'un programme, sur le disque, est constituée au moins de deux segments, l'un pour les instructions, l'autre pour les données. Chaque segment est lui-même constitué d'un ensemble de pages, pour exécuter le processus on peut se contenter de charger un nombre limité de pages. Le chargeur (ou loader) utilise pour cela un dispositif de pagination qui établit la correspondance entre les adresses des pages dans le module exécutable sur le disque et celles des zones de la mémoire physique où ces pages sont chargées. Dans ce dessin on a schématisé la façon dont deux pages d'un programme peuvent être chargées et adressées à travers cette fonction de pagination. Ce dispositif connaît, à tout instant, la liste des page libres dans la mémoire de façon à pouvoir en charger de nouvelles. Fonctionnement Comme les pages correspondant aux segments de données évoluent au cours de l'exécution elles doivent absolument être copiées dans le swapfile avant le chargement en mémoire. Au début de l'exécution un certain nombre de pages sont chargées dans la mémoire physique et le travail peut commencer. Lorsqu'une page de données doit être déchargée, elle est d'abord recopiée à son emplacement dans le swapfile. Lorsqu'un programme réclame une adresse dans une page qui n'est pas chargée, cela déclenche le mécanisme de pagination qui doit :
- trouver l'emplacement nécessaire pour charger la page manquante
- provoquer ce chargement
- calcule le numéro de page à charger à partir de l'adresse demandée par le processeur.
- charge la page manquante et indique que la zone de mémoire allouée est maintenant occupée.
- il est moins onéreux de remplacer une page qui n'a pas été modifiée en mémoire car il est inutile de la recopier dans le fichier de pagination : elle y est déjà inscrite. Une page d'un segment de code est donc préférable à une page d'un segment de données qui aura certainement été modifiée depuis son chargement.
- une page allouée à un seul processus provoquera ultérieurement moins de défauts de page, si elle est enlevée, qu'une page partagée entre plusieurs.
- une page qui n'a pas été utilisée depuis longtemps a également moins de chance de provoquer un défaut. C'est pourquoi il faudrait inscrire la date exacte de dernière utilisation mais comme cela serait très onéreux en temps et en place, on se limite à mettre un bit à 1. Régulièrement un processus remet tous les bits de toutes les pages à zéro. Les pages dont le bit est levé ont donc été utilisées depuis le dernier passage et sont conservées si possible. • Les processus d'allocation de page demandent beaucoup de ressources. Il faut allouer à un processus, dés son démarrage, un espace raisonnable, puis par la suite charger des groupes de pages contiguës. Les politiques, sur ce point, dépendent de la réalisation du système d'exploitation. Elles ne sont pas les mêmes pour les différents systèmes qui existent sur le marché. On comprend donc que la pagination est un mécanisme extrêmement coûteux en entrées-sorties. On cherche à obtenir le maximum de performances au moyen de fonctions spécialisées. Un exemple de fonctionnement est résumé ci-dessous. Les programmes sont tous d'abord copiés dans le swapfile. Puis, au fur et à mesure des besoins des pages sont chargées ou déchargées. Le swapfile doit donc être assez grand pour contenir toutes les images des programmes actifs. L'expérience montre qu'il n'est pas raisonnable que sa taille soit supérieure, dans la plupart des cas, à trois fois la taille de la mémoire physique. On remarquera que le swapfile peut se trouver morcelé, on utilisera des méthodes équivalentes pour le compacter. La pagination à un niveau Le mécanisme de traduction des adresses virtuelles en adresses réelles doit associer à chaque numéro de page virtuelle le numéro de case réelle qui contient cette page, si elle existe. La pagination à deux niveaux La pagination à un niveau d'un espace virtuel de grande taille peut conduire à des tailles importantes de la table des pages. L'exemple précédent de VAX-VMS montre une approche pour réduire cet encombrement, mais impose des contraintes sur la gestion des objets à l'intérieur même de cette mémoire virtuelle, puisqu'il faut qu'ils se trouvent au début ou à la fin de l'espace du processus. La pagination à deux niveaux a pour but de réduire la représentation de la table des pages d'un processus, sans avoir des contraintes aussi fortes. Pagination étendue Les Pentiums ont amené la pagination étendue. Les pages physiques ont une taille de 4KB ou 4MB dans ce cas, l’adresse linéaire est divisée en 2 champs : - Directory : 10 bits les plus significatifs - Offset : les 22 bits restants Entrées dans le répertoire - Flag Page Size mis à 1 - Les 10 bits de poids fort seulement sont nécessaires (multiples de 4MB) Les deux paginations peuvent cohabiter. Utilisés pour gérer des gros blocs de mémoire contigus
La segmentation vis à vis de la pagination
La segmentation et la pagination sont deux notions différentes qui sont utilisées conjointement sur certaines machines (par exemple, Multics, iAPX386). La segmentation doit être vue comme une structuration de l'espace des adresses d'un processus, alors que la pagination doit être vue comme un moyen d'adaptation de la mémoire virtuelle à la mémoire réelle.
• Avec la segmentation, le processus dispose d'un espace des adresses à deux dimensions que le processeur transforme en une adresse dans une mémoire linéaire. Sans la segmentation, le processus dispose directement de cette mémoire linéaire.
• Avec la pagination, on dispose d'une fonction de transformation dynamique des adresses de la mémoire linéaire en adresses de la mémoire physique, qui permet de placer les pages de la mémoire linéaire dans des cases quelconques de mémoire physique. Sans la pagination, les pages de la mémoire linéaire doivent être placées dans les cases de la mémoire physique de même numéro.
AVANTAGES DE LA PAGINATION
La pagination permet:
- une meilleure utilisation de la mémoire en diminuant au maximum la fragmentation : il n’y a aucune création de trous inutilisables entre les programmes.
- d’avoir un espace virtuel très grand quelque soit (ou presque) la quantité de mémoire physique disponible.
- La pagination permet donc, sur une machine donnée, d’exécuter des programmes plus grands que la mémoire physique.
INCONVENIENTS DE LA PAGINATION
La taille des tables de pages peut devenir très importante si l’espace virtuel est très grand (chaque processus devant avoir sa propre table) : ceci peut obliger à ranger les tables de pages dans un espace virtuel, lui-même paginé. Il faut alors, pour éviter une traduction d’adresse trop longue que le système soit aidé par des dispositifs matériels. Un processus ne peut pas utiliser simultanément deux routines qui ont été construites à la même adresse dans l’espace virtuel. La structure d’espace virtuel obtenue avec la pagination est identique à celle obtenue avec les registres de base. C’est la structure linéaire d’un grand tableau contigu.
* http://fr.wikipedia.org/wiki/Pagination_%28informatique%29