c++ - informatica - ¿Es la memoria de pila contigua?
pilas estructura de datos ejemplos (3)
La pila para un subproceso dado suele ser contigua en la memoria virtual (en Linux y sistemas similares, y en el modo de usuario en Windows). El kernel de Windows (en Windows Vista y superior) y z/OS permiten pilas no contiguas en la memoria virtual, y GCC 4.6 también lo permitirá . El compilador no necesita mover la pila en absoluto, incluso para los sistemas que tienen direcciones virtuales no contiguas para la pila; simplemente cambian donde se asignan nuevas partes. Sin embargo, el sistema operativo puede reasignar las páginas físicas a las virtuales para que la pila no sea contigua en la memoria física, aunque esté en la memoria virtual.
¿Cómo hace el compilador para hacer que la memoria de la pila sea contigua, hace que la memoria se mueva cada vez que el programa se está ejecutando o reserva la memoria en la pila que necesita el programa antes de ejecutarlo?
No hay requisitos para que la pila sea contigua en el idioma del sistema operativo o el hardware.
Desafío a cualquiera a que localice una referencia que explícitamente diga que esto es un requisito.
Ahora muchas implementaciones usan memoria contigua porque es simple. Esta es también la forma en que se enseña el concepto de pila a los estudiantes de CS (la pila crece hacia abajo y el montón se expande). Pero no hay requisitos para hacer esto. Creo que MS incluso experimentó con la colocación de marcos de pila en ubicaciones aleatorias en el montón para evitar ataques con las técnicas de aplastamiento de pila deliberadas utilizadas.
El único requisito de la pila es que los marcos están vinculados. De este modo, se permite que la pila empuje / haga estallar los marcos a medida que los ámbitos se ingresan / se dejan.
Pero todo esto es ortogonal a la pregunta original.
El compilador no intenta forzar la pila para que esté en la memoria contigua. No hay requisitos en el nivel de idioma que requieran que la pila sea contigua.
¿Cómo se implementa la pila generalmente.
Si esta era la pregunta. Entonces obtendría una respuesta más detallada y precisa de la comunidad.
Tiene su espacio de direcciones de memoria, digamos que se ejecuta de 1 a 100. Asigna su pila de 1 en adelante y su montón de 100 hacia abajo. Ok hasta ahora?
Debido a la naturaleza misma de la pila, siempre es compacta (no tiene agujeros). Eso sucede porque todo lo que está en la pila es el contexto de alguna función que fue llamada. Cada vez que una función sale, su contexto se elimina de la parte superior de la pila y volvemos a la función anterior. Creo que puedes entenderlo bien si obtienes un depurador y simplemente sigues las llamadas de función teniendo en cuenta cómo debe ser la pila.
Heap, por otro lado, no se comporta tan bien, digamos que hemos reservado memoria de 70 a 100 para heap. Podemos asignar un bloque de 4 bytes allí y puede ir de 70 a 74, luego asignamos 4 bytes más y ahora tenemos memoria asignada de 70 a 78. Pero esa memoria puede ser desasignada en cualquier punto del programa. Por lo tanto, podría desasignar los 4 bytes que asignó al principio, creando así un agujero.
Así es como pasan las cosas en tu espacio de direcciones. Hay una tabla que el kernel mantiene que mapea páginas del espacio de direcciones a páginas en memoria real. Como probablemente habrá notado, no puede esperar tener todo configurado de manera agradable cuando tiene más de un programa en ejecución. Entonces, lo que hace el kernel es hacer que cada proceso piense que todo el espacio de direcciones es memoria contigua (no pensemos en los dispositivos asignados en memoria por ahora), aunque podría estar asignado de forma no contigua en la memoria.
Espero haber dado un panorama razonable sobre el tema, pero probablemente hay mejores autores que yo, que probablemente disfrutará mucho más leyendo. Así que busque textos en la memoria virtual, podría ser un buen punto de partida para que entienda lo que quiere. Hay varios libros que lo describirán con mayor o menor detalle. Algunos que conozco: Organización de computadoras estructurada, por tanenbaum; Concepto de sistema operativo, por Silberschatz. Estoy bastante seguro de que Knuth lo discute en sus libros de algoritmos también. Si te sientes aventurero, puedes intentar leer su implementación x86 en manuales de inteligencia.