Lezione T15 - weblab.ing.unimore.it · Il valore risultante è il quantitativo di memoria in KB...

1

Lezione T15Gestione memoria processiSistemi Operativi (9 CFU), CdL Informatica, A. A. 2013/2014Dipartimento di Scienze Fisiche, Informatiche e MatematicheUniversità di Modena e Reggio Emiliahttp://weblab.ing.unimo.it/people/andreolini/didattica/sistemi-operativi

http://weblab.ing.unimo.it/people/andreolini/didattica/sistemi-operativi

2

Quote of the day(Meditate, gente, meditate ...)

“The name was borrowed from optics, recalls the virtual images formed in mirror and lenses – images that are not there but behave as if they are.”Peter J. Denning (1942-)Informatico teoricoCoautore di MULTICSCoinventore del demand pagingInventore del concetto di “working set”

3

INTRODUZIONE

4

Riassunto delle puntate precedenti(Per schiarirsi un po' le idee)

I meccanismi di gestione della memoria risultati finora vincenti sono i seguenti.

Modello di memoria flat (no segmentazione).Spazio di indirizzamento di un processo partizionatodinamicamente.Allocazione dinamica della memoria ai processi.Separazione degli spazi degli indirizzi kernel e user.Paginazione della memoria.Associazione ritardata delle pagine ai frame fisici.

Su questi meccanismi si vuole implementare un gestore della memoria per i processi utente.

5

Problema: allocazione completa(Enormemente inefficiente)

Sembrerebbe naturale:caricare completamente in memoria centrale unprogramma appena lanciato.fornire subito tutta la memoria richiesta.

Così facendo, però, la memoria principale si esaurisce molto presto.Se la memoria principale finisce, le applicazioni non possono partire.

→ Il grado di multiprogrammazione diminuisce.

6

Un esempio: LibreOffice(Il classico “mastodonte”)

Si consideri, ad esempio, il caricamento completo di una applicazione grande come LibreOffice.Si trasferisce in memoria centrale un quantitativo di dati impressionante.

Per avere un'idea: pmap $(pgrep soffice.bin)e si sommino i valori della seconda colonna.In alternativa: eseguire lo script di shell (in allegato)lo-memsize.sh.Il valore risultante è il quantitativo di memoria in KBrichiesto per caricare completamente in memoriaLibreOffice.

7

Una domanda esistenziale(Ma serve veramente tutta quella roba?)

Serve veramente tutto e subito quel quantitativo di dati?

Tutto il codice di Libreoffice è eseguito subito?Tutti i font sono usati subito?Tutte le funzioni dei menu sono invocate subito?

O è stata fatta una gran fatica (e consumata tanta memoria) per niente?

8

Un altro esempio: allocazioni grandi(Programmi di calcolo, macchine virtuali, videogiochi)

Sempre più spesso le applicazioni prenotano la memoria in blocchi grandi.

Ad esempio, per una macchina virtuale, 2GB.Domande.

Tutta quella memoria è usata subito o a breve?Che fare se l'allocazione eccede la memoriafisica a disposizione? Si ammazza il processo? Lo siblocca?

9

Una riflessione: il caricamento pigro(Si carica solo ciò che serve per l'esecuzione)

IDEA: invece di allocare tutto e subito, il kernelassocia aree di indirizzi lineari alle diverse componentidi una applicazione (codice programma, datiprogramma, codice librerie, dati librerie, stack).associa i file relativi su disco a tali aree, se necessario(codice soffice.bin, libreria libc.so.6, …).→ →Carica in memoria “solo il pezzo che serve” (traccia dicodice o libreria, dato, …).

→Caricamento pigro (lazy). Si caricano in memoria centrale solo le pagine riferite dalla CPU.

10

È possibile implementarlo?(In maniera efficiente, ovviamente?)

Come si può implementare in maniera efficiente il caricamento pigro?Si usano i meccanismi hardware (Intel) descritti nella lezione precedente.

Bit delle PTE: contengono lo stato di validità dellepagine.Page fault: rende valide le associazioni pagina ↔frame.

11

Ma funziona veramente?(Funziona, funziona!)

Aumenta il grado di multiprogrammazione.Si carica solo ciò che serve di un programma. Lamemoria centrale può contenere molte più tracce.

Aumenta l'efficienza del caricamento.Si carica solo ciò che permette al programma diiniziare l'esecuzione.

Si possono effettuare allocazioni grandi.Il kernel assegna aree di indirizzi lineari. Solo in casodi effettivo utilizzo le pagine delle aree sono associatea frame liberi.

12

MEMORIA VIRTUALE

13

Memoria virtuale(Una estensione del concetto di paginazione)

Il meccanismo di memoria virtuale è una estensione della tecnica di paginazione.L'idea di base è quella di legare una pagina:

ad un frame fisico (paginazione base).oppure ad un blocco di un file (novità).oppure ad un blocco del disco (novità).

In tal modo:alcune porzioni della memoria di un processo sonocaricate in memoria, mentre altre no.alcune porzioni della memoria di un processopossono essere inserite in swap, mentre altre no.

14

Schema di memoria virtuale(Un diagramma vale più di 1000 parole)

pagina 0

pagina 1

pagina 2

...

pagina n

Memoriavirtuale

Mappa dimemoria

Memoriafisica

Unità dimemorizzazione

secondaria

15

Spazio di indirizzamento lineare(Di un processo)

Ad ogni processo è associato uno spazio degli indirizzi (o spazio di indirizzamento) lineare.

Sequenza di indirizzi lineari adisposizione del processo.Organizzato per aree di memoriacontigue (dette segmenti), con leporzioni del processo (codice, dati,stack).Gestito in maniera pigra (solo ciòche serve effettivamente è caricatoin memoria).

Codice

Dati statici

Stack

Heap

0

Max

16

Spazio di indirizzamento – x86

Segmento di testo (ELF)Immagine binaria del codice (ad es., /bin/ls) 0x08048000 (128MB)

0x00000000

Segmento datiVariabili statiche inizializzate dal programmatore.

Esempio: static char *var = “value”;

Segmento BSSVariabili statiche non inizializzate, riempite di zeri.

Esempio: static char *username;

end_codestart_data

end_data

Random brk offset (LASR)

Heap start_brkbrkprogram break

Segmento mappe di memoriaMappature su file: ad es. /lib/libc.so

Mappature anonime

Random mmap offset (LASR)Stack

Random stack offset (LASR)

Kernel0xc0000000 (3GB)

Delle mappe dimemoria se neparla più avantiin questa lezione

I “segmenti” non sonoquelli Intel! Nel gergodel kernel, il segmentoè un'area di memorialineare contigua.

0xffffffff (4GB)LASR: Linear AddressSpace Randomization(per rendere i bufferoverflow più difficili)

mmap_base

17

Il descrittore di memoria in Linux(Rappresenta lo spazio di indirizzamento)

Il campo mm della task_struct di ciascun processo utente contiene un puntatore al descrittore di memoria che rappresenta lo spazio di indirizzamento di un processo.Esso è definito mediante la seguente struttura:

struct mm_struct.File $LINUX/include/mm_types.h.

18

Alcuni campi importanti di mm_struct(Puntatori agli indirizzi lineari delle aree; si confronti slide 15)

start_stack: indirizzo iniziale dello stack.mmap_base: indirizzo iniziale dell'area mmap.start_brk, brk: inizio e fine dell'heap.start_data, end_data: inizio e fine del segmento dati.start_code, end_code: inizio e fine del segmento testo.

task_struct(/bin/ls)

Descrittore diprocesso

mm_struct

Descrittore dimemoria

mm

Stack

Segmento mappe di memoria

Heap

Segmento BSS

Segmento dati

Segmento di testo

start_stack

mmap_base

brkstart_brk

end_data

start_data

end_code

start_code

19

Rappresentazione aree di memoria(Ciascuna è descritta da una struttura dati)

I campi ora visti sono semplicemente indirizzi lineari iniziali “notevoli”.In Linux, ognuna delle aree viste (codice, dati, stack, mappa) è rappresentata da una opportuna struttura dati:

struct vm_area_struct.File $LINUX/include/linux/mm_types.h.

Le aree di un processo in esecuzione sono visibili con il comando pmap PID.

20

Indirizzi iniziali e finali dell'area(Memorizzati in due campi opportuni di vm_area_struct)

Gli indirizzi iniziali e finali dell'area di memoria sono memorizzati in due campi della struttura vm_area_struct.

vm_start: indirizzo iniziale dell'area.vm_end: indirizzo successivo a quello finale dell'area.

21

Mappatura di memoria(Di file o di frame fisici; gestita in maniera pigra)

Le aree di memoria sono gestite in maniera pigra tramite una mappatura di memoria (memory map).Le singole pagine dell'area puntano:

ad un blocco di disco (4KB).ad un frame fisico (4KB).ad un blocco di una partizione di swap (4KB).a nulla (non sono state ancora mappate).

L'associazione avviene nel momento in cui la CPU genera un indirizzo lineare nella pagina e vi accede.

22

Legame area memoria file su disco↔(La vm_area_struct ha un campo puntatore alla struct file)

Se l'area di memoria lineare è associata al contenuto di un file su disco, l'area si dice supportata da file (file-backed).Il campo vm_file di vm_area_struct è un puntatore alla struct file rappresentante il file mappato.

23

Trasporto dei blocchi in memoria(Struct vm_operations_struct)

Le operazioni di mappatura del file variano da file system a file system.Si definisce una vm_operations_struct con i puntatori alle funzioni di gestione:

creazione mappa, distruzione mappa, fault, ...Il campo vm_ops di vm_area_struct contiene un puntatore alla struttura appropriata per il file system ospitante il file da mappare.

vm_area→vm_ops→fault() è invocata del pagefault handler.

24

Legame area memoria frame fisico↔(La vm_area_struct ha un campo puntatore alla struct anon_vma)

Se l'area di memoria lineare è associata a frame fisici, l'area si dice anonima (anonymous).Il campo anon_vma di vm_area_struct è un puntatore alla struct anon_vma rappresentante il frame fisico mappato.

25

I permessi di accesso(Lettura, scrittura, esecuzione)

Ciascuna area di memoria ha permessi di accessoVM_READ: in lettura.VM_WRITE: in scrittura.VM_EXEC: in esecuzione.

File $LINUX/include/linux/mm.h.I permessi sono contenuti nel campo vm_flags della vm_area_struct e sono usati dal kernel per verificare la correttezza delle operazioni richieste dagli utenti.

26

Collegamento delle aree di memoria(Storicamente, tramite liste doppiamente collegate)

Storicamente, le vm_area_struct sono sempre state collegate con una lista doppia.

Campi vm_next, vm_prev.Problema: l'individuazione dell'area contenentel'indirizzo richiede una scansione lineare dell'interalista terribilmente inefficiente.→

Oggi tali liste sono usate durante la fase di costruzione dello spazio d indirizzamento del processo (creazione, esecuzione).

27

Collegamento delle aree di memoria(Oggi, tramite alberi rosso-neri ordinati per indirizzo lineare iniziale dell'area)

Oggi si usano alberi rosso-neri ordinati per indirizzo lineare iniziale dell'area di memoria.

Lookup logaritmico nel numero di aree di memoria!A ciascun nodo di un albero rosso-nero è associata una struct rb_node che permette di risalire al nodo padre ed ai nodi figli.La vm_area_struct contiene un campo, vm_rb, di tipo struct rb_node per l'inserimento nell'albero.La radice dell'albero rosso-nero è contenuta nel nodo mm_rb del descrittore di memoria del processo (mm_struct).

28

Schema del collegamento(vm_area_struct collegata all'albero rosso-nero)

structrb_node

structrb_node

structrb_node

structrb_node

structrb_node

structrb_node

struct vm_area_struct {

struct rb_node vm_rb;

};

29

Schema delle aree di memoriavm_area_struct

VM_READ | VM_WRITE | VM_GROWS_DOWN

vm_area_structVM_READ | VM_EXEC


vm_area_structVM_READ | VM_WRITE



mm_structtask_struct/bin/ls

struct file/bin/ls

struct file/lib/ld.so

struct file/lib/libc.so

Stack(anonimo)

Memory map(supportato

da file)

Heap(anonimo)

BSS(anonimo)

Dati(supportato

da file)


Testo(supportato

da file)

vm_start

vm_end

vm_file

vm_filevm_next

vm_next

vm_next

vm_next

vm_next

vm_next

vm_file

vm_file

mmmmap

30

Individuazione dell'area di memoria(A partire da un indirizzo lineare)

È spesso necessario individuare l'area di memoria che contiene (presumibilmente) un indirizzo lineare.

Esempio classico: controlli di accesso.La funzione find_vma() scandisce l'albero rosso-nero puntato da mm_rb e ritorna la vm_area_struct più vicina o che contiene l'indirizzo lineare.

File $LINUX/mm/mmap.c.

31

Individuazione di un'area libera(Per creare nuove aree di memoria)

Un altro compito importante consiste nell'individuare un'area di memoria libera.

Esempi classici: esecuzione immagine, creazionemanuale di mappe anonime.

La funzione get_unmapped_area() scandisce l'albero rosso-nero puntato da mm_rb e ritorna un'area di memoria libera nell'area degli indirizzi noti per il codice, i dati, le mappe o lo stack.

File $LINUX/mm/mmap.c.

32

Creazione di un'area di memoria(Dal kernel, per scopi interni o su comando del sistema)

La funzione insert_memory_region() crea una nuova area di memoria e la inserisce sia nella lista collegata, sia nell'albero rosso-nero delle aree.

File $LINUX/mm/mmap.c.Solitamente è il kernel a creare aree di memoria. Anche l'utente può crearne con la chiamata di sistema mmap().

33

Distruzione di un'area di memoria(Dal kernel, per scopi interni o su comando del sistema)

La funzione do_munmap() distrugge un'area di memoria ed aggiorna la lista collegata e l'albero rosso-nero delle aree.

File $LINUX/mm/mmap.c.Solitamente è il kernel a distruggere aree di memoria. Anche l'utente può distruggere un'area che ha creato esplicitamente con la chiamata di sistema munmap().

34

Spostamento di un'area di memoria(Se cresce troppo, può andare a sbattere contro un'altra)

Un problema importante da risolvere è la sovrapposizione di due aree di memoria in seguito alla crescita di una delle due.Per evitarla, si può spostare un'area di memoria in un altro intervallo di indirizzi lineari.Tale funzionalità permette anche banalmente di estendere un'area (si sposta un solo estremo).La chiamata di sistema mremap() effettua lo spostamento.

File $LINUX/mm/mremap.c

35

Memory locking di un'area(L'area non viene più spostata su swap)Si può decidere di non far mai inserire nell'area di

swap un'area di memoria. → Gli accessi avvengono sempre da memoria

centrale (veloci).Attenzione: usare con cautela! Si rimuove memoria centrale altrimenti disponibile.La chiamata di sistema mlock() inchioda l'area in memoria impostando il flag VM_LOCKED.La chiamata di sistema munlock() toglie il lock.

File $LINUX/mm/mlock.c

36

PAGINAZIONE SU RICHIESTA

37

Definizione(Demand paging)

Il meccanismo di paginazione su richiesta (demand paging) fa uso della rappresentazione delle aree di memoria per gestire in maniera pigra lo spazio di indirizzamento di un processo.Sforzo congiunto di:

hardware (page fault, bit di accesso).kernel (gestione delle aree di memoria).librerie di sistema (caricamento del programma,creazione di aree di memoria).

38

Uno schema con gli attori principali(Chi collabora al demand paging?)

A0

B1

C2

D3

E4

F5

G6

H7

Spazio diindirizzamento

lineare4 v

Tabelladelle pagine

i6 v

ii

9 vii

01234567


fisico

C

F89

10


secondaria

A B

C DC D

E F

39

Scenario d'uso(Una demo vale più di 1000 parole)


lineare processo

load M

Spazio diindirizzamentolineare kernel

CodiceCodice

Tabella dellepagine

i


fisico

Frame libero


secondaria

40



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Frame libero


secondariaDall'indirizzo M viene estratto il riferimento alla tabella delle pagine.

41



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Frame libero


secondariaIl riferimento è invalido.Viene invocato il gestoredel page fault.

42



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Frame libero


secondariaSe l'indirizzo è illegale per il processo, lo si termina con il segnale 11 (segmentation fault).

X

43



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Frame libero


secondaria

Se l'indirizzo è mappato su un blocco del disco, si individuano la posizione del blocco ed un frame fisico libero in memoria.

A

44



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Frame libero


secondariaIl blocco del disco viene trasferito nel frame libero.

A

45



lineare processo

load M


CodiceCodice

Tabella dellepagine

v


fisico

Blocco disco


secondariaDopo il trasferimento si aggiorna il bit di validità nell'elemento della tabella delle pagine.

A

46



lineare processo

load M


CodiceCodice

Tabella dellepagine

v


fisico

Blocco disco


secondariaIl processore esegue di nuovo l'istruzione. Questa volta l'indirizzo contiene il dato richiesto.

A

47

Tempo di accesso effettivo(Media ponderata di due componenti)

Il tempo di accesso effettivo alla pagina Teff è la media ponderata dei tempi di due eventi disgiunti.

Tma: tempo di accesso in memoria senza page fault.Tge: tempo di accesso in memoria con page fault.

La media è ponderata sulla probabilità p ∈ [0, 1] di avere un page fault. Si ha:

Teff=(1-p)Tma+pTge=Tma+(Tge-Tma)p

48

Un esempio(Tanto per capire la pesantezza del page fault)

Siano dati i seguenti parametri:Tma=200ns, Tge=8ms, p=0.001.

Quanto vale Teff?Teff= Tma+(Tge-Tma)p

= 200ns+(8000000ns-200ns)*0.001= 200ns+7999800ns*0.001= 200ns+7999.800ns= 8.199800ns≃ 8.2μs

Peggiore di Teff/Tma

≃8200ns/200ns=41 volte!

49

Un altro esempio(Quanto deve valere p per peggiorare l'accesso del 10%?)

Siano dati i seguenti parametri:Tma=200ns, Tge=8ms.

Quanto deve valere al più p per avere Teff degradato di al più il 10% rispetto a Tma?[Teff(p)-Tma]/Tma≤ 0.1→ [200ns+7999800ns*p – 200ns]/200ns≤0.1

→ 200ns+7999800ns*p – 200ns≤20ns → 7999800ns*p ≤20ns → p≤20ns/7998000ns=0.0000025

Errore relativofra Teff e Tma

Si deve verificareal più un page faultogni 1/0.0000025=399990 accessi.

50

OTTIMIZZAZIONI

51

Problema: ripetizione di alcune aree(Tipicamente, il codice delle librerie)

Alcune aree di memoria sono presenti identiche in ogni processo.

Classico esempio: aree di testo delle librerie.Ogni processo che parte dovrebbe, in linea di principio, avere una copia di queste aree.

→ Enorme consumo di spazio.Un esempio (esagerato).

la macchina ha 200 processi attivi.ognuno vuole tutti i 1.7MB di testo della libreria del C.

→ Consumo complessivo: 200*1.7MB=340MB.

52

Soluzione: condivisione delle pagine(I processi hanno aree di memoria distinte che puntano agli stessi frame fisici)

Il kernel implementa un meccanismo di condivisione delle pagine fra più processi.Ad esempio, per tutti i processi dotati di un'area per il testo della libreria del C:

il kernel crea un'area di memoria.il kernel fa condividere gli stessi frame fisici caricati inmemoria la prima volta.

Il risparmio di memoria è enorme.N utenti della libreria, una sola istanza in memoria.

La condivisione funziona in sola lettura.Che succede se un processo modifica l'area?

53

Schema di condivisione(Più processi usano la stessa memoria fisica)

Stack

Testo/lib/libc.so

Heap

Dati statici

Codice

ProcessoP1

Stack

Testo/lib/libc.so

Heap

Dati statici

Codice

ProcessoP2

Frame testo/lib/libc.so



Memoriafisica

54

Problema: scrittura su aree condivise(Non si vuole propagare la modifica a tutti i processi!)

Cosa succede se, nello schema precedente, un processo modifica il contenuto della memoria?È di vitale importanza impedire che la modifica si propaghi a tutti i processi!Altrimenti, un processo potrebbe facilmente distruggere lo spazio di indirizzamento di un altro.

55

Problema: esecuzione di un programma(Distrugge la mappatura creata da fork())

Cosa succede se, dopo una fork(), il processo figlio esegue un programma diverso con la chiamata di sistema execve()?Le mappe di memoria create da fork() (codice, dati, stack) sarebbero da rifare integralmente da zero!Si può migliorare questa inefficienza?

56

Soluzione: condivisione delle pagine(I processi hanno aree di memoria distinte che puntano agli stessi frame fisici)

Il kernel implementa un meccanismo di condivisione delle pagine fra più processi.Ad esempio, per tutti i processi dotati di un'area per il testo della libreria del C:

alloca un nuovo frame fisico.copia nel nuovo frame fisico il contenuto del framecondiviso.associa la pagina al nuovo frame fisico.

Il COW risolve l'inefficienza fork()/exec()e isola la memoria dei processi.

57

Schema di COW(Prima della modifica da parte di P1)

ProcessoP1

ProcessoP2

Memoriafisica

A

B

C

58

Schema di COW(Dopo la modifica da parte di P1)

ProcessoP1

ProcessoP2

Memoriafisica

A

B

C

Copia C

59

ALLOCAZIONE DELLA MEMORIA

60

Allocazione dinamica della memoria(La vedremo meglio nell'esercitazione)

Gli strumenti di allocazione dinamica della memoria in GNU/Linux sono i seguenti.

Modifica dell'heap: brk().Creazione mappe di memoria: mmap(), munmap().Allocazione generale: malloc(), free().

61

Modifica dell'heap(Si alza e si abbassa l'asticella dell'heap, detta program break)

In Linux, due chiamate di sistema permettono di modificare il valore del program break, ossia il primo indirizzo lineare dopo l'heap.

brk(): impostazione di un indirizzo lineare assoluto.sbrk(): incremento e decremento del programbreak.

62

Creazione di mappe di memoria(Associate ad un file oppure anonime)

In Linux, due chiamate di sistema permettono di creare e distruggere mappe di memoria.

mmap(): creazione di una mappa.munmap(): distruzione della mappa.

Le mappe possono essere:associate a file o no.private ad un processo o condivise fra processi.su tutto un file o su una singola parte.

Attenzione: le mappe sono veramente condivise, nel senso che le modifiche di un processo sono viste da un altro.

63

Allocazione dinamica della memoria(By Doug Lea)

Un algoritmo di allocazione dinamica molto popolare è dlmalloc.

Creato nel 1987 da Doug Lea.Implementato (con alcune modifiche) nella GNU CLibrary.

L'algoritmo usa due meccanismi di allocazione diversi a seconda della dimensione richiesta.

Dimensione “piccola” (≤ 32 pagine): si espande l'heap.Dimensione “grande” (> 32 pagine): si crea unamappatura anonima.

→ Dettagli maggiori nell'esercitazione.

64

Motivazione(Uso dell'heap per allocazioni piccole)

Se l'allocazione è ragionevolmente piccola, basta “alzare l'asticella” dell'heap.

Lo spazio di indirizzamento logico cresce di poco (sirichiedono pochi frame fisici).

Quando viene liberata la memoria, il SO non la distrugge, bensì la mette a disposizione per future allocazioni.

Il SO non tocca i relativi elementi nella tabella dellepagine.

I frame fisici sono rilasciati “abbassando l'asticella”.

65

Una conseguenza importante(free() non fa nulla)

La free() non fa praticamente nulla. → Vantaggio prestazionale rispetto al caso più

generale di aggiornamento della tabella delle pagine.Perché non si usa sempre brk()?

Non si può alzare l'asticella indefinitamente; siandrebbe a sbattere contro le mappe di memoria!I frame fisici non sono restituiti al SO; si perdememoria fisica.

66

Motivazione(Uso di mmap() per allocazioni grandi)

Se l'allocazione è grande, è mandatorio creare una mappatura anonima con mmap().

→ Tale area di memoria può essere piazzata ovunque nello spazio di indirizzamento, fra stack e heap.

→ Non vi sono le sovrapposizioni viste in precedenza con l'heap.La memory_free() invoca la memory_unmap() per distruggere la associazione indirizzi logici-frame fisici.

Lezione T15 - weblab.ing.unimore.it · Il valore risultante è il quantitativo di memoria in KB...

Documents

Transcript of Lezione T15 - weblab.ing.unimore.it · Il valore risultante è il quantitativo di memoria in KB...