Programmare in C – Strutture dati dinamiche

Le strutture dati dinamiche sono strutture dati che crescono e calano di dimensioni secondo le necessità, grazie ad operazioni di allocazione e di deallocazione di memoria da uno spazio chiamato heap.

Le strutture dati dinamiche sono estremamente importanti in C perchè permettono al programmatore di controllare in pieno il consumo di memoria.

Le strutture dati dinamiche allocano blocchi di memoria dalla memoria heap secondo le richieste, e collegano questi blocchi così allocati in un qualche tipo di struttura grazie ai puntatori. Quando la struttura dati non necessità più di un blocco di memoria, il blocco viene rilasciato per un suo successivo riutilizzo (da parte di quel programma o di altre applicazioni). Si tratta quindi di un tentativo di utilizzare la memoria a disposizione in modo efficiente.

Per capire la filosofia di funzionamento delle strutture dati, cerchiamo per prima cosa di capire cosa è di preciso la memoria heap.

Strutture dati dinamiche: la memoria heap

Ad oggi, un personal computer o una workstation dispongono dai 16 ai 64 megabytes di RAM installata. Utilizzando una tecnica chiamata memoria virtuale, il sistema può effettuare lo swap di porzioni di memoria sull'hard disk e viceversa, per dare l'illusione che la CPU abbia a disposizione una memoria molto maggiore, ad esempio anche più di 200/500 megabytes.

La memoria virtuale è una tecnica molto potente per aumentare la quantità di RAM a disposizione su di una macchina in maniera poco costosa (cioè senza comprare effettivamente altra RAM), ma pone dei seri limiti di efficienza. Copiare dati dalla RAM verso il disco fisso e viceversa può rallentare – anche di molto – le prestazioni.

Per gli scopi didattici di questa guida faremo uso di un'ipotesi estremamente limitativa: supponiamo che un computer qualsiasi abbia uno spazio di memoria totale di 50 megabytes, indipendentemente dal fatto che si tratti di memoria fisica o memoria virtuale.

Il sistema operativo della macchina si aspetta di poter utilizzare uno spazio di memoria di 50 megabyte. Il sistema operativo usa lo spazio in vari modi.

Il sistema operativo e varie applicazioni, assieme alle loro variabili globali e agli stack, consumano memoria. Quando un programma termina, rilascia la memoria che deteneva in modo che questa possa essere riutilizzata da altri programmi. Da notare che, fissato un certo istante, parte della memoria rimane inutilizzata.

La memoria contiene il codice eseguibile delle diverse applicazioni che sono in esecuzione in un certo momento, assieme al codice eseguibile del sistema operativo. Ogni applicazione ha cette variabili globali associate. Queste variabili occupano memoria. Ogni applicazione usa un'area di memoria chiamata stack in cui sono contenuti tutti i parametri usati da ogni funzione e tutte le variabili locali. Lo stack ricorda inoltre l'ordine con cui le funzioni vengono chiamate, in modo che ogni funzione possa restituire il valore “corretto”. Ogni volta che una funzione viene chiamata, le sue variabili locali e i parametri sono “inseriti” nello stack. Quando la funzione termina, questi parametri locali sono “estratti”. A causa di ciò, la dimensione dello stack di un programma varia durante l'esecuzione, ma è limitata da una dimensione massima.

Non appena il programma termina, il sistema operativo viene incaricato di liberare la memoria, eliminando il suo spazio stack. Un nuovo programma può utilizzare quello spazio in un momento successivo. In questo modo, la memoria di un computer viene costantemente “riciclata” e riutilizzata da altri programmi.

Statisticamente, si può dire che il 50% della memoria totale di un computer non viene utilizzato. Il sistema operativo controlla e gestisce la memoria non utilizzata, che viene chiamata memoria heap. La memoria heap è estremamente importante perché diventa disponibile per l'uso da applicazioni durante l'esecuzione utilizzando le funzioni malloc (memory allocation) e free. La memoria heap permette ai programmi di allocare memoria esattamente quando ne sorge il bisogno durante l'esecuzione, molto meglio che pre-allocarlo con un array di dimensione fissata una volta per tutte.

Scarica subito una copia gratis

Scrivi un commento

Seguici anche sul tuo Social Network preferito!

Send this to a friend