¿Qué sucede cuando se ejecuta un programa de computadora?

180

Conozco la teoría general pero no puedo encajar en los detalles.

Sé que un programa reside en la memoria secundaria de una computadora. Una vez que el programa comienza a ejecutarse, se copia por completo en la RAM. Luego, el procesador recupera algunas instrucciones (depende del tamaño del bus) a la vez, las coloca en registros y las ejecuta.

También sé que un programa de computadora usa dos tipos de memoria: pila y montón, que también son parte de la memoria primaria de la computadora. La pila se usa para memoria no dinámica y el montón para memoria dinámica (por ejemplo, todo lo relacionado con el newoperador en C ++)

Lo que no puedo entender es cómo se conectan esas dos cosas. ¿En qué punto se utiliza la pila para la ejecución de las instrucciones? ¿Las instrucciones van desde la RAM, a la pila, a los registros?

gaijinco
fuente
43
¡+1 por hacer una pregunta fundamental!
mkelley33
21
hmm ... ya sabes, escriben libros sobre eso. ¿Realmente quieres estudiar esta parte de la arquitectura del sistema operativo con la ayuda de SO?
Andrey
1
Agregué un par de etiquetas basadas en la naturaleza de la pregunta relacionada con la memoria y la referencia a C ++, aunque creo que una buena respuesta también podría provenir de alguien con conocimientos de Java o C #)
Mkelley33
14
Votado y favorecido. Siempre he tenido demasiado miedo de preguntar ...
Maxpm
2
El término "los coloca en registros" no es del todo correcto. En la mayoría de los procesadores, los registros se utilizan para contener valores intermedios, no código ejecutable.

Respuestas:

161

Realmente depende del sistema, pero los sistemas operativos modernos con memoria virtual tienden a cargar sus imágenes de proceso y asignar memoria a algo como esto:

+---------+
|  stack  |  function-local variables, return addresses, return values, etc.
|         |  often grows downward, commonly accessed via "push" and "pop" (but can be
|         |  accessed randomly, as well; disassemble a program to see)
+---------+
| shared  |  mapped shared libraries (C libraries, math libs, etc.)
|  libs   |
+---------+
|  hole   |  unused memory allocated between the heap and stack "chunks", spans the
|         |  difference between your max and min memory, minus the other totals
+---------+
|  heap   |  dynamic, random-access storage, allocated with 'malloc' and the like.
+---------+
|   bss   |  Uninitialized global variables; must be in read-write memory area
+---------+
|  data   |  data segment, for globals and static variables that are initialized
|         |  (can further be split up into read-only and read-write areas, with
|         |  read-only areas being stored elsewhere in ROM on some systems)
+---------+
|  text   |  program code, this is the actual executable code that is running.
+---------+

Este es el espacio de direcciones de proceso general en muchos sistemas comunes de memoria virtual. El "agujero" es el tamaño de su memoria total, menos el espacio ocupado por todas las otras áreas; Esto proporciona una gran cantidad de espacio para que el montón crezca. Esto también es "virtual", lo que significa que se asigna a su memoria real a través de una tabla de traducción, y puede almacenarse en cualquier lugar en la memoria real. Se hace de esta manera para proteger un proceso de acceder a la memoria de otro proceso y hacer que cada proceso piense que se está ejecutando en un sistema completo.

Tenga en cuenta que las posiciones de, por ejemplo, la pila y el montón pueden estar en un orden diferente en algunos sistemas (consulte la respuesta de Billy O'Neal a continuación para obtener más detalles sobre Win32).

Otros sistemas pueden ser muy diferentes. DOS, por ejemplo, se ejecutó en modo real , y su asignación de memoria al ejecutar programas se veía de manera muy diferente:

+-----------+ top of memory
| extended  | above the high memory area, and up to your total memory; needed drivers to
|           | be able to access it.
+-----------+ 0x110000
|  high     | just over 1MB->1MB+64KB, used by 286s and above.
+-----------+ 0x100000
|  upper    | upper memory area, from 640kb->1MB, had mapped memory for video devices, the
|           | DOS "transient" area, etc. some was often free, and could be used for drivers
+-----------+ 0xA0000
| USER PROC | user process address space, from the end of DOS up to 640KB
+-----------+
|command.com| DOS command interpreter
+-----------+ 
|    DOS    | DOS permanent area, kept as small as possible, provided routines for display,
|  kernel   | *basic* hardware access, etc.
+-----------+ 0x600
| BIOS data | BIOS data area, contained simple hardware descriptions, etc.
+-----------+ 0x400
| interrupt | the interrupt vector table, starting from 0 and going to 1k, contained 
|  vector   | the addresses of routines called when interrupts occurred.  e.g.
|  table    | interrupt 0x21 checked the address at 0x21*4 and far-jumped to that 
|           | location to service the interrupt.
+-----------+ 0x0

Puede ver que DOS permitió el acceso directo a la memoria del sistema operativo, sin protección, lo que significaba que los programas de espacio de usuario generalmente podían acceder o sobrescribir directamente lo que quisieran.

Sin embargo, en el espacio de direcciones del proceso, los programas tendieron a parecerse, solo se describieron como segmento de código, segmento de datos, montón, segmento de pila, etc., y se asignó de manera un poco diferente. Pero la mayoría de las áreas generales todavía estaban allí.

Al cargar el programa y las bibliotecas compartidas necesarias en la memoria, y distribuir las partes del programa en las áreas correctas, el sistema operativo comienza a ejecutar su proceso donde sea que esté su método principal, y su programa toma el control desde allí, haciendo llamadas al sistema según sea necesario cuando los necesita

Los diferentes sistemas (incrustados, lo que sea) pueden tener arquitecturas muy diferentes, como los sistemas sin pila, los sistemas de arquitectura de Harvard (con código y datos que se mantienen en una memoria física separada), sistemas que realmente mantienen el BSS en la memoria de solo lectura (inicialmente establecida por el programador), etc. Pero esta es la esencia general.


Tu dijiste:

También sé que un programa de computadora usa dos tipos de memoria: pila y montón, que también son parte de la memoria primaria de la computadora.

"Pila" y "montón" son solo conceptos abstractos, en lugar de (necesariamente) "tipos" de memoria físicamente distintos.

Una pila es simplemente una estructura de datos de último en entrar, primero en salir. En la arquitectura x86, en realidad se puede abordar aleatoriamente utilizando un desplazamiento desde el final, pero las funciones más comunes son PUSH y POP para agregar y eliminar elementos, respectivamente. Se usa comúnmente para variables locales de función (denominado "almacenamiento automático"), argumentos de función, direcciones de retorno, etc. (más abajo)

Un "montón" es solo un apodo para un trozo de memoria que se puede asignar a pedido y se trata de forma aleatoria (es decir, puede acceder a cualquier ubicación directamente). Se usa comúnmente para estructuras de datos que asigna en tiempo de ejecución (en C ++, usando newy delete, mallocy amigos en C, etc.).

La pila y el montón, en la arquitectura x86, residen físicamente en la memoria del sistema (RAM) y se asignan a través de la asignación de memoria virtual en el espacio de direcciones del proceso como se describió anteriormente.

Los registros (aún en x86), residen físicamente dentro del procesador (a diferencia de la RAM), y son cargados por el procesador, desde el área de TEXTO (y también pueden cargarse desde otro lugar en la memoria u otros lugares dependiendo de las instrucciones de la CPU que son realmente ejecutados). Básicamente son ubicaciones de memoria en chip muy pequeñas y muy rápidas que se utilizan para diferentes propósitos.

El diseño del registro depende en gran medida de la arquitectura (de hecho, los registros, el conjunto de instrucciones y el diseño / diseño de la memoria son exactamente lo que se entiende por "arquitectura"), por lo que no lo ampliaré, pero le recomiendo que tome un curso de lenguaje ensamblador para entenderlos mejor.


Tu pregunta:

¿En qué punto se utiliza la pila para la ejecución de las instrucciones? ¿Las instrucciones van desde la RAM, a la pila, a los registros?

La pila (en sistemas / idiomas que los tienen y los usan) se usa con mayor frecuencia de esta manera:

int mul( int x, int y ) {
    return x * y;       // this stores the result of MULtiplying the two variables 
                        // from the stack into the return value address previously 
                        // allocated, then issues a RET, which resets the stack frame
                        // based on the arg list, and returns to the address set by
                        // the CALLer.
}

int main() {
    int x = 2, y = 3;   // these variables are stored on the stack
    mul( x, y );        // this pushes y onto the stack, then x, then a return address,
                        // allocates space on the stack for a return value, 
                        // then issues an assembly CALL instruction.
}

Escriba un programa simple como este, y luego compílelo en ensamblador ( gcc -S foo.csi tiene acceso a GCC), y eche un vistazo. El montaje es bastante fácil de seguir. Puede ver que la pila se usa para variables locales de función y para llamar a funciones, almacenar sus argumentos y valores de retorno. Esta es también la razón por la que haces algo como:

f( g( h( i ) ) ); 

Todos estos se llaman a su vez. Literalmente, está acumulando una pila de llamadas a funciones y sus argumentos, ejecutándolas y luego haciéndolas explotar a medida que retrocede (o sube). Sin embargo, como se mencionó anteriormente, la pila (en x86) en realidad reside en el espacio de memoria de su proceso (en la memoria virtual), por lo que puede manipularse directamente; no es un paso separado durante la ejecución (o al menos es ortogonal al proceso).

Para su información, lo anterior es la convención de llamada C , también utilizada por C ++. Otros lenguajes / sistemas pueden insertar argumentos en la pila en un orden diferente, y algunos lenguajes / plataformas ni siquiera usan pilas, y lo hacen de diferentes maneras.

También tenga en cuenta que estas no son líneas reales de ejecución de código C. El compilador los ha convertido en instrucciones de lenguaje de máquina en su ejecutable. Luego (generalmente) se copian del área de TEXTO a la tubería de la CPU, luego a los registros de la CPU y se ejecutan desde allí. [Esto fue incorrecto. Ver la corrección de Ben Voigt a continuación.]

Sdaz MacSkibbons
fuente
44
lo siento, pero una buena recomendación de libro sería una mejor respuesta, OMI
Andrey
13
Sí, "RTFM" siempre es mejor.
Sdaz MacSkibbons
56
@Andrey: tal vez deberías cambiar ese comentario a "también, es posible que quieras leer tu recomendación de buen libro " Entiendo que este tipo de pregunta merece más investigación, pero cada vez que tengas que comenzar un comentario con "lo siento pero. .. "tal vez deberías considerar marcar la publicación para la atención del moderador o al menos ofrecer una explicación de por qué tu opinión debería importarle a cualquiera de todos modos.
mkelley33
2
Excelente respuesta ¡Ciertamente me aclaró algunas cosas!
Maxpm
2
@Mikael: Dependiendo de la implementación, puede tener un almacenamiento en caché obligatorio, en cuyo caso cada vez que se leen datos de la memoria, se lee una línea de caché completa y se llena el caché. O puede ser posible darle al administrador de caché una pista de que los datos solo serán necesarios una vez, por lo que copiarlos en la caché no es útil. Eso es para leer. Para la escritura hay cachés de escritura y reescritura, que afectan cuándo los controladores DMA pueden leer los datos, y luego hay una gran cantidad de protocolos de coherencia de caché para tratar con múltiples procesadores, cada uno con su propia caché. Esto realmente merece su propia Q.
Ben Voigt
61

Sdaz ha recibido una cantidad notable de votos a favor en muy poco tiempo, pero lamentablemente está perpetuando una idea errónea sobre cómo las instrucciones se mueven a través de la CPU.

La pregunta formulada:

¿Las instrucciones van desde la RAM, a la pila, a los registros?

Sdaz dijo:

También tenga en cuenta que estas no son líneas reales de ejecución de código C. El compilador los ha convertido en instrucciones de lenguaje de máquina en su ejecutable. Luego (generalmente) se copian del área de TEXTO a la tubería de la CPU, luego a los registros de la CPU y se ejecutan desde allí.

Pero esto está mal. Excepto en el caso especial del código auto modificable, las instrucciones nunca ingresan la ruta de datos. Y no se ejecutan, no se pueden ejecutar desde la ruta de datos.

Los registros de la CPU x86 son:

  • Registros generales EAX EBX ECX EDX

  • Registros de segmento CS DS ES FS GS SS

  • Índice y punteros ESI EDI EBP EIP ESP

  • Indicador EFLAGS

También hay algunos registros de coma flotante y SIMD, pero a los fines de esta discusión los clasificaremos como parte del coprocesador y no de la CPU. La unidad de administración de memoria dentro de la CPU también tiene algunos registros propios, de nuevo trataremos eso como una unidad de procesamiento separada.

Ninguno de estos registros se utiliza para el código ejecutable. EIPcontiene la dirección de la instrucción de ejecución, no la instrucción en sí.

Las instrucciones pasan por una ruta completamente diferente en la CPU de los datos (arquitectura de Harvard). Todas las máquinas actuales son arquitectura Harvard dentro de la CPU. La mayoría de estos días también son arquitectura de Harvard en el caché. x86 (su máquina de escritorio común) son arquitectura de Von Neumann en la memoria principal, lo que significa que los datos y el código se entremezclan en la RAM. Eso no viene al caso, ya que estamos hablando de lo que sucede dentro de la CPU.

La secuencia clásica que se enseña en la arquitectura de computadoras es fetch-decode-execute. El controlador de memoria busca las instrucciones almacenadas en la dirección EIP. Los bits de la instrucción pasan por una lógica combinatoria para crear todas las señales de control para los diferentes multiplexores en el procesador. Y después de algunos ciclos, la unidad de lógica aritmética llega a un resultado, que se registra en el destino. Luego se busca la siguiente instrucción.

En un procesador moderno, las cosas funcionan un poco diferente. Cada instrucción entrante se traduce en una serie completa de instrucciones de microcódigo. Esto permite la canalización, ya que los recursos utilizados por la primera microinstrucción no se necesitan más tarde, por lo que pueden comenzar a trabajar en la primera microinstrucción a partir de la siguiente instrucción.

Para colmo, la terminología es un poco confusa porque el registro es un término de ingeniería eléctrica para una colección de flip-flops D. Y las instrucciones (o especialmente las microinstrucciones) pueden almacenarse temporalmente en una colección de D-flipflops. Pero esto no es lo que se quiere decir cuando un informático o ingeniero de software o desarrollador habitual utiliza el término registro . Significan los registros de ruta de datos como se enumeran anteriormente, y estos no se utilizan para transportar código.

Los nombres y la cantidad de registros de ruta de datos varían para otras arquitecturas de CPU, como ARM, MIPS, Alpha, PowerPC, pero todas ejecutan instrucciones sin pasarlas por la ALU.

Ben Voigt
fuente
Gracias por la aclaración. Dudaba en agregar eso ya que no estoy íntimamente familiarizado con eso, pero lo hice a pedido de otra persona.
Sdaz MacSkibbons
s / ARM / RAM / en "significa que los datos y el código se entremezclan en ARM". ¿Correcto?
Bjarke Freund-Hansen
@bjarkef: La primera vez sí, pero no la segunda. Lo arreglaré.
Ben Voigt
17

El diseño exacto de la memoria mientras se ejecuta un proceso depende completamente de la plataforma que esté utilizando. Considere el siguiente programa de prueba:

#include <stdlib.h>
#include <stdio.h>

int main()
{
    int stackValue = 0;
    int *addressOnStack = &stackValue;
    int *addressOnHeap = malloc(sizeof(int));
    if (addressOnStack > addressOnHeap)
    {
        puts("The stack is above the heap.");
    }
    else
    {
        puts("The heap is above the stack.");
    }
}

En Windows NT (y sus hijos), este programa generalmente producirá:

El montón está encima de la pila

En cajas POSIX, va a decir:

La pila está por encima del montón

El modelo de memoria UNIX está bastante bien explicado aquí por @Sdaz MacSkibbons, por lo que no lo reiteraré aquí. Pero ese no es el único modelo de memoria. La razón por la cual POSIX requiere este modelo es la llamada al sistema sbrk . Básicamente, en un cuadro POSIX, para obtener más memoria, un proceso simplemente le dice al Kernel que mueva el divisor entre el "agujero" y el "montón" más adentro de la región del "agujero". No hay forma de devolver la memoria al sistema operativo, y el sistema operativo en sí no gestiona su montón. Su biblioteca de tiempo de ejecución C tiene que proporcionar eso (a través de malloc).

Esto también tiene implicaciones para el tipo de código realmente utilizado en los binarios POSIX. Los cuadros POSIX (casi universalmente) usan el formato de archivo ELF. En este formato, el sistema operativo es responsable de las comunicaciones entre bibliotecas en diferentes archivos ELF. Por lo tanto, todas las bibliotecas usan código independiente de la posición (es decir, el código en sí mismo puede cargarse en diferentes direcciones de memoria y seguir funcionando), y todas las llamadas entre bibliotecas se pasan a través de una tabla de búsqueda para averiguar dónde debe saltar el control para cruzar función de biblioteca llama. Esto agrega algo de sobrecarga y puede explotarse si una de las bibliotecas cambia la tabla de búsqueda.

El modelo de memoria de Windows es diferente porque el tipo de código que usa es diferente. Windows usa el formato de archivo PE, que deja el código en formato dependiente de la posición. Es decir, el código depende de dónde se carga exactamente el código en la memoria virtual. Hay una bandera en la especificación de PE que le dice al sistema operativo dónde exactamente en la memoria la biblioteca o el ejecutable le gustaría mapearse cuando se ejecuta su programa. Si un programa o biblioteca no se puede cargar en su dirección preferida, el cargador de Windows debe volver a crearla biblioteca / ejecutable, básicamente, mueve el código dependiente de la posición para apuntar a las nuevas posiciones, lo que no requiere tablas de búsqueda y no se puede explotar porque no hay una tabla de búsqueda para sobrescribir. Desafortunadamente, esto requiere una implementación muy complicada en el cargador de Windows y tiene una considerable sobrecarga de tiempo de inicio si una imagen necesita ser modificada. Los grandes paquetes de software comercial a menudo modifican sus bibliotecas para comenzar a propósito en diferentes direcciones para evitar rebases; Windows hace esto con sus propias bibliotecas (por ejemplo, ntdll.dll, kernel32.dll, psapi.dll, etc., todas tienen direcciones de inicio diferentes de forma predeterminada)

En Windows, la memoria virtual se obtiene del sistema a través de una llamada a VirtualAlloc , y se devuelve al sistema a través de VirtualFree (Ok, técnicamente VirtualAlloc se concentra en NtAllocateVirtualMemory, pero eso es un detalle de implementación) (Compare esto con POSIX, donde la memoria no puede ser reclamado). Este proceso es lento (y IIRC requiere que lo asignes en trozos de tamaño de página físico; típicamente 4kb o más). Windows también proporciona sus propias funciones de almacenamiento dinámico (HeapAlloc, HeapFree, etc.) como parte de una biblioteca conocida como RtlHeap, que se incluye como parte del propio Windows, en el que mallocnormalmente se implementa el tiempo de ejecución C (es decir, y amigos).

Windows también tiene bastantes API de asignación de memoria heredadas de los días en que tenía que lidiar con los viejos 80386, y estas funciones ahora están construidas sobre RtlHeap. Para obtener más información sobre las diversas API que controlan la administración de memoria en Windows, consulte este artículo de MSDN: http://msdn.microsoft.com/en-us/library/ms810627 .

Tenga en cuenta también que esto significa en Windows un solo proceso y (y generalmente lo hace) tener más de un montón. (Normalmente, cada biblioteca compartida crea su propio montón).

(La mayor parte de esta información proviene de "Codificación segura en C y C ++" de Robert Seacord)

Billy ONeal
fuente
Gran información, gracias! Espero que "user487117" eventualmente regrese. :-)
Sdaz MacSkibbons
5

La pila

En la arquitectura X86, la CPU ejecuta operaciones con registros. La pila solo se usa por razones de conveniencia. Puede guardar el contenido de sus registros para apilarlos antes de llamar a una subrutina o una función del sistema y luego volver a cargarlos para continuar su operación donde lo dejó. (Podría hacerlo manualmente sin la pila, pero es una función de uso frecuente por lo que tiene soporte de CPU). Pero puedes hacer casi cualquier cosa sin la pila en una PC.

Por ejemplo, una multiplicación entera:

MUL BX

Multiplica el registro AX con el registro BX. (El resultado estará en DX y AX, DX que contiene los bits más altos).

Las máquinas basadas en pila (como JAVA VM) usan la pila para sus operaciones básicas. La multiplicación anterior:

DMUL

Esto muestra dos valores desde la parte superior de la pila y los multiplica, luego empuja el resultado nuevamente a la pila. La pila es esencial para este tipo de máquinas.

Algunos lenguajes de programación de nivel superior (como C y Pascal) usan este método posterior para pasar parámetros a funciones: los parámetros se envían a la pila en orden de izquierda a derecha y el cuerpo de la función los saca y los valores de retorno se retroceden. (Esta es una elección que hacen los fabricantes del compilador y abusa de la forma en que el X86 usa la pila).

El montón

El montón es otro concepto que existe solo en el ámbito de los compiladores. Le quita el dolor de manejar la memoria detrás de sus variables, pero no es una función de la CPU o del sistema operativo, es solo una opción de mantener el bloque de memoria que el sistema operativo proporciona. Podrías hacer esto muchas veces si quieres.

Acceder a los recursos del sistema

El sistema operativo tiene una interfaz pública para acceder a sus funciones. En DOS los parámetros se pasan en registros de la CPU. Windows usa la pila para pasar parámetros para las funciones del sistema operativo (la API de Windows).

vbence
fuente