Gestione della memoria centrale - so.sprg.uniroma2.itso.sprg.uniroma2.it/lucidi/lez-07-p1.pdf ·...

Gestione dellamemoria centrale

Marco Cesati

Schema della lezione

Memoria centrale

Segmentazione

Paginazione

Linux su Intel IA-32

SO’17 7.1

Lezione 7Gestione della memoria centrale

Sistemi operativi

9 maggio 2017

Marco Cesati

System Programming Research GroupUniversità degli Studi di Roma “Tor Vergata”


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.2

Di cosa parliamo in questa lezione?

La gestione della memoria centrale

1 Schemi di indirizzamento della memoria centrale2 La segmentazione3 La paginazione4 Linux su Intel IA-32


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.3

La memoria centrale

La memoria centrale è un componente essenziale per uncalcolatore elettronico:

È costituita dai chip di memoria dinamica (RAM)Contiene il codice ed i dati dei processi attivi nel sistemaContiene tutte le strutture di dati del nucleo del SO

La memoria centrale è una risorsa condivisa disponibile inquantità limitata

Deve essere gestita e amministrata dal SO

La modalità con cui un SO gestisce la memoria centraledipende essenzialmente dalle caratteristiche dell’architetturahardware del calcolatore

Gran parte delle architetture hardware moderne utilizza lostesso schema di base per la memoria centrale


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.4

Architettura della memoria centrale

Memory Management Unit (MMU)

Componente hardware del calcolatore elettronico che ha ilcompito di arbitrare, gestire e realizzare i trasferimenti dei datida e verso la memoria primaria

Poiché la memoria primaria è costituita una gerarchia di livellidi memoria, la MMU deve contenere circuiti per

controllare il funzionamento della memoria statica (cache)gestire le transazioni da e verso la memoria centrale(memoria dinamica, RAM)

Inoltre la MMU offre meccanismi essenziali per la realizzazionedi SO multiprogrammati:

astrazione degli spazi di indirizzamento dei processiprotezione degli accessi alle regioni di memoriamemoria virtuale


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.5

Indirizzi logici, fisici e di I/O

Si consideri una determinata cella di memoria: ad essa sonoassociati differenti tipi di indirizzi

Indirizzo logico

L’indirizzo che deve essere scritto in un registro della CPU onel codice operativo di una istruzione macchina

Indirizzo fisico

L’indirizzo che deve essere posto sul bus di comunicazione traCPU e RAM

Indirizzo di I/O

L’indirizzo che deve essere posto sul bus di sistema per avviareun trasferimento diretto tra RAM e periferica di I/O (DMA)


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.6

Indirizzi virtuali

In tutte le architetture dei microprocessori moderni, gliindirizzi logici sono diversi dagli indirizzi fisici

La trasformazione tra indirizzi logici e fisici è realizzataautomaticamente dalla MMU

CPU MMU RAMind. logico ind. fisicog

L’associazione (mapping) tra indirizzi logici e fisici è ingenere

dinamicamente modificabile

diversa da processo a processo

In questi casi l’indirizzo logico è anche chiamato

indirizzo virtuale


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.7

Spazi di indirizzamento

Lo spazio di indirizzamento fisico della memoria centrale ècostituito dall’insieme di tutti gli indirizzi fisici chepotenzialmente identificano celle di memoria RAM

La dimensione dello spazio di indirizzamento fisico è legataalla quantità di RAM installabile nel sistema

Non fa parte delle caratteristiche architetturali

Lo spazio di indirizzamento logico (o virtuale) è costituitodall’insieme di tutti gli indirizzi logici che possono essereutilizzati come identificatore di una cella di memoria in unregistro della CPU oppure nel codice operativo di unaistruzione macchina

È una caratteristica architetturale del calcolatore

Generalmente se un indirizzo logico è costituito da n bit, lospazio di indirizzamento logico ha dimensione 2n

La dimensione dell’indirizzo logico spesso coincide con ladimensione dei registri della CPU (ad es., 32 o 64 bit)

Indirizzi logici e fisici possono avere dimensioni differenti? Sì!


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.8

Vantaggi degli indirizzi virtuali

Due processi eseguono due programmi differenti:

Senza indirizzi virtuali Con indirizzi virtuali

I due processi debbono uti-lizzare indirizzi logici dif-ferenti perché condividonolo spazio di indirizzamentologico

I due processi possono uti-lizzare gli stessi indirizzi lo-gici, quindi compilazione ecaricamento dei programmisono più facili

È difficile impedire che unprocesso acceda ad un datodell’altro processo

È facile realizzare mecca-nismi di protezione degliaccessi

Il SO deve assegnare imme-diatamente a ciascun pro-cesso tutta la memoria ne-cessaria per l’intera esecu-zione

Il SO può creare dinami-camente l’associazione traindirizzo virtuale e fisico equindi ritardare l’assegna-zione della memoria


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.9

Trasformazione di indirizzi virtuali in indirizzi fisici

In linea di principio a ciascun indirizzo virtuale potrebbeessere associato un diverso indirizzo fisico

Questa associazione deve essere memorizzata dal SOutilizzando una parte della memoria centrale

Nel caso peggiore per ciascun indirizzo di memoria logico(o fisico) identificante un singolo byte si dovrebbero“sprecare” diversi byte di memoria per registrare ilcorrispondente indirizzo fisico (o logico)

L’associazione tra i due tipi di indirizzo viene realizzata pergruppi di dimensione minima di centinaia o migliaia di byte

Esistono sostanzialmente due schemi generali perrealizzare questa associazione:

La segmentazione

La paginazione


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.10

Segmentazione della memoria

La segmentazione della memoria centrale è un meccanismobasato sul concetto di segmento

Segmento

Insieme di indirizzi logici contigui caratterizzato da:un indirizzo fisico di baseuna lunghezza (numero di celle/indirizzi nel segmento)attributi e diritti di accesso comuni alle celle del segmento

La memoria centrale occupata da un processo può esseresuddivisa in modo naturale in diversi segmenti, ad esempio:

Il segmento di codice contenente le istruzioni macchina daeseguire, con soli diritti di esecuzioneIl segmento di dati contenente i dati del programma, condiritti di lettura e scritturaIl segmento di stack contenente lo stack User ModeUn segmento per lo heap (allocazione dinamica)Per ciascuna libreria, un segmento di codice ed uno di dati


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.11

Gli indirizzi logici con la segmentazione

Se l’architettura utilizza il meccanismo di segmentazione dellamemoria, il formato di un indirizzo logico è il seguente:

Segmento Spiazzamento

“Segmento” rappresenta un indice o altro identificatore perun determinato segmento di memoria“Spiazzamento” rappresenta la posizione (offset) dellacella richiesta all’interno del segmento

Gli indirizzi logici con segmentazione non sononecessariamente semplici valori numerici

Nel linguaggio C le operazioni di differenza trapuntatori sono ben definite soltanto per puntatoriallo stesso oggetto o vettore!


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.12

Esempio di segmentazione

Un processo esegue un programma costituito da 10 KiB diistruzioni macchina, 64 KiB di dati e 24 KiB di stack

Nel suo PCB è presente la seguente tabella dei segmenti:

# seg. base limite flag

0 0x00001000 10239 Exec codice1 0x00004000 65535 Read+Write dati2 0x00100000 24575 Read+Write stack3 0x0001a000 8191 Read+Write+Exec heap

...

A cosa corrisponde l’indirizzo fisico 0x00002010?

È nel segmento #0 all’offset 0x1010, quindi corrispondeall’istruzione macchina all’indirizzo logico <0;4112>

A cosa corrisponde l’indirizzo logico <3;12240>?

Non è un indirizzo logico valido!


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.13

Svantaggi della segmentazione

Quali sono i principali svantaggi della segmentazione?

A ciascun segmento deve corrispondere una zonacontigua di memoria fisica

Il SO deve assegnare a ciascun processo tutta la memoriafisica necessaria per l’esecuzione, anche se il processo nonla utilizzerà realmente

Possibile frammentazione: la memoria fisica ancora libera èsuddivisa in tante porzioni ciascuna delle quali troppopiccola per contenere un segmento di un nuovo processo

Lo spazio degli indirizzi logici di un processo non è“connesso” ed uniforme

L’indirizzo logico è suddiviso in due parti che debbonoessere trattate, anche a livello di codice macchina, in mododifferente


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.14

La paginazione

La paginazione della memoria centrale è un meccanismobasato sul concetto di pagina

Pagina (page)

Gruppo di indirizzi logici contigui di lunghezza prefissata conun insieme di attributi e diritti d’accesso comuni

Per estensione “pagina di memoria” indica anche un blocco didati di lunghezza prefissata in memoria primaria o secondaria

Qual è la principale differenza con la segmentazione?

I segmenti hanno lunghezza variabile mentre le paginehanno lunghezza costante e prefissataLa lunghezza prefissata permette di semplificare erendere più efficienti i circuiti della MMU

La lunghezza è sempre una potenza di due!

Lunghezza di una pagina: tra 512 byte e alcuni megabyte


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.15

Gli indirizzi fisici con la paginazione

Si consideri una architettura con pagine di dimensione N = 2n

La memoria fisica è partizionata in blocchi di N indirizzifisici chiamati page frame o pagine fisiche

In ciascuna page frame è memorizzabile il contenuto di unaed una sola pagina di memoria

L’indirizzo fisico iniziale di ciascuna page frame è unmultiplo di N:

Gli n bit meno significativi sono zero

I restanti bit sono chiamati numero di pagina fisica (PFN,Page Frame Number)

Formato di un generico indirizzo fisico:

PFN Spiazzamento

Ad esempio, se N = 4096, l’indirizzo fisico 0x00031104corrisponde alla cella in posizione 0x104 = 260 dellapage frame 0x31 = 49


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.16

Gli indirizzi logici con la paginazione

A differenza della segmentazione, gli indirizzi logici utilizzaticon la paginazione costituiscono uno spazio di indirizzamentoconnesso ed uniforme

Il formato dell’indirizzo logico è:

VPN Spiazzamento

Spiazzamento: posizione relativa della cella nella paginaÈ costituito dagli n bit meno significativi

VPN (Virtual Page Number): numero di indice della pagina

È costituito dai restanti bit più significativi

Il meccanismo di traduzione da indirizzi logici a indirizzi fisicitrasforma un VPN in un PFN e lascia invariati i bit dispiazzamento


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.17

Esempi di traduzione con la paginazione

Esempio #1:Dimensione pagina: N = 4096 byte (n = 12 bit)

Dimensione degli indirizzi logici: 32 bit (4 GiB)Dimensione degli indirizzi fisici: 30 bit (1 GiB)

Dimensione dei VPN: 32 − 12 = 20 bitDimensione dei PFN: 30 − 12 = 18 bit

Esempio #2:Dimensione pagina: N = 4096 byte (n = 12 bit)

Dimensione degli indirizzi logici: 32 bit (4 GiB)Dimensione degli indirizzi fisici: 36 bit (64 GiB)

Dimensione dei VPN: 32 − 12 = 20 bitDimensione dei PFN: 36 − 12 = 24 bit

Cosa comportano indirizzi logici più piccoli degli indirizzi fisici?

Un singolo processo può indirizzare soltanto unsottoinsieme della memoria fisicaNon è una buona soluzione, ma è spesso utilizzata permantenere la compatibilità architetturale (ad es. in IA-32)


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.18

La tabella di paginazione

Il cuore del meccanismo di paginazione è una struttura di datiche memorizza le associazioni tra indirizzi logici e fisici

Nella sua forma più semplice è una tabella di paginazione(page table):

Definita per ciascun processo e collegata al PCBCodificante l’indirizzo logico ed il corrispondente indirizzofisico per ciascuna pagina di memoria utilizzata dalprocessoPer ciascuna pagina memorizza anche attributi e diritti diaccesso

Esistono due tipi principali di tabelle di paginazione:

La tabella di tipo diretto è specifica per un singoloprocesso, e memorizza l’indirizzo fisico associato aciascun indirizzo logico utilizzato dal processoLa tabella di tipo inverso è comune per tutti i processi, ememorizza l’indirizzo logico associato a ciascun indirizzofisico in uso nel sistema


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.19

Il registro PTP

La tabella di paginazione è memorizzata in memoriacentrale

Nei sistemi multiprocessore, ciascuna CPU utilizza unatabella di paginazione diversa

Per poter trasformare un indirizzo logico in un indirizzofisico la MMU deve leggere il contenuto della tabella dipaginazionePertanto ogni CPU con paginazione contiene un registrospeciale:

Chiamato genericamente PTP (Page Table Pointer) o PTR(Page Table Register)

Contenente l’indirizzo fisico della tabella di paginazione

Se l’architettura utilizza tabelle di paginazione dirette ed ilSO è multiprogrammato, ciascun processo utilizza unapropria tabella di paginazione

il contenuto del PTP deve essere modificato ad ogni cambiodi contesto (processo)


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.20

Esempio di tabella di paginazione diretta

PTP

+

+

Page Table

Page frame

O f f s e tV P N


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.21

Paginazione gerarchica

Lo schema di paginazione diretta finora presentato ha un gravedifetto: la tabella di paginazione contiene una voce perciascuna pagina di memoria ed è diversa per ciascun processo

Esempio: con indirizzi logici da 32 bit, pagine da 4096 byte,PFN e flag codificati in 32 bit, ciascun processo occupa per lasola tabella di paginazione

232/212 × 4 = 4 MiB, ossia 1024 pagine

In un sistema con 100 processi attivi e 2 GiB di RAM, le tabelledi paginazione occupano oltre il 12% della memoria disponibile

Per porre rimedio a questo problema generalmente si hannotabelle di paginazione dirette gerarchiche

Sono allocate solo le tabelle “interne” che mappanoblocchi di indirizzi logici almeno parzialmente utilizzatiLe tabelle di paginazione non sono contigue in memoriafisica, riducendo i rischi di frammentazione della memoria


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.22

Paginazione diretta a due livelli

Il più semplice esempio di paginazione diretta gerarchicaconsiste in tabelle di paginazione organizzate su due livelli:

Una tabella esterna o di primo livello contiene riferimenti atabelle di paginazione interne o di secondo livelloLe tabelle interne contengono i PFN degli indirizzi logiciutilizzati dal processo

In uno schema a due livelli il VPN è costituito da due indici:

La parte più significativa è l’indice della tabella internaentro la tabella esternaLa parte meno significativa è l’indice della pagina entro latabella interna

Ad esempio, se N = 4096 e il VPN è costituito da 20 bit divisiin due parti uguali:

La tabella esterna ha 210 = 1024 vociCiascuna tabella interna ha 210 = 1024 voci e mappa unaporzione di 1024 × 4096 = 4 MiB di indirizzi logiciSe una voce occupa 4 byte, ciascuna tabella occupa 4 KiB


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.23

Paginazione diretta a tre o quattro livelli

Nelle architetture a 64 bit due livelli di tabelle di paginazionenon sono più sufficienti

Con indirizzi logici da 64 bit, pagine da 8192 byte, voci ditabella da 8 byte, tabelle interne lunghe 4 pagine, la tabellaesterna dovrebbe avere 264−13−12 = 239 voci (4 TiB)

La soluzione più diffusa consiste nell’aumentare il numero dilivelli di tabelle di paginazione

Con tre livelli, indirizzi logici da 64 bit, pagine da 8192 byte,voci di tabella da 8 byte, tabelle interne lunghe 1 pagina, latabella esterna ha 264−13−20 = 231 voci (16 GiB)

Con quattro livelli, indirizzi logici da 64 bit, pagine da 8192byte, voci di tabella da 8 byte, tabelle interne lunghe 4 pagine,la tabella esterna ha 264−13−36 = 215 voci (256 KiB)


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.24

Esempio di paginazione a quattro livelli

Source: Bovet, Cesati, Understanding the Linux kernel, 3rd ed., 2005, OReilly


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.25

Translation Lookaside Buffer

Svantaggio principale della paginazione gerarchica: per ogniaccesso ad una cella di memoria richiesto dal processo sononecessari diversi accessi in RAM

Ad esempio con una paginazione a tre livelli: per ciascunaccesso in RAM si deve accedere a tre voci in tabelle dipaginazione per ricavare l’indirizzo fisico

Translation Lookaside Buffer (TLB)

Meccanismo hardware o (parzialmente) software chememorizza in memoria statica veloce gli indirizzi fisicicorrispondenti agli ultimi o più frequenti indirizzi logiciutilizzati dalla CPU

Nelle architetture moderne questo meccanismo èestremamente importante per ottenere prestazioni significative

I processori più recenti hanno TLB organizzate con più livelligerarchici, come le memorie cache


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.26

Tabella di paginazione inversa

Nei sistemi in cui lo spazio di indirizzamento logico è molto piùgrande dello spazio di indirizzamento fisico diventaconveniente utilizzare le tabelle di paginazione inverse

Una tabella di paginazione inversa

è in comune per tutto il sistemacontiene per ciascun indirizzo fisico (page frame)l’indirizzo logico corrispondente

Ad esempio, in un sistema con 64 GiB di RAM e pagine da8192 byte è sufficiente una tabella di paginazione inversaavente 236−13 = 223 voci

Quali problemi debbono essere risolti con questo approccio?

Lo stesso indirizzo logico è utilizzato da più processiSi aggiunge il PID agli indirizzi logici memorizzati

La risoluzione di un indirizzo logico comporta la scansionedell’intera tabella

La tabella inversa è implementata come una struttura“hash”: PID e VPN sono applicati ad una funzione che dàl’indice della voce su cui è attestata la lista di collisione


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.27

Segmentazione in Intel IA-32

L’architettura Intel IA-32 usa sia la segmentazione che lapaginazione

CPU Segmentation unit

Paging unit RAM

ind. logico

ind. lineare

ind. fisicog

I segmenti sono contenuti in tabelle di descrittori disegmento globali (GDT) o locali per processo (LDT)

Ogni processo può accedere a sei segmenticontemporaneamente tramite sei registri speciali checontengono indici entro le tabelle GDT o LDT


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.28

Segmentazione in Linux su Intel IA-32

Per essere il più possibile portabile su differenti architetture, ilkernel Linux sfrutta essenzialmente soltanto il meccanismodella paginazione

Sono definiti sei segmenti “universali”:

segmento di codice per KM, indirizzi lineari tra0xc0000000 e 0xffffffffsegmento di dati per KM, indirizzi lineari tra 0xc0000000e 0xffffffffsegmento di codice per UM, indirizzi lineari tra 0 e0xbfffffffsegmento di dati per UM, indirizzi lineari tra 0 e0xbfffffffsegmento per lo stato del processo (Task State Segment,TSS, richiesto dall’hardware)segmento per la tabella locale dei descrittori LDT

I segmenti codice e dati si sovrappongono, quindi gli indirizzilogici di codice e dati producono indirizzi lineari nello stessospazio


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.29

Paginazione in Intel IA-32

Ciascun processo nell’architettura Intel IA-32 può utilizzareindirizzi fisici a 32 bit oppure a 36 bit

Con indirizzi fisici a 32 bit:

Le pagine hanno una dimensione prefissata di 4 KiB (duelivelli di paginazione) oppure di 4 MiB (un solo livello)

Con due livelli di paginazione le tabelle interne ed esternehanno 1024 voci

Con indirizzi fisici a 36 bit (PAE, Physical Address Extension):

Le pagine hanno dimensione prefissa di 4 KiB (tre livelli dipaginazione) oppure di 2 MiB (due livelli)

Con tre livelli di paginazione le tabelle di paginazioneincludono 4 (esterna), 512 e 512 voci

L’indirizzo della tabella di paginazione esterna è memorizzatonel registro speciale cr3


Marco Cesati


Memoria centrale

Segmentazione

Paginazione


SO’17 7.30

Paginazione in Linux su IA-32

Linux adotta uno schema di paginazione a quattro livelli

Lo schema generale viene adattato alle caratteristichehardware dell’architettura

In IA-32 senza PAE (indirizzi fisici da 32 bit), le quattrotabelle di paginazione si riducono a due

In pratica si considerano le tabelle eliminate comecomposte da una singola voce corrispondente a zero bitdell’indirizzo logico

In IA-32 con PAE (indirizzi fisici da 36 bit), le quattrotabelle si riducono a trePer ogni cambio di contesto, il contenuto del registro cr3viene salvato nel TSS del processo uscente, poi vieneripristinato il valore letto dal TSS del processo entranteLe tabelle di paginazione dei processi differisconoessenzialmente soltanto per le voci corrispondenti agliindirizzi logici inferiori a 3 GiB

Tutti i processi condividono gli spazi di indirizzamento logicoe fisico quando eseguono in Kernel Mode

Gestione della memoria centrale - so.sprg.uniroma2.itso.sprg.uniroma2.it/lucidi/lez-07-p1.pdf ·...

Documents

Transcript of Gestione della memoria centrale - so.sprg.uniroma2.itso.sprg.uniroma2.it/lucidi/lez-07-p1.pdf ·...