Utilisateur:Poil/vm

Le mécanisme de mémoire virtuelle à été mis au point dans les années 1960. Il est basé sur l'utilisation d'une mémoire de masse (type disque dur ou anciennement un tambour), dans le but, entre autres, est de permettre à des programmes de pouvoir s'exécuter dans un environnement matériel possédant moins de mémoire centrale que nécessaire.

La mémoire virtuelle permet :

• d'augmenter le taux de multiprogrammation
• de mettre en place des mécanisme de protection de la mémoire
• de partager la mémoire entre processus

Historique

L'article de référence de James Kilburn, paru en 1962, décrit le premier ordinateur (l'Atlas) doté d'un système de gestion de mémoire virtuelle paginée et utilisant un tambour comme extension de la mémoire centrale à tores de ferrite.
Aujourd'hui, tous les ordinateurs ont un mécanisme de gestion de la mémoire virtuelle, sauf certains supercalculateurs ou systèmes embarqués temps réel.

Mémoire virtuelle paginée

Le principe est le suivant : par un mécanisme de translation, les adresses virtuelles, émises par le processeur, seront traduites en adresses physiques.

On traduit des adresses virtuelles en adresses physiques, et certaines informations peuvent être temporairement placées sur un support de stockage.

De plus :

1. la mémoire virtuelle sera considérée comme une suite de zones de même taille appelées « pages ».
2. la mémoire physique va être considérée comme une suite de zones de même taille appelées « cadres », ou frames en anglais.
3. les adresses mémoires issues par l'unité centrale sont des adresses virtuelles.
4. une adresse virtuelle sera traduite en adresse physique par un mécanisme de translation.

L'adresse virtuelle issue du processeur est un couple (numéro de page, déplacement). À l'issue de la translation, ce couple deviendra (numéro de frame, déplacement). On notera que la valeur du déplacement restera identique.

Mémoire virtuelle : translation d'une adresse virtuelle en adresse physique

Pour passer du numéro de page au numéro de cadre, on se sert d'une table appelée « table des pages » (page table en anglais) où le numéro de page servira d'index. Les bits se trouvant dans cette table est le numéro de cadre. Chaque ligne de cette table sera appelée « entrée dans la table des pages » (pages table entry, abrégé PTE). La table des pages pouvant être située n'importe où en mémoire, un registre spécial (PTBR pour Page Table Base Register) conserve son adresse.

Mémoire virtuelle : translation du couple (page, déplacement), l'adresse virtuelle, en (frame, déplacement), l'adresse physique

Voici un exemple réel d'une machine dont le processeur génère des adresses virtuelles sur 32 bits, pouvant ainsi accéder à 4 Go de mémoire. La taille de la page à été fixée à 4 Ko. On en déduit que le champs déplacement occupe les 12 derniers bits, et le champs numéro de page les 20 suivants.

Mémoire virtuelle : translation du couple (page, déplacement), l'adresse virtuelle, en (frame, déplacement), l'adresse physique

On notera la présence d'un champ spécial appartenant à chaque PTE. Pour simplifier nous avons réduit la largeur de ce champs à un bit : le bit de validité. Si celui-ci est à 0, cela signifie que le numéro de frame est invalide. Il faut donc se doter d'une technique permettant de mettre à jour cette PTE pour la rendre valide.

Trois cas peuvent se produire :

1. l'entrée est valide : elle se substitue au numéro de page pour former l'adresse physique.
2. l'entrée dans la table de page est invalide. Dans ce cas il faut trouver un cadre libre en mémoire physique et mettre son numéro dans cette entrée de la table des pages.
3. l'entrée dans la table de page est valide mais correspond à une adresse sur la mémoire de masse ou se trouve le contenu du cadre. Un mécanisme devra ramener ces données pour les placer en mémoire physique.

Allocation à la demande

Dans les deux derniers cas, une interruption — appelée faute de page — est générée par le matériel et donne la main au système d'exploitation. Celui-ci est responsable soit de trouver une frame disponible en mémoire centrale afin de l'allouer au processus responsable de la faute de page, et éventuellement de recharger le contenu de cette frame par le contenu sauvé sur la mémoire de masse (couramment le disque dur, sur une zone appelée zone de swap).

Il se peut qu'il n'y ai plus de frame libre en mémoire centrale : celle ci est occupée à 100%. Dans ce cas il faut mettre au point un algorithme qui aura la responsabilité d'élire une page « victime ». Cette page se verra soit immédiatement reaffactée au processus demandeur, soit elle sera d'abord sauvegardé sur disque dur, et l'entrée de la table de page qui la référence mis à jour. On notera que la page victime peut très bien appartenir au processus qui manque de place.

Ci-dessous sont listés quelques exemples d'algorithmes. La première ligne correspond à la chaise de référence, c'est à dire l'ordre dans lequel les pages vont être accédées par le processus. On suppose que la mémoire centrale est composée de trois frames. La frame victime apparaîtra soulignée. Les fautes de pages initiales ne sont pas comptées (elles sont en nombre identique quelque soit l'algorithme choisi).

• L'algorithme optimal : le nombre de faute de page est réduit à 6. La règle de remplacement est «remplacer la frame qui ne sera pas utilisée pendant la durée la plus longue». Malheureusement cet algorithme nécessite de connaître l'avenir. Les autres algorithmes essayeront dont d'approcher cette solution optimale.

7		0		1		2		0		3		0		4		2		3		0		3		2		1		2		0		1		7		0		1
	7		7		7		2				2				2						2						2								7
			0		0		0				0				4						0						0								0
					1		1				3				3						3						1								1

• FIFO (First In First Out) ou Premier Arrivé, Premier Sorti : la frame victime est celle qui à été amenée en mémoire il y a le plus longtemps (la plus «ancienne»). Notez qu'il n'est pas nécessaire de conserver l'instant à laquelle une frame à été remplacée : il suffit de maintenir une structure FIFO est de remplacer la frame dont le numéro appairait en tête et d'insérer le numéro de la nouvelle frame en dernière position. Cet algorithme donne lieu à 12 remplacements :

7		0		1		2		0		3		0		4		2		3		0		3		2		1		2		0		1		7		0		1
	7		7		7		2				2		2		4		4		4		0						0		0						7		7		7
			0		0		0				3		3		3		2		2		2						1		1						1		0		0
					1		1				1		0		0		0		3		3						3		2						2		2		1

• L'algorithme le plus souvent utilisé est appelé LRU, pour Least Frequently Used en anglais. Il consiste à choisir comme victime la frame qui n'a pas été référencée depuis le plus longtemps. On peut l'implémenter soit en rajoutant des bits dans chaque entrée de la table de page qui indiquent quand à eu lieu la dernière référence à cette entrée, soit via une structure de liste ou l'on amènera en première position la frame récemment référencée, les frames victimes restant donc en dernières positions. Cet algorithme donne lieu à 8 remplacements :

7		0		1		2		0		3		0		4		2		3		0		3		2		1		2		0		1		7		0		1
	7		7		7		2				2				4		4		4		0						1				1				1
			0		0		0				0				0		0		3		3						3				0				0
					1		1				3				3		2		2		2						2				2				7

• Autres algorithmes :
  • Remplacement aléatoire : ou la frame victime est choisie au hasard.
  • LFU (Least Frequently Used ou bien Moins Souvent Utilisée) : on garde un compteur qui sera incrémenté à chaque fois que la frame sera référencée et la victime sera la frame avec le compteur le plus bas. Inconvénient  : au démarrage du programme quelques pages peuvent être intensément utilisées, puis plus jamais par la suite. La valeur du compteur sera si élevé qu'elle ne seront remplacées que trop tardivement. Il faut aussi gérer le cas de dépassement de capacité du compteur...

Il peut être relativement facile de trouver des cas chroniques qui rendent un algorithme inutilisable. Par exemple pour l'algorithme LRU il s'agirait d'un programme qui utilise 5 pages dans une boucle sur une machine qui ne compte que 4 frames. Il va d'abord utiliser les 4 premières frames séquentiellement (1, 2, 3, 4) puis une faute de page va survenir et c'est la page 1, la plus anciennement chargée, qui sera la victime. Les pages utilisées sont maintenant (5, 2, 3, 4). Puisque le programme boucle, il a besoin de la page 1 (à la suite de la page 5). Cette fois ci la page victime est la page 2, remplacée par la 1 : (5, 1, 3, 4), puis (5, 1, 2, 4), 5, 1, 2, 3) etc. Une faute de page est générée à chaque itération...

Anomalie de Belady

L'anomalie de Belady montre qu'avec l'algorithme FIFO, il est possible que plus de fautes de page soient générées alors qu'on à augmenté le nombre de frames (i.e. rajouté de la mémoire centrale). Il a aussi été démontré que certains algorithmes ne pouvaient pas souffrir de cette anomalie.

Méthode d'allocation dans une système multiprogrammé

Les méthodes d'élection de la page victime évoqués ci-dessus peuvent s'appliquer soit aux pages appartenant à un processus, on parle alors d'allocation locale, soit à toutes les pages (i.e. toute la mémoire), dans le cas la technique d'allocation est dite globale.

Dans un système d'allocation globale le temps d'exécution d'un processus peut grandement varier d'une instance à l'autre car le nombre de fautes de page ne dépend pas du processus lui même. D'une autre coté ce système permet au nombre de frames allouées à un processus d'évoluer.

Partage de mémoire dans un système paginé

Le schéma suivant montre trois processus en cours d'exécution, par exemple un éditeur de texte nommé Ed. Les trois instances sont toutes logées aux mêmes adresses virtuelles (1, 2, 3, 4, 5). Ce programme utilise deux zones mémoire distinctes : les pages qui contiennent le code, c'est à dire les instructions décrivant le programme, et la zone de données, le fichier en cours d'édition. Il suffit de garder les mêmes entrées dans la table de page pour que les trois instances se partagent la zone de code. Par contre, les entrées correspondantes aux pages de données sont, elles, distinctes.

Mémoire virtuelle : partage du code entre trois processus constitués de 3 pages de code et 2 pages de données.

Protection

Des bits de protections sont ajoutés à chaque entrée de la table de pages. Ainsi on pourra aisément faire la distinction entre les pages allouées au noyau, en lecture seule, etc. Voir l'exemple ci dessous.

Efficacité

On rencontre trois problèmes majeurs :

1. La taille de la table des pages : pour une architecture ou 20 bits sont réservés pour le numéro de page, la table occupera 4 Mo de mémoire minimum (1024 entrées de 4 octets chacune. Ce problème est résolu par l'utilisation de plusieurs tables de page : le champs numéro de page sera décomposé en plusieurs, chacun indiquant un déplacement dans la table de plus bas niveau. Les VAX et les Pentiums supportent deux niveaux, le SPARC trois, les Motorola 680x0 quatre... On peut aussi segmenter la table des pages.
2. Le temps d'accès : la table de page étant située en mémoire il faudrait 2 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 dans le TLB, si il y a correspondance, l'entrée de le TLB est utilisée, sinon une interruption est déclenchée et le TLB devra être remise à jour par l'entrée de la page de table stockée en mémoire avant que l'instruction fautive soit redémarre. Tous les microprocesseurs actuels possèdent un TLB.
3. Phénomène de trashing (effondrement) : 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 fautes de page sont générées. Le phénomène de trashing appairait à chaque fois que dans un système de stockage hiérarchique un des niveaux se voit surchargé. C'est par exemple le cas si la mémoire cache est trop petite. À ce moment là les aller-retour incessant de données le long de la hiérarchie vont fortement diminuer le rendement de l'ordinateur. 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.

Principe de localité

Le comportement des programmes n'est pas chaotique : le programme démarre, il fait appelle à des fonctions (ou parties de code) qui en appellent d'autre à leur tour etc. Chacun de ces appels définissent une région. Il est probable que le programme va passer beaucoup de temps à s'exécuter au sein des ces quelques régions : c'est le principe de localité. Le même principe peut être appliqué aux pages contenant des données.

Dit autrement : une programme accède fréquemment à un petit ensemble de pages, et cet ensemble de pages évolue lentement avec le temps.

Si l'on est capable de conserver en mémoire ces espaces souvent accédés, on diminue les chance de voir un programme se mettre à trasher, c'est à dire réclamer des pages qu'on vient de lui retirer récemment.

Le working set : espace de travail

On peut définir un paramètre, Δ, qui est le nombre de références aux pages accédées par le processus durant un certains laps de temps. La figure ci dessous montre la valeur de l'espace de travail à deux instants différents :

Visualisation du Working Set pour &Delta = 10, aux instants

Il faut choisir la valeur de Δ avec soin : trop petite elle ne couvre pas l'espace de travail nominal du processus, si elle est trop grande elle inclus des pages inutiles. Si Δ est égale à l'infini, il couvre la totalité du programme, bien sur.

C'est au système d'exploitation de mettre en œuvre les algorithmes pour que la valeur de Δ soit optimum de sorte à ce que le taux de multiprogrammation et l'utilisation de l'unité centrale soient maximisés. En d'autres termes : éviter le trashing. Si la somme des espaces de travail de chacun des processus est supérieur au nombre de frames disponible, il y aura forcément effondrement.

Fragmentation

Un système paginé à l'inconvénient de générer une fragmentation interne : une page entière est allouée à un processus, alors que seules quelques octets sont occupées. Par exemple, si l'on suppose une taille de page de 4 k, un processus ayant besoin de 5 000 octets va se voir allouer 2 pages, soit 8 192 octets, près de 40% sont «perdu».

Prépagination

Un des avantage des la mémoire virtuelle est de pouvoir commencer l'exécution d'un programme dès que sa première page de code est chargée en mémoire. La prépagination va non seulement charger la première page, mais les quelques suivantes, dont la probabilité d'être accédée est très élevée.

Taille des pages pour quelques ordinateurs

Voici indiqué en bits, l'espace total adressable, la largeur des champs numéro de page, et déplacement.

Machine	Espace adressable	Champs numéro de page	Taille de la page
Atlas	20	11	9
PDP-10	18	9	9
IBM-370	24	13 ou 12	11 ou 12
Pentium Pro	32	12 ou 22	20 ou 12
Alpha 21064	43	13	30

Exemple

• Voici un exemple, tiré du manuel du Tahoe, un clone du Vax :

Les adresses sont codées sur 32 bits (4 Go d'espace total)

La taille de la page est de 1 Ko (codée sur 10 bits).

Les entrées dans la table des pages sont à ce format :

  3  3    2        2   2   2  2
  1  0    7        3   2   1  0                                               0  
+---+------+-----+---+---+---+------------------------------------------------+
| V | PROT |     | N | M | U |                      NDP                       |
+---+------+-----+---+---+---+------------------------------------------------+

Les champs M, U, N et NDP ne sont valides que si le bit V est à 1. Quand V est à 0, le champs NDP contient l'adresse sur le disque dur où se trouve la page.

Le champs PROT est doit être interprété comme ci (la valeur du champs est donnée en binaire sur 4 bits ) :

Valeur	Protection
0000	Aucun accès
1000	Lecture pour le noyau
1100	Lecture/écriture pour le noyau
1010	Lecture utilisateur et noyau
1110	Lecture utilisateur, lecture/écriture pour le noyau
1111	Lecture/écriture utilisateur et noyau

Le bit 24, N (Non-cachée), signifie que la page n'est pas en cache et que le système doit lire ou écrire directement depuis ou vers la mémoire.

Le bit M (Modifiée) est modifié par le le matériel si le contenu de la page est modifié.

Le bit U (Utilisée indique si la page à été lu ou écrite par un processus. Il est utile, en association avec les autres, pour la détermination de l'espace de travail (Working Set) d'un processus (cf. ci-dessus).

• L'appelle système vfork(2) du système d'exploitation Unix crée un nouveau contexte (processus) en dupliquant la table des pages du processus qui fait l'appel (son père). La partie de la table de page marquée en lecture seule (le code) sera dupliquée tel quel. Les pages qui correspondent aux données sont marquées copy on write. Quand Unix doit effectuer une écriture sur une page marquée copy on write il allouera une nouvelle frame, recopiera le contenu de la frame original et fera la modification demandée sur cette nouvelle frame. vfork(2) est donc un appel système peu coûteux car, finalement, il ne fait pas grand chose...

• Pour ceux qui savent lire les sources C d'Unix, la définition des PTE est donnée dans le fichier <.../pte.h> de diverses architectures. Un excellent exemple de comment on utilise celles ci depuis un programme utilisateur est fourni dans le source du programme ps de BSD 4.3.

Segmentation

La segmentation offre une vue de la mémoire plus consistante avec celle de l'utilisateur. En effet celui ci ne considère pas (ou rarement !) la mémoire comme une suite de pages mais plutôt par des espaces, ou des régions, dédiées à une utilisation particulière comme par exemple : le code d'un programme, les données, la pile, un ensemble de sous-programmes, des modules, un tableau etc. La segmentation reflète cette organisation.

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 :

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.

Problème de fragmentation

Les systèmes paginés rencontrent un problème de fragmentation interne : de la place est perdu à la fin d'une page. Les système segmentés connaissent un problème de fragmentation externe : des espaces entre des segments sont trop petits pour loger de nouveaux fragments, cette espace est donc perdu.

L'espace libre de 12 Ko de la disposition mémoire (1) diminue quand une partie est allouée à un nouveau segment. Néanmoins il n'est pas certain que le plus petit segment résiduel, visible en (2), sera assez grand pour répondre à la prochaine requête du système d'exploitation.

Il est possible de le récupérer en compactant la mémoire, c'est à dire en déplacement les segments — tout en reflétant ces modifications dans les table des segments — de sorte à ce qu'il soient contigües. Néanmoins cette opération est coûteuse.

Partage de segments

Il est possible de partager des segments entre processus, comme illustré sur la figure ci dessous, où deux processus Ed1 et Ed2 partage le même segment de code (programme) mais ont des segments pour les données disjoints et de tailles différentes.

Deux utilisateurs utilisant le même programme (un éditeur par exemple) se verront partager le même segment de code, mais pas de données.

Protection dans un système segmenté

Cette protection sera assurée par des bits supplémentaires ajoutées dans la table des segments, de la même façon que pour un système paginé.

Systèmes mixtes paginés/segmentés

Il est possible de mixer les deux modes précédents :

1. la pagination segmentée, où la table des pages sera segmenté. Autrement dit, le numéro de page p du couple (p, d) de l'adresse virtuelle sera interprété comme un segment (s, p’). Ce système résoud le problème de taille de la table des pages.
2. la segmentation paginée, où chaque segment sera paginé. Autrement dit, le champs déplacement d du couple (s, d) de l'adresse virtuelle sera interprété comme un numéro de page et un déplacement (p, d’).

Swapping

Il est parfois nécessaire de supprimer toutes les pages ou segments d'un processus de la mémoire centrale. Dans ce cas le processus sera dit swappé, et toutes les données lui appartenant seront stockées sur en mémoire de masse. Cela peut survenir pour des processus dormants depuis longtemps, alors que le système d'exploitation à besoin d'allouer de la mémoire aux processus actifs. Les pages ou segments de code (programme) ne seront jamais swappés, mais tout simplement réassignés, car on peut les retrouver dans le fichier correspondant au programme (le fichier de l'exécutable).

Bibliographie

• One level storage system, Kilburn, Edwards, Lanigan, Summer, IRE Transactions on elecronic computers, EC-11, vol. 2, avril 1962, pp. 223-235.
• Computer Organization and Design, Hennessy, Patterson, Morgan Koffman, [1]
• Operating system concepts, Patterson, Silberschatz.
• Computer Organisation & Architecture, Hennessy, Patterson, Morgan Koffman.
• Computer Archtecture : A Quantitative Approach
• Computation Structures
• Structured Computer Organisation
• VAX reference Manual
• Sperry 7000/40 Architecture and Assembly Language Manual