21 Jul 2023, 2:49 PM

9. Gestione della memoria

Un compito fondamentale di ogni SO è la gestione della memoria, in particolare la condivisione della memoria da parte di più processi è essenziale per l'efficienza del sistema. In particolare, in seguito all'introduzione della multiprogrammazione è diventata necessaria la definizione di uno spazio di indirizzamento, ovvero l'insieme degli spazi di memoria indirizzabili da un processo, e la sua protezione, poichè se non gestita può portare al sovrapporsi degli spazi di indirizzamento tra due o più processi. Le tecniche di gestione utilizzabili sono generalmente dipendenti dall'hardware, in quanto questo implementa apposite istruzioni e algoritmi di gestione. Dal punto di vista di un processo, la maggior parte degli accessi in memoria avviene tramite decodifica degli indirizzi, ovvero la traduzione di un indirizzo logico (come una variabile) in un indirizzo fisico, che corrisponde ad una vera e propria locazione in memoria.
Ogni programma deve essere portato in memoria ed essere trasformato in processo per essere eseguito
È importante però ricordare che il programma diventa un processo solo quando raggiunge la memoria. Solo una volta che il processo ha terminato, la memoria viene rilasciata.

Vediamo ora le diverse fasi della traduzione da programma a processo.

TraduzioneProg-Proc.png|700

Gli indirizzi hanno diverse rappresentazioni nelle varie fasi di costruzione di un programma.

Binding

Prima abbiamo accennato che per effettuare un accesso in memoria dobbiamo prima tradurre un indirizzo logico in un indirizzo fisico. Questa operazione è chiamata binding e può avvenire in differenti modi e tempi:

a tempo di compilazione: deve essere già nota la locazione del programma, pertanto gli indirizzi fisici sono scritti direttamente nel codice. Il binding avviene a compile time ed è definito statico in quanto gli indirizzi fisici e logici sono uguali e se questi cambiano il codice deve essere ricompilato.
a tempo di caricamento: nel codice si specifica un indirizzo assoluto come primo indirizzo di allocazione e gli altri sono scritti in relazione a quest'ultimo (offset). Anche questo tipo di binding è statico, ma il codice va ricompilato solo se cambia l'indirizzo di riferimento.
a tempo di esecuzione: non sono presenti indirizzi assoluti (fisici) nel codice, perchè la locazione in memoria potrebbe cambiare anche durante l'esecuzione. Questo tipo di binding è definito dinamico ed è utilizzato oggi nella maggior parte dei SO, ma richiede HW apposito per essere efficiente, ovvero la Memory Management Unit (MMU). In breve, è un dispositivo hardware che mappa indirizzi virtuali (logici) in indirizzi fisici. Ha un suo registro base (chiamiamolo $r$ ) il cui valore viene aggiunto ad ogni indirizzo generato da un processo, e inviato alla memoria. Il programma utente interagisce con gli indirizzi logici (da 0 a max) ma non vede mai gli indirizzi fisici reali (da r a r+max). In questo modo il programma è indipendente da informazioni specifiche della memoria (valore di rilocazione, capacità della memoria, …).

Nota

Per assicurare che non ci siano accessi illegali alla memoria, ogni processo è associato ad un registro base e ad un registro limite. Il registro base contiene il più basso valore indirizzabile da un processo, mentre il registro limite contiene il totale di indirizzi specificabili dal programma, in modo tale che (reg. base + reg. limite) diano il più piccolo valore non indirizzabile dal programma, il limite superiore dello spazio degli indirizzi. Pertanto un indirizzo logico^[1] (generato dalla CPU, detto anche indirizzo virtuale) è sempre minore del registro limite e gli indirizzi fisici (indirizzo visto dalla memoria) devono essere compresi tra reg. di base e (reg. di base + reg. limite). Nel caso di binding dinamico, o a run time, basta cambiare il valore del registro di base, tutti gli indirizzi fisici saranno calcolati durante le operazioni con uno spiazzamento sugli indirizzi logici, in particolare ind. fisico = ind. logico + reg. base. Invece nel binding a compile o load-time indirizzo fisico e logico coincidono, visto che sono fissi e se cambiano bisogna ricompilare il programma.

Dynamic linking and loading

Le operazioni di linking e di loading viste nell'immagine sopra possono essere effettuate in modo statico o dinamico.

Linking: associazione a librerie esterne, il metodo statico prevede di creare una copia del codice delle librerie usate. Nel metodo dinamico il codice è invece sostituito da stub, ovvero riferimenti alla specifica libreria. Se questa viene richiamata, lo stub carica in memoria la libreria. Si ha la possibilità di avere librerie condivise se ci sono più processi che utilizzano le stesse. In questo modo si ha un generale risparmio di codice, d'altro canto, in quanto questo e condiviso, si ha la necessità di supervisione da parte del SO.
Loading: associazione a librerie di sistema, con il metodo statico tutto il codice delle routine è caricato insieme al programma al tempo dell'esecuzione, anche il codice inutile, come per il linking statico. Con il metodo dinamico, il caricamento è posticipato al momento del primo utilizzo del metodo e il codice non utilizzato non viene caricato.
Risulta così molto efficiente, specie se si fa uso di codice usato molto raramente, come le routine di errore.

In conclusione, in un sistema multiprogrammato non è possibile conoscere in anticipo dove un processo può essere posizionato in memoria, dunque il binding a tempo di compilazione non è possibile. Inoltre l’esigenza di avere lo swap impedisce di poter utilizzare indirizzi rilocati in modo statico quindi nemmeno il binding a tempo di caricamento è possibile. Pertanto, nei sistemi general-purpose si usa soltanto il binding a tempo di esecuzione (detto anche rilocazione dinamica) e da ora in poi assumiamo che quest'ultimo sia usato e che tutto il processo debba essere caricato in memoria.

Allocazione della memoria

Esistono differenti politiche per il caricamento dei processi in memoria e per riservare loro lo spazio. Gli obiettivi principali di questo ambito di gestione sono l'aumentare l'utilizzo della memoria, allocando più processi possibili ed aumentando il grado di multiprogrammazione.

Vediamo ora $4$ schemi di gestione della memoria.

Allocazione contigua

I processi vengono allocati in memoria in posizioni contigue all’interno di una partizione. Inoltre tutta la memoria è suddivisa in partizioni, che possono essere di dimensione fissa o variabile. Distinguiamo quindi i $2$ casi, vedendo prima la tecnica delle partizioni fisse e successivamente quella a partizioni variabili.

Partizioni Fisse

Il SO crea appositamente delle partizioni di dimensione fissa e predeterminata all'avvio, ma che possono avere dimensione diversa tra loro. L'assegnazione della memoria è effettuata dallo scheduling a lungo termine e possiamo implementarla in $2$ modi:

Una coda per partizione: il processo viene assegnato alla partizione più piccola in grado di contenerlo. È una soluzione poco flessibile visto che possono esserci partizioni vuote.
Coda unica: un'unica queue, con la quale le partizioni vengono assegnate con differenti algoritmi come:
- FCFS: Facile, ma vi è un basso utilizzo della memoria
- Scansione della coda
  - Best-fit-only: Scelta del job con dimensioni più simili alla partizione
  - First-available-fit: Scelta del primo job che può stare nella partizione

Vantaggi

Relativa semplicità

Svantaggi

Il grado di multiprogrammazione è limitato dal n° di partizioni; per esempio se la ram ha 20 partizioni allora può contenere massimo 20 processi
Abbiamo il problema della frammentazione, che porta ad uno spreco di memoria. Essa può essere interna (alla partizione) se la dimensione della partizione è più grande della dimensione del job, ossia la partizione non viene riempita del tutto e si spreca un po' di spazio, oppure esterna se la dimensione della partizione è più piccola della dimensione del job, ossia alcune partizioni non vengono utilizzate e rimangono vuote.

Partizioni variabili

Il SO crea partizioni di dimensioni identiche a quelle dei processi, cercando così di eliminare la frammentazione interna. Quando arriva un processo, viene messo nella prima buca (blocco di memoria disponibile) che può contenerlo. Dunque il S.O. deve mantenere informazioni sulle partizioni allocate e sulle buche. L'assegnazione della memoria possiamo implementarla in $3$ modi:

First-fit: il processo viene allocato nella prima buca grande a sufficienza (metodo migliore)
Best-fit: il processo viene allocato nella buca più piccola che può contenerlo (minimizza lo spreco ma è troppo lento, visto che bisogna scansionare tutte le buche)
Worst-fit: processo allocato nella buca più grande trovata (spreca memoria ed è troppo lento, visto che bisogna scansionare tutte le buche)

Vantaggi

Non produce frammentazione interna (in realtà c'è sempre un po' frammentazione interna, ma è minimizzata, non si può fare meglio), in quanto ogni partizione ha dimensione pari a quella richiesta dal processo.

Svantaggi

Tuttavia in media aumenta la frammentazione esterna, in quanto si producono molte partizioni di piccola dimensione. Si stima infatti che con il first-fit, dati $N$ blocchi allocati, $0.5 \cdot N$ blocchi vanno persi.

Quale può essere una soluzione intuitiva per risolvere questo problema? La compattazione!
Si può quindi spostare il contenuto della memoria in modo da rendere contigue tutte le partizioni. Questo tuttavia è possibile solo se la rilocazione è dinamica e richiede la modifica del registro base. Per questo potrebbe risultare anche abbastanza costoso.

Partizionamento-Var.png|700

Tecnica del buddy system

È un compromesso tra partizioni fisse e variabili. Essenzialmente la memoria è vista come una serie di blocchi di dimensione $2^{K}$ , con $L < k < U$ , dove $2^{L}$ è il più piccolo blocco allocato mentre $2^{U}$ è il più grande blocco allocato (es. tutta la memoria).
All'inizio tutta la memoria è disponibile, dunque ci sarà un blocco unico di dimensione $2^{U}$ . Quando arriva una richiesta di dimensione $s$ , si cerca un blocco libero con dimensione “adatta” purché sia pari a una potenza del $2$ . In parole semplici, se dividendo per $2$ il blocco la richiesta non ci sta più allora la piazzo nel blocco corrente, altrimenti posso dividere il blocco in $2$ e rifare ricorsivamente il controllo, finchè appunto non arriverò ad allocare un blocco di dimensione $2^{U - 1} < s \leq 2^{U}$ , quindi grande più o meno quanto la richiesta. Quando invece un processo rilascia la memoria, il suo blocco torna a far parte della lista dei blocchi di dimensione corrispondente. Se si formano $2$ blocchi adiacenti di dimensione $2^{K}$ , è possibile compattarli ottenendo un unico blocco libero di dimensione $2^{K + 1}$ . Di seguito è riportato un esempio.

Buddy-system.png|700

Vantaggi

La compattazione richiede solo di scorrere la lista dei blocchi di dimensione $2^{K}$ , quindi è veloce.

Svantaggi

La frammentazione interna è ampiamente ridotta rispetto all'allocazione a partizioni fisse, ma persiste, come si può notare nell'esempio sopra.

Paginazione

Questa tecnica evita del tutto la frammentazione esterna (come le partizioni variabili) in quanto permette l'allocazione dei processi non contigua. Questo è possibile con la divisione della memoria fisica in frame e la memoria logica in pagine di uguale dimensione. Quando un processo richiede memoria gli vengono assegnate delle pagine, per cui la frammentazione interna è limitata al più ad una pagina per processo. Per esempio, se la dimensione della pagina è pari a $1 K B$ , la dimensione del programma pari a $2.3 K B$ , saranno necessarie $3$ pagine per allocare il processo e dell’ultima pagina si userà solo $0.3 K B$ . Dunque è ancora possibile della frammentazione interna, ma solo nell’ultima pagina. Le corrispondenze pagine-frame sono registrate in un'apposita page table salvata in memoria, che ogni processo possiede. Quando la CPU legge un indirizzo logico, la MMU effettua la traduzione grazie alla tabella.

Come avviene la traduzione da indirizzo logico ad indirizzo fisico?

L’indirizzo generato dalla CPU viene diviso in due parti:

numero di pagina (p): ci indica la pagina in sè
offset (d): ci indica i bit che dobbiamo leggere di quella pagina

Esempio

In questo esempio abbiamo una memoria di $8 K B$ divisa in pagine da $1 K B$ ciascuna. Dunque la pagina $0$ va da $0$ a $1023$ , la pagina $1$ da $1024$ a $2047$ ecc.

Come viene tradotto l'indirizzo logico $936$ ?
L'indirizzo appartiene alla pagina $0$ , visto che $⌊ \frac{936}{1024} ⌋ = 0$ , e l'offset sarà proprio di $936$ . Dunque visto che le pagine partono da $0$ e i frame da $1$ , la pagina $0$ viene tradotta proprio nel frame $1$ (che vanno da $1024$ a $2047$ ). Dunque l'indirizzo fisico sarà $1024 + offset = 1024 + 936 = 1960$
Come viene tradotto l'indirizzo logico $2049$ ?
L'indirizzo appartiene alla pagina $2$ , visto che $⌊ \frac{2049}{1024} ⌋ = 2$ , e l'offset sarà di $2049 m o d 2048 = 1$ . Dunque visto che le pagine partono da $0$ e i frame da $1$ , la pagina $2$ viene tradotta nel frame $3$ (che vanno da $3072$ a $4095$ ). Dunque l'indirizzo fisico sarà $3072 + offset = 3072 + 1 = 3073$

Tale metodo ha un'efficienza accettabile solo se la tabella è ad accesso rapido, altrimenti il costo di accesso risulta proibitivo. Vediamo ora le $2$ alternative per l'implementazione della paginazione.

Implementazione tramite registri

Le entry (righe) della tabella delle pagine sono memorizzate in appositi registri della CPU. La velocità di accesso è massima, ma questa soluzione causa parecchio overhead nel context switch. Il problema principale, tuttavia, è lo scarso numero di registri disponibili e quindi delle entry memorizzabili.

Implementazione in memoria

Questo metodo prevede di tenere in memoria la tabella di ogni processo in esecuzione. La locazione della tabella è memorizzata in un apposito registro detto Page Table Base Register (PTBR). Questo riduce di molto l'overhead in quanto, durante il context switch, la CPU dovrà solo cambiare il valore del PTBR. Opzionalmente è disponibile anche il registro Page-table length register (PTLR), che contiene la dimensione della tabella delle pagine.

Il problema principale di questo approccio è il tempo di accesso alla memoria, in quanto ogni traduzione richiede un accesso per leggere la tabella ed un accesso per l'indirizzo fisico.

Per risolvere questo problema si utilizza una cache apposita detta Translation Lookaside Buffer (TLB), che consiste in una serie di coppie chiave-valore, contenente le associazioni pagina-frame. La realizzazione HW di tale cache permette il confronto parallelo di tutte le entry e risulta pertanto estremamente veloce. Se un'associazione non viene trovata nel TLB, si procede ad un accesso in memoria e si copia l'associazione nella TLB. Sebbene questa possa contenere un numero limitato di entry visto che è molto costoso, la sua hit ratio è molto alta, riducendo così il tempo di accesso sensibilmente. Generalmente, il TLB viene ripulito ad ogni context switch per evitare mapping di indirizzi errati. In alternativa, è possibile memorizzare in ogni tupla un ID del processo, per evitare di smontare ogni volta la cache.
Riassumendo, durante un accesso alla memoria:

se la pagina cercata è nel TLB, il TLB restituisce il numero di frame con un singolo accesso. In questo modo il tempo richiesto è minore del 10% del tempo richiesto in assenza di TLB
altrimenti è necessario accedere alla tabella delle pagine in memoria

Possiamo allora calcolare il tempo di accesso effettivo alla pagina. Nella formula sottostante α rappresenta l'hit ratio, ovvero la percentuale delle volte in cui una pagina si trova nel TLB.

EAT = (T_{T L B} + T_{M E M}) \cdot α + (T_{T L B} + 2 \cdot T_{M E M}) \cdot (1 - α)

dove $T_{T L B}$ rappresenta il tempo di accesso al TLB, mentre $T_{M E M}$ il tempo di accesso alla memoria.

Protezione

Per garantire sicurezza è possibile aggiungere bit di flag alle entry della tabella delle pagine:

bit di validità: alle volte (spesso) un processo non usa tutti gli indirizzi logici del proprio spazio e pertanto alcune pagine rimangono vuote. Questo bit segnala tali pagine, i tentativi di accedere ad esse sono bloccati.
bit di accesso: utilizzabili per marcare una pagina come eseguibile, read-only, read/write, etc. In generale per definire i diritti di accesso.

Pagine Condivise

Possibilità interessante che si apre con la paginazione è la condivisione di pagine fra più processi. Dunque vi è un’unica copia fisica, ma più copie logiche (una per processo). Il requisito è che tali pagine contengano solo codice read-only. Questo meccanismo può essere usato per esempio quando si esegue lo stesso programma più volte con dati diversi. Per esempio, se apro $3$ processi di Word, il 90% del codice viene caricato dalla stessa pagina.

Paginazione multilivello

L'evoluzione dell'hardware ha portato ad un aumento esponenziale dello spazio di indirizzamento logico e di conseguenza anche della dimensione della tabella delle pagine. Per limitare la dimensione e risparmiare spazio in memoria, è possibile adottare una struttura gerarchica per la tabella, ovvero le tabelle portano ad altre tabelle. Inoltre solo alcune parti delle tabelle delle pagine sono memorizzate in memoria, le altre sono su disco. Si deve però tenere conto che ogni livello aggiuntivo richiede un ulteriore accesso in memoria, quindi si limita di solito questo tipo di struttura ad un massimo di due o tre livelli (costo troppo elevato in caso di cache miss nel TLB).

Tabella delle pagine invertita

Altra tecnica pensata per far fronte ai problemi della gestione di page table di grandi dimensioni. Anzichè avere una tabella per ogni singolo processo, si ha un'unica tabella di sistema dove le associazioni sono invertite: non sono più pagina $\to$ frame, ma frame $\to$ pagina, dunque abbiamo un entry per ogni frame. Diventa necessario memorizzare anche il PID del processo che detiene il frame, dunque ogni entry conterrà la coppia <process-id, page-number> e ogni indirizzo logico è una tripla <process-id, page-number, offset>. In generale, con questa tecnica si ha un risparmio di memoria, ma vi è un aumento del tempo necessario per cercare un riferimento ad una pagina. Quindi visto che sarebbe da pazzi usare una ricerca sequenziale, generalmente si opta per usare una tabella di hash che rende il tempo di look-up $O (1)$ . In pratica, è necessario un meccanismo per gestire le collisioni quando diversi indirizzi virtuali corrispondono allo stesso frame. Inoltre, persiste comunque il problema della frammentazione esterna.

Segmentazione

La segmentazione permette la divisione dello spazio di indirizzamento di un processo in segmenti di dimensione variabile, creati dal compilatore. Solitamente questi rispecchiano la visione che ha l'utente del processo, pertanto si avranno, per esempio, un segmento per il codice, uno per i dati, etc.
Similmente alla paginazione, si ha una tabella dei segmenti chiamata segment table che mappa indirizzi logici bidimensionali in indirizzi fisici unidimensionali. Nello specifico, ogni entry contiene una coppia di valori <base, limite>, rappresentanti rispettivamente l'indirizzo di partenza del segmento e la dimensione dello stesso.
Gli indirizzi logici sono formati dal numero di segmento (posizione della entry nella tabella) e dall'offset interno allo stesso. Questo rende immediato il controllo di legalità dell'indirizzo.
Anche qui, come nella paginazione, sono presenti 2 registri contenenti informazioni sulla tabella dei segmenti. Abbiamo il Segment-table base register (STBR) che punta alla locazione della tabella dei segmenti in memoria, e il Segment-table length register (STLR) che indica il numero di segmenti usati da un programma (è obbligatorio, non opzionale). Ovviamente un indirizzo logico <s, d> (dove s è il numero di segmento e d l'offset) è valido se s < STLR, ovvero il suo numero identificativo non può superare il numero totale di segmenti.
Come facciamo invece a recuperare un indirizzo specifico dalla tabella dei segmenti? Basterà sommare STBR, che punta al primo segmento della tabella, a s, ottenendo così l'indirizzo del segmento desiderato. Infine, come per la paginazione, viene usata una cache TLB per memorizzare le entry maggiormente usate.

Esempio

Proviamo ad effettuare una traduzione da indirizzo logico ad indirizzo fisico.
Tabella dei segmenti:

Segmento	Limite	Base
0	600	219
1	14	2300
2	100	90
3	580	1327

Come viene tradotto l'indirizzo logico <0, 430>?
L'indirizzo appartiene al segmento 0 ed ha un offset di 430. L'indirizzo limite è 600 e visto che $430 < 600$ , questo è un indirizzo valido. Pertanto l'indirizzo fisico sarà $430 + base = 430 + 219 = 649$
Come viene tradotto l'indirizzo logico <1, 20>?
L'indirizzo appartiene al segmento 1 ed ha un offset di 20. L'indirizzo limite è 14 e visto che $20 ≰ 14$ , questo non è un indirizzo valido.

Protezione

Per come è strutturata, la segmentazione supporta naturalmente la protezione e la condivisione di codice. Come per la paginazione ad ogni segmento sono associati i bit di bit di accesso (read/write/execute) e i bit di validità (0 ⇒ segmento non legale).

Svantaggi

Uno svantaggio sta nel fatto che il SO deve allocare tutti i segmenti e si può incorrere in frammentazione esterna, visto che i segmenti hanno lunghezza variabile.

Segmentazione paginata

Ancora una volta, la soluzione è combinare i due schemi prendendo i lati positivi di ognuno.
Si arriva così alla segmentazione paginata, cioè una tecnica mista che consiste nel paginare segmenti di memoria.
Nello specifico:

Ogni segmento è suddiviso in pagine
Ogni segmento possiede la sua tabella delle pagine
La tabella dei segmenti non contiene più l’indirizzo base di ogni segmento, ma l’indirizzo base delle tabelle delle pagine per ogni segmento

Si elimina così il problema dell'allocazione e della frammentazione esterna.

È l'indirizzo generato dalla CPU, anche definito come indirizzo virtuale. Gli indirizzi logici sono trattati dai programmi utente, gli indirizzi fisici fanno riferimento alla effettiva posizione del dato nella memoria. ↩︎