9 Sessione Bonus di Domande e Risposte di Allen Briggs <briggs@ninthwonder.com>

FreeBSD usa un intervallo tra zone di swap fissato, con un valore predefinito di 4. Questo significa che FreeBSD riserva spazio per quattro aree di swap anche se ne hai una sola o due o tre. Poiché lo swap è intervallato lo spazio di indirizzamento lineare che rappresenta le “quattro aree di swap” verrà frammentato se non si possiedono veramente quattro aree di swap. Ad esempio, se hai due aree di swap A e B la rappresentazione dello spazio di FreeBSD per quell'area di swap verrà interrotta in blocchi di 16 pagine:

A B C D A B C D A B C D A B C D

FreeBSD 3.X usa una “lista sequenziale delle regioni libere ” per registrare le aree di swap libere. L'idea è che grandi blocchi di spazio libero e lineare possano essere rappresentati con un nodo singolo (kern/subr_rlist.c). Ma a causa della frammentazione la lista sequenziale risulta assurdamente frammentata. Nell'esempio precedente, uno spazio di swap completamente non allocato farà si che A e B siano mostrati come “liberi” e C e D come “totalmente allocati”. Ogni sequenza A-B richiede un nodo per essere registrato perché C e D sono buchi, dunquei nodi di lista non possono essere combinati con la sequenza A-B seguente.

Perché organizziamo lo spazio in intervalli invece di appiccicare semplicemente le area di swap e facciamo qualcosa di più carino? Perché è molto più semplice allocare strisce lineari di uno spazio di indirizzamento ed ottenere il risultato già ripartito tra dischi multipli piuttosto che cercare di spostare questa complicazione altrove.

La frammentazione causa altri problemi. Essendoci una lista lineare nella serie 3.X, ed avendo una tale quantità di frammentazione implicita, l'allocazione e la liberazione dello swap finisce per essere un algoritmo O(N) invece di uno O(1). Combinalo con altri fattori (attività di swap pesante) e comincerai a trovarti con livelli di overhead come O(N^2) e O(N^3), e ciò è male. Il sistema dela serie 3.X può anche avere necessità di allocare KVM durante un'operazione di swap per creare un nuovo nodo lista, il che può portare ad un deadlock se il sistema sta cercando di liberare pagine nella memoria fisica in un momento di scarsità di memoria.

Nella serie 4.X non usiamo una lista sequenziale. Invece usiamo un albero radicato e mappe di bit di blocchi di swap piuttosto che nodi lista. Ci prendiamo il peso di preallocare tutte le mappe di bit richieste per l'intera area di swap ma ciò finisce per consumare meno memoria grazie all'uso di una mappa di bit (un bit per blocco) invece di una lista collegata di nodi. L'uso di un albero radicato invece di una lista sequenziale ci fornisce una performance quasi O(1) qualunque sia il livello di frammentazione dell'albero.

Si, questo può confondere. La relazione è “obiettivo” contro “realtà”. Il nostro obiettivo è separare le pagine ma la realtà è che se non siamo in crisi di memoria, non abbiamo bisogno di farlo.

Questo significa che FreeBSD non cercherà troppo di separare le pagine sporche (coda inattiva) da quelle pulite (code della cache), ne cercherà di disattivare le pagine (coda pagine attive -> coda pagine inattive) quando il sistema non è sotto sforzo, anche se non vengono effettivamente usate.

Un fault COW può essere o legato a uno zero-fill o a dati di programma. Il meccanismo è lo stesso in entrambi i casi poiché i dati di programma da copiare sono quasi certamente già presenti nella cache. E infatti li tratto insieme. FreeBSD non effettua preventivamentela copia dei dati di programma o lo zero-fill, effettua la mappatura preventiva delle pagine che sono presenti nella sua cache.

Una vm_page rappresenta una tupla (oggetto,indice#). Una pv_entry rappresenta una voce nella tabella delle pagine hardware (pte). Se hai cinque processi che condividono la stessa pagina fisica, e tre delle tabelle delle pagine di questi processi mappano effettivamente la pagina, questa pagina verrà rappresentata da una struttura vm_page singola e da tre strutture pv_entry.

Le strutture pv_entry rappresentano solo le pagine mappate dalla MMU (una pv_entry rappresenta un pte). Ciò significa che è necessario rimuovere tutti i riferimenti hardware a vm_page (in modo da poter riutilizzare la pagina per qualcos'altro, effettuare il page out, ripulirla, sporcarla, e così via) possiamo semplicemente scansionare la lista collegata di pv_entry associate con quella vm_page per rimuovere o modificare i pte dalla loro tabella delle pagine.

Sotto Linux non c'è una lista collegata del genere. Per poter rimuovere tutte le mappature della tabella delle pagine hardware per una vm_page linux deve indicizzare ogni oggetto VM che potrebbe aver mappato la pagina. Ad esempio, se si hanno 50 processi che mappano la stessa libreria condivisa e si vuole liberarsi della pagina X in quella libreria, sarà necessario cercare nella tabella delle pagine per ognuno dei 50 processi anche se solo 10 di essi ha effettivamente mappato la pagina. Così Linux sta barattando la semplicità del design con le prestazioni. Molti algoritmi per la VM che sono O(1) o (piccolo N) in FreeBSD finiscono per diventare O(N), O(N^2), o anche peggio in Linux. Poiché i pte che rappresentano una particolare pagina in un oggetto tendono ad essere allo stesso offset in tutte le tabelle delle pagine nelle quali sono mappati, la riduzione del numero di accessi alla tabela delle pagine allo stesso offset eviterà che la la linea di cache L1 per quell'offset venga cancellata, portando ad una performance migliore.

FreeBSD ha aggiunto complessità (lo schema pv_entry) in modo da incrementare le prestazioni (per limitare gli accessi alla tabella delle pagine solo a quelle pte che necessitino di essere modificate).

Ma FreeBSD ha un problema di scalabilità che linux non ha nell'avere un numero limitato di strutture pv_entry e questo provoca problemi quando si hanno condivisioni massicce di dati. In questo caso c'è la possibilità che finiscano le strutture pv_entry anche se c'è ancora una grande quantità di memoria disponibile. Questo può essere risolto abbastanza facilmente aumentando il numero di struttre pv_entry nella configurazione del kernel, ma c'è veramente bisogno di trovare un modo migliore di farlo.

Riguardo il sovrapprezzo in memoria di una tabella delle pagine rispetto allo schema delle pv_entry: Linux usa tabelle delle pagine “permanenti” che non vengono liberate, ma non necessita una pv_entry per ogni pte potenzialmente mappato. FreeBSD usa tabelle delle pagine “throw away”, eliminabili, ma aggiunge una struttura pv_entry per ogni pte effettivamente mappato. Credo che l'utilizzo della memoria finisca per essere più o meno lo stesso, fornendo a FreeBSD un vantaggio algoritmico con la capacità di eliminare completamente le tabelle delle pagine con un sovraccarico prestazionale minimo.

Sai come funziona una memoria cache hardware L1? Spiego: Considera una macchina con 16MB di memoria principale ma solo 128K di cache L1. In genere il modo in cui funziona la cache è che ogni blocco da 128K di memoria principale usa gli stessi 128K di cache. Se si accede all'offset 0 della memoria principale e poi al 128K su può finire per cancellarei dati che si erano messi nella cache dall'offset 0!

Ora, sto semplificando di molto. Ciò che ho appena descritto è quella che viene detta memoria cache a “corrispondenza diretta”, o direct mapped. La maggior parte delle cache moderne sono quelle che vengono dette set-associative a 2 o 4 vie. L'associatività di questo tipo permette di accedere fino ad N regioni di memoria differenti che si sovrappongano sulla stessa cache senza distruggere i dati preventivamente immagazzinati. Ma solo N.

Dunque se ho una cache set associativa a 4 vie posso accedere agli offset 0, 128K, 256K 384K ed essere ancora in grado di accedere all'offset 0 ritrovandolo nella cache L1. Se poi accedessi all'offset 512K, ad ogni modo, uno degli oggetti dato immagazzinati precedentemente verrebbero cancellati dalla cache.

È estremamente importante ... estremamente importante che la maggior parte degli accessi del processore alla memoria vengano dalla cache L1, poiché la cache L1 opera alla stessa frequenza del processore. Nel momento in cui si ha un miss [1] nella cache L1 si deveandare a cercare nella cache L2 o nella memoria principale, il processore andrà in stallo, e potenzialmente potrà sedersi a girarsi i pollici per un tempo equivalente a centinaia di istruzioni attendendo che la lettura dalla memoria principale venga completata. La memoria principale (la RAM che metti nel tuo computer) è lenta, se comparata alla velocità del nucleo di un moderno processore.

Ok, ora parliamo della colorazione dele pagine: tutte le moderne cache sono del tipo noto come cache fisiche. Esse memorizzano indirizzi di memoria fisica, non indirizzi di memoria virtual. Ciò permette alla cache di rimanere anche nel momento in cui ci sia un cambio di contesto tra processi, e ciò è molto importante.

Ma nel mondo UNIX® devi lavorare con spazi di indirizzamento virtuali, non con spazi di indirizzamento fisici. Ogni programma che scrivi vedrà lo spazio di indirizzamento virtuale assegnatogli. Le effettive pagine fisiche nascoste sotto quello spazio di indirizzi virtuali non saranno necessariamente contigue fisicamente! In effetti, potresti avere due pagine affiancate nello spazio di indirizzamento del processo cge finiscono per trovarsi agli offset 0 e 128K nella memoria fisica.

Un programma normalmente assume che due pagine affiancate verranno poste in cache in maniera ottimale. Cioè, che possa accedere agli oggetti dato in entrambe le pagine senza che esse si cancellino a vicenda le rispettiva informazioni in cache. Ma ciò è vero solo se le pagine fisiche sottostanti lo spazio di indirizzo virtuale sono contigue (per quel che riguarda la cache).

Questo è ciò che viene fatto dalla colorazione delle pagine. Invece di assegnare pagine fisiche casuali agli indirizzi virtuali, che potrebbe causare prestazioni non ottimali della cache, la colorazione dele pagine assegna pagine fisiche ragionevolmente contigue. Dunque i programmi possono essere scritti assumendo che le caratteristiche per lo spazio di indirizzamento virtuale del programma della cache hardware sottostante siano uguali a come sarebbero state se avessero usato lo spazio di indirizzamento fisico.

Si note ho detto “ragionevolmente” contigue invece che semplicemente “contigue”. Dal punto di vista di una cache di 128K a corrispondenza diretta, l'indirizzo fisico 0 è lo stesso che l'indirizzo fisico 128K. Dunque due agine affiancate nello spzio di indirizzamento virtuale potrebbero finire per essere all'offset 128K e al 132K nella memoria fisica, ma potrebbero trovarsi tranquillamente anche agli offset 128K e 4K della memoria fisica e mantenera comunque le stesse caratteristiche prestazionali nei riguardi della cache. Dunque la colorazione delle pagine non deveassegnare pagine di memoria fisica veramente contigue a pagine di memoria virtuale contigue, deve solo assicurarsi che siano assegnate pagine contigue dal punto di vista delle prestazioni/operazioni della cache.