Virtual Memory in the IA-64 Linux Kernel | Cerca per titolo, autore, parola chiave | ||||||||
Virtual Memory in the IA-64 Linux Kernel Di Stephane Eranian e David Mosberger, 2002. Tratto da IA-64 Linux Kernel: Design and Implementation. In Linux, i processi vengono eseguiti in un ambiente virtuale, in cui al singlo processo viene assegnato l'intero spazio degli indirizzi di memoria. Lo spazio degli indirizzi virtuali parte dall'indirizzo 0 e arriva all'indirizzo massimo possibile. Su una piattaforma a 32-bit, quale IA-32, l'indirizzo massimo è: 232 - 1 = 0xffffffff Su una piattaforma a 64-bit, quale IA-64, l'indirizzo massimo è: 264 - 1 = 0xffffffffffffffff Esistono almeno tre validi motivi per usare la virtual memory:
La parte sinistra della figura 4.1 illustra lo spazio virtuale degli indirizzi come si presenta ad un determinato processo in una piattaforma a 64-bit. Come si vede dalla figura, lo spazio virtuale degli indirizzi è suddiviso in aree della stessa dimensione, chiamate pagine virtuali (virtual pages). Le pagine virtuali hanno una dimensione fissa, una potenza di 2. Per esempio, IA-32 usa pagine da 4 Kbyte: 4096 byte (212). Per massimizzare le prestazioni, IA-64 supporta molteplici dimensioni di pagina: 4, 8, 16, 64 Kbyte. Nella figura, lo spazio di indirizzi a 64-bit è diviso in sole 16 pagine, così che ciascuna pagina dovrebbe avere una dimensione di: 264 ÷ 16 = 260 byte , pari a ben: 1,152,921,504,606,846,976 byte. Oppure, espresso in esadecimale: 0x1000000000000000 byte. Pagine così grandi, ovviamente, non sono realistiche, ma l'alternativa di disegnare miliardi di pagine, di dimensioni certamente più realistiche, era poco praticabile. Quindi, almeno per questa sezione, continueremo ad illustrare la memoria virtuale con pagine di queste enormi dimensioni. La figura, inoltre, mostra che le pagine sono numerate in modo sequenziale: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 È possibile calcolare il numero della pagina virtuale (virtual page number o VPN) da un indirizzo virtuale dividendo quest'ultimo per la dimensione della pagina (page size) e tenendo solo la parte intera del risultato. Il resto, viene chiamato page offset. Per esempio, dividendo l'indirizzo di memoria virtuale: 0x40000000000003f8 per la dimensione della pagina: 0x1000000000000000 abbiamo 4 con un resto di: 0x3f8 (1016) Quindi, questo indirizzo mappa l'indirizzo virtuale: pagina numero 4, con page offset 0x3f8, vale a dire il byte numero 1016 della pagina numero 4. Prendiamo ora in considerazione la parte destra della figura 4.1, che mostra lo spazio di memoria fisica. Come lo spazio virtuale di memoria, esso è diviso in aree di uguale dimensione, che, nel caso della memoria fisica, si chiamano page frames. Come le pagine virtuali, anche le page frames sono numerate. È possibile calcolare il page frame number (PFN) da un indirizzo fisico dividendo quest'ultimo con le dimensioni del page frame e tenendo solo la parte intera del risultato. Il resto rappresenta il page frame offset. Normalmente, le page frames hanno le stesse dimensioni delle pagine virtuali (virtual pages). A volte, sarebbe comodo avere virtual pages più grandi della page frame (superpages). Così come, a volte, sarebbe comodo suddividere una page frame in multiple virtual pages più piccole (subpages). IA-64 supporterebbe entrambe, ma Linux non le usa. Se da una parte siamo portati a pensare che le page frame occupino una singola regione contigua dello spazio fisico degli indirizzi, non è inusuale incontrare, nello spazio della memoria fisica, dei buchi di memoria (memory holes). Questi buchi possono essere causati dal firmware, dalla presenza di aree dedicate alle periferiche di I/O, oppure, più semplicemente, dalla presenza di aree di memoria non utilizzata. La presenza di questi buchi della memoria comporta che alcune aree di memoria fisica non siano disponibili ad ospitare il contenuto delle virtual pages. Nell'esempio in Figura 4.1, le page frames 2 e 3 rappresentano un buco (hole). È bene ricordare che anche se un solo byte all'interno di una page frame è inutilizzabile, l'intera page frame deve essere marcata come buco (hole). Virtual-to-physical address translation La mappatura (corrispondenza) tra pagine virtuali di memoria e page frames (pagine della memoria fisica) è memorizzata in una struttura di dati chiamata page table (tabella delle pagine). La page table per il nostro esempio è mostrata nella parte sinistra della Figura 4.2. Il kernel Linux è responsabile della creazione e della manutenzione delle page tables, ma si serve di un hardware della CPU, la Memory Management Unit (MMU), per tradurre un indirizzo virtuale di un processo nel corrispondente indirizzo fisico. Nella figura 4.2, abbiamo l'esempio del nostro indirizzo virtuale: 0x40000000000003f8 Coma mostra chiaramente la figura, la MMU estrae la VPN (Virtual Page Number), che noi sappiamo già essere 4, dall'indirizzo virtuale, per poi cercare, all'interno della page table, la corrispondente PFN (Page Frame Number). Nel nostro caso, la ricerca si ferma al primo record della page table, che rivela il numero della PFN: 7. L'MMU quindi ricostruisce l'indirizzo fisico, concatenando la PFN con il frame offset ricavato dall'indirizzo virtuale: 7 0x0000000000003f8 L'indirizzo fisico quindi sarà: 0x70000000000003f8 Se nello spazio virtuale della memoria, quell'indirizzo puntava al byte numero 1016 della pagina 4, nello spazio fisico della memoria quell'indirizzo punta al byte numero 1016 della pagina 7. La prossima questione è: come vengono create le page tables. Linux potrebbe creare i record di una page-table ogni volta in cui un'area di memoria virtuale viene allocata. Tuttavia, questo potrebbe rivelarsi una gran perdita di tempo, visto che i programmi tendono ad allocare molta più memoria di quanta poi useranno. Per esempio, il segmento text di un programma spesso include una gran quantità di codice di gestione degli errori (error handling), che raramente verrà eseguito. Per evitare di buttare via memoria per pagine virtuali che non verranno mai richieste, Linux usa un metodo chiamato demand paging. Con questo metodo, lo spazio virtuale degli indirizzi parte vuoto, nel senso che tutte le pagine virtuali vengono marcate nella page table come non presenti. Quando un processo tenta di accedere ad una pagina virtuale non presente, la CPU genera un errore di pagina (page fault). Il page fault viene intercettato dal kernel, che attiva il gestore dei page fault (fault handler). A questo punto, il kernel può allocare una nuova page frame, determinarne il contenuto (una page frame a zero, una page frame con il codice caricato dalla data section del programma, una page frame con il text segment di un programma), aggiornare la page table per marcare la pagina come presente. L'esecuzione, a questo punto, torna al processo, all'istruzione che aveva generato l'errore (fault). Visto che la pagina richiesta ora è presente, l'istruzione potrà essere eseguita senza generare alcun errore. Paging and swapping Quando ci sono molti processi in esecuzione su un sistema, la memoria fisica può realmente arrivare ad esaurimento. Cosa accade, in Linux, quando c'è bisogno di una page frame, ma la memoria fisica è piena? Ebbene, in questi casi, Linux prende una page frame che è mappata da una virtual page alla quale non è avvenuto recentemente alcun accesso, ne scrive il contenuto in un'area speciale del disco fisso, chiamata swap space, per poi mappare la page frame appena liberata alla nuova virtual page. Naturalmente, la page table del processo al quale Linux ha "rubato" la page frame deve essere aggiornata, marcando il record della page-table come not present. Nello stesso record, viene salvata la locazione su disco in cui è stata copiata la pagina. In altre parole, un record della page-table marcato come presente contiene il numero della page frame fisica che mappa alla virtual page, mentre un record della page-table marcato come not present contiene la locazione su disco fisso alla quale è possibile ritrovare il contenuto della pagina. La marcatura not present genererà un page fault alla prossima richiesta della page frame da parte del processo, spingendo il kernel a riportare la page frame dal disco fisso alla memoria fisica. La tecnica di rubare una pagina ad un processo per scriverla su disco fisso è chiamata paging. Una tecnica simile, ma differente, è lo swapping, una forma molto più aggressiva del paging, nel senso che, in caso di mancanza di memoria fisica, non sposta su disco una sola pagina, bensì tutte le pagine del processo. Linux usa il paging, non lo swapping. Tuttavia, visto che entrambe le tecniche scrivono le pagine nello spazio di swap, molti programmatori tendono ad utilizzare i due termini, "swapping" e "paging" in modo interscambiabile. Il problema critico, in termini di performance, sia per lo swapping, sia per il paging, è come scegliere la pagina da spostare dalla memoria fisica al disco fisso. Il pericolo, infatti, è di scegliere una pagina che dovrà poi essere riportata nella memoria fisica al prossimo accesso alla memoria. Vista l'enorme differenza tra la latenza derivata da un accesso al disco fisso (dell'ordine di diversi millisecondi) e la latenza derivata da un accesso alla memoria (dell'ordine di decine di nanosecondi), fare la scelta giusta potrebbe fare la differenza tra completare un'operazione in pochi secondi o in almeno tre ore! L'algoritmo che determina quale pagina spostare dalla memoria fisica è chiamato replacement policy. Il replacement policy (OPT) ottimale, ovviamente, è scegliere la pagina alla quale si accederà il più tardi possibile, in futuro. Naturalmente, in generale, è impossibile conoscere il futuro comportamento dei processi, così l'OPT ricopre un interesse solo teorico. Un replacement policy che spesso funziona bene, almeno per quanto sia realizzabile un OPT, è il "the least recently used (LRU)", o "il meno recentemente usato". LRU cerca nel passato, non nel futuro, e seleziona la pagina alla quale non è stato richiesto l'accesso per il periodo di tempo più lungo. Sfortunatamente, sebbene potrebbe essere implementato, LRU ha un problema di praticità, perchè richiederebbe la creazione e l'aggiornamento continuo di una struttura di dati (come, per esempio, una lista LRU) per ogni accesso alla memoria fisica. Quindi, il sistema operativo usa una serie di approssimazioni della LRU policy, quali il clock replacement e la not frequently used (NFU) policy. In Linux, il page replacement è ulteriormente complicato dal fatto che il kernel può occupare una quantità variabile (nonpageable) di memoria, per i propri usi. Quando il kernel ha bisogno di una nuova page frame, si trova di fronte a due scelte: prendere una pagina dal kernel, oppure prenderne una da un processo. In altre parole, il kernel ha bisogno non solo di una replacement policy, ma anche di una memory balancing policy, che determini quanta memoria viene usata dai buffer del kernel e quanta è mappata dalle pagine virtuali di memoria (virtual pages). La combinazione page replacement e memory balancing pone un problema complesso, al quale non esiste una soluzione perfetta. Quindi, il kernel Linux usa una serie di euristiche che tendono a lavorare bene, in pratica. Per implementare queste euristiche, il kernel Linux mantiene due bit extra in ciascun record della page-table: l'accessed bit e il dirty bit. L'accessed bit dice al kernel se c'è stato un accesso alla pagina (read, written, executed) dall'ultima volta in cui il bit è stato azzerato (cleared). Il dirty bit dice se la pagina è stata modificata dall'ultima volta in cui è stata creata. Linux usa un kernel thread, chiamato kernel swap daemon: kswapd che, periodicamente, verifica lo stato di questi due bit. Dopo l'ispezione, azzera (clears) l'accessed bit. Se il demone kswapd si accorge che il kernel ha bisogno di memoria, si attiva per liberare le pagine che non sono state usate di recente. Se il dirty bit di una pagina è impostato, diventa necessario scriverne il contenuto sul disco fisso (eseguire il paging), prima di liberare la pagina in memoria. Poichè eseguire un paging ha, in termini di prestazioni, un costo, kswapd preferisce liberare prima le pagine i cui accessed bit e dirty bit sono a zero (cleared). Per definizione, queste pagine non hanno avuto accessi recenti e non richiedono di copiare il contenuto su disco. Protection In un sistema multiutente e multitasking come Linux, molti processi, spesso, eseguono lo stesso programma. Se guardiamo allo spazio virtuale di memoria di ciascuno di questi processi, scopriamo che i processi condividono molte pagine identiche. Inoltre, molte di queste pagine non subiscono modifiche durante l'esecuzine del processo, perchè contengono dati di sola lettura (read-only data) o il text segment del programma, che, ovviamente, non cambia durante l'esecuzione. Ovviamente, avrebbe molto senso sfruttare questa comunanza, usando una sola pagina della memoria fisica per ciascuna delle pagine virtuali che abbiano lo stesso contenuto. Un esempio realistico è illustrato in figura 4.3: le page frames 0, 1, 5 servono contemporaneamente le virtual pages 1, 2, 3 di ben due processi, chiamati bash 1 e bash 2. Mentre abbiamo ben 9 virtual pages in uso, per i due processi, grazie alla condivisione delle pagine, in particolare delle tre pagine contenenti i text segment, nella memoria fisica sono attive solo 6 pagine. Naturalmente, la condivisione delle pagine non potrebbe essere eseguita in sicurezza, se non fossimo in grado di garantire che nessuna delle pagine condivise possa essere modificata. Altrimenti, i cambiamenti apportati da un processo sarebbero visibili anche ai processi concorrenti e questo potrebbe portare a comportamenti imprevedibili da parte di ciascun programma. E qui entrano in gioco i bit dei permessi inseriti nelle pagine. Ogni record della page-table contiene 3 permission bit: R, W, X permission bit. Se un processo tenta un accesso non permesso ad una page frame viene inviata una page protection violation fault, alla quale il kernel risponde, inviando al processo un segmentation violation signal (SIGSEGV). I 3 permission bit della pagina permettono di condividere in sicurezza una page frames. Il kernel deve solo assicurarsi che tutte le pagine virtuali che puntano ad una page frame condivisa abbiano disabilitato il bit di scrittura (the W permission bit). Il segmento text di un programma è il candidato ideale per la condivisione delle page frame, poiché, per definizione, questo segmento può solo essere eseguito, quindi letto, ma mai sovrascritto. Quindi, le pagine contenenti il segmento text di un programma possono essere condivise da tutti i processi che eseguono il programma. Lo stesso vale per le pagine contenenti dati di sola lettura (read-only). Linux va anche oltre: quando un processo esegue un: fork di se stesso, il kernel disabilita il bit di scrittura (write access) in tutte le pagine virtuali (che diventano read-only) e imposta le page tables in modo tale che il processo padre (parent) ed il processo figlio (child) condividano tutte le page frames. Inoltre, il kernel marca tutte le pagine che, prima di questa operazione, erano sovrascrivibili (writable) come copy-on-write (COW). "Copy on write" significa letteralmente: ognuno condivide con gli altri una sola copia dello stesso dato (la pagina, in questo caso), almeno fino a quando qualcuno tenta di modificarlo, caso in cui del dato (della pagina) viene fatta una copia. Con le pagine di memoria, questo significa permetterne la condivisione, creandone una nuova solo in caso di reale modifica. Questa tecnica è particolarmente usata proprio con il: fork che crea un nuovo processo, inizialmente identico al processo padre, di cui condivide tutte le risorse. Solo successivamente, viene eseguito un: exec che assegna nuove risorse, compreso un nuovo spazio di indirizzi, al processo figlio (child process). Se il processo padre o il processo figlio tenta di scrivere in una copy-on-write page, viene sollevata un'eccezione: protection violation fault. A questo punto, invece di inviare un segnale di segmentation violation, il kernel prima fa una copia privata della virtual page, poi ripristina il bit del permesso di scrittura (write permission) di quella pagina. A questo punto, l'esecuzione può tornare al processo che aveva sollevato l'errore, che sarà in grado, ora, di eseguire l'istruzione di scrittura della page. Il page sharing (condivisione delle pagine) qui descritto accade automaticamente, senza che il processo ne sia a conoscenza. Ci sono volte in cui due o più processi desiderano esplicitamente cooperare e condividere alcune pagine virtuali. Linux supporta queste richieste con la system call: mmap() ed il System V shared memory system.
|
|||||||||
Virtual Memory in the IA-64 Linux Kernel | Disclaimer: questo è un link a contenuti ospitati su server esterni. |