|
Gestione della memoriaIn informatica, la gestione della memoria è una forma di gestione delle risorse relativa alla memoria dei computer. Lo scopo principale è quello di orchestrare l'allocazione di porzioni della memoria di sistema ai vari programmi che la richiedono. La gestione della memoria è un aspetto critico di ogni sistema di elaborazione che supporta l'esecuzione di più processi contemporaneamente.[1] Gerarchie di memoriaLa grande quantità di dati normalmente presente in un elaboratore è memorizzata su supporti che possono presentare caratteristiche molto diverse tra loro, in termini di tempo di accesso, di capacità e di costo. Tali supporti sono organizzati come una struttura gerarchica in cui al livello più alto troviamo i dispositivi di memoria più lenti, con capacità maggiore e meno costosi; man mano che si scende in questa gerarchia, i supporti hanno capacità sempre più piccola, tempo di accesso sempre più basso e costo maggiore. L'obiettivo che si vuole raggiungere è quello di ottimizzare il rapporto prestazioni/costo, ottenendo, così, prestazioni equiparabili al caso in cui tutte le informazioni necessarie siano disponibili al livello più basso della gerarchia, con un costo paragonabile al caso in cui siano concentrate al livello più alto. In un elaboratore comune una tipica gerarchia di memoria è quella in cui si trova, al livello più alto, il disco fisso, dove le informazioni vengono conservate in maniera permanente; subito dopo si trova la memoria principale (DRAM/SDRAM), di elevata capacità nell'ordine del GB, basso costo e basso tempo di accesso. Qui vengono conservate le informazioni relative ai processi in esecuzione: quando un nuovo processo viene caricato, vi verranno trasferite almeno le informazioni basilari che ne permetteranno la messa in esecuzione. Nel caso tale livello della gerarchia risultasse saturo, verranno adottate politiche di ottimizzazione che possono consistere dalla compattazione della memoria allo swap-out[2] delle pagine, il quale consiste nel trasferimento di informazioni al livello superiore, ossia al disco fisso. Ai livelli inferiori abbiamo la memoria cache; possono esistere più livelli di questo tipo di memoria e vengono normalmente indicati con una serie decrescente di numeri, via via che si scende nella gerarchia. Normalmente il livello cache L1 è “on-chip”, ossia è direttamente presente nella CPU in maniera tale da ridurre fisicamente la latenza dei collegamenti. Il livello più basso della gerarchia è sicuramente rappresentato dai registri del processore[3] il cui tempo di accesso è valutabile in un ciclo di clock[4]. Tecniche di gestione della memoriaUn meccanismo di gestione della memoria può essere individuato da quattro parametri fondamentali, quali:
Fatta eccezione per alcune, ad ogni combinazione di questi quattro fattori corrisponde una tecnica di gestione della memoria. RilocazioneGli indirizzi generati dal processore su cui è in esecuzione un processo sono detti “indirizzi logici” o “virtuali” e fanno riferimento alla memoria virtuale del processo stesso. Tali indirizzi, però, non corrispondono necessariamente agli indirizzi dove sono effettivamente rese disponibili le informazioni cercate, ossia gli “indirizzi fisici”, per questo motivo è necessario che sia messo in atto un meccanismo che consenta di mettere in corrispondenza gli indirizzi logici con gli indirizzi fisici: la rilocazione statica prevede, appunto, che all'atto del caricamento del processo, il “caricatore”, che a questo punto conosce l'area di memoria fisica dove verrà caricata la memoria virtuale dello stesso, provveda a sostituire tutti gli indirizzi logici che possono essere generati, negli indirizzi fisici corrispondenti. Questa politica, se da un lato permette di risparmiare l'eventuale overhead dovuto alla traduzione a runtime degli indirizzi logici, tempo che peraltro verrà speso all'atto del caricamento, dall'altro non è prestante in caso vengano adottate politiche di swapping, in quanto, ogni qual volta verrà fatto lo swap-in[5] di un'area di memoria precedentemente scaricata, potrebbe rendersi necessario effettuare nuovamente la rilocazione di tutti gli indirizzi. Spazio virtualeLa memoria virtuale di un processo in cui sono presenti tutte le informazioni necessarie alla sua esecuzione, come il codice, l'area riservata per lo stack e i dati, può essere strutturata come uno spazio degli indirizzi contiguo, ossia con indirizzi da 0 a N, in cui N rappresenta la dimensione della memoria virtuale, oppure può essere suddivisa in segmenti indipendenti, ad esempio un segmento per il codice, un segmento per lo stack ed infine uno per i dati. Nel secondo caso risulta più naturale il concetto di poter applicare diversi permessi di lettura/scrittura ad ogni segmento. Allocazione della memoria fisicaDefinisce come deve essere scelto lo spazio di memoria fisica da assegnare al processo. Supponendo di essere nel caso di spazio virtuale unico, nel momento in cui questo deve essere caricato in memoria, occorre individuare un'area libera di dimensioni maggiori o uguali a N, dove N rappresenta la dimensione dello spazio degli indirizzi; se, per ipotesi, fossero disponibili diverse aree di dimensioni minori di N, queste non sarebbero selezionabili anche se la somma delle loro dimensioni fosse maggiore o uguale a N. Nel caso di spazio virtuale segmentato il problema è riconducibile a quello prima descritto, in quanto il fenomeno ora non si verificherebbe al livello dell'intero spazio degli indirizzi, ma del singolo segmento, anche se in questo modo aumentano le probabilità di trovare una partizione di dimensione sufficiente, essendo la dimensione del singolo segmento minore rispetto a quello dell'intera memoria virtuale. Il fenomeno appena descritto è definito “frammentazione” e rappresenta un problema di ottimizzazione della gestione della memoria in quanto tende a ridurre l'utilizzazione della stessa. Nei sistemi con rilocazione dinamica il problema della frammentazione può essere risolto con il compattamento della memoria. In questi sistemi, infatti, viene adottata una funzione, detta funzione di rilocazione, che permette di far corrispondere ad ogni indirizzo virtuale l'indirizzo fisico corrispondente; sfruttando questa caratteristica, se venisse richiesta un'area di memoria contigua di dimensione N, ma la memoria risultasse frammentata, le aree libere potrebbero essere compattate in un'unica area di dimensione pari alla somma delle precedenti. Tale modifica non si ripercuoterà sull'esecuzione degli altri processi quando la funzione di rilocazione viene aggiornata al nuovo stato della memoria. Nel caso di rilocazione statica, l'allocazione della memoria fisica deve essere forzatamente contigua; infatti, in questo caso gli indirizzi sono tradotti a tempo di caricamento e ne consegue che ad indirizzi virtuali contigui debbano corrispondere indirizzi fisici contigui. Un chiaro esempio di come non possa essere altrimenti lo si può avere pensando al ciclo fetch-execute[6] del processore, il quale cercherà la prossima istruzione da eseguire all'indirizzo virtuale successivo rispetto a quello dell'istruzione la cui esecuzione si è appena conclusa; se la memoria virtuale non fosse allocata in maniera contigua è evidente che tale modello fallirebbe. Caricamento dello spazio virtualeIndica se lo spazio virtuale deve essere caricato in memoria per intero, copiandolo dal disco alla memoria principale, oppure se ne deve essere caricata solo una parte, eventualmente anche minima, come solo il descrittore di processo. In quest'ultimo caso, quando viene generato un indirizzo logico che fa riferimento ad un'area di memoria virtuale non ancora presente in memoria principale, viene sollevata un'eccezione chiamata page fault, la cui gestione porterà alla copia di quest'ultima in memoria principale. PartizioniPartizioni fisse o variabiliTale tecnica non utilizza meccanismi hardware di supporto alla gestione della memoria (MMU), effettuando la rilocazione statica degli indirizzi virtuali mediante il caricatore rilocante. L'allocazione della memoria fisica viene fatta in maniera continua, lo spazio virtuale è unico e viene caricato tutto insieme. La memoria è suddivisa in N partizioni fisse, ovvero di indirizzo iniziale e dimensioni determinate, di cui una è riservata al sistema operativo mentre le altre sono disponibili ad ospitare lo spazio virtuale dei processi. Quando un processo viene mandato in esecuzione, se vi sono partizioni libere verrà scelta la partizione di dimensione minima tra quelle la cui dimensione è maggiore o uguale alla dimensione dello spazio virtuale del processo stesso; se non esiste una partizione con queste caratteristiche, oppure tutte le partizioni sono occupate, si provvede ad effettuare lo swap-out dello spazio virtuale di un processo, con il vincolo che quando questo dovrà tornare in esecuzione, lo swap-in dovrà essere fatto nella stessa partizione dove prima risiedeva. Tale vincolo è da imputare all'adozione della rilocazione statica. È evidente che la probabilità di trovare partizioni con la stessa dimensione dello spazio virtuale del processo che di volta in volta viene caricato è piuttosto bassa, ne consegue che la differenza tra la dimensione della partizione selezionata e la dimensione della memoria virtuale costituisce un'area di memoria non utilizzata. Considerando singolarmente tali aree, queste possono avere dimensione trascurabile mentre la somma delle loro dimensioni può costituire una porzione considerevole di memoria non utilizzata. Tale inconveniente è detto di “frammentazione interna”. Questo modello di gestione della memoria si presta bene ad allocare dinamicamente memoria ai processi, ossia all'implementazione di politiche di swapping. A questo proposito, per ogni partizione viene tenuta una lista di descrittori di processi, ossia tutti quei processi a cui è stata assegnata quella determinata partizione. Il primo descrittore della lista appartiene al processo correntemente allocato in quella partizione mentre gli altri sono residenti nella swap-area. Periodicamente, seguendo una politica round-robin, la memoria viene revocata al primo processo di ogni partizione, il suo descrittore viene posto in fondo alla lista e la partizione viene assegnata al prossimo processo nella stessa. In conclusione, lo schema a partizioni fisse, grazie alla sua semplicità, richiede un basso overhead per la gestione delle partizioni, tuttavia è da segnalare la totale mancanza di flessibilità dovuta alla dimensione fissata delle partizioni che non possono essere adattate alla dimensione dello spazio virtuale dei processi che di volta in volta vengono caricati. Lo schema di gestione della memoria con partizioni variabili, invece, permette di definire dinamicamente le caratteristiche delle singole partizioni in modo tale che corrispondano alle esigenze dei processi che di volta in volta vengono allocati. Inizialmente tutta la memoria è costituita da un'unica partizione libera di dimensione K; quando viene caricato un nuovo processo con memoria virtuale di dimensione N viene creata una partizione di dimensione esattamente N. A questo punto la memoria risulta divisa in due partizioni: una in cui è allocato il processo suddetto e di dimensione N, l'altra disponibile ad ospitare nuovi processi di dimensioni K-N. Quando un processo termina rilasciando la partizione occupata, non necessariamente si viene a creare una nuova partizione libera. Se l'area di memoria che si viene a liberare è adiacente ad altre partizioni libere vengono compattate tutte in un'unica partizione di dimensione pari alla somma delle stesse. Lo schema di allocazione a partizioni variabili presenta maggiore flessibilità rispetto a quello a partizione fisse; infatti si perde la necessità di definire le partizioni in fase di installazione del sistema, in quanto ad ogni processo viene allocata un'area di memoria di dimensioni esattamente uguali a quelle della memoria virtuale del processo, eliminando così il problema della frammentazione interna. Tuttavia, anche questo schema soffre di un tipo di frammentazione, ossia la “frammentazione esterna”, che si presenta quando le singole partizioni libere sono di dimensione inferiore alla quantità di memoria richiesta, anche se la loro somma è maggiore uguale a quest'ultima. L'adozione di questo schema di allocazione implica la necessità di tenere traccia delle partizioni libere; questo viene fatto organizzando le partizioni come nodi di una lista. Ogni partizione nelle prime due posizioni di memoria indica la sua dimensione e l'indirizzo della successiva partizione libera. Tale lista può essere organizzata secondo due politiche: la prima, “best-fit”, richiede che la lista tenga le partizioni libere in maniera ordinata per dimensioni crescenti. In questo modo, in fase di richiesta di una partizione, si scorre la lista fino a quando non si trova una partizione di dimensioni maggiori o uguali rispetto all'area di memoria richiesta. Una volta trovata la partizione adatta si “ritaglia” ad-hoc per il processo che si sta caricando, andando a creare una nuova partizione libera che andrà a contribuire al fenomeno della frammentazione della memoria, oppure verrà compattata ad eventuali partizioni libere adiacenti. In fase di rilascio la lista deve essere interamente scandita per verificare la presenza di partizioni libere adiacenti per effettuare il compattamento. Una seconda politica di gestione della lista delle partizioni libere è denominata “first-fit” e consiste nel tenere organizzata la lista tenendo le partizioni ordinate sugli indirizzi; è evidente che questo schema è particolarmente efficiente in fase di rilascio, in quanto nella ricerca di partizioni libere adiacenti vengono considerati l'elemento precedente e successivo nella lista. Partizioni multipleQuesto schema, adottabile nel caso di spazio virtuale segmentato, prevede che ad un singolo processo non sia allocata una singola partizione di dimensioni pari allo spazio virtuale del processo, ma un numero uguale al numero dei suoi segmenti. Segmentando lo spazio virtuale, ad esempio nei segmenti "codice", "stack" e "dati", è possibile permettere la condivisione di segmenti tra processi. Pensando, ad esempio, al segmento "codice", possono essere mandati in esecuzione più processi che eseguono lo stesso programma ma su dati diversi; questo schema permette di far condividere il segmento di "codice" in maniera tale da ottimizzare la gestione della memoria. Avendo spezzettato la memoria virtuale del processo in segmenti più piccoli, ridurremmo, pur non eliminandolo, il fenomeno della frammentazione. SegmentazionePer eliminare il fenomeno della frammentazione della memoria sarebbe necessario provvedere al suo compattamento, ma tuttavia ciò non è possibile o meglio non considerabile dal punto di vista dell'efficienza nel caso venga adottata la rilocazione statica degli indirizzi. Adottando, invece, la rilocazione dinamica, ovvero traducendo gli indirizzi logici in indirizzi fisici attraverso un'opportuna funzione di rilocazione eventualmente implementata ad hardware (MMU), possiamo compattare la memoria avendo come unica conseguenza il dover aggiornare tale funzione di rilocazione. Nel caso di memoria virtuale segmentata, la MMU deve contenere tante coppie di registri base/limite, una per ogni segmento in cui la memoria è suddivisa. I registri base/limite di un segmento contengono l'indirizzo fisico base dove il segmento è stato allocato e la sua dimensione di quest'ultimo. Quando il processore genera un indirizzo virtuale viene presa in considerazione la coppia di registri base/limite del segmento a cui l'indirizzo generato appartiene. Se, ad esempio, l'indirizzo viene generato in fase di fetch di un'istruzione, esso farà sicuramente riferimento al segmento "codice". L'indirizzo virtuale a questo punto viene confrontato con il valore contenuto nel registro limite: se il primo è maggiore verrà generata un'eccezione, in quanto l'indirizzo richiesto non appartiene al segmento, altrimenti verrà sommato il valore presente nel registro base, ottenendo l'indirizzo fisico a cui effettivamente l'informazione richiesta è resa disponibile. Questa è una possibile implementazione della funzione di rilocazione. Nel caso in cui la memoria virtuale sia suddivisa nei soli segmenti "codice", "stack" e "dati", è facile individuare, per ogni indirizzo generato dal processore, a quale segmento esso appartiene: se viene generato in fase di prelievo di un'istruzione oppure durante l'esecuzione di istruzioni di salto e/o di salto a sottoprogramma questo apparterrà al segmento "codice"; appartengono al segmento di "stack" tutti gli indirizzi generati durante l'esecuzione di istruzioni di push/pop ed, infine, appartengono al segmento "dati" gli indirizzi generati durante l'esecuzione delle altre istruzioni. Tale schema di allocazione permette anche una più facile realizzazione del meccanismo di swapping, infatti, allo swap-in di un segmento non esiste più il vincolo di doverlo allocare nella stessa partizione occupata prima della revoca, in quanto la scelta di una partizione diversa implica semplicemente l'aggiornamento dei registri base/limite corrispondenti. Il caso appena descritto si limita a considerare che la memoria virtuale sia suddivisa in soli tre segmenti, tuttavia non esiste nessun motivo logico tale da vincolare il linker a fare questa scelta. La memoria virtuale di un processo può essere suddivisa in un numero indeterminato di segmenti semanticamente significativi, eventualmente limitati dall'architettura. Tale passaggio implica due problemi: il primo è di natura logica e consiste nella sopravvenuta impossibilità di determinare “automaticamente” il segmento a cui un indirizzo virtuale generato appartiene. Infatti, se possiamo determinare che un indirizzo generato durante la fase di fetch appartiene al segmento "codice", se esistono più segmenti "codice" non possiamo determinare a quale di questi esattamente appartiene. Il secondo problema è di natura strutturale e deriva dal fatto che il numero di coppie di registri base/limite contenute all'interno della MMU non può essere eccessivamente elevato. Il primo problema viene risolto facendo generare al processore non più il singolo indirizzo logico, ma una coppia <sg, off>, dove sg rappresenta l'indice del segmento e off è l'offset all'interno del segmento. Per quanto riguarda il secondo problema viene introdotta una struttura dati tabellare, mantenuta nell'area di memoria riservata al sistema operativo, detta tabella dei segmenti, i cui record sono costituiti dalla coppia indirizzo base/limite di ogni segmento, spesso indicati come descrittori di segmento. La MMU mantiene solo una coppia di registri denominati rispettivamente STLR (Segment Table Limit Register), che contiene la dimensione della tabella dei segmenti e STBR (Segment Table Base Register), contenente l'indirizzo base della tabella dei segmenti. Quando viene generato un indirizzo virtuale nel formato <sg, off>, la MMU confronta sg con STLR: se il primo risulta maggiore o uguale del secondo viene generata un'eccezione, in quanto si sta facendo riferimento ad un segmento inesistente, altrimenti si accede alla coppia indirizzo base/limite sommando a STBR il valore di sg. Ottenuta tale coppia, si confronta off con il valore indicante la dimensione del segmento; nuovamente, se il primo risulta maggiore o uguale, viene generata un'eccezione, altrimenti al valore indicante l'indirizzo base del segmento viene sommato off, ottenendo quindi l'indirizzo fisico. Il ricorso alla tabella dei segmenti comporta una notevole perdita di efficienza da parte della CPU, infatti, per ogni indirizzo virtuale generato occorre fare due accessi in memoria: uno per ottenere la coppia indirizzo base/limite del segmento a cui tale indirizzo fa riferimento ed uno per accedere effettivamente all'informazione richiesta. Per ovviare a tale problema vengono mantenuti nella MMU un numero variabile (da 4 a 8) di registri associativi; ogni qual volta viene generato un indirizzo virtuale viene verificato prima se il descrittore di segmento a cui l'indirizzo appartiene è contenuto in tale memoria di registri, detta anche TLB (Translation Lookaside Buffer): se è contenuto, la traduzione viene effettuata senza alcun ulteriore accesso in memoria, altrimenti si effettua l'accesso, memorizzando il descrittore di segmento appena recuperato nel TBL, scartando eventualmente quello riferito meno di recente. Tenendo conto del principio di località degli indirizzi, con i pochi registri associativi presenti nella MMU, è possibile tradurre l'80% degli indirizzi senza accedere alla tabella dei segmenti. Questo schema permette di definire politiche più accurate per quanto riguarda la condivisione e la protezione, dando la possibilità di associare ad ogni segmento permessi di lettura/scrittura e condivisione, aggiungendo appositi campi al descrittore di segmento. Segmentazione a domandaLa memoria segmentata fa riferimento ad uno schema che prevede che la memoria virtuale del processo sia caricata per intero in memoria fisica. Ci sono, quindi, due condizioni possibili: una è che il processo, quindi tutti i segmenti che compongono la sua memoria virtuale, sono allocati in memoria, l'altra è che, invece, il processo è stato spostato nella swap-area. A questo punto è necessario aggiungere due nuovi stati a quelli in cui un processo si può trovare (pronto, bloccato, esecuzione), ovvero quelli che corrispondono a "pronto" e "bloccato", ma con spazio virtuale non allocato in memoria. All'atto della chiamata della primitiva swap-out su di un processo che è in stato di "pronto" o "bloccato", il suo stato passa rispettivamente o a "pronto-swapped" o a "bloccato-swapped". Discorso inverso vale se viene invocata la primitiva swap-in su di un processo di cui è stato effettuato lo swap. Il caricamento della memoria virtuale di un processo per intero nella memoria fisica crea un vincolo sulla dimensione della prima; infatti, la somma delle dimensioni di tutti i segmenti che compongono la memoria virtuale di un processo deve essere inferiore alla dimensione complessiva della memoria fisica. Per eliminare questo vincolo possiamo adottare una politica on-demand sulla gestione dei segmenti. Un segmento viene caricato in memoria solo quando viene generato un indirizzo virtuale che gli appartiene; a quel punto viene generata un'eccezione dalla MMU che provvede a comunicare l'evento (segment-fault) al processore, il quale manderà in esecuzione un opportuno handler che, comunicando col gestore della memoria, permetterà di caricare in memoria il segmento richiesto, permettendo di portare a termine il recupero dell'informazione richiesta. Quando viene fatta richiesta di un segmento non presente in memoria, se quest'ultima viene trovata piena, si provvede a spostare nella swap-area uno o più segmenti dello stesso processo oppure di altri processi. Con questa tecnica diventa più prestante la fase di caricamento di un processo, infatti non è più necessario copiare parti della memoria virtuale nella memoria fisica, in quanto questo verrà fatto solo quando sarà richiesto. L'implementazione della segmentazione a domanda prevede che al descrittore di segmento sia aggiunto un campo, di un bit, che indica la presenza o meno del segmento in memoria. Per facilitare l'implementazione di eventuali algoritmi di rimpiazzamento dei segmenti possono essere aggiunti altri campi al descrittore di segmento, come il bit U, che viene settato periodicamente a 0, via software, e settato a 1, via hardware, ogni qual volta viene fatto riferimento al segmento, o il bit M, che indica se il segmento è stato modificato o meno; se M è posto a 0, ovvero il segmento non è stato modificato, non è necessario riscriverlo nella swap-area quando e se questo verrà scelto come segmento da rimpiazzare. Memoria paginataIl problema della frammentazione può essere parzialmente risolto adottando lo schema di memoria segmentata e applicando la tecnica del compattamento che, tuttavia, richiede un overhead non trascurabile. Tale problema si potrebbe risolvere se potessimo allocare in memoria fisica, ad indirizzi non contigui, indirizzi virtuali contigui. Per fare ciò, basterebbe implementare la funzione di rilocazione in maniera tale da far corrispondere ad ogni indirizzo virtuale, l'indirizzo fisico assegnato. Si intuisce subito che tale implementazione consisterebbe in una tabella di corrispondenza di dimensioni esattamente uguali a quelle della memoria virtuale, penalizzando le prestazioni. Occorre, quindi, raggiungere un compromesso, suddividendo lo spazio virtuale in insiemi di indirizzi virtuali tra loro contigui, detti pagine: una pagina va allocata in un'area di memoria contigua, due pagine non devono necessariamente essere allocate in porzioni di memoria tra loro contigue. La funzione di rilocazione è ora realizzabile ricorrendo ad una tabella di corrispondenza tra pagine virtuali e pagine fisiche. Ogni indirizzo virtuale generato è suddiviso in due parti: la prima indica l'indice di pagina virtuale, la seconda l'offset all'interno della pagina. La traduzione dell'indirizzo virtuale in indirizzo fisico ora avviene accedendo alla tabella delle pagine con l'indice di pagina virtuale, in modo da ottenere l'indirizzo base della pagina fisica corrispondente; l'indirizzo fisico si ottiene sommando a quest'ultimo l'offset indicato nell'indirizzo virtuale generato (le pagine virtuali sono allocate in posizioni contigue di memoria fisica). La dimensione della tabella di corrispondenza dipende dal numero di pagine che compongono la memoria virtuale del processo che, a sua volta, dipende dalla dimensione della singola pagina. Supponendo una macchina con indirizzi a 32 bit e dimensione della pagina di 1024 indirizzi, indirizzabili, quindi, con 10 bit, l'offset di pagina sarà indicato nei 10 bit meno significativi dell'indirizzo virtuale; restano 22 bit (i più significativi) che sono disponibili per l'indice di pagina virtuale, con un totale di 2^22 pagine virtuali possibili. È evidente che la tabella delle pagine non sia allocabile nella MMU e quindi deve essere allocata nella memoria fisica, tenendo traccia, in un opportuno registro, dell'indirizzo base della tabella; tale registro è comunemente indicato con l'acronimo RPTP (Registro Puntatore alla Tabella delle Pagine). Per ridurre il numero di accessi alla tabella delle pagine, nella MMU è presente un numero variabile di registri associativi (da 4 a 8) nei quali vengono mantenute le corrispondenze tra le pagine virtuali e le pagine fisiche a cui più recentemente è stato fatto riferimento. La memoria di registri appena definita è anche chiamata TLB (Translation Lookaside Buffer). Nel momento in cui viene generato un indirizzo virtuale, viene controllato se la corrispondenza tra l'indice di pagine virtuale indicato nell'indirizzo generato e l'indice di pagina fisica corrispondente sia presente nel TLB; se tale controllo ha esito positivo, la traduzione dell'indirizzo viene fatta senza alcun ulteriore accesso in memoria, altrimenti si accede alla tabella delle pagine, si effettua la traduzione e solo allora si provvede a recuperare l'informazione desiderata. Il record della tabella delle pagine, recuperato con l'accesso in memoria fatto, viene memorizzato nel TLB, scartando eventualmente quello a cui si è fatto riferimento meno di recente. Il gestore della memoria fisica, a sua volta, mantiene aggiornato l'elenco delle pagine fisiche disponibili, in una propria tabella, dove per ogni elemento viene riportato se la pagina è occupata o meno e, se lo è, l'indice del processo a cui è stata assegnata. Quando un processo deve essere caricato, viene richiesto al gestore della memoria il numero di pagine necessarie a contenerlo; se non sono disponibili un numero sufficiente di pagine fisiche, si provvederà a deallocare pagine virtuali dello stesso processo o di altri processi, provocandone lo swap-out. Un aspetto importante è la dimensione delle pagine. Al diminuire di questa, aumenta la dimensione delle tabella delle pagine; al limite sarà uguale al numero di posizioni della memoria virtuale, rendendo la non contiguità delle posizioni completa. Al crescere della dimensione delle pagine assistiamo nuovamente ad una forma di frammentazione interna che si verificherà sulla pagina fisica che contiene l'ultima pagina virtuale del processo, a meno che la dimensione della memoria virtuale non sia un multiplo di quella delle pagine. Il fenomeno della frammentazione in caso di dimensione della pagine elevata, può verificarsi anche in altri casi: si pensi ad un insieme di dati che un processo vuole condividere, poiché i diritti di accesso e condivisione sono riportati sul descrittore di pagina virtuale e quindi si riferiscono alla singola pagina, tali dati saranno disposti in una pagina a sé stante, sul cui descrittore sarà impostato il flag di condivisione; nuovamente, se la dimensione di tale insieme non sarà un multiplo della dimensione della pagina, si verifica il fenomeno della frammentazione. Per ovviare a questi problemi, occorre individuare un compromesso sulla dimensione delle pagine, i cui valori tipici oscillano tra i 512 byte e i 4 KB. Un ulteriore aspetto riguardante la condivisione consiste nel tener presente che quando due processi condividono strutture dati, all'interno di queste possono essere presenti riferimenti (puntatori) al altre posizioni di memoria; questo dà luogo ad un problema definito come problema dei riferimenti indiretti in strutture dati condivise e può essere risolto in quattro modi:
Paginazione a domandaCon la tecnica della paginazione si ha il vincolo di dover caricare lo spazio virtuale di un processo per intero perché questo sia eseguibile, tuttavia l'adozione di una politica di caricamento di uno spazio virtuale a domanda porta ad una maggiore flessibilità nella gestione della memoria, permettendo di non tenere in memoria parti dello spazio virtuale che magari non verranno neanche mai usate. Tale politica può essere implementata aggiungendo al descrittore di pagina il bit di presenza e altri, per facilitare l'implementazione di algoritmi di rimpiazzamento. Quando viene generato un indirizzo virtuale, la MMU verifica, accedendo alla tabella di rilocazione, se il bit di presenza è settato a uno: la pagina è presente in memoria e l'indirizzo fisico si ottiene sommando all'indice di pagina fisica ricavato, l'offset indicato nell'indirizzo generato. Se il bit di presenza viene trovato a zero, la MMU genera un'eccezione (fault di pagina) che verrà gestita da un opportuno handler che provvederà al caricamento in memoria della pagina virtuale richiesta. Nel caso tutte le pagine fisiche siano occupate si provvederà al rimpiazzamento di una pagina dello stesso processo o di un processo diverso. Lo swap-out delle pagine deve tener conto di un importante aspetto: un processo può essere stato posto in stato di bloccato in quanto sta attendendo il completamento di un trasferimento I/O da un dispositivo alla memoria principale e magari ad un buffer allocato in una pagina fisica X. Tale trasferimento avviene attraverso il canale DMA, il bus I/O infatti non può essere usato da un processo in stato “bloccato” in quanto questo si interfaccia direttamente con la CPU. Se la pagina X viene scelta come pagina da rimpiazzare, copiando il suo contenuto nella swap-area, e associandovi un'altra pagina virtuale, dello stesso o di un diverso processo, il trasferimento I/O andrebbe a creare una situazione inconsistente in quanto la copia sarebbe fatta in posizioni diverse da quelle di destinazione. Per ovviare a tale problema è presente nei descrittori di pagina fisica un ulteriore bit, detto bit di lock, che se posto a 1 indica all'algoritimo di rimpiazzamento delle pagine che quella pagina non può essere scelta. Memoria segmentata e paginataLe tecniche della segmentazione e della paginazione possono sembrare molto simili tra loro ma in realtà sono profondamente diverse. Mentre la prima si propone di suddividere la memoria virtuale in moduli semanticamente significativi ed indipendenti tra di loro, quindi non più concependola come una piatta sequenza di bytes, la seconda, invece, si propone di suddividere la memoria virtuale in insiemi di posizioni, le pagine, senza interessarsi della semantica e in modo da permettere l'allocazione della memoria fisica in maniera non contigua, eliminando così il fenomeno della frammentazione. È possibile definire una tecnica che prevede sia la strutturazione della memoria virtuale in segmenti, sia la suddivisione di ogni segmento in un insieme di pagine. Utilizzando tale tecnica, gli indirizzi virtuali vanno visti come coppie <sg, sc> dove sg rappresenta l'indice del segmento e sc lo scostamento all'interno del segmento. All'atto della traduzione viene recuperato il descrittore di segmento individuato da sg che contiene due campi: base e limite. Il campo base non indica più l'indirizzo base della partizione in cui è stato allocato il segmento desiderato, ma l'indirizzo della tabella delle pagine relativa a quel segmento. Ogni segmento ha una propria tabella delle pagine. Il valore sc viene, a sua volta, suddiviso in due campi: i bit meno significativi costituiscono l'offset all'interno della pagina, mentre quelli più significativi indicano l'indice di pagina virtuale mediante il quale è possibile recuperare il descrittore di pagina virtuale. A questo punto, se si adotta una politica di paging on demand, viene fatto il controllo sul bit di presenza ed eventualmente generato un fault di pagina, altrimenti, sommando all'indirizzo base della pagina fisica, letto dal descrittore appena recuperato, l'offset presente nei bit meno significativi di sc si ottiene l'indirizzo fisico. Note
Bibliografia
Altri progetti
Collegamenti esterni
|
