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 ;
• l'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 suivant : 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 elle est aussi très dommageable, car elle 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 (s'ils ont lieu) ;
• les tableaux, les listes et autres 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 du 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 (en temps réel) plus rapidement.

Les overlays

Une des premières versions d'exécutable partiellement en mémoire est celle des overlays : l'idée est de charger successivement en mémoire des portions disjointes et différentes de code, exécutées l'une après l'autre. Les différentes passes d'un compilateur sont souvent réalisées en utilisant des overlays. Les overlays 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ée 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. À 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.

La pagination à la demande (demand paging)

La pagination à la demande est la plus répandue des implémentations de mémoire virtuelle ; elle demande de nombreuses capacité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 paresseux » (lazy swapper). Un swappeur paresseux charge une page uniquement si elle est nécessaire.

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

• le matériel (MMU) traduit 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 fait partie de l'espace des adresses logiques mais n'est pas chargée : il y a un défaut de page (page fault).

En général, une erreur d'adresse est due à 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. On peut même faire démarrer un processus sans aucune page en mémoire : le premier défaut de page aurait alors 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 de provoquer un défaut de page, 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ée 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 pagination à la demande 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). En revanche, la partie logicielle est beaucoup plus importante. Enfin, il faut que les instructions puissent être interrompues puis réexécutées après un défaut de page, ce qui n'est pas le cas sur tous les processeurs et ce qui est fondamental.

Efficacité

Soit $ma$ le temps moyen d'accès à la mémoire et $p$ la probabilité d'occurrence d'un défaut de page. Le temps effectif d'accès avec la pagination à la demande est :

$$t_{\text{effectif}} = (1 - p) \times ma + p \times t_{\text{défaut}}$$

où $t_{\text{défaut}}$ est le temps de gestion d'un défaut de page. Un défaut 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 un défaut 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 vers un cadre de 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 processus ;
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 des autres tables) pour indiquer que la page demandée est maintenant en mémoire ;
11. attendre que le processus soit sélectionné de nouveau pour utiliser l'unité centrale ;
12. restaurer le contexte du processus et réexécuter l'instruction fautive.

Toutes ces opérations ne sont pas toujours réalisées (on peut en particulier supposer que l'on ne préempte pas 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 trois actions suivantes :

• gérer l'interruption ;
• charger la page demandée ;
• relancer 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.

En prenant un temps d'accès mémoire de 500 nanosecondes (0,5 µs) et un temps de gestion de défaut de page de 5 millisecondes, on obtient (en microsecondes) :

$$t_{\text{effectif}} = (1 - p) \times 0{,}5 + p \times 5000 \approx 0{,}5 + 5000\,p$$

Un défaut de page tous les mille accès ($p = 10^{-3}$) donne un temps effectif d'environ 5,5 µs, soit onze fois plus long que l'accès standard.

Il faut réduire la fréquence à moins d'un défaut de page tous les 100 000 accès pour obtenir une dégradation inférieure à 10 %. On comprend bien que les choix à faire sur les pages qu'il faut placer en mémoire sont très importants.

Ces choix deviennent encore plus importants quand on a de nombreux utilisateurs et qu'il y a sur-allocation de la mémoire, par exemple lors de l'exécution concurrente de 6 processus de 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 solutions 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 de défaut de page, là où l'on s'attribuait une page libre de la mémoire centrale.

Il nous faut maintenant sélectionner une victime, c'est-à-dire une des pages occupées de la mémoire centrale, qui sera écrite sur disque et remplacée par la page demandée. Remarquons que dans ce cas-là notre temps de transfert est doublé si la victime a été modifiée, car il 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'un défaut de page). Il est possible de réaliser des systèmes de segmentation à la demande, 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 entre les différents processus et le système ?

• remplacement local : le processus se voit affecter 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. On retrouve 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 de code est partagé par les deux processus (réentrance standard des processus UNIX).

Mais avec la pagination à la demande, on peut introduire une nouvelle notion : la « copie sur écriture » (copy-on-write). On ajoute aux entrées de la table des pages des indicateurs de copie sur écriture. L'idée est de ne réaliser la copie d'une page que lorsque l'un des processus qui peuvent y accéder réalise 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 surtout visible dans le cas très fréquent où le fork est immédiatement suivi par un exec. En effet, ce dernier va libérer toutes les pages : il est donc inutile de les recopier juste avant cette libération.

Avant la généralisation de la copie sur écriture, BSD a introduit l'appel système vfork(), qui ne copie rien : le fils emprunte l'espace d'adressage du père, qui reste suspendu jusqu'à ce que le fils appelle execve ou _exit. L'intérêt est de pouvoir réaliser rapidement un execve sans avoir à recopier l'espace d'adressage du processus père ; en contrepartie, le fils ne doit modifier aucune donnée ni retourner de la fonction qui a appelé vfork.

Projection de fichiers en mémoire

La fonction mmap permet la projection de fichiers en mémoire. Le segment de fichier indiqué est placé en mémoire à une adresse de l'espace du processus. Le segment de fichier peut ainsi être parcouru par des accès par adresse, sans utiliser d'appels de lecture ou d'écriture.

#include <sys/mman.h>

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

int munmap(void *addr, size_t length);

L'adresse addr indique où l'on souhaite placer la projection ; elle n'est qu'une indication pour le système, sauf avec l'option MAP_FIXED. Si le paramètre est NULL, le système choisit l'adresse de placement. Dans tous les cas, l'adresse effective est retournée par la fonction (ou MAP_FAILED en cas d'échec). L'intervalle [offset, offset + length[ du fichier fd est placé en mémoire ; offset doit être un multiple de la taille de page (sysconf(_SC_PAGE_SIZE)). prot indique les protections d'accès : PROT_NONE ou une combinaison par OU bit à bit de PROT_READ, PROT_WRITE et PROT_EXEC. flags indique si l'on veut que les écritures réalisées dans les pages contenant la projection soient partagées avec les autres processus et reportées dans le fichier (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 addr et de longueur length. Une projection MAP_SHARED (d'un fichier, ou anonyme avec MAP_ANONYMOUS) constitue aussi une forme de mémoire partagée entre processus.

Les conseils et politiques de chargement des zones projetées

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 on va utiliser le segment de mémoire. En particulier : va-t-on lire le fichier séquentiellement ou de façon aléatoire ? A-t-on encore besoin du fichier après lecture ? Bien sûr, la fonction madvise ne se limite pas aux pages projetées, mais c'est sur celles-ci qu'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 zones plus délicates et moins bien cartographiées en général (sic).

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

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_WILLNEED : prévoit un accès dans un futur proche
• MADV_DONTNEED : ne prévoit pas d'accès dans un futur proche

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

Chargement dynamique de bibliothèques

Indépendamment de l'existence de la mémoire virtuelle, il est possible de gérer « à la main » le code accessible en utilisant le chargement explicite (non automatique) de bibliothèques partagées, avec les fonctions dlopen, dlsym et dlclose déclarées dans <dlfcn.h>.