Algorithmes de remplacement de pages et thrashing
Résumé
Ce document présente les principaux algorithmes de remplacement de pages en mémoire, comme FIFO, LRU, LFU ou l'horloge, avec leurs principes respectifs. Il explique ensuite le phénomène de thrashing, qui survient lorsqu'un système passe plus de temps à faire du paging qu'à traiter, ainsi que la notion d'ensemble de travail. L'élève y apprendra à comparer ces méthodes et à comprendre les causes de la baisse de performance d'un système.
Points clés
- FIFO remplace la page présente en mémoire réelle depuis le plus longtemps et est facile à mettre en œuvre avec une liste de pages.
- LRU remplace la page dont la dernière utilisation est la plus ancienne ; le document la présente comme la meilleure méthode.
- LFU remplace la page la moins fréquemment référencée et nécessite des compteurs de référence.
- L'algorithme de l'horloge est une variante de FIFO qui donne à chaque page une seconde chance.
- Le thrashing survient lorsqu'un système passe plus de temps à faire du paging que du traitement, ce qui fait chuter les performances.
- Le thrashing est lié au degré de multiprogrammation : réduire ce niveau atténue le problème.
- L'ensemble de travail est l'ensemble des pages qu'un processus requiert dans un intervalle de temps donné de son exécution.
Algorithmes de remplacement de pages
Au hasard: C'est la pire de toutes les méthodes, mais facile à implémenter.
FIFO: Remplace la page qui est présente depuis le plus longtemps dans la mémoire réelle. Facile à mettre en œuvre car l'information de contrôle FIFO est une liste de pages.
LRU: Remplace la page dont la dernière utilisation est la plus ancienne.
C'est-à-dire, remplacer la page qui n'a pas été mentionnée depuis la plus longue période. C'est la meilleure méthode car le passé est un bon indicateur de l'avenir.
NUR: La victime est choisie parmi les pages cycliques depuis la dernière fois où les bits de dernière minute ont été supprimés.
LFU: Remplace une page avec des références moins fréquentes. Nécessite des compteurs de référence.
L'horloge: Est une variante de FIFO et donne à chaque page une seconde chance de rester dans la mémoire réelle. Cet algorithme trie les pages réelles dans une liste circulaire et tourne dans le sens horaire.
L'horloge à deux mains: L'objectif de cet algorithme est de privilégier les pages qui sont référencées pour qu'elles restent en mémoire.
Localité du processus: Le phénomène est appelé ainsi, notamment entre les processus, dans lequel on utilise seulement un nombre limité de pages pour une période donnée de son exécution.
Thrashing
On dit qu'un système est en thrashing lorsqu'il passe plus de temps à faire du paging que du traitement. Par conséquent, il y a une baisse significative des performances du système, ce qui peut provoquer un effondrement des performances en raison de défauts de page excessifs.
Le thrashing est directement lié au degré de multiprogrammation. Réduire ce niveau atténue le problème du thrashing.
Le terme thrashing signifie simplement que la procédure actuelle est dans une mauvaise situation.
Ensemble de travail
C'est l'ensemble des pages qu'un processus requiert dans un intervalle de temps de son exécution. Officieusement, il s'agit de la plus grande collection de ses pages qui doivent résider dans la mémoire réelle pour assurer un certain niveau d'efficacité acceptable.
Dans le modèle de l'ensemble de travail, on permet l'exécution d'un processus si son ensemble de travail est complètement en mémoire.
Nous définissons WS (ensemble de travail) comme l'ensemble des pages virtuelles du processus P qui ont été accessibles dans les dernières secondes du temps virtuel de P. Sa stratégie est calculée pour la valeur P pour chaque instant où P complète l'utilisation du processeur (temps virtuel).
La taille de l'ensemble de travail d'un processus repose sur:
- L'emplacement de la mémoire où le processus accède.
- Le délai entre les chargements de l'ensemble de travail.
- La taille de la page.
Télécharger
PDF Word HTMLQuestions fréquentes
Quel est l'algorithme de remplacement de pages considéré comme le meilleur ?
Le document présente LRU comme la meilleure méthode, car il remplace la page qui n'a pas été utilisée depuis la plus longue période. Il justifie ce choix par le fait que le passé est un bon indicateur de l'avenir.
Qu'est-ce que le thrashing ?
Le thrashing désigne la situation où un système passe plus de temps à faire du paging qu'à traiter les processus. Il entraîne une baisse significative des performances, pouvant aller jusqu'à un effondrement, à cause de défauts de page excessifs.
Comment réduire le problème du thrashing ?
Le document indique que le thrashing est directement lié au degré de multiprogrammation. Réduire ce niveau atténue donc le problème.
Testez-vous
Fiches de révision
Cliquez sur une fiche pour voir la réponse.
Test
Questions générées par IA à partir du document : vérifiez les réponses avec le texte.