Gestione della frammentazione in un pool di memoria?

Question

Supponiamo di avere un oggetto del pool di memoria con un costruttore che accetta un puntatore a un grosso frammento di memoria ptr e la dimensione N. Se faccio molte assegnazioni e allocazioni casuali di varie dimensioni posso ottenere la memoria in uno stato tale che non posso allocare un oggetto M byte contiguo in memoria anche se ci può essere molto gratis! Allo stesso tempo, non riesco a compattare la memoria perché ciò causerebbe un puntatore pendente sui consumatori. Come si risolve la frammentazione in questo caso?

Answer 1

Volevo aggiungere i miei 2 cent perché solo nessuno ha sottolineato che dalla descrizione sembra che si stia implementando un allocatore di heap standard (i.e ciò che tutti noi già usiamo ogni volta quando chiamiamo malloc() o operatore nuovo).

Un mucchio è esattamente come un oggetto, che va a gestore della memoria virtuale e chiede grande pezzo di memoria (ciò che si chiama "una piscina"). Quindi ha tutti i tipi di algoritmi diversi per affrontare il modo più efficiente di allocare blocchi di varie dimensioni e liberarli. Inoltre, molte persone hanno modificato e ottimizzato questi algoritmi nel corso degli anni. Per molto tempo Windows è stato dotato di un'opzione chiamata heap a bassa frammentazione (LFH) che era necessario abilitare manualmente. A partire da Vista LFH viene utilizzato per tutti gli heap per impostazione predefinita.

Cumuli non sono perfetti e possono sicuramente impantanarsi prestazioni quando non utilizzati correttamente. Poiché i produttori di sistemi operativi non possono probabilmente anticipare ogni scenario in cui si utilizzerà un heap, i loro gestori di heap devono essere ottimizzati per l'utilizzo "medio". Ma se hai un requisito simile ai requisiti per un heap regolare (cioè molti oggetti, dimensioni diverse ...) dovresti prendere in considerazione solo l'uso di un heap e non reinventarlo perché è probabile che la tua implementazione sia inferiore a quale sistema operativo ti fornisce già.

Con l'allocazione della memoria, l'unico momento in cui è possibile ottenere prestazioni non semplicemente utilizzando l'heap è la rinuncia a qualche altro aspetto (overhead di allocazione, durata dell'allocazione ....) che non è importante per l'applicazione specifica.

Ad esempio, nella nostra applicazione avevamo un requisito per molte allocazioni inferiori a 1 KB ma queste allocazioni erano utilizzate solo per periodi di tempo molto brevi (millisecondi). Per ottimizzare l'app, ho utilizzato la libreria Boost Pool ma l'ho estesa in modo che il mio "allocatore" contenesse effettivamente una raccolta di oggetti del pool boost, ciascuno responsabile dell'allocazione di una dimensione specifica da 16 byte fino a 1024 (in passaggi da 4). Questo ha fornito quasi libera (O (1) complessità) allocazione/liberazione di questi oggetti ma la cattura è che a) l'utilizzo della memoria è sempre grande e non va mai giù anche se non abbiamo un singolo oggetto allocato, b) Boost Pool mai libera la memoria che usa (almeno nella modalità in cui la usiamo), quindi la usiamo solo per oggetti che non rimangono molto a lungo.

Quindi, quale aspetto (s) di normale allocazione di memoria si è disposti a rinunciare nella tua app?

Answer 2

A seconda del sistema ci sono un paio di modi per farlo.

Cercare di evitare la frammentazione in primo luogo, se si assegnano blocchi in potenza di 2 si ha meno possibilità di causare questo tipo di frammentazione. Ci sono un paio di altri modi per aggirarlo, ma se si raggiunge questo stato, si ha solo OOM a quel punto perché non ci sono modi delicati di gestirlo se non di uccidere il processo che richiede memoria, bloccando finché non si può allocare memoria, o restituendo NULL come area di allocazione.

Un altro modo è passare i puntatori ai puntatori dei dati (es: int **). Quindi puoi riorganizzare la memoria sotto il programma (thread safe spero) e compattare le allocazioni in modo da poter allocare nuovi blocchi e mantenere ancora i dati da vecchi blocchi (una volta che il sistema arriva a questo stato anche se diventa un sovraccarico pesante ma dovrebbe raramente essere fatto).

Esistono anche modi di "binning" della memoria in modo da avere pagine contigue per esempio dedicare 1 pagina solo ad allocazioni di 512 e meno, un altro per 1024 e meno, ecc ... Questo rende più facile prendere decisioni su quale bin usare e nel peggiore dei casi dividi dal successivo bin più alto o unisci da un bin inferiore che riduce la possibilità di frammentare su più pagine.

Answer 3

• scrivere il pool per operare come un elenco di allocazioni, è quindi possibile estendere e distruggere in base alle esigenze. questo può ridurre la frammentazione.
• e/o implementare il supporto di trasferimento (o spostamento) di allocazione in modo da poter compattare le allocazioni attive. l'oggetto/detentore potrebbe aver bisogno di assistenza, poiché il pool potrebbe non sapere necessariamente come trasferire i tipi stessi. se il pool viene utilizzato con un tipo di raccolta, è molto più semplice eseguire la compattazione/i trasferimenti.

Answer 4

Attuare object pools per gli oggetti che si alloca spesso guiderà la frammentazione in modo considerevole, senza la necessità di cambiare il vostro allocatore di memoria.

Answer 5

Sarebbe utile sapere più esattamente cosa si sta effettivamente cercando di fare, perché ci sono molti modi per affrontare questo.
Ma la prima domanda è: sta succedendo davvero, o è una preoccupazione teorica?

Una cosa da tenere a mente è che si dispone di molto più spazio di memoria virtuale disponibile rispetto alla memoria fisica, quindi anche quando la memoria fisica è frammentata, c'è ancora molta memoria virtuale contigua. (Ovviamente, la memoria fisica è poco chiara sotto, ma il tuo codice non lo vede.)

Penso che a volte ci sia una paura ingiustificata della frammentazione della memoria, e di conseguenza le persone scrivono un allocatore di memoria personalizzato (o peggio, loro elaborare uno schema con maniglie e memoria mobile e compattazione). Penso che questi siano raramente necessari nella pratica, e a volte può migliorare le prestazioni per buttare fuori questo e tornare a usare malloc.