Parte 3: Gestione della memoria

(1)

Parte 3: Meccanismi di Gestione

della Memoria

• Gestione della memoria principale

– richiami su:

• binding degli indirizzi, caricamento dinamico, collegamento dinamico, overlay, indirizzi logici e fisici

– Swapping

– Allocazione contigua

– Problema della frammentazione – Paginazione

– Segmentazione – Tecniche combinate

2

Parte 3: Meccanismi di Gestione

della Memoria

• Memoria Virtuale

– Paginazione su richiesta

– Algoritmi di rimpiazzamento delle pagine – Allocazione dei frame

– Problema del Trashing

• Gestione della memoria secondaria

– File System

• Interfaccia, implementazione, file system distribuiti – Struttura della memoria secondaria

• scheduling del disco • gestione dell’area di swap

3

Gerarchia di Memorie

• Velocità implica costo maggiore, capacità minore, volatilità maggiore

P i ù v e l o c i P i ù c a p a c i

(2)

9. Gestione della Memoria

• I programmi devono essere in MP almeno parzialmente per essere eseguiti

⇒gestire la MP in modo da favorire l'utilizzo efficiente della CPU (e la comodità d’uso da parte dei programmatori e degli utenti dei programmi)

• Poiché la MP è piccola (per le esigenze) e volatile (per le esigenze)

→usare la Memoria Secondaria (MS) per allargare e rendere non volatile la MP

⇒Gestione della MS per estendere la MP ⇒Gestione della MS per memorizzare dati e/o

programmi in modo permanente

5

Gestione della Memoria Primaria

(Richiami)

• Ciclo di fetch&Execute → genera in vario modo

indirizzi di MP

• 9.1.1 Address Binding:

– condivisione della MP → i programmi che sono in MP devono dividersi lo spazio di indirizzi della MP fisica – in quale momento un programma e i suoi dati vengono

legati (binding) ai loro indirizzi?

• Preparazione di un programma utente

6

9.1.1 Preparazione di un programma

utente

(3)

• Caricamento dinamico: un modulo non viene caricato finché una delle sue procedure non viene richiamata

⇒il caricatore include la funzionalità di rilocazione

• È fatto (può essere fatto) a cura del programma stesso. Il SO fornisce memoria e librerie per il caricamento nella memoria fisica

9.1.2 Gestione della Memoria

Primaria (Richiami 2)

8

9.1.3 Gestione della Memoria

Primaria (Richiami 3)

• Linking dinamico: anche il linking è posposto a tempo di esecuzione, non solo il caricamento.

– il nucleo del programma viene staticamente linkato a uno stub

– lo stub controlla se il modulo è caricato in memoria e se non lo è ...

– localizza il modulo su MS

– linka il modulo al nucleo e lo carica in memoria – rimpiazza così se stesso nell’immagine del

programma

9

9.1.3 Gestione della Memoria

Primaria (Richiami 3)

• Permette lo sharing del codice del modulo fra processi diversi→ shared libraries • Richiede aiuto dal SO

– per lo sharing delle librerie

– per rendere efficienti gli stub nel loro lavoro – per rimpiazzare il codice degli stub

(4)

9.1.4 Gestione della Memoria

Primaria (Richiami 4)

• Overlay: per evitare che (alla fine) tutto il programma sia in MP, esso è diviso in overlay =:= parti di programma che possono occupare (in momenti diversi) gli stessi indirizzi di MP

• Gli overlay possono avere parti comuni che non vengono caricate e scaricate, e parti diverse che fanno risparmiare occupazione complessiva di memoria. La struttura può essere ripetuta

11

9.1.4 Gestione della Memoria

Primaria (Richiami 4)

• Notare il componente overlay driver • Gli overlay sono già linked e pre-caricati in

indirizzi assoluti⇒ l’overlay driver non è un loader rilocante, non alloca memoria

all’overlay, e quindi è molto efficiente • Gli overlay sono tornati di moda con i PC e i

loro semplici SO

• Non hanno bisogno di supporto da parte del SO

12

9.1.4 Gestione della Memoria

Primaria (Richiami 4)

• Ma il programma deve essere strutturato in modo opportuno (da parte dell’utente) e supportato da parte della catena di programmazione (compilatore e linker)

(5)

9.2 Spazio Indirizzi Fisico e Logico

• Logico: generato dalla CPU; detto anche virtuale • Fisico: visto dalla MP

• Il binding a tempo di esecuzione realizza una distinzione fra spazio logico/virtuale e spazio

fisico

⇒Tradurre indirizzi virtuali in indirizzi fisici: solo con opportuno dispositivo hardware: MMU o

traduttore di indirizzi. Esempio banale:

generalizzazione del registro base

14

9.2 Spazio Indirizzi Fisico e Logico

• Notare:

– I registri del traduttore sono gestiti solo dal SO – Il programma vede e usa solo indirizzi virtuali

15

9.3 Swapping

• Salvare in memoria secondaria l’immagine di un processo che non esegue (swap out) e ricaricarla (swap in) prima di dargli la CPU

(6)

9.3 Swapping

• Es: multiprogrammazione con RR

– quando il quanto di tempo scade, swap out del processo

– swap in di quello a cui dare la CPU – esecuzione del processo

• Si può fare swap in in anticipo in modo che i primi processi della RQ siano in MP pronti per eseguire

• I processi che non sono in RQ è meglio che siano in MS: detto anche roll-in e roll-out quando si usa scheduling a priorità

17

9.3 Swapping

• Dove si fa swap in?

– nello stesso posto in MP, se il binding è fatto a tempo di compilazione+caricamento

– anche in un altro posto se il binding è fatto a tempo di esecuzione

• Richiede memoria di salvataggio (backing store, BS), in genere disco veloce

• Il tempo di context switch può essere molto alto se il processo è in BS (⇒ niente hard real time!)

18

9.3 Swapping

• Es: Processo di 100K, transfer throughput 1MB/sec

→transfer time 100msec ⇒ 200msec di context switch (swap out + swap in) ⇒ in RR il quanto di tempo dovrebbe essere circa 2sec (10 volte il context switch time)

• Il tempo di switch dipende molto dal transfer time e quindi si fa swap della sola memoria usata effettivamente dal processo

(7)

9.3 Swapping

• Se il processo è in BS non si può fare I/O direttamente sulle sue variabili⇒ transitare da buffer di sistema oppure bloccare lo swapping • Unix usava una versione di swapping e rilocazione • Windows 3.1 tiene in BS i processi "vecchi" e li

ricarica solo quando l’utente li seleziona (mouse) per farli girare

• Windows/NT usa il traduttore degli indirizzi dei nuovi processori e fornisce memory management sofisticato

20

9.4 Allocazione della Memoria

• Ma come si alloca la memoria ai processi?

21

9.4 Allocazione Contigua della

Memoria

• Due partizioni della memoria: una per il SO e una per i programmi utente

• Spesso il SO sta in memoria dove sta il vettore delle interruzioni, che di solito è in memoria bassa

0

640K

Utente Sistema operativo

(8)

9.4.1 Allocazione a Partizione

Singola

• Con registri di rilocazione e di limite (supporto hardware!) si ottiene:

– protezione del SO da accessi di utente – protezione dei processi l’uno verso l’altro

– dimensione dinamica del SO (per codice transiente) e degli utenti

23

9.4.2 Allocazione a Partizioni

Multiple

• La memoria è divisa in partizioni di dimensione fissa (ma non tutte uguali!)

• Ogni partizione contiene un unico programma, dall’inizio alla fine dell’esecuzione

• Il numero delle partizioni è uguale al grado di multiprogrammazione

• Quando il processo finisce la sua esecuzione, si carica un altro job dalla job queue (e il job entra nel sistema)

24

9.4.2 Allocazione a Partizioni

Multiple

• Usato ad esempio da IBM OS/360 (MFT) • Schema dell’IBM MVT: la memoria è

descritta nelle sue parti occupate da una immagine di processo, oppure libera (buco) • All’inizio è tutto un grande buco libero • Quando arriva un job, si cerca un buco per

contenere l’immagine del suo processo in memoria: il resto rimane un buco più piccolo.

(9)

26

9.4.2 Allocazione a Partizioni

Multiple

• P₄, P₅rimangono in job queue perché non c’è posto per loro in memoria. Quando finisce P2si forma un buco per P₄

• Bisogna fondere i buchi adiacenti • Dove allocare un processo?

– First Fit – Best Fit – Worst Fit

• Worst Fit funziona peggio degli altri; First e Best non sono sempre uno meglio dell’altro, ma First Fit costa molto meno di Best Fit

27

9.4.3 Frammentazione Esterna e

Interna

• Esterna: la memoria libera risulta scomposta in molteplici buchi piccoli, non contigui, che non riescono ad ospitare processi grandi

– Statisticamente, se N blocchi sono allocati, altri 0,5*N blocchi sono inutilizzati a causa della frammentazione esterna⇒ 30% della memoria totale è sprecato. Viene detta la regola del 50%

• Interna: costa troppo descrivere buchi molto piccoli, e quindi si agganciano ad una

(10)

9.4.3 Frammentazione Esterna e

Interna

• Soluzione possibile: compattamento. Spostare le immagini dei processi in MP in modo che le immagini siano contigue⇒ si forma così un unico buco

• Il compattamento richiede rilocazione delle immagini, sia del codice che dei dati. Ciò è possibile solo se la rilocazione è realizzata

dinamicamente (a run-time)

29

9.4.3 Frammentazione Esterna e

Interna

• Modi di compattare:

– tutti i processi ad un estremo della memoria (molto costoso)

– spostare i processi in buchi già esistenti verso gli estremi della memoria (si sposta di meno)

– parziale: solo per fare entrare un processo particolare – combinandolo con lo swapping

30

9.4.3 Frammentazione Esterna e

Interna

(11)

9.5 Paginazione

• Allocare in modo non contiguo, usando memoria dove è già disponibile, e dividere la memoria in buchi tutti uguali detti pagine

• 9.5.1 Metodo di Base

– Memoria Primaria divisa in frame, tutti uguali;

– memoria logica divisa in pagine tutte uguali, di dimensione uguale a quella dei frame;

– la BS è divisa in blocchi la cui dimensione è ancora uguale a quella delle pagine

32

9.5 Paginazione

• È necessario un supporto hardware: interposto fra CPU e MP

• indirizzo = (#pagina, offset di pagina) se i frame cominciano a

indirizzi multipli della dimensione del frame, e la dimensione è una potenza di 2, basta rilocare l’indirizzo di partenza della pagina

33

9.5 Paginazione

• #pagina è usato come indice in una page

table (preparata dal SO) che contiene

l’indirizzo di base del frame su cui è allocata la pagina

• Dimensione della pagina (2m_{): da 512 a} 8192 byte

(12)

Esempio di Paginazione

35

9.5 Paginazione

• C’è solo frammentazione interna (per l’ultima pagina dello spazio di indirizzi del processo)

– pagine piccole è meglio!

• Pagine grandi sono meglio per l’I/O

– la dimensione delle pagine è storicamente cresciuta per il diminuire del costo della memoria

• Serve una page table per ogni processo ⇒ protezione fra utenti

36

9.5 Paginazione

• Il SO mantiene anche una frame table che descrive lo stato di allocazione della memoria fisica

• Per fare I/O occorre dare al dispositivo l’indirizzo fisico, non quello virtuale (compito del SO)

• Per cambiare contesto occorre modificare i registri che definiscono la page all’hardware che traduce gli indirizzi⇒ context switch più lento!

(13)

9.5.1 Allocazione delle pagine

38

9.5.2.1 Supporto Hardware

• Svariati metodi per supportare le page table (PT) in hardware

• Il più semplice:

– set di registri dedicati allo scopo e molto veloci: ogni indirizzo generato dalla CPU deve essere tradotto – Es. PDP-11: 8 registri, pagine di 8KB. Spazio virtuale

di 64KB

– Ragionevole fino a PT di 256 elementi: oggi si hanno PT di milioni di elementi

⇒tutta la PT in hardware non è possibile

⇒PT in MP + PageTableBaseRegister (PTBR) che punta all’inizio della PT in MP

39

• PT in MP è molto lenta: raddoppia gli accessi in memoria (che già è lenta!)

⇒usare una cache (come al solito!) chiamata:

– registri associativi, oppure – MMU, oppure

– translation look-aside buffer (TLB)

9.5.2.1 Supporto Hardware

(14)

• Si interroga con page number e restituiscono frame number o trap

• Se ha successo (hit) penalizzazione circa del ~10% del tempo di accesso alla memoria

• Se ha insuccesso (miss) allora – si usa la PT in memoria

– certi hardware vanno da se in memoria – si inserisce il nuovo elemento della PT in TLB – se il TLB è pieno si sostituisce un vecchio elemento

9.5.2.1 Funzionamento del TLB

41

9.5.2.1 Funzionamento del TLB

42

• Quando si cambia contesto bisogna svuotare (flush) o invalidare il TLB altrimenti la traduzione sarebbe errata!

⇒grande costo del cambio di contesto

• inoltre molte trap perché il TLB è vuoto, oppure • salvataggio e ripristino del contenuto del TLB, ma

allora la commutazione di contesto è ancora più lunga ⇒grande è quindi il vantaggio nel commutare i contesto

fra thread dello stesso task

(15)

9.5.2.1 Importanza dell’ Hit Ratio

• Hit Ratio =:= tasso di successo nel TLB • Hp: 20 nsec accesso al TLB, 100nsec

accesso a MP; allora con hit ratio dell’80% si ha

effective memory access time = 0.80*120+0.2*220=140nsec • Con hit ratio del 98%

effective memory access time = 0.98*120+0.02*220=122nsec

• Motorola 68030 ha un TLB di 22 elementi, Intel 80486 ha 32 registri. Sostengono di avere un hit ratio da 80 a 98%

44

9.5.2.2 Protezione

• Bit in PT possono definire la pagina come read-only, read/write, execute, invalid

– trap per uso invalido, perché la CPU dichiara l’uso che vuole fare dell’indirizzo

45

9.5.2.2 Protezione

• Le pagine invalide sono quelle non usate dal processo (dimensione minore dello spazio max possibile)

• Le PT sono molto più piccole del max ⇒ page table length register(s) (PTLR(s)) offerti da alcuni hardware

(16)

9.5.3 Paginazione Multilivello

• Address Space di 232_{(ora anche 2}64_{); pagine di} 4KB(212₎

⇒dimensione PT 232_{/ 2}12_{= 2}20_{= 1 milione di}

elementi; 4B per entry → 4MB per la PT, per ogni processo: un pò troppo!

⇒Non si può allocare in modo contiguo ⇒I processi non la usano tutta

⇒È comodo che sia "sparsa", composta da molte zone usate, separate da buchi non usati (libertà nell’uso dello spazio virtuale)

⇒Usare uno schema a due livelli

47

9.5.3 Paginazione Multilivello

48

• Page Table esterna e interna. VAX ha una page table esterna di soli 4 elementi

• SPARC ha 3 livelli; MC68030 4 livelli

• Ancora serve caching! Con hit ratio di 98% si ha

effective memory address time = 0.98*120+0.02*520=128 nsec

(17)

• Le PT è comoda per il SO ma occupa un sacco di memoria

• Una IPT descrive invece solo l’occupazione dei frame di memoria fisica⇒ grande a seconda della memoria fisica

• Un elemento di IPT è così fatto, ad es. IBM RT:

<process-id, page-number> • e gli indirizzi sono una tripla

<process-id, page-number, offset>

9.5.4 Page Table Invertita (IPT)

50

9.5.4 Page Table Invertita (IPT)

51

9.5.4 Page Table Invertita (IPT)

• Le PT sono ancora necessarie per le pagine che sono su BS. Possono a loro volta essere tenute in MS

• Hash Table per facilitare la ricerca nella IPT che è tenuta per indirizzi fisici e viene scandita per indirizzi virtuali

• L’accesso hash aumenta gli accessi in memoria: si usano registri di cache

(18)

9.5.5 Pagine Condivise

• La paginazione rende "facile" la condivisione di codice (non

automodificantesi, o rientrante), anche a livello di librerie

• Le IPT non si prestano allo sharing perché obbligano le pagine condivise a stare nello stesso indirizzo virtuale e a usare un jolly-process-id nella IPT (⇒ si generano PT sparse!)

53

Esempio di condivisione di pagine

54

9.6 Segmentazione

• La paginazione separa la visione della memoria dell’utente da quella fisica. • MA come è più naturale per l’utente?

– Lineare oppure una collezione di segmenti di dimensione diversa, senza ordinamento fra loro?

(19)

9.6 Segmentazione

• 9.6.1 Metodo base

indirizzo = <#segmento, offset>

• L’utente (compilatore, linker) libero di usare i segmenti per riflettere la struttura del programma

– variabili locali

– codice di una funzione o procedura

– variabili locali statiche di funzione o procedura – stack di esecuzione

– ciascun array su un suo segmento

56

9.6.2 Supporto Hardware

• Segment Table (ST): ogni elemento contiene base (fisica) e limite del segmento

• Notare la somma vera e propria!

57

(20)

9.6.2 Supporto Hardware

• ST può stare in registri di macchina (ma allora deve essere piccola!)

• ST in MP e Segment Table Base Register (STBR) che la punta + Segment Table

Length Register (STLR) perché la

lunghezza della ST può variare molto • Cache usata per non raddoppiare il tempo di

accesso 59

9.6.4 Protezione e Sharing

• Protezione associata ai segmenti • Sharing associato ai segmenti • Richiedono ambedue al SO meno lavoro della paginazione 60

9.6.4 Frammentazione

• Lo scheduler di lungo termine (job scheduler) deve trovare posto ai segmenti (come per la paginazione) ma i segmenti sono di dimensione diversa

⇒gestione dinamica della memoria ⇒best-fit o first-fit

⇒frammentazione esterna

⇒si può compattare quando si vuole

• La grandezza media dei segmenti è abbastanza piccola

(21)

9.7 Segmentazione con Paginazione

• Ogni schema ha i suoi vantaggi. Infatti MC680xx ha paginazione (modificata), Intel 80x86 segmentazione (modificata)

⇒vanno a fondere i due approcci

• Chi ha insegnato a tutti è stato il MULTICS

– 18 bit di segment number, 16 bit di offset – Ogni segmento (64KB) è paginato a 1KB.

62

9.7.1 Traduzione degli indirizzi

in MULTICS

63

• Anche la ST è troppo grande, per cui viene paginata anch’essa, componendo il segment number

• Vi sono 16 registri associativi che contengono una chiave di 8+10+6=24 bit e come valore il numero di frame

9.7.1 Traduzione degli indirizzi

in MULTICS

(22)

• Intel 386 e 486 usano segmentazione + paginazione. OS/2 usa solo in parte il 386 • Ci sono 16K segmenti ognuno fino a 4GB,

dimensione di pagina 4KB • Ogni processo ha due partizioni:

– 1. Una privata, fino a 8K segmenti: descritta in una Local Descriptor Table (LDT)

– 2. Una condivisa fra tutti i processi, fino a 8K segmenti: descritta in una Global Descriptor Table (GDT)

9.7.2 OS/2 a 32 bit

65

9.7.2 OS/2 a 32 bit

• Ogni elemento di LDT e di GDT è di 8 byte: indirizzo di base, lunghezza, protezioni, ...

– Indirizzo logico =:= <selettore, offset>, dove

selettore= <s, g, p> di ampiezza:

13 1 2

con s=#segmento; g=LDT/GDT; p=protezioni;

offsetè di 32 bit

• Come è fatta la CPU? ...

66

• La CPU ha:

– 6 segment registers (che contengono il selector) per indirizzare 6 segmenti contemporaneamente – 6 registri di microprogramma che contengono i

descrittori dei 6 segment register (presi dalla relativa Local/Global Descriptor Table)

• Un indirizzo è sempre relativo ad un segment register

(23)

• Offset + base del segmento generano un indirizzo (virtuale) a 32bit lineare (la somma è su 32bit), ma prima è controllato il limite del segmento e poi viene mappato scomponendolo così:

page-number page-offset p1 p2 d

10 10 12 bit

• Paginazione a due livelli

9.7.2 OS/2 a 32 bit

68

9.7.2 OS/2 a 32 bit

• p1 è chiamato directory pointer e p2 page table pointer

• La Directory Table deve stare in memoria, ma le Page Table possono essere swapped-out (invalid bit nell’elemento di directory) • Le Page Table sono nella zona bassa della MP (il primo bit nell’elemento di directory è l’invalid bit)

69

(24)

Conclusioni

• Algoritmi di gestione della memoria molto diversi, da quelli semplici per sistema single user alla segmentazione paginata

• È il supporto hardware che determina la classe di algoritmi usabili ⇔ il supporto hardware è progettato pensando alla classe di algoritmi che si vuole supportare

71

Conclusioni

• Quali considerazione fare nel valutare un metodo di gestione della memoria?

– supporto hardware disponibile – velocità (più è complesso, più è lento) – frammentazione (limita il livello di

multiprogrammazione)

– rilocazione: supportata/non supportata – swapping: se possibile aumenta il livello di

multiprogrammazione

– condivisione testo e dati fra utenti (ancora per aumentare il livello di multiprogrammazione) – protezione 72

Esercizio 9.5

• P1 (212K), P2(417K), P3 (112K), P4 (426K) • First-Fit: P1(2),P2(5),P3(3) • Best-Fit: P1(4),P2(2),P3(3),P4(5) • Worst-Fit: P1(5),P2(2),P3(4) 100k 500k 200k 300k 600k P1 P2 P3

(25)

Esercizio Allocazione Contigua

• Memoria a partizioni variabili

• Buchi liberi in ordine crescente di indirizzo:

– 8k, 4k, 20k, 18k, 7k, 10k, 12k, 15k

• Quale buco viene scelto per le richieste

– A) 11k – B) 20k – C) 9k First Fit: A -> 20K B -> non allocabile C -> 9K 8k, 4k, 18k, 7k, 10k, 12k, 15k 74

Esercizio Allocazione Contigua

• Best Fit: – A -> 12K – B -> 20K – C -> 10K 8k, 4k, 18k, 7k, 1k, 1k, 15k 75 • Worst Fit: – A -> 20K – B -> non allocabile – C -> 18K 8k, 4k, 9k, 9k, 7k, 10k, 12k, 15k

(26)

Esercizio: Paginazione

• Spazio Indirizzi virtuali (logici) di 64K : 16 bit

• Memoria fisica di 32K

• Pagine di 4K : 12 bit offset (16 pagine)

I x 7 I X 6 V 1 5 V 3 4 I X 3 I X 2 V 0 1 V 2 0 Valido/invalido # frame # pagina 77 • 24: 0000 000000011000

– #pag: 0, offset 24 Æ #frame: 2 offset 24 – 0010 000000011000 Æ 8216 • (0 * 4096)+24 Æ (2 * 4096)+24 = 8216 • 8195: (2 * 4096) + 3 Æ page fault • 16385: (4 * 4096) + 1 Æ (3 * 4096) +1 = 12289 I x 7 I X 6 V 1 5 V 3 4 I X 3 I X 2 V 0 1 V 2 0 Valido/invalido # frame # pagina 78

Esercizio: Paginazione

• Dimensione Pagine di FFF byte

• Memoria fisica e` composta da 7F frame • # pagine massimo e` FF

• Qual e` la lunghezza di un indirizzo logico?

– Offset: 12 bit, #pag: 8 bit Æ 20 bit

• Qual e` la lunghezza di un indirizzo fisico ?

(27)

• 0345C: #pag: 03 offset: 45C – 7E 45C Æ (126*4096)+1116 = 517212 … V 126 (7E) 3 … … … Valido/invalido # frame # pagina