No cache version.
Caching disabled. Default setting for this page:enabled (code LNG204)If the display is too slow, you can disable the user mode to view the cached version.
Gestion de la mémoires virtuelle (suite)
Dans les principes de gestion de la mémoire virtuelle par le VMM (Virtual Memory Manager), nous devons envisager plusieurs aspects : le chargement (fetch), le placement, et le remplacement.
Stratégies de gestion de la mémoire
Stratégies de chargement en mémoire
Le chargement détermine quand une page ou un segment peut passer de la Ms vers la Mp.
Stratégie de chargement à la demande : c'est seulement quand une page ou un segment est référencé par un processus en exécution que le chargement s'effectue.
Avantage : gain de place en mémoire.
Désavantage : lenteur du chargement.
Stratégie de chargement anticipatif : le système tente de déterminer à l'avance quelle page (ou segment) sera prochainement référencée par le processus.
Avantage : gain de temps (la page est déjà chargée).
Désavantage : nécessite de la place mémoire.
Stratégies de placement en mémoires
Le placement détermine où un segment (ou une nouvelle page) peut être chargé en Mp.
Le système de pagination est le plus facile à gérer, car la nouvelle page peut se placer n'importe où : toutes les pages sont de taille identique.
Par contre, la gestion des systèmes à segmentation est plus ardue car la taille des segments est adaptée à la taille des processus. Les emplacements mémoire libérés ne sont donc pas de tailles identiques.
Stratégies de remplacement en mémoires
Le remplacement détermine qui (quelle page ou quel segment) doit libérer de l'espace mémoire pour la nouvelle page ou le nouveau segment.
Stratégies de remplacements de pages
Random page replacement
Une manière de ne pas faire de discrimination entre les utilisateurs est la technique aléatoire.
Toutes les pages en Mp ont les mêmes chances d'être sélectionnées pour un remplacement.
La page prochainement référencée à autant de chance que les autres d'être sélectionnée pour quitter la Mp, ce qui est désastreux et provoquera à coup sur un miss.
FIFO : First-In-First-Out page replacement
Ce système repose sur le principe des files : le premier entré est le premier sorti.
Cette technique peut utiliser un cachet de temps (timestamp) pour chaque page qui entre en Mp. Lorsqu'une nouvelle page se présente, s'il n'y a pas assez de place c'est la page la plus ancienne (celle qui possède le timestamp le plus élevé) qui est remplacée.
Le principe est de premier abord attrayant : la page la plus ancienne a eu sa chance, et il est temps pour elle de laisser la chance à une nouvelle page.
La faiblesse de ce raisonnement est qu'il ne tient pas compte des pages qui sont en mémoire depuis longtemps mais qui sont constamment utilisées. Dans ce cas, il serait très peu rentable de remplacer cette page, car elle serait quasi immédiatement remontée en Mp.
Ce système de gestion peut ne pas utiliser de timestamp, et travailler avec une simple file, dans laquelle une page nouvellement arrivée se place en fin (tail of the queue) et les anciennes pages sont remplacées du début de la file (head of the queue).
Anomalie Belady
Il semblerait normal de penser que plus le nombre de pages allouées à un processus est élevé, plus le nombre de miss est bas.
Et bien non : Belady, Nelson et Shedler ont découvert que dans le système FIFO de remplacement de pages, il était possible que les page faults (cas où la page ne se trouve pas en Mp, et où il faut la monter de la Ms) augmentent en même temps que le nombre de pages allouées à un processus.
LRU : Least-Recently-Used page replacement
Ce système repose sur le remplacement des pages qui n'ont pas été utilisées depuis le plus grand temps.
Chaque page doit donc utiliser un cachet de temps (timestamp). Ce marqueur détermine le temps depuis lequel la page n'a pas été utilisée.
Deux techniques sont possibles : à chaque fois que la page est utilisée, le cachet est soit réinitialisé (remis à 0), soit repositionné à la fin de la file.
Le problème de ce type de gestion se présente quand un processus est utilisé de manière cyclique. Il est peut-être le plus anciennement utilisé, et le prochain à être utilisé. Il ne serait donc pas rentable de le renvoyer en Ms alors qu'il doit bientôt être en Mp.
LFU : Least-Frequently-Used page replacement
Variation du système LRU, le système LFU permet à une nouvelle page de remplacer la page qui est la moins fréquemment utilisée.
L'idée parait bonne : si la page n'est pas souvent utilisée, nous pouvons prendre le risque de devoir la monter en Mp si nous en avons besoin.
Le non-sens d'un tel système est que la nouvelle page (qui est donc la moins fréquemment utilisée puisqu'on vient seulement de faire appel à elle) peut avoir besoin d'une autre page.
Cette autre page monte en Mp, et remplace la moins fréquemment utilisée, donc celle qui vient de l'appeler.
NUR : Not-Used-Recently page replacement
Le système LRU remplace la page la plus anciennement utilisée, en vérifiant en plus si la page a été modifiée.
Que se passe-t-il si la page n'a pas été modifiée ?
Comme elle existe déjà en Ms, il suffit de la supprimer de la Mp.
Et si la page a été modifiée ?
Dans ce cas, elle ne correspond plus à ce qui existe en Ms, et il faut la sauver à la place de l'ancienne.
L'opération nécessite moins de temps si la page n'a pas été modifiée, il est donc probablement plus rentable de remplacer une page non modifiée qu'une page qui l'a été.
Le système utilise donc 2 bits pour assurer la gestion :
- Bit de référencement
- 0 si la page n'a pas été référencée.
- 1 si la page a été référencée.
- Bit de modification (aussi appelé dirty bit)
- 0 si la page n'a pas été modifiée.
- 1 si la page a été modifiée.
En utilisant le bit de référence puis le bit de modification, nous obtenons un système de classement de 4 groupes:
RESET : Comment expliquer qu'une page soit modifiée sans même être lue ?
Comme le système travaille, au bout d'un temps toutes les pages sont référencées. Comment dès lors établir de priorité de remplacement si tous les bits de référencement sont à 1 ?
De temps en temps, le système d'exploitation réinitialise l'ensemble des bits de référence à la valeur 0.
Après un reset, la page possède son bit de référencement à 0, mais l'opération de reset a modifié la page et son bit de modification est à présent à 1.
Modified FIFO
Cette technique de file FIFO modifiée est aussi appelée variante de la deuxième chance.
Un seul bit est utilisé, le bit de référencement (0 = non référencé; 1 = référencé).
Les pages sont dans une file. Quand une nouvelle page se présente, la page en tête de la file (la plus ancienne) doit normalement être remplacée. Le système vérifie l'état de son bit de référencement : s'il est à 0, la page est remplacée, sinon la page est mise en bout de file (elle a une deuxième chance, mais son bit de référencement est réinitialisé à 0) et la page suivante est examinée.
Working sets
Au moment de la création d'un processus, ce dernier est certain de pouvoir disposer d'un nombre minimal de pages en mémoire, ou jeu de page (window size).
L'ensemble des pages utilisées par ce processus pendant un certain temps est un ensemble de travail (working set).
Denning a développé une vue de l'activité de pagination d'un programme (the working set theory of program behaviour). Son approche conduit à modéliser l'espace de travail (working set model, Denning, 1970) afin de réduire les page faults (défaut de page : la page ne se trouve pas immédiatement à disposition, il faut aller la chercher en Ms) par un pré chargement des pages (prepaging).
Si nous pouvons trouver le working set en entier en mémoire, l'exécution du processus ne provoquera aucun page fault durant son état running.
Si trop peu de page frames sont chargées en mémoire, nous pouvons avoir une dégradation du système (thrashing : le système passe trop de temps à transporter les données entre la Mp et la Ms).
Un moyen de prévenir le thrashing est de fournir assez de page frames pour remplir la moitié de l'espace de stockage "pseudo contigu" alloué au processus en mémoire virtuelle.
Si la mémoire vient à manquer, le VMM retire des pages du jeu de pages de chaque processus qui possède un jeu de page supérieur à la taille minimale.
Quand le jeu de pages d'un processus atteint son minimum, le VMM observe alors si ce processus génère des page faults pour déterminer s'il faut lui allouer un plus grand nombre de pages, ou si le jeu de pages minimum du processus est suffisant pour son exécution. Ce mécanisme permet de prévenir le trashing, et porte le nom de réduction automatique des jeux de pages (automatic working-set trimming).
English translation
You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.
Thank you in advance.
Document created the 15/05/2004, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/en/systeme-exploitation-gestion-memoire-virtuelle.html
The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.
