Che cos'è un elenco gratuito?
Un elenco gratuito è una struttura di dati che contiene gli indirizzi delle posizioni di memoria del computer che possono essere utilizzati da un programma in esecuzione quando si utilizza l'allocazione dinamica della memoria. L'elenco diventa necessario quando un programma deve allocare spazio da un'area di memoria libera chiamata heap. L'implementazione di un elenco libero può essere un semplice elenco collegato o potrebbe essere una struttura di dati più complessa come un albero di ordinamento La maggior parte dei linguaggi di programmazione per computer di alto livello gestiscono automaticamente l'elenco gratuito, eliminando la necessità di una gestione manuale.
Quando un programma richiede spazio per archiviare informazioni durante l'esecuzione del programma, deve richiedere una quantità specifica di memoria al sistema operativo sottostante. Le posizioni dei blocchi di memoria che possono essere utilizzate sono archiviate Per garantire che l'allocazione abbia esito positivo, la quantità di memoria richiesta deve essere disponibile in uno o più di questi blocchi. Quando viene restituito un puntatore a una posizione di memoria appropriata, quell'elemento dell'elenco viene rimosso.
Dopo che un programma è stato utilizzato utilizzando la memoria, può disallocarlo, il che implica il passaggio del puntatore al blocco di memoria nella lista libera, dove sarà disponibile la prossima volta che un'allocazione è È possibile che l'allocazione della memoria non riesca perché l'elenco è vuoto o perché non ci sono blocchi di memoria disponibili abbastanza grandi da soddisfare la richiesta del programma.
La forma più semplice di gestione della memoria è chiamata primo sistema di adattamento, che mantiene un unico elenco di posizioni di memoria libere. Quando viene inviata una richiesta di memoria, l'elenco viene attraversato e il primo blocco viene restituito abbastanza grande. Se il blocco è più del doppio della dimensione richiesta, viene dimezzato e la metà inutilizzata viene aggiunta all'elenco. Questo metodo scambia la codifica semplice per il rischio di avere aree di memoria frammentate che potrebbero non essere mai riportate nell'elenco.
Una diversa forma di gestione della memoria è chiamata sistema di allocazione degli amici: a differenza del primo sistema adatto, l'allocazione degli amici mantiene diversi elenchi liberi, ognuno dei quali contiene blocchi aperti di una sola dimensione particolare. quando viene ricevuta una richiesta di allocazione, viene consultato l'elenco che contiene blocchi che sono abbastanza grandi da riempire la richiesta e viene restituita una posizione aperta Se nessun blocco libero è inferiore al doppio della dimensione richiesto sono disponibili, un blocco più grande è diviso in due per soddisfare i requisiti.
Il termine "elenco libero" può riferirsi a un singolo elenco collegato di indirizzi di memoria oppure a un tipo di struttura di dati molto più complesso. Diversi tipi di alberi di ordinamento, se mantenuti semplici ed equilibrati, può aiutare ad aumentare la velocità di ricerca di blocchi di memoria aperti a spese della complicazione del codice sorgente. Un elenco collegato può essere più lento di un albero di ordinamento specializzato ma crea un codice di programmazione molto più facile da leggere, debug e modifica.
Alcuni linguaggi di programmazione e sistemi operativi utilizzano uno speciale meccanismo chiamato garbage collection, un processo che può aiutare a prendere le diverse voci in un elenco libero e a consolidare gli spazi liberi in modo che siano contigui. l'effetto di prevenire la frammentazione e consentire l'allocazione di blocchi di memoria più grandi.