Une deuxième technique : la pagination

Une autre amélioration possible (et souvent retenue) est l'utilisation d'allocations non contigües : pagination et/ou segmentation.

L'allocation contiguë est très contraignante et entraîne généralement une fragmentation externe importante, qui de surcroît augmente avec le temps. Une solution consiste à découper en morceaux le processus, et d'allouer indépendemment pour chacun des morceaux une zone mémoire.

Mémoire virtuelle

La mémoire virtuelle est une technique autorisant l'exécution de processus pouvant ne pas être complètement en mémoire.

La mémoire logique (utilisable par le programmeur) est plus grande que la mémoire physique.

Processus i			1	3		5										...
Processus j		2								5			4			...

Il faut gérer l'information :

Processus i
pages	cadres
2	1
3	3
5	5

Processus j
pages	cadres
1	2
10	5
13	4

Mémoire
cadres	processus	ecriture	modifiée
0
1	i	x	x
2	j	x
3	i
4	j	x	x
5	i,j

Le partage des cadres par plusieurs processus permet :

• le partage de données et ainsi la communication inter processus.
• le partage de code (réentrant) et donc une optimisation importante de la mémoire. Par exemple, les fonctions des bibliothèques dynamiques ne sont chargées qu'une seule fois.

Pour éviter une recherche (même dichotomique) dans la table des pages d'un processus, il est nécessaire d'avoir une table indicée par les pages, et donc un champ qui indique sa présence où non dans un cadre.

Une adresse logique est alors constituée de :

numéro de page	déplacement dans la page
p	d
(m-n) bits	n bits

Le matériel nécessaire à la pagination (schéma page 269)

Supposons une mémoire de $2^{32} = 4 Giga$ et une taille des pages de $2^{12} = 4 K$. La taille de la table des pages peut posséder $2^{20} = 1 M$ entrées, et ne loge donc pas dans une page, elle est donc paginée.

Tables à plusieurs niveaux

Une amélioration consiste à utiliser une table de pages à plusieurs niveaux.

indice page principale	indice page secondaire	décalage
p1	p2	d
10	10	12	pour un 80386

La page principale est en mémoire et seule les pages secondaires nécessaires également (entrées de la table primaire marquées présentes).

Mémoire associative

Une autre amélioration consiste à utiliser une mémoire associative. C'est une mémoire cache matérielle avec un nombre d'entrées restreint (32, 64), et qui permet d'associer en un seule cycle le numéro du cadre à un numéro de page, si l'entrée est présente. Ce dispositif est efficace s'il répond à 95/100 des requêtes.

Tables inverses

Avec les adresses 64 bits, les tables de pages deviennent très très grande. Une solution consiste à utiliser une table des pages inversée commune à tous les processus et d'une fonction de hachage.

Les propriétés de la mémoire virtuelle

taille du processus :

il n'est plus nécessaire d'estimer la taille d'un processus, on lui fournit des pages au besoin.

fragmentation interne :

Statistiquement $F_i = (N \times T) / 2$ ou $N$ est le nombre de processus en mémoire, et $T$ la taille d'un bloc (une page). $F_i$ est donc une fonction linéaire de la taille du bloc, il suffit donc de diminuer la taille des blocs pour diminuer la fragmentation interne.

Diminuer la taille des blocs va engendrer d'une part des sur-coûts de gestion des blocs; d'autre part un ralentissement des performances d'entrées-sorties.

Une fois de plus, il faut trouver le bon compromis.

fragmentation externe :

nulle : chaque cadre libre est utilisable.

liaison d'adresse :

le code doit être relogable. Il faut une table des pages et une valeur de translation par cadres de page.

Défauts de pages

C'est le traitement par logiciel des pages marquées absentes pendant le déroulement d'une instruction. Il faut :

1. arrêter l'instruction,
2. trouver un cadre libre (au besoin en libérer un),
3. charger la page,
4. relancer l'instruction. Il faut pour cela que le processeur ait sauvegarder le contexte du début de l'instruction. (impossible sur 68000)