¿Qué es una lista gratuita?
Una lista libre es una estructura de datos que contiene las direcciones de las ubicaciones de memoria de la computadora que están disponibles para su uso por un programa en ejecución cuando se utiliza la asignación dinámica de memoria. La lista se hace necesaria cuando un programa debe asignar espacio desde un área de memoria libre llamada montón. La implementación de una lista libre puede ser una simple lista vinculada o podría ser una estructura de datos más compleja, como un La mayoría de los lenguajes de programación de computadoras de alto nivel manejan automáticamente la lista gratuita, eliminando la necesidad de administración manual.
Cuando un programa requiere espacio para almacenar información durante la ejecución del programa, debe solicitar una cantidad específica de memoria del sistema operativo subyacente. Las ubicaciones de los bloques de memoria que se pueden utilizar se almacenan de forma gratuita lista. Para que la asignación sea exitosa, la cantidad de memoria solicitada debe estar disponible en uno o más de estos bloques. Cuando se devuelve un puntero a una ubicación de memoria adecuada, ese elemento de la lista se elimina.
Una vez que un programa termina de usar la memoria, puede desasignarlo, lo que implica pasar el puntero al bloque de memoria nuevamente a la lista libre, donde estará disponible la próxima vez que se asigne una asignación. Es posible que la asignación de memoria falle porque la lista está vacía o porque no hay bloques de memoria disponibles lo suficientemente grandes como para satisfacer la solicitud del programa.
La forma más simple de administración de memoria se llama el primer sistema de ajuste. Este sistema mantiene una lista única de ubicaciones de memoria libre. Cuando se envía una solicitud de memoria, se recorre la lista y el primer bloque se devuelve lo suficientemente grande. Si el bloque es más del doble del tamaño solicitado, se divide por la mitad y la mitad no utilizada se vuelve a agregar a la lista. Este método cambia la codificación simple por El riesgo de tener áreas de memoria fragmentadas que nunca podrían volver a la lista.
Una forma diferente de administración de memoria se denomina sistema de asignación de amigos. A diferencia del primer sistema de ajuste, la asignación de amigos mantiene varias listas libres, cada una con bloques abiertos de un solo tamaño en particular. Esto significa que cuando se recibe una solicitud de asignación, se consulta la lista que contiene bloques que son lo suficientemente grandes como para completar la solicitud, y se devuelve una ubicación abierta. Si no hay bloques libres que sean menos del doble del tamaño solicitados están disponibles, un bloque más grande se divide en dos para cumplir con los requisitos.
El término "lista libre" puede referirse a una sola lista vinculada de direcciones de memoria, o puede referirse a un tipo mucho más complejo de estructura de datos. Diferentes tipos de árboles de clasificación, si se mantienen simples y equilibrados, puede ayudar a aumentar la velocidad de encontrar bloques de memoria abiertos a costa de complicar el código fuente. Una lista vinculada puede ser más lenta que un árbol de clasificación especializado, pero crea un código de programación que es mucho más fácil de leer, depurar y modificar.
Algunos lenguajes de programación y sistemas operativos utilizan un mecanismo especial llamado recolección de basura. Este es un proceso que puede ayudar a tomar las diferentes entradas en una lista libre y consolidar los espacios libres para que sean contiguos. El efecto de prevenir la fragmentación y permitir la asignación de bloques de memoria más grandes.