Memoria virtuale - paginazione su richiesta e sostituzione delle pagine

La nota Memoria centrale - allocazione contigua, paginazione e segmentazioneUn programma deve stare in memoria centrale per girare; la MMU traduce a ogni accesso l'indirizzo logico (virtuale) in indirizzo fisico, sommando un registro di rilocazione e controllando il limite; con l'allocazione contigua (partizioni fisse o variabili, first/best/worst fit) si hanno frammentazione interna ed esterna e serve la compattazione; la paginazione divide memoria logica in pagine e memoria fisica in frame della stessa dimensione (potenza di 2), elimina la frammentazione esterna, traduce (p, d) con la tabella delle pagine (PTBR, PTLR) e riduce il costo dei due accessi con il TLB (EAT = h * t + (1 - h) * 2t); le tabelle grandi si dividono in gerarchiche, hash o invertite; lo swapping sposta intere pagine o processi su disco; la segmentazione usa blocchi di lunghezza variabile con coppia (base, limite), eventualmente paginati; Intel IA-32 usa segmentazione con paginazione a due livelli (10+10+12 bit) e IA-64 quattro livelli su 48 bit.Memoria centrale - allocazione contigua, paginazione e segmentazione → ha mostrato come si traducono gli indirizzi quando tutto il processo è in memoria. Qui si toglie questa condizione. La stessa tecnica vista dall'architettura (con la cache come termine di confronto) è 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 → 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é la memoria virtuale

Il codice deve stare in memoria per essere eseguito, ma raramente serve tutto insieme: codice per gli errori, routine insolite, grandi strutture dati dichiarate e usate in parte. Un programma eseguito anche se solo parzialmente caricato ha tre vantaggi:

• non è più limitato dalla memoria fisica disponibile;
• ogni programma occupa meno memoria mentre gira, quindi più programmi girano insieme (più CPU utilizzata);
• serve meno I/O per caricare o scaricare i programmi.

Definizione (memoria virtuale). La memoria virtuale è la separazione tra la memoria logica vista dall'utente e la memoria fisica: solo una parte delle pagine di un processo deve stare in RAM, il resto sta su disco. Lo spazio degli indirizzi virtuali (la visione logica di come il processo è in memoria) parte di solito da 0 ed è contiguo, e può essere molto più grande di quello fisico; la MMU lo mappa sulla RAM (e non solo: anche sul disco).

Con questo meccanismo anche fork è più leggera: si copia solo un sottoinsieme delle pagine del padre (vedi copy-on-write più avanti, e 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 →).

Lo spazio virtuale di un processo

Lo stack parte dal massimo e cresce verso il basso, lo heap parte dal basso e cresce verso l'alto; tra i due c'è un buco di indirizzi che non richiede memoria fisica finché heap o stack non crescono. Le pagine possono anche essere condivise tra processi, per esempio le librerie dinamiche o la memoria per la comunicazione tra processi. Per l'organizzazione in C vedi 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 →.

Paginazione su richiesta (demand paging)

Definizione (demand paging). Invece di caricare l'intero processo, si caricano solo le pagine che servono, nel momento in cui il processo le riferisce.

Una pagina già caricata è residente in memoria. Quando il processo riferisce una pagina:

• riferimento non valido (fuori dallo spazio del processo): il processo è abortito;
• pagina già in memoria: si usa;
• pagina non in memoria: va portata dal disco.

L'MMU ha una riga di tabella con un bit di validità (valid-invalid bit): v significa "residente in memoria", i significa "non in memoria" (oppure non legale). All'inizio tutte le righe sono i. Se durante la traduzione l'MMU trova i, scatta un page fault.

I passi del page fault

1. Un riferimento a una pagina con bit i causa un trap al sistema operativo: il page fault è in pratica un'interruzione (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 →).
2. Il sistema operativo controlla in una tabella interna (di solito nel PCB) se il riferimento era non valido (aborto) oppure la pagina era solo non ancora in memoria.
3. Si cerca un frame libero.
4. Si programma un'operazione sul disco per leggere la pagina nel frame.
5. Terminata la lettura, si aggiorna la tabella delle pagine: bit a v e numero di frame.
6. Si riavvia l'istruzione che aveva causato il fault: il processo non si accorge di nulla, e il programma non deve cambiare.

Se si parte senza nessuna pagina in memoria si ha il demand paging puro: il primo fault è sull'istruzione iniziale, e ogni altra pagina si carica al primo accesso. Una singola istruzione può riferire più pagine e quindi dare più fault (per esempio una somma di due numeri in memoria con risultato scritto in memoria: istruzione più tre operandi). Il problema è attenuato dalla località dei riferimenti (vedi 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à →).

Il sistema operativo tiene una lista dei frame liberi (free-frame list): all'avvio tutta la memoria vi è inserita. I frame sono di norma azzerati prima di essere assegnati (zero-fill-on-demand), per sicurezza: un processo non deve leggere i resti di un altro.

Le fasi nel caso peggiore

Trap; salvataggio dei registri e dello stato; si stabilisce che l'interruzione è un page fault; si controlla che il riferimento fosse legale e dove sta la pagina su disco; si emette la lettura (attesa in coda del dispositivo, ricerca e latenza, trasferimento); nel frattempo la CPU è data a un altro processo; interruzione del disco (I/O finito); salvataggio dello stato dell'altro processo; si stabilisce che l'interruzione veniva dal disco; si correggono tabelle; attesa che la CPU torni al processo; ripristino dei registri e riavvio dell'istruzione.

Prestazioni

Tre attività: gestione del fault (poche centinaia di istruzioni), lettura della pagina (moltissimo tempo), riavvio (poco). Con $p$ la frequenza dei page fault ($0\le p\le1$: $p=0$ nessun fault, $p=1$ ogni riferimento è un fault):

$$\text{EAT}=(1-p)\cdot t_{\text{mem}}+p\cdot t_{\text{fault}}$$

dove $t_{\text{fault}}$ include servizio dell'interruzione, eventuale scrittura della vittima su disco e lettura della pagina.

Esempio (slide). Accesso alla memoria 200 ns, servizio medio del fault 8 ms $=8\,000\,000$ ns. $\text{EAT}=(1-p)\,200+p\cdot8\,000\,000=200+7\,999\,800\,p$ ns. Con un fault ogni 1000 accessi ($p=0{,}001$): $\text{EAT}=200+7999{,}8=8199{,}8$ ns $\approx 8{,}2\ \mu$s, 40 volte più lento. Per un degrado minore del 10%: $220>200+7\,999\,800\,p$, cioè $p<2{,}5\cdot10^{-6}$, meno di un fault ogni 400 000 accessi.

Quindi i fault devono essere rarissimi, e questo succede grazie alla località. Calcoli di questo tipo, anche con il TLB, sono in Esercizio - Tempo di accesso effettivo con TLB e page fault (eserciziario, esercizi 32, 70 e 118).

Ottimizzazioni

• L'I/O sulla swap è più veloce di quello sul file system (anche sullo stesso dispositivo): blocchi più grandi, meno gestione. Si può copiare l'intera immagine del processo nella swap all'avvio e poi paginare da lì.
• In Solaris e BSD si carica il codice dal file eseguibile e lo si scarta semplicemente quando si libera il frame (non si riscrive). Si scrive sulla swap solo quanto non è associato a un file (stack, heap) o è stato modificato e non ancora riscritto.

Copy-on-write

Con copy-on-write (COW) padre e figlio condividono le stesse pagine dopo una fork; solo quando uno dei due modifica una pagina condivisa, questa viene copiata. Si copiano solo le pagine modificate: la creazione dei processi è molto più efficiente (spesso il figlio fa subito exec e non modifica quasi nulla).

Sostituzione delle pagine

Se non ci sono frame liberi: tutti sono occupati dalle pagine dei processi, ma anche dal kernel e dai buffer di I/O. Si deve liberare un frame: terminare il processo, scaricarlo, oppure sostituire una pagina. La sostituzione delle pagine completa la separazione tra memoria logica e fisica: si può offrire una grande memoria virtuale su una piccola RAM.

Procedimento base

1. Trovare la pagina richiesta sul disco.
2. Trovare un frame libero: se c'è, si usa; altrimenti si usa un algoritmo di sostituzione per scegliere una vittima, e se la vittima è modificata (dirty) si scrive su disco.
3. Caricare la pagina nel frame e aggiornare le tabelle (vittima non valida, nuova valida).
4. Riavviare l'istruzione.

Ora un fault può richiedere due trasferimenti (scrittura della vittima e lettura della nuova), con EAT più alto. Il bit di modifica (modify bit o dirty bit) riduce i trasferimenti: solo le pagine modificate sono scritte. Una pagina non modificata si scarta e basta.

Due problemi: allocazione dei frame (quanti a ogni processo) e sostituzione (quale pagina). Si vuole il minimo numero di page fault, sia al primo accesso sia ai riaccessi.

Stringa dei riferimenti

Gli algoritmi si valutano su una stringa dei riferimenti (reference string), cioè la sequenza dei numeri di pagina (non degli indirizzi interi). Un accesso ripetuto a una pagina già presente non causa un fault. Il risultato dipende dal numero di frame: più frame, di solito meno fault (ma non sempre, vedi Belady).

FIFO

Definizione (FIFO). Si sostituisce la pagina da più tempo in memoria (la prima caricata). Basta una coda.

Stringa 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1, 3 frame: 15 fault. La tabella mostra il contenuto di ogni frame (F = fault):

FIFO può togliere una pagina usatissima solo perché vecchia.

Anomalia di Belady

Con FIFO aumentare i frame può aumentare i fault. Stringa 1 2 3 4 1 2 5 1 2 3 4 5: con 3 frame ci sono 9 fault, con 4 frame 10.

Algoritmo ottimo (OPT)

Definizione (OPT). Si sostituisce la pagina che non sarà usata per il periodo più lungo. Ha il minimo numero di fault possibile.

Con la stessa stringa e 3 frame: 9 fault, il meglio ottenibile. Ma richiede di conoscere il futuro: non è realizzabile, serve solo come termine di paragone per misurare gli altri algoritmi.

LRU (least recently used)

Definizione (LRU). Si sostituisce la pagina non usata da più tempo: si usa il passato come stima del futuro.

Stessa stringa e 3 frame: 12 fault, meglio di FIFO (15), peggio di OPT (9). Due realizzazioni:

• contatore: ogni riga di tabella ha un campo che riceve il valore dell'orologio a ogni riferimento; alla sostituzione si cerca il valore minimo (serve una ricerca);
• pila: una pila di numeri di pagina; a ogni riferimento la pagina va in cima (cima = più recente, fondo = LRU); l'aggiornamento è più costoso ma non serve la ricerca.

Entrambe richiedono hardware speciale e aggiornamenti a ogni riferimento: troppo lento in software.

Algoritmi a pila

OPT e LRU sono algoritmi a pila (stack algorithms): l'insieme delle pagine in memoria con $n$ frame è sempre un sottoinsieme di quello con $n+1$ frame. Quindi più frame non possono peggiorare il risultato: non hanno l'anomalia di Belady. FIFO non è un algoritmo a pila.

Gli esercizi con tabelle complete sono in Esercizio - Sostituzione delle pagine con FIFO, LRU e OPT (eserciziario, esercizi 38, 39, 40, 48, 57, 58 e 80) e Esercizio - Anomalia di Belady e limiti sui page fault (slide di memoria virtuale, eserciziario, esercizi 33 e 84).

Approssimazioni di LRU

Pochi sistemi hanno l'hardware per LRU. Molti offrono un bit di riferimento per pagina: inizialmente 0, posto a 1 quando la pagina è riferita. Si può sostituire una pagina con bit 0, ma non si sa l'ordine dei riferimenti.

Seconda opportunità (second chance, algoritmo dell'orologio). È FIFO con il bit di riferimento. Le pagine sono disposte in una lista circolare con una lancetta. Per scegliere la vittima: se la pagina puntata ha bit 0, si sostituisce; se ha bit 1, si azzera il bit, la pagina resta (ha avuto la sua seconda opportunità) e si passa alla successiva. Se tutti i bit sono 1, la lancetta fa un giro intero azzerandoli e poi sostituisce la prima, quindi degenera in FIFO. Un esempio di second chance globale è in Esercizio - Second chance globale con bit di riferimento (eserciziario, esercizio 51).

Seconda opportunità migliorata (enhanced). Usa la coppia (riferimento, modifica):

Si scorre l'orologio e si sostituisce la prima pagina della classe più bassa non vuota.

Allocazione dei frame

Ogni processo ha bisogno di un numero minimo di frame, e il sistema ha un totale massimo. Come dividerli?

• Uguale (equal allocation): con 100 frame (dopo quelli del sistema operativo) e 5 processi, 20 a testa (si può tenere una parte come riserva di frame liberi).
• Proporzionale (proportional allocation): secondo la dimensione $s_i$ (o la priorità) di ogni processo: $a_i=m\,\dfrac{s_i}{S}$ con $S=\sum s_i$ e $m$ i frame totali. È dinamica, perché cambia al variare di processi e dimensioni. Esempio (slide): $m=62$, $s_1=10$ KB, $s_2=127$ KB, $S=137$: $a_1=62\cdot10/137\approx5$ e $a_2=62\cdot127/137\approx57$ (esattamente $4{,}5$ e $57{,}5$, poi arrotondati).

Sostituzione globale e locale

Pool di frame liberi e recupero

Per ridurre il ritardo del fault si tiene sempre un pool di frame liberi: la nuova pagina va subito in un frame libero e dopo, con calma, si elimina la vittima e si aggiunge ai liberi. Inoltre si può lasciare intatto il contenuto dei frame liberi e annotare cosa contengono: se la pagina è riferita di nuovo prima del riuso, non si rilegge dal disco. Con la sostituzione globale si recupera quando la lista dei liberi scende sotto una soglia, invece di aspettare lo zero. Se non si riesce a mantenere un minimo di frame liberi, si può cambiare politica o terminare processi molto esigenti.

Thrashing

Se un processo non ha abbastanza pagine, il tasso di page fault è altissimo:

1. la CPU è poco utilizzata (i processi attendono il disco);
2. il sistema pensa di dover aumentare il grado di multiprogrammazione;
3. si aggiunge un altro processo: peggio (altri frame sottratti).

Questo è il thrashing: i processi passano il tempo a scaricare e caricare pagine. La sostituzione locale lo limita, ma un solo processo in thrashing tiene occupato il disco e rallenta anche gli altri.

Località e working set

La paginazione funziona perché c'è località: un processo passa da una località a un'altra, e in ogni intervallo usa un sottoinsieme di pagine (una funzione, i suoi dati, le variabili globali). Si ha thrashing quando $\sum(\text{dimensione delle località})>\text{memoria totale}$.

Definizione (working set). Sia $\Delta$ la finestra del working set: gli ultimi $\Delta$ riferimenti. Il working set $WS$ è l'insieme delle pagine riferite in quella finestra: un'approssimazione della località. $WSS_i$ è la sua dimensione per il processo $P_i$.

Se $\Delta$ è troppo piccola non copre la località; troppo grande ne copre più d'una; con $\Delta=\infty$ è l'intero processo. La richiesta totale di frame è $D=\sum_iWSS_i$; se $D>m$ (frame disponibili) c'è thrashing e il sistema deve sospendere o scaricare un processo. Il tasso di fault ha picchi (cambio di località) e valli (working set caricato). Un esercizio è Esercizio - Working set, thrashing e frequenza dei page fault (eserciziario, esercizio 87).

Frequenza dei page fault (PFF)

Metodo diretto: si fissa una frequenza accettabile per ogni processo, con sostituzione locale. Se il tasso reale è troppo basso, si toglie un frame al processo; se è troppo alto, gliene si dà uno.

Altre considerazioni

• Prepaging: all'avvio o alla ripresa si caricano in anticipo alcune pagine che serviranno (per esempio l'ultimo working set). Pro: meno fault iniziali. Contro: I/O e memoria sprecati se le pagine non servono.
• Dimensione della pagina: sempre potenza di 2, da $2^{12}$ (4096 byte) a $2^{22}$ (4 MB). Si valutano frammentazione interna, risoluzione, costo dell'I/O, numero di fault, località, dimensione della tabella, efficacia del TLB.
• TLB reach: $\text{TLB reach}=(\text{righe del TLB})\times(\text{dimensione della pagina})$, la memoria raggiungibile dal TLB. Ideale: il working set di ogni processo sta nel TLB. Per aumentarlo: pagine più grandi (più frammentazione interna) o pagine di più dimensioni.
• Struttura dei programmi (laboratorio 7): byte data[20][1024] con pagine da 1024 byte e un solo frame. Il C salva le matrici per righe: una riga è una pagina. Con il ciclo esterno sulle righe (for i... for j...) si hanno 20 fault; con il ciclo esterno sulle colonne si ha un fault a ogni scrittura, $1024\cdot20=20\,480$ fault. Con RAM reale, TLB e cache i fault non cambiano molto, cambiano i TLB miss e i cache miss. Vedi Esercizio - Località dei riferimenti, scorrere una matrice per righe o per colonne (laboratorio 7).

Strumenti Linux (laboratorio 7)

getpagesize() in C e getconf PAGESIZE da terminale restituiscono la dimensione della pagina in byte (di solito 4096); cpuid dà informazioni su TLB e cache (poco accurate in una macchina virtuale); perf stat -e cache-misses,dTLB-load-misses,page-faults ./programma misura gli eventi; lo stack di Linux è di 8 MB, limite aggirabile con ulimit -s unlimited.

Memoria del kernel

La memoria del kernel è trattata a parte, di solito da un pool: richiede strutture di dimensioni diverse, e una parte deve essere contigua (per esempio per i dispositivi di I/O). Due tecniche tipiche di UNIX e Linux.

Buddy system. Si parte da un segmento di pagine fisicamente contigue e si alloca con un allocatore a potenze di 2: la richiesta è arrotondata alla potenza di 2 superiore; se serve un pezzo più piccolo di quello libero, si divide il blocco in due "compagni" (buddies) della potenza di 2 più bassa, fino alla misura giusta. Pro: i blocchi liberi vicini si fondono velocemente. Contro: frammentazione interna. Esempio: da 256 KB una richiesta di 21 KB: $256\to128+128$, $128\to64+64$, $64\to32+32$, e un 32 KB serve la richiesta (spreco $32-21=11$ KB).

Slab allocation. Una slab è una o più pagine contigue; una cache è un insieme di slab per ciascuna struttura dati del kernel, riempita di oggetti (istanze della struttura) marcati liberi. Gli oggetti allocati sono marcati usati; se una slab è piena, si usa una vuota o se ne crea una nuova. Pro: nessuna frammentazione tra segmenti, richieste servite rapidamente.

Domande d'esame

1. Descrivere cosa succede quando si verifica un page fault. Trap, controllo di validità (altrimenti abort), ricerca di un frame libero (o vittima, scritta su disco se dirty), lettura della pagina, aggiornamento della tabella (bit a valido), riavvio dell'istruzione. Nel frattempo la CPU va a un altro processo.
2. Con $t_{\text{mem}}=100$ ns e page fault di 10 ms, quale $p$ massimo per un degrado del 20%? $120>100+p\cdot(10\,000\,000-100)$ cioè $p<20/9\,999\,900\approx2\cdot10^{-6}$.
3. FIFO, LRU, OPT su 2 3 2 1 5 2 4 5 3 2 5 2 con 3 frame; cos'è l'anomalia di Belady? Si calcola per ognuno la tabella dei frame (vedi Esercizio - Sostituzione delle pagine con FIFO, LRU e OPT (eserciziario, esercizi 38, 39, 40, 48, 57, 58 e 80)); l'anomalia è l'aumento dei fault passando a più frame con FIFO, assente negli algoritmi a pila (LRU, OPT).