back-alt
rechercher

memory_chip

La pagination, la segmentation et la mémoire virtuelle

 

Plan

1          Les défis de la gestion de la mémoire. 1

2          Segments de recouvrement (overlays) 2

3          Le va-et-vient (swapping) 2

3.1           C’est l’utilisation de la mémoire secondaire : la « swap file ». 2

3.2           Système simple de swapping. 3

3.3           Système plus complexe de va-et-vient 4

3.4           Fragmentation. 5

3.5           Conclusion. 6

4          Mémoire virtuelle : principes de base. 7

5          Mémoire virtuelle par pagination. 9

5.1           Principe de base. 9

5.2           Défauts de page et « page file ». 10

5.3           Table des pages et multiprogrammation. 14

5.4           Deux problèmes avec la table des pages. 15

5.5           Simulation du fonctionnement de la mémoire virtuelle. 16

6          La segmentation. 16

7          Les exercices. 17

8          Lectures obligatoires. 22

9          Pour en savoir davantage. 22

 

1      Les défis de la gestion de la mémoire

On a commencé à le voir au chapitre précédent, il y a plusieurs problèmes qui se posent avec la gestion de la mémoire.

MCj04414980000[1]

1.      Comment faire pour accommoder en mémoire un programme qui est plus grand que la mémoire physique ?

2.      Comment faire pour permettre la multiprogrammation, c’est-à-dire :

a.       plusieurs processus qui tournent sur la même mémoire physique

b.      plusieurs utilisateurs qui utilisent la même machine, donc la même mémoire physique

sans que

c.       un processus puisse corrompre la mémoire d’un autre

d.      l’on tombe à court de mémoire, parce que la somme des besoins des processus excède la mémoire physique ?

Dans un système d’exploitation, c’est le gestionnaire de mémoire (« memory manager ») qui se charge de répondre à ces questions. Il y a plusieurs stratégies. Explorons-en quelques-unes.

2      Segments de recouvrement (overlays)

Pour tenter de placer en mémoire un programme dont la taille excède la mémoire physique disponible, on utilisait parfois l’overlay (recouvrement).

figure1

Un programme conçu pour l’overlay, confiné au 640 Ko de mémoire de DOS

L’overlay consiste pour le programmeur à concevoir son programme comme un ensemble de blocs objets qui occupent, un à la fois, la même région de la mémoire, le premier bloc étant écrasé par le second, le second par le troisième, etc.

L’idée est de ne conserver en mémoire que l’information qui est nécessaire à un moment donné pour que le processus tourne. Quand le bloc n’est plus nécessaire, il peut être écrasé par le suivant.

En pratique, cette technique complexe n’est plus utilisée, sauf dans certains systèmes embarqués où la mémoire est très exiguë.

 

3      Le va-et-vient (swapping)

3.1    C’est l’utilisation de la mémoire secondaire : la « swap file »

Une partie importante des solutions aux problèmes soulevés consiste à utiliser la mémoire secondaire (disques, mémoire Flash, etc.) pour combler les besoins en mémoire des processus.

Cette mémoire secondaire est plus lente, mais elle est très importante dans les systèmes modernes.

Le va-et-vient est mis en œuvre lorsque tous les processus ne peuvent tenir simultanément en mémoire. On doit alors en déplacer temporairement certains sur une mémoire provisoire, en général, une partie réservée du disque (swap file, ou fichier d’échange).

Sur le disque, la zone de va-et-vient d’un processus peut être allouée à la demande dans la zone de va-et-vient générale (swap file). Quand un processus est déchargé de la mémoire centrale, on lui recherche une place. Les places de va-et-vient sont gérées de la même manière que la mémoire centrale. La zone de va-et-vient d’un processus peut aussi être allouée une fois pour toute au début de l’exécution. Lors du déchargement, le processus est sûr d’avoir une zone d’attente libre sur le disque.

3.2    Système simple de swapping

Le cas le plus simple est celui où la mémoire centrale est juste assez grande pour le système d’exploitation et un processus utilisateur. Tous les processus doivent être transférés dans cet espace lorsqu’on leur alloue un quantum de temps. Le va-et-vient est continuel et on comprend que la performance du système dépend nettement du comportement du processus et de la quantité de temps machine qu’il consomme lors de son transfert en mémoire centrale pour utiliser son quantum de temps.

http://www.colvir.net/prof/yves.bergeron/inf331/v-et-v_s.gif

Le va-et-vient simple a pour inconvénient de laisser l’unité centrale inactive pendant les transferts de processus entre la mémoire principale et la mémoire de stockage. Même avec des traitements limités par l’unité centrale et un quantum de temps plutôt long, le temps pris pour le va-et-vient reste le facteur prépondérant.

3.3    Système plus complexe de va-et-vient

Le problème majeur des deux mécanismes expliqués plus haut est qu’il n’y a que le processus courant en mémoire. Si celui-ci n’utilise pas son quantum temps parce qu’il se bloque à cause d’une E/S (ce qui est très probable dans le cas d’un système interactif), le temps efficace de l’utilisation du processeur est inférieur au temps consacré aux échanges avec la mémoire auxiliaire.

On peut régler ce problème en acceptant plusieurs processus simultanément en mémoire. La technique d’ordonnancement et de va-et-vient deviennent alors beaucoup plus complexes à gérer. De plus, la protection des zones de mémoire lorsqu’il y a plus d’un processus en mémoire physique devient une priorité. Le système d’exploitation doit alors protéger chacun d’eux des interférences des autres, sans oublier de se protéger lui-même des programmes utilisateurs.

Le système exécute pendant un certain quantum de temps les processus en mémoire puis déplace un de ces processus au profit d’un de ceux en attente dans la mémoire provisoire. L’algorithme de remplacement peut être le tourniquet.

http://www.colvir.net/prof/yves.bergeron/inf331/swap.gif

Le système de va-et-vient, s’il permet de pallier le manque de mémoire nécessaire à plusieurs utilisateurs, n’autorise cependant pas l’exécution de programmes de taille supérieure à celle de la mémoire centrale. Les stratégies qui suivent solutionnent ces problèmes.

3.4    Fragmentation

Un autre problème qui surgit lors du va-et-vient est l’apparition de « trous » dans la mémoire secondaire, un phénomène que l’on appelle fragmentation externe. En quelque sorte, cela peut constituer un gaspillage de mémoire : si les « trous » qui restent sont trop petits pour accommoder un processus, on ne peut lui faire de la place sans d’abord faire un va-et-vient. Dans la dernière étape de la figure ci-dessous, on a 660K de mémoire libres, mais un processus de 600K ne peut tourner, car la mémoire à laquelle il a accès n’est pas contiguë. Il existe bien des solutions à ceci, mais elles sont relativement coûteuses.

img190

Progression de l’utilisation de la mémoire.

Des « trous » se forment petit à petit, c’est le phénomène de la fragmentation.

3.5    Conclusion

Les deux techniques d’utilisation de la mémoire secondaire présentées plus haut sont relativement anciennes. Elles étaient utilisées sous DOS et Windows 3.1 (ci-contre), par exemple.

Les principaux inconvénients sont, comme on l’a dit plus haut :

1.      temps de transfert entre la mémoire principale et secondaire

2.      impossibilité d’exécuter un programme de taille supérieure à celle de la mémoire centrale

3.      problèmes de fragmentation

Les utilisations modernes de la mémoire secondaire et de la swap file se font dans le cadre de la mémoire virtuelle, que nous voyons ensuite.

32BitDiskAccess

Taille de la swap file sous Windows 3.1 (en allemand…)

4      Mémoire virtuelle : principes de base

La mémoire virtuelle est une technique de gestion de la mémoire qui permet de ne garder en mémoire qu’une partie d’un processus.

Une partie du processus est gardée en mémoire centrale, l’autre partie, sur la mémoire secondaire. Lorsque le processus a besoin d’une partie qui est sur la mémoire secondaire, celle-ci est copiée en mémoire pour être exécutée.

Cela permet notamment de faire tourner des processus dont les besoins en mémoire excèdent la place en mémoire physique : on ne garde en mémoire que ce qui doit tourner.

Couplée à la multiprogrammation, la mémoire virtuelle permet notamment de faire tourner les processus de plusieurs utilisateurs à la fois, en gardant des parties de ces processus en mémoire.

 

Considérons un ensemble de programmes s’exécutant « simultanément » sur un ordinateur quelconque. La mémoire totale requise par l’ensemble des programmes peut être bien plus grande que la quantité de mémoire physique disponible sur la machine, mais seule une fraction de cette mémoire est utilisée de manière active à chaque instant donné. La mémoire principale n’a donc besoin de contenir que les parties actives des programmes. Une autre motivation est de permettre aux programmes de dépasser la taille de la mémoire physique, ce qui n’est pas possible dans le mécanisme du va-et-vient.

La mémoire virtuelle permet d’exécuter des programmes dont la taille excède la taille de la mémoire réelle.

L’implantation de la mémoire virtuelle gère automatiquement deux niveaux de hiérarchie de mémoire, la mémoire physique (RAM) et la mémoire secondaire (le disque). La mémoire physique de nos appareils, même équipés de 1,2, 4 Go, demeure limitée pour être en mesure de supporter nos exigences et celles du système d’opération en matière de mémoire de travail.

On distingue deux saveurs de mémoire virtuelle, en général :

1.      La mémoire virtuelle par pagination (la plus utilisée)

2.      La mémoire virtuelle par segmentation

Voyons-les, tout en gardant à l’esprit la distinction entre adresses réelles et adresses virtuelles que nous avons vue plus tôt.

MCj04349290000[1]Rappel

Le processeur génère les adresses virtuelles, transformées par le MMU en adresses physiques, qui désignent des emplacements dans la mémoire physique.

On a ainsi l’espace d’adressage virtuel (visible par les processus) et l’espace d’adressage physique (visible par le MMU).

 

 

MMU : Memory management unit

5      Mémoire virtuelle par pagination

5.1    Principe de base

La pagination fonctionne ainsi :

    La mémoire physique est divisée en petites unités appelées cadres de pages

    La mémoire virtuelle est divisée en unités de même taille, appelées pages

    Lorsqu’un programme tente d’accéder à une page dans la mémoire virtuelle, le MMU fait correspondre celle-ci au cadre de page correspondant, dans la mémoire physique

La figure ci-dessous illustre cette stratégie.

Schématisation de mémoire paginée

Lorsque le processus dont l’espace virtuel est illustré tente d’accéder à l’adresse virtuelle 0, il fait référence à la page 0; celle-ci correspond au cadre de page 2, dans la mémoire physique, soit celui aux adresses entre 8 Ko et 12 Ko.

On conserve la correspondance entre les pages et les cadres de pages dans une table appelée table des pages (« page table »).

Dans la plupart des OS modernes, la mémoire virtuelle et la mémoire physique sont divisées logiquement en pages de quelques kilo-octets (1, 2 ou 4 ko généralement). Dans la plupart des ordinateurs, la dimension de la page est fixée à 4 k.

La correspondance de taille est donc parfaite puisque la mémoire virtuelle et la mémoire physique ont des pages de dimension identique.

MCj04325260000[1]La mémoire virtuelle permet donc de faire tourner un processus qui demande plus de mémoire (60 Ko, à gauche dans la figure) que disponible dans la mémoire physique (28 Ko, à droite dans la figure).

5.2    Défauts de page et « page file »

Que se passe-t-il si le processus illustré plus haut tente d’accéder à une page (mémoire virtuelle), comme la page 8K (marquée d’un astérisque *), qui n’a pas de correspondance dans la mémoire physique ?

Il se produit alors un défaut de page : le système d’exploitation doit sélectionner un cadre de page (physique), le libérer en le copiant sur le disque (mémoire secondaire) et le remplacer par la mémoire désirée. On met la table des pages à jour ensuite.

La partie du disque qui sert à stocker les pages qui ne tiennent plus en mémoire s’appelle « swap file » (fichier de va-et-vient) ou « page file ».

La figure ci-contre montre de la mémoire virtuelle correspondant soit à un cadre de page (mémoire physique) ou à des pages sur la « swap file ». La correspondance mémoire s’appelle la traduction d’adresses.

 

Configuration de la mémoire virtuelle sous Windows XP

Fichier de page de va-et-vient pagefile.sys correspondant

 

 

Évolution de la taille du fichier d’échange dans le gestionnaire de tâches

 

Comme la taille de la plage d’adresse virtuelle (typiquement, avec 32 bits, 232) est plus grande que celle de la mémoire physique (par exemple : 230 pour 1 Go de mémoire physique), il arrive souvent qu’on ait un défaut de page. La page virtuelle est absente de la mémoire physique et ne correspond pas encore à une adresse physique, mais elle se trouve sur disque. Il faudra alors la charger et la placer dans la mémoire physique pour être exécutée.

En raison du coût extrêmement élevé d’un défaut de page (plusieurs centaines de milliers de cycles de processeur), les concepteurs souhaitent toujours réduire le nombre de défauts en optimisant le placement des pages.

 

Défauts de pages dans Word durant l’édition de ce document

Fait avec Process Explorer de Sysinternals.

 

Lors du défaut de page, le contrôle est redonné au système d’exploitation et on y parvient grâce au mécanisme des interruptions. Lorsque le système d’exploitation a repris le contrôle, il doit trouver la page dans la mémoire secondaire (sur disque) et décider de l’endroit où placer la page demandée en mémoire physique. Mais l’adresse virtuelle ne nous dit pas directement par elle-même où se situe la plage sur le disque. Il faut donc conserver une trace de l’emplacement sur le disque de chaque page de l’espace d’adressage virtuel.

Habituellement, puisqu’on ne sait pas à l’avance à quel moment une page sera choisie pour être remplacée, le système d’exploitation crée généralement l’espace sur disque pour toutes les pages d’un processus lorsqu’il crée ce dernier.

En raison du contrôle constant du système d’exploitation, certains processus demeurent toujours présents en mémoire vive comme le démontre l’image suivante; on voit clairement que certaines zones de codes d’un système UNIX ne peuvent être évincées de la mémoire physique en raison de leur action de contrôle.

http://www.colvir.net/prof/yves.bergeron/inf331/pagin_p.gif

5.3    Table des pages et multiprogrammation

Une page virtuelle peut donc correspondre à n’importe quelle page physique. Mais il faut un moyen efficace pour trouver les pages physiques. Ce mécanisme est une structure appelée table des pages. Une table des pages propre pour chaque processus qui réside en mémoire est indexée par le numéro de page issu de la mémoire virtuelle et contient le numéro de cadre de page physique correspondant. Chaque programme dispose donc de sa propre table des pages qui met l’espace d’adressage virtuel de celui-ci en correspondance avec la mémoire physique.

La mémoire virtuelle paginée et sa table des pages viennent donc solutionner en partie les problèmes de coexistence de plusieurs processus (multiprogrammation) : chaque processus a sa propre table des pages, et donc la mémoire physique contient des cadres de pages appartenant à plusieurs processus distincts.

5.4    Deux problèmes avec la table des pages

5.4.1    Lenteur

La table des pages étant située en mémoire, il faudrait deux accès mémoire par demande de la part du processeur. Pour pallier ce problème, les entrées les plus souvent utilisées sont conservées dans une mémoire associative (mémoire cache) appelée TLB pour Translation Lookaside Buffer. Chaque adresse virtuelle issue du processeur est cherchée d’abord dans le TLB ; s’il y a correspondance, l’entrée du TLB est utilisée, sinon une interruption est déclenchée et le TLB devra être remis à jour par l’entrée de la table des pages stockée en mémoire avant que l’instruction fautive ne soit redémarrée. Tous les microprocesseurs actuels possèdent un TLB.

En effet, lorsqu’une traduction d’un numéro de page virtuelle est utilisée, il est probable qu’elle soit à nouveau nécessaire dans un futur proche, car les références aux mots de cette page ont des propriétés de localité aussi bien temporelle que spatiale.

Le TLB correspond à ce petit morceau de papier que nous utilisons souvent pour noter l’emplacement d’un ensemble de livres que nous avons recherchés dans le fichier ; plutôt que de sans cesse parcourir tout le fichier, nous notons l’emplacement de plusieurs livres et utilisons le bout de papier comme s’il s’agissait d’un cache.

Un TLB est un cache qui ne détient que des correspondances de tables des pages. Chaque entrée d’étiquette dans le TLB détient une partie du numéro de page virtuelle, et chaque entrée de données du TLB détient un numéro de page physique.

5.4.2    L’écroulement (« thrashing »)

Plus le taux de multiprogrammation augmente, moins chaque processus se voit allouer de pages. Au bout d’un moment, le système sature car trop de défauts de page sont générés.

On peut allouer les pages de mémoire physique en nombre égal pour chaque processus. Par exemple, si la mémoire totale fait 100 pages et qu’il y a cinq processus, chaque processus recevra 20 pages. On peut aussi allouer les pages proportionnellement aux tailles des programmes. Si un processus est deux fois plus grand qu’un autre, il recevra le double de pages.

Ces techniques d’allocation, utilisées telles quelles, peuvent provoquer un écroulement du système. En effet, ce dernier n’est viable que si les défauts de pages sont contenus au dessous d’une limite relativement basse. Si le nombre de processus est trop grand, l’espace propre à chacun sera insuffisant et ils passeront leur temps à gérer des défauts de pages.

http://www.colvir.net/prof/yves.bergeron/inf331/defauts_pagent16.gif

NT avec 16 megs de mémoire vive; beaucoup de défauts de pages

http://www.colvir.net/prof/yves.bergeron/inf331/defauts_pagent64.gif

NT avec 64 megs de mémoire vive; moins de défauts de pages

Il est possible de diminuer les effets de ce comportement soit en rajoutant des ressources matérielles (ajouter de la mémoire), diminuer le taux de multiprogrammation, ou modifier la priorité des processus.

5.5    Simulation du fonctionnement de la mémoire virtuelle

Cette applet, programmée par Ngon Tran, montre la simulation du fonctionnement de la mémoire virtuelle paginée.

6      La segmentation

Alors que la pagination propose un espace d’adressage plat et indifférencié, (offert par les processeurs RISQ ex : Sun), la segmentation partage les processus en segments bien spécifiques. On peut ainsi avoir des segments pour des procédures, pour la table de symboles, pour le programme principal, etc. Ces segments peuvent être relogeables et avoir pour origine un registre de base propre au segment.

Chaque objet logique sera désigné par un segment. Dans un segment l’adressage se fera à l’aide d’un déplacement. Le couple (segment, déplacement) sera traduit en adresse mémoire par le biais d’une table de segments contenant deux champs, limite et base. La base est l’adresse de début du segment, et limite la dernière adresse du même segment.

442px-Vm7

Segmentation : l’adresse virtuelle issue du processeur à la forme (segment, déplacement). Elle est traduite en adresse physique par le biais d’une table de segments. Un test est effectué pour vérifier que l’adresse est bien dans l’intervalle du segment.

La segmentation permet aussi le partage, par exemple du code d’un éditeur entre plusieurs processus. Ce partage porte alors sur un ou plusieurs segments.

Un exemple réduit d’architecture segmentée est donné par la famille x86 qui possède 4 segments : le code (CS Code Segment), la pile (SS Stack Segment), les données (DS Data Segment) et un supplémentaire, à la discrétion du programmeur (ES Extra Segment).

7      Les exercices

1)      Avec Windows 3.1, est-ce que la swap file pouvait contenir une partie seulement d’un processus ? Pourquoi ?

2)      À la section 3.4, on a vu la fragmentation externe.

a)      Donnez une solution possible à ce problème.

b)      Pourquoi la mémoire virtuelle paginée ne rencontre-t-elle pas ce problème ?

c)      Dans la mémoire virtuelle paginée, qu’est-ce que la fragmentation interne ?

3)      En vous aidant de ce lien, expliquez les indicateurs suivants dans le Gestionnaire de tâches de Windows (CTRL+SHIFT+ESC).

a)      Charge dédiée (Total, Limite, Pic)

b)      Mémoire physique (Total, Disponible)

c)      Comment pouvez-vous vous servir du Pic de Charge dédiée pour déterminer la taille optimale du fichier d’échange (page file) sous Windows ?

d)      À quoi sert la « Cache système ». Indice : Chronométrez le temps qu’il vous faut pour lancer Excel une première fois, fermez-le et chronométrez à nouveau.

4)      Un utilisateur se plaint de recevoir plusieurs fois par jour le message ci-dessous. Expliquez ce message et trouvez une façon de réduire sa fréquence d’apparition.



5)      Qu’est-ce qu’un « memory leak » et comment le reconnaîtriez-vous dans un programme ?

6)      Sur votre poste au labo, installez Process Explorer de Sysinternals et configurez-le pour obtenir les statistiques des défauts de pages pour chacun des processus qui roulent sur l’ordinateur. Une fois en fonction, démarrez le plus grand nombre de grosses applications possibles et observez les changements de performances du système au rythme de l’augmentation des défauts de page.  Quelle application est la plus gourmande, quelle est celle qui produit le plus grand nombre de défauts de page et à partir de quand voyez un net changement dans la souplesse d’utilisation de l’appareil ?

7)      Étudiez l’applet du lien suivant et tentez de comprendre comment fonctionnent les changements de pages de la mémoire virtuelle avec la présence du TLB. Écrivez un texte détaillé qui résume son fonctionnement à partir des notes de cours. Utilisez la commande « Step » au bas de l’écran pour faire tourner l’applet un peu plus lentement. Sans doute utile pour l’examen !

8)      Répondez aux questions suivantes (nous utilisons une capture d’écran de l’applet mentionnée dans le lien plus haut, écrite par Ngon Tran).

a) Le processus vert vient d’utiliser la page 24. Dans quel cadre de page se trouve-t-elle ?

b) Est-ce qu’il faudrait consulter la table de pages s’il fallait que le processus doive trouver le cadre de page de la page 24, à nouveau ?

c) Dans quel cadre de page se trouve la page virtuelle 17 du processus vert, selon la table de page ? Selon le TLB ?

d) Le processus jaune utilise également la page virtuelle 17, comme on le voit dans cet extrait du schéma : .

Comment se fait-il alors qu’il n’y ait pas une collision entre la page 17 du processus vert et la page 17 du processus jaune ?

e) Si le processus vert lisait maintenant la page 2, y aurait-il un défaut de page ? S’il lisait plutôt la page 18 ?

f) Que remarquez-vous sur les tables lors de la commutation entre deux processus (context switch) ?

9)      Lorsqu’on augmente la quantité de mémoire physique, qu’arrive-t-il au temps moyen entre deux défauts de pages ? Augmentation ou diminution ? Lisez bien la question…

10)  Admettons qu’une instruction demande 1 μs (microseconde) sans défaut de page, mais 3001 μs lorsque se produit un défaut de page. Si un programme prend 60 s pour s’exécuter avec 15 000 défauts de page, combien de temps prendra-t-il s’il n’y a plus que 7500 défauts de page ?

11)  Répondez aux questions suivantes sur la gestion de la mémoire virtuelle sous Windows XP

a)      Est-il utile de mettre la pagefile sur un autre disque que le disque système ?

b)      Peut-on désactiver la mémoire virtuelle si on a beaucoup de RAM ?

c)      Doit-on défragmenter le pagefile pour améliorer les lectures-écritures ?

d)      Est-il utile de diviser le pagefile sur plusieurs disques ?

12)  On fait tourner le programme C ci-dessous et on observe le message d’erreur Segmentation fault, et le programme crashe. Que signifie ce message ?

int main(int argc, char **argv)
{
    int *test = -1;
    *test = 18;
}

 

13)  Regardez attentivement la figure suivante et expliquez pourquoi deux processus distincts (pids 14460 et 14472) affichent les mêmes adresses mémoire.  Si vous ne trouvez pas, relisez les notes précédentes…

8      Lectures obligatoires

Les notes de cours précédentes

9      Pour en savoir davantage

L’article Wikipédia sur la mémoire virtuelle est très bien et bien illustré

http://en.wikipedia.org/wiki/IA-32

 

seg-faultSur ThinkGeek…

 

Dernière mise à jour le 16 octobre 2009 à 23h16 par Yves Bergeron.