Qu'est-ce que Linux utilise pour implémenter la mémoire virtuelle ?

Lors de l'utilisation de l'algorithme FIFO, 12 remplacements de pages sont effectués, soit exactement deux fois plus que l'algorithme de remplacement optimal.

L'algorithme FIFO produira également un phénomène anormal où lorsque le nombre de blocs physiques alloués augmente, le nombre de défauts de page augmente au lieu de diminuer. Cela a été découvert par Belady en 1969, c'est pourquoi on l'appelle Anomalie Belady, comme. indiqué dans le tableau ci-dessous.

Seul l'algorithme FIFO peut rencontrer des anomalies Belady, tandis que les algorithmes LRU et OPT ne connaîtront jamais d'anomalies Belady.

3.3 Algorithme de remplacement les moins récemment utilisés (LRU)

Les moins récemment utilisées (LRU, Les moins récemment utilisées)Sélection de l'algorithme de remplacementLes pages qui n'ont pas été visitées depuis le plus longtemps seront éliminées, Il est supposé que les pages qui n'ont pas été visitées au cours de la période écoulée pourraient ne pas l'être dans un avenir proche.

Cet algorithme définit un champ de visite pour chaque page afin d'enregistrer le temps écoulé depuis le dernier accès à la page Lors de l'élimination des pages, sélectionnez celle avec la plus grande valeur parmi les pages existantes à éliminer.

LRU a de meilleures performances, mais nécessite une prise en charge matérielle pour les registres et les piles, et est plus cher.

LRU est un algorithme de stack class. Théoriquement, il peut être prouvé que l’exception Belady est impossible à produire dans les algorithmes de pile. L'algorithme FIFO est implémenté sur la base d'une file d'attente et non d'un algorithme de pile.

3.4 Algorithme de remplacement d'horloge (CLOCK)

Les performances de l'algorithme LRU sont proches de l'OPT, mais il est difficile à mettre en œuvre et coûteux ; l'algorithme FIFO est simple à mettre en œuvre, mais a des performances médiocres. Par conséquent, les concepteurs de systèmes d'exploitation ont essayé de nombreux algorithmes, essayant d'approcher les performances de LRU avec une surcharge relativement faible. Ces algorithmes sont tous des variantes de l'algorithme CLOCK.

L'algorithme simple CLOCK associe un bit supplémentaire à chaque trame, appelé bit d'utilisation. Lorsqu'une page est chargée pour la première fois dans la mémoire principale puis consultée, le bit d'utilisation est défini sur 1.

Pour l'algorithme de remplacement de page, l'ensemble de cadres candidats au remplacement est considéré comme un tampon circulaire et est associé à un pointeur. Lorsqu'une page est remplacée, le pointeur est défini pour pointer vers l'image suivante dans le tampon.

Lorsqu'une page doit être remplacée, le système d'exploitation analyse le tampon pour trouver la première image avec un bit d'utilisation de 0. Chaque fois qu'une trame avec un bit d'utilisation de 1 est rencontrée, le système d'exploitation réinitialise le bit à 0 ; si toutes les trames ont un bit d'utilisation de 1, le pointeur termine un cycle dans le tampon, effaçant tous les bits d'utilisation mis à 0 et reste. à la position d'origine, en remplaçant la page dans le cadre. Étant donné que cet algorithme vérifie cycliquement l'état de chaque page, il est appelé algorithme CLOCK, également connu sous le nom d'algorithme Non récemment utilisé (NRU).

Les performances de l'algorithme CLOCK sont relativement proches de celles de LRU, et en augmentant le nombre de bits utilisés, l'algorithme CLOCK peut être rendu plus efficace. En ajoutant un bit modifié modifié au bit utilisé, nous obtenons un algorithme de remplacement CLOCK amélioré.

• n'a pas été consultée récemment et n'a pas été modifiée (u=0, m=0).

• a été récemment consulté mais n'a pas été modifié (u=1, m=0).

• n'a pas été visité récemment, mais a été modifié (u=0, m=1).

• a été récemment consulté et modifié (u=1, m=1).

• À partir de la position actuelle du pointeur, scannez le frame buffer. Lors de cette scrutation, aucune modification n'est apportée aux bits d'utilisation. La première trame rencontrée (u=0, m=0) est sélectionnée pour être remplacée.

• Si l'étape 1 échoue, analysez à nouveau et trouvez le cadre de (u=0, m=1). La première trame de ce type rencontrée est sélectionnée pour être remplacée. Lors de cette scrutation, pour chaque trame sautée, son bit d'utilisation est mis à 0.

• Si l'étape 2 échoue, le pointeur reviendra à sa position d'origine et les bits utilisés de toutes les images de l'ensemble seront 0. Répétez l'étape 1 et, si nécessaire, l'étape 2. Cela trouvera des cadres à remplacer.

les pages qui n'ont pas changé sont préférées lors de leur remplacement. Cela fait gagner du temps puisque les pages modifiées doivent être réécrites avant d'être remplacées.

4. Stratégie d'allocation de pages

4.1 Taille de l'ensemble résident

combien d'espace mémoire principale allouer à un processus spécifique, cela doit prendre en compte les points suivants :

• Plus la quantité de stockage allouée à un processus est petite, plus le nombre de processus résidant dans la mémoire principale est petit. à tout moment Plus l'utilisation du temps du processeur peut être efficace.

• Si un processus a trop peu de

  pages en mémoire principale, malgré le principe de localité, le taux de défauts de page sera quand même relativement élevé.

• Si

  le nombre de pages est trop important, en raison du principe de localité, allouer plus d'espace mémoire principale à un processus spécifique n'aura pas d'impact évident sur le taux d'erreur du processus.

• Remplacement local à allocation fixe : il alloue un certain nombre de blocs physiques à chaque processus, ne change pas pendant toute l'exécution . Si un défaut de page se produit pendant l'exécution du processus, vous ne pouvez sélectionner qu'une seule page parmi les pages de la mémoire du processus et l'échanger, puis charger la page requise. Il est difficile de déterminer le nombre de blocs physiques qui doivent être alloués à chaque processus lors de la mise en œuvre de cette stratégie : un nombre trop faible entraînera des erreurs de page fréquentes, et un nombre trop important réduira l'utilisation du processeur et d'autres ressources.

Remplacement global d'allocation variable
•  : Il s'agit de la stratégie d'allocation et de remplacement de blocs physiques la plus simple à mettre en œuvre. Chaque processus du système se voit attribuer un certain nombre de blocs physiques, et le système d'exploitation lui-même maintient également une file d'attente de blocs physiques gratuits. blocs. Lorsqu'un défaut de page se produit dans un processus, le système retire un bloc physique de la file d'attente de blocs physiques libre, l'affecte au processus, puis charge la page à y charger.

• Remplacement local d'allocation variable : il alloue un certain nombre de blocs physiques à chaque processus. Lorsqu'une erreur de page se produit dans un processus, une seule page des pages mémoire du processus peut être échangée, de sorte que. Cela n’affectera pas le fonctionnement des autres processus. Si le processus manque fréquemment des pages pendant l'exécution du processus, le système attribuera un certain nombre de blocs physiques au processus jusqu'à ce que le taux de pages manquées du processus tende vers un niveau approprié, à l'inverse, si le processus la page ; le taux d'échec est particulièrement faible pendant que le processus est en cours d'exécution. Vous pouvez alors réduire de manière appropriée le nombre de blocs physiques alloués au processus.

4.2 Moment de chargement des pages Afin de déterminer le moment où le système charge les pages manquantes lorsque le processus est en cours d'exécution, les deux stratégies de pagination suivantes peuvent être adoptées :

• Stratégie de pré-pagination : selon le principe de localité, charger plusieurs pages adjacentes à la fois peut être plus efficace que charger une page à la fois. Mais si la plupart des pages chargées n’ont pas été consultées, cela est inefficace. Par conséquent, il est nécessaire d’utiliser une stratégie de pré-pagination basée sur la prédiction pour précharger en mémoire les pages qui devraient être consultées dans un avenir proche. Cependant, le taux de réussite actuel des pages pré-ajustées n'est que d'environ 50 %. Par conséquent, cette stratégie est principalement utilisée lorsque le processus est chargé pour la première fois et que le programmeur indique quelles pages doivent être chargées en premier.

  Stratégie de pagination de demande
•  : La

  page à laquelle le processus doit accéder pendant le fonctionnement n'est pas dans la mémoire et une demande est effectuée, et le système transférera la page requise dans la mémoire. Les pages transférées par cette stratégie seront certainement accessibles, et cette stratégie est relativement facile à mettre en œuvre, cette stratégie est donc principalement utilisée dans les mémoires virtuelles actuelles. Son inconvénient est qu'il ne charge qu'une page à la fois. Lorsque de nombreuses pages sont chargées et extraites, cela consomme trop de surcharge d'E/S. 4.3 D'où charger la page

Le stockage externe dans le système de pagination des requêtes est divisé en deux parties : la zone de fichiers

pour le stockage des fichiers et la page d'échange. zone d'échange. La zone d'échange utilise généralement la méthode d'allocation continue, tandis que la zone de fichiers utilise la méthode d'allocation discrète, de sorte que la vitesse d'E/S disque de la zone d'échange est plus rapide que celle de la zone de fichiers. Il existe trois situations dans lesquelles les pages peuvent être transférées : Le système dispose de suffisamment d'espace dans la zone d'échange : Vous pouvez transférer toutes les pages requises depuis la zone d'échange pour augmenter la vitesse de transfert des pages. Pour cette raison, avant l'exécution du processus, les fichiers liés au processus doivent être copiés de la zone de fichiers

• Le système manque de suffisamment d'espace dans la zone d'échange : Tous les fichiers qui ne seront pas modifiés sont directement transférés depuis la zone de fichiers

  (pas besoin de réécrire lors de l'échange). Mais pour les pièces qui peuvent être modifiées, elles doivent être transférées vers la zone d'échange lors de leur échange, puis retransférées depuis la zone d'échange lorsque cela est nécessaire ultérieurement.

• Méthode UNIX : Les fichiers liés au processus sont placés dans la zone des fichiers, donc les pages qui n'ont pas été exécutées doivent être chargées depuis la zone des fichiers. Les pages qui ont déjà été exécutées mais qui ont été échangées sont placées dans la zone d'échange, elles doivent donc être chargées depuis la zone d'échange la prochaine fois. Si la page partagée demandée par le processus est transférée en mémoire par d'autres processus, il n'est pas nécessaire de la transférer depuis la zone d'échange.

• 5. Gigue de page (bosse) et ensemble de travail (ensemble résident) 5.1 Gigue de page (saut)

comportement de planification de page fréquent est appelé gigue, ou turbulence. Si un processus passe plus de temps à paginer qu'il n'en faut à s'exécuter, alors le processus est en difficulté.

le nombre de pages fréquemment consultées par un processus est supérieur au nombre de cadres de page physiques disponibles. La technologie de mémoire virtuelle peut conserver davantage de processus en mémoire pour améliorer l'efficacité du système. En régime permanent, la quasi-totalité de la mémoire principale est occupée par des blocs de processus, et le processeur et le système d'exploitation ont un accès direct à autant de processus que possible. Mais s'il n'est pas géré correctement, la majeure partie du temps du processeur sera consacrée à échanger des blocs, c'est-à-dire à demander l'opération de chargement de pages, plutôt qu'à exécuter les instructions du processus, ce qui réduira considérablement l'efficacité du système.

L'ensemble de travail (ou ensemble résident) fait référence à l'ensemble de pages auxquelles un processus doit accéder dans un certain intervalle. Les pages fréquemment utilisées doivent figurer dans l'ensemble de travail, tandis que les pages qui n'ont pas été utilisées depuis longtemps sont supprimées de l'ensemble de travail. Afin d'éviter les perturbations du système, vous devez choisir une taille d'ensemble de travail appropriée.

Le principe du modèle d'ensemble de travail est de permettre au système d'exploitation de suivre l'ensemble de travail de chaque processus et d'attribuer au processus des blocs physiques plus grands que son ensemble de travail. S'il existe des blocs physiques libres, vous pouvez transférer un autre processus vers la mémoire pour augmenter le nombre de multi-programmes. Si la somme de tous les ensembles de travail augmente pour dépasser le nombre total de blocs physiques disponibles, le système d'exploitation met un processus en pause, le page et alloue ses blocs physiques à d'autres processus pour éviter toute interruption.

Choisir correctement la taille de l'ensemble de travail aura un impact important sur l'utilisation de la mémoire et l'amélioration du débit du système .

6. Résumé La méthode de gestion de

pagination et la méthode de gestion de segmentation sont similaires à de nombreux endroits, comme la mémoire est discontinue, et il existe des mécanismes de traduction d'adresses pour le mappage d'adresses, etc. Cependant, il existe de nombreuses différences entre les deux. Le Tableau 3-20 répertorie la comparaison entre la gestion de pagination et la gestion de segmentation sous divers aspects.