Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 4
Plus grand svp ! Organisation et gestion de la mémoire
Année 2002-2003

Suite N°1...

4.2 PAGINATION
                       Un livre, un lutrin et des photocopies.

La première pagination était dans l'Atlas, ordinateur de Ferranti et de l'université de Manchester en 1961.

Principe de la pagination.

Une page est un ensemble connexe d'emplacements de mémoire. Les pages ont toutes la même dimension. La mémoire est entièrement paginée ou ne l'est pas tout. La pagination réalise un pavage régulier de la mémoire réelle et de la mémoire virtuelle s'il y a lieu.

Les pages sont créées par une gestion particulière de l'espace d'adressage. Elles n'impliquent pas de modification des bancs de mémoire. Elles ont une réalité logique et non physique. La création de pages est faite en séparant les adresses en deux champs jointifs, l'un contenant les bits de poids fort, l'autre contenant les bits de poids faible. Cette manipulation induit la notion de page sous la forme :

• de l'adresse basse, bits de poids faible, dite adresse dans la page;
• de l'adresse haute, bits de poids fort, dite numéro de page.

La pagination est une structure du support.

Ainsi, pour un adressage total sur 32 bits soit 4 Go (adresses linéaires), si le champ d'adresse basse est de 12 bits, la page a pour taille 4 Ko. Il reste 20 bits en partie haute qui induisent 1 M pages. La pagination est un jeu d'adressage, elle s'applique à la mémoire virtuelle.

Soit une adresse complète, figurant en position d'argument dans une instruction. Que peut-il se passer ?

Si la pagination n'existe pas, deux cas se présentent :

• ou bien le mot d'adresse spécifiée existe réellement en mémoire centrale et l'accès sera fait à partir du bus;
• ou bien il y a défaut de mémoire car ce mot n'y existe pas. L'accès est alors au mieux refusé explicitement (défaut de mémoire), au pire est ignoré, entraînant alors une exécution erronée du programme.

Le processeur National Semiconductor 32032 date de 1985, il avait une capacité d'adressage de 24 bits soit 16 Mo, il était le premier de la série 32000 qui se poursuit. Les informations qui suivent NE SONT PAS UNE DESCRIPTION COMPLÈTE NI CONFORME du NS32032, elles s'en inspirent. Il applique la pagination de façon dépouillée sans mélange avec une segmentation. Elle utilise trois champs jointifs et non deux.

L'espace adressable total est pavé de pages de 512 octets, accessibles en deux étapes, l'une d'indirection, l'autre d'indexation. L'adressage fait appel à trois champs d'adresse :

• l'adresse dans la page de 512 octets par le champ C de 9 bits, poids faibles;
• l'adresse de la page, à prendre dans une table à 128 entrées, sélectionnée par le champ B de 7 bits, poids moyens;
• l'adresse de la table de pages, à prendre dans une table des tables à 256 entrées, sélectionnée par le champ A de 8 bits, poids forts.

L'opération se fait par deux sélections successives :
- sélection de la table des pages : contenu d'adresse A dans la table des tables;
- sélection de la page, contenu de l'entrée B de la table des pages.

Le schéma ci-dessous présente les cheminements qui, à partir de l'adresse interne à un programme, déterminent l'adresse effective en mémoire.

A est l'adresse de début de la table des tables. Elle a 256 entrées, chaque entrée de 24 bits est l'adresse d'implantation de la table qui peut ainsi être logée en un emplacement quelconque en mémoire. Cet accès fonctionne en indirection.

B est le numéro de la page à l'intérieur de la table des pages dont la table des tables a donné l'adresse de début. La table des pages a 128 entrées, chaque entrée a une longueur de 15 bits. Elle est considérée comme les 15 bits de plus fort poids d'une adresse, elle pointe l'une quelconque des pages de la mémoire.

C est l'adresse dans la page, c'est un déplacement à concaténer avec les 15 bits précédents pour obtenir une adresse sur 24 bits.

Si les 16 Mo sont câblés, le fonctionnement est direct.

Le lecteur remarquera les nombres suivants et leur pertinence :

La page a 512 octets, taille normale d'un secteur de disque en vue du stockage.

L'adresse dans la table + l'adresse dans la page a 16 bits, correspondant à 64 ko, c'est à dire la taille de la mémoire des processeurs à 8 bits précédant cette génération. Un segment des Intel 8086 avait 64ko au plus.

Gestion de la mémoire virtuelle.

Si les 16 Mo ne sont pas câblés, il faut gérer les pages indépendamment de leur localisation physique, mémoire centrale ou externe. La mémoire externe doit contenir pour cela une zone d'au plus 16 Mo, image de la mémoire centrale totale possible, nécessairement gérée par le système d'exploitation. Un indicateur associé à chaque entrée de la table des tables (a) dit si toutes les pages de la table correspondante sont ou ne sont pas en mémoire câblée. Un indicateur de même nature attaché à chaque entrée de la table des pages (b) dit si la page est ou n'est pas en mémoire câblée. La gestion des emplacements peut ainsi être faite soit par blocs de 64 ko présents ou absents dans leur totalité de la mémoire, soit par page. Le bloc n'est pas nécessairement d'un seul tenant. Chaque page est autonome pour ce qui est de sa position dans la mémoire centrale. Si la page adressée est en mémoire centrale, l'adressage se poursuit. Si elle ne l'est pas, le dispositif de transfert est activé. Il demande au système d'exploitation une adresse de page libre, écrit son adresse réelle dans la table des pages, lit la page en cause dans la mémoire externe, charge la page et met à jour les tables.

On a fait ici l'hypothèse que la page de la table (b) était chargée et donc son bit de présence valait 1.

Le lecteur curieux trouvera la description détaillée du NS32532, successeur actuel de la même famille dans http://www.national.com.

REMARQUONS que l'adresse physique est une CONCATÉNATION de deux adresses.

La pagination est une technique utilisée pour implanter par morceaux un grand espace linéaire d'adresses dans un espace câblé disponible plus petit. On a parfois estimé que la baisse du coût de la mémoire centrale rendrait ce dispositif inutile. Néanmoins, comme il est toujours moins coûteux d'ajouter un bit à un registre d'adresse que de câbler une mémoire de taille double, la pagination conserve un avenir.

L'exemple ci-dessus a une complexité intermédiaire, il contient un étage de plus que la description de base sous la forme de pages et d'une seule table des pages. La réalisation peut être encore plus complexe quand le système d'exploitation crée des machines virtuelles à la demande. Chacune aura alors son dispositif propre de mémoire virtuelle.Ces manipulations de pages sont le fonctionnement courant de la mémoire.
Le chargement d'un nouveau programme consiste à lui allouer des pages virtuelles et ensuite réelles en quantité suffisante.

La pagination gère l'espace de mémoire considérée comme CONNEXE de 0 jusqu'à sa taille maximale utile. Elle est INDÉPENDANTE des contenus.

Protocoles de remplacement des pages

Quand la page nécessaire n'est pas en mémoire centrale, on dit qu'il y a défaut de page (miss) comme pour le défaut de ligne dans un cache. Un emplacement doit être trouvé pour l'y loger. Si tous sont occupés, il faut choisir celui qui sera libéré. Plusieurs algorithmes existent. Avant leurs énoncés, remarquons que cette question est la même que celle que l'on a vue pour le remplacement des éléments logés dans un cache.

Il n'y a pas de différence par rapport à ce que nous avons vu pour les caches. Le choix du protocole obéira à des critères différents parceque la page est beaucoup plus grande que la ligne de cache et donc :

• la demande est donc moins fréquente,
• plus de temps peut être consacré à exécuter un algorithme.

• Remplacement aléatoire, il consiste à choisir au hasard la page à éliminer. Son avantage est de traiter uniformément toutes les pages et tous les processus. Il n'est envisageable que si le nombre de pages en mémoire est grand.
• Premier entré premier sorti FIFO, il consiste à choisir la page la plus anciennement chargée. Il faut que l'heure de chargement de la page soit conservée. Cette heure est en général conservée dans une liste des numéros de pages ordonnée par date. Ce protocole est simple à concevoir. On s'aperçoit vite que nombre de pages ont été chargées il y a longtemps car elles sont d'utilisation permanente comme les pages du système ou la page de menu principal d'une application.
• La page la moins récemment utilisée LRU (least recently used), il consiste à choisir la page qui n'a pas été utilisée depuis le plus longtemps. On ne conserve pas l'heure de chargement mais l'heure de chaque utilisation. L'idée mise en application est qu'une page qui n'est plus utilisée depuis longtemps a peu de chances de l'être à nouveau. Il est indispensable d'avoir un circuit spécialisé pour entretenir la liste des heures associées aux numéros de pages ou encore la liste des pages accompagnées de leur heure.
• La page la moins fréquemment utilisée LFU(least frequently used), la méthode est voisine de la précédente à part le fait que l'on compte le nombre d'accès au lieu de changer une heure à chaque accès. Il faut prendre une mesure de sauvegarde pour les pages chargées en dernier qui n'ont pu accumuler un compte significatif.
• La page qui n'a pas été récemment utilisée NRU (not recently used), la marque associée à chaque page est plus courte, un seul bit ici. Quand une page est chargée, ce bit est mis à zéro, il ne repassera à un que lors d'un accès nouveau. La recherche de la page à éliminer se ramène à l'une des pages dont le bit est à zéro. Ce système, dans son principe, supprime l'inégalité due à l'heure d'utilisation. Pour éviter de n'avoir pas de page à éliminer et remettre en quelque sorte la pendule à l'heure, on met à zéro tous les bits assez fréquemment.

Chacun des protocoles a qualités et défauts. Les qualités sont un fonctionnement convenable en situation courante. Les défauts apparaissent dans des cas particuliers :

• en FIFO, les défauts apparaissent quand le couple programme-données utilise effectivement un espace grand par rapport à la mémoire réelle;
• en LRU, les défauts apparaissent quand le couple programme-données contient soit des boucles de programmes soit des tables de données de grande dimension;
• en LFU, une page qui a été beaucoup utilisée, par exemple pour une boucle, var este en mémoire longtemps après la fin de la boucle;
• en NRU, une page dont l'utilisation est quasi périodique à fréquence faible sera presque toujours éliminée.

Toutes les mémoires sont des espaces. Il est normal d'y utiliser les mêmes protocoles pour y faire de la place quand il n'y en a plus.

Autre dispositif utile, la table en un coup d'œil

Ce dispositif est connu sous le nom de TLB ou TLAB, translation look-aside buffer. On considère que les pages les plus récemment utilisées le seront à nouveau (la notion de localité). C'est un cache pour la table des pages. On y enregistre les entrées de la table des pages utilisées récemment. Le petit nombre d'entrées rend possible la technique associative.

Des configurations usuelles sont :

Machine	Date	Nombre d'entrées	Type
MIPS R10000	1996	64	associatif
PowerPC 601	1993	Données: 256 Instructions: 4	associatif à deux blocs
HP PA7100	1993	120	associatif