La mémoire virtuelle

Les méthodes de gestion mémoire que nous venons de voir ont toutes un défaut majeur qui est de garder l'ensemble du processus en mémoire, ce qui donne :

• un coût en swap important
• impossibilité de créer de très gros processus

Les méthodes de mémoire virtuelle permettent d'exécuter un programme qui ne tient pas entièrement en mémoire centrale ! Nous avons commencé par présenter des algorithmes de gestion de la mémoire qui utilisent le concept de base suivante : l'ensemble de l'espace logique adressable d'un processus doit être en mémoire pour pouvoir exécuter le processus.

Cette restriction semble à la fois raisonnable et nécessaire, mais aussi très dommageable car cela limite la taille des processus à la taille de la mémoire physique.

Or si l'on regarde des programmes très standards, on voit que :

• il y a des portions de code qui gèrent des cas très inhabituels qui ont lieu très rarement (si ils ont lieu)
• les tableaux, les listes et autre tables sont en général initialisés à des tailles beaucoup plus grandes que ce qui est réellement utile
• Certaines options d'application sont très rarement utilisées

Même dans le cas où le programme en entier doit résider en mémoire, tout n'est peut-être pas absolument nécessaire en même temps. Avec la mémoire virtuelle, la mémoire logique devient beaucoup plus grande que la mémoire physique.

Cela implique de nombreux avantages : comme les utilisateurs consomment individuellement moins de mémoire, plus d'utilisateurs peuvent travailler en même temps. Avec l'augmentation de l'utilisation du CPU et de débit que cela implique (mais pas d'augmentation de la vitesse). Moins d'entrées-sorties sont effectuées pour l'exécution d'un processus, ce qui fait que le processus s'exécute (temps réel) plus rapidement.

Les overlays

Une des premières versions d'exécutable partiellement en mémoire est celle des "overlay" qui est l'idée de charger successivement des portions disjointes et différentes de code en mémoire, exécutées l'une après l'autre. Les différentes passes d'un compilateur sont souvent réalisées en utilisant un overlay. Les overlay nécessitent quelques adaptations de l'éditeur de liens et des mécanismes de relocation.

Le chargement dynamique

Un autre système couramment utilisé dans les logiciels du marché des micros est le chargement dynamique. Avec le chargement dynamique, une fonction n'est chargé en mémoire qu'au moment de son appel. Le chargement dynamique demande que toutes les fonctions soient repositionnables en mémoire de façon indépendante. A chaque appel de fonction on regarde si la fonction est en mémoire sinon un éditeur de liens dynamique est appelé pour la charger. Dans les deux cas (overlay et chargement dynamique), le système joue un rôle très restreint, il suffit en effet d'avoir un bon système de gestion de fichiers. Malheureusement, le travail que doit réaliser le programmeur pour choisir les overlays et/ou installer un mécanisme de chargement dynamique efficace est non trivial et requiert que le programmeur ait une parfaite connaissance du programme. Ceci nous amène aux techniques automatiques.

Demande Paging

La méthode de Demand Paging est la plus répandue des implémentations de mémoire virtuelle, elle demande de nombreuse capcités matérielles.

Nous partons d'un système de swap où la mémoire est découpée en pages. Comme pour le swap, quand un programme doit être exécuté nous le chargeons en mémoire (swap in) mais au lieu de faire un swap complet, on utilise un "swappeur paresseur" (lazy swapper). Un swappeur paresseux charge une page uniquement si elle est nécessaire.

Que ce passe-t-il quand le programme essaie d'accéder à une page qui est hors mémoire ?

• le matériel va traduire l'adresse logique en une adresse physique grâce à la table des pages
• tant que les pages demandées sont en mémoire, le programme tourne normalement, sinon la page est contenue dans l'espace des adresses logiques mais n'est pas chargée, il y a une page fault.

En général, une erreur d'adresse est dûe à une tentative d'accès à une adresse extérieure (invalide). Dans ce cas, le programme doit être interrompu, c'est le comportement normal d'un système de swap. Mais il est possible avec un swappeur paresseux que la page existe mais ne soit pas en mémoire centrale, d'où les étapes suivantes dans ce cas : On peut faire démarrer un processus sans aucune page en mémoire. La première Page fault aurait lieu à la lecture de la première instruction (l'instruction n'étant pas en mémoire). Il faut réaliser une forme spéciale de sauvegarde de contexte, il faut garder une image de l'état du processus qui vient d'effectuer une Page Fault mais de plus il faudra redémarrer (réexécuter) l'instruction qui a placé le processus dans cet état, en effet il est possible que l'instruction ne soit pas terminé par manque de données. Le système d'exploitation a ici un rôle important, c'est lui qui va réaliser le chargement de la page manquante puis relancer le processus et l'instruction. Les circuits nécessaires à la méthode de Demande Paging sont les mêmes que ceux que l'on utilise pour un système de swap paginé, c'est à dire une mémoire secondaire et un gestionnaire de pages (table des pages). Par contre, la partie logicielle est beaucoup plus importante. Enfin il faut que les instructions soient interruptibles, ce qui n'est pas toujours le cas sur tous les processeurs et ce qui est fondamental.

Efficacité

Efficacité des performances de Demande Paging : Soit ma = 500 nanosecondes, le temps moyen d'accès a une mémoire. Le temps effectif d'accès avec le Demand Paging est : temps effectif = (1-p)*ma + p* "temps de gestion de l'erreur de page" où p est la probabilité d'occurrence d'une erreur de page (page fault). Une erreur de page nécessite de réaliser les opérations suivantes

1. lever une interruption pour le système
2. sauvegarder le contexte du processus
3. déterminer que l'interruption est une erreur de page
4. vérifier que la page en question est une page légale de l'espace logique, déterminer où se trouve la page dans la mémoire secondaire
5. exécuter une lecture de la page sur une mémoire libre (libérer éventuellement une page cf. algorithme de remplacement de page)
   • attendre que le périphérique soit libre
   • temps de latence du périphérique
   • commencer le transfert
6. allouer pendant ce temps là le cpu à un autre utilisateur
7. interruption du périphérique
8. sauvegarde du contexte du processus courant
9. déterminer que l'interruption était la bonne interruption (venant du périphérique)
10. mise à jour de la table des pages et d'autres pages pour indiquer que la page demandée est en mémoire maintenant.
11. attendre que le processus soit sélectionné de nouveau pour utiliser l'unité centrale (cpu)
12. charger le contexte du processus

Toutes ces instructions ne sont pas toujours réalisées (on peut en particulier supposer que l'on ne peut pas préempter l'unité centrale, mais alors quelle perte de temps pour l'ensemble du système). Dans tous les cas, nous devons au moins réaliser les 3 actions suivantes :

• gérer l'interruption
• swapper la page demandée
• relance le processus

Ce qui coûte le plus cher est la recherche de la page sur le disque et son transfert en mémoire, ce qui prend de l'ordre de 1 à 10 millisecondes.

Ce qui nous donne en prenant une vitesse d'accès mémoire de 1 microseconde et un temps de gestion de page de 5 millisecondes un

temps effectif = (1-p)+p * 5000 microsecondes

Une erreur de page toutes les mille pages nous donne un temps effectif onze fois plus long que l'accès standard.

Il faut réduire à moins d'une erreur de page tout les 100 000 accès pour obtenir une dégradation inférieur à 10. On comprend bien que les choix à faire sur des pages qu'il faut placer en mémoire sont donc très importants.

Ces choix deviennent encore plus importants quand l'on a de nombreux utilisateurs et qu'il y a sur-allocation de la mémoire, exécution concurrente de 6 processus de la taille supérieure ou égale à la mémoire physique !

Si l'on suppose de plus que nos 6 programmes utilisent dans une petite séquence d'instructions toutes les pages de leur mémoire logique, nous nous trouvons alors dans une situation de pénurie de pages libres. Le système d'exploitation peut avoir recours à plusieurs solution dans ce cas-là

1. tuer le processus fautif
2. utiliser un algorithme de remplacement de page

Cet algorithme de remplacement est introduit dans notre séquence de gestion d'erreur de page là où l'on s'attribuait une page libre de la mémoire centrale.

Maintenant il nous faut sélectionne une victime, c'est à dire, une des pages occupées de la mémoire centrale qui sera swappée sur disque et remplacée par la page demandée. Remarquons que dans ce cas-là notre temps de transfert est doublé, comme i faut à la fois lire une page et sauvegarder une page sur disque (le temps de transfert disque est ce qui est le plus coûteux dans la gestion d'une erreur de page). Il est possible de réaliser des systèmes de demande segments, mais le lecteur avisé remarquera rapidement les problèmes posés par la taille variable des segments.

Allocation de pages aux processus

Comment répartir les pages sur les différents processus et le système ?

• remplacement local le processus se voit affecté un certain nombre de pages qu'il va utiliser de façon autonome, son temps d'exécution ne dépend que de son propre comportement

• remplacement global le comportement d'allocation de pages aux processus dépend de la charge du système et du comportement des différents processus.

  Le remplacement local demande que l'on réalise un partage entre les différents processus.

Le partage "équitable" : m pages de mémoire physique, n processus, m/n pages par processus ! O nretrouve ici un problème proche de la fragmentation interne, un grand nombre de pages est donné à un processus qui en utilise effectivement peu.

Si la mémoire est libre et assez grande, les deux processus sont grossièrement aussi rapides, par contre si on lance dix exemplaires du premier, le temps d'attente est juste multiplié par 10. Pour le deuxième, le temps d'attente est au moins multiplié par 100.

L'appel fork et la mémoire virtuelle

Nous avons vu que la primitive fork() réalise une copie de l'image mémoire du processus père pour créer le processus fils. Cette copie n'est pas intégrale car les deux processus peuvent partager des pages marquées en lecture seule, en particulier le segment du code est partagé par les deux processus (réentrance standard des processus unix).

Mais avec le système de demand-paging, on peut introduire une nouvelle notion qui est la "copie sur écriture" (copy on write). On ajoute à la structure de page de la table des pages des indicateurs de "copie sur écriture". L'idée est de réaliser la copie de la page uniquement dans le cas où l'un des processus qui peuvent y accéder réaliser une écriture. Dans ce cas-là, la page est recopiée avant l'écriture et le processus écrivain possède alors sa propre page. L'intérêt de ce mécanisme est srutout visible dans le cas très fréquent où le fork est immédiatement suivi par un exec. En effet ce dernier va réaliser une libération de toutes les pages, il est donc inutile de les recopier juste avant cette libération.

Le système BSD a introduit la première version de cette idée en partant de l'appel système vfork() qui lui permet le partage total de toutes les pages entre le processus père et le processus fils sans aucune copie. L'intérêt est de pouvoir réaliser rapidement un execve sans avoir à recopier l'espace d'adressage du processus père.

Projection de fichiers en mémoire

La fonction mmap permet la projection de fichiers en mémoire. LE segment du fichier indique est placé en mémoire à partir de l'adresse indiquée. Le segment de fichier peut aisni être parcouru par des accès par adresse sans utiliser de commande de lecture ou d'écriture.

#include <sys/mman.h>
#include <sys/types.h>

void *mmap(void *adr, int len, int prot, int options, int desc, int offset);

int munmap(void *adr, int len);

L'adresse adr indique où doit être placé le fichier, cette adresse doit être une adresse de début de page (un multiple de sysconf(_SC_PAGE_SIZE), si le paramètre est NULL alors le système sélectionne l'adresse de placement qui est retournée par la fonction. L'intervalle de position [offset, offset+len] du fichier desc est placé en mémoire). prot indique les protections d'accès sous HP-UX les protections suivantes sont disponibles : PROT_NONE, PROT_READ, PROT_READ|PROT_EXECUTE, PROT_READ|PROT_WRITE, PROT_READ|PROT_WRITE|PROT_EXECUTE options indique si l'on veut que les écritures réalisées dans les pages contenant la projection soient partagées (MAP_SHARED), ou au contraire qu'une copie sur écriture soit réalisée (MAP_PRIVATE). La fonction munmap permet de libérer la zone mémoire d'adresse adr et de longueur len. Pour une autre forme de mémoire partagée.

Les conseils et politiques de chargement des zonnes mmapés

Une fois que l'on a décidé de faire des projections en mémoire avec mmap il peut être opportun de faire appel à la fonction madvise qui permet de donner un conseil au système en le prévenant par avance de la façon dont vous allez utiliser le segment de mémoire. En particulier allez vous lire le fichier sequentiellement ou de façon aléaatoire. Avez vous encore besoin du fichier après lecture etc. Biensur la fonction madvise ne se limite pas aux pages mappés mais c'est sur celle ci q'il est le plus facile de prendre des décisions, les autres pages étant gérées dans la pile, le tas et le code dans des zone plus délicates et moins bien cartographiées en général (sic).

#include <sys/mman.h>
int madvise(void *start, size_t length, int advise*);

La valeur du conseil advice :

• MADV_NORMAL : Comportement par défaut
• MADV_RANDOM : prévoit des accès aux pages dans un ordre aléatoire
• MADV_SEQUENTIAL : prévoit des accès aux pages dans un ordre séquentiel
• MADV_WILINEED : prévoit un accès dans un futur proche
• MADV_DONTNEED : ne prévoit pas d'accès dans un futur proche

Biensur ce ne sont que des conseils le système les utilisera si il en a la possibilité, soit parce qu'il a du temps idle soit parce qu'il profitera des lectures groupées sur disque en réalisant des lectures en avance dans le cas séquentiel. Il peut aussi profiter de l'indication DONTNEED pour prendre des décisions dans le code de remplacement de page.

Chargement dynamique

Indépendemment de l'existence de la mémoire virtuelle il est possible de gérer "à la main" le code accessible en utilisant le chargement direct (non automatique) de librairies.