operating system - Aparte de malloc/free ¿un programa necesita el sistema operativo para proporcionar algo más?
operating-system kernel (7)
Estoy trabajando en el diseño del kernel (que en realidad voy a llamar el "núcleo" para ser diferente, pero básicamente es el mismo) para un sistema operativo en el que estoy trabajando. Los detalles del sistema operativo en sí son irrelevantes si no puedo poner en marcha tareas múltiples, administración de memoria y otras cosas básicas, así que tengo que trabajar en eso primero. Tengo algunos questinos sobre el diseño de una rutina malloc.
Me imagino que malloc () va a ser una parte del kernel en sí (me estoy inclinando hacia esto) o una parte del programa, pero voy a tener que escribir mi propia implementación de la biblioteca estándar C, ya sea manera, entonces puedo escribir un malloc. Mi pregunta es bastante simple en este sentido, ¿cómo gestiona C (o C ++) su montón?
Lo que siempre me han enseñado en las clases de teoría es que el montón es una pieza de memoria en constante expansión, comenzando en una dirección específica y en muchos sentidos comportándose como una pila. De esta forma, sé que las variables declaradas en el alcance global están en el principio, y más variables se "empujan" al heap como se declaran en sus respectivos ámbitos, y las variables que salen del alcance simplemente se dejan en el espacio de memoria, pero ese espacio está marcado como libre, por lo que el montón puede expandirse más si es necesario.
Lo que necesito saber es cómo es que C realmente maneja un montón de expansión dinámica de esta manera. ¿Hace un programa compilado C sus propias llamadas a una rutina malloc y maneja su propio montón, o necesito proporcionarle un espacio expandido automáticamente? Además, ¿cómo sabe el programa C dónde comienza el montón?
Ah, y sé que los mismos conceptos se aplican a otros idiomas, pero me gustaría que hubiera algún ejemplo en C / C ++ porque me siento más cómodo con ese idioma. También me gustaría no preocuparme por otras cosas como la pila, ya que creo que puedo manejar cosas como esta por mi cuenta.
Entonces, supongo que mi verdadera pregunta es, aparte de malloc / free (que maneja obtener y liberar páginas para sí mismo, etc.) ¿un programa necesita el sistema operativo para proporcionar algo más?
¡Gracias!
EDITAR Estoy más interesado en cómo C usa malloc en relación con el montón que en el funcionamiento real de la rutina malloc. Si ayuda, estoy haciendo esto en x86, pero C es un compilador cruzado, así que no debería importar. ^ _ ^
EDITAR ADEMÁS: entiendo que pueda estar confundiendo los términos. Me enseñaron que el "montón" era donde el programa almacena cosas como variables globales / locales. Estoy acostumbrado a lidiar con una "pila" en la programación de ensamblaje, y me di cuenta de que probablemente sea eso lo que quiero decir. Un poco de investigación por mi parte muestra que "montón" se usa más comúnmente para referirse a la memoria total que un programa ha asignado para sí mismo, o, el número total (y orden) de páginas de memoria que el sistema operativo ha proporcionado.
Entonces, con eso en mente, ¿cómo trato con una pila en constante expansión? (Parece que mi clase de teoría C fue ligeramente ... defectuosa).
¿Estás confundiendo el montón y la pila?
Lo pregunto porque mencionas "una pieza de memoria en constante expansión", alcance y variables de empuje en el montón a medida que se declaran. Eso seguramente parece que estás hablando de la pila.
En las declaraciones de implementación C más comunes de variables automáticas como
int i;
generalmente van a resultar en que me asignen en la pila. En general malloc no se involucrará a menos que lo invoque explícitamente, o alguna invocación de biblioteca que haga lo invoca.
Recomiendo consultar "Expert C Programming" de Peter Van Der Linden para obtener información general sobre cómo los programas C suelen funcionar con la pila y el montón.
En general, la biblioteca C maneja la implementación de malloc , solicitando memoria del sistema operativo (ya sea a través de mmap anónimo o, en sistemas más antiguos, sbrk ) según sea necesario. Por lo tanto, su lado kernel debe manejar la asignación de páginas enteras a través de algo así como uno de esos medios.
Luego depende de malloc distribuir la memoria de una manera que no fragmente demasiado la memoria libre. Sin embargo, no estoy demasiado optimista con los detalles de esto; sin embargo, el término arena viene a la mente. Si puedo buscar una referencia, actualizaré esta publicación.
Hay múltiples formas de abordar el problema.
La mayoría de las veces los programas C tienen su propia funcionalidad malloc / free. Ese funcionará para los objetos pequeños. Inicialmente (y tan pronto como se agote la memoria), el administrador de memoria le pedirá al sistema operativo más memoria. Los métodos tradicionales para hacer esto son mmap y sbrk en las variantes de Unix (GlobalAlloc / LocalAlloc en Win32).
Sugiero que eche un vistazo al asignador de memoria Doug Lea (google: dlmalloc) desde un punto de vista del proveedor de memoria (por ejemplo, OS). Ese asignador es de primera clase en uno muy bueno y tiene ganchos para todos los sistemas operativos principales. Si desea saber qué espera un asignador de alto rendimiento de un sistema operativo, este es su primera elección.
Lectura obligatoria: Knuth - Art of Computer Programming, Volumen 1, Capítulo 2, Sección 2.5. De lo contrario, podría leer Kernighan & Ritchie "The C Programming Language" para ver una implementación; o bien, podría leer Plauger "The Standard C Library" para ver otra implementación.
Creo que lo que debe hacer dentro de su núcleo será un poco diferente de lo que ven los programas fuera del núcleo. En particular, la asignación de memoria interna para programas se ocupará de la memoria virtual, etc., mientras que los programas que están fuera del código simplemente verán los resultados de lo que el núcleo ha proporcionado.
malloc generalmente se implementa en el tiempo de ejecución de C en el espacio de usuario, y depende de llamadas específicas del sistema operativo para mapear en páginas de memoria virtual. El trabajo de malloc y free es administrar esas páginas de memoria, que son de tamaño fijo (normalmente 4 KB, pero a veces más grandes), y cortarlas en pedazos para que las aplicaciones puedan usarlas.
Ver, por ejemplo, la implementación de GNU libc .
Para una implementación mucho más simple, consulte la clase de sistemas operativos MIT del año pasado. Específicamente, vea el folleto final del laboratorio y eche un vistazo a lib/malloc.c . Este código usa el sistema operativo JOS desarrollado en la clase. La forma en que funciona es que se lee a través de las tablas de páginas (proporcionadas de solo lectura por el sistema operativo), en busca de rangos de direcciones virtuales no asignados. Luego usa las llamadas al sistema sys_page_alloc y sys_page_unmap para mapear y desasignar páginas en el proceso actual.
Lea sobre administración de memoria virtual (paginación). Es altamente específico de la CPU y cada sistema operativo implementa la administración de VM especialmente para cada CPU compatible. Si está escribiendo su sistema operativo para x86 / amd64, lea sus respectivos manuales.
¡¡Peligro PELIGRO!! Si está considerando siquiera intentar el desarrollo del kernel, debe ser muy consciente del costo de sus recursos y su disponibilidad relativamente limitada ...
Una cosa sobre la recursividad, es que es muy, muy costosa (al menos en tierra de kernel), no vas a ver muchas funciones escritas para simplemente continuar sin restricciones, o de lo contrario tu kernel entrará en pánico.
Para subrayar mi punto aquí, (en .com heh), revisa esta publicación del blog NT Debugging sobre desbordamiento de la pila kernel, específicamente,
· En plataformas basadas en x86, la pila de kernel-mode es de 12 K.
· En plataformas basadas en x64, la pila de kernel-mode es 24K . (Las plataformas basadas en x64 incluyen sistemas con procesadores que utilizan la arquitectura AMD64 y procesadores que utilizan la arquitectura Intel EM64T).
· En las plataformas basadas en Itanium, la pila en modo kernel es de 32K con una tienda de respaldo de 32K .
Eso es realmente, no mucho;
Los sospechosos de siempre
1. Usando la pila liberalmente.
2. Funciones de llamada recursivamente.
Si lees un poco sobre el blog, verás cuán duro puede ser el desarrollo del kernel con un conjunto bastante único de problemas. Tu clase de teoría no estaba mal, era simple, simple. ;)
Pasar de la teoría -> el desarrollo del kernel es tan significativo como sea posible en un cambio de contexto (¡quizás guarde alguna interacción del hipervisor en la mezcla!).
De todos modos, nunca asuma, valide y pruebe sus expectativas.