La memoria virtuale con esercizio di rilocazione paginata

La memoria virtuale con esercizio di rilocazione paginata

La memoria virtuale, in informatica, è un’architettura che permette di “ingannare” il software utilizzando (per esempio) parte di un HDD (hard disk) per rendere virtualmente illimitata la quantità di memoria allocabile. Ci sono due principi che regolano la gestione della memoria virtuale:

  • Principio di località temporale: È probabile che locazioni di memoria usate recentemente siano riutilizzate molto presto (ad esempio: i cicli).
  • Principio di località spaziale: Se indirizziamo un certo indirizzo di memoria, è probabile che venga indirizzato un indirizzo vicino ad esso (ad esempio: le strutture di tipo vettoriale)

Il vantaggio principale della memoria virtuale è il fatto che, in base a questi due principi, è possibile mantenere solo le parti necessarie del programma in RAM ed è possibile scaricare su disco le parti inutilizzate se la memoria centrale disponibile sta finendo. I due principi sopra elencati sono fondamentali perchè il programma deve sembrare immediatamente accessibile agli occhi dell’utente, anche se non è caricato interamente in memoria. Infatti il meccanismo della memoria virtuale prevede lo swapping, ovvero il passaggio di un blocco di memoria dalla memoria centrale alla porzione su disco dedicata alla memoria virtuale e viceversa. Questo passaggio ha in ogni caso un costo per quanto riguarda risorse e (soprattutto) tempo.

Gestione virtuale paginata

La porzione del disco dedicata alla memoria virtuale, la RAM e il programma vengono divisi in pagine di una determinata dimensione, che saranno usati come blocco minimo per l’allocazione. La tabella delle pagine strutturata in questo modo:

  • Numero di pagina fisica
  • Bit di presenza
  • Numero di pagina logica
  • Istante di referenziazione

Se dobbiamo accedere ad un istruzione successiva di un programma, si controlla se la pagina corrispondente all’indirizzo è stata già copiata in una pagina fisica. Se così non è viene generato il cosidetto page fault. In tal caso viene cercata una pagina disponibile per memorizzare quella mancante. Se non ce ne sono (come per esempio la memoria piena) viene una liberata una pagina con uno di questi criteri:

  • FIFO (First In First Out): Viene eliminata dalla memoria la pagina che, tra quelle presenti, è stata caricata per prima. Produce mediamente un’alto numero di page fault e può rivelarsi lenta quando una pagina viene usata frequentemente (questa diventerà sempre la più vecchia e quindi sarà continuamente eliminata e ricaricata).
  • LRU (Least Recently Used): Elimina la pagina che non è stata referenziata da più tempo, in base al principio di località temporale. Quest’algoritmo è più efficiente rispetto all’algoritmo FIFO, ma presenta un maggiore overhead, dovuto all’algoritmo usato per trovare la pagina più vecchia. Si fa infatti riferimento all’istante di referenziazione presente nella tabella delle pagine. La pagina con istante minore viene rimossa per far spazio a quella nuova. È quindi necessario scorrere tutte le pagine per trovare quella con istante minore, e ciò provoca l’overhead. Si può anche usare una lista per la gestione di questo metodo di rimozione della pagina: ogni volta che si fa riferimento ad una pagina la si sposta alla testa della lista e se c’è bisogno di swappare una pagina si elimina la pagina in coda alla lista. In questo caso l’overhead è dovuto alla gestione della lista.
  • NRU (Not Recently Used): Elimina una pagina che non è stata referenziata da tempo, ma non importa che sia per forza quella utilizzata da meno tempo.

Gestione virtuale segmentata

Dividendo il programma in segmenti, a differenza delle pagine, possiamo evitare di spezzare su blocchi consecutivi, per esempio, una funzione. Questo problema sparisce appena usiamo i segmenti. Il loro utilizzo si avvicina al partizionamento dinamico.

Gestione virtuale segmentata-paginata

Questa tecnica è equivalente alla tecnica di tipo segmentato. I segmenti sono a loro volta divisi in pagine di uguale dimensione. I vantaggi e gli svantaggi sono quelli della paginazione e della segmentazione messi insieme: abbiamo un meccanismo flessibile, ma ricompare ancora una volta la frammentazione dovuta al page breakage.

Esercizio di rilocazione paginata

Supponiamo di avere una certa dimensione di RAM, HDD e pagine.

HDD=128 byte   

RAM =32 byte   

Pagina=16 byte

Troviamo il numero di bit necessari per indirizzare totalmente RAM e HDD. Troviamo quindi la potenza di 2 pari alla grandezza.

HDD=128 byte=27 byte –> 7 bit per l ‘ indirizzamento dell’intero

HDD RAM =32 byte=25 byte –> 5 bit per l ‘ indirizzamento dell’intera RAM

Se ci viene fornito il PC (Program Counter) al posto dell’HDD, il suo numero di bit sarà l’esponente da dare a 2 per ottenere la grandezza dell’HDD (e viceversa), e quindi il suo numero di bit corrisponderà a quelli necessari per indirizzare completamente l’HDD.

Quindi, un generico indirizzo di memoria logico (in HDD) e fisico (in RAM) sarà nella forma:

HDD : XXXXXXX <– Sono 7 bit

RAM : XXXXX <– Sono 5 bit

Trovando la potenza di 2 pari alla grandezza della pagina:

Pagina=16 byte=24 byte –> 4 bit per l ‘ indirizzamento all’interno della pagina

Vedremo che i primi 4 bit presi da destra indicano l’offset, ovvero un qualsiasi byte che sarà indirizzato nella pagina (che sia essa fisica o logica) indicata nella parte sinistra.

L’indirizzo generico quindi diventa:

HDD : XXXYYYY RAM : XYYYY

L’offset (indicato dalle Y) non cambia!

Se per esempio dobbiamo rilocare l’indirizzo logico 24, procediamo convertendo tale numero in binario, ottenendo 11000. Gli indirizzi generici diventeranno:

HDD : 001∣1000

RAM : X1000

Essendo n = Numero Bit Indirizzamento in RAM – Offset (ovvero i bit che possono cambiare in un indirizzo fisico), l’indirizzo logico 24 potrà essere rilocato nei vari 2n indirizzi fisici disponibili, ovvero un indirizzo il cui offset sarà sempre uguale e il cambiamento d’indirizzo sarà determinato dalle varie combinazioni di 0 ed 1 nella restante parte dell’indirizzo fisico.

In questo caso il 24, date quelle determinate dimensioni di RAM, HDD e pagina, potrà essere rilocato negli indirizzi fisici:

  • 0 1000 –>(8)10
  • 1 1000 –>(24)10

Quindi, come abbiamo detto in precedenza, la relazione tra pagine logiche è pagine fisiche è mantenuta dalla tabella delle pagine. Essa avrà tante colonne quante sono le pagine nello spazio d’indirizzamento logico, ovvero 2n,con n = Numero bit indirizzamento in HDD – Offset.

La memoria virtuale con esercizio di rilocazione paginata

Se per esempio l’indirizzo logico 24 viene rilocato nell’indirizzo fisico 8, la tabella delle pagine sarà così:

Indirizzo di Pagina Logica Bit di Presenza Indirizzo di Pagina Fisica Istante
000
001 1 0 X
010
011
100
101
110
111

Se l’indirizzo fisico rilocato fosse stato il 24, l’indirizzo di pagina fisica ovviamente sarebbe stato 1. Tornando alla rilocazione del 24 nell’8, la tabella delle pagine indica che tutti i 16 byte della seconda (001) pagina logica sono stati rilocati nella prima (0) pagina fisica, perchè la pagina è usata come blocco unitario (vedi l’immagine precedente). La seguente tabella descrive questa rilocazione. Come vediamo i primi 3 bit dell’indirizzo logico ed il primo bit (da sinistra) dell’indirizzo fisico non variano perchè, come detto prima, quei bit identificano una singola pagina. Questa tabella conterrà 16 righe, tante quante sono i byte che corrispondono ad una pagina.

Indirizzo logico Indirizzo fisico
001 0000 16 0 0000 0
001 0001 17 0 0001 1
001 0010 18 0 0010 2
001 0011 19 0 0011 3
001 0100 20 0 0100’ì 4
001 0101 21 0 0101 5
001 0110 22 0 0110 6
001 0111 23 0 0111 7
001 1000 24 0 1000 8
001 1001 25 0 1001 9
001 1010 26 0 1010 10
001 1011 27 0 1011 11
001 1100 28 0 1100 12
001 1101 29 0 1101 13
001 1110 30 0 1110 14
001 1111 31 0 1111

15

Precedente Definizione di Array e Matrici in informatica con implementazione in C Successivo Definizione di Lista in informatica con implementazione in C

Lascia un commento

*