¿Hay alternativas para apilar + montón + modelo de memoria estática?

9

Todos los programas que he visto organizan su memoria de datos en una o más pilas de llamadas (generalmente de tamaño fijo, pero a veces no), el montón y la memoria estática. Últimamente, el almacenamiento estático de subprocesos locales también se ha agregado a esto.

¿Ha habido intentos de organizar el diseño de la memoria de datos de una manera radicalmente diferente, por ejemplo, sin la pila de llamadas? ¿O organizar la memoria de una manera diferente que logre lo mismo?

ikh
fuente
Depende de lo que quieras decir con "apilar". Puede colocar los marcos de la pila de llamadas en el montón (vincularlos con punteros). Entonces no tiene una región de memoria lineal dedicada para la pila, pero conceptualmente todavía tiene una pila de llamadas.
y depende de lo que quieras decir con "recientemente". Creo que el almacenamiento local de subprocesos es tan antiguo como los subprocesos. Pero anteriormente era accesible a través de llamadas al sistema, mientras que ahora los idiomas más nuevos le dan acceso a él directamente.
DXM
La pila de llamadas es necesaria porque las funciones de procedimiento necesitan saber quién las llamó para que puedan devolver resultados y continuar la ejecución. El mecanismo actual, si lo hace, es bastante barato en términos de ciclos de CPU y con x64 al menos, casi todos los argumentos de función se pasan a través de registros
James
2
Puede encontrar la publicación de Eric Lippert, ¿Por qué tener una pila? de interés. Su punto principal es que una pila proporciona una manera eficiente y simple de rastrear ubicaciones de memoria. Él discute una alternativa en varias publicaciones mucho más antiguas, Continuation Passing Style .
Brian

Respuestas:

8

Es posible que desee retroceder y ver de dónde y por qué provienen esos modelos existentes. Cuando se crea un proceso, simplemente se le da un área de almacenamiento plana que simplemente se indexa de 0 a N. Debido a que esta área de almacenamiento (hablando de RAM aquí) está respaldada por un hardware dedicado y algunos semiconductores sofisticados, resulta ser bastante rápido, pero no es el único de su tipo. Otros dispositivos, como los discos duros, son esencialmente lo mismo, espacio plano direccionable por un índice, pero muchos órdenes de magnitud más lentos.

La razón por la que existe "un montón" es porque no sería práctico para cada aplicación intentar administrar el uso de RAM por sí mismo. En el pasado, así fue exactamente como sucedió, los programadores planearon con anticipación exactamente para qué se usaría cada ubicación de RAM. Como el software se volvió más complejo, alguien dijo: ¿no sería bueno si pudiera ir a un recuadro negro y decir "Necesito 10 bytes así que dame" y no tener que preocuparme por todos los detalles intrincados de dónde y cómo esos 10 bytes provienen o cómo se recuperan. Eso es un montón, realmente no se vuelve más básico que eso.

Cada vez que se crea un subproceso, hay algunas estructuras de datos (y una pila), que se adquieren utilizando la misma "operación Gimme" que acabo de describir. Una pila casi universalmente utilizada porque encaja perfectamente con los marcos de pila de llamadas de función y su naturaleza LIFO. En teoría, la invocación de cada función y las variables locales podrían asignarse en el montón, pero eso simplemente sería demasiado costoso, en comparación con solo unas pocas instrucciones de ensamblaje que se necesitan para actualizar el registro del puntero de pila (ESP en x86).

El almacenamiento local de subprocesos (TLS) también está integrado en la parte superior del montón. Cuando se crea un subproceso, como parte de un viaje al montón para asignar memoria para las estructuras de administración, también se asigna un espacio separado para TLS desde el montón.

Entonces, al final, todo lo que realmente tiene es un asignador de memoria genérico (es decir, el montón) y todo lo demás es una forma especializada además de eso. En otras palabras, si está dispuesto a renunciar a algún aspecto de "Quiero asignar tanto (o tan poco) como quiera, manténgalo todo el tiempo que quiera y libre cuando quiera", podría salirse del comercio fuera del asignador genérico de almacenamiento dinámico para otro modelo que ofrece velocidad pero a costa de alguna otra limitación.

Toma pila. Es increíblemente rápido en comparación con el montón, pero las dos compensaciones son 1) no se controla cuando se libera la memoria; en cambio, una vez que la función se cierra, lo que haya asignado se ha ido y 2) debido a que las pilas generalmente tienen un tamaño limitado, debe tener cuidado al asignar grandes cantidades de datos directamente en la pila.

Otro tipo de "modelo de memoria" es el Virtual Memory Manager (VMM) ofrecido por casi todos los principales sistemas operativos a través de llamadas al sistema. VMM es muy similar al montón en el sentido de que puede solicitar cualquier cantidad de memoria y mantenerla todo el tiempo que desee. Sin embargo, la limitación es que solo puede asignar memoria en múltiplos de tamaño de página (por ejemplo, 4KB), por lo que usar VMM directamente causaría una gran sobrecarga en una aplicación típica que a menudo asigna 8-24 bytes a la vez. De hecho, casi todas las implementaciones de almacenamiento dinámico se crean sobre VMM específicamente con el fin de permitir una asignación de bloques pequeños muy genérica, no especializada . El almacenamiento dinámico va a VMM cada vez que necesita más memoria y luego distribuye muchos fragmentos pequeños de esa memoria a la aplicación.

Si tiene una aplicación, que necesita asignar bloques grandes, puede considerar ir directamente a VMM, aunque algunos montones tienen una declaración if dentro de malloc () y si el tamaño del bloque es mayor que algún umbral, simplemente van a VMM para ti.

Otra forma de asignadores en lugar de usar directamente el montón, serían los grupos. Un grupo es un asignador especializado donde todos los bloques son del mismo tamaño. Las agrupaciones (al igual que stack y TLS) se crean sobre el montón o VMM. Las piscinas son útiles en lugares donde se asignan muchos (millones) de objetos pequeños de corta duración del mismo tamaño. Piense en un servicio de red que procesa solicitudes entrantes. Las solicitudes de cada cliente pueden dar como resultado que se asigne la misma estructura de N bytes para manejar esa solicitud. La desventaja de usar grupos es que cada grupo solo maneja un tamaño de bloque (pero puede crear múltiples grupos). La ventaja de los grupos es que, dado que todos los objetos son del mismo tamaño, no requiere una lógica compleja. En cambio, cada vez que necesita un nuevo bloque, solo le da el que se liberó recientemente.

Y por último, recuerda esa cosa del disco duro que mencioné arriba. Podría tener un modelo de memoria que se comporte como un sistema de archivos y duplique la misma idea de entradas de directorio y nodos-i para permitir la asignación jerárquica de bloques de datos donde cada bloque de datos se direcciona con una ruta. Eso es exactamente lo que hace tmpfs .

Más allá de lo que mencioné, estoy seguro de que hay otros modelos más especializados, pero al final ya que todo se basa en el espacio de direcciones planas (hasta que algunos genuinos tengan algún tipo de espacio extraño, no $$ plano ), todo vuelve a ese asignador genérico "dame" que es VMM o el montón.

DXM
fuente
1

Los únicos casos en los que puedo pensar son en hardware especializado donde puede tener todo ejecutándose en ubicaciones fijas en la memoria. Se requiere casi todo en el modelo de memoria actual si desea programas completamente flexibles.

Sin la pila, no puede tener variables locales, pilas de llamadas, etc. Cualquier otra cosa que escriba para implementar terminará pareciéndose mucho a la pila.

La memoria estática y el montón que podría dejar caer para ciertas aplicaciones, pero nuevamente los necesitará de una forma u otra para hacer algo más avanzado.

Entonces, cualquier cosa que inventes para reemplazar uno de estos tres terminará pareciéndose mucho a uno de estos tres al final ...

Para abordarlo desde el otro ángulo, ¿qué podría agregar que sea nuevo? Podría argumentar que cosas como gráficos / procesadores físicos / cachés de CPU / etc. son una nueva ubicación de memoria, pero en realidad son solo una instancia separada o una forma de acelerar el acceso a los modelos existentes.

... así que hasta que alguien presente un salto conceptual gigante de algún tipo, creo que es poco probable que veamos cambios importantes en esta área durante mucho tiempo ...

Tim B
fuente
44
La mayoría de las personas tiende a suponer que la forma actual es la mejor / única forma, y ​​si se le da una pizarra en blanco, simplemente copiará lo que ya existe. Las otras personas son las que realmente avanzan el progreso tecnológico. No quiere decir que yo personalmente conozco ningún modelos de la competencia graves (a menos que contar los ordenadores cuánticos), pero afirmando que todo lo que uno podría llegar a miraría lo mismo que lo que ya existe es esencialmente una forma de razonamiento circular.
Aaronaught
@Aaronaught: la otra cara de su argumento es que otras personas gastan toneladas de tiempo, dinero y energía pensando fuera de la caja y por cada 1000 (tal vez mucho más) de ellos, uno eventualmente podría avanzar en el progreso tecnológico, mientras que el resto no llega a ninguna parte . Mientras que el primer grupo, a quien se podría considerar más práctico, toma estos modelos existentes tal cual e innova sobre ellos :)
DXM
@aaronaught Creo que lo cubrí con "hasta que alguien presente un salto conceptual gigante de algún tipo";) Si tiene un modelo alternativo mejor, no dude en sugerirlo ... si no, se siente un poco hipócrita quejarse "algunas personas" cuando eres uno de ellos :)
Tim B
1
@DXM: ¿Entonces? ¿Dije que todos deberíamos invertir nuestro tiempo en investigar nuevos modelos de memoria? Solo estaba señalando la falla (significativa) en la afirmación de que una persona solo puede inventar cosas que ya se han inventado.
Aaronaught
Un reclamo que nunca hice ...
Tim B