Gestion de la mémoires virtuelle (suite)

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.

Table des matières Haut

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.

Table des matières Haut

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).

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.

Table des matières Haut

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.

Table des matières Haut

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.

Table des matières Haut

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.

Table des matières Haut