¿Qué y dónde están la pila y el montón?

8105

Los libros de lenguaje de programación explican que los tipos de valor se crean en la pila y los tipos de referencia se crean en el montón , sin explicar cuáles son estas dos cosas. No he leído una explicación clara de esto. Entiendo lo que es una pila . Pero,

  • ¿Dónde y qué están (físicamente en la memoria de una computadora real)?
  • ¿En qué medida están controlados por el sistema operativo o el lenguaje en tiempo de ejecución?
  • ¿Cuál es su alcance?
  • ¿Qué determina el tamaño de cada uno de ellos?
  • ¿Qué lo hace a uno más rápido?
mattshane
fuente
175
Una buena explicación se puede encontrar aquí. ¿Cuál es la diferencia entre una pila y un montón?
Songo
12
También (realmente) bueno: codeproject.com/Articles/76153/… (la parte de pila / montón)
Ben
3
Relacionado, ver Choque de pila . Las correcciones de Stack Clash afectaron algunos aspectos de las variables del sistema y comportamientos como rlimit_stack. También vea Red Hat Issue 1463241
jww
3
@mattshane Las definiciones de pila y montón no dependen de ningún tipo de valor y referencia. En otras palabras, la pila y el montón se pueden definir completamente incluso si los tipos de valor y referencia nunca existieron. Además, al comprender los valores y los tipos de referencia, la pila es solo un detalle de implementación. Per Eric Lippert: The Stack es un detalle de implementación, primera parte .
Mateo

Respuestas:

5968

La pila es la memoria reservada como espacio reutilizable para un hilo de ejecución. Cuando se llama a una función, se reserva un bloque en la parte superior de la pila para variables locales y algunos datos de contabilidad. Cuando esa función regresa, el bloque no se usa y se puede usar la próxima vez que se llame a una función. La pila siempre está reservada en un orden LIFO (último en entrar, primero en salir); el bloque reservado más recientemente es siempre el siguiente bloque que se liberará. Esto hace que sea realmente sencillo hacer un seguimiento de la pila; liberar un bloque de la pila no es más que ajustar un puntero.

El montón es la memoria reservada para la asignación dinámica. A diferencia de la pila, no hay un patrón obligatorio para la asignación y desasignación de bloques del montón; Puede asignar un bloque en cualquier momento y liberarlo en cualquier momento. Esto hace que sea mucho más complejo hacer un seguimiento de qué partes del montón están asignadas o libres en un momento dado; Hay muchos asignadores de almacenamiento dinámico disponibles para ajustar el rendimiento del almacenamiento dinámico para diferentes patrones de uso.

Cada subproceso obtiene una pila, mientras que normalmente solo hay un montón para la aplicación (aunque no es raro tener varios montones para diferentes tipos de asignación).

Para responder sus preguntas directamente:

¿En qué medida están controlados por el sistema operativo o el tiempo de ejecución del lenguaje?

El sistema operativo asigna la pila para cada subproceso de nivel de sistema cuando se crea el subproceso. Normalmente, el tiempo de ejecución del lenguaje llama al sistema operativo para asignar el montón a la aplicación.

¿Cuál es su alcance?

La pila está unida a un hilo, por lo que cuando el hilo sale, la pila se recupera. El montón generalmente se asigna al inicio de la aplicación por el tiempo de ejecución, y se recupera cuando la aplicación (técnicamente proceso) se cierra.

¿Qué determina el tamaño de cada uno de ellos?

El tamaño de la pila se establece cuando se crea un hilo. El tamaño del montón se establece en el inicio de la aplicación, pero puede crecer a medida que se necesita espacio (el asignador solicita más memoria del sistema operativo).

¿Qué lo hace a uno más rápido?

La pila es más rápida porque el patrón de acceso hace que sea trivial asignar y desasignar memoria de ella (un puntero / entero simplemente se incrementa o disminuye), mientras que el montón tiene una contabilidad mucho más compleja involucrada en una asignación o desasignación. Además, cada byte en la pila tiende a reutilizarse con mucha frecuencia, lo que significa que tiende a asignarse a la memoria caché del procesador, lo que lo hace muy rápido. Otro golpe de rendimiento para el montón es que el montón, que es principalmente un recurso global, generalmente tiene que ser seguro para múltiples subprocesos, es decir, cada asignación y desasignación debe estar, típicamente, sincronizada con "todos" otros accesos de montón en el programa.

Una demostración clara:
Fuente de la imagen: vikashazrati.wordpress.com

Jeff Hill
fuente
74
Buena respuesta, pero creo que debería agregar que mientras el sistema operativo asigna la pila cuando se inicia el proceso (suponiendo la existencia de un sistema operativo), el programa la mantiene en línea. Esta es otra razón por la que la pila también es más rápida: las operaciones de inserción y extracción suelen ser una instrucción de máquina, y las máquinas modernas pueden realizar al menos 3 de ellas en un ciclo, mientras que la asignación o liberación del montón implica llamar al código del sistema operativo.
sqykly
276
Estoy realmente confundido por el diagrama al final. Pensé que lo tenía hasta que vi esa imagen.
Sina Madani
10
@Anarelle el procesador ejecuta instrucciones con o sin un sistema operativo. Un ejemplo cercano a mi corazón es el SNES, que no tenía llamadas API, ni sistema operativo como lo conocemos hoy, pero tenía una pila. Asignar en una pila es sumar y restar en estos sistemas y eso está bien para las variables destruidas cuando son reventadas al regresar de la función que las creó, pero restringe eso a, digamos, un constructor, del cual el resultado no puede ser simplemente tirado a la basura. Para eso necesitamos el montón, que no está vinculado a la llamada y el retorno. La mayoría de los sistemas operativos tienen un montón de API, no hay razón para hacerlo por su cuenta
2016
2
"pila es la memoria reservada como espacio de memoria virtual". Frio. Pero, ¿dónde está realmente "puesto a un lado" en términos de estructura de memoria Java? ¿Es memoria Heap / Memoria no Heap / Otro (estructura de memoria Java según betsol.com/2017/06/… )
Jatin Shashoo
44
@JatinShashoo Java runtime, como intérprete de código de bytes, agrega un nivel más de virtualización, por lo que lo que usted mencionó es solo el punto de vista de la aplicación Java. Desde el punto de vista del sistema operativo, todo eso es solo un montón, donde el proceso de tiempo de ejecución de Java asigna parte de su espacio como memoria "sin montón" para el código de bytes procesado. El resto de ese almacenamiento dinámico a nivel de sistema operativo se utiliza como almacenamiento dinámico a nivel de aplicación, donde se almacenan los datos del objeto.
kbec
2350

Apilar:

  • Almacenado en la memoria RAM de la computadora al igual que el montón.
  • Las variables creadas en la pila quedarán fuera de alcance y se desasignarán automáticamente.
  • Mucho más rápido de asignar en comparación con las variables en el montón.
  • Implementado con una estructura de datos de pila real.
  • Almacena datos locales, direcciones de retorno, utilizadas para pasar parámetros.
  • Puede tener un desbordamiento de pila cuando se usa demasiado de la pila (principalmente de recursión infinita o demasiado profunda, asignaciones muy grandes)
  • Los datos creados en la pila se pueden usar sin punteros.
  • Usaría la pila si sabe exactamente cuántos datos necesita asignar antes del tiempo de compilación y no es demasiado grande.
  • Generalmente tiene un tamaño máximo ya determinado cuando se inicia su programa.

Montón:

  • Almacenado en la RAM de la computadora al igual que la pila.
  • En C ++, las variables en el montón deben destruirse manualmente y nunca quedar fuera de alcance. Los datos se libera con delete, delete[]ofree .
  • Más lento para asignar en comparación con las variables en la pila.
  • Se usa bajo demanda para asignar un bloque de datos para uso del programa.
  • Puede tener fragmentación cuando hay muchas asignaciones y desasignaciones.
  • En C ++ o C, los datos creados en el montón se señalarán mediante punteros y se asignarán con newo mallocrespectivamente.
  • Puede tener errores de asignación si se solicita que se asigne un búfer demasiado grande.
  • Usaría el montón si no sabe exactamente cuántos datos necesitará en el tiempo de ejecución o si necesita asignar muchos datos.
  • Responsable de fugas de memoria.

Ejemplo:

int foo()
{
  char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
  bool b = true; // Allocated on the stack.
  if(b)
  {
    //Create 500 bytes on the stack
    char buffer[500];

    //Create 500 bytes on the heap
    pBuffer = new char[500];

   }//<-- buffer is deallocated here, pBuffer is not
}//<--- oops there's a memory leak, I should have called delete[] pBuffer;
Brian R. Bondy
fuente
31
El puntero pBuffer y el valor de b se encuentran en la pila, y probablemente se asignan en la entrada de la función. Dependiendo del compilador, el buffer también puede asignarse en la entrada de la función.
Andy
36
Es un error común pensar que el Cidioma, tal como lo define el C99estándar del idioma (disponible en open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf ), requiere una "pila". De hecho, la palabra 'apilar' ni siquiera aparece en el estándar. Esto responde que el Cuso de la pila de wrt / to es verdadero en general, pero de ninguna manera es requerido por el lenguaje. Consulte knosof.co.uk/cbook/cbook.html para obtener más información y, en particular, cómo Cse implementa en arquitecturas de bolas extrañas como en.wikipedia.org/wiki/Burroughs_large_systems
johne
55
@Brian Debe explicar por qué el búfer [] y el puntero pBuffer se crean en la pila y por qué los datos de pBuffer se crean en el montón. Creo que algunas personas podrían confundirse con su respuesta, ya que podrían pensar que el programa está instruyendo específicamente que la memoria se asigne en la pila frente al montón, pero este no es el caso. ¿Es porque Buffer es un tipo de valor mientras que pBuffer es un tipo de referencia?
Howiecamp
99
@Remover: ningún puntero contiene una dirección y puede apuntar a algo en el montón o en la pila por igual. new, malloc y algunas otras funciones similares a malloc se asignan en el montón y devuelven la dirección de la memoria asignada. ¿Por qué querrías asignar en el montón? Para que su memoria no se salga del alcance y se libere hasta que lo desee.
Brian R. Bondy
35
"Responsable de las pérdidas de memoria" - ¡Los montones no son responsables de las pérdidas de memoria! ¡Los codificadores perezosos / olvidadizos / ex-java / codificadores que no dan una mierda son!
Laz
1371

El punto más importante es que montón y pila son términos genéricos para las formas en que se puede asignar memoria. Se pueden implementar de muchas maneras diferentes, y los términos se aplican a los conceptos básicos.

  • En una pila de elementos, los elementos se colocan uno encima del otro en el orden en que se colocaron allí, y solo puede quitar el superior (sin volcar todo el objeto).

    Apilar como una pila de papeles

    La simplicidad de una pila es que no necesita mantener una tabla que contenga un registro de cada sección de memoria asignada; la única información de estado que necesita es un puntero único al final de la pila. Para asignar y desasignar, simplemente incremente y disminuya ese puntero único. Nota: a veces se puede implementar una pila para comenzar en la parte superior de una sección de memoria y extenderse hacia abajo en lugar de crecer hacia arriba.

  • En un montón, no hay un orden particular en la forma en que se colocan los elementos. Puede acceder y eliminar elementos en cualquier orden porque no hay un elemento 'superior' claro.

    Montón como un montón de regaliz allsorts

    La asignación del montón requiere mantener un registro completo de qué memoria está asignada y qué no, así como un poco de mantenimiento general para reducir la fragmentación, encontrar segmentos de memoria contiguos lo suficientemente grandes como para ajustarse al tamaño solicitado, y así sucesivamente. La memoria se puede desasignar en cualquier momento dejando espacio libre. A veces, un asignador de memoria realizará tareas de mantenimiento, como desfragmentar la memoria moviendo la memoria asignada o recolectando basura, identificando en tiempo de ejecución cuando la memoria ya no está dentro del alcance y desasignándola.

Estas imágenes deberían hacer un trabajo bastante bueno al describir las dos formas de asignar y liberar memoria en una pila y un montón. Ñam!

  • ¿En qué medida están controlados por el sistema operativo o el tiempo de ejecución del lenguaje?

    Como se mencionó, heap y stack son términos generales, y se pueden implementar de muchas maneras. Los programas de ordenador tienen típicamente una pila llamada pila de llamadas , que almacena la información relevante para la función actual como un puntero a cualquier función que fue llamado, y cualquier variable local. Debido a que las funciones llaman a otras funciones y luego regresan, la pila crece y se reduce para retener información de las funciones más abajo en la pila de llamadas. Un programa realmente no tiene control de tiempo de ejecución sobre él; está determinado por el lenguaje de programación, el sistema operativo e incluso la arquitectura del sistema.

    Un montón es un término general utilizado para cualquier memoria que se asigne de forma dinámica y aleatoria; es decir, fuera de servicio. El sistema operativo suele asignar la memoria, y la aplicación llama a las funciones API para hacer esta asignación. Se requiere un poco de sobrecarga para administrar la memoria asignada dinámicamente, que generalmente se maneja mediante el código de tiempo de ejecución del lenguaje de programación o el entorno utilizado.

  • ¿Cuál es su alcance?

    La pila de llamadas es un concepto de nivel tan bajo que no se relaciona con el 'alcance' en el sentido de la programación. Si desarma algún código, verá referencias de estilo de puntero relativas a partes de la pila, pero en lo que respecta a un lenguaje de nivel superior, el idioma impone sus propias reglas de alcance. Sin embargo, un aspecto importante de una pila es que una vez que una función regresa, cualquier cosa local a esa función se libera inmediatamente de la pila. Eso funciona de la manera que esperarías que funcione dado el funcionamiento de tus lenguajes de programación. En un montón, también es difícil de definir. El alcance es lo que expone el sistema operativo, pero su lenguaje de programación probablemente agrega sus reglas sobre qué es un "alcance" en su aplicación. La arquitectura del procesador y el sistema operativo utilizan direccionamiento virtual, que el procesador traduce a direcciones físicas y hay fallas de página, etc. Realizan un seguimiento de qué páginas pertenecen a qué aplicaciones. Sin embargo, nunca debe preocuparse realmente por esto, ya que solo usa cualquier método que use su lenguaje de programación para asignar y liberar memoria, y verificar si hay errores (si la asignación / liberación falla por algún motivo).

  • ¿Qué determina el tamaño de cada uno de ellos?

    Nuevamente, depende del idioma, el compilador, el sistema operativo y la arquitectura. Una pila suele estar preasignada, porque por definición debe ser memoria contigua. El compilador de idiomas o el sistema operativo determinan su tamaño. No almacena grandes cantidades de datos en la pila, por lo que será lo suficientemente grande como para que nunca se use por completo, excepto en casos de recursión interminable no deseada (por lo tanto, "desbordamiento de pila") u otras decisiones de programación inusuales.

    Un montón es un término general para cualquier cosa que pueda asignarse dinámicamente. Dependiendo de la forma en que lo mires, cambia constantemente de tamaño. De todos modos, en los procesadores y sistemas operativos modernos, la forma exacta en que funciona es muy abstracta, por lo que normalmente no debe preocuparse mucho por cómo funciona en el fondo, excepto que (en los idiomas que le permite) no debe usar memoria que aún no ha asignado o memoria que ha liberado.

  • ¿Qué lo hace a uno más rápido?

    La pila es más rápida porque toda la memoria libre siempre es contigua. No es necesario mantener una lista de todos los segmentos de memoria libre, solo un puntero a la parte superior actual de la pila. Los compiladores generalmente almacenan este puntero en un registro especial y rápido para este propósito. Además, las operaciones posteriores en una pila generalmente se concentran en áreas de memoria muy cercanas, lo que a un nivel muy bajo es bueno para la optimización de las memorias caché en el procesador.

thomasrutter
fuente
20
David: No estoy de acuerdo con que sea una buena imagen o que "apilar hacia abajo" sea un buen término para ilustrar el concepto. Cuando agrega algo a una pila, los otros contenidos de la pila no se empujan hacia abajo, permanecen donde están.
thomasrutter
8
Esta respuesta incluye un gran error. Las variables estáticas no se asignan en la pila. Vea mi respuesta [link] stackoverflow.com/a/13326916/1763801 para aclaraciones. está equiparando variables "automáticas" con variables "estáticas", pero no son todas iguales
davec
13
Específicamente, usted dice que las "variables locales asignadas estáticamente" se asignan en la pila. En realidad, se asignan en el segmento de datos. Solo las variables asignadas automáticamente (que incluyen la mayoría pero no todas las variables locales y también cosas como los parámetros de función pasados ​​por valor en lugar de por referencia) se asignan en la pila.
davec
99
Me acabo de dar cuenta de que tienes razón: en C, la asignación estática es algo separado en lugar de un término para cualquier cosa que no sea dinámica . He editado mi respuesta, gracias.
thomasrutter
55
No solo C. C., Pascal, Python y muchos otros tienen las nociones de asignación estática versus automática versus dinámica. Decir "asignación estática" significa lo mismo en casi todas partes. En ningún idioma, la asignación estática significa "no dinámico". Desea el término asignación "automática" para lo que está describiendo (es decir, las cosas en la pila).
davec
727

(He movido esta respuesta de otra pregunta que fue más o menos un engaño de esta).

La respuesta a su pregunta es específica de la implementación y puede variar entre compiladores y arquitecturas de procesador. Sin embargo, aquí hay una explicación simplificada.

  • Tanto la pila como el montón son áreas de memoria asignadas desde el sistema operativo subyacente (a menudo, memoria virtual que se asigna a la memoria física a pedido).
  • En un entorno de subprocesos múltiples, cada subproceso tendrá su propia pila completamente independiente, pero compartirán el montón. El acceso concurrente debe controlarse en el montón y no es posible en la pila.

El montón

  • El montón contiene una lista vinculada de bloques usados ​​y libres. Las nuevas asignaciones en el montón (por newo malloc) se satisfacen creando un bloque adecuado a partir de uno de los bloques libres. Esto requiere actualizar la lista de bloques en el montón. Esta metainformación sobre los bloques en el montón también se almacena en el montón a menudo en un área pequeña justo delante de cada bloque.
  • A medida que crece el montón, a menudo se asignan nuevos bloques desde direcciones más bajas hacia direcciones más altas. Por lo tanto, puede pensar en el montón como un montón de bloques de memoria que crece en tamaño a medida que se asigna la memoria. Si el montón es demasiado pequeño para una asignación, el tamaño a menudo se puede aumentar adquiriendo más memoria del sistema operativo subyacente.
  • Asignar y desasignar muchos bloques pequeños puede dejar el montón en un estado en el que hay muchos bloques libres pequeños intercalados entre los bloques usados. Una solicitud para asignar un bloque grande puede fallar porque ninguno de los bloques libres es lo suficientemente grande como para satisfacer la solicitud de asignación, aunque el tamaño combinado de los bloques libres puede ser lo suficientemente grande. Esto se llama fragmentación del montón .
  • Cuando un bloque usado que está adyacente a un bloque libre se desasigna, el nuevo bloque libre puede fusionarse con el bloque libre adyacente para crear un bloque libre más grande que reduzca efectivamente la fragmentación del montón.

El montón

La pila

  • La pila a menudo funciona en conjunto con un registro especial en la CPU llamado puntero de la pila . Inicialmente, el puntero de la pila apunta a la parte superior de la pila (la dirección más alta en la pila).
  • La CPU tiene instrucciones especiales para insertar valores en la pila y extraerlos de la pila. Cada inserción almacena el valor en la ubicación actual del puntero de la pila y disminuye el puntero de la pila. Un mensaje emergente recupera el valor señalado por el puntero de la pila y luego aumenta el puntero de la pila (no se confunda con el hecho de que agregar un valor a la pila disminuye el puntero de la pila y eliminar un valor lo aumenta . Recuerde que la pila crece hasta El fondo). Los valores almacenados y recuperados son los valores de los registros de la CPU.
  • Cuando se llama a una función, la CPU utiliza instrucciones especiales que empujan el puntero de instrucción actual , es decir, la dirección del código que se ejecuta en la pila. Luego, la CPU salta a la función configurando el puntero de instrucción a la dirección de la función llamada. Más tarde, cuando la función regresa, el puntero de instrucción anterior se saca de la pila y la ejecución se reanuda en el código justo después de la llamada a la función.
  • Cuando se ingresa una función, el puntero de la pila se reduce para asignar más espacio en la pila para las variables locales (automáticas). Si la función tiene una variable local de 32 bits, se reservan cuatro bytes en la pila. Cuando la función regresa, el puntero de la pila se mueve hacia atrás para liberar el área asignada.
  • Si una función tiene parámetros, estos se envían a la pila antes de la llamada a la función. El código en la función puede entonces navegar hacia arriba en la pila desde el puntero de la pila actual para localizar estos valores.
  • Las funciones de anidamiento funcionan como un encanto. Cada nueva llamada asignará parámetros de función, la dirección de retorno y el espacio para variables locales y estos registros de activación se pueden apilar para llamadas anidadas y se desenrollarán de la manera correcta cuando las funciones regresen.
  • Como la pila es un bloque de memoria limitado, puede provocar un desbordamiento de la pila al invocar demasiadas funciones anidadas y / o asignar demasiado espacio para variables locales. A menudo, el área de memoria utilizada para la pila se configura de tal manera que escribir debajo de la parte inferior (la dirección más baja) de la pila desencadenará una trampa o excepción en la CPU. El tiempo de ejecución puede detectar esta condición excepcional y convertirla en algún tipo de excepción de desbordamiento de pila.

La pila

¿Se puede asignar una función en el montón en lugar de una pila?

No, los registros de activación para funciones (es decir, variables locales o automáticas) se asignan en la pila que se utiliza no solo para almacenar estas variables, sino también para realizar un seguimiento de las llamadas a funciones anidadas.

Cómo se gestiona el montón depende realmente del entorno de tiempo de ejecución. C usa mallocy C ++ usa new, pero muchos otros lenguajes tienen recolección de basura.

Sin embargo, la pila es una característica de nivel más bajo estrechamente vinculada a la arquitectura del procesador. Hacer crecer el montón cuando no hay suficiente espacio no es demasiado difícil, ya que se puede implementar en la llamada a la biblioteca que maneja el montón. Sin embargo, el crecimiento de la pila a menudo es imposible ya que el desbordamiento de la pila solo se descubre cuando es demasiado tarde; y cerrar el hilo de ejecución es la única opción viable.

Martin Liversage
fuente
35
@ Martin: una muy buena respuesta / explicación que la respuesta más abstracta aceptada. Sería más ilustrativo un programa de ensamblaje de muestra que muestre punteros / registros de pila que se utilizan con respecto a las llamadas a funciones.
Bikal Lem
3
Cada tipo de referencia es una composición de tipos de valores (int, string, etc.). Como se dice, los tipos de valor se almacenan en la pila de cómo funciona cuando forman parte del tipo de referencia.
Nps
15
En mi opinión, esta respuesta fue la mejor, porque me ayudó a comprender qué es realmente una declaración de devolución y cómo se relaciona con esta "dirección de devolución" que encuentro de vez en cuando, lo que significa llevar una función a la pila, y por qué las funciones se insertan en las pilas. ¡Gran respuesta!
Alex
3
Esto es lo mejor en mi opinión, es decir, por mencionar que el montón / pila son muy específicos de la implementación. Las otras respuestas suponen muchas cosas sobre el lenguaje y el entorno / SO. +1
Qix - MONICA FUE MALTRATADA el
2
¿Qué quiere decir? "El código en la función es capaz de navegar por la pila desde el puntero de la pila actual para localizar estos valores". ? ¿Puedes explicar esto por favor?
Koray Tugay
404

En el siguiente código C #

public void Method1()
{
    int i = 4;
    int y = 2;
    class1 cls1 = new class1();
}

Así se gestiona la memoria

Imagen de variables en la pila

Local Variableseso solo necesita durar mientras la invocación de la función vaya en la pila. El montón se usa para variables cuya vida útil realmente no conocemos por adelantado, pero esperamos que duren un tiempo. En la mayoría de los idiomas, es fundamental que sepamos en tiempo de compilación qué tan grande es una variable si queremos almacenarla en la pila.

Los objetos (que varían en tamaño a medida que los actualizamos) van al montón porque no sabemos en el momento de la creación cuánto tiempo durarán. En muchos idiomas, el montón es basura recolectada para encontrar objetos (como el objeto cls1) que ya no tienen referencias.

En Java, la mayoría de los objetos van directamente al montón. En lenguajes como C / C ++, las estructuras y las clases a menudo pueden permanecer en la pila cuando no se trata de punteros.

Más información se puede encontrar aquí:

La diferencia entre la asignación de la pila y la memoria del montón «timmurphy.org

y aquí:

Crear objetos en la pila y el montón

Este artículo es la fuente de la imagen de arriba: Seis conceptos importantes de .NET: pila, montón, tipos de valores, tipos de referencia, boxeo y unboxing - CodeProject

pero tenga en cuenta que puede contener algunas imprecisiones.

Snowcrash
fuente
15
Esto es incorrecto. i y cls no son variables "estáticas". se llaman variables "locales" o "automáticas". Es una distinción muy importante. Ver [link] stackoverflow.com/a/13326916/1763801 para aclaraciones
davec
99
No dije que fueran variables estáticas . Dije que int y cls1 son elementos estáticos . Su memoria está asignada estáticamente y, por lo tanto, van a la pila. Esto está en contraste con un objeto que requiere asignación de memoria dinámica que, por lo tanto, va en el montón.
Snowcrash
12
Cito "Elementos estáticos ... ir a la pila". Esto es simplemente incorrecto. Los elementos estáticos van en el segmento de datos, los elementos automáticos van en la pila.
davec
14
Además, quien escribió ese artículo de codeproject no sabe de qué está hablando. Por ejemplo, dice que "los primitivos necesitan memoria de tipo estático", lo cual es completamente falso. Nada le impide asignar dinámicamente primitivas en el montón, simplemente escriba algo como "int array [] = new int [num]" y listo, primitivas asignadas dinámicamente en .NET. Esa es solo una de varias imprecisiones.
davec
8
Edité tu publicación porque has cometido serios errores técnicos sobre lo que está en la pila y el montón.
Tom Leys
209

La pila Cuando llama a una función, los argumentos de esa función más alguna otra sobrecarga se colocan en la pila. Alguna información (como a dónde ir al regreso) también se almacena allí. Cuando declara una variable dentro de su función, esa variable también se asigna en la pila.

Desasignar la pila es bastante simple porque siempre desasigna en el orden inverso en el que asigna. Las cosas de la pila se agregan a medida que ingresa las funciones, los datos correspondientes se eliminan al salir de ellas. Esto significa que tiende a permanecer dentro de una pequeña región de la pila a menos que llame a muchas funciones que invocan muchas otras funciones (o cree una solución recursiva).

El montón El montón es un nombre genérico para el lugar donde coloca los datos que crea sobre la marcha. Si no sabe cuántas naves espaciales creará su programa, es probable que use el nuevo operador (o malloc o equivalente) para crear cada nave espacial. Esta asignación se mantendrá durante un tiempo, por lo que es probable que liberemos las cosas en un orden diferente al que las creamos.

Por lo tanto, el montón es mucho más complejo, porque terminan siendo regiones de memoria que no se utilizan entrelazadas con fragmentos que sí lo son: la memoria se fragmenta. Encontrar memoria libre del tamaño que necesita es un problema difícil. Es por eso que se debe evitar el montón (aunque todavía se usa con frecuencia).

Implementación La implementación de la pila y el montón generalmente depende del tiempo de ejecución / SO. A menudo, los juegos y otras aplicaciones que son críticas para el rendimiento crean sus propias soluciones de memoria que toman una gran cantidad de memoria del montón y luego la distribuyen internamente para evitar depender del sistema operativo para la memoria.

Esto solo es práctico si su uso de memoria es bastante diferente de la norma, es decir, para juegos en los que carga un nivel en una operación enorme y puede tirar todo el lote en otra operación enorme.

Ubicación física en la memoria Esto es menos relevante de lo que cree debido a una tecnología llamada Memoria virtual que hace que su programa piense que tiene acceso a una determinada dirección donde los datos físicos están en otro lugar (¡incluso en el disco duro!). Las direcciones que obtiene para la pila están en orden creciente a medida que su árbol de llamadas se vuelve más profundo. Las direcciones para el montón no son predecibles (es decir, específicas de la implementación) y, francamente, no son importantes.

Tom Leys
fuente
16
Una recomendación para evitar el uso del montón es bastante sólida. Los sistemas modernos tienen buenos administradores de almacenamiento dinámico, y los lenguajes dinámicos modernos utilizan el almacenamiento dinámico ampliamente (sin que el programador realmente se preocupe por ello). Yo diría que use el montón, pero con un asignador manual, ¡no se olvide de liberar!
Greg Hewgill
2
Si puede usar la pila o el montón, use la pila. Si no puede usar la pila, realmente no hay otra opción. Utilizo mucho y, por supuesto, utilizo std :: vector o hits similares en el montón. ¡Para un novato, evitas el montón porque la pila es simplemente muy fácil!
Tom Leys
Si su idioma no implementa la recolección de basura, los punteros inteligentes (objetos asignados por separado que se ajustan alrededor de un puntero que hace un recuento de referencias para fragmentos de memoria asignados dinámicamente) están estrechamente relacionados con la recolección de basura y son una forma decente de administrar el montón en una caja fuerte y de manera libre de fugas. Se implementan en varios marcos, pero tampoco son tan difíciles de implementar para sus propios programas.
BenPen
1
"Es por eso que se debe evitar el montón (aunque todavía se usa con frecuencia)". No estoy seguro de lo que esto significa prácticamente, especialmente porque la memoria se administra de manera diferente en muchos idiomas de alto nivel. Como esta pregunta está etiquetada como independiente del idioma, diría que este comentario / línea en particular está mal ubicado y no es aplicable.
LintfordPickle
2
Buen punto @JonnoHampson: si bien hace un punto válido, argumentaría que si está trabajando en un "lenguaje de alto nivel" con un GC, probablemente no le interesen los mecanismos de asignación de memoria, y entonces no incluso importa lo que son la pila y el montón.
Tom Leys
194

Para aclarar, esta respuesta tiene información incorrecta ( Thomas arregló su respuesta después de los comentarios, genial :)). Otras respuestas simplemente evitan explicar qué significa la asignación estática. Así que explicaré las tres formas principales de asignación y cómo se relacionan generalmente con el segmento de montón, pila y datos a continuación. También mostraré algunos ejemplos en C / C ++ y Python para ayudar a las personas a comprender.

Las variables "estáticas" (AKA asignadas estáticamente) no se asignan en la pila. No asuma que muchas personas lo hacen solo porque "estático" se parece mucho a "stack". En realidad no existen ni en la pila ni en el montón. Son parte de lo que se llama segmento de datos .

Sin embargo, generalmente es mejor considerar " alcance " y " duración " en lugar de "apilar" y "montón".

El alcance se refiere a qué partes del código pueden acceder a una variable. Generalmente pensamos en el alcance local (solo se puede acceder mediante la función actual) versus el alcance global (se puede acceder desde cualquier lugar), aunque el alcance puede ser mucho más complejo.

La duración se refiere a cuando una variable se asigna y se desasigna durante la ejecución del programa. Por lo general, pensamos en la asignación estática (la variable persistirá durante toda la duración del programa, por lo que es útil para almacenar la misma información en varias llamadas a funciones) frente a la asignación automática (la variable solo persiste durante una sola llamada a una función, por lo que es útil para almacenar información que solo se usa durante su función y puede descartarse una vez que haya terminado) versus asignación dinámica (variables cuya duración se define en tiempo de ejecución, en lugar de tiempo de compilación como estático o automático).

Aunque la mayoría de los compiladores e intérpretes implementan este comportamiento de manera similar en términos de uso de pilas, montones, etc., un compilador a veces puede romper estas convenciones si lo desea, siempre y cuando el comportamiento sea correcto. Por ejemplo, debido a la optimización, una variable local solo puede existir en un registro o eliminarse por completo, aunque la mayoría de las variables locales existen en la pila. Como se ha señalado en algunos comentarios, puede implementar un compilador que ni siquiera usa una pila o un montón, sino algunos otros mecanismos de almacenamiento (rara vez se hace, ya que las pilas y los montones son excelentes para esto).

Proporcionaré un código C simple anotado para ilustrar todo esto. La mejor manera de aprender es ejecutar un programa bajo un depurador y observar el comportamiento. Si prefiere leer Python, salte al final de la respuesta :)

// Statically allocated in the data segment when the program/DLL is first loaded
// Deallocated when the program/DLL exits
// scope - can be accessed from anywhere in the code
int someGlobalVariable;

// Statically allocated in the data segment when the program is first loaded
// Deallocated when the program/DLL exits
// scope - can be accessed from anywhere in this particular code file
static int someStaticVariable;

// "someArgument" is allocated on the stack each time MyFunction is called
// "someArgument" is deallocated when MyFunction returns
// scope - can be accessed only within MyFunction()
void MyFunction(int someArgument) {

    // Statically allocated in the data segment when the program is first loaded
    // Deallocated when the program/DLL exits
    // scope - can be accessed only within MyFunction()
    static int someLocalStaticVariable;

    // Allocated on the stack each time MyFunction is called
    // Deallocated when MyFunction returns
    // scope - can be accessed only within MyFunction()
    int someLocalVariable;

    // A *pointer* is allocated on the stack each time MyFunction is called
    // This pointer is deallocated when MyFunction returns
    // scope - the pointer can be accessed only within MyFunction()
    int* someDynamicVariable;

    // This line causes space for an integer to be allocated in the heap
    // when this line is executed. Note this is not at the beginning of
    // the call to MyFunction(), like the automatic variables
    // scope - only code within MyFunction() can access this space
    // *through this particular variable*.
    // However, if you pass the address somewhere else, that code
    // can access it too
    someDynamicVariable = new int;


    // This line deallocates the space for the integer in the heap.
    // If we did not write it, the memory would be "leaked".
    // Note a fundamental difference between the stack and heap
    // the heap must be managed. The stack is managed for us.
    delete someDynamicVariable;

    // In other cases, instead of deallocating this heap space you
    // might store the address somewhere more permanent to use later.
    // Some languages even take care of deallocation for you... but
    // always it needs to be taken care of at runtime by some mechanism.

    // When the function returns, someArgument, someLocalVariable
    // and the pointer someDynamicVariable are deallocated.
    // The space pointed to by someDynamicVariable was already
    // deallocated prior to returning.
    return;
}

// Note that someGlobalVariable, someStaticVariable and
// someLocalStaticVariable continue to exist, and are not
// deallocated until the program exits.

Un ejemplo particularmente conmovedor de por qué es importante distinguir entre la duración y el alcance es que una variable puede tener un alcance local pero una duración estática, por ejemplo, "someLocalStaticVariable" en el ejemplo de código anterior. Dichas variables pueden hacer que nuestros hábitos de denominación comunes pero informales sean muy confusos. Por ejemplo, cuando decimos " local " usualmente queremos decir " variable asignada localmente con alcance local " y cuando decimos global generalmente queremos decir " variable asignada estáticamente con alcance global ". Desafortunadamente cuando se trata de cosas como " variables asignadas estáticamente a archivos con alcance ", muchas personas simplemente dicen ... " ¿eh? ".

Algunas de las opciones de sintaxis en C / C ++ exacerban este problema; por ejemplo, muchas personas piensan que las variables globales no son "estáticas" debido a la sintaxis que se muestra a continuación.

int var1; // Has global scope and static allocation
static int var2; // Has file scope and static allocation

int main() {return 0;}

Tenga en cuenta que poner la palabra clave "static" en la declaración anterior evita que var2 tenga un alcance global. Sin embargo, la var1 global tiene asignación estática. ¡Esto no es intuitivo! Por esta razón, trato de nunca usar la palabra "estática" cuando describo el alcance, y en su lugar digo algo como "archivo" o "archivo limitado". Sin embargo, muchas personas usan la frase "estática" o "alcance estático" para describir una variable a la que solo se puede acceder desde un archivo de código. En el contexto de la vida útil, "estático" siempre significa que la variable se asigna al inicio del programa y se desasigna cuando el programa sale.

Algunas personas piensan que estos conceptos son específicos de C / C ++. No son. Por ejemplo, el ejemplo de Python a continuación ilustra los tres tipos de asignación (hay algunas diferencias sutiles posibles en los lenguajes interpretados en los que no entraré aquí).

from datetime import datetime

class Animal:
    _FavoriteFood = 'Undefined' # _FavoriteFood is statically allocated

    def PetAnimal(self):
        curTime = datetime.time(datetime.now()) # curTime is automatically allocatedion
        print("Thank you for petting me. But it's " + str(curTime) + ", you should feed me. My favorite food is " + self._FavoriteFood)

class Cat(Animal):
    _FavoriteFood = 'tuna' # Note since we override, Cat class has its own statically allocated _FavoriteFood variable, different from Animal's

class Dog(Animal):
    _FavoriteFood = 'steak' # Likewise, the Dog class gets its own static variable. Important to note - this one static variable is shared among all instances of Dog, hence it is not dynamic!


if __name__ == "__main__":
    whiskers = Cat() # Dynamically allocated
    fido = Dog() # Dynamically allocated
    rinTinTin = Dog() # Dynamically allocated

    whiskers.PetAnimal()
    fido.PetAnimal()
    rinTinTin.PetAnimal()

    Dog._FavoriteFood = 'milkbones'
    whiskers.PetAnimal()
    fido.PetAnimal()
    rinTinTin.PetAnimal()

# Output is:
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is tuna
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is steak
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is steak
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is tuna
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is milkbones
# Thank you for petting me. But it's 13:05:02.256000, you should feed me. My favorite food is milkbones
davec
fuente
Me referiría a una variable estática declarada dentro de una función que solo tiene accesibilidad local , pero generalmente no usaría el término "alcance" con ella. Además, vale la pena señalar que el único aspecto de pila / montón con el que los idiomas tienen esencialmente cero flexibilidad: un lenguaje que guarda el contexto de ejecución en una pila no puede usar esa misma pila para contener cosas que necesitarán sobrevivir a los contextos en los que se crean . Algunos idiomas PostScripttienen múltiples pilas, pero tienen un "montón" que se comporta más como una pila.
supercat
@supercat Eso tiene sentido. Definí el alcance como "qué partes del código pueden acceder a una variable" (y creo que esta es la definición más estándar), así que creo que estamos de acuerdo :)
davec
Consideraría que el "alcance" de una variable está limitado por el tiempo y el espacio. Se requiere una variable en el ámbito del objeto de clase para mantener su valor mientras exista el objeto. Se requiere una variable dentro de un ámbito de contexto de ejecución para mantener su valor siempre que la ejecución permanezca en ese contexto. Una declaración de variable estática crea un identificador cuyo alcance está limitado al bloque actual, que se adjunta a una variable cuyo alcance no está limitado.
supercat
@supercat Es por eso que uso la palabra vida útil, que es como yo llamo lo que llamas alcance temporal. Reduce la necesidad de sobrecargar la palabra "alcance" con tantos significados. Hasta donde puedo decir, no parece haber un consenso total sobre definiciones exactas, incluso entre las fuentes canónicas. Mi terminología se extrae parcialmente de K&R y parcialmente del uso predominante en el primer departamento de CS en el que estudié / enseñé. Siempre es bueno escuchar otra vista informada.
davec
1
debes estar bromeando. ¿realmente puedes definir una variable estática dentro de una función?
Zaeem Sattar
168

Otros han respondido bastante bien a los trazos amplios, así que agregaré algunos detalles.

  1. La pila y el montón no necesitan ser singulares. Una situación común en la que tiene más de una pila es si tiene más de un hilo en un proceso. En este caso, cada hilo tiene su propia pila. También puede tener más de un montón, por ejemplo, algunas configuraciones de DLL pueden dar lugar a diferentes DLL que se asignan desde diferentes montones, por lo que generalmente es una mala idea liberar memoria asignada por una biblioteca diferente.

  2. En C puede obtener el beneficio de la asignación de longitud variable mediante el uso de alloca , que asigna en la pila, en lugar de alloc, que asigna en el montón. Esta memoria no sobrevivirá a su declaración de devolución, pero es útil para un buffer de memoria virtual.

  3. Hacer un gran búfer temporal en Windows que no utilizas mucho no es gratis. Esto se debe a que el compilador generará un bucle de sonda de pila que se llama cada vez que se ingresa su función para asegurarse de que la pila existe (porque Windows usa una sola página de protección al final de su pila para detectar cuándo necesita aumentarla. Si accede a la memoria a más de una página del final de la pila, se bloqueará). Ejemplo:

void myfunction()
{
   char big[10000000];
   // Do something that only uses for first 1K of big 99% of the time.
}
Don Neufeld
fuente
Re "como opuesto a alloc": ¿Quieres decir "como opuesto a malloc"?
Peter Mortensen
¿Qué tan portátil es alloca?
Peter Mortensen
@PeterMortensen no es POSIX, no se garantiza la portabilidad.
Don Neufeld
135

Otros han respondido directamente a su pregunta, pero al tratar de entender la pila y el montón, creo que es útil considerar el diseño de memoria de un proceso UNIX tradicional (sin hilos y mmap()asignadores basados). La página web del Glosario de administración de memoria tiene un diagrama de este diseño de memoria.

La pila y el montón se ubican tradicionalmente en los extremos opuestos del espacio de direcciones virtuales del proceso. La pila crece automáticamente cuando se accede, hasta un tamaño establecido por el núcleo (que se puede ajustar con setrlimit(RLIMIT_STACK, ...)). El montón crece cuando el asignador de memoria invoca el brk()o sbrk()llamada al sistema, la cartografía más páginas de memoria física en el espacio virtual de direcciones del proceso.

En sistemas sin memoria virtual, como algunos sistemas integrados, a menudo se aplica el mismo diseño básico, excepto que la pila y el montón son de tamaño fijo. Sin embargo, en otros sistemas integrados (como los basados ​​en microcontroladores PIC de Microchip), la pila del programa es un bloque de memoria separado que no es direccionable por las instrucciones de movimiento de datos, y solo puede modificarse o leerse indirectamente a través de las instrucciones de flujo del programa (llamada, volver, etc.). Otras arquitecturas, como los procesadores Intel Itanium, tienen múltiples pilas . En este sentido, la pila es un elemento de la arquitectura de la CPU.

bk1e
fuente
117

¿Qué es una pila?

Una pila es una pila de objetos, típicamente uno que está ordenado cuidadosamente.

Ingrese la descripción de la imagen aquí

Las pilas en las arquitecturas de computación son regiones de la memoria donde los datos se agregan o eliminan de una manera de último en entrar, primero en salir.
En una aplicación multiproceso, cada subproceso tendrá su propia pila.

¿Qué es un montón?

Un montón es una colección desordenada de cosas apiladas al azar.

Ingrese la descripción de la imagen aquí

En arquitecturas informáticas, el montón es un área de memoria asignada dinámicamente que es administrada automáticamente por el sistema operativo o la biblioteca del administrador de memoria.
La memoria en el montón se asigna, se desasigna y se redimensiona regularmente durante la ejecución del programa, y ​​esto puede conducir a un problema llamado fragmentación.
La fragmentación ocurre cuando los objetos de memoria se asignan con pequeños espacios intermedios que son demasiado pequeños para contener objetos de memoria adicionales.
El resultado neto es un porcentaje del espacio de almacenamiento dinámico que no se puede utilizar para más asignaciones de memoria.

Ambos juntos

En una aplicación multiproceso, cada subproceso tendrá su propia pila. Pero, todos los diferentes hilos compartirán el montón.
Debido a que los diferentes subprocesos comparten el montón en una aplicación de subprocesos múltiples, esto también significa que debe haber cierta coordinación entre los subprocesos para que no intenten acceder y manipular los mismos fragmentos de memoria en el montón en al mismo tiempo.

¿Cuál es más rápido, la pila o el montón? ¿Y por qué?

La pila es mucho más rápida que el montón.
Esto se debe a la forma en que se asigna la memoria en la pila.
Asignar memoria en la pila es tan simple como mover el puntero hacia arriba.

Para las personas nuevas en la programación, probablemente sea una buena idea usar la pila, ya que es más fácil.
Debido a que la pila es pequeña, querrá usarla cuando sepa exactamente cuánta memoria necesitará para sus datos, o si sabe que el tamaño de sus datos es muy pequeño.
Es mejor usar el montón cuando sabe que necesitará mucha memoria para sus datos, o simplemente no está seguro de cuánta memoria necesitará (como con una matriz dinámica).

Modelo de memoria Java

Ingrese la descripción de la imagen aquí

La pila es el área de memoria donde se almacenan las variables locales (incluidos los parámetros del método). Cuando se trata de variables de objeto, estas son meramente referencias (punteros) a los objetos reales en el montón.
Cada vez que se crea una instancia de un objeto, se reserva una porción de memoria de almacenamiento dinámico para contener los datos (estado) de ese objeto. Como los objetos pueden contener otros objetos, algunos de estos datos pueden contener referencias a esos objetos anidados.

Shreyos Adikari
fuente
115

La pila es una parte de la memoria que puede manipularse mediante varias instrucciones clave del lenguaje ensamblador, como 'pop' (eliminar y devolver un valor de la pila) y 'push' (empujar un valor a la pila), pero también llamar ( llamar a una subrutina (esto empuja la dirección para volver a la pila) y regresar (regresar de una subrutina, esto saca la dirección de la pila y salta a ella). Es la región de memoria debajo del registro del puntero de la pila, que se puede configurar según sea necesario. La pila también se usa para pasar argumentos a las subrutinas, y también para preservar los valores en los registros antes de llamar a las subrutinas.

El montón es una porción de memoria que el sistema operativo le da a una aplicación, generalmente a través de una llamada al sistema como malloc. En los sistemas operativos modernos, esta memoria es un conjunto de páginas a las que solo el proceso de llamada tiene acceso.

El tamaño de la pila se determina en tiempo de ejecución y, en general, no crece después del lanzamiento del programa. En un programa en C, la pila debe ser lo suficientemente grande como para contener cada variable declarada dentro de cada función. El almacenamiento dinámico crecerá dinámicamente según sea necesario, pero el sistema operativo finalmente está haciendo la llamada (a menudo aumentará el almacenamiento dinámico en más del valor solicitado por malloc, por lo que al menos algunos futuros mallocs no necesitarán volver al núcleo para obtener más memoria. Este comportamiento es a menudo personalizable)

Debido a que ha asignado la pila antes de iniciar el programa, nunca necesita malloc antes de poder usar la pila, por lo que es una ligera ventaja. En la práctica, es muy difícil predecir qué será rápido y qué será lento en los sistemas operativos modernos que tienen subsistemas de memoria virtual, porque la forma en que se implementan las páginas y dónde se almacenan es un detalle de implementación.

Daniel Papasian
fuente
2
También vale la pena mencionar aquí que Intel optimiza en gran medida los accesos a la pila, especialmente cosas como predecir dónde regresa de una función.
Tom Leys
113

Creo que muchas otras personas le han dado respuestas correctas sobre este asunto.

Sin embargo, un detalle que se ha pasado por alto es que el "montón" debería de hecho llamarse la "tienda gratuita". La razón de esta distinción es que la tienda gratuita original se implementó con una estructura de datos conocida como "montón binomial". Por esa razón, la asignación desde implementaciones tempranas de malloc () / free () fue la asignación desde un montón. Sin embargo, en este día moderno, la mayoría de las tiendas gratuitas se implementan con estructuras de datos muy elaboradas que no son montones binomiales.


fuente
8
Otro punto crítico: la mayoría de las respuestas (a la ligera) implican que el Clenguaje requiere el uso de una "pila" . Este es un concepto erróneo común, aunque es el paradigma dominante (de lejos) para implementar C99 6.2.4 automatic storage duration objects(variables). De hecho, la palabra "apilar" ni siquiera aparece en el C99lenguaje estándar: open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf
johne
[@Heath] Tengo un pequeño comentario sobre tu respuesta. Eche un vistazo a la respuesta aceptada a esta pregunta . Dice que la tienda gratuita probablemente sea ​​la misma que la del montón , aunque no necesariamente lo es.
OmarOthman
91

Puedes hacer algunas cosas interesantes con la pila. Por ejemplo, tiene funciones como alloca (suponiendo que puede superar las abundantes advertencias sobre su uso), que es una forma de malloc que utiliza específicamente la pila, no el montón, para la memoria.

Dicho esto, los errores de memoria basados ​​en la pila son algunos de los peores que he experimentado. Si usa memoria de almacenamiento dinámico y sobrepasa los límites de su bloque asignado, tiene una posibilidad decente de desencadenar una falla de segmento. (No 100%: su bloque puede ser incidentalmente contiguo con otro que haya asignado previamente). Pero dado que las variables creadas en la pila siempre son contiguas entre sí, escribir fuera de los límites puede cambiar el valor de otra variable. He aprendido que cada vez que siento que mi programa ha dejado de obedecer las leyes de la lógica, es probable que sea un desbordamiento del búfer.

Peter
fuente
¿Qué tan portátil es alloca? Por ejemplo, ¿funciona en Windows? ¿Es solo para sistemas operativos tipo Unix?
Peter Mortensen
89

Simplemente, la pila es donde se crean las variables locales. Además, cada vez que llama a una subrutina, el contador del programa (puntero a la siguiente instrucción de máquina) y cualquier registro importante, y a veces los parámetros se insertan en la pila. Luego, cualquier variable local dentro de la subrutina se inserta en la pila (y se usa desde allí). Cuando finaliza la subrutina, todo eso se vuelve a sacar de la pila. La PC y los datos de registro se vuelven a poner donde estaban cuando aparecieron, para que su programa pueda seguir su camino feliz.

El montón es el área de memoria de la que se hacen asignaciones dinámicas de memoria (llamadas "nuevas" o "asignadas" explícitas). Es una estructura de datos especial que puede realizar un seguimiento de los bloques de memoria de diferentes tamaños y su estado de asignación.

En los sistemas "clásicos", la RAM se colocaba de tal manera que el puntero de la pila comenzaba en la parte inferior de la memoria, el puntero del montón comenzaba en la parte superior y crecían uno hacia el otro. Si se superponen, se queda sin RAM. Sin embargo, eso no funciona con los sistemas operativos multiproceso modernos. Cada hilo tiene que tener su propia pila, y estos pueden crearse dinámicamente.

TED
fuente
[@TED] ¿Por qué dijiste "a veces los parámetros se insertan en la pila"? Lo que sé es que siempre lo son. ¿Podría por favor elaborar más?
OmarOthman
1
@OmarOthman: lo digo porque depende totalmente del escritor de su compilador / intérprete lo que sucede cuando se llama a una subrutina. El comportamiento clásico de Fortran es no usar una pila en absoluto. Algunos idiomas admiten cosas exóticas como el paso por nombre, que es efectivamente una sustitución textual.
TED
83

De WikiAnwser.

Apilar

Cuando una función o un método llama a otra función que a su vez llama a otra función, etc., la ejecución de todas esas funciones permanece suspendida hasta que la última función devuelva su valor.

Esta cadena de llamadas a funciones suspendidas es la pila, porque los elementos en la pila (llamadas a funciones) dependen unos de otros.

Es importante tener en cuenta la pila en el manejo de excepciones y las ejecuciones de subprocesos.

Montón

El montón es simplemente la memoria utilizada por los programas para almacenar variables. El elemento del montón (variables) no tiene dependencias entre sí y siempre se puede acceder al azar en cualquier momento.

devXen
fuente
"Me gusta más la respuesta aceptada, ya que es aún más bajo". Eso es malo, no bueno.
ligereza corre en órbita el
54

Apilar

  • Acceso muy rápido
  • No tiene que desasignar explícitamente variables
  • El espacio es gestionado eficientemente por la CPU, la memoria no se fragmentará
  • Solo variables locales
  • Límite en el tamaño de la pila (depende del sistema operativo)
  • Las variables no pueden ser redimensionadas

Montón

  • Se puede acceder a las variables de forma global
  • No hay límite en el tamaño de la memoria
  • (Relativamente) acceso más lento
  • No se garantiza el uso eficiente del espacio, la memoria puede fragmentarse con el tiempo a medida que se asignan bloques de memoria y luego se liberan
  • Debe administrar la memoria (está a cargo de asignar y liberar variables)
  • Las variables pueden redimensionarse usando realloc ()
desconocido
fuente
50

OK, simplemente y en pocas palabras, significan ordenado y no ordenado ...!

Pila : en los elementos de pila, las cosas se ponen una encima de la otra, ¡significa que será más rápido y más eficiente ser procesado! ...

Así que siempre hay un índice para señalar el elemento específico, también el procesamiento será más rápido, ¡también existe una relación entre los elementos! ...

Montón : Sin orden, el procesamiento será más lento y los valores se desordenarán sin un orden o índice específico ... hay aleatorio y no hay relación entre ellos ... por lo que el tiempo de ejecución y uso podría variar ...

También creo la imagen a continuación para mostrar cómo pueden verse:

ingrese la descripción de la imagen aquí

Alireza
fuente
49

En breve

Se utiliza una pila para la asignación de memoria estática y un montón para la asignación de memoria dinámica, ambos almacenados en la RAM de la computadora.


En detalle

La pila

La pila es una estructura de datos "LIFO" (último en entrar, primero en salir), que es administrada y optimizada por la CPU bastante de cerca. Cada vez que una función declara una nueva variable, se "inserta" en la pila. Luego, cada vez que sale una función, todas las variables empujadas a la pila por esa función se liberan (es decir, se eliminan). Una vez que se libera una variable de pila, esa región de memoria queda disponible para otras variables de pila.

La ventaja de usar la pila para almacenar variables es que la memoria se administra por usted. No tiene que asignar memoria a mano o liberarla una vez que ya no la necesita. Además, debido a que la CPU organiza la memoria de la pila de manera tan eficiente, leer y escribir en las variables de la pila es muy rápido.

Más se puede encontrar aquí .


El montón

El almacenamiento dinámico es una región de la memoria de su computadora que no se administra automáticamente para usted y que la CPU no lo hace de manera tan estricta. Es una región de memoria más flotante (y es más grande). Para asignar memoria en el montón, debe usar malloc () o calloc (), que son funciones integradas de C. Una vez que haya asignado memoria en el montón, usted es responsable de usar free () para desasignar esa memoria una vez que ya no la necesite.

Si no lo hace, su programa tendrá lo que se conoce como pérdida de memoria. Es decir, la memoria en el montón aún se reservará (y no estará disponible para otros procesos). Como veremos en la sección de depuración, hay una herramienta llamada Valgrind que puede ayudarlo a detectar pérdidas de memoria.

A diferencia de la pila, el montón no tiene restricciones de tamaño en tamaño variable (aparte de las limitaciones físicas obvias de su computadora). La memoria de almacenamiento dinámico es un poco más lenta de leer y escribir, porque uno tiene que usar punteros para acceder a la memoria en el almacenamiento dinámico. Hablaremos de punteros en breve.

A diferencia de la pila, las variables creadas en el montón son accesibles por cualquier función, en cualquier parte de su programa. Las variables de montón son esencialmente de alcance global.

Más se puede encontrar aquí .


Las variables asignadas en la pila se almacenan directamente en la memoria y el acceso a esta memoria es muy rápido, y su asignación se trata cuando se compila el programa. Cuando una función o un método llama a otra función que a su vez llama a otra función, etc., la ejecución de todas esas funciones permanece suspendida hasta que la última función devuelva su valor. La pila siempre está reservada en un orden LIFO, el bloque reservado más recientemente es siempre el siguiente bloque que se liberará. Esto hace que sea realmente simple hacer un seguimiento de la pila, liberar un bloque de la pila no es más que ajustar un puntero.

Las variables asignadas en el montón tienen su memoria asignada en tiempo de ejecución y el acceso a esta memoria es un poco más lento, pero el tamaño del montón solo está limitado por el tamaño de la memoria virtual. Los elementos del montón no tienen dependencias entre sí y siempre se puede acceder de forma aleatoria en cualquier momento. Puede asignar un bloque en cualquier momento y liberarlo en cualquier momento. Esto hace que sea mucho más complejo hacer un seguimiento de qué partes del montón están asignadas o libres en un momento dado.

Ingrese la descripción de la imagen aquí

Puede usar la pila si sabe exactamente cuántos datos necesita asignar antes del tiempo de compilación, y no es demasiado grande. Puede usar el montón si no sabe exactamente cuántos datos necesitará en tiempo de ejecución o si necesita asignar una gran cantidad de datos.

En una situación de subprocesos múltiples, cada subproceso tendrá su propia pila completamente independiente, pero compartirán el montón. La pila es específica de subproceso y el montón es específico de la aplicación. Es importante tener en cuenta la pila en el manejo de excepciones y las ejecuciones de subprocesos.

Cada subproceso obtiene una pila, mientras que normalmente solo hay un montón para la aplicación (aunque no es raro tener varios montones para diferentes tipos de asignación).

Ingrese la descripción de la imagen aquí

En tiempo de ejecución, si la aplicación necesita más almacenamiento dinámico, puede asignar memoria de la memoria libre y si la pila necesita memoria, puede asignar memoria de la memoria asignada de memoria libre para la aplicación.

Incluso, se dan más detalles aquí y aquí .


Ahora ve a las respuestas de tu pregunta .

¿En qué medida están controlados por el sistema operativo o el tiempo de ejecución del lenguaje?

El sistema operativo asigna la pila para cada subproceso de nivel de sistema cuando se crea el subproceso. Normalmente, el tiempo de ejecución del lenguaje llama al sistema operativo para asignar el montón para la aplicación.

Más se puede encontrar aquí .

¿Cuál es su alcance?

Ya dado en la parte superior.

"Puede usar la pila si sabe exactamente cuántos datos necesita asignar antes del tiempo de compilación, y no es demasiado grande. Puede usar el montón si no sabe exactamente cuántos datos necesitará en tiempo de ejecución o si necesita asignar muchos datos ".

Más se puede encontrar aquí .

¿Qué determina el tamaño de cada uno de ellos?

El sistema operativo establece el tamaño de la pila cuando se crea un subproceso. El tamaño del montón se establece en el inicio de la aplicación, pero puede crecer a medida que se necesita espacio (el asignador solicita más memoria del sistema operativo).

¿Qué lo hace a uno más rápido?

La asignación de la pila es mucho más rápida ya que todo lo que realmente hace es mover el puntero de la pila. Con los grupos de memoria, puede obtener un rendimiento comparable de la asignación de almacenamiento dinámico, pero eso viene con una ligera complejidad adicional y sus propios dolores de cabeza.

Además, stack vs. heap no es solo una consideración de rendimiento; También le informa mucho sobre la vida útil esperada de los objetos.

Los detalles se pueden encontrar desde aquí .

Abrar Jahin
fuente
36

En la década de 1980, UNIX se propagó como conejitos con grandes compañías rodando las suyas. Exxon tenía uno, al igual que docenas de marcas perdidas en la historia. La disposición de la memoria quedaba a discreción de muchos implementadores.

Un programa C típico se presentaba plano en la memoria con la oportunidad de aumentar cambiando el valor brk (). Típicamente, el HEAP estaba justo por debajo de este valor brk y al aumentar brk aumentó la cantidad de almacenamiento dinámico disponible.

El STACK individual era típicamente un área debajo de HEAP que era un tramo de memoria que no contenía nada de valor hasta la parte superior del siguiente bloque fijo de memoria. Este siguiente bloque a menudo era CÓDIGO, que podría sobrescribirse con datos de pila en uno de los hacks famosos de su era.

Un bloque de memoria típico era BSS (un bloque de valores cero) que accidentalmente no se puso a cero en la oferta de un fabricante. Otro era DATA que contenía valores inicializados, incluidas cadenas y números. Un tercero era CODE que contenía CRT (tiempo de ejecución C), main, funciones y bibliotecas.

El advenimiento de la memoria virtual en UNIX cambia muchas de las restricciones. No hay una razón objetiva por la cual estos bloques deben ser contiguos, fijos en tamaño u ordenados de una manera particular ahora. Por supuesto, antes de que UNIX fuera Multics que no sufría estas restricciones. Aquí hay un esquema que muestra uno de los diseños de memoria de esa época.

Un típico diseño de memoria de programa de UNIX C estilo 1980

jlettvin
fuente
36

pila , montón y datos de cada proceso en la memoria virtual:

pila, montón y datos estáticos

Yousha Aleayoub
fuente
26

Un par de centavos: creo que será bueno dibujar una memoria gráfica y más simple:

Esta es mi visión de la construcción de memoria de proceso con simplificación para una comprensión más fácil de lo que sucede.


Flechas: muestran dónde crecen la pila y el montón, el tamaño de la pila del proceso tiene un límite, definido en el sistema operativo, los límites del tamaño de la pila de subprocesos por parámetros en la API de creación de subprocesos generalmente. El almacenamiento dinámico suele limitar el tamaño máximo de memoria virtual del proceso, por ejemplo, para 32 bits de 2 a 4 GB.

De manera tan simple: el montón de procesos es general para el proceso y todos los subprocesos en el interior, utilizando para la asignación de memoria en el caso común con algo como malloc () .

Stack es una memoria rápida para almacenar en el caso común punteros y variables de retorno de funciones, procesados ​​como parámetros en la llamada de función, variables de función local.

Maxim Akristiniy
fuente
23

Dado que algunas respuestas se volvieron quisquillosas, voy a contribuir con mi ácaro.

Sorprendentemente, nadie ha mencionado que múltiples pilas de llamadas (es decir, no relacionadas con el número de subprocesos a nivel del sistema operativo) se encuentran no solo en lenguajes exóticos (PostScript) o plataformas (Intel Itanium), sino también en fibras , hilos verdes y algunas implementaciones de corutinas .

Las fibras, los hilos verdes y las corutinas son similares en muchos aspectos, lo que genera mucha confusión. La diferencia entre las fibras y los hilos verdes es que los primeros usan la multitarea cooperativa, mientras que el segundo puede presentar uno cooperativo o preventivo (o incluso ambos). Para la distinción entre fibras y corutinas, vea aquí .

En cualquier caso, el propósito de ambas fibras, hilos verdes y corutinas es tener múltiples funciones ejecutándose simultáneamente, pero no en paralelo (ver esta pregunta SO para la distinción) dentro de un solo hilo a nivel del sistema operativo, transfiriendo el control de un lado a otro de manera organizada.

Al usar fibras, hilos verdes o corutinas, generalmente tiene una pila separada por función. (Técnicamente, no solo una pila sino un contexto completo de ejecución es por función. Lo más importante es que la CPU se registra). Para cada hilo hay tantas pilas como funciones que se ejecutan simultáneamente, y el hilo cambia entre ejecutar cada función de acuerdo con la lógica de su programa. Cuando una función llega a su fin, su pila se destruye. Por lo tanto, el número y la vida útil de las pilas son dinámicas y no están determinadas por el número de subprocesos a nivel de sistema operativo.

Tenga en cuenta que dije " generalmente tengo una pila separada por función". Hay implementaciones apiladas y apiladas de couroutines. La mayoría de las implementaciones notable stackful C ++ son Boost.Coroutine y Microsoft PPL s' async/await. (Sin embargo, las funciones reanudables de C ++ (también conocidas como " asyncyawait es probable que las "), que se propusieron para C ++ 17, utilicen rutinas sin pila.

La propuesta de fibras para la biblioteca estándar de C ++ está próxima. Además, hay algunas bibliotecas de terceros . Los hilos verdes son extremadamente populares en lenguajes como Python y Ruby.

shakurov
fuente
19

Tengo algo que compartir, aunque los puntos principales ya están cubiertos.

Apilar

  • Acceso muy rapido.
  • Almacenado en la RAM.
  • Las llamadas a funciones se cargan aquí junto con las variables locales y los parámetros de funciones pasados.
  • El espacio se libera automáticamente cuando el programa se sale de un alcance.
  • Almacenado en memoria secuencial.

Montón

  • Acceso lento en comparación con la pila.
  • Almacenado en la RAM.
  • Las variables creadas dinámicamente se almacenan aquí, lo que luego requiere liberar la memoria asignada después de su uso.
  • Se almacena donde se realiza la asignación de memoria, siempre se accede por puntero.

Nota interesante:

  • Si las llamadas de función se hubieran almacenado en el montón, habría resultado en 2 puntos desordenados:
    1. Debido al almacenamiento secuencial en la pila, la ejecución es más rápida. El almacenamiento en el montón habría resultado en un gran consumo de tiempo, haciendo que todo el programa se ejecute más lentamente.
    2. Si las funciones se almacenaron en el montón (almacenamiento desordenado señalado por el puntero), no habría habido forma de volver a la dirección de la persona que llama (que la pila da debido al almacenamiento secuencial en la memoria).
Pankaj Kumar Thapa
fuente
1
Conciso y limpio. nice :)
ingconti
13

¡Guauu! Tantas respuestas y no creo que una de ellas haya acertado ...

1) ¿Dónde y qué están (físicamente en la memoria de una computadora real)?

La pila es la memoria que comienza como la dirección de memoria más alta asignada a la imagen de su programa, y ​​luego disminuye en valor desde allí. Está reservado para los parámetros de función llamados y para todas las variables temporales utilizadas en funciones.

Hay dos montones: público y privado.

El montón privado comienza en un límite de 16 bytes (para programas de 64 bits) o un límite de 8 bytes (para programas de 32 bits) después del último byte de código en su programa, y ​​luego aumenta su valor desde allí. También se llama el montón predeterminado.

Si el montón privado es demasiado grande, se superpondrá al área de la pila, al igual que la pila se superpondrá al montón si se hace demasiado grande. Debido a que la pila comienza en una dirección más alta y desciende a una dirección más baja, con el pirateo adecuado puede hacer que la pila sea tan grande que sobrepase el área de montón privado y se superponga al área de código. El truco es superponer suficiente área del código que pueda enganchar en el código. Es un poco difícil de hacer y corre el riesgo de que se bloquee el programa, pero es fácil y muy efectivo.

El montón público reside en su propio espacio de memoria fuera del espacio de imagen de su programa. Es esta memoria la que será desviada al disco duro si los recursos de memoria escasean.

2) ¿En qué medida están controlados por el sistema operativo o el tiempo de ejecución del lenguaje?

El programador controla la pila, el sistema operativo administra el almacenamiento dinámico privado y nadie controla el almacenamiento dinámico público porque es un servicio del sistema operativo: usted realiza solicitudes y se otorgan o rechazan.

2b) ¿Cuál es su alcance?

Todos son globales para el programa, pero sus contenidos pueden ser privados, públicos o globales.

2c) ¿Qué determina el tamaño de cada uno de ellos?

El tamaño de la pila y el montón privado están determinados por las opciones de tiempo de ejecución de su compilador. El montón público se inicializa en tiempo de ejecución utilizando un parámetro de tamaño.

2d) ¿Qué lo hace a uno más rápido?

No están diseñados para ser rápidos, están diseñados para ser útiles. La forma en que el programador los utiliza determina si son "rápidos" o "lentos"

ÁRBITRO:

https://norasandler.com/2019/02/18/Write-a-Compiler-10.html

https://docs.microsoft.com/en-us/windows/desktop/api/heapapi/nf-heapapi-getprocessheap

https://docs.microsoft.com/en-us/windows/desktop/api/heapapi/nf-heapapi-heapcreate

ar18
fuente
8

Muchas de las respuestas son correctas como conceptos, pero debemos tener en cuenta que el hardware necesita una pila (es decir, un microprocesador) para permitir llamar a subrutinas (LLAMAR en lenguaje ensamblador ...). (OOP chicos lo llamarán métodos )

En la pila, guarda las direcciones de retorno y la llamada → push / ret → pop se gestiona directamente en el hardware.

Puede usar la pila para pasar parámetros ... incluso si es más lenta que usar registros (diría un gurú del microprocesador o un buen libro de BIOS de la década de 1980 ...)

  • Sin pila, ningún microprocesador puede funcionar. (No podemos imaginar un programa, incluso en lenguaje ensamblador, sin subrutinas / funciones)
  • Sin el montón puede. (Un programa en lenguaje ensamblador puede funcionar sin él, ya que el montón es un concepto de SO, como malloc, que es una llamada de OS / Lib.

El uso de la pila es más rápido como:

  • Es hardware, e incluso push / pop son muy eficientes.
  • malloc requiere ingresar al modo kernel, usar bloqueo / semáforo (u otras primitivas de sincronización), ejecutar algún código y administrar algunas estructuras necesarias para realizar un seguimiento de la asignación.
ingconti
fuente
¿Qué es el OPP? ¿Te refieres a OOP (programación orientada a objetos )?
Peter Mortensen
¿Quieres decir que malloces una llamada de kernel?
Peter Mortensen
1) sí, lo siento ... OOP ... 2) malloc: escribo brevemente, lo siento ... malloc está en el espacio del usuario ... pero puede activar otras llamadas ... el punto es que usar el montón PUEDE ser muy lento ...
ingconti
" Muchas respuestas son correctas como conceptos, pero debemos tener en cuenta que el hardware necesita una pila (es decir, un microprocesador) para permitir llamar a subrutinas (CALL en lenguaje ensamblador ...) ". Está confundiendo la pila de CPU (si había una en la CPU moderna) y las pilas de tiempo de ejecución del idioma (una por hilo). Cuando los programadores hablan de una pila, esta es la pila de ejecución de subprocesos del tiempo de ejecución, por ejemplo, una pila de subprocesos NET), no estamos hablando de la pila de CPU.
minutos
1

La pila es esencialmente una memoria de fácil acceso que simplemente gestiona sus elementos como una pila de "bueno". Solo los artículos cuyo tamaño se conoce de antemano pueden ir a la pila . Este es el caso de números, cadenas, booleanos.

El montón es una memoria para elementos de los que no puede predeterminar el tamaño y la estructura exactos . Dado que los objetos y las matrices pueden mutar y cambiar en tiempo de ejecución, tienen que ir al montón.

Fuente: Academind

NattyC
fuente
0

Gracias por una muy buena discusión, pero como un novato real, me pregunto dónde se guardan las instrucciones. En el PRINCIPIO, los científicos decidían entre dos arquitecturas (von NEUMANN, donde todo se considera DATOS y HARVARD, donde un área de memoria estaba reservada para instrucciones y otra para datos). Finalmente, elegimos el diseño von Neumann y ahora todo se considera "igual". Esto me hizo difícil cuando estaba aprendiendo el ensamblaje https://www.cs.virginia.edu/~evans/cs216/guides/x86.html porque hablan sobre registros y apiladores.

Todo lo anterior habla de DATOS. Supongo que, dado que una instrucción es una cosa definida con una huella de memoria específica, iría a la pila y todos los registros 'esos' discutidos en el ensamblaje están en la pila. Por supuesto, luego vino la programación orientada a objetos con instrucciones y datos que se integraron en una estructura que era dinámica, por lo que ahora las instrucciones también se mantendrían en el montón.

aquagremlin
fuente