Allocazione dinamica della memoria

Con allocazione dinamica della memoria, in informatica, si intende l'allocazione di memoria per l'utilizzo di un programma durante la propria esecuzione.

Questo metodo è utilizzato per distribuire il possesso di limitate quantità di memoria tra varie porzioni di dati e codice. Un oggetto allocato dinamicamente rimane tale fintanto che non viene deallocato esplicitamente, o dal programmatore o da un garbage collector; questo comportamento è molto differente da quello utilizzato per l'allocazione di memoria automatica o statica. Si dice in gergo che un siffatto oggetto ha una durata della vita dinamica.

L'azione di soddisfare una richiesta di allocazione, che si occupa di cercare e trovare un blocco di memoria inutilizzata di una certa dimensione nell'heap (vedi oltre), è un problema di non facile soluzione. Sono state proposte varie soluzioni, tra cui:

• Free list
• Paging
• Allocazione di memoria con algoritmo buddy

Il problema principale per la maggior parte degli algoritmi di allocazione dinamica della memoria è evitare la frammentazione interna ed esterna, cercando di mantenere efficiente l'allocazione e la deallocazione. Inoltre, la maggior parte degli algoritmi in uso è soggetta al problema che un gran numero di piccole allocazioni può causare un grosso spreco di memoria a causa dell'accumulo di metadati; per questo motivo, molti programmatori preferiscono evitare questo problema utilizzando talvolta una strategia chiamata chunking.

Allocazione di blocchi di dimensione fissa

Una soluzione è quella di avere una lista concatenata LIFO di blocchi di memoria di dimensione prefissata. Questa tecnica funziona incredibilmente bene per semplici sistemi embedded.

Algoritmo buddy

Un'altra possibile soluzione è quella di utilizzare un allocatore che sfrutti l'algoritmo buddy. In questo modo, la memoria è allocata da un grande blocco di memoria, la cui dimensione è una potenza di due. Se il blocco è grande più del doppio rispetto al necessario, esso viene diviso in due. Viene scelta una delle metà ed il processo viene ripetuto ricorsivamente (controllo della dimensione ed eventuale divisione a metà) finché il blocco ottenuto è grande appena a sufficienza per l'uso (in altre parole, quando un'ulteriore divisione per due lo renderebbe più piccolo della dimensione di memoria necessaria).

Tutti i segmenti di memoria della stessa dimensione (quello che viene chiamato buddy in inglese) sono conservati in una lista concatenata ordinata oppure in un albero. Quando un blocco viene rilasciato viene confrontato con il suo vicino: se entrambi sono della stessa dimensione, allora sono combinati ed inseriti nella lista di buddy di dimensione appena più grande. Quando viene richiesto un blocco, l'allocatore comincerà la sua ricerca tra i blocchi di dimensione appena sufficiente, evitando divisioni non necessarie.

Bisogna anche ricordare che l'uso di siffatti allocatori non è ristretto ai soli sistemi realtime, ma anzi esso viene utilizzato anche in vari sistemi operativi (come nel kernel di Linux).

Allocazione di memoria basata su heap

Nell'allocazione di memoria basata su heap, la memoria è allocata all'interno di un grande blocco di memoria inutilizzata chiamato heap (che non ha nulla a che vedere con l'omonima struttura dati, ma ha a che fare col significato gergale della parola "un mucchio di qualcosa"). La dimensione della memoria da allocare può essere determinata a runtime e la durata di vita dell'allocazione stessa non dipende dalla procedura o dallo stack frame correnti. Si accede per via indiretta alla regione di memoria allocata, in genere attraverso un riferimento. L'esatto algoritmo utilizzato per organizzare l'area di memoria e le operazioni di allocazione/deallocazione viene in genere nascosto dietro un'interfaccia astratta (information hiding) e potrebbe usare uno qualsiasi dei metodi elencati in precedenza.

In contrasto, la memoria dello stack delle chiamate è normalmente di dimensione limitata e la durata di vita delle allocazioni dipende dalla durata delle corrispondenti funzioni.

Call stack

Il programmatore può allocare lo heap per mezzo di apposite funzioni. Utilizzando il linguaggio C, è possibile utilizzare le funzioni

void* malloc(size_t n)

oppure

void* calloc(size_t nelem, size_t dimelem)

che consentono di allocare porzioni di memoria all'interno dello heap.

Solitamente, il sistema operativo non si occupa della gestione dello heap e dunque l'allocazione e la deallocazione della memoria all'interno di questo segmento sono a carico del programmatore. Infatti, ogni volta che viene allocata della memoria per mezzo delle funzioni (ad esempio in C) citate in precedenza, è opportuno deallocare la memoria allocata utilizzando la funzione

void free(void*)

Linguaggi come Java della Oracle utilizzano la memoria heap per la memorizzazione delle istanze degli oggetti che insistono all'interno di un programma in esecuzione per mezzo della Java Virtual Machine.

In Java, l'utilizzo della memoria heap è totalmente trasparente per il programmatore poiché vi sono dei meccanismi di gestione automatici dello heap utilizzato, come detto, per la memorizzazione delle istanze degli oggetti.

La deallocazione della memoria heap utilizzata per gli oggetti avviene in modo automatico attraverso il garbage collector, un thread della Java Virtual Machine che si occupa di liberare la memoria heap utilizzata da oggetti che non sono più riferiti all'interno dell'istanza del programma.

Stack e problemi di collisione

Immaginiamo lo spazio di indirizzamento una serie di pile contenitrici. Ognuna di queste pile è una parte di memoria dedicata ad una funzione ed è chiamata "stack frame".

Essendo organizzate in pila, quando vengono aggiunti vengono posti idealmente uno sopra all'altro. In questo modo l'ultimo ad essere stato aggiunto è anche il primo ad essere usato (last in, first out); eseguito il primo seguono gli altri fino ad arrivare al primo aggiunto che si trova in fondo alla pila.

Durante l'esecuzione di istanze di programmi, può accadere che heap e stack collidano.
Ovviamente, questo genere di situazione può causare errori in fase di esecuzione. I sistemi operativi mettono a disposizione dei meccanismi per modificare le soglie delle dimensioni di questi due segmenti (stack segment e data segment). Questi meccanismi sono ad esempio delle chiamate di sistema. In Unix, è possibile utilizzare la chiamata di sistema

brk(2)

L'ultimo piatto (ovvero quello che sta alla base della pila) è il segmento di testo, cosiddetto code-segment, puntato da

CS:IP

e contiene le istruzioni in linguaggio macchina del programma ed è in sola lettura.

Bibliografia

• Donald Knuth. The Art of Computer Programming v. 1; Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.4: Dynamic Storage Allocation, pp. 435–456.

Voci correlate

• malloc
• bsdmalloc
• mtmalloc
• umem alloc
• Vmalloc
• Slab (allocazione)
• Slob (allocazione)
• Slub (allocazione)
• mmap
• Puntatore hazard
• Heap Layers
• Hoard (allocatore di memoria)
• Memory pool
• Obstack
• Allocazione automatica della memoria
• Allocazione statica della memoria

Collegamenti esterni

• (EN) Dynamic Storage Allocation: A Survey and Critical Review. di Paul R. Wilson, Mark S. Johnstone, Michael Neely e David Boles.
• (EN) Dynamic Storage Allocation (DSA) (archiviato dall'url originale il 14 marzo 2007). di Herbert Glarner, un programma che descrive tecniche efficienti di allocazione
• (EN) Semplici algoritmi di allocazione della memoria. URL consultato il 4 settembre 2017 (archiviato dall'url originale il 9 aprile 2006). sulla OSDEV Community