Asignadores de listas libres Power-of-Two | Asignadores de memoria del núcleo

El poder de dos listas libres es un algoritmo para la asignación de memoria del núcleo . Se usa con frecuencia para implementar malloc() y free() en la biblioteca C de nivel de usuario. Este enfoque utiliza un conjunto de listas libres . Cada lista almacena buffers de un tamaño particular y todos los tamaños son potencias de dos . Por ejemplo, considere la figura a continuación, hay seis listas libres, almacenando búferes de tamaños 32 , 64 , 128 , 256 , 512 y 1024 bytes.

Cada búfer tiene un encabezado de un tamaño fijo que conduce a un área utilizable reducida. Cuando el búfer está libre, su encabezado almacena un puntero al siguiente búfer libre. Cuando se asigna el búfer, su encabezado apunta a la lista libre a la que debe devolverse. En algunas implementaciones, contiene el tamaño del área asignada. Esto ayuda a detectar ciertos errores, pero requiere la rutina free() para calcular la ubicación de la lista libre a partir del tamaño.

Cuando el cliente llama a malloc() , pasa el tamaño requerido como argumento. El asignador calcula el tamaño del búfer más pequeño que es lo suficientemente grande para satisfacer la solicitud. Esto implica agregar espacio para el encabezado ( 4 bytes ) al tamaño solicitado y redondear el valor resultante a la siguiente potencia de dos. Los búferes de 32 bytes satisfacen requests de 0 a 28 bytes , los búfer de 64 bytes satisfacen requests de 29 a 60 bytes , y así sucesivamente. El asignador luego elimina un búfer de la lista libre apropiada y el puntero en el encabezado apunta a la lista libre correspondiente. Devuelve a la persona que llama un puntero al byte que sigue inmediatamente al encabezado en el búfer.
La siguiente figura representa la vista conceptual debúferes asignados y punteros a los búferes.

Cuando el cliente libera el búfer, llama a la rutina free() , pasando el puntero devuelto por malloc() como argumento. El usuario no tiene que especificar el tamaño del búfer que se va a liberar. Sin embargo, es esencial liberar todo el búfer obtenido de malloc() ; no existe ninguna disposición para liberar solo una parte del colchón asignado. El método free() mueve el puntero hacia atrás cuatro bytes para acceder al encabezado. Recibe el puntero de lista libre del encabezado y coloca el búfer en esa lista. 

El asignador puede manejar una nueva solicitud malloc() para ese tamaño de una de tres maneras:

• Bloquee la solicitud hasta que se libere un búfer del tamaño adecuado.
• Satisfaga la solicitud con un búfer más grande, comenzando con la siguiente lista y continuando la búsqueda hasta que encuentre una lista que no esté vacía.
• Obtenga memoria adicional del asignador de nivel de página para generar más búferes de ese tamaño.

ventajas :

• El algoritmo es simple y razonablemente rápido.
• El objetivo principal de este algoritmo es evitar las largas búsquedas lineales del método del mapa de recursos y eliminar por completo el problema de la fragmentación.
• El asignador también presenta una interfaz de programación familiar, con la importante ventaja de que la rutina free() no necesita recibir el tamaño del búfer como argumento. Como resultado, un búfer asignado puede pasarse a otras funciones y subsistemas y finalmente liberarse usando solo el puntero al búfer.
• La interfaz no permite que un cliente libere solo una parte del búfer asignado.

Desventajas :

• El redondeo de requests a la siguiente potencia de dos a menudo deja mucho espacio sin usar en el búfer, lo que resulta en una mala utilización de la memoria.
• El problema empeora debido a la necesidad de almacenar el encabezado en los búfer asignados. Por ejemplo, una solicitud de 512 bytes consumiría un búfer de 1024 bytes .
• No existe ninguna disposición para fusionar buffers libres adyacentes para satisfacer requests más grandes. Generalmente, el tamaño de cada búfer permanece fijo durante su vida útil. La única flexibilidad es que, a veces, se pueden usar grandes búferes para requests pequeñas.
• Aunque algunas implementaciones permiten que el asignador robe memoria del sistema de paginación , no existe ninguna disposición para devolver los búfer libres excedentes al asignador de nivel de página.