Frammentazione della memoria

Matteo - 9 mag 2006 01:15

Il koan si riduce a: qualunque linguaggio voi utilizziate, se avete bisogno di gestire grandi quantità di dati, frammentate il più possibile questi dati in buffer diversi; evitate il più possibile di creare buffer monolitici di decine o centinaia di mega: esaurirete la memoria senza accorgervene.

Mi capita in questi giorni di combattere contro un problema particolarmente insidioso legato a come funziona l'allocazione di memoria su Windows: si manifesta con l'impossibilità, in alcune occasioni, di allocare blocchi ingenti di memoria come un unico blocco, nonostante la memoria disponibile sia ancora enorme, sia fisica sia virtuale.

La situazione è questa: un'applicazione svolge calcoli su una grande quantità di dati, divisi in blocchi di grosse dimensioni, in modalità simili a quelle mostrate in figura:


A, B e C sono algoritmi. 1, 2, 3 e 4 sono blocchi di dati; 1 è l'input e 4 è l'output. Si può notare che dopo aver concluso A, il blocco 1 non è più necessario e viene eliminato dalla memoria; analogamente quando si stanno eseguendo gli altri algoritmi, l'unica memoria allocata è quella dei blocchi interni all'algoritmo corrente. Ad un blocco di memoria non corrisponde necessariamente un unico malloc, ma corrisponde ad una struttura complessa che comprende blocchi più piccoli, di dimensione che può variare da pochi kilobyte a diversi megabyte (nel mio caso fino al caso "estremo" di circa 300 megabyte).

Veniamo al problema. In tutti i giochi di allocazione / deallocazione / riallocazione che avvengono durante il processamento, la memoria si "frammenta" a tal punto che ad un certo punto non ci sia più "spazio libero" per un nuovo buffer di dimensioni ragguardevoli: è il caos, il calcolo si interrompe magari dopo ore senza ottenere alcun risultato. Ma la cosa peggiore è seguire durante il calcolo l'occupazione di memoria dal task manager o dall'interno del programma con GlobalMemoryStatus: nulla fa presagire l'esaurimento della memoria. Magari ci potrebbero essere ancora da sfruttare, in base a quei numeri, centinaia di megabyte in più rispetto alla quantità richiesta. Caso di cui sono testimone: 1200 mega di memoria virtuale disponibili, 70 mega richiesti con un malloc e non disponibili. Cosa cavolo succede?!

La risposta al problema nel suo complesso che posso fornire non è facilissima e si basa su ipotesi personali formate in base alla mia conoscenza (limitata?) sui meccanismi interni della gestione della memoria di Windows. La risposta breve alla prima domanda è: non c’è più spazio contiguo, nella memoria virtuale, per un buffer così grande. Spiegato meglio, vuol dire che il sistema non è in grado di fornire all'applicazione un puntatore alla memoria tale che da quel punto in avanti ci sia lo spazio richiesto libero: se chiedo x megabyte, il sistema non riesce a trovare uno spazio di indirizzi liberi a partire da un puntatore ptr fino a (ptr + x*1024*1024). La domanda successiva è ovvia: perché?

Prima, chiariamo qual è la differenza tra memoria virtuale e memoria fisica (che sia RAM o file di swap, non cambia nulla): la memoria virtuale è quella a cui l'applicazione può accedere senza preoccuparsi di dove sia collocato fisicamente il bit che va a leggere o a scrivere; è uno spazio di indirizzi contiguo di circa 2 gigabyte a cui teoricamente l'applicazione può accedere senza limiti:  l'unica preoccupazione dell'applicazione è quella di chiedere al sistema quanta memoria gli serve e dirgli quando non gli serve più ed il sistema fa il resto. Il resto significa gestire proprio il collegamento tra la memoria virtuale e la memoria fisica, ovvero quella che mantiene per un certo tempo fisicamente un bit in un certo stato e che può essere fornita da periferiche eterogenee: hard disk, memoria RAM più o meno veloce, cache di primo o secondo livello… Il collegamento viene stabilito in modo piuttosto semplice: la memoria virtuale e quella fisica vengono divise in tante parti di dimensione uguale, le pagine, e in una tabella vengono memorizzati i collegamenti tra una pagina della memoria virtuale e una della memoria fisica: se un'applicazione vuole accedere ad una certa pagina della memoria virtuale, il sistema capisce a quale pagina della memoria fisica l'applicazione vuole effettivamente accedere. La cosa importante da capire in questo caso è che la dimensione delle pagine di memoria è piccola rispetto ai buffer che qui si vogliono utilizzare: il risultato ovvio è che uno dei nostri buffer occuperà senz'altro molte pagine (contigue) di memoria virtuale. Un secondo passo importante è capire che le pagine contigue di memoria virtuale non sono necessariamente contigue nella memoria fisica: secondo lo schema spiegato rozzamente prima questo non è affatto necessario (ed in effetti impedirebbe altri meccanismi che qui non ci interessano). La relazione tra memoria virtuale e memoria fisica può essere rozzamente rappresentata come in figura:

 

Torniamo allora al problema: perché ad un certo punto il sistema non trova più uno spazio sufficiente di memoria virtuale anche se di fisica ce n'è in abbondanza? La risposta è: perché la memoria libera c’è ma è divisa in mille buchi tra la memoria occupata. Infatti se la nostra applicazione fa un numero sconsiderato di allocazioni, deallocazioni o reallocazioni, la memoria virtuale diventa una specie di groviera, in cui si alternano blocchi relativamente piccoli di memoria libera e memoria occupata: la memoria si dice frammentata, l'effetto è che ad un certo punto non c'è un buco abbastanza grande per contenere il buffer richiesto. Uno degli indici utilizzabili per rendersi conto del problema lo fornisce la funzione GetProcessMemoryInfo, contenuta nella libreria PSAPI: riempie una struttura PROCESS_MEMORY_COUNTERS che nel campo PeakPagefileUsage indica il massimo della memoria di paging utilizzata — l'impressione è che il valore sia collegato proprio allo spazio di indirizzamento utilizzato. Senza mettere mano al codice dell'applicazione, questo valore è mostrato anche nelle informazioni sul processo fornite da Spy++, una delle utility comprese nel pacchetto di Visual C: se il picco si avvicina ai 2 gigabyte, la vostra applicazione è "a rischio".

Al problema sembra ci siano diverse soluzioni, nessuna comunque definitiva: ad un certo punto, col crescere delle dimensioni del problema, per quanto la nostra politica di uso della memoria possa essere sofisticata, si arriverà a questa situazione, comunque prima di arrivare al limite della memoria fisica (comunque limitata per le applicazioni a 2 GB da Windows).

La soluzione più semplice ma secondo certi aspetti meno efficace consiste nel frammentare il più possibile i buffer, evitando di allocare in un solo malloc decine di megabyte. L'impatto può essere a seconda dei casi anche importante sul resto dell'applicazione: su un'applicazione già "matura" può rivelarsi necessario riscrivere porzioni importanti del codice di calcolo per gestire dati divisi in blocchi. Un vantaggio di questa soluzione è che, se adottata dall'inizio in modo da non impattare troppo sulle prestazioni del calcolo (entrano in gioco considerazioni di vario genere, anche avanzate come quelle sull'uso della cache), può semplificare il lavoro per realizzare altre soluzioni più sofisticate.

Una soluzione diversa e di efficacia a me ancora non chiara riguarda l'uso di routine di gestione della memoria più avanzate del classico malloc: ad esempio l'uso delle routine della famiglia Heap* permette in certi casi di ricompattare la memoria virtuale in modo indolore per liberare spazi contigui sufficientemente grandi. Purtroppo anche questa soluzione prevede nella maggior parte dei casi modifiche ingenti su applicazioni già esistenti e tra l'altro appesantisce il codice con meccanismi decisamente più complessi di quelli molto semplici del malloc che in alcuni casi (ad esempio nell'uso di librerie esterne di appoggio) ne impediscono di fatto l'utilizzo. Resta comunque da approfondire questa tecnica, in quanto offre un ulteriore livello di astrazione tra la memoria utilizzata dall'applicazione e quella fisica che se ben utilizzato potrebbe ridurre molto l'impatto del problema, soprattutto su applicazioni realizzati fin dall'inizio con quest'ottica.

Parte del problema è che algoritmi complessi possono richiedere un numero molto alto di allocazioni, deallocazioni e reallocazioni della memoria; quando queste operazioni crescono di numero, l'impatto sulla frammentazione della memoria che esse comportano diventa notevole; appare quindi importante ridurre al massimo il loro utilizzo, sebbene questo non possa risolvere del tutto il problema. Partendo da questa consapevolezza, una soluzione per certi versi "estrema" potrebbe essere quella di allocare uno spazio sufficientemente grande di memoria all'inizio del calcolo (quando non c'è ancora frammentazione) e di gestire dall'applicazione stessa l'allocazione della memoria da parte delle routine, magari ridefinendo direttamente le funzioni di malloc per non dover modificare le routine di calcolo già esistenti. La soluzione, sebbene offra la possibilità di realizzare teoricamente una politica perfettamente adeguata alle necessità dell'applicazione specifica, è evidentemente molto complessa da realizzare e soffre comunque di problemi non banali, ad esempio legati all'allocazione delle risorse del sistema e ad un certo carico sulle prestazioni dovuto alla doppia gestione della stessa memoria da parte prima del sistema e poi dell'applicazione.

In generale la soluzione più interessante sembra la più semplice, ovvero la prima: frammentare i dati. Primo perché offre il vantaggio che con relativamente poca fatica si ottiene un beneficio relativo abbastanza immediato: si riesce a "tappare meglio i buchi" e quindi soffrire più raramente del problema di memoria insufficiente. Ma, cosa ancora più importante, da un algoritmo che lavori "a blocchi" si riesce con meno difficoltà a realizzarne uno che possa appoggiarsi ad esempio ad una memoria di massa che non abbia i vincoli di indirizzamento della memoria: un disco rigido ad esempio. I blocchi ad esempio possono essere memorizzati su disco e caricati nella memoria solo quando necessario — sta ovviamente all'analista riuscire a creare il minor numero di input / output tra i due. Un secondo vantaggio della memorizzazione su disco è che, se il calcolo è realizzato in modo adeguato e i blocchi degli algoritmi sono separati come nella figura sopra (quasi utopistica in alcuni casi), il calcolo può essere portato avanti in esecuzioni successive del programma, con la memoria "fresca" di un nuovo avvio dell'applicazione, o addirittura ogni blocco algoritmico può essere eseguito da un processo separato, con il proprio spazio di indirizzamento, all'interno della stessa applicazione. Per non parlare poi dei problemi di crash nel programma a calcolo avanzato che avrebbero decisamente meno impatto se lo stato del calcolo fosse periodicamente salvato e potesse essere parzialmente ripristinato successivamente. Il calcolo basato su blocchi di dati memorizzati su memoria secondaria è chiamato tradizionalmente out-of-core e ha implicazioni e possibilità — molto interessanti — che vanno ben al di là della presente trattazione.

Le implicazioni di quanto detto vanno al di là della programmazione su Windows in Visual C++: coinvolgono un meccanismo di gestione della memoria condiviso da molti sistemi operativi e certamente indipendente nella maggior parte dei casi dal linguaggio utilizzato. Ho personalmente affrontato questo problema in Visual C, ma non mi stupirei se effetti analoghi di esaurimento prematuro della memoria fossero rilevabili su Java, Visual Basic o quant'altro, con conseguenze forse ancor meno comprensibili o gestibili che nel caso del Visual C.

 

frammentazione

dario - 27 ott 2006 09:40

Frammentazione interna ed esterna
Da notare che tutti i file-system commerciali utilizzano la tecnica del file-paging: un supporto di memoria di massa viene suddiviso in pagine o cluster (la cui misura in genere varia da 512B a 4KB), per ottimizzare le operazioni di lettura e scrittura. Questo però può causare uno spreco di memoria, soprattutto quando la pagine sono di grandi dimensioni (si pensi ad un file di 5 KB ed un file-system con cluster di 4 KB: ne sono necessari 2 per un totale di 8 KB ed uno spreco di ben 3 KB): in questo caso si parla di frammentazione interna.
Invece, per frammentazione esterna s'intende il fenomeno per il quale tra due file si viene a creare uno spazio vuoto troppo piccolo per memorizzarvi un altro file: questo fenomeno è tipico dei file-system con cluster troppo piccoli.
Weblog Koan Progetti Foto Contatti DW.net map