¿Qué hace que el concepto de pila sea útil en la programación embebida?

Question

A continuación se muestra una ilustración del concepto de pila:

He leído muchas veces sobre el puntero de pila y cómo algunas variables se almacenan en SRAM en una pila.

Muchos tutoriales explican cómo funciona, pero no por qué existe este concepto.

Imagina que soy el programa y quiero guardar mi taza, mi reloj y mi sombrero en mi habitación. ¿Por qué voy a guardarlos uno encima del otro en lugar de ponerlos en lugares aleatorios de mi habitación?

El programa puede llegar a los datos siempre que tenga su dirección. Pero si el puntero de la pila pone x en la parte superior y. ¿Cómo va a llegar a y sin eliminar x entonces? Así que para mí una pila debe hacer las cosas (el acceso a los datos) aún más difícil.

¿Puede dar un ejemplo muy sencillo con registros o código ensamblador o código C para ilustrar el beneficio de este concepto de apilamiento, a saber, "Last in, first out" (LIFO)?

Answer 1

por qué existe este concepto

La pila es un mecanismo de almacenamiento temporal muy sencillo. Para ampliar tu analogía, es la mesa de entrada de tu habitación (que sacas de la pared). Ya está ahí, sabes dónde está y cómo consultarla. Así que apilas allí tu(s) objeto(s). Cuando terminas, coges tus cosas y guardas la mesa, devolviéndote tu espacio.

Si quisieras colocarlos en lugares aleatorios, primero tendrías que asignar ese espacio (ya sea en BCC o en el montón), como construir una mesa para poner el sombrero. Luego (en el caso del almacenamiento en el montón), cuando te quites el sombrero y salgas de la habitación, tendrás que deconstruir la mesa antes de irte. De lo contrario, cuando vuelvas a entrar en tu habitación y construyas una mesa para tu sombrero, acabarás quedándote sin espacio para mesas. Eso se llama pérdida de memoria ¡!

Si quieres usar una variable permanente (de BCC) sería como hacer una tabla por artículo, y siempre están ahí ocupando espacio, los uses o no.

¿Cómo va a llegar a y sin eliminar x entonces?

No hay problema. Hay otros registros (¿un estante en la habitación?) que el puntero de la pila es copiado a (SPc). Luego se añade el puntero de la pila para crear el espacio temporal en la pila. Así que SP+=1 para almacenar X . Entonces SP+=1 de nuevo para almacenar Y . El programador puede seguir accediendo a la memoria apuntada por SPc+1 . Por supuesto, la forma más eficiente es hacer SPc+2 y luego poner X en SPc+1 e Y en SPc+2 pero esa es otra historia.

Answer 2

Imagina que soy el programa y quiero guardar mi taza, mi reloj y mi sombrero en mi habitación. ¿Por qué voy a guardarlos uno encima del otro en lugar de ponerlos en lugares aleatorios de mi habitación?

No lo harías.

Pero podrías poner el abrigo, la sudadera con capucha y la camiseta en una pila, en ese orden, porque sólo necesitas la de arriba, y para usar la de abajo, tienes que usar las otras primero.

O, si se trata de una función recursiva, y sólo se necesitan las variables de la instancia más reciente de la función, al ponerlas en una pila y mirar la superior siempre se obtiene la instancia más reciente. Normalmente, un entorno de programación de propósito general generalizaría eso para todas las llamadas a funciones, de modo que no necesita analizar todo el árbol de llamadas para saber cuáles pueden ser llamadas desde cada una. Eso da una menor huella de memoria que asignar un área distinta para cada función.

Probablemente nada de esto sea específico de la programación embebida, las pilas también aparecen en los algoritmos de otros lugares.

Answer 3

Ya hay algunas respuestas muy detalladas, pero creo que podría ser útil centrarse en una de las más importantes.

Una pila le ayuda a escribir código reentrante, es decir, subrutinas que pueden ser llamadas de nuevo antes de que terminen. Las necesitas para los algoritmos recursivos y, a veces, para los manejadores de eventos.

Si intentas escribir una de estas sin pila, uno de los problemas que tienes es cómo volver de la subrutina y reanudar la ejecución. Tienes que guardar el estado original del programa en algún lugar, y si la subrutina es llamada de nuevo, tiene que poner la nueva información en algún otro lugar sin sobrescribir la otra información.

Otro problema que se presenta es cuando una subrutina necesita datos temporales locales. Si se llama a la misma función de forma recursiva, cada llamada necesita sus propios datos locales que no sobrescribirán los datos de las llamadas anteriores.

Una pila no es la única manera de hacer esto, pero es la solución que todo el mundo acabó utilizando porque es muy sencilla: se asigna un nuevo bloque de memoria restando el número de bytes que se necesita del puntero de la pila. Asignar memoria desde un montón es mucho más lento y complicado. Además, los programas utilizaban la pila con tanta frecuencia que la mayoría de las CPUs la incorporaron a sus conjuntos de instrucciones.

Answer 4

Cuando llegas y entras en tu habitación asignas tres cajas. Las apilas en sus lados para que puedas ver el extremo abierto de cada caja. Pones el sombrero, el reloj y la taza en las cajas, un objeto en cada una. Esa es la clave para que la pila sea útil para la computación de propósito general. Puedes tener acceso aleatorio a tu pila asignada durante el tiempo que estés en tu habitación. Cuando te mudas, liberas esas cajas y las devuelves al montón de cajas de la pila vacías.

Consigues tu habitación, vas a asignar una caja, la colocas de tal manera que el lado abierto esté de cara a ti (no está arriba o abajo sino a un lado). Pon tu taza en ella. Vas a asignar otra caja, la colocas encima de la primera caja apilada, también con el extremo abierto hacia ti, y pones tu sombrero en ella. Repite la operación hasta que tengas los artículos deseados almacenados en cajas de apilamiento. Mientras dure tu estancia puedes acceder al azar (cualquier artículo en cualquier orden) a cualquiera de las veces de tu pila. Cuando te vayas, vacías y devuelves una caja a la vez del propietario de las cajas de la pila.

Es cierto que apilarlas de forma que el extremo abierto quede cubierto por la siguiente caja de la pila y sólo se pueda acceder al elemento de la parte superior de la pila no funciona ni tiene sentido para la informática de propósito general (con lenguajes de programación compilados de alto nivel). Hay un caso de uso que se encuentra en algunos procesadores. Las direcciones de retorno de las llamadas a funciones. Se anidan las llamadas a funciones y no se puede hacer trampa, hay que regresar de una antes de poder regresar de la siguiente superior. Así que puedes usar una pila de tal manera que sólo puedes ver en cualquier momento el contenido del elemento en la parte superior de la pila y todos los demás están bloqueados de la vista.

Así que, ¿por qué no probarlo?

unsigned int fun ( unsigned int a, unsigned int b )
{
    unsigned int x;
    x=b;
    return a+x;
}

Sin optimizar:

Disassembly of section .text:

00000000 <fun>:
   0:   e24dd010    sub sp, sp, #16
   4:   e58d0004    str r0, [sp, #4]
   8:   e58d1000    str r1, [sp]
   c:   e59d3000    ldr r3, [sp]
  10:   e58d300c    str r3, [sp, #12]
  14:   e59d2004    ldr r2, [sp, #4]
  18:   e59d300c    ldr r3, [sp, #12]
  1c:   e0823003    add r3, r2, r3
  20:   e1a00003    mov r0, r3
  24:   e28dd010    add sp, sp, #16
  28:   e12fff1e    bx  lr

Tenemos idealmente tres cosas en la pila, copia de a, copia de b y x. Son 12 bytes. La convención de llamada para esta herramienta y objetivo dice que la pila debe estar alineada en un límite de 64 bits, por lo que el compilador en su lugar asigna 16 bytes.

   0:   e24dd010    sub sp, sp, #16

Ajustar el puntero de la pila, similar a hacer cuatro push en la pila. La pila crece hacia abajo (bastante común) en el espacio de direcciones. La pila crece hacia arriba desde las direcciones más bajas hacia las más altas.

En este momento no sabemos ni nos importa lo que hay en esas ubicaciones de la pila. Suponemos que es basura.

   4:   e58d0004    str r0, [sp, #4]

Esta es la clave de su comprensión. El puntero de la pila se puede utilizar con un desplazamiento (no era y no es siempre el caso). Así que usted 1) no tiene que empujar para asignar y 2) no tiene que pop para descubrir y descubrir los elementos que fueron empujados.

r0 es donde se pasa la variable a así:

[sp+12] [sp+8] [sp+4] escriba aquí la variable a (r0) [sp+0]

   8:   e58d1000    str r1, [sp]

r1 contiene la variable b según la convención

[sp+12] [sp+8] [sp+4] a [sp+0] escriba b aquí

   c:   e59d3000    ldr r3, [sp]

[sp+12] [sp+8] [sp+4] a [sp+0] b

leer el valor b de la pila en r3

  10:   e58d300c    str r3, [sp, #12]

[sp+12] esto es x, escribe r3 (el valor b) aquí [sp+8] [sp+4] a [sp+0] b

  14:   e59d2004    ldr r2, [sp, #4]

leer a en r2

[sp+12] x [sp+8] [sp+4] a [sp+0] b

  18:   e59d300c    ldr r3, [sp, #12]

leer x en r3

[sp+12] x [sp+8] [sp+4] a [sp+0] b

  1c:   e0823003    add r3, r2, r3

sumar r2 (a) y r3 (x) y guardar en r3

  20:   e1a00003    mov r0, r3

hacer de r3 (a+x)(que es a+b) el valor de retorno (r0)

sip, absolutamente podrían haber hecho una suma r0,r3,r2 pero esto no está optimizado y por el momento r3 mantiene x

  24:   e28dd010    add sp, sp, #16

siempre devuelve la pila (puntero) tal y como la encontraste

  28:   e12fff1e    bx  lr

Para ser justos, esto es lo que hace la optimización:

00000000 <fun>:
   0:   e0810000    add r0, r1, r0
   4:   e12fff1e    bx  lr

Aquí hay otro y este está técnicamente conectado con los primeros días del concepto de pila.

unsigned int more_fun ( unsigned int );
unsigned int fun ( unsigned int a, unsigned int b )
{
    return(a+more_fun(b));
}

Optimizado:

00000000 <fun>:
   0:   e92d4010    push    {r4, lr}
   4:   e1a04000    mov r4, r0
   8:   e1a00001    mov r0, r1
   c:   ebfffffe    bl  0 <more_fun>
  10:   e0800004    add r0, r0, r4
  14:   e8bd4010    pop {r4, lr}
  18:   e12fff1e    bx  lr

Si ayuda a entenderlo, esto es el equivalente funcional de lo anterior:

push {lr}     
push {r4}     
mov r4, r0        
mov r0, r1        
bl  <more_fun>  
add r0, r0, r4    
pop {r4}
pop {lr}      
bx  lr            

Así que hay varias cosas que suceden aquí. Estamos empujando dos cosas en la pila. r4 y lr. Por la convención de llamada no podemos destruir r4 (r0-r3 sí, no r4). Así que si queremos usar r4 tenemos que guardarlo y restaurarlo (uso perfecto de la pila). lr contiene la dirección de retorno de la función. bl modifica lr, así que tenemos que guardar lr para esta función para que la llamada a more_fun no pierda nuestro lugar en el mundo. r0 es el primer parámetro, a, para la llamada a fun, también es el primer parámetro de la llamada a more_fun así como el valor de retorno de more_fun, así que tenemos que guardar a en algún sitio, y el compilador eligió usar r4, que veremos por qué más adelante. En lugar de guardar r0 en la pila, guarda algún otro registro en la pila (que more_fun y todas las llamadas a funciones anidadas devolverán/dejarán sin tocar) y guarda r0 (a) en ese registro (r4).

He creado esta función para que la variable a se utilice después de la llamada a more_fun, lo que significa que tenemos que recordar la variable a a través de una llamada. Y el compilador eligió empujar r4 y guardar a en r4.

   0:   e92d4010    push    {r4, lr}

guardar la dirección de retorno y conservar el contenido de r4 para poder utilizarlo en la función

   4:   e1a04000    mov r4, r0

guardar el valor a en r4

   8:   e1a00001    mov r0, r1

el valor b (r1) es el primer parámetro (r0) de la llamada a more_fun, prepara la llamada a more_fun poniendo b en r0

   c:   ebfffffe    bl  0 <more_fun>

llamar a more_fun

  10:   e0800004    add r0, r0, r4

sumar el valor de retorno de more_fun y la variable en r4 (a) y guardar en r0 (el valor de retorno de fun())

  14:   e8bd4010    pop {r4, lr}

restaurar el contenido de r4 al valor encontrado cuando la función comenzó. restaurar la dirección de retorno de fun()

  18:   e12fff1e    bx  lr

retorno de la llamada a la función.

Quizá se pregunte por qué no hacerlo así:

push {r0}
mov r0, r1
push {lr}
bl  0 <more_fun>
pop {lr}
pop {r1}
add r0, r0, r1
bx  lr

push {r0}

guardar la variable a en la pila la necesitamos más tarde

mov r0, r1

preparar la llamada a more_fun poniendo b como primer parámetro

push {lr}

bl modifica lr, lr es la dirección que necesitamos devolver de fun() por lo que necesitamos guardarla temporalmente en la pila.

bl  0 <more_fun>

llame a más diversión (tenga en cuenta que esto está desvinculado el enlazador rellenaría la dirección relativa más tarde)

pop {lr}

restaurar la dirección de retorno a lr

pop {r1}

recuperar el valor de la variable a en r1

add r0, r0, r1

añade el valor de retorno de more_fun más la variable a. r0 es el valor de retorno de la función fun()

bx  lr

retorno de fun();

Si la convención de llamada no tenía una regla de alineación de la pila no hay nada de malo en que el compilador genere código así. Utiliza mucho menos espacio en la pila cuando empiezas a anidar funciones (lo que hacemos normalmente). Solemos llegar a quemar un segundo registro como puntero de marco, añadir más instrucciones por función para preparar el marco y restaurarlo al final. ¿Por qué? para poder desenrollar pilas con herramientas de depuración, no me sirven los depuradores y menos desenrollar pilas de alguna manera automática. Personalmente no tengo necesidad de quemar permanentemente código y espacio de memoria para algo que nunca usaré.

Pre-asignar todo lo que necesitamos para la duración de la función hace que sea más fácil de leer para los humanos (una variable específica en la pila estará o puede estar siempre en un desplazamiento fijo de la pila o del puntero del marco (ambos)). Esto facilita la generación de código desde el compilador y facilita la depuración del código generado, lo que hace que el compilador sea más fiable y tenga menos errores. A costa de la memoria para el usuario. Los propios autores del compilador son más que capaces de escribir código para llevar la cuenta de los elementos de la pila durante la función

[sp+0] variable a

empuje b

[sp+4] variable a [sp+0] variable b

Se puede generar fácilmente código para saber que en este punto de la función a está en [sp+4]

pop b

[sp+0] variable a

y en este punto de la función a está en [sp+0].

Buena suerte para conseguir que los compiladores lo hagan. Es lo que es, si se utiliza un lenguaje de alto nivel se acepta automáticamente un mayor consumo de código y datos y un golpe de rendimiento. Es cierto que se obtiene más código de calidad, depurado y más fácil de mantener y reutilizar.

Pero a partir de un concepto tradicional, elemental, de escribir cosas en una tarjeta de notas y apilar las tarjetas de notas para guardar cosas temporalmente . Esto demuestra que

push {r0}
mov r0, r1
push {lr}
bl  0 <more_fun>
pop {lr}
pop {r1}
add r0, r0, r1
bx  lr

Ahora, ¿por qué empujar r4 y no r0?

push {r4, lr}      push {r0,lr}
mov r4, r0         
mov r0, r1         mov r0,r1
bl  0 <more_fun>   bl more_fun
                   ldr r1,[sp]
add r0, r0, r4     add r0,r0,r1
pop {r4, lr}       pop {r1,lr}
bx  lr             bx lr

mismo número de instrucciones. Pero cambias una operación de registro por una operación de memoria que es más lenta/peor. Así que hacer lo de r4 ya es mejor aquí. Añade más variables (no demasiadas) y hay un punto dulce en el que usar más registros en la función (r4,r5,r6...) empujándolos al principio y sacándolos al final, es mucho más eficiente que hacer accesos a la pila durante la función, no sólo una instrucción más lenta cambiada por otra.

Se puede prescindir de las pilas si se puede prescindir de los lenguajes de programación (relativamente modernos) (si se escribe en lenguaje ensamblador, por ejemplo). Los lenguajes compilados dan lugar a convenciones de llamada y a variables locales y globales. Las variables locales, las direcciones de retorno, etc. conducen a una pila y a un puntero de pila y a un direccionamiento relativo del puntero de pila. Sin las instrucciones de direccionamiento relativo del puntero de la pila (o del marco de la pila), los lenguajes compilados se vuelven mucho menos atractivos para ese procesador.

Answer 5

En muchas situaciones, es necesario completar los pasos secundarios antes de poder completar los pasos más grandes. Piensa en las instrucciones para construir legos. De vez en cuando hay que parar y decir "Vale, deja la gran creación. Tenemos que armar una pieza más pequeña que será más fácil de construir por sí sola".

Si me permite usar su ejemplo:

Imagina que soy el programa y quiero guardar mi taza, mi reloj y mi sombrero en mi habitación. ¿Por qué voy a guardarlos uno encima del otro en lugar de ponerlos en lugares aleatorios de mi habitación?

Ahora estoy seguro de que no quisiste decir "aleatorio". Querías decir "arbitrario". Aleatorio significa que tendrías que ir a buscar tu reloj cada vez - algo que el código embebido intenta evitar hacer. Querías decir que los pondrías en lugares individuales, no uno encima del otro.

Así que vamos a escribir algunas instrucciones. Aquí está parte de la rutina de "despertar". (ignora el énfasis por ahora, tendrá sentido más tarde)

1. Coge la taza que está en la esquina inferior derecha de la mesita de noche de tu habitación.
2. Beber zumo de naranja en el vaso
3. Ponga la taza en la esquina inferior derecha de la mesita de noche de su habitación .
4. Recoge el reloj del centro de la mesita de noche de su habitación
5. Poner el reloj en la muñeca
6. Recoger el sombrero de la parte superior de la mesita de noche de su habitación
7. Ponte el sombrero.

Ahora, vayamos de vacaciones. Somos animales de costumbres, así que queremos seguir la misma rutina al despertarnos. Sin embargo, hay un problema. Las instrucciones anteriores especifican "la mesita de noche de tu habitación". Esa habitación está a cientos de kilómetros de distancia. Estás en una habitación de hotel. Así que escribimos otra rutina, "wakeupInHotel"

1. Recoge el vaso que está en la esquina inferior derecha de la mesita de noche en la habitación del hotel .
2. Beber zumo de naranja en el vaso
3. Ponga la taza en la esquina inferior derecha de la mesita de noche de la habitación del hotel .
4. Recoge el reloj del centro de la mesita de noche en la habitación del hotel
5. Poner el reloj en la muñeca
6. Recoger el sombrero de la parte superior de la mesita de noche en la habitación del hotel
7. Ponte el sombrero.

Esto funciona, sólo sustituimos una sección en negrita por otra. Pero obviamente esta es una forma difícil de escribir código. Tienes que escribir una versión diferente para cada habitación en la que estés. Hay veces que se escribe de esta forma (por rapidez), pero normalmente queremos hacer instrucciones más genéricas como "wakeupIn(currentRoom)":

1. Recoge el vaso que está en la esquina inferior derecha de la mesita de noche en currentRoom .
2. Beber zumo de naranja en el vaso
3. Ponga la taza en la esquina inferior derecha de la mesita de noche en currentRoom .
4. Recoge el reloj del centro de la mesita de noche en currentRoom
5. Poner el reloj en la muñeca
6. Recoger el sombrero de la parte superior de la mesita de noche en currentRoom
7. Ponte el sombrero.

Ahora puedo tener "wakeupInRoom(myBedroom)" y "wakeupInRoom(hotel)" que ejecutan las instrucciones anteriores en el contexto de currentRoom=miHabitación o currentRoom=miHotel. Es mucho más eficiente y se parece más a la forma en que queremos prepararnos por la mañana.

Así que lo que necesitamos es un lugar para almacenar esta información de alcance que describe el medio ambiente en la que se está ejecutando la función. Esto no tiene que ser una pila. Puedes poner la información en cualquier lugar, y hacer que el contexto sea sólo un puntero a él.

Sin embargo, volviendo al proceso de ensamblaje de los lego, nos encontramos con que muy a menudo estos contextos empiezan a anidarse. Se empieza a construir un producto grande. Luego se pasa a construir un subcomponente más pequeño hasta que se completa, y entonces se reanuda el montaje del producto grande. A continuación, se pasa a construir otro subcomponente. Piensa en IKEA.

Cuando se produce este patrón de subpasos, nos damos cuenta de algo útil. El contexto del subpaso no es necesario hasta el momento en que se llama al subproceso. Y una vez que el subproceso se completa, ya no necesitas el contexto para él. Así que terminas con este patrón en el que tienes este gran árbol de contextos (quizás tienes 1 contexto para poner cada rueda del artilugio lego, usando la misma subrutina "putOnWheel"). La mayor parte de ese árbol está inactivo y no es necesario la mayor parte del tiempo. Es ineficiente.

Entonces, ¿qué debemos conservar? Necesitamos mantener el contexto actual, obviamente. Y necesitamos mantener los contextos de los pasos más grandes para que cuando hayamos terminado con nuestro paso actual, podamos volver al proceso más grande.

Si observas la estructura, te das cuenta de que una pila es una forma muy eficiente de mantener el control de estos datos. No tienes que mantener todo el árbol, sólo el camino desde la tarea raíz hasta tu tarea actual.

Una pila tiene algunos beneficios particulares:

• La CPU sólo tiene que llevar la cuenta de un puntero: la parte superior de la pila. El resto no es importante hasta que la tarea actual regrese. También almacenamos el "puntero de retorno" en la pila, de modo que la CPU sólo ve la parte superior de la pila, y podemos utilizar la memoria normal para manejar el resto de la cadena. Esto significa que la CPU no necesita ninguna función complicada para soportar esta estructura. Sólo un único puntero.
• Esta estructura no desperdicia memoria. Sólo tiene el "puntero de retorno" extra que necesita para apoyar la idea de volver a la tarea más grande, y nada más.
• El programa puede reutilizar la memoria de la pila para llamadas con diferentes contextos. A medida que te adentres en la programación embebida de orden superior (como C) te acostumbrarás a la idea de que cada ubicación de memoria tiene un "tipo", que es el tipo de datos que se almacena en ella. No puedes cambiar estos tipos una vez elegidos. Dado que podemos "tirar" los contextos después de haber terminado con ellos, podemos tratar el espacio justo por encima de la "parte superior de la pila" como nada más que "espacio no asignado" hasta que llames a algo usando ese espacio. Esto hace que la contabilidad sea tremendamente sencilla.

Así que, al final, utilizamos la pila porque es la estructura de datos perfecta para mantener estos patrones jerárquicos de subtareas. Y, a lo largo de las décadas, los programadores han encontrado abrumadoramente que las cosas que queremos que hagan los ordenadores encajan en este patrón de subtareas. Y es por eso que básicamente todos los ordenadores tienen una pila.

La excepción, por supuesto, son los procesadores integrados ultradimensionales. Son lo suficientemente pequeños como para no poder hacer mucho, así que no hay mucha oportunidad de hacer el tipo de optimizaciones que mostramos en la rutina de activación. En esos procesadores, cualquier cosa que quieras hacer puede ser escrita a mano. Esto requiere más esfuerzo (y a veces más habilidad), pero evita desperdiciar los preciosos bytes para el "puntero de retorno". También significa que no necesitas las instrucciones de la CPU necesarias para manipular una pila, por lo que puedes tener un conjunto de instrucciones más pequeño. Pero fuera de estos casos extremos, utilizamos las pilas porque funcionan.