Lezione 16 Memoria - weblab.ing.unimore.it file1 Lezione 16 Memoria Sistemi Operativi (9 CFU), CdL...

1

Lezione 16MemoriaSistemi Operativi (9 CFU), CdL Informatica, A. A. 2014/2015Dipartimento 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...)

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships. ”Linus Torvalds (1969-)ProgrammatoreAutore di Subsurface

3

INTRODUZIONE

4

Problema: separazione dei processi(Necessaria, altrimenti è possibile manomettere altre applicazioni)

Per poter eseguire, i processi hanno bisogno di memoria.La memoria assegnata ad un processo non deve poter essere accessibile ad altri (a meno che non lo si voglia esplicitamente).

Altrimenti, un'applicazione maliziosa potrebbecancellare (o, peggio, alterare) la sua memoria.

→ Serve un meccanismo per isolare la memoria di processi diversi.

5

Problema: rappresentazione memoria(Preferibilmente contigua, altrimenti le strutture dati del kernel esplodono)

Il kernel deve annotarsi la memoria allocata ai processi.Se la memoria è allocata in tanti blocchi distanti fra loro, è più oneroso per il kernel tenerne traccia.

Liste con tantissimi elementi (lookup molto lento).È preferibile usare pochi blocchi contigui.

Ciò diventa sempre più difficile all'aumentare deiprocessi.

→ Serve un meccanismo per garantire blocchi contigui di memoria in presenza di più processi.

6

Problema: separazione dei processi(Necessaria, altrimenti è possibile manomettere altre applicazioni)

Per poter eseguire, i processi hanno bisogno di memoria.La memoria assegnata ad un processo non deve poter essere accessibile ad altri (a meno che non lo si voglia esplicitamente).

Altrimenti, un'applicazione maliziosa potrebbecancellare (o, peggio, alterare) la sua memoria.

→ Serve un meccanismo per isolare la memoria di processi diversi.

7

Problema: caricamento applicazioni(Il caricamento dell'intera applicazione è inefficiente)

Per poter eseguire, i processi hanno bisogno di essere caricati in memoria.Una strategia naive è quella di caricare l'intera applicazione in memoria prima di avviarla.

Alcune applicazioni (Firefox, Libreoffice) sono enormi.Alcune applicazioni (emacs) sono usate al10%-20% del loro potenziale. Si finisce per caricarecodice che non sarà mai eseguito.

→ Serve un meccanismo per poter caricare solo ciò che serve (codice, dati) di una applicazione.

8

Problema: caching(Il caricamento dei dati da disco è lento ed inefficiente; va minimizzato)

Le unità di memorizzazione di massa possono essere molto lente.Il caricamento dei dati da tali unità deve essere fatto solo se necessario.

L'eventuale rilettura di un dato già letto va evitatacome la peste.Il processo lento di scrittura non va avviato per ognisingolo byte.

→ Servono meccanismi di caching e buffering per limitare le interazioni con dischi lenti.

9

Le idee vincenti 1/2(Facili a dirsi, difficili a farsi)

Dare ad ogni processo l'illusione di essere l'unico in memoria centrale.

→ Spariscono di colpo tutte le preoccupazioni legatealla sovrapposizione di partizioni.

Partizionare in blocchi piccoli le unità di memoria assegnabili ai processi.

→ Si riduce di molto la frammentazione esterna.

10

Le idee vincenti 2/2(Facili a dirsi, difficili a farsi)

Usare più schemi di indirizzi di memoria.Schema virtuale: usato dal processore per:

creare zone di memoria contigue sparisce la→frammentazione esterna.associare l'indirizzo di memoria a RAM o disco

implementazione efficiente dello swap.→Schema fisico: usato per accedere al chip RAM.È necessario mappare lo schema virtuale nello schema fisico in maniera efficiente.

11

Supporto hardware nelle CPU Intel(Implementa le idee summenzionate)

Segmentazione (dall'8086).Suddivisione della memoria di un processo in aree peril codice, i dati, lo stack. Ciascun blocco ha il proprio intervallo di indirizzi e permessi di accesso.

Paginazione (dall'80386).Visione della memoria di un processo per blocchettidi dimensione piccola (4KB). Ciascun blocco ha ilproprio intervallo di indirizzi e permessi di accesso.

→ Su questi due supporti per schemi di inidirizzi si fonda il sottosistema di memoria virtuale dei moderni SO.

12

Schemi degli indirizzi(Logici, lineari, fisici)

Indirizzo logico: generato dalla CPU, dato in pasto all'unità di segmentazione.Indirizzo lineare: prodotto dell'unità di segmentazione, viene dato in pasto alla unità di paginazione.Indirizzo fisico: prodotto dell'unità di paginazione, viene usato per accedere al dato.

jmp 0058:FFEC

Unità disegmentazione

0058:FFEC 0x9121C Unità dipaginazione

0x4000021C

CPU

NorthBridge

RAM

logico lineare fisico

13

GESTIONE MEMORIA KERNEL

14

Buddy system(Un allocatore a potenze di due)

Il kernel gestisce la memoria fisica libera mediante un allocatore a potenze di due.

Nei processori più recenti, tale area di memoria ègestita da più allocatori, ciascuno per ogni CPU.Per semplicità, si propone la versione su singola CPU.

In un allocatore a potenze di due, le richieste di memoria sono soddisfatte, per l'appunto, a potenze di due.

4KB, 8KB, 16KB, 32KB, …Richiesta di 11KB: soddisfatta con un blocco di 16KB.

15

Rappresentazione ad albero(I nodi sono aree di memoria libera e fisicamente contigua)

I frame fisici sono organizzati in un albero. Ciascun nodo è un blocco di memoria fisica contigua.Si supponga di dover servire una richiesta di 21KB. Come opera l'allocatore?

256KB

128KB 128KB

64KB 64KB

32KB 32KB

16

Un esempio di uso(Costruzione ricorsiva dell'albero)

Inizialmente è presente un solo nodo (di 256KB per semplicità).Viene ricevuta la richiesta di 21KB.

256KB

17


L'allocatore considera l'unico blocco foglia da 256KB.La dimensione del blocco libero è maggiore del doppio di 21KB.L'allocatore spacca a metà il blocco, creando due blocchi da 128KB.I due blocchi da 128KB si chiamano compari (buddy).

256KB

128KB 128KB

18


L'allocatore considera il primo blocco foglia da 128KB.La dimensione del blocco libero è maggiore del doppio di 21KB.L'allocatore spacca a metà il blocco, creando due blocchi da 64KB.

256KB

128KB 128KB

64KB 64KB

19


L'allocatore considera il primo blocco foglia da 64KB.La dimensione del blocco libero è maggiore del doppio di 21KB.L'allocatore spacca a metà il blocco, creando due blocchi da 32KB.

256KB

128KB 128KB

64KB 64KB

32KB 32KB

20

Un esempio di uso(Assegnazione di un blocco)

L'allocatore considera il primo blocco foglia da 32KB.La dimensione del blocco libero è:

maggiore di 21KB.minore di 42KB.

→ Non si può spezzare ulteriormente. Si associa un blocco da 32KB.

256KB

128KB 128KB

64KB 64KB

32KB 32KB

21

Un esempio di uso(Fusione di blocchi liberi adiacenti)

Quando il blocco è restituito l'allocatore prova a fondere il blocco liberato con il suo vicino (coalescing).

256KB

128KB 128KB

64KB 64KB

32KB 32KB

Coalescing

22

Un esempio di uso(Fusione di blocchi liberi adiacenti)

Se ci riesce (ossia, se il compare è libero) l'allocatore prova a fondere compari contigui sempre più grandi.

256KB

128KB 128KB

64KB 64KB

Coalescing

23

Cenni implementativi(Buddy system in Linux)

In Linux, l'albero è implementato tramite la struttura dati seguente:

struct free_area.$LINUX/include/mm.h.

L'elemento i contiene blocchi di 2i frame fisici (detti di ordine i).

012345689

order free_area

1011

24

Allocazione e rilascio di frame fisici(Tramite funzioni molto semplici)

L'allocazione ed il rilascio di frame fisici avviene tramite le funzioni già viste (e parte integrante dell'allocatore buddy):

alloc_pages().free_pages().

25

Organizzazione dell'allocatore(Per “lastre” di “oggetti”; si allarga e si accorcia come una fisarmonica)

Uno SLAB è un insieme di pagine logiche associate a frame fisici contigui.Uno o più SLAB contigui formano una cache.Ciascuna cache è un contenitore di oggetti.Un oggetto è un'area di memoria di una specifica dimensione.

Struttura dati, buffer.Una cache contiene solo oggetti di un dato tipo.Implementazione: in due file.

$LINUX/mm/slab.c, $LINUX/mm/slab-common.c.

26

Architettura dello SLAB(Un'immagine vale più di 1000 parole)

Oggetti Cache SLAB

Oggettida 3KB

Oggettida 7KB

Uno SLAB(gruppo dipaginecontiguefisicamente)Padding

27

Stati di uno SLAB(Pieno, vuoto, parzialmente vuoto)

Pieno.Tutti i suoi oggetti sono marcati in uso.

Vuoto.Tutti i suoi oggetti sono marcati liberi.

Parzialmente vuoto.I primi oggetti sono marcati in uso, i rimanentisono marcati liberi.

Tutti gli oggetti in un dato stato sono mantenuti vicini si riduce la frammentazione esterna.→

28

Creazione cache(“Formatta” lo spazio di memoria fisico)

Una cache è creata in fase di inizializzazione.Boot del kernel, caricamento di un modulo.

Operazioni svolte:Prenotazione memoria logica.Associazione con frame fisici contigui.Suddivisione di una cache in SLAB.Creazione degli oggetti liberi all'interno degli SLAB.Padding fra oggetti.

Funzione kmem_cache_create().

29

Esempio di creazione cache(Inode cache di EXT4)

Un esempio di kmem_cache_create() è preso dal codice di EXT4 per la creazione delle strutture dati relative agli inode.Si usa una cache di struct ext4_inode_info.

File $LINUX/fs/ext4/super.c.Funzione init_inodecache().

30

Recupero di un elemento dalla cache(Semplicissimo)

La funzione kmem_cache_alloc() individua un oggetto libero dalla cache e lo ritorna all'utente.Dopo l'uso, l'oggetto può essere restituito alla cache con la funzione kmem_cache_free().

31

Individuazione di un oggetto libero 1/2(L'allocatore mantiene aggiornati diversi puntatori)

L'allocatore SLAB gestisce diversi puntatori per motivi di efficienza

puntatore allo SLAB parzialmente vuoto.puntatore al primo SLAB vuoto.puntatore al primo oggetto libero all'interno di unoSLAB.

32

Individuazione di un oggetto libero 2/2(L'allocatore mantiene aggiornati diversi puntatori)

Quando il kernel richiede una struttura dati, l'allocatore cerca di fornire il primo oggetto libero all'interno dello SLAB parzialmente vuoto.Se non esistono SLAB parzialmente vuoti, si fornisce il primo oggetto libero del primo SLAB vuoto.Se non esiste uno SLAB vuoto, l'allocatore ne crea uno (cache grow) e lo appende in fondo alla cache.

33

Gestione dimensione cache(L'allocatore mantiene aggiornati diversi puntatori)

La dimensione di una cache è gestita in maniera trasparente all'utente e dinamica attraverso due funzioni.

kmem_cache_grow(): aggiunge uno SLAB ad unacache esistente.kmem_cache_shrink(): rimuove uno SLAB dauna cache esistente.

La memoria è presa/restituita dall'/all'allocatore buddy.

34

Distruzione cache(Rilascia la memoria prenotata)

La funzione kmem_cache_destroy() distrugge le strutture dati di gestione della cache e ritorna le pagine all'allocatore buddy.

35

Vantaggi dell'allocatore SLAB(Diversi)

L'allocatore SLAB non soffre del problema della frammentazione interna (la memoria viene ritornata “su misura”).Gli oggetti sono preallocati in fase di creazione degli SLAB; le funzioni di allocazione e deallocazione della memoria sono velocissime.

36

Svantaggi dell'allocatore SLAB(Uno, ma particolarmente fastidioso)

L'allocatore SLAB richiede una struttura dati ben precisa su cui costruire la cache.Che succede se un utente vuole allocare un buffer generico di n byte (n potenza di due)?

37

kmalloc(), kfree()(La soluzione al problema precedente)

Il kernel mette a disposizione un allocatore di buffer generici con sintassi molto simile a quella dell'allocatore della libreria del C.

void *malloc(size_t size): ritorna un bufferin grado di contenere l'allocazione richiesta.void free(const void *objp): distrugge ilbuffer.

Tali funzioni sono implementate tramite diverse cache di buffer a potenze di due crescenti.

38

Quante cache esistono nel sistema?(È possibile scoprirlo con alcuni semplici comandi)

Il file /proc/slabinfo contiene l'elenco delle cache attivate dal kernel, con statistiche sull'uso.Il primo campo di ogni riga è il nome della cache.

Notate le cache di nome kmalloc-8, kmalloc-16, …È da queste cache che kmalloc() pesca gli oggettiper soddisfare le allocazioni di buffer generici.

39

Memoria consumata dal kernel(Il comando free -w)

Il comando free mostra il consumo di memoria di kernel e applicazioni.In particolare, per il kernel si è interessati ai due campi seguenti.

Buffers: memoria dedicata ai buffer dati mantenutinelle cache del sistema di I/O.

Cached: memoria usata dall'allocatore SLAB.La vista di default di free presenta la somma di “buffers” e “cached”. L'opzione -w separa i due contributi.

free -w

40

Esercizi (3 min.)

1. Si usi il comando dd per far leggere tanti dati da uno dei dischi rigidi. Nel frattempo si monitori l'andamento dei campi “buffers” e “cached”. Che cosa succede?

42

Esercizi (3 min.)

2. Si interrompa il comando dd appena dato e lo si lanci nuovamente.

Come variano i campi “buffers” e “cached”?

44

Esercizi (3 min.)

3. Si usi il comando seguente da amministratore per pulire tutte le cache di sistema:

echo 3 > /proc/sys/vm/drop_cachesCome variano i campi “buffers” e “cached”?

46

MEMORIA VIRTUALE

47

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.

48

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

49

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

50

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

51

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.

52

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

53

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.

54

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.

55

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.

56

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.

57

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.

58

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.

59

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.

60

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).

61

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).

62

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;

};

63

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

64

Esercizi (3 min.)

4. Si apra il browser chromium. Si stampino le mappe di memoria create dal kernel per caricare l'applicazione.

66

PAGINAZIONE SU RICHIESTA

67

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).

68

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

69

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

70



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Frame libero


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

71



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Frame libero


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

72



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

73



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

74



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Frame libero


secondariaIl blocco del disco viene trasferito nel frame libero.

A

75



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

76



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

77

Resident Set, Virtual Memory Set(Come misurarla?)

Resident Set. È l'insieme di pagine cui è associato un frame fisico. La sua dimensione (Resident Set Size, RSS) misura il consumo effettivo di memoria fisica di un processo.Virtual Memory Set. È l'insieme delle pagine componenti lo spazio di indirizzamento di un processo. La sua dimensione (Virtual Memory Set Size, VMSS) misura la grandezza dello spazio di indirizzamento del processo.

78

Esercizi (5 min.)

5. Si apra il browser chromium. Si stampino le mappe di memoria create dal kernel per caricare l'applicazione. Si cerchi di individuare la dimensione delle seguenti aree:

spazio di indirizzamento virtuale (VSZ).porzione dello spazio virtuale caricata in memoriacentrale (RSS).

80

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.

81

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?

82

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

83

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.

84

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?

85

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.

86

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

ProcessoP1

ProcessoP2

Memoriafisica

A

B

C

87

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

ProcessoP1

ProcessoP2

Memoriafisica

A

B

C

Copia C

88

SOSTITUZIONE DELLE PAGINE

89

Overcommit della memoria(Simile all'overbooking dei biglietti aerei)

Un'ipotesi fatta da molti SO moderni è la seguente: un programma non userà mai tutta la memoria che alloca.

→ Il SO alloca tutta la memoria virtuale (lineare) possibile, anche se:

è un quantitativo osceno.non è utilizzata tutta subito.

Il SO sovrassegna la memoria (overcommit).Concetto analogo a quello di “overbooking” delle prenotazioni aeree.

90

Problema: pressione di memoria(Contrariamente all'ipotesi fatta, i processi iniziano ad usare tutta la memoria)

Cosa succede se i processi cominciano ad usare tutta la memoria prenotata?

→ I frame fisici a disposizione della macchina si esauriscono.

→ Non esistono più frame liberi a disposizione. → Il SO non riesce a fornire la memoria fisica

sovraprenotata dall'allocazione virtuale. → Diventa fondamentale liberare memoria fisica.

Che fare?

91

Possibili soluzioni(Convincono molto poco)

Uccisione del processo che ha provato ad usare la memoria sovraprenotata.

Abbassa il grado di multiprogrammazione.Si rischia di perdere interamente il lavoro svolto finoradal processo.

Swap-out dell'intero processo che ha provato ad usare la memoria sovraprenotata.

Abbassa il grado di multiprogrammazione.Rallenta di molto l'esecuzione del processo.

92

Sostituzione delle pagine(Un approccio chirurgico al problema)

La soluzione vincente è quella di effettuare una sostituzione di pagina.Si sceglie una pagina (detta vittima).Si distrugge l'associazione pagina frame della ↔vittima (ricavando un frame fisico libero).Si associa il frame fisico libero alla pagina riferita dal processo.

93



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Occupato

Occupato

Occupato

Occupato


secondaria

94



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico


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

Occupato

Occupato

Occupato

Occupato

95



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico


secondaria

Il riferimento è invalido.Viene invocato il gestoredel page fault. Si supponga di non avere alcun frame libero.

Occupato

Occupato

Occupato

Occupato

96



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico


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

XOccupato

Occupato

Occupato

Occupato

97



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Occupato

Occupato

Occupato


secondariaIl gestore del page fault prova a recuperare un frame libero. Non ne esiste uno.

Occupato

98



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico

Occupato

Occupato

Occupato


secondariaIl gestore del page fault seleziona una pagina vittima.

Vittima

99



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico


secondariaLa pagina vittima è sincronizzata su disco.

AOccupato

Occupato

Occupato

Vittima

100



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico


secondariaSi aggiorna la tabella delle pagine del processo che si è visto scippare il frame fisico.

Occupato

Occupato

Occupato

Libero

Tabella dellepagine

i

101



lineare processo

load M


CodiceCodice

Tabella dellepagine

i


fisico


secondaria

Se necessario, si aggiorna il frame fisico libero con il contenuto di un blocco dal disco (ad es., mappatura su file).

B

Occupato

Occupato

Occupato

Libero

102



lineare processo

load M


CodiceCodice

Tabella dellepagine

v


fisico


secondaria

Dopo il trasferimento si aggiorna il bit di validità nell'elemento della tabella delle pagine del processo richiedente.

Occupato

Occupato

Occupato

Occupato

103



lineare processo

load M


CodiceCodice

Tabella dellepagine

v


fisico


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

Occupato

Occupato

Occupato

Occupato

104

ALLOCAZIONE MEMORIA: HEAP

105

Allocazione mediante heap(Primitiva)

Il modo più semplice di allocare memoria in maniera dinamica consiste nell'innalzare il program break.In Linux (come in tutti i sistemi UNIX), il program break è gestibile con due chiamate di sistema:

sbrk(). brk().

106

sbrk()(Incrementa il program break e ritorna il suo valore precedente)

La chiamata di sistema sbrk() consente di incrementare e decrementare il valore attuale del program break di un offset specifico.

Si fornisce come argomento un intero (l'incremento).Viene ritornato il valore del program breakalla modifica (tutto OK) oppure -1 (errore).man sbrk per tutti i dettagli.

Esempio d'uso: sorgente sbrk.c contenuto nell'archivio 16-esempi.tar.gz.

107

brk()(Imposta il program break ad un indirizzo)

La chiamata di sistema brk() imposta il program break ad un indirizzo lineare specifico.

Si fornisce come argomento un void * all'indirizzolineare.Viene ritornato 0 (tutto OK) o -1 (errore).

Esempio d'uso: sorgente brk.c contenuto nell'archivio 16-esempi.tar.gz.

108

sbrk() vs. brk()(Un confronto fra le due chiamate di sistema)

La chiamata sbrk() è indubbiamente più versatile di brk().

→ brk() viene usata raramente nelle applicazioni.Tuttavia, brk() è usata nelle librerie di sistema come la funzione di gestione basso livello.

→ sbrk() è implementata tramite brk(). → malloc() è implementata tramite brk().

109

Esercizi (5 min.)

6. Modificare il sorgente del programma sbrk.c in modo tale da scrivere la lettera 'A' otto byte dopo il vecchio indirizzo iniziale dell'heap.

111

Esercizi (3 min.)

7. Modificare il sorgente del programma sbrk.c in modo tale da scrivere la lettera 'A' trentadue byte dopo il vecchio indirizzo iniziale dell'heap.

Qual è il risultato atteso?Che cosa succede in realtà?

112

Soluzioni

7. Si studi il sorgente del programma sbrk_write_offarea.c, contenuto nell'archivio16-soluzioni.tar.gz.

Ci si aspetterebbe un “segmentation fault”, poiché si sta scrivendo fuori area.Invece, il programma esce correttamente.

113

Esercizi (3 min.)

8. Individuare l'offset minimo a partire dal quale la scrittura di un carattere provoca il segmentation fault.

Che cosa si deduce?

115

Esercizi (5 min.)9. Modificare il sorgente del programma sbrk.c

in modo tale da:allocare 16 byte mediante modifica al program break.deallocare i 16 byte appena allocati mediantemodifica al program break.scrivere la lettera 'A' 8 byte dopo il vecchio indirizzoiniziale dell'heap.


117

Esercizi (5 min.)10. Modificare il sorgente del programma sbrk.c in modo tale da:

allocare 16 byte mediante modifica al program break.scrivere la lettera 'A' 8 byte dopo il vecchio indirizzoiniziale dell'heap.deallocare i 16 byte appena allocati mediantemodifica al program break.scrivere la lettera 'A' 8 byte dopo il vecchio indirizzoiniziale dell'heap.


119

Scoperte(Che cosa si è imparato da questi esperimenti?)

Le chiamate brk() e sbrk() provocano allocazioni per pagine.Scrivere fuori area non implica la ricezione di un segmentation fault.Una volta liberata l'area di memoria virtuale (tramite diminuzione del program break) i frame fisici sono restituiti al kernel.

→ Se si prova a scrivere su tale area, si ottiene unsegmentation fault.

120

ALLOCAZIONE MEMORIA: MALLOC

121

L'allocatore della libreria del C(Usa il program break e le mappature di memoria)

L'allocatore standard della libreria del C usa due funzioni di libreria.

malloc(): prenotazione di aree lineari di memoria.free(): restituzione di aree lineari di memoria.

Allocazioni piccole: si gestisce una lista di blocchi liberi all'interno dell'heap.Allocazioni grandi: si crea una nuova mappa di memoria anonima.La soglia fra le due allocazioni è posta a 128KB.

122

Esempio di allocazione piccola(Gestione lista blocchi liberi nell'heap)

L'esempio malloc-small.c contenuto nell'archivio 16-esempi.tar.gz mostra l'uso di malloc() per una quantità piccola di memoria (16B). Osservazioni:

dopo la malloc() il program break cresce di 132KB.l'indirizzo iniziale dell'area è 16B dopo il vecchioprogram break.dopo la free() il program break non vienemodificato.

123

Esempio di allocazione media(Gestione lista blocchi liberi nell'heap)

L'esempio malloc-average.c contenuto nell'archivio 16-esempi.tar.gz mostra l'uso di malloc() per una quantità piccola di memoria (4KB). Osservazioni:

dopo la malloc() il program break cresce di 136KB(i 128KB di espansione iniziale, più 4KB richiesti, più4KB per uso interno).l'indirizzo iniziale dell'area è 16B dopo il vecchioprogram break.dopo la free() il program break viene abbassatodi 4KB.

124

Esempio di allocazione grande(Mappatura anonima di memoria)

L'esempio malloc-big.c contenuto nell'archivio 16-esempi.tar.gz mostra l'uso di malloc() per una quantità piccola di memoria (256KB). Osservazioni:

il program break rimane inalterato.L'l'indirizzo iniziale dell'area sembra essere dentro lazona delle mappature di memoria.

125

Lista dei blocchi liberi nell'heap(Per allocazioni <128KB)

Per allocazioni <128KB, malloc() usa l'heap e mantiene una lista doppiamente collegata di aree libere.L'invocazione di malloc() provoca, come prima cosa, la ricerca di un blocco libero sufficientemente grande nella lista.Nel caso in cui sia trovato un blocco disponibile, viene ritornato quello.

126

Il blocco di controllo(Per allocazioni <128KB)

Se nella lista non è trovato alcun blocco di memoria di dimensioni sufficienti, viene allocato un nuovo blocco di memoria.Viene allocato anche un blocco di controllo contenente informazioni di stato sulla memoria appena allocata (ad esempio, la quantità).

Informazionidi controllo

Memoria ad uso dellafunzione invocante

Indirizzo ritornatoda malloc()

Blocco dicontrollo

Memoriaallocata

16 byte

127

Restituzione del blocco alla lista(Per allocazioni <128KB)

Quando la memoria è liberata tramite free() il blocco allocato è reinserito nella lista.I primi byte del blocco (ora libero) sono usati per memorizzare i collegamenti all'elemento libero successivo e precedente.

Informazionidi controllo

Bloccolibero

Blocco dicontrollo

Memorialibera

Puntatoreal blocco

liberoprecedente

Puntatoreal blocco

liberosuccessivo

Al blocco liberoprecedente

Al blocco liberosuccessivo

128

MISURAZIONE

129

Misurazione del demand paging(Quante risorse sta consumando?)

Il comando vmstat fornisce informazioni specifiche sulle prestazioni del gestore della memoria virtuale.

swpd, free, buff, cache: già visti con free.bi, bo: blocchi trasferiti da e verso il disco(attività di disco legata alla paginazione).si, so: swap-in, swap-out (paginazione dovuta alloswapping).r, b: processi in stato di esecuzione o di attesa di I/O(ingorgo dovuto a sovraccarico di CPU e/o disco).us, sy, ni, wa: consumo risorse CPU.

130

Misurazione dei page fault(Quanto è intensa l'attività di paginazione?)

Il comando sar fornisce informazioni specifiche sull'attività di page fault.

sar -B 1: misura l'attività di page fault ognisecondo.

Campi interessanti.majflt/s: numero di major fault al secondo.fault/s: numero di major+minor fault al secondo.

131

Major e minor page fault(Fault Indirizzo valido virtualmente ma pagina non presente fisicamente→

Major Carica da disco; Minor Alloca un frame)→ →Major (page) fault. L'indirizzo virtuale è valido ed è associato ad un blocco su disco non ancora caricato.

Il kernel trova un frame libero (con le buone o con lecattive) e ci carica dentro il blocco di disco associato.

Minor (page) fault. L'indirizzo virtuale è valido ed è associato ad un'area di memoria virtuale non ancora modificata.

Il kernel trova un frame libero (con le buone o con lecattive) e lo associa al blocco virtuale corrispondente.

132

Esercizi (5 min.)

11. Distruggere tutte le cache, se possibile.Eseguire il seguente comando:

lowriterIn un altro terminale, monitorare l'attività di paginazione.Quali fault si riscontrano all'inizio?

133

Soluzioni

11. Si riscontrano major fault per la lettura del programma e delle librerie condivise da disco.

134

That's all, folks!(https://www.youtube.com/watch?v=gAj8jLe_shQ)

Lezione 16 Memoria - weblab.ing.unimore.it file1 Lezione 16 Memoria Sistemi Operativi (9 CFU), CdL...

Documents

Transcript of Lezione 16 Memoria - weblab.ing.unimore.it file1 Lezione 16 Memoria Sistemi Operativi (9 CFU), CdL...