Mémoire Virtuelle Flashcards
Quel est le principe de la mémoire virtuelle ?
Donner à chaque processus sa propre mémoire
Qu’est-ce que la mémoire ?
Vaste tableau de M octets/cases, numérotées de 0 à M-1
Indice = adresses
Contenu = complète liberté du programmeur
C’est quoi l’allocation ?
C’est décidé ou mettre quoi dans la mémoire
Physiquement, c’est quoi la mémoire ?
On a une hiérarchie mémoire : cache, RAM, disque, avec coopération entre noyau et le matériel. Plusieurs technologies aux latences très différentes.
Quels sont les deux technologies pour la mémoire vive ?
SRAM (Static Random Access Memory)
DRAM (Dynamic Random Access Memory)
Quel est le principe de la mémoire cache ?
Garder en local d’une copie des données récemment accedées dans la SRAM. en cas de défaut de cache, aller chercher dans la DRAM tout un bloc avec les données voisines
Comment on implémente la mémoire cache ?
On ajoute une petite SRAM dans le CPU, d’une capacité de quelques Mio
[ CPU <—> Cache ] <——> [DRAM]
Indirection ou déréferencement
Accès en direct à quelque chose, i.e. au travers d’une référence.
All problems in CS can be solved by another level of indirection, David Wheeler
Abstraction : adressage direct
Réalité : adressage virtuel
- le CPU ne manipule que des adresses virtuelles, par l’intermédiaire du MMU
Un accès à la mémoire (lecture/écriture)
= un mot = un paquet de plusieurs octets consécutifs que le CPU va lire en un seul coup
Problème 0 : La mémoire est trop lente
Solution : mémoire cache
Memory Management Unit (MMU)
Composant qui traduit chaque adresse virtuelle (VA) en une adresse physique (PA)
= dictionnaire VAS —> PAS
- reconfigurée par l’OS à chaque changement de contexte
Fonctionnement de la MMU
—————— ——— —————
| VM des proc |—> |MMU |—> |Mém. phys.|
——————— ——— —————
VA Indirection PA
Mémoire centrale
= mémoire physique = DRAM
Virtualisation des adresses
On aura un espace d’adressage virtuel (VAS) et un espace d’adressage physique (PAS)
Le VAS
VAS = {0, 1, …, N-1}
Le CPU exprime les adresses sur n bits, N = 2^n
Chaque processus a un VAS privé
Le PAS
PAS = {0, 1, …, M-1}
On aura une adresse pour chaque octet de [DRAM + périphériques]
Les adresses sont exprimées sur m bits : M=2^m
Problème 1 : pas assez de mémoire, vive
Solution : va-et-vient (swapping)
—> ne pas tous stocker en DRAM, mais utiliser la DRAM (à vérif) comme un cache pour les VAS
Problème 2 : gestion des zones libres/occupées en DRAM
Solution : pagination (paging) = une unique taille de bloc
Problème 3 : isolation entre processus, protection du noyau
Garantir que les VAS ne se chevauchent pas dans le PAS
Problème 4 : partage de données en processus
Une même page peut apparaître dans deux VAS.
Pagination à la demande
Utiliser le disque pour agrandir la mémoire vive
↕️
Utiliser la DRAM comme un cache du disque
[CPU] <— [MMU] —> [DRAM] <——> [Disk]
Numérotation des pages
• Numéro de page virtuelle : VPN ∈{0, 1, …, X−1} où X = N ÷P
• Numéro de page physique : PPN ∈{0, 1, …, Y−1} où Y = M ÷P
Traduire des adresses
C’est traduire le numéro des pages : à chaque accès mémoire, le MMU a pour rôle de traduire le VPN en son PPN
Algorithme de traduction VA —> PA
1) Calculer VPN et PO
VA = VPN x P + PO
(VPN = VA ÷ P et PO = VA mod P)
2) Trouver le PPN correspondant au VPN grâce à PT
3) Calculer PA
PA = PPN x P + PO
NB : offset PO identique sur VP et PP
Swap file
Le fichier servant d’espace d’échange, dans lequel est stocké le contenu des processus « alloués sur le disque »
Latence disque
Trop importante pour faire attendre le CPU
=> DRAM = 10 à 100 fois plus lent que SRAM/CPU
=> disque = 1000 à 100 000 fois plus lent que DRAM
Qui gère la pagination à la demande ?
Trop complexe pour être géré purement en matériel
=> le mécanisme est implémenté par le noyau, avec la coopération du matériel
Bloc lors de la pagination
Unique taille P = 2^p
- disque dur géré par blocs appelés secteurs
- DRAM par blocs appelés pages physiques
- VAS par blocs appelés pages virtuelles
Les VAS sont des vues sur la mémoire physique
En vérité chaque donnée est toujours bien stockée en DRAM, mais visible depuis le CPU seulement à une adresse virtuelle
VA -> PA
VA ——-> VPN et PO VPN ——> PPN
P PT
PA = PPN x P + PO
Implémentation des calculs d’adresses
Taille de la page = 2^P
Donc division entière par P, modulo P, multiplication par P et addition de l’offset = gratuite
—-) opération sur les bits
Qu’est-ce que la table de pagination PT ?
C’est un dictionnaire, stocké en mémoire principale
Clé = VPN, Valeur = PPN + métadonnées
[Clé + Valeur] = Page Table Entry PT
1 processus =
1 VAS = 1 PT
Mémoire virtuelle paginée
1) CPU demande à accéder à une adresse virtuelle VA
2) MMU consulte le bon PTE pour connaître le PPN
3) MMU transmets la requête traduite PA sur le bus système
4) Réponse transmise au CPU sans intervention de la MMU
Validité du PTE
On aura différents comportements en fonction de si la page est accessible ou non.
swapped-out ou uncached pages
unallocated ou unmapped pages
Implémenté par un drapeau dans le PTE (valid bit)
Du point de vue de la MMU, page présente en DRAM =
Accès possible = PTE valide
Si CPU essaye d’accéder, MMU traduit vers adresse physique
Du point de vue de la MMU, page absente en DRAM =
Accès impossible = PTE invalide
Si CPU essaye d’accéder, MMU lève une interruption
Quand le PTE est invalide
MMU lève une interruption logicielle (trappe)
Le CPU saute dans le noyau et effectue l’ISR associée, avec une différence si page non-allouée ou si déchargée
Si lorsque le CPU saute dans le noyau la page non allouée
Erreur irrécupérable : le noyau tue le processus fautif (segmentation fault)
Si lorsque le CPU saute dans le noyau la page est déchargée
Défaut de page (page fault) : le noyau doit charger la page en DRAM
Défaut de page
- CPU demande une certaine adresse virtuelle
- MMU trouve un PTE invalide dans la PT : elle envoie une IRQ
- OS vérifie que la page virtuelle demandée existe bien.
- OS trouve une page physique libre (parfois il faut décharger=swap out une autre page)
- OS charge=swap in la page demandée depuis le disque
ici : latence disque = I/O burst > changement de contexte, execution d’un autre proc pour rentabiliser le CPU
- Lorsque la page est chargée : OS met à jour le PTE dans la PT
- OS rend la main au processus d’origine
Principe de localité des accès
Des adresses proches sont accédées à des instants proches
Performances
AMAT, thrashing, …
Average Memory Access Time
AMAT = page hit time + (page fault rate x page fault penalty)
Les défauts de pages doivent rester rares
Page hit time
≈ latence DRAM ≈ 50 ms
Page fault penalty
≈ latence disque ≈ 5 ms
Working Set d’un processus
C’est l’ensemble des pages virtuelles accédées récemment par ce processus
Thrashing (écroulement soudain des performances)
Se produit lorsque
Somme(Working Set Sizes) > taille(DRAM)
- l’écroulement soudain des performances est causés par un excès de défauts de page.
Remède = réduire le degré de multiprogrammation.
Comment gère-t-on les zones libres et occupées en drame ?
Allocation dynamique de pages : appel système mmap()
mmap()
include <sys/mman.h>
void * mmap(NULL, size_t len, int prot, int flags, 0, 0);
renvoie l’adresse virtuelle de la nouvelle région
len > le noyau allouera toujours un nb entier de pages
prot > PROT_READ, PROT_WRITE, PROT_EXEC
flags > MAP_ANONYMOUS | MAP_PRIVATE
Notion de swap file
Memory swapping = va-et-vient entre DRAM et un swap file
Swap in lors d’un défaut de page
Swap out pour libérer des pages physiques
MAP_ANONYMOUS
swap depuis/vers un fichier anonyme
Allocation paresseuse de la région, page par page
- le premier accès dans une page causera un défaut
- le noyau alloue (et efface) une page physique quelconque
MAP_FILE
swap depuis/vers un fichier ordinaire
Contenu initial de la région = lu depuis le fichier
Lecture paresseuse, seulement lorsque défaut de page
Memory-Mapped I/O
Communication avec les périphériques via leurs adresses physiques
En général : adresses MMIO réservées au noyau + drivers
Et adresses DRAM allouées au processus userland
Isolation entre processus
Chaque processus dispose d’un VAS individuel
> l’OS maintient une table de pagination pour chaque processus
Partage entre processus
Une même page peut être présente dans plusieurs VAS (page physique visible depuis plusieurs processus)
Partage entre processus et projection des pages
- en lecture seule
- en lecture/écriture
- en copy-on-write
Projection en lecture seule
Ne consomme aucun espace supplémentaire sur le disque (ex, le fichier executable)
Projection en lecture/écriture
Mémoire partagée, permet la communication entre plusieurs processus
Projection en copy-on-write
Duplication paresseuse : éviter de stocker deux fois des pages identiques.
Idée : ne pas dupliquer les données immédiatement mais attendre qu’une des deux copies soit effectivement modifiée (fork() astucieux)
Dupliquer un processus
Dédoubler son PCB et son VAS
Paramètres flags contrôlant partage dans MAP_ANONYMOUS
si flags = MAP_ANONYMOUS | MAP_SHARED
- processus enfants pourront accéder
si flags = MAP_ANONYMOUS | MAP_PRIVATE
- isolation via Copy-On-Write
Signature de mmap dans le cas d’un MAP_FILE
void* mmap(…, …, int fd, int offset);
avec fd = file descriptor retourné par open
Paramètres flags dans le cas d’un MAP_FILE
si flags = MAP_FILE | MAP_SHARED
- swap vers le fichier d’origine
si flags = MAP_FILE | MAP_PRIVATE
- Copy-On-Write puis swap vers fichier anonyme
Protection des périphériques matériels
Il suffit pour le noyau de s’assurer que chaque processus ne voit jamais les adresses physiques des périphériques
