Cos'è un elenco gratuito?
Un elenco gratuito è una struttura di dati che contiene gli indirizzi delle posizioni di memoria del computer disponibili per l'uso da un programma in esecuzione quando si utilizza l'allocazione di memoria dinamica. L'elenco diventa necessario quando un programma deve allocarespazio 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 comeun albero di ordinamento. La maggior parte dei linguaggi di programmazione di computer di alto livello gestiscono automaticamente l'elenco gratuito, rimuovendo la necessità di gestione manuale.
Quando un programma richiede spazio per archiviare le informazioni durante l'esecuzione del programma, ITdeve richiedere una quantità specifica di memoria dal sistema operativo sottostante. Le posizioni dei blocchi di memoria che possono essere utilizzati sono archiviati nell'elenco gratuito. Affinché l'allocazione abbia esito positivo, la quantità di memoria richiestadeve essere disponibile in uno o più di questi blocchi. Quando un puntatore a una locazione di memoria appropriatan viene restituito, quell'elemento dell'elenco viene rimosso.
Dopo che un programma viene eseguito usando la memoria, può de-allocarla. Ciò comporta il passaggio del puntatore alla memoriaBlocca nell'elenco gratuito, dove sarà disponibile la prossima volta che verrà tentata un'allocazione. È possibile che l'allocazione della memoria fallisca perché l'elenco è vuoto o perché non ci sono blocchi di memoria disponibili abbastanza da soddisfare ilRichiesta del programma.
La forma più semplice di gestione della memoria è chiamata prima sistema di adattamento. Questo sistema mantiene un unico elenco di posizioni di memoria gratuita. Quando viene inviata una richiesta di memoria,L'elenco viene attraversato e viene restituito il primo blocco che è abbastanza grande. Se il blocco è più del doppio della dimensione richiesta, viene dimezzato e la metà inutilizzata viene aggiunta all'elenco. Questo metodo scambia una semplice codifica per il rischio di avere una memoria frammentataaree che non potrebbero mai essere restituite all'elenco.
Una diversa forma di gestione della memoria è chiamata sistema di allocazione Buddy. A differenza del primo sistema di adattamento, l'allocazione del Buddy mantiene diversi elenchi gratuiti, ognuno in possessoblocchi aperti di una sola dimensione particolare. Ciò significa che quando viene ricevuta una richiesta di allocazione, l'elenco che contiene blocchi che sono abbastanza grandi da riempire la richiesta viene consultata e viene restituita una posizione aperta. Se noSono disponibili blocchi gratuiti che sono meno del doppio delle dimensioni richieste, un blocco più grande viene diviso in due per soddisfare i requisiti.
Il termine elenco libero può fare riferimento a un singolo elenco collegato di indirizzi di memoria,oppure può riferirsi a un tipo molto più complesso di struttura dei dati. Diversi tipi di ordinamento, se mantenuti semplici ed equilibrati, possono aiutare ad aumentare la velocità di trovare blocchi di memoria aperti a spese di complicanzail codice sorgente. Un elenco collegato può essere più lento di un albero di ordinamento specializzato ma crea programmiCodice ing molto più facile da leggere, debug e modifica.
Alcuni linguaggi di programmazione e sistemi operativi utilizzano un meccanismo speciale chiamato Garbage Collection. Questo è un processo che può aiutare a prendere le diverse voci su unElenco libero e consolidare gli spazi liberi in modo che siano contigui. Ciò ha l'effetto di prevenire la frammentazione e consentire l'assegnazione di blocchi di memoria più grandi.