Allocation de mémoire du système d'exploitation Q & R # 3

Question:Quand une erreur de page se produit-elle? Expliquez diverses stratégies / algorithmes de remplacement de page.

Answer:Dans la technique de gestion de la mémoire de pagination à la demande, si une page dont l'exécution est demandée n'est pas présente dans la mémoire principale, une erreur de page se produit. Pour charger la page demandée dans la mémoire principale, un cadre de page libre est recherché dans la mémoire principale et alloué. Si aucun cadre de page n'est libre, le gestionnaire de mémoire doit libérer un cadre en échangeant son contenu vers un stockage secondaire et ainsi faire de la place pour la page requise. Pour échanger des pages, de nombreux schémas ou stratégies sont utilisés.

Diverses stratégies / algorithmes de remplacement de page

  1. The Optimal Page Replacement Algorithm- Cet algorithme remplace la page qui ne sera pas utilisée pendant la plus longue période de temps. Au moment où l'erreur de page se produit, certains ensembles de pages sont en mémoire. L'une de ces pages sera référencée dans la toute prochaine instruction. D'autres pages peuvent ne pas être référencées avant 10 100 ou peut-être 1000 instructions. Ces informations peuvent être stockées avec chaque page dans le PMT (Page Map Table).

    P #baseDécalageDIVERS
    1  dix
    2  NÉANT
    3  1000
    ...
    dix  100

    L'algorithme de page optimal supprime simplement la page avec le plus grand nombre de telles instructions, ce qui implique qu'elle sera nécessaire dans un avenir le plus lointain. cet algorithme a été introduit il y a longtemps et est difficile à mettre en œuvre car il nécessite une connaissance future du comportement du programme. Cependant, il est possible d'implémenter un remplacement de page optimal lors de la deuxième exécution en utilisant les informations de référence de page collectées lors de la première exécution.

  2. NRU(Not Recently Used) Page Replacement Algorithm- Cet algorithme nécessite que chaque page ait deux bits d'état supplémentaires «R» et «M» appelés respectivement bit de référence et bit de changement. Le bit de référence (R) est automatiquement mis à 1 chaque fois que la page est référencée. Le bit de changement (M) est mis à 1 chaque fois que la page est modifiée. Ces bits sont stockés dans le PMT et sont mis à jour sur chaque référence mémoire. Lorsqu'une erreur de page se produit, le gestionnaire de mémoire inspecte toutes les pages et les divise en 4 classes basées sur les bits R et M.

    • Class 1: (0,0) - ni récemment utilisé ni modifié - la meilleure page à remplacer.

    • Class 2: (0,1) - pas récemment utilisé mais modifié - la page devra être écrite avant le remplacement.

    • Class 3: (1,0) - récemment utilisé mais propre - sera probablement réutilisé bientôt.

    • Class 4: (1,1) - récemment utilisé et modifié - sera probablement utilisé à nouveau, et une écriture sera nécessaire avant de le remplacer.

    Cet algorithme supprime une page au hasard de la classe non vide numérotée la plus basse.

    Avantages:

    • C'est facile à comprendre.

    • Il est efficace à mettre en œuvre.

  3. FIFO (First in First out) Page Replacement Algorithm- C'est l'un des algorithmes de remplacement de page les plus simples. La page la plus ancienne, qui a passé le plus de temps en mémoire, est choisie et remplacée. Cet algorithme est implémenté à l'aide de la file d'attente FIFO pour conserver les pages en mémoire. Une page est insérée à l'extrémité arrière de la file d'attente et est remplacée au début de la file d'attente.

    Sur la figure, la chaîne de référence est 5, 4, 3, 2, 5, 4, 6, 5, 4, 3, 2, 6 et il y a 3 cadres vides. Les 3 premières références (5, 4, 3) provoquent des défauts de page et sont placées dans des cadres vides. La référence suivante (2) remplace la page 5 car la page 5 a été chargée en premier et ainsi de suite. Après 7 défauts de page, la référence suivante est 5 et 5 est déjà en mémoire donc pas de défaut de page pour cette référence. De même pour la référence suivante 4. Les marques + indiquent l'entrée d'une page tandis que le cercle montre la page choisie pour la suppression.

    Avantages

    • FIFO est facile à comprendre.

    • C'est très simple à mettre en œuvre.

    Désavantage

    • Pas toujours bon en performance. Il peut remplacer une page active pour en apporter une nouvelle et ainsi provoquer immédiatement un défaut de page de cette page.

    • Un autre effet secondaire inattendu est l'anomalie FIFO ou l'anomalie de Belady. Cette anomalie indique que le taux d'erreur de page peut augmenter à mesure que le nombre de cadres de page alloués augmente.

    Par exemple, la figure suivante présente la même trace de page mais avec une mémoire plus grande. Ici, le nombre de cadres de page est de 4.

    Ici, les défauts de page sont 10 au lieu de 9.

  4. LRU(Least Recently Used) Algorithm- L'algorithme le moins récemment utilisé (LRU) remplace la page qui n'a pas été utilisée pendant la plus longue période. Il est basé sur l'observation que les pages qui n'ont pas été utilisées pendant une longue période resteront probablement inutilisées le plus longtemps et doivent être remplacées.

    Au départ, 3 cadres de page sont vides. Les 3 premières références (7, 0, 1) provoquent des défauts de page et sont introduites dans ces cadres vides. La référence suivante (2) remplace la page 7. La référence de page suivante (0) étant déjà en mémoire, il n'y a pas d'erreur de page. Maintenant, pour la référence suivante (3), le remplacement de LRU voit que, des trois trames en mémoire, la page 1 a été utilisée le moins récemment, et est donc remplacée. Et ainsi le processus se poursuit.

    Avantages

    • L'algorithme de remplacement de page LRU est silencieux et efficace.

    • Il ne souffre pas de l'anomalie de Belady.

    Désavantages

    • Sa mise en œuvre n'est pas des plus faciles.

    • Sa mise en œuvre peut nécessiter une assistance matérielle importante.