Quel est l'algorithme de remplacement de page ?

Pendant le processus de mappage d'adresse, s'il s'avère que la page à accéder n'est pas dans la mémoire, une interruption de défaut de page se produira. Lorsqu'un défaut de page se produit, s'il n'y a pas de page libre dans la mémoire du système d'exploitation, le système d'exploitation doit sélectionner une page dans la mémoire et la déplacer hors de la mémoire pour laisser de la place au transfert de la page. Les règles utilisées pour sélectionner les pages à éliminer sont appelées algorithmes de remplacement de page.

Algorithmes de remplacement communs

Algorithme de remplacement optimal (OPT)

Ceci est un algorithme de remplacement de page idéal, mais en pratique il est impossible à mettre en œuvre. L'idée de base de cet algorithme est la suivante : lorsqu'un défaut de page se produit, certaines pages sont en mémoire, dont l'une sera bientôt accédée (incluant également la page de l'instruction suivante), tandis que d'autres pages ne seront accessibles que 10 minutes plus tard. ou 100 Ou il sera accessible après 1000 instructions. Chaque page peut [1] être marquée avec le nombre d'instructions à exécuter avant le premier accès à la page. L'algorithme de remplacement de page optimal indique simplement que la page avec le balisage le plus important doit être remplacée. Le seul problème de cet algorithme est qu’il ne peut pas être implémenté. Lorsqu'un défaut de page se produit, le système d'exploitation n'a aucun moyen de savoir quand chaque page sera ensuite consultée. Bien que cet algorithme ne soit pas possible à mettre en œuvre, l'algorithme de remplacement de page optimal peut être utilisé pour mesurer et comparer les performances des algorithmes réalisables.

Algorithme de remplacement premier entré, premier sorti (FIFO)

L'algorithme de remplacement de page le plus simple est la méthode premier entré, premier sorti (FIFO). L'essence de cet algorithme est de toujours choisir la page qui est restée le plus longtemps dans la mémoire principale (c'est-à-dire la plus ancienne) à remplacer, c'est-à-dire la page qui entre en premier dans la mémoire et en sort en premier. La raison est la suivante : la première page transférée en mémoire est plus susceptible de ne plus être utilisée que la page qui vient d'être transférée en mémoire. Créez une file d'attente FIFO pour stocker toutes les pages en mémoire. Les pages remplacées sont toujours placées en tête de la file d'attente. Lorsqu'une page est mise en mémoire, elle est insérée en fin de file d'attente.

Cet algorithme n'est idéal que lors de l'accès à l'espace d'adressage [1] dans un ordre linéaire, sinon il n'est pas efficace. Parce que les pages fréquemment consultées ont tendance à rester le plus longtemps dans la mémoire principale et, par conséquent, elles doivent être remplacées car elles deviennent « anciennes ».

Un autre inconvénient du FIFO est qu'il présente un phénomène anormal, c'est-à-dire que lorsque le bloc de stockage est augmenté, le taux d'interruption par défaut de page augmente. Bien entendu, le sens de la page qui provoque cette anomalie est en réalité rare.

Algorithme le moins récemment utilisé (LRU)

La principale différence entre l'algorithme FIFO et l'algorithme OPT est que l'algorithme FIFO utilise la durée après l'entrée de la page la mémoire en remplacement La base de l'algorithme OPT est le moment où la page sera utilisée dans le futur. Si le passé récent est utilisé comme approximation du futur proche, les pages qui n'ont pas été utilisées pendant la plus longue période dans le passé peuvent être remplacées. Son essence est que lorsqu'une page doit être remplacée, la page qui n'a pas été utilisée pendant le plus longtemps au cours de la période précédente est sélectionnée pour la remplacer. Cet algorithme est appelé algorithme le moins récemment utilisé (Least Récemment Utilisé, LRU).

L'algorithme LRU est lié à la dernière fois que chaque page a été utilisée. Lorsqu'une page doit être remplacée, l'algorithme LRU sélectionne la page qui a été la moins utilisée au cours de la période écoulée.

L'algorithme LRU est un algorithme de remplacement de page fréquemment utilisé et est considéré comme assez bon, mais il y a un problème sur la façon de le mettre en œuvre.

L'algorithme LRU nécessite la prise en charge du matériel réel.

Le problème est de savoir comment déterminer l'ordre de la dernière heure utilisée. Il existe deux manières possibles pour cela :

1.

Le cas le plus simple est de faire correspondre chaque entrée de la table des pages à un champ de temps d'utilisation et d'ajouter une horloge ou un compteur logique au CPU. Cette horloge est incrémentée de 1 à chaque accès mémoire. Chaque fois qu'une page est accédée, le contenu du registre d'horloge est copié dans le champ de temps d'utilisation de l'entrée correspondante de la table de pages. De cette façon, nous pouvons toujours conserver « l’heure » à laquelle chaque page a été visitée pour la dernière fois. Lors du remplacement de pages, sélectionnez la page avec la plus petite valeur temporelle. Ce faisant, non seulement la table des pages doit être consultée, mais également l'heure dans la table des pages doit être maintenue lorsque la table des pages change (en raison de la planification du processeur), et le problème de dépassement de la valeur d'horloge doit également être pris en considération. .

2.

Utilisez une pile pour conserver les numéros de page. Chaque fois qu'une page est consultée, elle est retirée de la pile et placée au sommet de la pile. De cette façon, la page la plus utilisée est toujours placée en haut de la pile, et la page la moins utilisée est placée en bas de la pile. Puisqu'un article doit être retiré du milieu de la pile, une chaîne bidirectionnelle avec des pointeurs de tête et de queue est utilisée pour le relier. Dans le pire des cas, supprimer une page et la placer en haut de la pile nécessite de changer 6 pointeurs. Il y a une surcharge pour chaque modification, mais la page à remplacer peut être obtenue directement sans recherche, car le pointeur de queue pointe vers le bas de la pile, là où se trouve la page à remplacer.

Étant donné que la mise en œuvre de l'algorithme LRU nécessite une grande quantité de support matériel, elle nécessite également une certaine quantité de surcharge logicielle. Ce qui est réellement implémenté est donc un algorithme d’approximation LRU simple et efficace.

Un algorithme d'approximation LRU est l'algorithme Not Récemment Utilisé (NUR).

Il ajoute un bit de référence à chaque entrée de la table des blocs de stockage et le système d'exploitation les met périodiquement à 0. Lorsqu'une page est accédée, ce bit est défini par le matériel. Au fil du temps, ces bits peuvent être examinés pour déterminer quelles pages ont été utilisées et quelles pages n'ont pas été utilisées depuis la dernière fois qu'elles ont été mises à 0. La page dont le bit est 0 peut être éliminée car elle n'a pas été consultée dans la période récente.

4) Algorithme de remplacement d'horloge (implémentation approximative de l'algorithme LRU)

5) Algorithme de remplacement le moins utilisé (LFU)

Lors de l'utilisation de l'algorithme de remplacement le moins utilisé, il doit être dans Chaque page en mémoire est configurée avec un registre à décalage pour enregistrer la fréquence d'accès à la page. L'algorithme de remplacement sélectionne la page la moins utilisée au cours de la période précédente comme page d'expulsion.

En raison de la vitesse d'accès élevée de la mémoire, telle que 100 ns, une page peut être consultée des milliers de fois en continu en 1 ms. Par conséquent, il n'est généralement pas possible d'utiliser directement un compteur pour enregistrer le nombre de fois. fois qu'une page est consultée, en utilisant plutôt une méthode de registre à décalage. Chaque fois qu'une page est accédée, le bit le plus élevé du registre à décalage est mis à 1, puis décalé vers la droite à chaque fois (par exemple, 100 ns). De cette façon, la page qui a été la moins utilisée au cours de la période récente sera celle avec le plus petit ΣRi.

Le graphe d'accès aux pages de l'algorithme de remplacement LFU est exactement le même que le graphe d'accès de l'algorithme de remplacement LRU ; en d'autres termes, un tel ensemble de matériel peut implémenter à la fois l'algorithme LRU et l'algorithme LFU ; Il convient de souligner que l'algorithme LFU ne reflète pas vraiment l'utilisation de la page, car dans chaque intervalle de temps, un seul bit du registre est utilisé pour enregistrer l'utilisation de la page. Par conséquent, accéder une fois équivaut à accéder à 10 000 fois.

6) Algorithme de travail

7) Algorithme d'horloge de travail

8) Algorithme de vieillissement (un algorithme efficace très similaire au LRU)

9) Algorithme NRU (Non utilisé récemment)

10) Algorithme de la seconde chance

L'idée de base de l'algorithme de la seconde chance est la même que celle du FIFO, mais il a été amélioré pour éviter les pages fréquemment utilisées Remplacez-le. Lorsqu'une page de remplacement est sélectionnée, ses bits d'accès sont vérifiés. S'il est à 0, la page est éliminée ; si le bit d'accès est à 1, on lui donne une seconde chance et la page FIFO suivante est sélectionnée. Lorsqu'une page a une seconde chance, son bit d'accès est remis à 0 et son heure d'arrivée est réglée sur l'heure actuelle. Si la page a été visitée pendant cette période, la position 1 est visitée. Les pages ayant ainsi reçu une seconde chance ne seront éliminées que lorsque toutes les autres pages auront été éliminées (ou auront également reçu une seconde chance). Ainsi, si une page est utilisée fréquemment, son bit d'accès reste toujours à 1 et elle n'est jamais supprimée.

L'algorithme de la seconde chance peut être considéré comme une file d'attente circulaire. Utilisez un pointeur pour indiquer quelle page doit être éliminée ensuite. Lorsqu'un bloc de mémoire est nécessaire, le pointeur avance jusqu'à trouver une page dont le bit d'accès est 0. Au fur et à mesure que le pointeur avance, le bit d’accès passe à 0. Dans le pire des cas, tous les bits d'accès sont à 1 et le pointeur parcourt toute la file d'attente pendant une semaine, donnant à chaque page une seconde chance. A ce moment, il dégénère en algorithme FIFO.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!