[PDF] La mémoire virtuelle - Traduction dadresses et pagination à la

View - Download La mémoire virtuelle - Traduction dadresses et pagination à la

Previous PDF

Next PDF

La mémoire virtuelle

Traduction d"adresses et pagination à la demande

Address Translation & Demand Paging

Guillaume Salagnac

Insa de Lyon - Informatique

Résumé des épisodes précédents : noyau vs userlandProcessus 1HardwareProcessus 2KernelArchitectureVM2VM1

Le processus vu comme une "machine virtuelle»

un processeur pour moi tout seul : "CPU virtuel» une mémoire pour moi tout seul : "mémoire vir tuelle» 2/42

La mémoire virtuelle : intuition

Principe : chaque processus a sa propre mémoire une mémoire = un vaste tableau d" octets indices = adresses •contenu : complète liberté du programmeur décider où mettre quoi = allocation l"intér ieur du processus (cf chap .4)

Implémentation :

combinaison de plusieurs technologies hiérarchie mémoire : cache ,RAM, disque •en principe, invisible pour le programmeur

coopération entre noyau et matérielFFF...FFF:01110101110010111010011111001100000...000:000...001:000...002:

3/42

Problème n

o0 : la mémoire est trop lente

Seulement

deux technologies pour la mémoire viv eSRAM :1 bit = 6 tr ansistors

Mémoire cache : ajouter une petite SRAM

dans le CPU garde une copie des données récemment accédéesCPUCacheDRAM capacité : quelques Mio

DRAM seulement utile sur

déf autde cache (en V O: cache miss) solution entièrement HW : complètement invisible pour le SW 4/42

Problème n

o1 : la mémoire est trop petite un processus = 2

64adresses = 18446744073709551616 octets

= 17179869184 GioFFF...FFF:01110101110010111010011111001100000...000:000...001:000...002:

VSDRAM

mémoire physique = quelques Gio 5/42

Problème n

o2 : comment gérer l"espace disponible?

Même si chaque processus n"a pas besoin de 2

64octets,

•il y a de nombreux processus simultanément •des dizaines? des centaines? des milliers? •combien d"espace occupe chacun? pour combien de temps? •qui manipulent des éléments hétérogènes 6/42

Problème n

o3 : comment protéger chaque processus?Process 1code 1data 1code 2Process 2var 1data 2var 2

Problème n

o4 : comment permettre la coopération?Process 1code 1data 1code 2Process 2var 1data 2var 2shared memory 7/42

Solution : ajouter un niveau d"indirection

All problems in computer science can be solved by another level of indirectionDavid WheelerDéfinition : Indirection aka déréferencementProcessus 1 Accèsindirectà quelque chose, i.e. au travers d"uneréférenceExemples •pour joindre quelqu"un au téléphone, devoir pas- ser d"abord par un standard invoquer une méthode virtuelle en C++, Java...

Processus 1

IndirectionProcessus NM

´emoire virtuelleM

´emoire physique8/42

Abstraction : adressage directCPUMemoryM-2:M-1:LOAD 1234011101011100101110010010010110011010000001011010100011000111000101011001101001111100110010100000 0101101010001100 011100010:1:1232:1233:1234:1235:1236:1237:1238:2:

la mémoire = tableau deMcases numérotées de 0 àM-1 une case = un octet (1B = 1 b yte ) = 8 bits un accès (i.e. lecture ou écriture) = un mot ( word ) = un paquet de plusieurs octets consécutifs en général 4 octets (= 32 bits) ou 8 octets (= 64 bits) 9/42

Réalité : adressage virtuelCPUMainmemor y0:1:5328:5329:5330:5331:5332:5333:5334:M-2:M-1:LOAD1234 011101012:110010111001001001011001101000000101101010001100011100010101100110100111110011001010000001011010 1000110001110001 MemoryManagementUnit1010000001011010 1000110001110001 LOAD5330 VirtualAddressPhysicalAddress

Sur une architecture moderne :

CPU ne manipule que des

"adresses vir tuelles» (V A) composant supplémentaire :

Memor yManagement Unit

(MMU) traduit

à la v oléechaque V Aen une

"adresse ph ysique» (P A) mem centrale = mem principale = mem physique = DRAM 10/42

Virtualisation des adresses : remarques

Espace d"adressage virtuel

= V AS= {0,1,2,...,N-1} chaque processus dispose d"un VAS privé

Espace d"adressage physique

= P AS= {0,1,2,...,M-1} une adresse pour chaque octet de (DRAM + périphériques) traduit les adresses virtuelles en adresses physiques sera reconfigurée par l"OS à chaque changement de conte xte11/42

À retenir : pourquoi la mémoire virtuelle

Problème 1 : pas assez de mémoire vive

= utiliser la DRAM comme un cache pour les VAS Problème 2 : gestion des zones libres/occupées (en DRAM)

Problème 3 :

isolation entre processus ,protection du no yau

Problème 4 :

par tage de données entre processus 12/42 Plan

1. La mémoire virtuelle : intuitions et motivation

2. Pagination et traduction d"adresses

3. Memory swapping : pagination à la demande

4. Gestion de la mémoire physique

5. Protection, Isolation et partage

13/42

Pagination à la demande : principe

utiliser le disque pour "agrandir la mémoire vive» utiliser la DRAM comme un cache du disque CPUDRAMDiskVASPAS0123012336373839ABCABBACMMU 14/42

Pagination à la demande : remarques

contenu des processus "alloué sur le disque» dans un fichier (ou plusieurs) appelé leswap file •données chargées en RAM seulement lorsque accédées latence disque trop importante pour faire attendre le CPU

DRAM = 10x à 100x plus lent que SRAM/CPU

•disque = 1000x à 100 000x plus lent que DRAM avec la coopér ationdu matér iel •invisible pour le programmeur d"applicationUne unique taille de bloc : P=2 poctets (en général P=4Kio) parfois : "fr ames» en V O,soit "cadres» en VF 15/42

Numérotation des pagesN-2.N-1.0.1.2.P-1.P.P⇁1.2P-1.2P.Virtual Address SpaceVirtual AddressN-P.Virtual Page nν0

Virtual Page nν1 Virt▷ Page nνX-1 M-2.M-1.0.1.2.P-1.P.P⇁1.2P-1.2P.Physical Address SpacePhysical AddressM-P.

Physical Page nν0

Physical Page nν1

Phys▷ Page nνY-1VS

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 16/42

Traduire des adresses = traduire des nº de pagesN-2:N-1:0:1:2:P-1:P:P+1:2P-1:2P:Virtual Address SpaceVAN-P:Virtual Page nº0

Virtual Page nº1 Virt. Page nºX-1 M-2:M-1:0:1:2:P-1:P:P+1:2P-1:2P:Physical Address SpacePAM-P:

Physical Page nº0

Physical Page nº1

Phys. Page nºY-110X01VPN=⌊VA÷P⌋YPPN=⌊PA÷P⌋42}Physical Page nº42011101011100101110010010010110011010000001011010100011000101100110100000010110100111000101011001100011000101100111001100

Rôle de la Memory Management UnitN-2:À chaque accès mémoire, "traduire» leVPN en son PPN 17/42

Traduction d"adresses : principe

un Virtual Address Space = une "vue» sur la mémoire ph ysique en vérité chaque donnée est toujours bien stockée en DRAM mais visible depuis le CPU seulement à une

adresse vir tuelleAlgorithme de traduction VA7→PA (implémenté par la MMU)1)calculer VPN = ⌊VA÷P⌋etPO = V Amod P

autrement dit, VA = VPN×P + PO •PO =P ageOffset = position à l"intér ieurde la page 2) trouv erle

PPN correspondant au VPN

dans un annuaire appelé la

T ablede P agination

= Page TablePT 3 ) calculer

P A= PPN ×P + PO

offset identique dans la page virtuelle et la page physique18/42

Implémentation des calculs d"adresses

Taille de page = P = 2

pdonc :

Exemple avec m=n=16 et p=10 :1011010010100110?

???????VirtualAddress(nbits) =1011010010100110??

??VirtualPageNumber (npbits) PageOffset(pbits) 0010100110011010?PhysicalPageNumber (mpbits) =0110100010100110?

???????PhysicalAddress(mbits) PageTable: VPN?→PPNPPO= VPO 19/42

Implémentation de la table de pagination

PT = dictionnaire = "tab lede correspondances» = lookup table une clé = un nº de pages virtuelle VPN une valeur = un nº de page physique PPN + des métadonnées une paire clé+v aleur = une

P ageT ableEntr y

PTE PT elle-même stockée en mémoire principale beaucoup trop de PTE pour tenir en entier dans la MMU autrefois : tableau exhaustif. aujourd"hui : arbre de recherche consultation : implémentée en matériel par la MMU

Rappel : 1 processus = 1 VAS = 1 PT

20/42

Mémoire virtuelle paginée : à retenirCPUMMUPAS0123VAS0123VPNPPN012312VPNPPNØØPTVA=VPN.POPA=PPN.POAABBCD

1)

CPU demande à accéder à une

adresse vir tuelle V A 2) MMU consulte le bon PTE (dans la PT) pour connaître le PPN 3)

MMU tr ansmetla requête tr aduiteP Asur le

b ussystème 4) réponse tr ansmiseau CPU sans inter ventionde la MMU 21/42
Plan

1. La mémoire virtuelle : intuitions et motivation

2. Pagination et traduction d"adresses

3. Memory swapping : pagination à la demande

4. Gestion de la mémoire physique

5. Protection, Isolation et partage

22/42

Pagination à la demande : principe

utiliser le disque pour "agrandir la mémoire vive» utiliser la DRAM comme un cache du disque CPUDRAMDiskVASPAS0123012336373839ABCABBACMMU Problème : et si le programme accède à sa page n o2? et no3? 23/42

Table de pagination : PTE valide vs PTE invalide

Page Virt. n

o3 : existe sur le disque maispas chargée en DRAM en VOswapped-outouuncached

Page Virt. n

o2 : n"existe pas du tout :adresses vir tuellesin utilisées en VOunallocatedouunmapped

Du point de vue de la MMU :

page présente en DRAM = accès possible =

PTE v alide

page absente de DRAM = accès impossible =

PTE in valide

implem : un drapeau (booléen) dans le PTE : le"valid bit» 24/42

Accès à une page virtuelle au PTE invalide

Quand un processus accède à une page invalide :

MMU lève une interruption logicielle (trappe)

•CPU saute dans le noyau et exécute l"ISR associée

Idée : noter le n

ode secteur dans la PTE, à la place du PPN!

Exemple :

PTE valide?n ode page physique ou n ode secteurPTE n o0vPP n o2PTE n o1vPP n o0PTE n o2iØ PTE n o3isecteur n

o38(en vrai c"est un peu plus compliqué, cfvm_area_structdans Linux mais l"idée est la même)25/42

Défaut de page : déroulement temporel

1.

CPU demande une cer taineadresse vir tuelle

2.

MMU trouv eun PTE in validedans la PT

3.

MMU en voieune requête d"interr uption

4. OS vér ifieque la page vir tuelledemandée e xistebien 5.

OS trouv eune page ph ysiquelibre

il faut parfois décharger ( swap out ) une autre page 6.

OS charge (

swap in ) la page demandée depuis le disque •exécution d"un autre processus pour rentabiliser le CPU 7. lorsque page chargée : OS met à jour le PTE dans la PT 8.

OS rend la main au processus d"or igine

accès mémoire ré-exécuté, cette fois avec succès •toujours "invisible» pour le programmeur 26/42

Pagination à la demande VS performances

Temps d"accès moyen : Average Memory Access Time AMAT = page hit time + (page fault rate×page fault penalty) page hit time≈latence DRAM≈50 ns page fault penalty≈latence disque≈5 ms accédées récemment par ce processus

Attention : si

somme( Working Set Sizes ) > taille(DRAM) alors causé par un excès de défauts de page remède : réduire le degré de multiprogrammation 27/42
Plan

1. La mémoire virtuelle : intuitions et motivation

2. Pagination et traduction d"adresses

3. Memory swapping : pagination à la demande

4. Gestion de la mémoire physique

5. Protection, Isolation et partage

28/42

Pourquoi la mémoire virtuelle?

Problème 1 : pas assez de mémoire vive

= utiliser la DRAM comme un cache pour les VAS Problème 2 : gestion des zones libres/occupées (en DRAM)

Problème 3 :

isolation entre processus ,protection du no yau

Problème 4 :

par tage de données entre processus 29/42

Allocation dynamique de pages

Grâce à la pagination

chaque VP peut être placée dans n"impor tequelle PP typiquement, dans différentes PP au cours du temps Allocation de nouvelle(s) page(s) vierge(s) pour un processus es:VAS0123mmap(...) 30/42
L"appel systèmemmap()Pour demander dynamiquement l"allocation de nouvelles pages include void* mmap(NULL, size_tlen,//length of region ,in bytes intprot,//protections intflags,//type of mapping des pages vierges juste pour moi(et la barre verticale est un "bitwise OR») 31/42

Notion de "Swap File»

Rappel : chaque page virtuelle existe d"abord sur le disqueCPUDRAMDiskVASPAS0123012336373839ABCABBACMMU

memory swapping = v a-et-viententre DRAM et un s wapfile swap in lors d"un déf autde page swap out pour libérer des pages ph ysiques 32/42

Différents types de mapping mémoire

Allocation paresseuse de la région, page par page : le premier accès dans une page causera un défaut noyau alloue (et efface) une page physique quelconque

Paramètreflagscontrôle aussi le partage

siflags = MAP_ANONYMOUS|MAP_SHARED: siflags = MAP_ANONYMOUS|MAP_PRIVATE: 33/42

Différents types de mapping mémoire

Contenu initial de la région = lu depuis le fichier signaturevoid* mmap(...,..., int fd, int offset); fd=file descriptorretourné paropen() lecture paresseuse, seulement lorsque défaut de page

Paramètreflagscontrôle le "partage»

siflags = MAP_FILE|MAP_SHARED siflags = MAP_FILE|MAP_PRIVATE 34/42
Différents types de mapping mémoireMAPANONYNOUSMAPFILEsur le fichierfdcontenu initialpages vierges´ ecritures´ ecrituresswap outswap outpages vierges´ ecrituresswap out´ ecrituresswap outpriv

´ees (copy-on-write)MAPSHAREDMAPPRIVATElu depuis le fichierfdvers le fichierfdglu depuis le fichierfdvers fichier anonymevers fichier anonymevers fichier anonymepriv

´ees (copy-on-write)visibles depuis tous

les processus qui ont ce mappingcontenu initialcontenu initialcontenu initial 35/42
Plan

1. La mémoire virtuelle : intuitions et motivation

2. Pagination et traduction d"adresses

3. Memory swapping : pagination à la demande

4. Gestion de la mémoire physique

5. Protection, Isolation et partage

36/42

Protection des périphériques

Rappel : Memory-Mapped I/O

communication avec les périphs via leurs adresses ph ysiquesEn général adresses DRAM : allouées aux processus userland adresses MMIO : réservées au noyau + drivers

Note : la MMU elle-même est un

périphérique 37/42

Isolation entre processus

Principe : chaque processus dispose d"un VAS individuel

Remarques :

RAM allouée aux pages virtuelles "les plus utiles»

MMU reconfigurée à chaque

changement de conte xte permet aussi d"isoler le noyau vs processus userland 38/42

Isolation vs partage : quelques cas particuliers

Rappel : chaque processus dispose d"un VAS distinct... ...mais une même page peut être présente dans plusieurs VAS! Exemple :VAS1PAS01230123ØØVAS20123ØØPage Table 1Page Table 2CABABBEED

Projection des pages

•en lecture seule : par ex, le fichier exécutable •ne consomme aucun espace supplémentaire sur le disque •en lecture/écriture : mémoire partagée •permet la communication entre plusieurs processus •en copy-on-write : duplication paresseuse •évite de stocker deux fois des pages identiques 39/42
Copy-On-Write vsfork()Idée : ne pas dupliquer les données immédiatement, mais attendre qu"une des deux copies soit effectivement modifiéeVAS1PAS01230123Page Table 1ABABr/wr/w Imaginons un certain processus P1 avec deux pages A et B : on note PCB1 sonProcess Control Block, et on note PT1 sa table de pagination Initialement, les deux pages sont accessibles en lecture-écriture 40/42
Copy-On-Write vsfork()Idée : ne pas dupliquer les données immédiatement, mais

attendre qu"une des deux copies soit effectivement modifiéeVAS1PAS01230123VAS20123Page Table 1ABABABPage Table 2rorororo

P1 fait unfork(), donnant naissance à P2. Le noyau : duplique PCB et table de pagination marquetousles PTE (de PT1 et de PT2) en lecture seule marque dans les deux PCB ces pages commecopy-on-write 40/42
Copy-On-Write vsfork()Idée : ne pas dupliquer les données immédiatement, mais

attendre qu"une des deux copies soit effectivement modifiéeVAS1PAS01230123VAS20123Page Table 1ABABABPage Table 2rorororoP1

Lorsque

P1 essa yed"écr ire

dans sa page n o0 :

MMU trouve un PTE en lecture seule

40/42
Copy-On-Write vsfork()Idée : ne pas dupliquer les données immédiatement, mais

attendre qu"une des deux copies soit effectivement modifiéeVAS1PAS01230123VAS20123Page Table 1ABABABPage Table 2Ar/wr/wroro

Le noyau constate dans PCB1 que la page est en copy-on-write il duplique finalement le contenu de la page et modifie les deux PT+PCB pour autoriser lecture/écriture puis, rend la main à P1 40/42
Copy-On-Write vsfork()Idée : ne pas dupliquer les données immédiatement, mais

attendre qu"une des deux copies soit effectivement modifiéeVAS1PAS01230123VAS20123Page Table 1A"BABABPage Table 2A"r/wr/wroroP1

P1 essaye à nouveau d"écrire dans sa page n

o0 nouvelle donnée A" visible seulement depuis P1 En résumé :fork()"duplique» bien le VAS, mais ne copie pas les pages avant que ce soit vraiment utile 40/42
Plan

1. La mémoire virtuelle : intuitions et motivation

2. Pagination et traduction d"adresses

3. Memory swapping : pagination à la demande

4. Gestion de la mémoire physique

5. Protection, Isolation et partage

41/42

À retenir : la mémore virtuelle

La hiér archiemémoire plusieurs technologies aux latences très différentes (ns vs ms) pr. de localité des accès : adresses proches∼instants proches cache du processeur : géré en matér iel

Traduction d"adresses

découplage addresses CPUquotesdbs_dbs48.pdfusesText_48

[PDF] pagination mémoire fin d'étude

[PDF] pagination mémoire master

[PDF] pagination mémoire word

[PDF] pagination word 2007

[PDF] pagne noir de bernard dadié pdf

[PDF] pagne noir résumé

[PDF] paht

[PDF] pain d'antan recette

[PDF] pair impair

[PDF] Pair ou impair

[PDF] paire de chromosome 11 drépanocytose

[PDF] Paire ou impair

[PDF] Paix de Dieu et Treve de Dieu

[PDF] Paix et Guerre

[PDF] Palais bourbon