Information Technology Reference
In-Depth Information
- la page la plus anciennement chargée est sélectionnée comme étant a priori la
page victime ;
- si la valeur du bit de référence est à 0, alors la page est effectivement remplacée;
- si la valeur du bit de référence est au contraire à 1, alors une seconde chance est
donnée à la page. Son bit de référence est remis à 0, et la page la plus ancienne-
ment chargée suivante est sélectionnée.
Cet algorithme constitue une bonne approximation de l'algorithme LRU. Il est
beaucoup moins coûteux à implémenter car de nombreux matériels offrent directe-
ment un bit de référence associé à chaque case de la mémoire centrale.
Remplacement LFU et MFU
Avec l'algorithme LFU, c'est la page la moins fréquemment utilisée qui est remplacée.
Cet algorithme présente un problème vis-à-vis des pages abondamment référencées
sur un court laps de temps. La valeur du compteur pour ces pages étant élevée, elles
ne sont pas retirées de la mémoire centrale, même si elles ne sont plus jamais réfé-
rencées.
Avec l'algorithme MFU, c'est au contraire la page la plus fréquemment utilisée
qui est remplacée. L'argument à la base de cet algorithme est qu'une page ayant un
petit nombre de références vient sans doute d'être chargée en mémoire centrale et
doit donc y rester.
L'implémentation de ces deux algorithmes est réalisée à l'aide d'un compteur
associé à chaque entrée de table des pages qui mémorise le nombre de références à
une page. Cependant, les performances de ces deux algorithmes ne sont pas très bonnes
et ils sont rarement utilisés.
13.3.4 Performance
Les performances d'un système informatique peuvent être sensiblement affectées
par le mécanisme de pagination à la demande, si le nombre de défauts de pages est
trop important. En effet, dans un système utilisant la pagination à la demande, le
temps d'accès effectif à un mot de la mémoire centrale augmente proportionnelle-
ment avec le nombre de défaut de pages : soit p, 0
1 la probabilité d'un défaut
de page, soit ta, le temps d'accès à un mot de la mémoire centrale sans défaut de
page alors le temps effectif d'accès est (1 - p)
≤
p
≤
temps de défaut de page.
Le temps de défaut de page est surtout impacté par le temps nécessaire pour
réaliser l'opération d'entrées-sorties permettant de charger la page manquante en
mémoire centrale. Un temps moyen pour réaliser une telle opération d'entrées-sorties
avec les technologies de disque actuelles est de 25 ms. Ainsi, le temps effectif d'accès
devient, si l'on considère un temps d'accès à la mémoire centrale égal à 100 ns :
(1 - p)
×
ta
+
p
×
p
Pour obtenir une dégradation des performances inférieure à 10 %, il faut que la
probabilité p soit inférieure à 0,000 000 4, c'est-à-dire que moins d'un accès mémoire
sur 2 500 000 provoque un défaut de page.
×
100
+
p
×
25 000 000
=
100
+
24 999 900
×
Search WWH ::
Custom Search