Allocazione della memoria (PDF)

SO4 Gabriele Imbrici 1° semestre Allocazione della memoria I moduli di gestione della memoria si differenziano in base al tipo di allocazione della stessa, che può essere contigua o non contigua. Nell’a...

SO4 Gabriele Imbrici 1° semestre Allocazione della memoria I moduli di gestione della memoria si differenziano in base al tipo di allocazione della stessa, che può essere contigua o non contigua. Nell’allocazione contigua la memoria viene allocata in modo che il processo occupi un insieme di locazioni i cui indirizzi siano consecutivi tra di loro. Queste parti di processo saranno poi gestite dal SO. L’allocazione contigua può essere effettuata con approcci diversi, ovvero: Monoallocazione Partizionamento Statico Partizionamento dinamico Segmentazione L’allocazione non contigua consiste nell’allocare la memoria in modo tale che un unico oggetto logico viene posto in aree separate e non adiacenti. Questo approccio può essere utile per caricare solo alcune parti di processo alla volta in memoria, risparmiando cosı̀ spazio. L’allocazione non contigua utilizza la paginazione che permette l’impiego della memoria virtuale. MONOALLOCAZIONE La monoallocazione consiste nel dividere la memoria centrale in due parti contigue, una parte dedi- cata al SO (Monitor) e l’altra dedicata agli altri processi in esecuzione. L’ultima operazione eseguita dal BIOS è il caricamento del SO, per cui è il primo processo a venire caricato e occuperà uno dei due estremi della memoria. Il SO occuperà un certo numero di celle di memoria e dall’ultima cella in poi sarà tutto spazio libero per l’allocazione di altri processi. È necessario che ci sia un registro barriera che indichi la prima/ultima locazione indirizzabile dai processi utente. Se un processo generasse una locazione inferiore/superiore a quell’indirizzo barriera non andrebbe bene, perché verrebbe intaccato lo spazio del SO. Verrà quindi generato un interrupt che manderà in esecuzione il SO che terminerà il processo che ha generato l’indirizzo. Un altro possibile approccio è rendere la parte di SO accessibile in sola lettura, anche se è un ap- proccio poco utilizzato perché è limitativo. Servirà quindi un meccanismo che classifichi le locazioni di memoria in base al loro livello di accesso, ovvero 1 eseguibile, read-only, read-write e cosı̀ via. Questi diritti di accesso possono essere implementati attraverso dei bit di protezione che indicano le op- erazioni eseguibili su quelle locazioni di memoria. Alla richiesta di esecuzione di un programma, il SO si assicura che le dimensioni del processo siano com- patibili con la memoria disponibile, se sı̀ conferisce il controllo al processo utente fino al suo completamento o ad eventuali errori e alla sua terminazione la memoria viene liberata e può essere assegnata ad un altro processo in coda. Può capitare inoltre che venga messa a disposizione una condivisione dei dati attraverso una politica di accordi tra processi, ovvero i dati da condividere vengono scritti su locazioni di memoria che non verranno sovrascritte al cambio di processo, ma è raro perché la monoallocazione viene utilizzata in ambienti mono- programmati. Questo è uno dei più grandi difetti di questo approccio, ovvero non supporta la multiprogrammazione. I processi devono essere ottimizzati per la memoria nella quale risiederanno, cosa che porterebbe a sacri- fici sulle prestazioni, inoltre processi più grandi della memoria disponibile o non potranno essere eseguiti o bisognerà adottare dei metodi particolari per suddividerli (overlay). I suoi costi di progettazione sono però bassi ed è affidabile perché è un sistema semplice ed è gestito da moduli hardware appositi, infatti trova buon impiego nei microcomputer dedicati a specifici compiti. PARTIZIONAMENTO STATICO Il partizionamento statico è la prima possibilità che ci permette di mantenere in memoria più processi (multiprogrammazione). Questo approccio consiste nel prendere lo spazio di memoria libero (quindi non del SO) e dividerlo in diverse regioni con confini fissati (partizioni), all’interno di ognuna delle quali ci sarà un processo. La suddivisione della memoria viene fatta ”fuori linea”, cioè il SO appena viene caricato, prima ancora di mandare in esecuzione qualsiasi processo suddivide la memoria rimasta. Le partizioni possono essere create secondo diverse politiche, ma dipendono in generale dalla capacità della memoria fisica disponibile, dal livello di multiprogrammazione desiderata e dalle dimensioni dei processi più frequentemente eseguiti. Una volta create le partizioni non potranno variare fino al prossimo riavvio del sistema. Le partizioni possono avere dimensioni diverse tra di loro, ma resta il fatto che una volta scelta questa dimensione non potrà cambiare. Il SO, per tenere traccia di tutte le partizioni, utilizza una struttura dati chiamata tabella di descrizione delle partizioni (TDP) e in questa tabella sono contenuti gli at- tributi e lo stato corrente di ogni partizione. L’unico campo variabile in questa tabella è lo stato della partizione che indica se è libera o allocata. Ogni partizione ha un numero identificativo, la propria dimensione e la base, cioè il punto di memoria da cui parte (è un meccanismo simile a base e limite per i processi). Quando un processo richiede di essere allocato in memoria, il sistema verifica se ci sono partizioni libere (consultando la TDP) e se le trova verifica se la partizione è abbastanza grande da contenere il processo. Se il processo può essere allocato in quella partizione, lo stato di quest’ultima viene cambiato da disponibile ad allocata e viene aggiornato l’indirizzo di rilocazione nel processo nel suo PCB con l’indirizzo della prima cella della partizione. Questo può essere un problema nel caso di processi che hanno una dimensione variabile. Quando un processo viene deallocato, semplicemente nella rispettiva partizione di memoria viene cambiato lo stato da allocata a disponibile. 2 I dati del processo ci sono ancora, semplicemente la partizione è stata resa disponibile ad un nuovo processo e i dati vecchi verranno sovrascritti da quelli nuovi. Esistono diverse politiche con la quale si può cercare una partizione in memoria libera per un processo: First Fit: consiste nell’allocare la prima partizione libera sufficientemente larga per contenere il processo. È l’algoritmo di ricerca più veloce perché gli altri prevedono che la scansione continui, ma è sconveniente in termini di efficienza di memoria; Best Fit: questo algoritmo controllerà tutte le partizioni disponibili e assegnerà al processo quella che genera il minor spreco possibile, ovvero la più piccola partizione che può comunque contenerlo. È più lento del First Fit, ma è più efficiente in termini di utilizzo della memoria. Worst Fit: al contrario del Best Fit, questo algoritmo assegnerà al processo la partizione che genera maggior spreco possibile. Unisce i punti deboli del First Fit (poco efficiente a livello di memoria) e del Best Fit (lento). Può essere utile quando la dimensione di un processo potrebbe crescere molto nel tempo, per cui sarà necessario molto più spazio di memoria rispetto a quello iniziale. Il funzionamento del gestore della memoria e dello scheduler sono strettamente collegati. Lo scheduler decide quale dei processi nella coda Ready mandare in esecuzione. Se il processo è in Ready, vuol dire che si trova in memoria centrale. Per determinare quali processi sono pronti per l’esecuzione, quindi, lo scheduler fa uso della tabella delle partizioni: oltre ai campi precedentemente menzionati prima, sarà presente un ulteriore campo contenente il PID del processo che occupa quella partizione (se è allocata). Può anche capitare che il modulo di gestione della memoria sospenda un processo perché in coda New ce n’è uno con priorità più elevata e sarà quindi necessario fare spazio. Un altro caso potrebbe porsi quando non sono disponibili processi in coda Ready e quindi, per impedire che la CPU rimanga in idle, viene fatto lo swap-in di processi pronti ad essere eseguiti. In ogni caso, il modulo di gestione della memoria dovrà informare lo scheduler delle operazioni compiute sui processi, altrimenti c’è il rischio che venga schedulato un processo non più presente in memoria. Se un processo è troppo grande per essere posto in una partizione si possono prendere alcuni approcci per risolvere il problema: Se la dimensione delle partizioni è decisa fuori linea, si può riavviare il sistema chiedendo una partizione di dimensione maggiore; Si implementa il concetto di overlay, ovvero si divide il processo in più moduli che possono trovarsi in memoria centrale in momenti differenti. Questi moduli saranno poi gestiti dal SO, inoltre possono essere in alcuni casi condivisi tra più processi permettendo il risparmio della memoria; Se esiste una partizione in grado di contenere il processo ma è già occupata, si può considerare di fare lo swap-out del processo che la occupa per fare spazio al nuovo processo. Il gestore dello swapping può decidere di quale processo fare lo swapping in base a dimensione della partizione richiesta, priorità, tipo di eventi attesi dal processo e tempo trascorso in memoria dal processo. SWAPPING Per compiere lo swapping, bisognerà salvare alcune informazioni di quel processo per fare in modo che si possa riprendere la sua esecuzione successivamente ripartendo da dove si era fermata. Queste informazioni includono codice eseguibile e ultima istruzione eseguita (da salvare nel PCB), dati già elaborati, stack (da salvare nel PCB), stato del processo (da salvare nel PCB), descrittore del processo e file 3 aperti. Siccome la quantità di dati da spostare NON è piccola, bisogna dedicare una parte dell’Hard Disk come area di swap, nella quale sarà definito un file detto file di swapping. La dimensione di quest’area di swap determina quanti processi potranno essere spostati nell’Hard Disk dalla memoria centrale. Un’area di swap troppo piccola si riempirebbe velocemente e aumenterebbe i tempi di overhead del sistema perché verrebbero richieste operazioni di swapping più frequentemente. In un’area di swapping potrebbe esserci un unico file di swapping contenente tutti i processi, oppure più file di swapping, uno per ogni processo. Nel caso di file unico questo viene creato all’avvio del sistema, è collocato su una periferica di memorizzazione secondaria (ad esempio una SSD, che è anche più veloce) e in genere indirizzo e dimensione sono statici cosı̀ da poter fare uso dell’indirizzamento diretto. Essendo di dimensione fissa c’è un numero limitato di processi che il file può contenere e bisogna scegliere una dimensione adeguata: un file troppo piccolo causerebbe le limitazioni elencate sopra, mentre un file troppo grande sprecherebbe spazio in memoria. Il secondo approccio consiste nel creare un file apposito per ogni processo. Non ci sono restrizioni sul numero di processi attivi, inoltre non c’è il problema della dimensione di un file unico. Gli svantaggi sono i tempi di accesso più lunghi e consumo di spazio maggiore perché diversi file più piccoli usano più spazio di un unico grande file. Uno swapping efficiente richiede che i processi siano rilocabili dinamicamente, perché quando un processo viene swappato non sempre potrà tornare nella stessa area di memoria in cui si trovava preceden- temente. Quindi il processo potrà spostarsi da una parte di memoria all’altra e questo significa che gli indirizzi del processo devono essere di natura rilocabile. I processi devono quindi avere supporto fisico alla rilocazione, operazione che viene effettuata dinami- camente attraverso i registri base (per la rilocazione) e limite (per la protezione). MECCANISMI DI PROTEZIONE Il registro base contiene l’indirizzo più basso del processo e il registro limite contiene il valore dell’indirizzamento virtuale più alto contenuto dal programma. Invece per quanto riguarda la condivisione controllata di dati e codice tra processi cooperanti, il sistemi a partizione fisse basano i propri meccanismi sull’isolamento degli spazi di indirizzamento, ciò comporta una difficoltà di condivisione. Per la condivisione dei dati tra processi esistono alcuni approcci: Affidamento degli oggetti condivisi al SO: ogni parte condivisa viene affidata e gestita al SO. Questo comporta che l’area di memoria del SO cambi dinamicamente e che le routine dei processi utente siano legate al SO per scambiare i dati; Lasciare che ogni processo abbia una propria copia dell’oggetto e diffondere gli aggiorna- menti con gli altri processi. Potrebbe però capitare che uno dei processi che utilizzano quell’oggetto sia stato sospeso e quindi non riceverà gli aggiornamenti; Utilizzare una partizione dedicata per lo scambio di dati. È necessario fare degli accorgimenti sui registri base e limite, specialmente se le partizioni non sono 4  contigue, altrimenti il SO considererebbe qualsiasi accesso a quell’area condivisa come una violazione di memoria. Questo modello non è più utilizzato perché presenta degli svantaggi. Innanzitutto genera frammentazione interna, ovvero nel caso in cui un processo occupi una partizione considerevolmente più piccola dello spazio ad esso necessario ci sarebbe uno spreco di memoria. Se le partizioni non sono abbastanza grandi da ammettere un processo potrebbe essere necessaria l’implementazione di alcuni schemi di overlay. Non c’è supporto per i processi che possono variare dimensione nel tempo, in quanto le partizioni hanno dimensione fissa e infine il livello di multiprogrammazione è dettato dal numero di partizioni decise dal sis- tema, quindi non potrà variare in base alle esigenze. PARTIZIONAMENTO DINAMICO Il partizionamento dinamico funziona analogamente a quello del partizionamento statico ma il gestore della memoria assegna partizioni di memoria di dimensione variabile dinamicamente in base alle richi- este dei processi. Più precisamente il gestore della memoria ricerca una porzione di memoria contigua libera e la partizione viene creata registrando la base, la dimensione e il suo stato nella TDP, la rimanente memoria libera viene rimessa a disposizione. Questa tabella non sarà creata all’avvio del sistema, ma si riempirà dinamicamente man mano che si aggiungono nuove partizioni. Quando un processo termina o avviene una operazione di swapping, il gestore della memoria rilascia lo spazio libero all’insieme di aree di memoria libera e cancella la riga corrispondente nella TDP. L’insieme delle aree libere varia dinamicamente, gli spazi interni all’area libera vengono utilizzati per mantenere una lista a puntatori. Il gestore della memoria può creare e allocare partizioni finché non viene esaurita la memoria fisica o finché non viene raggiunto il massimo grado di multiprogrammazione. Cosı̀ come per il partizionamento dinamico, anche in questo caso ci sono diversi algoritmi per l’assegnazione di una zona di memoria ad un processo, alcuni dei quali seguono gli stessi principi: First-Fit: termina la ricerca quando viene individuato il primo blocco di memoria sufficientemente grande da contenere il processo. Best-Fit: alloca il blocco di memoria libero più piccolo che può contenere il processo. Worst-Fit: alloca il blocco di memoria libero più grande le cui dimensioni superino quelle della partizione richiesta. Next-Fit: ricerca l’allocazione di memoria libera nella lista delle aree libere e il suo puntatore rimane disponibile per le prossime ricerche per risparmiare tempo di ricerca. Qualsiasi algoritmo di selezione delle aree, crea “buchi” di memoria inutilizzati. Questo fenomeno viene detto frammentazione esterna, ovvero la creazione di aree di memoria libere di piccole dimensioni non contigue e impossibilità di allocazione di memoria richiesta da un processo, pur con- tenendo la memoria globalmente un’area di dimensione sufficiente. 5 COMPATTAZIONE Una soluzione è la compattazione della memoria spostando i processi residenti in memoria in modo da creare partizioni libere più grandi. Questa operazione generalmente richiede un grande costo di CPU. La compattazione può essere effettuata: 1. Continuamente: la memoria viene compattata ogni volta che un processo libera un’area la frammentazione è ridotta al minimo questa operazione ha un grande costo di CPU 2. Su necessità: la compattazione viene effettuata quando non si riesce ad allocare memoria ad un processo richiedente un controllo preliminare verifica se il totale dell’area liberabile è sufficiente a contenere il processo Inoltre, la compattazione, può essere effettuata in due modi: Spostamento selettivo incrementale: la compattazione viene eseguita ricercando una strategia di movimento ottimale dei processi per compattare al meglio la memoria. Con questo approccio i processi sono distribuiti su entrambi gli estremi. Cosı̀ facendo è possibile risparmiare tempo negli spostamenti, ma è un approccio poco utilizzato perché spesso il calcolo della strategia ottimale è dispendioso a livello di risorse; Spostamento globale: la compattazione viene eseguita spostando ad uno ad uno i processi su uno dei due estremi della memoria. Lo spostamento non è ottimizzabile ma non richiede strategie particolari. La condivisione dei dati e protezione dei processi avviene in modo analogo al partizionamento statico. Inoltre il partizionamento dinamico permette a due partizioni contigue di sovrapporre un’area di memoria che potranno utilizzare come area condivisa, ma è una forma di condivisione molto restrittiva che può avvenire solo tra due processi. Il partizionamento dinamico quindi: richiede un supporto hardware modesto, analogo al partizionamento statico la differenza tra i due schemi risiede sostanzialmente nel software elimina la frammentazione interna ma produce quella esterna che può essere eliminata con la compat- tazione si adegua ad ambienti con carico non predicibile di lavoro come ad esempio sviluppo di software SEGMENTAZIONE La segmentazione è uno schema di gestione della memoria che si basa sulla divisione dello spazio di indirizzamento dei processi in entità logiche che possono essere poste in aree non contigue di memoria. La segmentazione fornisce strumenti per la rilocazione dinamica, la protezione e la condivisione. Un programma eseguito può essere suddiviso, ad esempio, in codice, dati e stack, ciascuno di questi oggetti può essere posto in un segmento diverso di dimensione differenti. La frammentazione esterna può essere ridotta se la dimensione delle aree richieste è più piccola. 6 Lo schema di gestione della memoria supporta la visione che l’utente ha della memoria, come abbiamo detto, un programma è una collezione di segmenti (che contiene il codice e tutti altri elementi essenziali per la corretta esecuzione del programma). Ciascuno di questi oggetti può essere posto in un segmento diverso di dimensioni differenti ed ogni entità (segmento) è identificata da un nome. Le entità possono essere presenti in memoria anche in maniera non contigua. L’indirizzo logico si compone di due parti, il nome dell’entità (identificativo dal suo numero) e lo scostamento all’interno del segmento. La segmentazione condivide alcune proprietà: Dagli schemi di allocazione contigua: contigua relativamente ad un singolo segmento: i dati di ogni singola entità logica devono essere posti in un’area contigua di memoria. Dagli schemi di allocazione non contigua: relativamente all’intero spazio di indirizzamento del processo, ovvero blocchi logici diversi possono essere messi in segmenti non contigui. La raccolta degli oggetti in segmenti viene predisposta dal programmatore e ciascun segmento inizia all’indirizzo virtuale zero. Ogni elemento ha un nome che viene poi tradotto in un indirizzo in fase di caricamento in memoria. Un singolo dato all’interno del segmento viene identificato dallo “spiazzamento” relativo all’inizio del seg- mento in cui appartiene. L’indirizzamento nella segmentazione è di tipo bidimensionale, la designazione univoca di un dato o di una istruzione richiede il nome del segmento e lo spaziamento all’interno del segmento. La memoria fisica mantiene invece l’indirizzamento lineare: è necessario un meccanismo per la traduzione degli indirizzi bidimensionali di segmenti virtuali in indirizzi fisici. Per caricare un processo segmentato il SO cerca di allocare N partizioni adatte per gli N segmenti in cui è suddiviso il processo e crea un descrittore di segmento registrandovi l’indirizzo fisico in cui è stato posto il segmento e la sua dimensione, infine l’insieme dei descrittori di segmento di un processo viene raccolto nella tabella dei descrittori di segmento, TDS – segment table (La base è l’indirizzo fisico di inizio del segmento in memoria, il limit, specifica la lunghezza del segmento (usato an- che per controllo e protezione da violazioni). Due registri hardware, RBTDS(Registro Base della Tabella dei Descrittori di Segmento) e RLTDS(Registro Limite della Tabella dei Descrittori di Segmento), contengono l’indirizzo di inizio e fine della TDS associata al processo in esecuzione. Ciò consente anche il controllo d’accesso a segmenti non assegnati al processo. La base ed il limite della TDS (di un processo) vengono caricati nei registri RBTDS e RLTDS e quando un processo subisce uno swapping, al ritorno in memoria va aggiornata la sua TDS. Generalmente si preferisce rigenerarla totalmente con la mappa statica fornita dal linker. L’eventuale compattazione richiede l’aggiornamento nella TDS delle righe relative ai segmenti spostati. Se i descrittori di segmento sono pochi o alcuni sono utilizzati molto frequentemente, risulta con- veniente caricarli in registri appositi (ad esempio in cache). Intel, ad esempio, usa registri specifici: Code Segment(segmento contenente il programma), Data Seg- ment (segmento contenente la Symbol Table), Stack Segment (segmento contenente lo stack), Extra Segment (segmenti contenenti informazioni extra). Ad ogni segmento è anche possibile assegnare una modalità di accesso, ad esempio il segmento del codice potrà essere solo eseguito, mentre il segmento della Symbol Table potrà essere sia letto che scritto. I diritti di accesso sono registrati nella segment table. 7 MECCANISMI DI PROTEZIONE La forma più naturale di protezione per un sistema operativo segmentato è l’utilizzo di registri base e limite. La protezione tra spazi di indirizzamento di processi differenti è garantita dalla collocazione dei segmenti in aree disgiunte di memoria. Una caratteristica offerta dai sistemi segmentati consiste nel fornire un livello di protezione all’interno dello spazio di indirizzamento di un singolo processo. È possibile definire diritti e modalità di accesso per ogni “tipo” di segmento. Esempio: accesso in modalità ”execute” (o anche ”read-only”) al segmento codice accesso in modalità ”read/write” al segmento stack accesso ”read/only” o ”read/write” al segmento dati MECCANISMI DI CONDIVISIONE La segmentazione offe una condivisione semplice e flessibile. Gli oggetti condivisi sono collocati in segmenti dedicati e separati. Il segmento condiviso può essere mappato, attraverso la TDS, nello spazio di indirizzamento virtuale di tutti i processi autorizzati ad accedervi. Lo spiazzamento interno di un dato risulta identico per tutti i processi che lo condividono. COLLEGAMENTO DINAMICO Il Collegamento Dinamico indica il caricamento di una procedura, ad esempio una libreria, in fase di esecuzione di un processo e solo su sua richiesta. Lo spazio in memoria per una procedura viene occupato solo se e quando tale procedura viene richi- esta. La segmentazione consente di aggiungere nuovi segmenti al processo richiedente, aggiornando la TDS e i registri base e limite della TDS. CONCLUSIONI La segmentazione permette un’efficienza maggiore nell’utilizzo della memoria centrale perché non è necessario che venga assegnato uno spazio contiguo ad un processo ma, verrà diviso in più segmenti con un significato specifico. Inoltre viene eliminata la frammentazione interna perché si potrà assegnare al segmento la dimensione richiesta, inoltre ha un supporto efficiente per protezione, condivisione e collegamento dinamico. Però presenta alcuni svantaggi. Innanzitutto si incappa nella frammentazione esterna, quindi c’è il rischio di non trovare uno spazio contiguo abbastanza grande per un segmento. La compattazione in questo caso viene anche resa più complessa. Inoltre il duplice accesso alla memoria può potenzialmente rallentare il sistema, per risolvere questo prob- lema ci deve essere un supporto hardware apposito. La gestione della memoria è più complessa rispetto al partizionamento statico e dinamico e infine non è ancora possibile eseguire processi più grandi delle dimensioni fisiche della memoria centrale. 8 PAGINAZIONE Con la paginazione si inizia a vedere un esempio di allocazione non contigua. Questo approccio consiste nel dividere la memoria fisica in “pagine” tutte della stessa dimensione (attual- mente tra i 4KB e gli 8KB), chiamate frame. I processi a loro volta vengono divisi in pagine della stessa dimensione di quelle fisiche, che infatti saranno poi caricate nei frame di memoria. Quando bisogna caricare un processo in memoria, infatti, vengono prelevate le pagine del processo dalla memoria ausiliaria e vengono caricate nelle pagine fisiche (blocchi) della memoria centrale. A differenza della segmentazione, che veniva gestita dal programmatore, la paginazione è gestita dal SO e trasparente al programmatore. Con la paginazione, quando la CPU genera un indirizzo questo è composto da due parti (non è bidi- mensionale): la prima parte (i bit più significativi) indica il numero di pagina logica, mentre la seconda parte (i bit meno significativi) indica il displacement (spiazzamento) all’interno della pagina desiderata. Rispetto alla segmentazione, le pagine hanno una dimensione fissa e uguale tra loro. Questo significa che non sarà possibile generare uno spiazzamento che sia più grande della dimensione della pagina stessa. Il sistema operativo tiene traccia delle corrispondenza tra pagina virtuale e pagine fisiche mediante la tabella delle pagine (TDP) o la page table. La page table viene costruita al momento del caricamento in memoria del processo e contiene l’indirizzo di partenza del frame fisico in cui risiede la rispettiva pagina virtuale. La tabella sarà composta da un numero di righe pari al numero frame di memoria occupati. Ogni processo ha la propria tabella delle pagine. Il numero di pagina logica dovrà essere tradotto con il rispettivo indirizzo del frame fisico occupato in memo- ria, per cui il sistema controllerà la page table del processo corrente per risalire all’indirizzo fisico. Viene cercato l’indirizzo logico generato, una volta trovato si prende il corrispondente indirizzo fisico e si accoda ad esso il displacement, ottenendo cosı̀ l’indirizzo fisico della cella di memoria cercata. Il SO a sua volta possiede la cosiddetta tabella di memoria (TDM) che viene utilizzata per tenere traccia di tutti i frame fisici. Per ogni frame viene indicato se è libero o allocato e il numero di righe della tabella è uguale al numero di frame totali in memoria. Esiste inoltre una tabella dei frame liberi. Quando un processo richiede di essere allocato, il sistema verifica la sua dimensione in pagine e, se ci sono abbastanza frame disponibili, comincia ad allocare nei frame liberi le pagine del processo, aggiornando il loro stato (da libero ad allocato) nella tabella di memoria e aggiungendo una nuova entry nella page table del processo per ognuna delle sue pagine. Quando il processo richiedente ha uno spazio di indirizzamento non multiplo della dimensione delle pagine fisiche, si crea il fenomeno della frammentazione interna della pagina. Questo è comunque un fenomeno molto ridotto e legato alla dimensione della pagina fisica. Nella frammentazione interna, l’ultima pagina assegnata ad un programma non sarà completamente piena. Pagine molto piccole hanno minore frammentazione, carico eccessivo nell’accesso al meccanismo di traduzione degli indirizzi, numerosi accessi alla memoria di massa. Quando un processo termina o subisce uno swapping, restituisce tutte le pagine fisiche ad esso assegnate e la sua TDP viene eliminata. 9 MEMORIZZAZIONE DI AREE LIBERE La consultazione della Tabella di Memoria statica per trovare n pagine fisiche libere richiede una ricerca su un numero di righe che in media è x = n/q. q è la probabilità che una pagina sia libera e si lega alla percentuale di memoria libera u: u q= 0