Algorithmes de pagination

Lors d'un défaut de page, si tous les cadres sont utilisés, il faut en libérer un afin de pouvoir y mettre la nouvelle page.

Le choix de la page à évincer est crucial.

Soit une mémoire comportant 5 cadres :

Numéro de cadre	1	2	3	4	5
Numéro de page	7	2	5	1	9

et une demande pour la page 3.

Algorithme optimal

La solution optimale consiste à évincer la page dont l'occurrence de la prochaine utilisation est la plus éloignée dans le futur.

Supposons que la suite de références aux pages soit 3, 9, 4, 3, 2, 1, 2, 7...

La page à évincer est la page 5 qui est la seule à ne pas apparaître dans cette liste. La nouvelle configuration mémoire est donc :

Numéro de cadre	1	2	3	4	5
Numéro de page	7	2	3	1	9

Propriétés

L'algorithme précédent :

• minimise le nombre de défauts de page,
• n'est pas implémentable (hormis dans certaines requêtes dans un SGBD), car il fait l'hypothèse de la connaissance du futur.

LRU : Least Recently Used

L'idée est la suivante : futur = miroir du passé.

L'implémentation demande de stocker une date comme attribut de la table des pages, qui est mise à jour à chaque accès. Cette solution demande un accès à l'horloge pour chaque accès, c'est trop coûteux.

Il est possible d'approximer la date avec un tableau de n bits, plus n est grand, meilleur est l'approximation. Chaque accès provoque un décalage vers la droite de toutes les dates (1 pour la page accédée, 0 pour les autres). La plus petite valeur indique la page la moins récemment utilisée.

FIFO

La date de chargement est inscrite (une seule fois) dans la table des pages. la plus ancienne est évincée.

L'algorithme FIFO possède l'anomalie de Belady : Il existe des suites de requêtes s, telles que :
nombreDefautsPage(s, n cadres) $<$ nombreDefautsPage(s, (n+1) cadres).

seconde chance et horloge

Horloge = FIFO + approximation du dernier accès par un seul bit R.

Quelques variantes

Sur la base des algorithmes précédents, il est possible de tenir compte également de :

• du bit de modification de la page. Une page modifiée doit être sauvegardée, ce qui prend du temps. Il est préférable de choisir une page non modifiée, mais attention aux pages de codes qui ne sont jamais modifiées.
• du nombre d'accès dans un intervalle de temps donné.
• du propriétaire des pages. Les pages peuvent être traitées globalement, où bien localement par processus. Dans ce cas on évince une page du processus qui provoque le défaut de page. Attention, pour qu'un processus fonctionne correctement, il faut lui assurer en permanence un nombre minimum de pages en mémoire.

Le principe de localité

Statistiquement, on constate que les suites de requêtes émises par un processus ne sont pas aléatoires. Pour chacune des pages accédées, la courbe du nombre d'accès en fonction du temps ressemble à une courbe de Gauss. Cela signifie que lorsque l'on charge une page, il est fort probable qu'elle va être beaucoup utilisée dans les instructions suivantes.

En fonction de ce principe, les algorithmes basés sur la date du dernier accès et/ou sur le nombre d'accès récent sont meilleurs que ceux basés sur la date du chargement et/ou le nombre d'accès depuis le début du processus.

Pré-chargement

Le pré-chargement s'oppose à la pagination à la demande, une page peut être chargée sans qu'elle soit demandée.

L'hypothèse correspond à un principe de localité physique et non pas temporel comme le précédent. Si le processus à besoin de la page $p$, il va sans doute avoir besoin dans peu de temps des pages $p-1$ et $p+1$. Celles-ci sont donc préchargées lors du chargement de $p$ sur défaut de page.

Une autre utilisation du pré-chargement est lié au va-et-vient. Lorsqu'un processus est replacé en mémoire, il est opportun qu'il retrouve tout de suite l'ensemble des pages qu'il avait au moment de sa sauvegarde sur disque.

Spool de cadres libres

Une amélioration consiste à avoir toujours un nombre de cadres libres supérieur à un seuil. Ainsi le traitement d'un défaut de page devient :

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

Il faut alors qu'en tâche de fond, un démon libère des cadres lorsque le nombre des libres devient proche du seuil. Il utilise un algorithme parmi les précédents.

1. choisir une page à évincer,
2. la sauvegarder si nécessaire,
3. ajouter le cadre à l'ensemble des cadres libres.

Une seconde optimisation consiste à se souvenir pour chacun des cadres libres de la dernière page contenue. Si celle-ci est de nouveau demandée, il est inutile de la rechargée (le cadre contient la bonne version), il suffit de retourner le bon numéro de cadres.