Además de malloc / free, ¿un programa necesita el sistema operativo para proporcionar algo más?

https://stackoverflow.com/questions/196136

10-07-2019
|

Pregunta

Estoy trabajando en el diseño del kernel (que en realidad voy a llamar al '' núcleo '' solo para ser diferente, pero es básicamente lo mismo) para un sistema operativo en el que estoy trabajando. Los detalles del sistema operativo en sí son irrelevantes si no puedo hacer que la multitarea, la administración de memoria y otras cosas básicas estén en funcionamiento, por lo que primero tengo que trabajar en eso. Tengo algunos questinos sobre el diseño de una rutina malloc.

Calculo que malloc () va a ser parte del núcleo en sí (me inclino por esto) o parte del programa, pero voy a tener que escribir mi propia implementación de C biblioteca estándar de cualquier manera, así que puedo escribir un malloc. Mi pregunta es realmente bastante simple a este respecto, ¿cómo maneja 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, que comienza en una dirección específica y en muchos sentidos se comporta como una pila. De esta manera, sé que las variables declaradas en el alcance global están al principio, y más variables son "empujadas". en el montón tal como se declaran en sus respectivos ámbitos, y las variables que quedan fuera del alcance simplemente se dejan en el espacio de memoria, pero ese espacio se marca como libre para que el montón pueda expandirse más si es necesario.

Lo que necesito saber es, ¿cómo demonios C maneja realmente un montón de expansión dinámica de esta manera? ¿Un programa C compilado realiza sus propias llamadas a una rutina malloc y maneja su propio montón, o necesito proporcionarle un espacio que se expande 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 lenguajes, pero me gustaría que cualquier ejemplo esté en C / C ++ porque me siento más cómodo con ese lenguaje. 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 por sí mismo, etc.) ¿necesita un programa el sistema operativo para proporcionar algo más?

¡Gracias!

EDIT 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 de malloc. Si ayuda, estoy haciendo esto en x86, pero C es un compilador cruzado, por lo que no debería importar. ^ _ ^

EDITAR ADEMÁS: Entiendo que me pueden confundir los términos. Me enseñaron que el "montón" fue donde el programa almacenaba cosas como variables globales / locales. Estoy acostumbrado a lidiar con una " pila " en programación de ensamblaje, y me di cuenta de que probablemente lo digo en su lugar. Una pequeña investigación de mi parte muestra que '' montón '' se usa más comúnmente para referirse a la memoria total que un programa se ha asignado a sí mismo, o al 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 cada vez más amplia? (parece que mi clase de teoría C fue levemente ... defectuosa).

Solución

malloc generalmente se implementa en el tiempo de ejecución C en el espacio de usuario, confiando en 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 (generalmente 4 KB, pero a veces más grandes), y cortarlas y cortarlas en cuadritos. piezas que las aplicaciones pueden usar.

Vea, por ejemplo, la implementación de GNU libc .

Para una implementación mucho más simple, consulte la sistemas operativos MIT de la última año. Específicamente, vea el folleto de laboratorio final y eche un vistazo a lib / malloc.c . Este código utiliza el sistema operativo JOS desarrollado en la clase. La forma en que funciona es que lee las tablas de páginas (proporcionadas de solo lectura por el sistema operativo), buscando rangos de direcciones virtuales sin asignar. Luego utiliza las llamadas del sistema sys_page_alloc y sys_page_unmap para asignar y desasignar páginas en el proceso actual.

Otros consejos

Hay varias 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).

Le sugiero que eche un vistazo al asignador de memoria Doug Lea ( google: dlmalloc) desde el punto de vista de un proveedor de memoria (p. ej., SO). Ese asignador es de primera clase en uno muy bueno y tiene ganchos para todos los principales sistemas operativos. Si desea saber qué espera un asignador de alto rendimiento de un sistema operativo, este es su código.

¿Estás confundiendo el montón y la pila?

Pregunto porque mencionas "un pedazo de memoria cada vez mayor", alcance y empujando variables en el montón a medida que se declaran. Eso seguro suena como si realmente estuvieras hablando de la pila.

En las implementaciones de C más comunes, las declaraciones de variables automáticas como

int i;

generalmente dará como resultado que se me asigne en la pila. En general, malloc no se involucrará a menos que lo invoque explícitamente, o alguna llamada a la biblioteca que realice lo invoca.

Recomiendo mirar " Programación experta C " por Peter Van Der Linden para obtener información sobre cómo los programas en C suelen funcionar con la pila y el montón.

Lectura obligatoria: Knuth - Art of Computer Programming, Volumen 1, Capítulo 2, Sección 2.5. De lo contrario, podría leer Kernighan & amp; Ritchie " El lenguaje de programación C " para ver una implementación; o puede leer Plauger " The Standard C Library " para ver otra implementación.

Creo que lo que necesita hacer dentro de su núcleo será algo diferente de lo que ven los programas fuera del núcleo. En particular, la asignación de memoria en el núcleo para los programas se ocupará de la memoria virtual, etc., mientras que los programas fuera del código simplemente ven los resultados de lo que el núcleo ha proporcionado.

Lea sobre la administración de memoria virtual (paginación). Es altamente específico de la CPU, y cada sistema operativo implementa la gestión de VM especialmente para cada CPU compatible. Si está escribiendo su sistema operativo para x86 / amd64, lea sus respectivos manuales.

Generalmente, 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 del núcleo de las cosas debe manejar la asignación de páginas enteras a través de algo como uno de esos medios.



 Entonces depende de  malloc  repartir la memoria de una manera que no fragmente demasiado la memoria libre. Sin embargo, no estoy demasiado  au fait  con los detalles de esto; sin embargo, me viene a la mente el término  arena . Si puedo buscar una referencia, actualizaré esta publicación.



	
		
	
	
			 Peligro ¡¡Peligro !! Si incluso está considerando intentar el desarrollo del núcleo, debe tener muy en cuenta el  costo  de sus recursos y su disponibilidad relativamente limitada ... 

 Una cosa sobre la recursividad es que es muy costosa (al menos en la tierra del kernel), no verá muchas funciones escritas para simplemente continuar sin ayuda, o su kernel entrará en pánico. 

 Para subrayar mi punto aquí, (en stackoverflow.com heh), mira esta publicación en  blog de depuración de NT  sobre desbordamientos de pila de kernel, específicamente, 


   · En plataformas basadas en x86, el
  la pila en modo kernel es  12K . 
  
   · En plataformas basadas en x64, el
  la pila en modo kernel es  24K . (basado en x64
  plataformas incluyen sistemas con
  procesadores que utilizan el AMD64
  arquitectura y procesadores que utilizan el
  Arquitectura Intel EM64T). 
  
   · En plataformas basadas en Itanium, el
  la pila en modo kernel es  32K  con un  32K 
  tienda de respaldo. 


 Eso es realmente, no mucho; 


    Los sospechosos habituales  
  
  
  
   1. Usando la pila generosamente. 
  
   2. Llamar a funciones de forma recursiva. 


 Si lees un poco el blog, verás lo difícil que puede ser el desarrollo del núcleo con un conjunto de problemas bastante único. Tu clase de teoría no estaba mal, era simple, simple. ;) 

 Para ir de la teoría - > el desarrollo del kernel es lo más significativo posible de un cambio de  contexto  (¡tal vez guarde alguna interacción de hipervisor en la mezcla!). 

 De todos modos, nunca asuma, valide y pruebe sus expectativas.



	
		
			Licenciado bajo: CC-BY-SA con atribución
			No afiliado a StackOverflow