Domenico Cotroneo » 17.Gestione della memoria

Sommario

• Introduzione
• Aspetti caratterizzanti la gestione della memoria
• Paginazione
• Segmentazione
• Segmentazione con paginazione

Introduzione

La memoria principale costituisce, insieme alla CPU, una delle risorse necessarie per fornire il supporto al concetto di processo.

Infatti, per realizzare l’astrazione di processo, o programma in esecuzione, è necessario disporre:

• di una unità di elaborazione che esegue il programma;
• di un’area di memoria nella quale il programma risiede (immagine del processo).

Aspetti caratterizzanti la gestione della memoria

Supporto Hardware per la gestione della memoria (MMU).

Organizzazione logica della memoria virtuale (segmentata o contigua).

Organizzazione fisica (allocazione del processo in zone contigue o in zone non contigue).

Dimensione della memoria virtuale (dimensione dell’immagine di un processo maggiore della dimensione fisica della memoria).

Tecniche di gestione della memoria

Parametri caratterizzanti la gestione della memoria

Rilocazione

• statica
• dinamica

Allocazione

• contigua
• non contigua

Organizzazione dello spazio virtuale

• spazio virtuale unico
• spazio virtuale segmentato

Caricamento

• tutto insieme
• a domanda

Rilocazione

Generalmente, l’associazione di istruzioni e dati a indirizzi di memoria si può compiere nelle seguenti fasi:

• Compilazione: se nella fase di compilazione si sa dove il processo risiederà nella memoria, si può generare codice assoluto (absolute code); se, in un momento successivo, la locazione iniziale cambiasse, sarebbe necessario ricompilare il codice;
• Caricamento: se nella fase di compilazione non è possibile sapere in che punto della memoria risiederà il processo, il compilatore deve generare codice rilocabile (relocatable code);
• Esecuzione: se durante l’esecuzione il processo può essere spostato da un segmento di memoria a un altro, si deve ritardare l’associazione degli indirizzi fino alla fase d’esecuzione (rilocazione dinamica). Per realizzare questo schema sono necessarie specifiche caratteristiche dell’architettura.

Fasi di elaborazione per un programma utente

Swapping

Uno dei principali motivi che rende necessaria la rilocazione dinamica è lo swapping.

Un processo può essere trasferito temporaneamente nella memoria ausiliaria (backing store) e poi riportato nella memoria centrale al momento di riprenderne l’esecuzione.

Ciò al fine di far convivere nel sistema più processi la cui somma delle immagini eccede la memoria disponibile.

Roll out, roll in: variante impiegata per gli algoritmi di scheduling basati sulle priorità: il processo con priorità inferiore viene scaricato dalla memoria centrale.

La maggior parte del tempo di swapping è data dal tempo di trasferimento. Il tempo di trasferimento totale è direttamente proporzionale alla quantità di memoria interessata

Rilocazione dinamica: spazio di indirizzi logici e fisici

Il concetto di spazio degli indirizzi logici associato a uno spazio degli indirizzi fisici separato è fondamentale per una corretta gestione della memoria.

• Indirizzo logico (logical address): indirizzo generato dalla CPU; detto anche indirizzo virtuale (virtual address).
• Indirizzo fisico (physical address): indirizzo visto dall’unità di memoria.

Il metodo di associazione degli indirizzi nella fase di compilazione produce indirizzi logici e fisici identici.

Nell’associazione in fase di caricamento, invece, gli indirizzi logici vengono completamente rimpiazzati da quelli fisici.

Infine, nell’associazione nella fase d’esecuzione gli indirizzi logici non coincidono con gli indirizzi fisici.

Unità di gestione della memoria (MMU)

Dispositivo (hardware) per l’associazione, nella fase di esecuzione, degli indirizzi logici agli indirizzi fisici.

Nello schema MMU (Memory Management Unit), quando un processo utente genera un indirizzo, prima dell’invio all’unità di memoria, si somma a tale indirizzo il valore contenuto nel registro di rilocazione.

Il programma utente tratta con gli indirizzi logici; non considera mai gli indirizzi fisici reali.

Immagine di un processo

Costituita da tre segmenti indipendenti: codice; dati; stack

Allocazione

L’immagine di un processo può essere allocata in memoria fisica secondo due modalità:

1. allocazione contigua;
2. allocazione non contigua (paginazione).

Allocazione contigua della memoria

La memoria centrale si divide di solito in due partizioni:

• una per il sistema operativo residente;
• una per i processi utenti.

Protezione della memoria

Lo schema a registro di rilocazione viene usato per proteggere il sistema operativo dai processi utenti e i processi utenti dagli altri processi utenti.

Il registro di rilocazione contiene il valore dell’indirizzo fisico minore; il registro di limite contiene l’intervallo di indirizzi logici (ciascun indirizzo logico deve essere minore del contenuto del registro di limite).

Registri di rilocazione e di limite

Allocazione contigua della memoria con partizioni variabili

Come soddisfare una richiesta di dimensione n data una lista di buchi liberi.

First-fit: si assegna il primo hole abbastanza grande.

Best-fit: si assegna l’hole più piccolo in grado di contenere il processo; occorre compiere la ricerca su tutta la lista, sempre che non sia ordinata per domensione. Produce le hole inutilizzate più piccole, ed è pertanto noto come best-fit.

Worst-fit: si assegna il hole più grande; anche in questo caso occorre esaminare tutta la lista. Produce le hole inutilizzate più grandi.

First-fit e best-fit funzionano meglio di worst-fit poiché rendono più efficienti l’utilizzo della memoria.

Frammentazione

Frammentazione esterna: Spazio di memoria perduto sotto forma di spezzoni:

• lo spazio di memoria totale sarebbe sufficiente per soddisfare una richiesta, ma non è contiguo.

Frammentazione interna: Spazio di memoria perduto perché assegnato ma non utilizzato:

• la memoria è assegnata con valori multipli di una certa dimensione, per cui ad un processo potrebbe venirne assegnata un valore leggermente maggiore a quello richiesto.

Una soluzione al problema della frammentazione esterna è data dalla compattazione:

• riordina il contenuto della memoria per riunire la memoria libera in un unico grosso blocco;
• è possibile solo se la rilocazione è dinamica, e si compie nella fase di esecuzione.

Organizzazione dello spazio virtuale

Un aspetto importante della gestione della memoria è quello della separazione tra la visione della memoria dell’utente (spazio virtuale) e l’effettiva memoria fisica.

Lo spazio virtuale può essere visto come:

• uno spazio unico (corrispondente all’intera immagine del processo);
• un insieme di segmenti.

La segmentazione

La segmentazione consiste nell’allocare segmenti indipendenti in zone di memoria fisica non contigue.

Tale tecnica consente di aumentare la complessità del linker.

Tecnica di segmentazione

Per ogni indirizzo virtuale x deve essere possibile capire a quale segmento esso appartiene ... nel caso più semplice la MMU deve avere tre coppie RB/RL

Schema generale

Il passaggio da tre soli segmenti ad un numero arbitrario implica che:

• il processore generi indirizzi virtuali che indicano esplicitamente a quale segmento l’indirizzo appartiene (x=<sg, of >);
• non è più possibile mantenere i registri base/limite all’interno della MMU e, pertanto, le coppie base/limite per ogni segmento sono mantenute in un’apposita Tabella dei segmenti.

Traduzione degli indirizzi segmentati

Al descrittore di un processo vengono aggiunti due campi:

• numero di segmenti del processo;
• indirizzo della tabella dei segmenti.

Quando il processo è schedulato i valori precedenti vengono caricati in due appositi registri di macchina:

• Segment Table Limit Register (STLR);
• Segment Table Base Register (STBR).

Traduzione degli indirizzi segmentati

Efficienza nell’accesso in memoria

Il ricorso alla tabella dei segmenti allocata in memoria principale genera una notevole perdita di efficienza:

• per ogni indirizzo generato dalla CPU è necessario raddoppiare gli accessi alla memoria (uno alla tabella dei segmenti ed uno all’informazione desiderata).

Al fine di ridurre questa perdita di efficienza vengono mantenuti nella MMU alcuni registri associativi.

Tempo effettivo d’accesso

Lookup associativo = ε unità di tempo.

Si assuma un tempo d’accesso alla memoria pari a k

Tasso di successi (hit ratio): percentuale di volte che un numero di pagina si trova nei registri associativi

Tasso di successi = α

Tempo effettivo d’accesso (EAT, effective access time)

EAT = (k + ε) α + (2k + ε)(1 – α) = (2 – α)k + ε

La località dei programmi aiuta a migliorare l’efficienza!

Protezione

Aggiunta di un terzo campo di controllo nel quale sono presenti alcuni bit che rappresentano i diritti di accesso al segmento

Paginazione

Metodo di gestione della memoria che permette che lo spazio degli indirizzi fisici di un processo non sia contiguo.

Suddivide la memoria fisica in blocchi di memoria di dimensioni fisse (noti anche come pagine fisiche o frame). La dimensione di una pagina è tipicamente una potenza di 2, compresa tra 512 byte e 16 MB.

Tiene traccia di tutti i blocchi liberi.

Utilizza una tabella delle pagine per tradurre gli indirizzi logici in indirizzi fisici.

Può evitare la frammentazione esterna, ma introduce frammentazione interna.

Schema di traduzione degli indirizzi

Ogni indirizzo generato dalla CPU è diviso in:

• Numero di pagina (p): serve come indice per la tabella delle pagine, che contiene l’indirizzo di base nella memoria fisica di ogni pagina;
• Scostamento di pagina (d): combinato con l’indirizzo di base definisce l’indirizzo della memoria fisica, che si invia all’unità di memoria.

Architettura di paginazione

Architettura di paginazione

La tabella delle pagine è mantenuta nella memoria principale.

Un registro di base della tabella delle pagine (page-table base register, PTBR) punta alla tabella stessa.

Un registro di lunghezza della tabella delle pagine (page-table length register, PRLR) indica la dimensione della tabella delle pagine.

Con questo metodo, per accedere a un byte occorrono due accessi alla memoria, uno per l’elemento della tabella delle pagine e uno per il byte stesso.

La soluzione tipica a questo problema consiste nell’impiego di una speciale, piccola cache di memoria veloce detta TLB (translation look-aside buffer), una memoria associativa ad alta velocità.

Tempo effettivo d’accesso

Lookup associativo = ε unità di tempo.

Si assuma un tempo d’accesso alla memoria pari a k.

Tasso di successi (hit ratio): percentuale di volte che un numero di pagina si trova nel TLB; relativo al numero di registri associativi.

Tasso di successi = α

Tempo effettivo d’accesso (EAT, effective access time)

EAT = (k + ε) α + (2k + ε)(1 – α) = (2 – α)k + ε

Protezione della memoria

In un ambiente paginato, la protezione della memoria è assicurata dai bit di protezione associati a ogni blocco di memoria.

Di solito si associa un bit di validità a ciascun elemento della tabella delle pagine:

• “bit valido” indica che la pagina corrispondente è nello spazio d’indirizzi logici del processo, quindi è una pagina valida;
• “bit non valido” indica che la pagina non è nello spazio d’indirizzi logici del processo.

Dimensione della tabella delle pagine

Spazio d’indirizzamento=32 bit.
Dimensione delle pagine di 1KBbyte (2¹⁰)

• Dimensione della tabella 2²²= 4 Mbyte !!!
• Frammentazione interna media= 2K Byte

Dimensione delle pagine di 64Kbyte (2¹⁶)

• Dimensione della tabella 2¹⁶=64 K
• Frammentazione interna media= 32 Kbyte !!!

Bisogna cercare un buon compromesso tra i due valori

Struttura della tabella delle pagine

• Paginazione gerarchica
• Tabella delle pagine di tipo hash
• Tabella delle pagine invertita

Paginazione gerarchica

Suddivide la tabella delle pagine in parti più piccole, secondo una organizzazione gerarchica.

Un metodo consiste nell’adottare un algoritmo di paginazione a due livelli, nel quale si pagina la stessa tabella delle pagine.

Esempio di paginazione a due livelli

Un indirizzo logico (su una macchina a 32 bit con dimensione delle pagine di 4K) è suddiviso in:

• un numero di pagina di 20 bit
• uno scostamento di pagina di 12 bit
  • con 12 bit si possono indirizzare 2¹²=4K locazioni

Paginando la tabella delle pagine, anche il numero di pagina è a sua volta diviso in:

• un numero di pagina di 10 bit
• uno scostamento di pagina di 10 bit

Quindi, l’indirizzo logico è:

dove p_i è un indice della tabella esterna delle pagine, e p₂ è lo scostamento all’interno della pagina indicata dalla tabella esterna delle pagine.

Schema di una tabella delle pagine a due livelli

Tabella delle pagine di tipo hash

Comune negli spazi d’indirizzi relativi ad architetture > 32 bit.

L’argomento della funzione di hash è il numero della pagina virtuale. Ogni elemento della tabella hash contiene una lista concatenata di elementi che la funzione hash fa corrispondere alla stessa locazione.

I numeri di pagina virtuali vengono confrontati e, se coincidono, si usa l’indirizzo del relativo blocco di memoria per generare l’indirizzo fisico desiderato.

Tabella delle pagine invertita

Generalmente ogni tabella delle pagine contiene un elemento per ogni pagina virtuale, ed esiste una tabella per ogni processo.

Tabella delle pagine invertita

• Una sola tabella delle pagine per tutti i processi.
• Questa tabella ha un elemento per ogni pagina reale.
• Ogni elemento contiene l’indirizzo virtuale della pagina memorizzata in quella locazione fisica, con informazioni sul processo che possiede tale pagina.
• Utilizzata nelle architetture UltraSparc (64 bit) e Power PC.

Pagine condivise

Codice condiviso

• Una copia di codice rientrante condiviso tra i processi (es. editor di testi, compilatori, interfacce a finestre).
• Il codice condiviso deve essere collocato nella stessa locazione nello spazio degli indirizzi logici di tutti i processi.

Codice privato e dati

• Ciascun processo dispone di una propria copia di codice e dati.
• Le pagine per il codice e i dati possono essere collocate in un qualsiasi punto nello spazio degli indirizzi logici.

Segmentazione paginata