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.
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 |
L'algorithme précédent :
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.
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).
Sur la base des algorithmes précédents, il est possible de tenir compte également de :
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.
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 , il va sans doute avoir besoin dans peu de temps des pages
et
. Celles-ci sont donc préchargées lors du chargement de
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.
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 :
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.
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.