Memoria centrale - allocazione contigua, paginazione e segmentazione

Questa nota spiega come il sistema operativo assegna la memoria centrale (main memory, RAM) ai processi e come l'hardware, la MMU (Memory-Management Unit), traduce gli indirizzi. Il caso in cui un processo non sta tutto in memoria è in Memoria virtuale - paginazione su richiesta e sostituzione delle pagineLa memoria virtuale separa la memoria logica da quella fisica: basta che alcune pagine siano in RAM; con la paginazione su richiesta (demand paging) una pagina si carica solo al primo riferimento, e un riferimento a una pagina non residente (bit di validità = i) genera un page fault gestito dal sistema operativo in sei passi; EAT = (1 - p) * accesso + p * servizio del fault, con p minuscolo; copy-on-write rende economica la fork; se non ci sono frame liberi si sceglie una vittima con FIFO (anomalia di Belady), OPT (ottimo, irrealizzabile), LRU (algoritmo a stack), second chance (bit di riferimento, orologio) o la versione con bit di modifica; i frame si assegnano in modo uguale o proporzionale, con sostituzione globale o locale; se un processo non ha abbastanza frame va in thrashing; il modello del working set e la frequenza dei page fault lo evitano; considerazioni su prepaging, dimensione della pagina, TLB reach e struttura dei programmi; memoria del kernel con buddy system e slab.Memoria virtuale - paginazione su richiesta e sostituzione delle pagine →. La gerarchia registri, cache, RAM e il principio di località sono in Gerarchia di memoria e principio di localitàCaratteristiche delle memorie (posizione, capacità, unità di trasferimento, metodo di accesso, prestazioni, volatilità); compromesso costo-capacità-velocità e gerarchia a livelli; località temporale e spaziale con esempi; hit, miss e tempo medio di accesso con calcolo svolto.Gerarchia di memoria e principio di località → e Memoria cacheBlocchi, linee ed etichette; scomposizione dell'indirizzo; associazione diretta, completamente associativa e associativa a insiemi con calcolo dei campi; politiche di rimpiazzo (LRU, FIFO, casuale); politiche di scrittura (write-through, write-back con bit sporco, write-allocate); dimensione del blocco; cache multilivello e separate; come ridurre i miss; quesiti sui campi dell'indirizzo.Memoria cache →.

Perché serve una gestione della memoria

La CPU può eseguire solo istruzioni che si trovano nei registri, nella cache o in memoria centrale: la memoria vede solo un flusso di indirizzi con richieste di lettura, oppure indirizzi con dati da scrivere. Un accesso ai registri costa meno di un ciclo di clock, uno alla memoria centrale può costare molti cicli e la CPU resta in attesa (stall); la cache sta in mezzo per nascondere questo ritardo.

Il programma sta sul disco e deve essere portato in memoria per girare (vedi Processi - stati, PCB, creazione con fork ed execUn processo è un programma in esecuzione (entità attiva) con codice (text), dati globali, heap, stack e lo stato dell'esecuzione; il kernel lo descrive con il PCB (Process Control Block: stato, program counter, registri, informazioni di scheduling, memoria, accounting, file aperti, in Linux la struct task_struct) e passa da un processo all'altro con il context switch (puro overhead); gli stati sono new, ready, running, waiting, terminated, con una ready queue e varie wait queue; in UNIX fork() crea un figlio copia del padre (restituisce 0 al figlio e il pid del figlio al padre), exec() sostituisce il programma del figlio, wait()/waitpid() raccoglie lo stato di uscita: senza di essa un figlio terminato è uno zombie, un figlio il cui padre è morto è un orfano adottato da init/systemd; i processi cooperanti comunicano con memoria condivisa (POSIX shm) o scambio di messaggi (diretto o indiretto, sincrono o asincrono, buffer a capacità zero, limitata, illimitata) e con pipe ordinarie (padre-figlio, unidirezionali) e named pipe (FIFO).Processi - stati, PCB, creazione con fork ed exec →). Con più processi in memoria nasce il problema della protezione: un processo deve poter accedere solo ai propri indirizzi.

Registri base e limite

Una protezione semplice usa una coppia di registri.

Definizione (registri base e limite). Il registro base contiene il più piccolo indirizzo fisico legale del processo, il registro limite la dimensione dell'intervallo. L'accesso all'indirizzo $a$ è legale se $\text{base}\le a<\text{base}+\text{limite}$.

L'hardware controlla ogni accesso generato in modalità utente. Se l'indirizzo è fuori intervallo, si ha un trap al sistema operativo (errore fatale per il processo). Le istruzioni che caricano base e limite sono privilegiate: solo il kernel (in modalità kernel) può cambiarle, altrimenti un processo potrebbe allargare il proprio intervallo. Vedi InterruptClassi di interruzioni; I/O guidato da interrupt; sequenza hardware e software di gestione con salvataggio del contesto sullo stack; identificazione della sorgente (linee multiple, polling, daisy chain, vettore); priorità e interruzioni annidate; eccezioni e modi in ARM.Interrupt → per il meccanismo del trap.

Indirizzi logici e fisici

Associazione degli indirizzi (address binding)

Un programma non può essere sempre caricato all'indirizzo 0 (il primo processo sì, gli altri no). Gli indirizzi cambiano forma durante la vita del programma:

• nel codice sorgente sono simbolici (conta, main);
• il compilatore li trasforma in indirizzi rilocabili, per esempio "14 byte dopo l'inizio di questo modulo";
• il linker o il loader li associano a indirizzi assoluti (per esempio 74014).

Questa associazione può avvenire in tre momenti:

Definizione (indirizzo logico e fisico). L'indirizzo logico (o virtuale) è quello generato dalla CPU; l'indirizzo fisico è quello visto dall'unità di memoria. Coincidono con l'associazione in compilazione e in caricamento, differiscono con quella in esecuzione. L'insieme degli indirizzi logici di un programma è il suo spazio degli indirizzi logici, quello dei corrispondenti fisici è il suo spazio degli indirizzi fisici.

La MMU e il registro di rilocazione

La MMU è la parte dell'hardware che traduce a ogni accesso, in esecuzione, l'indirizzo logico in fisico. Un tempo era un componente separato, oggi è dentro la CPU. Il caso più semplice generalizza i registri base e limite: il registro base diventa registro di rilocazione e il suo valore si somma a ogni indirizzo logico quando questo esce verso la memoria.

Esempio. Registro di rilocazione 14000, limite 3000. L'indirizzo logico 346 diventa $14000+346=14346$. L'indirizzo logico 3500 è $\ge 3000$: trap.

Il programma lavora solo con indirizzi logici e non vede mai quelli reali. Il riferimento fisico viene deciso solo nel momento dell'accesso.

Caricamento dinamico

Con l'associazione in esecuzione si può fare il caricamento dinamico (dynamic loading): una routine non viene caricata finché non è chiamata. Il programma principale parte subito; le routine rare (gestione di errori, casi insoliti) non occupano memoria se non servono. Il sistema operativo non deve fare nulla di speciale: spetta al programmatore progettare il programma in questo modo, oppure alle librerie condivise.

Allocazione contigua

L'allocazione contigua è il metodo dei primi sistemi: la memoria si divide in due parti, una per il sistema operativo (di solito negli indirizzi bassi, dove stanno i vettori delle interruzioni) e una per i processi, e ogni processo occupa una sola sezione contigua. La protezione si ottiene con i registri di rilocazione e limite: il registro di rilocazione contiene il più piccolo indirizzo fisico, il limite l'intervallo degli indirizzi logici, ciascuno dei quali deve essere minore del limite. La MMU traduce in modo dinamico, e questo permette al sistema operativo di cambiare dimensione (per esempio un driver caricato solo quando serve).

Partizioni fisse e variabili

• Partizioni fisse: la memoria è divisa in aree di dimensione prestabilita, una per il sistema operativo e le altre per i processi, anche di dimensioni diverse (una più grande per i processi grossi). Sono facili da gestire, ma il grado di multiprogrammazione è limitato dal numero di partizioni, e un processo molto grande può non starci.
• Partizioni variabili: ogni processo riceve esattamente quanto chiede. La memoria libera forma buchi (holes) sparsi; quando un processo arriva, si cerca un buco abbastanza grande; quando un processo termina, la sua partizione si libera e i buchi adiacenti si fondono. Il sistema operativo tiene l'elenco delle partizioni occupate e dei buchi.

Come scegliere il buco (problema dell'allocazione dinamica)

Per soddisfare una richiesta di $n$ byte da un elenco di buchi liberi:

First fit e best fit sono migliori di worst fit per velocità e occupazione. Un esempio svolto con i diagrammi della memoria è in Esercizio - Allocazione contigua con first fit, best fit, worst fit e next fit (eserciziario, esercizi 35, 36, 54, 55, 102 e 115).

Esempio. Buchi liberi (in KB, nell'ordine): 8, 15, 3, 11, 5, 7, 20, 25. Arriva una richiesta di 11 KB. First fit prende 15 (il primo che basta, resto 4); best fit prende 11 (resto 0); worst fit prende 25 (resto 14).

Frammentazione

Definizione. La frammentazione interna è la memoria assegnata a un processo ma non usata, interna alla sua partizione (tipica delle partizioni fisse e della paginazione). La frammentazione esterna è la memoria libera totale sufficiente a una richiesta, ma divisa in buchi troppo piccoli, non contigui (tipica delle partizioni variabili).

La regola del 50 per cento (analisi di first fit): dati $N$ blocchi assegnati, ne vanno persi per frammentazione circa $0{,}5N$. Quindi circa un terzo della memoria può restare inutilizzabile.

La frammentazione esterna si cura con la compattazione (compaction): si spostano i contenuti della memoria per riunire tutta la memoria libera in un solo blocco. È possibile solo se la rilocazione è dinamica (cioè in esecuzione: basta cambiare il registro di rilocazione dopo lo spostamento) ed è costosa perché copia molta memoria. L'altra cura è non richiedere contiguità: la paginazione.

Paginazione

Definizione (paginazione). La memoria fisica è divisa in blocchi di dimensione fissa chiamati frame (cornici), la memoria logica in blocchi della stessa dimensione chiamati pagine. Un processo di $N$ pagine, per girare, occupa $N$ frame liberi, ovunque si trovino: lo spazio fisico di un processo è non contiguo. La dimensione è una potenza di 2.

Il sistema deve tenere traccia di tutti i frame liberi e, per ogni processo, una tabella delle pagine (page table) che dice in quale frame si trova ogni pagina. Questo elimina la frammentazione esterna e il problema dei buchi.

Traduzione dell'indirizzo

L'indirizzo logico di $m$ bit, con pagine di $2^n$ byte, si divide in due campi:

• $p$ indicizza la tabella delle pagine, che contiene l'indirizzo base (numero di frame) di ogni pagina;
• $d$ si somma alla base per ottenere l'indirizzo fisico: l'offset non cambia nella traduzione.

Se il frame $f$ è la base della pagina $p$, l'indirizzo fisico è $f\cdot 2^n+d$.

Esempio (slide, $m=4$, $n=2$). Pagine da 4 byte, memoria fisica da 32 byte (8 frame). Lo spazio logico ha $2^4=16$ byte, cioè $2^{m-n}=4$ pagine. Il byte b ha indirizzo logico 1, cioè 00 01: $p=0$, $d=1$. Se la tabella dice che la pagina 0 sta nel frame 5, l'indirizzo fisico è $5\cdot4+1=21$, come nella slide. Se invece la pagina 3 sta nel frame 2, l'indirizzo logico 13 (11 01, $p=3$, $d=1$) diventa $2\cdot4+1=9$.

Esempio ($m=16$, $n=12$). Pagine da 4 KB: 4 bit di numero di pagina (16 pagine), 12 bit di offset. Un programma di 100 000 byte occupa $\lceil 100000/4096\rceil=25$ pagine, quindi ha bisogno di 25 frame.

La traduzione passo per passo e le dimensioni dei campi sono negli esercizi Esercizio - Traduzione degli indirizzi con la tabella delle pagine (eserciziario, esercizi 34, 37, 59, 62 e 86) e Esercizio - Dimensioni di page table e indirizzi, paginazione a più livelli (eserciziario, esercizi 66, 67, 69, 72, 76, 81, 82, 93 e 100).

Frammentazione interna e dimensione delle pagine

Il processo occupa un numero intero di frame, quindi l'ultimo frame è in parte vuoto.

Esempio (slide). Pagine da 2048 byte, processo da 72 766 byte: $72766=35\cdot2048+1086$, servono 36 pagine; l'ultima usa 1086 byte, e lo spreco è $2048-1086=962$ byte.

Caso peggiore: $\text{frame}-1$ byte sprecati. In media, mezzo frame per processo. Sembrerebbe quindi che pagine piccole siano meglio; ma ogni riga della tabella occupa memoria e un trasferimento da disco è più efficiente se grande. Le dimensioni sono perciò cresciute col tempo (oggi 4 KB e oltre; la maggior parte dei sistemi ne offre più di una).

Implementazione della tabella delle pagine

La tabella può essere molto grande, quindi sta in memoria centrale:

• il PTBR (page-table base register) punta all'inizio della tabella del processo in esecuzione;
• il PTLR (page-table length register) ne dice la lunghezza; un riferimento oltre il limite è un errore.

Al cambio di contesto si ricaricano PTBR e PTLR del nuovo processo (vedi Processi - stati, PCB, creazione con fork ed execUn processo è un programma in esecuzione (entità attiva) con codice (text), dati globali, heap, stack e lo stato dell'esecuzione; il kernel lo descrive con il PCB (Process Control Block: stato, program counter, registri, informazioni di scheduling, memoria, accounting, file aperti, in Linux la struct task_struct) e passa da un processo all'altro con il context switch (puro overhead); gli stati sono new, ready, running, waiting, terminated, con una ready queue e varie wait queue; in UNIX fork() crea un figlio copia del padre (restituisce 0 al figlio e il pid del figlio al padre), exec() sostituisce il programma del figlio, wait()/waitpid() raccoglie lo stato di uscita: senza di essa un figlio terminato è uno zombie, un figlio il cui padre è morto è un orfano adottato da init/systemd; i processi cooperanti comunicano con memoria condivisa (POSIX shm) o scambio di messaggi (diretto o indiretto, sincrono o asincrono, buffer a capacità zero, limitata, illimitata) e con pipe ordinarie (padre-figlio, unidirezionali) e named pipe (FIFO).Processi - stati, PCB, creazione con fork ed exec →).

Con questa organizzazione ogni accesso a dati o istruzioni richiede due accessi alla memoria: uno alla tabella per trovare il frame e uno al dato. Il problema si attenua con una piccola cache associativa dedicata, il TLB.

TLB (translation look-aside buffer)

Definizione (TLB). Il TLB è una memoria associativa veloce che conserva le coppie (numero di pagina, numero di frame) usate di recente. La ricerca avviene in parallelo su tutte le righe. Se $p$ è nel TLB (TLB hit) si ottiene subito il frame; altrimenti (TLB miss) si legge la tabella in memoria e si carica la riga nel TLB, eventualmente sostituendone un'altra.

Dettagli (confronta con la Memoria cacheBlocchi, linee ed etichette; scomposizione dell'indirizzo; associazione diretta, completamente associativa e associativa a insiemi con calcolo dei campi; politiche di rimpiazzo (LRU, FIFO, casuale); politiche di scrittura (write-through, write-back con bit sporco, write-allocate); dimensione del blocco; cache multilivello e separate; come ridurre i miss; quesiti sui campi dell'indirizzo.Memoria cache →):

• il TLB è piccolo: da 64 a 1024 righe;
• alcune righe possono essere "bloccate" (wired down) per avere accesso sempre veloce;
• alcuni TLB memorizzano in ogni riga un ASID (address-space identifier) che identifica il processo e protegge gli spazi degli indirizzi; senza ASID il TLB va svuotato a ogni cambio di contesto, altrimenti il nuovo processo userebbe le traduzioni del vecchio.

Tempo di accesso effettivo (EAT)

Definizione (hit ratio e EAT). Il hit ratio $h$ è la frazione di accessi in cui la pagina si trova nel TLB. Se un accesso alla memoria costa $t$, il tempo di accesso effettivo è

$$\text{EAT}=h\cdot t+(1-h)\cdot 2t.$$

Se si conta anche il tempo $\tau$ di ricerca nel TLB: $\text{EAT}=h\,(\tau+t)+(1-h)\,(\tau+2t)$.

Esempio (slide). $t=10$ ns. Con $h=0{,}80$: $\text{EAT}=0{,}8\cdot10+0{,}2\cdot20=12$ ns, cioè il 20% in più. Con $h=0{,}99$: $0{,}99\cdot10+0{,}01\cdot20=10{,}1$ ns, solo l'1% in più.

Altre esercitazioni di calcolo sul TLB sono in Esercizio - Tempo di accesso effettivo con TLB e page fault (eserciziario, esercizi 32, 70 e 118).

Protezione e condivisione

• A ogni riga della tabella si associano bit di protezione (sola lettura, lettura e scrittura, solo esecuzione).
• Il bit di validità (valid-invalid) dice se la pagina appartiene allo spazio logico del processo (valida) o no (non valida). Un riferimento a una pagina non valida produce un trap al kernel. In alternativa si usa il PTLR.
• Pagine condivise: una sola copia di codice rientrante (reentrant, non si modifica mai) può essere condivisa tra processi, per esempio un editor di testo, un compilatore, le librerie. Più righe di tabelle diverse puntano allo stesso frame; è simile ai thread che condividono lo spazio del processo, e se si condividono pagine in lettura e scrittura serve per la comunicazione tra processi (un caso pratico sono i file mappati in memoria, in Sistemi di I-O e memory-mapped I-OIl sistema operativo nasconde la varietà dei dispositivi con driver e un'interfaccia uniforme (dispositivi a blocchi, a caratteri, di rete, timer, ioctl); l'hardware è fatto di porte, bus e controller con registri di dato, stato e controllo, indirizzati con istruzioni di I/O dedicate o con il memory-mapped I/O; la CPU comunica con il dispositivo con il polling (busy wait, adatto a dispositivi veloci), con le interruzioni (linea IRQ, vettore, priorità, mascherabili) o con il DMA (trasferimenti di blocchi senza CPU, un'interruzione alla fine); le chiamate possono essere bloccanti, non bloccanti o asincrone; le istruzioni di I/O sono privilegiate e si passa dalle system call; il kernel gestisce errori, buffer e protezione; mmap() mappa un file nello spazio di indirizzi di un processo: accesso con load e store, caricamento pigro con il demand paging, meno chiamate di sistema e meno copie, condivisione con MAP_SHARED.Sistemi di I-O e memory-mapped I-O →).

Struttura della tabella delle pagine

Una tabella semplice può essere enorme. Con indirizzi logici di 32 bit e pagine da 4 KB ($2^{12}$): $2^{32}/2^{12}=2^{20}\approx1$ milione di righe; con 4 byte a riga sono 4 MB per ogni processo, e non si vuole allocare tutto contiguo in memoria. Tre soluzioni.

Tabelle gerarchiche (a più livelli)

Si pagina la tabella delle pagine. Con due livelli (forward-mapped) e indirizzo a 32 bit con pagine da 4 KB, il numero di pagina da 20 bit si divide in due campi da 10:

La tabella esterna ha $2^{10}$ righe da 4 byte, cioè 4 KB: esattamente un frame. Ogni tabella interna è anche di 4 KB. Si allocano solo le tabelle interne che servono: per un processo piccolo bastano la tabella esterna e poche interne. Costo: un accesso in più alla memoria per livello.

Con indirizzi a 64 bit due livelli non bastano: con pagine da 4 KB le righe sono $2^{64-12}=2^{52}$; con tabella interna da $2^{10}$ righe, l'esterna avrebbe $2^{42}$ righe, troppo grande. Si può aggiungere un terzo livello, ma anche la seconda tabella esterna sarebbe di $2^{32}\cdot4$ byte $=16$ GB, e servirebbero 4 accessi alla memoria per un indirizzo.

Tabelle hash

Comuni con spazi oltre i 32 bit. Il numero di pagina virtuale è passato a una funzione di hash (vedi Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash →); ogni posizione contiene una catena di elementi con lo stesso hash. Ogni elemento contiene: numero di pagina, frame, puntatore al successivo. Si scorre la catena cercando la pagina. La variante a gruppi (clustered) fa riferire ogni riga a un gruppo di pagine (per esempio 16), indicizzate dai bit meno significativi del numero di pagina: è un ibrido tra hash e gerarchica.

Tabella delle pagine invertita

Una sola tabella per tutto il sistema, con una riga per ogni frame fisico: contiene la pagina logica che vi è caricata e l'identità del processo proprietario (pid). Riduce molto la memoria per le tabelle, ma aumenta il tempo di ricerca (bisogna cercare la coppia pid, pagina in tutta la tabella). Una tabella hash dell'invertita limita la ricerca a una o poche righe.

Esempio (esercizio 82). Indirizzi virtuali di 21 bit, fisici di 16 bit, pagine da 2 KB $=2^{11}$: la tabella normale ha $2^{21-11}=2^{10}=1024$ righe; l'invertita ha $2^{16-11}=2^5=32$ righe (una per frame); la memoria fisica massima è $2^{16}=64$ KB.

Swapping

Se la memoria non basta per tutti i processi, si usa un'area su disco (backing store, di solito un disco veloce, ad accesso diretto e non attraverso il file system). Un processo può essere scaricato (swapped out) temporaneamente e poi ricaricato (swapped in): lo spazio totale dei processi può superare la memoria fisica.

Il cambio di contesto diventa lento. Se la memoria è piena e il processo scelto dallo scheduler non è in memoria, bisogna scaricarne uno e caricare quello.

Esempio (slide). Processo da 100 MB, disco a 50 MB/s: scaricarlo costa $100/50=2$ s, ricaricare un processo della stessa dimensione altri 2 s: 4 s per un solo cambio di contesto, oltre al tempo normale di scheduling (vedi Scheduling della CPU - FCFS, SJF, priorità e round robinLo scheduler della CPU sceglie tra i processi pronti quello a cui dare il core (il dispatcher esegue il cambio, con latenza di dispatch); lo scheduling è non preemptive (il processo tiene la CPU finché termina o si blocca) o preemptive (la CPU gli può essere tolta, con rischio di race condition); i criteri sono utilizzo della CPU e throughput (da massimizzare), tempo di attesa, di turnaround (completamento meno arrivo) e di risposta (da minimizzare); FCFS è semplice ma soffre dell'effetto convoglio (esempio 24, 3, 3: attesa media 17 contro 3); SJF è ottimo per l'attesa media ma richiede la lunghezza del prossimo burst, stimata con la media esponenziale tau(n+1) = alfa t(n) + (1-alfa) tau(n); SRTF è la versione preemptive (esempio con attesa media 6,5 contro 7,75); round robin dà a ciascuno un quanto q e nessuno attende più di (n-1)q; la priorità causa starvation, risolta con l'aging; code multilivello e a feedback (MLFQ) combinano le politiche.Scheduling della CPU - FCFS, SJF, priorità e round robin →). Il tempo dipende dalle prestazioni del disco, vedi Memoria di massa e scheduling del discoLa memoria di massa è fatta di dischi rigidi (HDD: piatti, tracce, cilindri, settori) e memorie non volatili NAND (SSD); tempo di accesso HDD = seek + latenza rotazionale (mezzo giro, 30/RPM secondi), tempo di I/O = accesso + trasferimento + overhead del controller; i blocchi sono indirizzati con un LBA lineare; per l'HDD si minimizza il seek con FCFS, SSTF (rischio di starvation), SCAN (ascensore) e C-SCAN (più uniforme), con le varianti LOOK e C-LOOK e il deadline di Linux; per le NVM contano FTL, garbage collection, overprovisioning e wear leveling; il sistema operativo formatta (fisico e logico), partiziona, gestisce il boot e lo spazio di swap; parità ed ECC rilevano e correggono errori; il RAID usa striping, mirroring e parità (livelli 0, 1, 4, 5, 6, 10) per più velocità e affidabilità, con MTTDL = 1/PDL.Memoria di massa e scheduling del disco →.

Linux e Windows usano una variante: si scaricano singole pagine invece di processi interi. Questa tecnica, che permette di sovraccaricare la memoria senza il costo dello swap intero, si chiama paginazione su richiesta (demand paging) ed è l'argomento di Memoria virtuale - paginazione su richiesta e sostituzione delle pagineLa memoria virtuale separa la memoria logica da quella fisica: basta che alcune pagine siano in RAM; con la paginazione su richiesta (demand paging) una pagina si carica solo al primo riferimento, e un riferimento a una pagina non residente (bit di validità = i) genera un page fault gestito dal sistema operativo in sei passi; EAT = (1 - p) * accesso + p * servizio del fault, con p minuscolo; copy-on-write rende economica la fork; se non ci sono frame liberi si sceglie una vittima con FIFO (anomalia di Belady), OPT (ottimo, irrealizzabile), LRU (algoritmo a stack), second chance (bit di riferimento, orologio) o la versione con bit di modifica; i frame si assegnano in modo uguale o proporzionale, con sostituzione globale o locale; se un processo non ha abbastanza frame va in thrashing; il modello del working set e la frequenza dei page fault lo evitano; considerazioni su prepaging, dimensione della pagina, TLB reach e struttura dei programmi; memoria del kernel con buddy system e slab.Memoria virtuale - paginazione su richiesta e sostituzione delle pagine →. Il termine swapping indica di solito quello "standard", a processi interi.

Segmentazione

Invece di pagine uguali si divide il processo in segmenti di lunghezza variabile, che riflettono la struttura logica del programma: codice, dati globali, ogni funzione, stack, heap, tabella dei simboli.

Definizione (segmentazione). L'indirizzo logico è una coppia $\langle s, d\rangle$: numero di segmento e scostamento. La tabella dei segmenti ha per ogni segmento una base (indirizzo fisico dell'inizio) e un limite (lunghezza). Si controlla $d<\text{limite}_s$; se vale, l'indirizzo fisico è $\text{base}_s+d$; altrimenti c'è un trap (errore di segmentazione).

Esempio (esercizio 90). Tabella: segmento 0 base 219 limite 600; segmento 1 base 2300 limite 14. L'indirizzo $\langle 0,430\rangle$ è valido ($430<600$) e vale $219+430=649$; $\langle 1,10\rangle$ vale $2300+10=2310$; un riferimento $\langle 1,20\rangle$ sarebbe illegale ($20\ge14$).

Pro: protezione e condivisione per segmento (il codice sola lettura è un segmento). Contro: ha frammentazione esterna (segmenti di lunghezza variabile, stessa situazione delle partizioni variabili). Esercizi: Esercizio - Segmentazione e traduzione degli indirizzi (eserciziario, esercizi 49, 78 e 90).

Segmentazione con paginazione

Per togliere la frammentazione esterna si pagina ogni segmento: l'utente definisce i segmenti, e il gestore della memoria li divide in pagine. L'indirizzo ha tre parti: segmento (che indicizza un segment descriptor che punta alla tabella delle pagine di quel segmento), pagina (che indicizza il frame in quella tabella) e scostamento.

Architetture Intel

IA-32 (32 bit)

Segmentazione con paginazione:

• ogni segmento può essere lungo 4 GB, e un processo ha fino a 16 K segmenti, divisi in due gruppi: i primi 8 K sono privati del processo e stanno nella LDT (local descriptor table), gli altri 8 K sono condivisi e stanno nella GDT (global descriptor table);
• la CPU genera un indirizzo logico (selettore più offset); l'unità di segmentazione usa il selettore per scegliere la riga della LDT o della GDT (che contiene base e limite), controlla il limite (altrimenti trap) e produce un indirizzo lineare da 32 bit; l'unità di paginazione lo traduce nell'indirizzo fisico. Le due unità insieme sono la MMU;
• paginazione a due livelli (10+10+12 bit): i 10 bit più alti indicizzano la page directory, il cui indirizzo sta nel registro CR3 del processo corrente; la riga punta alla tabella interna indicizzata dai 10 bit successivi; gli ultimi 12 sono l'offset nella pagina da 4 KB;
• un flag nella page directory permette pagine da 4 MB: la riga punta direttamente al frame da 4 MB e i 22 bit meno significativi sono l'offset.

IA-64 (64 bit)

L'architettura attuale usa in pratica 48 bit per gli indirizzi (oltre 16 exabyte sono troppi): pagine da 4 KB, 2 MB o 1 GB e quattro livelli di paginazione (9 bit per livello: $4\cdot9+12=48$).

Lo spazio di un processo in C

Come un programma C usa lo spazio virtuale (codice, dati statici, heap che cresce verso l'alto, stack che cresce verso il basso) è in Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →; l'uso di indirizzi e puntatori è in Puntatori in CUn puntatore contiene un indirizzo di memoria; operatori & e *, NULL, puntatori come parametri per modificare variabili del chiamante, aritmetica dei puntatori, legame tra array e puntatori, const, puntatori a puntatori.Puntatori in C →. Il buco tra heap e stack non occupa memoria fisica finché non cresce. La stessa memoria virtuale, vista dall'architettura, è in Memoria virtualeIndirizzi virtuali e fisici, pagine e frame; traduzione con la tabella delle pagine e calcolo dei campi; page fault e sostituzione delle pagine; TLB e tempo di accesso effettivo; protezione e condivisione; confronto con la cache.Memoria virtuale →.

Domande d'esame

1. Differenza tra frammentazione interna ed esterna e come si risolvono. Interna: spazio inutilizzato dentro una partizione o un frame (paginazione: in media mezzo frame per processo; si riduce con pagine più piccole, ma la tabella cresce). Esterna: memoria libera divisa in buchi non contigui (partizioni variabili e segmentazione); si risolve con la compattazione (solo con rilocazione dinamica) o rendendo non contigua l'allocazione (paginazione).
2. Un sistema ha pagine da 4 KB, indirizzi logici da 32 bit e righe da 4 byte. Dimensione della tabella e come ridurla? $2^{32}/2^{12}=2^{20}$ righe, $4$ MB per processo. Si riduce con tabelle gerarchiche (10+10+12: la tabella esterna è di 4 KB e si allocano solo le interne usate), hash (spazi grandi) o invertita (una riga per frame).
3. TLB con $t=100$ ns e $h=0{,}9$. $\text{EAT}=0{,}9\cdot100+0{,}1\cdot200=110$ ns. Con $h=0{,}99$: $101$ ns. Il TLB è una cache associativa di coppie pagina-frame; senza ASID va svuotato a ogni cambio di contesto.