|
Articolo pubblicato sul n. 53 di MCmicrocomputer (Edizioni Technimedia Srl - Roma) nel giugno 1986
Memoria virtuale, Paginazione, Segmentazione
Questo mese discuteremo sulla gestione della memoria dei
calcolatori, come è ormai costume in questa rubrica, non
troppo mini. Ovvero in che modo un calcolatore
multiprogrammato
Ragioni storiche Agli albori dell'informatica, anni '50, ovviamente nessuno pensava di multiprogrammare un calcolatore. Già era un problema mandare in esecuzione un programma, figuriamoci più d'uno in parallelo. La memoria di tali prototipi era così piccola a causa degli alti costi per bit che solo programmini davvero semplici potevano essere elaborati. A quei tempi non esistevano nemmeno le memorie di massa: si immetteva il programma su supporto cartaceo (schede o nastri perforati) e i risultati dell'elaborazione potevano essere o letti direttamente sulla carta della stampante o tuttalpiù si potevano far perforare nuove schede per usare i risultati del primo calcolo per elaborazioni future. Poi arrivarono i nastri magnetici (nell'informatica) e i primi supporti veloci come dischi e tamburi, grazie ai quali si cominciarono a sfruttare meglio le potenzialità di calcolo di questi sistemi. Le memorie centrali continuavano però a costare molto, tant'è che si pensò di suddividere i programmi più grossi in piccole porzioni da caricare in memoria a turno, a seconda della relativa fetta di programma che in quell'istante doveva essere elaborata. Così il programmatore, conoscendo le dimensioni della memoria del calcolatore, provvedeva ad aggiungere in punti opportuni dei suoi programmi istruzioni tipo "carica questo pezzo", "scarica quest'altro" o roba simile. Tali operazioni dovevano essere usate intelligentemente, pena un appesantimento troppo grave dell'elaborazione, che se andava avanti a carica e scarica di pezzi di memoria centrale in memoria secondaria (e viceversa), portava a tempi di elaborazione troppo lunghi per essere appena sopportabili. Inoltre, un programma scritto per un calcolatore con una certa quantità di memoria difficilmente era trasportabile su un calcolatore compatibile al primo con quantità di memoria diversa, in quanto come minimo bisognava riorganizzare le suddivisioni per ottenere prestazioni accettabili sul secondo sistema. Fu così che nel 1961, in Inghilterra, un gruppo di persone pensò ad una gestione automatica (ossia da parte del sistema) di questo procedimento di togli e metti porzioni di programma. In primo luogo sgravando il programmatore da tale onere e, non meno importante, aumentando la portabilità di un programma da un sistema all'altro, purché ambedue dotati del medesimo automatismo. Nacque così il concetto di... Memoria virtuale Prima di andare avanti vogliamo rispondere a quei lettori che fino a questo momento si sono chiesti cosa centra tutto questo con la multiprogrammazione, e soprattutto a quelli che hanno pensato: "Sì, va bene, ma ora la Ram costa poche migliaia di lire a Kappa...". Il problema non è tanto l'effettiva quantità di memoria di cui un calcolatore dispone, quanto di come questa sia visibile ai vari processi in corso d'esecuzione. Infatti se è vero che moderno un calcolatore può facilmente disporre di qualche megabyte di memoria, è anche vero che su questo possono benissimo "girare" un centinaio di processi e un megabyte diviso 100 può ugualmente essere poco, come ai vecchi tempi. Quello che hanno fatto a Manchester nel 1961 è stato di separare il concetto di spazio logico di memoria da quello di spazio fisico. Cioè: "Caro programmatore, fai conto che la memoria disponibile sia di 64 Kappa, poi come sia possibile fare ciò in 32 non è affar tuo, se la sbriga il sistema". Questo ad esempio se lo spazio fisico di memoria (=€£centrale) sia pari a 32 kappa e vogliamo che i programmi ne vedano il doppio. Il primo approccio che considereremo è detto: Paginazione
Il sistema considera il programma su disco come suddiviso
in 8 pagine da 8 kappa l'una (vedi figura 1.A). Analogamente
vedrà la propria memoria centrale suddivisa in pagine da 8
kappa, questa volta in numero Questo in prima approssimazione. E' importante notare come il sistema agisca in maniera completamente trasparente all'utente che, dal canto suo, può benissimo essere ignaro di tutto ciò. Ad esempio, il programmatore potrebbe riferire nelle prime istruzioni del suo programma alla cella di memoria n.40000. 40000 diviso 8192, 8 kappa, fa 4 col resto 7232: per il sistema il programmatore ha fatto un riferimento alla cella 7232 della pagina logica n.4: se la pagina 4 è già presente in memoria centrale bene, altrimenti bisognerà caricarla da disco. Analogamente, se il processore sta elaborando le istruzioni della prima pagina logica e arrivati in fondo banalmente non vi è un goto a un indirizzo della stessa pagina, il sistema automaticamente caricherà la seconda pagina logica, se questa naturalmente non è già presente in memoria, per proseguire così l'elaborazione.
A questo punto è ovvio che il sistema in ogni momento
deve conoscere un po' di informazioni riguardanti le pagine,
fisiche e logiche. Innanzitutto deve essere al corrente di
quali pagine logiche sono in memoria centrale e dove queste
sono state poste. Se nell'esempio precedente la pagina
logica 4 è stata precedentemente caricata nella pagina
fisica n.2, il riferimento cella 7232 della pagina logica 4
diventa cella 7232
Il sistema dovrà quindi conservare da qualche parte una tabella delle pagine dove mantenere le informazioni che gli servono: per ogni pagina logica si servirà di un descrittore (vedi figg. 2.A e 2.B) che provvederà ad aggiornare man mano che evolverà lo stato della memoria virtuale (nuovi arrivi, modifica alle pagine e così via). A questo punto, scendiamo un po' nei dettagli per vedere più da vicino come avviene la trasformazione dell'indirizzo logico (es. cella 40000) nel corrispondente indirizzo fisico in una delle pagine di memoria centrale del calcolatore preso in esempio. Poniamoci come prima nel caso in cui la pagina logica 4 sia già presente nell'area fisica n.2 a seguito di un precedentemente riferimento. Dicevamo che lo spazio logico indirizzabile ammonta a 64 kappa: ciò vuol dire che per accedere ad una qualsiasi cella delle 65536 possibili occorrerà un indirizzamento a 16 bit, essendo 2 elevato a 16 = 65536.
Torniamo a noi: l'100 (uno-zero-zero, non cento, mi raccomando) prelevato ci servirà per accedere al corrispondente elemento nella tabella delle pagine, mostrata sempre in fig.2A. Lì dentro potremo prelevare la posizione in memoria centrale della pagina logica (10, in decimale 2) e sostituire questo valore al posto dell'100 precedente ottenendo 101110001000000 pari a 23616 in decimale che è la cella fisica corrispondente, nel nostro caso, alla cella logica da cui siamo partiti. Working set Ciò che abbiamo appena descritto è quanto avviene nel caso in cui la pagina di memoria che stiamo riferendo è presente in memoria centrale essendo stata riferita precedentemente. Come già detto, l'informazione circa la presenza o meno in memoria centrale, la troviamo nella tabella delle pagine quando vi accediamo per trasformare l'indirizzo logico in indirizzo fisico con l'algoritmo appena discusso. E' ovvio che può benissimo capitare di non trovare la pagina in memoria e in questo caso occorrerà caricarla da disco per procedere con l'elaborazione. Altrettanto ovvio è che quanto più carichiamo e scarichiamo pagine di memoria tanto più sarà faticoso portare a termine una elaborazione. Nel 1968 Denning (un altro dei "potenti" in informatica) osservò come la maggior parte dei programmi non indirizzino uniformemente tutto lo spazio logico di memoria, ma prevalentemente un certo insieme di pagine detto working set che con l'avanzare dell'elaborazione, tende a stabilizzarsi verso determinati valori. Se quindi il numero delle pagine fisiche disponibili per ospitare pagine logiche di una elaborazione è più grande del workink set del programma, la gestione della memoria virtuale non ci creerà molti problemi in quanto a continui togli e metti. Al contrario se il numero delle pagine è inferiore al working set del programma, potremo rassegnarci all'idea di assistere a molto movimento memoria-disco prima di vedere terminata l'elaborazione. Tornando ai calcolatori multiprogrammati, possiamo ora notare come non sia arbitrario il numero di programmi mantenibili contemporaneamente in memoria: infatti essendo questa, sebbene grande, per definizione non illimitata, caricando troppi programmi dovremmo destinare ad ognuno di questi via via sempre un numero inferiore di pagine che oltrepassato il limite minimo del working set di ciascuno, come detto, farebbe degradare troppo le prestazioni dell'intero sistema. Fate largo Il terzo ed ultimo problema riguarda l'eventualità di non avere spazio disponibile in memoria centrale per caricare la nuova pagina richiesta: occorre scegliere una pagina da scartare per fare posto al nuovo arrivo. Sceglierne una a caso certamente non sarà una buona idea anche perché se siamo sfortunati potremmo essere costretti a ricaricarla in memoria subito dopo. Anche per questo problema non esistono soluzioni ottime in assoluto ma si basano tanto per cambiare su osservazioni probabilistiche. Una prima idea potrebbe essere quella di scartare la pagina meno recentemente usata ossia quella che da più tempo non è stata riferita: con buone probabilità tale pagina non ci servirà più. Tale algoritmo detto LRU (Last-Recently-Used) non è molto agevole da implementare in quanto occorre tenere traccia dei riferimenti fatti alle pagine mantenute in memoria. Un altro algoritmo detto FIFO (First-In-First-Out) come dice il suo nome semplicemente scarta la pagina che da più tempo risiede in memoria, indipendentemente dai riferimenti ad essa fatti nell'ultimo intervallo di tempo. In ogni caso, sia l'uno che l'altro possono miseramente fallire sotto alcune ipotesi: vediamo un piccolo esempio. Immaginiamo di disporre di otto pagine in memoria centrale e che il nostro programma ne occupi nove (di logiche, naturalmente). Sia il caso, inoltre, che il nostro programma è composto semplicemente un grosso loop: si tratta di eseguire di filato le nove paginate di istruzioni e l'ultima istruzione è un goto all'inizio del programma. La sequenza di eventi sarà questa:
e così via caricando e scaricando fino al termine dell'elaborazione. Cosa è successo? Semplicemente il working set del nostro programma era di nove pagine secche e noi ne avevamo disponibili solo otto: con LRU e FIFO non potevamo aspettarci di meglio. Segmentazione Un'alternativa alla gestione della memoria virtuale appena vista, è la segmantazione. La differenza fondamentale tra i due metodi riguarda la lunghezza delle singole porzioni di memoria occupate, che nel primo caso ha dimensione fissa (es.: 8 kappa) mentre con la segmentazione viene allocato di volta in volta uno spazio di lunghezza variabile, a seconda di quanto effettivamente ne serve. Infatti, nell'esempio precedente, se il programma in questione invece di essere lungo 64 kappa fosse stato lungo 60, l'ultima delle sue 8 pagine sarebbe ovviamente piena solo per metà nonostante il sistema allocasse in memoria centrale sempre 8 kappa, per qualsiasi pagina. D'altro canto, come vedremo, la segmentazione è un po' più pesante da implementare, in particolare per la gestione degli spazi vuoti, se si vuole godere di tutti i suoi benefici. La lunghezza dei singoli segmenti, come detto prima, dipenderà dal caso: ad esempio possiamo allocare un segmento della lunghezza del programma principale, altri segmenti per i singoli sottoprogrammi, ancora allocheremo segmenti per le strutture dati, tutti ovviamente saranno presenti in memoria solo quando servono, per non occupare inutilmente spazio. Anche per la segmentazione, abbiamo il problema di trasformare indirizzamenti logici (coppie segmento-posizione in questo) in indirizzi fisici (essenzialmente una ben precisa locazione della memoria), solo che in questo caso il giochetto di prima non è più applicabile proprio per l'arbitrarietà della posizione di inizio e della lunghezza dei segmenti stessi. Ci avvarremo di una memoria associativa ad alta velocità, detta cache memory, tramite la quale partendo dal segmeto otteniamo l'indirizzo di inizio dello stesso in memoria e sommandoci la posizione relativa che ci interessa otteniamo l'indirizzo fisico. Per fare un esempio, immaginamo di dover indirizzare la locazione 100 del segmento n.3. Supponiamo inoltre che tale segmento sia già presente in memoria centrale a partire dalla locazione 2000. Passando 3 alla memoria associativa questa ci restituirà l'inizio del terzo segmento (2000), basterà sommarci 100 per ottenere 2100 che è l'indirizzo fisico corrispondente dunque alla cella cercata. Oltre a tutto questo, come prima, abbiamo i problemi riguadanti il carico e lo scarico dei segmenti nonché l'onere di ricercare lo spazio necessario prima dell'operazione di caricamento.
Si parte, naturalmente, con la memoria completamente libera come mostrato in fig. 4.A. Carichiamo in memoria un primo segmento: fig.4.B; immaginiamo di caricare allo stesso modo altri segmenti necessari all'elaborazione del primo: la situazione è mostrata in fig. 4.C, al momento l'unico spazio libero rimasto sono le 1000 celle a fine memoria. Supponiamo a questo punto che il segmento 2 non serva più e il sistema decida di scaricarlo rendendo libero lo spazio corrispondente. L'evoluzione procede poi con l'allocazione di 900 celle per il segmento 5, fig.4.E, la deallocazione dello spazio corrispondente al segmento 1, fig.4.F, poi del segmento 5, fig.4.G, lasciando la memoria come indicato in fig.4.H, dopo aver scaricato anche il segmento 3. Ovviamente il sistema dovrà essere a conoscenza dello stato della memoria, prima di caricare qualcosa da disco. Un modo per descrivere tale stato, è quello di tenere traccia degli spazi liberi tramite una opportuna lista: un elenco delle posizioni degli spazi vuoti con relativa lunghezza di ognuno di questi.
Strategie di allocazione La lista degli spazi vuoti è usata dal sistema in tre casi: quando occorre trovare lo spazio per caricare un nuovo segmento, dopo aver caricato un segmento ( e quindi lo spazio libero è diminuito) o dopo aver liberato spazio a causa di un rilascio. Per quanto riguarda il primo di questi tre punti, come per la paginazione possono presentarsi due altre eventualità: spazio disponibile e non. Ad esempio, per continuare l'elaborazione, potrebbe essere necessario il segmento 34, non presente in memoria centrale. D'altra parte, se non disponiamo di spazio a sufficienza (e il sistema può accorgersi di ciò consultando la lista "liberi") occorrerà scaricare qualche segmento, magari uno di quelli che è stato usato meno nell'ultimo intervallo di tempo. Ancora, potrebbe verificarsi il caso in cui lo spazio in memoria ci sia, ma sparso un po' qua, un po' là in modo da non permettere un'allocazione contigua: in condizioni simili, generalmente non vengono scaricati altri segmenti, ma appositi algoritmi ricompattano la memoria, in modo da concentrare i "vuoti" in coda o in testa per poi caricare in quella zona il segmento ricercato. Ultimo problema: posto che vi sia spazio a sufficienza ossia che la lista "liberi" sia ben nutrita e con molti tagli anche più grandi del segmento che dobbiamo caricare, come scelgo la zona di memoria da occupare€£? Esistono essenzialmente tre algoritmi: il primo, first fit, scorrendo la lista alloca il primo spazio che trova sufficientemente capiente per contenere il segmento. Dà ottimi risultati, proprio per la sua intrinseca semplicità, specialmente se ricerche successive non ricominciano da inizio lista, ma ciclicamente scorrono questa a partire dall'ultima allocazione fatta: ciò permette di non concentrare pezzettini piccoli, non utilizzabili direttamente, in testa alla memoria. Un secondo algoritmo, best fit, scorre tutte le volte l'intera lista per trovare il vuoto più piccolo capace di contenere il segmento richiesto: se abbiamo la fortuna di trovare spazi esattamente lunghi quanto il segmento sfrutteremo certamente bene la memoria, ma se ciò non avviene (e di solito è così) inevitabilente aggiungeremo ogni volta nuovi vuoti piccoli che certamente non fanno piacere. Complementare a questo, l'algoritmo worst fit, cerca il segmento più lungo che c'è in modo da lasciare conseguentemente anche un nuovo vuoto abbastanza grande quindi con ottime probabilità di essere adoperato in futuro.
Bibliografia: "Structured Computer Organization" Prentice-Hall, 1976
A.N. Habermann: "Introduction to Operating System Design" Science Research Associates, 1976 Impaginato originale...
Articolo pubblicato su www.digiTANTO.it - per ulteriori informazioni clicca qui |
di 4 essendo disponibili solo
32768 byte (figura 1.B). Dando RUN al programma, si carica
in memoria la prima pagina da disco nella prima pagina
fisica e si inizia l'elaborazione. Se in tale porzione di
programma si riferisce a una cella non compresa nei primi 8
kappa, occorre caricare da disco la pagina corrispondente
che ad esempio verrà posta nella seconda pagina in memoria
centrale. Posto che non vi sia più spazio occorrerà
crearlo scaricando una pagina da memoria a disco, per fare
largo al nuovo arrivo. Così via fino a completamento
dell'esecuzione.
della pagina fisica 2 che è poi quella
che ci interessa. Analogamente, delle pagine non caricate in
memoria deve conoscere dove queste siano locate su disco, ad
esempio traccia e settore. Un'altra informazione utile
potrebbe riguardare il fatto se una pagina sia stata
modificata o meno dall'elaborazione del programma stesso.
Questo può essere utile quando dobbiamo fare posto in
memoria centrale per caricare una nuova pagina: se la
vecchia non è stata modificata, non bisognerà scaricarla
su disco dato che una copia perfettamente identica sarà
già lì presente. Generalmente le pagine che contengono
solo istruzioni non sono modificate dall'elaborazione,
mentre quelle contenenti dati è più probabile che debbano
essere scaricate su disco a causa di modifiche avvenute
durante l'elaborazione.
40000 in notazione binaria, come mostrato anche in fig.3
è 1001110001000000: le prime tre cifre binarie (a
cominciare da sinistra) di tale numero rappresenta il numero
della pagina virtuale (100) che in decimale diventa 4. Le
rimanenti 13 cifre rappresentano invece la posizione
all'interno della pagina, nel nostro caso 7232. Come questo
sia possibile è assai semplice: 8192, la dimensione di una
pagina, è proprio una potenza di 2, quindi il quoziente e
il resto di tale divisione si ottiene semplicemente
guardando il numero binario da dividere. Se non vi torna,
come già detto nel primo articolo di Appunti di
Informatica, è solo perché avete paura dei numeri binari,
tutto qui. Essi sono isomorfi ai numeri naturali in base 10
che sappiamo ben manipolare sin dal tempo delle elementari:
prendiamo un numero decimale qualsiasi, 1234567 ad esempio e
proviamo a dividerlo per 10000, questa volta ovviamente una
potenza di 10: un coro unanime urlerà 123 col resto di
4567, semplicemente guardando il dividendo.
Passiamo ora a considerare la figura 4: come indica la
didascalia rappresenta un esempio di evoluzione, col passare
del tempo, di memoria virtuale gestita con segmentazione,
avendo disponibili solo 8000 celle di memoria centrale.
Inoltre tale lista dovrà essere manipolata
intelligentemente, se non si vuole arrivare ben presto alla
paralisi completa di tutto il sistema. Per esempio, tornando
alla figura 4.F notiamo che sono presenti tre spazi: uno di
1000 celle all'inizio, uno di 600 celle a partire dalla
posizione 1900 e uno di 1000 celle in fondo. Scaricando il
segmento 5, come mostrato in figura 4.G gli spazi liberi non
passano da 3 a 4 ma, badaben-badaben-badaben, diventano 2,
il primo lungo 2500 celle, il secondo come prima di 1000
celle in fondo alla memoria. Per completezza, in figura 5 è
mostrata le liste degli spazi vuoti corrispondenti alle otto
situazioni di memoria mostrate in figura 4.
