Pagination : l'algorithme FIFO
l'algorithme FIFO est souvent utilisé dans des situations où l'espace mémoire physique
est limité et où il est nécessaire de gérer efficacement le remplacement des pages. Voici
comment cela se passe dans un scénario où la mémoire physique est insuffisante pour
contenir toutes les pages nécessaires :
Scénario d'utilisation de l'algorithme FIFO
1. Contexte :
• Vous avez une mémoire physique limitée, par exemple, elle peut contenir
3 pages à la fois.
• Votre programme nécessite plus de pages que ce que la mémoire
physique peut contenir simultanément.
2. Chargement initial :
• Lorsque votre programme commence à s'exécuter, les premières pages
nécessaires sont chargées dans la mémoire physique jusqu'à ce que celle-
ci soit pleine.
• Supposons que les premières pages nécessaires sont A, B et C. Elles sont
chargées en mémoire, donc la mémoire physique contient : [A, B, C].
3. Nouvelle page requise :
• À un moment donné, votre programme nécessite une nouvelle page D qui
n'est pas encore en mémoire.
• Étant donné que la mémoire physique est pleine, une des pages existantes
doit être remplacée pour faire de la place pour la nouvelle page D.
4. Application de l'algorithme FIFO :
• L'algorithme FIFO détermine quelle page a été la première à entrer en
mémoire (dans cet exemple, c'est la page A).
• La page A est retirée de la mémoire.
• La nouvelle page D est chargée à sa place.
• Maintenant, la mémoire physique contient : [B, C, D].
5. Continuation du processus :
• Ce processus se répète chaque fois qu'une nouvelle page doit être chargée
et que la mémoire est pleine.
• Par exemple, si la prochaine page requise est E, la page B (qui est
maintenant la plus ancienne) sera remplacée par E.
• La mémoire physique contiendra alors : [C, D, E].
Illustration
Imaginons une séquence d'accès aux pages : A, B, C, D, A, B, E, A, B, C, D
• Initialement, les pages A, B et C sont chargées : [A, B, C].
• La page D est demandée, A est remplacée : [B, C, D].
• La page A est demandée, B est remplacée : [C, D, A].
• La page B est demandée, C est remplacée : [D, A, B].
• La page E est demandée, D est remplacée : [A, B, E].
Avantages et Limites
• Avantages :
• Simplicité : Facile à comprendre et à implémenter.
• Pas besoin de suivre des statistiques complexes sur l'utilisation des pages.
• Inconvénients :
• Pas optimal : Peut conduire à un nombre élevé de défauts de page si les
pages récemment utilisées sont souvent demandées.
• Ne tient pas compte de la fréquence ou de la récence de l'utilisation des
pages, contrairement à d'autres algorithmes comme LRU (Least Recently
Used).
L'algorithme FIFO est donc un choix basique et simple pour le remplacement des pages
en mémoire, particulièrement utile dans des environnements où la simplicité et la
facilité de mise en œuvre sont plus importantes que l'optimisation des performances de
la mémoire.
L'algorithme LRU
L'algorithme LRU (Least Recently Used), ou "le moins récemment utilisé" en français,
est un algorithme de gestion de la mémoire virtuelle utilisé pour la pagination. Il
fonctionne sur le principe que les pages qui n'ont pas été utilisées depuis le plus
longtemps sont les meilleures candidates pour être remplacées lorsqu'une nouvelle
page doit être chargée en mémoire et qu'il n'y a plus de place disponible.
Fonctionnement de l'algorithme LRU
6. Initialisation :
• Une structure de données, comme une liste ou une pile, est utilisée pour
suivre l'ordre d'utilisation des pages.
7. Chargement des pages :
• Chaque fois qu'une page est accédée, elle est déplacée au sommet de la
liste (ou marquée comme récemment utilisée).
• Si la page n'est pas en mémoire, elle est ajoutée à la mémoire et placée au
sommet de la liste.
8. Remplacement de pages :
• Si une nouvelle page doit être chargée mais que la mémoire est pleine,
l'algorithme LRU choisit la page qui n'a pas été utilisée depuis le plus
longtemps (celle au bas de la liste).
• Cette page est retirée de la mémoire.
• La nouvelle page est ajoutée à la mémoire et placée au sommet de la liste.
Exemple
Supposons que nous avons une mémoire physique qui peut contenir 3 pages et une
séquence de pages à charger comme suit : A, B, C, D, A, B, E, A, B, C, D.
9. Chargement des pages :
• Charge A : Mémoire = [A] (A est la plus récemment utilisée)
• Charge B : Mémoire = [A, B] (B est la plus récemment utilisée)
• Charge C : Mémoire = [A, B, C] (C est la plus récemment utilisée)
10. Mémoire pleine, besoin de remplacer une page pour charger D :
• Remplace A (le moins récemment utilisé) par D : Mémoire = [B, C, D] (D
est la plus récemment utilisée)
11. Page A est de nouveau demandée :
• Remplace B (le moins récemment utilisé) par A : Mémoire = [C, D, A] (A
est la plus récemment utilisée)
12. Page B est de nouveau demandée :
• Remplace C (le moins récemment utilisé) par B : Mémoire = [D, A, B] (B
est la plus récemment utilisée)
13. Nouvelle page E doit être chargée :
• Remplace D (le moins récemment utilisé) par E : Mémoire = [A, B, E] (E
est la plus récemment utilisée)
Illustration
Imaginons une séquence d'accès aux pages : A, B, C, D, A, B, E, A, B, C, D
• Initialement, les pages A, B et C sont chargées : [A, B, C].
• La page D est demandée, A est remplacée : [B, C, D].
• La page A est demandée, B est remplacée : [C, D, A].
• La page B est demandée, C est remplacée : [D, A, B].
• La page E est demandée, D est remplacée : [A, B, E].
Avantages et Limites
• Avantages :
• Meilleures performances que FIFO en général, car il tend à minimiser les
défauts de page.
• Approche plus intelligente, car elle considère la récence d'utilisation des
pages.
• Inconvénients :
• Plus complexe à implémenter que FIFO.
• Peut nécessiter plus de ressources pour suivre l'ordre d'utilisation des
pages (par exemple, une liste ou une pile à mettre à jour constamment).
L'algorithme LRU est donc un choix efficace pour le remplacement des pages en
mémoire, particulièrement utile dans des environnements où l'optimisation des
performances mémoire est cruciale. Il est souvent préféré à FIFO en raison de sa
capacité à mieux gérer les accès fréquents et récents aux pages.
Différence clé
• Critère de remplacement :
• FIFO : Remplace la page qui est dans la mémoire depuis le plus
longtemps, indépendamment de son utilisation récente.
• LRU : Remplace la page qui n'a pas été utilisée depuis le plus longtemps,
en tenant compte de l'utilisation récente.
L'algorithme MFU
L'algorithme MFU (Most Frequently Used), ou "le plus fréquemment utilisé" en français,
est un autre algorithme de remplacement de pages utilisé dans la gestion de la mémoire
virtuelle. Il fonctionne sur le principe que les pages qui ont été utilisées le plus
fréquemment sont les meilleures candidates pour être remplacées, en supposant qu'une
page fréquemment utilisée dans le passé continuera à l'être à l'avenir. Cependant, cette
hypothèse peut parfois être contre-intuitive, car les pages fréquemment utilisées
peuvent devenir des pages chaudes que l'on souhaiterait garder en mémoire.
Fonctionnement de l'algorithme MFU
14. Initialisation :
• Une structure de données est utilisée pour suivre le nombre de fois que
chaque page est accédée.
15. Chargement des pages :
• Chaque fois qu'une page est accédée, son compteur d'accès est
incrémenté.
• Si la page n'est pas en mémoire, elle est ajoutée à la mémoire et son
compteur d'accès est initialisé à 1.
16. Remplacement de pages :
• Si une nouvelle page doit être chargée mais que la mémoire est pleine,
l'algorithme MFU choisit la page avec le plus grand compteur d'accès
(celle qui a été utilisée le plus fréquemment).
• Cette page est retirée de la mémoire.
• La nouvelle page est ajoutée à la mémoire avec un compteur d'accès
initialisé.
Exemple
Supposons que nous avons une mémoire physique qui peut contenir 3 pages et une
séquence de pages à charger comme suit : A, B, C, D, A, B, E, A, B, C, D.
17. Chargement des pages :
• Charge A : Mémoire = [A] (Compteurs : A=1)
• Charge B : Mémoire = [A, B] (Compteurs : A=1, B=1)
• Charge C : Mémoire = [A, B, C] (Compteurs : A=1, B=1, C=1)
18. Mémoire pleine, besoin de remplacer une page pour charger D :
• Toutes les pages ont le même compteur d'accès, on peut choisir n'importe
laquelle. Supposons que A soit remplacée : Mémoire = [D, B, C]
(Compteurs : D=1, B=1, C=1)
19. Page A est de nouveau demandée :
• Remplace D (Supposons que D a été choisi pour être remplacé) : Mémoire
= [A, B, C] (Compteurs : A=1, B=1, C=1)
20. Page B est de nouveau demandée :
• Incrémente le compteur de B : Mémoire = [A, B, C] (Compteurs : A=1, B=2,
C=1)
21. Nouvelle page E doit être chargée :
• Remplace B (page la plus fréquemment utilisée) : Mémoire = [A, E, C]
(Compteurs : A=1, E=1, C=1)
Illustration
Imaginons une séquence d'accès aux pages : A, B, C, D, A, B, E, A, B, C, D
• Initialement, les pages A, B et C sont chargées : [A, B, C] (Compteurs : A=1, B=1,
C=1)
• La page D est demandée, A est remplacée (ou n'importe laquelle car les
compteurs sont égaux) : [D, B, C] (Compteurs : D=1, B=1, C=1)
• La page A est de nouveau demandée, D est remplacée : [A, B, C] (Compteurs :
A=1, B=1, C=1)
• La page B est de nouveau demandée, incrémente le compteur de B : [A, B, C]
(Compteurs : A=1, B=2, C=1)
• La page E est demandée, B est remplacée : [A, E, C] (Compteurs : A=1, E=1, C=1)
Avantages et Limites
• Avantages :
• Simple à comprendre et à mettre en œuvre.
• Peut être utile dans certains contextes spécifiques où les pages les plus
fréquemment utilisées doivent être remplacées.
• Inconvénients :
• Contre-intuitif dans la plupart des cas, car les pages fréquemment
utilisées sont souvent importantes à garder en mémoire.
• Souvent moins performant que LRU et FIFO en pratique.
L'algorithme MFU est donc moins couramment utilisé que FIFO ou LRU, car il repose sur
une hypothèse qui n'est pas toujours vraie dans les scénarios réels de gestion de
mémoire. Cependant, il peut être utile dans des cas spécifiques où les pages les plus
fréquemment utilisées doivent effectivement être remplacées.
L'algorithme optimal
L'algorithme optimal de remplacement de pages, souvent appelé algorithme OPT ou
Belady's optimal algorithm, est un algorithme théorique qui fournit la solution la plus
efficace possible pour le remplacement des pages. Il fonctionne en remplaçant la page
qui ne sera pas utilisée pendant la plus longue période à l'avenir. Bien qu'il soit
impossible à mettre en œuvre en pratique parce qu'il nécessite la connaissance parfaite
des accès futurs, il est utilisé comme point de référence pour évaluer l'efficacité des
autres algorithmes de remplacement de pages.
Fonctionnement de l'algorithme optimal (OPT)
22. Initialisation :
• Charge les pages en mémoire jusqu'à ce que la mémoire soit pleine.
23. Chargement des pages :
• Lorsque toutes les pages en mémoire sont pleines et qu'une nouvelle page
doit être chargée, l'algorithme optimal regarde dans le futur pour
déterminer quelle page ne sera pas utilisée pendant la plus longue
période de temps.
24. Remplacement de pages :
• Remplace la page qui ne sera pas utilisée pendant la période la plus
longue à l'avenir.
Exemple
Supposons que nous avons une mémoire physique qui peut contenir 3 pages et une
séquence de pages à charger comme suit : A, B, C, D, A, B, E, A, B, C, D.
25. Chargement des pages :
• Charge A, B, C : Mémoire = [A, B, C]
26. Nouvelle page requise :
• La page D doit être chargée.
• Regardons la séquence future : A, B, E, A, B, C, D
• Parmi A, B et C, la page C est celle qui ne sera pas utilisée pendant la
période la plus longue (elle est utilisée après A et B).
• Remplace C par D : Mémoire = [A, B, D]
27. Prochaine page : A
• A est déjà en mémoire : Mémoire = [A, B, D]
28. Prochaine page : B
• B est déjà en mémoire : Mémoire = [A, B, D]
29. Nouvelle page : E
• Regardons la séquence future : A, B, C, D
• Parmi A, B et D, la page D est celle qui ne sera pas utilisée pendant la
période la plus longue (elle est utilisée après A et B).
• Remplace D par E : Mémoire = [A, B, E]
30. Prochaine page : A
• A est déjà en mémoire : Mémoire = [A, B, E]
Illustration
Imaginons une séquence d'accès aux pages : A, B, C, D, A, B, E, A, B, C, D
• Initialement, les pages A, B et C sont chargées : [A, B, C]
• La page D est demandée, C est remplacée (car elle ne sera pas utilisée avant
longtemps) : [A, B, D]
• La page A est de nouveau demandée : [A, B, D]
• La page B est de nouveau demandée : [A, B, D]
• La page E est demandée, D est remplacée (car elle ne sera pas utilisée avant
longtemps) : [A, B, E]
Avantages et Limites
• Avantages :
• Offre la performance théorique maximale possible en minimisant le
nombre de défauts de page.
• Sert de référence pour comparer d'autres algorithmes de remplacement
de pages.
• Inconvénients :
• Impossible à implémenter en pratique car il nécessite une connaissance
parfaite des accès futurs.
• Utilisé uniquement pour des analyses théoriques et des comparaisons.
Conclusion
L'algorithme optimal est le meilleur algorithme de remplacement de pages en termes de
performances théoriques, mais il est impraticable à utiliser dans des systèmes réels en
raison de l'impossibilité de prédire les accès futurs aux pages. D'autres algorithmes,
comme LRU, FIFO et MFU, sont utilisés dans les systèmes réels, même s'ils ne sont pas
aussi efficaces que l'algorithme optimal.
