Quand la mémoire vive est pleine
Le remplacement de pages est le choix de la page à renvoyer sur le disque. Il a lieu quand la mémoire vive est pleine et qu’une nouvelle page doit entrer. Un mauvais choix ralentit toute la machine.
Un bureau plein de dossiers pose la même question : lequel ranger pour faire de la place ?
À la fin de cette leçon
Remarque
Je peux simuler le remplacement de pages FIFO et LRU et compter les défauts de page.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Défaut de page | un accès à une page absente de la mémoire vive | |
| Chaîne de références | la suite des pages demandées, dans l’ordre | 1, 2, 1, 3 |
| FIFO | on renvoie la page entrée en premier | |
| LRU | on renvoie la page utilisée le moins récemment | |
| Remplacement | le choix de la page à renvoyer sur le disque | |
| Cadre | un emplacement de la mémoire vive pour une page |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
FIFO renvoie la page la plus ancienne
Avec FIFO, on garde les pages dans l’ordre d’entrée. Quand il faut de la place, on renvoie celle qui est entrée la première, même si on s’en sert encore.
La règle est simple à programmer. Elle ignore pourtant si la page est utile.
Suivez l’exemple : références 1, 2, 1, 3, 1, 4, avec 2 cadres.
Exemple travaillé : FIFO sur six références
| Référence | Résultat | Cadres après |
|---|---|---|
| 1 | défaut | 1 |
| 2 | défaut | 1, 2 |
| 1 | succès | 1, 2 |
| 3 | défaut, on renvoie 1 | 2, 3 |
| 1 | défaut, on renvoie 2 | 3, 1 |
| 4 | défaut, on renvoie 3 | 1, 4 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
LRU renvoie la page la plus délaissée
Avec LRU, on renvoie la page dont le dernier usage est le plus ancien. L’idée : une page utilisée récemment a de bonnes chances de l’être bientôt.
Il faut noter la date de chaque usage, même sur un succès. Cela coûte du travail au système.
Les mêmes références avec LRU
| Référence | Résultat | Cadres après |
|---|---|---|
| 1 | défaut | 1 |
| 2 | défaut | 1, 2 |
| 1 | succès | 2, 1 |
| 3 | défaut, on renvoie 2 | 1, 3 |
| 1 | succès | 3, 1 |
| 4 | défaut, on renvoie 3 | 1, 4 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Compter les défauts FIFO
references = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
cadres_max = 3 # essayez 4
cadres = []
defauts = 0
for page in references:
if page not in cadres:
defauts = defauts + 1
if len(cadres) == cadres_max:
cadres.pop(0)
cadres.append(page)
print(defauts)
Ce que le programme affiche
Avec 3 cadres, il affiche 9. Changez cadres_max en 4 et relancez : il affiche 10.
Plus de mémoire a donc donné plus de défauts. Ce curieux résultat s’appelle l’anomalie de Belady. LRU ne le connaît pas : sur ces références il fait 10 défauts avec 3 cadres et 8 avec 4.
Compter les compteurs de défauts du noyau
grep -E 'pgfault|pgmajfault' /proc/vmstat | wc -lAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Deux compteurs, des valeurs propres à la machine
La commande affiche 2. Le fichier /proc/vmstat contient pgfault, qui compte tous les défauts, et pgmajfault, qui compte ceux qui ont demandé le disque.
Leurs valeurs ne sont pas dans cette sortie : elles montent tant que la machine tourne. Les défauts sans disque sont rapides, les autres sont lents.
Erreur fréquente
Attention
Beaucoup de gens pensent que plus de cadres donne toujours moins de défauts. Avec FIFO, ce n’est pas garanti : l’exemple passe de 9 à 10. Avec LRU, ajouter des cadres ne fait jamais augmenter les défauts.