C - El diseño de su propio libre() la función

Question

Hoy en día, apareció para una entrevista y el entrevistador me preguntó esto,

1. Dime la pasos cómo va a diseñar su propia función free() para desasignar la memoria asignada.
2. ¿Cómo puede ser más eficiente que la función free() predeterminada de C? ¿Qué puedes concluir?

que estaba confundido, no podía pensar en la manera de diseñar.

¿Qué opinas chicos?

---

EDIT: Puesto que necesitamos saber acerca de cómo malloc() obras, ¿puede decirme los pasos para escribir nuestra propia función malloc()

Answer 1

Esa es en realidad una pregunta bastante vaga, y esa es probablemente la razón por la que te confundiste. ¿Quiere decir, dada una implementación malloc existente, cómo trataría de desarrollar una forma más eficiente de liberar la memoria subyacente? ¿O esperaba que comenzaras a discutir diferentes tipos de implementaciones de malloc y sus beneficios y problemas? ¿Esperaba que supiera cómo funciona la memoria virtual en la arquitectura x86?

Además, por más eficiente, ¿quiere decir más eficiente en el uso del espacio o más eficiente en el tiempo? ¿Libre() tiene que ser determinista? ¿Tiene que devolver la mayor cantidad posible de memoria al sistema operativo porque se encuentra en un entorno con poca memoria y tareas múltiples? ¿Cuál es nuestro criterio aquí?

Es difícil decir por dónde empezar con una pregunta vaga como esa, aparte de comenzar a hacer sus propias preguntas para obtener una aclaración. Después de todo, para diseñar su propia función gratuita, primero debe saber cómo se implementa malloc. Entonces, lo más probable es que la pregunta era si sabías o no sobre cómo se puede implementar Malloc.

Si no está familiarizado con las funciones internas de la administración de la memoria, la forma más fácil de comenzar con la comprensión de cómo se implementa malloc es escribir primero la suya propia.

Consulte this IBM DeveloperWorks article called "Inside Memory Management" para empezar.

Pero antes de que pueda escribir su propio malloc/free, primero necesita memoria para asignar/libre. Desafortunadamente, en un SO de modo protegido, no puede direccionar directamente la memoria en la máquina. Entonces, ¿cómo lo consigue?

Solicítelo al sistema operativo. Con las funciones de memoria virtual del x86, cualquier parte de la memoria RAM o de intercambio se puede asignar a una dirección de memoria por el sistema operativo. Lo que su programa ve como memoria podría estar físicamente fragmentado en todo el sistema, pero gracias al administrador de memoria virtual del núcleo, todo parece igual.

El kernel generalmente proporciona llamadas al sistema que le permiten asignar memoria adicional para su proceso. En los sistemas operativos UNIX más antiguos, esto generalmente era brk/sbrk para hacer crecer la memoria dinámica en el borde de su proceso o reducirla, pero muchos sistemas también proporcionan mmap/munmap para simplemente mapear un gran bloque de memoria dinámica. Es solo una vez que tener acceso a un gran bloque de memoria de aspecto contiguo que necesita malloc/free para administrarlo.

Una vez que su proceso tiene algo de memoria de montón disponible, se trata de dividirlo en fragmentos, con cada fragmento conteniendo su propia meta información sobre su tamaño y posición y si está asignado o no, y luego administrar esos fragmentos. Una simple lista de estructuras, cada una con algunos campos para metainformación y una gran cantidad de bytes, podría funcionar, en cuyo caso Malloc debe ejecutar la lista hasta encontrar un trozo no asignado lo suficientemente grande (o trozos que pueda combinar), y luego mapea con más memoria si no puede encontrar un trozo suficientemente grande. Una vez que encuentras un trozo, simplemente devuelves un puntero a los datos. free() puede usar ese puntero para retroceder algunos bytes a los campos de miembros que existen en la estructura, que luego puede modificar (es decir, marcar chunk.allocated = false;).Si hay suficientes fragmentos no asignados al final de su lista, puede incluso eliminarlos de la lista y desasignar o reducir esa memoria fuera del montón del proceso.

Sin embargo, es un método realmente simple para implementar malloc. Como se puede imaginar, hay muchas maneras posibles de dividir su memoria en fragmentos y luego administrar esos fragmentos. Hay tantas formas como estructuras de datos y algoritmos. Todos están diseñados para diferentes propósitos, como limitar la fragmentación debido a trozos pequeños asignados mezclados con trozos pequeños no asignados, o asegurar que malloc y libre corren rápido (o a veces incluso más lentamente, pero de forma más lenta). Hay dlmalloc, ptmalloc, jemalloc, Hoard's malloc, y muchos más, y muchos de ellos son bastante pequeños y concisos, así que no temas leerlos. Si mal no recuerdo, "The C Programming Language" de Kernighan y Ritchie incluso usa una implementación simple de malloc como uno de sus ejemplos.

Answer 2

Puede no a ciegas diseñar free() sin saber cómo funciona bajo malloc() porque su implementación de free() necesitaría saber cómo manipular los datos de contabilidad y eso es imposible sin saber cómo se implementa malloc().

lo tanto una cuestión unswerable podría ser cómo se diseñe malloc() y free() lugar que no es una cuestión trivial, pero que pudiera responder parcialmente, por ejemplo, mediante la propuesta de algunos muy sencilla implementación de un banco de memoria que haría no ser equivalente a malloc(), por supuesto, pero indicaría su presencia de conocimiento.

Answer 3

malloc y free solo tienen un significado si su aplicación va a funcionar sobre un sistema operativo. Si desea escribir sus propias funciones de administración de memoria, debe saber cómo solicitar la memoria desde ese sistema operativo específico o puede reservar la memoria del montón inmediatamente usando el malloc existente y luego usar sus propias funciones para distribuir/redistribuir la memoria asignada. a través de su aplicación

Answer 4

Los patrones de uso de la memoria pueden ser un factor. Una implementación predeterminada de free no puede suponer nada acerca de la frecuencia con la que asigna/desasigna y qué tamaños asigna cuando lo hace.

Por ejemplo, si con frecuencia asigna y desasigna objetos que son de tamaño similar, puede ganar velocidad, eficiencia de memoria y fragmentación reducida mediante el uso de un grupo de memoria.

EDITAR: como se señaló sharptooth, solo tiene sentido diseñar diseños libres y malloc. Entonces, lo primero sería averiguar cómo se implementa malloc.

Answer 5

Un enfoque común cuando solo tiene acceso al espacio de usuario (generalmente conocido como grupo de memoria) es obtener una gran cantidad de memoria del sistema operativo cuando se inicia la aplicación. Su malloc necesita verificar qué áreas del tamaño correcto de ese grupo aún están libres (a través de alguna estructura de datos) y entregar punteros a esa memoria. Su free necesita marcar la memoria como libre nuevamente en la estructura de datos y posiblemente necesite verificar la fragmentación del grupo.

Las ventajas son que puede hacer la asignación en tiempo casi constante, el inconveniente es que su aplicación consume más memoria de la que realmente se necesita.

Answer 6

Existe una arquitectura que se supone que malloc y free deben cumplir, esencialmente una arquitectura de clase que permite que coexistan diferentes estrategias. Luego, la versión de free que se ejecuta corresponde a la versión de malloc utilizada.

Sin embargo, no estoy seguro de la frecuencia con la que se observa esta arquitectura.

Answer 7

El conocimiento del funcionamiento de malloc() es necesario para implementar free(). Puede encontrar una implementación de malloc() y free() usando la llamada al sistema sbrk() en K & R El lenguaje de programación C Capítulo 8, Sección 8.7 "Ejemplo - Un asignador de almacenamiento" pp.185-189.

Answer 8

Cuénteme los pasos de cómo diseñará su propia función free() para desasignar la memoria asignada.

#include <stdlib.h> 
#undef free 
#define free(X) my_free(X) 

inline void my_free(void *ptr) { } 

¿Cómo puede ser más eficiente que la función free() por defecto de C?

Es extremadamente rápido, requiere cero ciclos de máquina. También hace que los errores de uso después desaparezcan. Es una función free muy útil para usar en programas que se instancian como procesos por lotes de corta duración; se puede implementar de manera útil en algunas situaciones de producción.

¿Qué se puede concluir?

Realmente quiero este trabajo, pero en otra compañía.