Gestion de la mémoire centrale - Architecture des Machines et des Systemes Informatiques - page 342

d'adressage du processus en défaut de page. Dans le second cas, la page victime peut
appartenir à l'espace d'adressage de n'importe lequel des processus présents en
mémoire centrale. Ce dernier cas est le plus souvent mis en œuvre car il donne de
meilleurs résultats quant à l'utilisation de la mémoire centrale.
Le mécanisme de conversion d'une adresse logique < p, d > vers l'adresse physique

correspondante devient maintenant :
1. accès à l'entrée p de la table des pages du processus actif et test de la valeur du bit
de validation V;
2. si la valeur du bit V est à 0, alors il y a défaut de page.
3. une case libre est recherchée. Si il n'y a pas de cases libres, une page victime est
choisie. Si la valeur du bit M pour cette page est à 1, alors une opération d'entrées-
sorties est lancée pour sauvegarder la page victime ;
4. une opération d'entrées-sorties est lancée pour charger la page dans la mémoire
centrale dans la case libre ou libérée;
5. la table des pages du processus est mise à jour c'est-à-dire que le bit de validation V
passe à 1 et le champ numéro de case est renseigné avec l'adresse d'implantation
de la case abritant maintenant la page p;
6. la conversion de l'adresse logique vers l'adresse physique est reprise selon le
principe vu au paragraphe 13.2.2.
Le choix optimal pour la page victime consiste à libérer une case en déchargeant
de la mémoire centrale une page qui ne servira plus du tout, de façon à ne pas provo-
quer de défaut de page ultérieur sur cette même page. Évidemment, il n'est pas
possible de savoir si telle ou telle page d'un processus est encore utile ou pas.
Plusieurs algorithmes, appelés algorithmes de remplacement de pages , ont été
définis qui tendent plus ou moins vers l'objectif optimal. Ce sont les stratégies : FIFO
( First In, First Out ), LRU ( Least Recently Used ), algorithme de la seconde chance,
LFU ( Least Frequently Used ) et MFU ( Most Frequently Used ).
L'évaluation de ces différentes stratégies s'effectue en comptant sur une même
suite de références à des pages, le nombre de défaut de pages provoqués. Une telle
suite de références à un même ensemble de pages est appelée chaîne de références.
Ainsi dans les paragraphes suivants, nous donnons un exemple de chaque stratégie
sur la chaîne de références 8, 1, 2, 3, 1, 4, 1, 5, 3, 4, 1, 4, 3 où chaque chiffre i corres-
pond à un accès à la page i. Dans chaque exemple, nous supposons une mémoire
centrale composée de trois cases initialement vides. La page victime apparaît en
italique. La lettre D signale l'occurrence d'un défaut de page.

Remplacement FIFO
Avec cet algorithme, c'est la page la plus anciennement chargée qui est remplacée.
Une implémentation de cet algorithme peut être réalisée en conservant dans la table
des pages, la date de chargement de chaque page. La page choisie est alors celle pour
laquelle la date de chargement est la plus ancienne.