El orden de la memoria describe el orden de acceso a la memoria de la computadora por parte de una CPU. El término puede referirse al orden de memoria generado por el compilador durante el tiempo de compilación , o al orden de memoria generado por una CPU durante el tiempo de ejecución .
En los microprocesadores modernos , la ordenación de la memoria caracteriza la capacidad de la CPU para reordenar las operaciones de la memoria; es un tipo de ejecución desordenada . El reordenamiento de la memoria se puede utilizar para utilizar completamente el ancho de banda del bus de diferentes tipos de memoria, como cachés y bancos de memoria .
En la mayoría de los monoprocesadores modernos, las operaciones de memoria no se ejecutan en el orden especificado por el código del programa. En los programas de un solo subproceso, todas las operaciones parecen haberse ejecutado en el orden especificado, con toda la ejecución fuera de orden oculta para el programador; sin embargo, en entornos de subprocesos múltiples (o cuando se interactúa con otro hardware a través de buses de memoria), esto puede llevar a problemas. Para evitar problemas, se pueden utilizar barreras de memoria en estos casos.
Orden de memoria en tiempo de compilación
La mayoría de los lenguajes de programación tienen alguna noción de un hilo de ejecución que ejecuta declaraciones en un orden definido. Los compiladores tradicionales traducen expresiones de alto nivel a una secuencia de instrucciones de bajo nivel relativas a un contador de programa en el nivel de la máquina subyacente.
Los efectos de ejecución son visibles en dos niveles: dentro del código del programa en un nivel alto, y en el nivel de la máquina como lo ven otros subprocesos o elementos de procesamiento en la programación concurrente , o durante la depuración cuando se usa una ayuda de depuración de hardware con acceso al estado de la máquina ( algo de soporte para esto a menudo se integra directamente en la CPU o el microcontrolador como un circuito funcionalmente independiente aparte del núcleo de ejecución que continúa funcionando incluso cuando el núcleo mismo se detiene para una inspección estática de su estado de ejecución). El orden de la memoria en tiempo de compilación se relaciona con el primero y no con estos otros puntos de vista.
Problemas generales del orden del programa
Efectos de la evaluación de expresiones en el orden del programa
Durante la compilación, las instrucciones de hardware a menudo se generan con una granularidad más fina que la especificada en el código de alto nivel. El principal efecto observable en una programación procedimental es la asignación de un nuevo valor a una variable nombrada.
suma = a + b + c; imprimir (suma);
La declaración de impresión sigue a la declaración que asigna a la variable suma y, por lo tanto, cuando la declaración de impresión hace referencia a la variable calculada, sum
hace referencia a este resultado como un efecto observable de la secuencia de ejecución anterior. Según lo definido por las reglas de secuencia del programa, cuando la print
llamada a la función hace referencia sum
, el valor de sum
debe ser el de la asignación ejecutada más recientemente a la variable sum
(en este caso, la instrucción inmediatamente anterior).
A nivel de máquina, pocas máquinas pueden sumar tres números en una sola instrucción, por lo que el compilador tendrá que traducir esta expresión en dos operaciones de suma. Si la semántica del lenguaje del programa restringe al compilador a traducir la expresión en orden de izquierda a derecha (por ejemplo), entonces el código generado se verá como si el programador hubiera escrito las siguientes declaraciones en el programa original:
suma = a + b; suma = suma + c;
Si al compilador se le permite explotar la propiedad asociativa de la suma, podría generar en su lugar:
suma = b + c; suma = a + suma;
Si al compilador también se le permite explotar la propiedad conmutativa de la suma, podría generar en su lugar:
suma = a + c; suma = suma + b;
Tenga en cuenta que el tipo de datos enteros en la mayoría de los lenguajes de programación solo sigue el álgebra para los números enteros matemáticos en ausencia de desbordamiento de enteros y que la aritmética de punto flotante en el tipo de datos de punto flotante disponible en la mayoría de los lenguajes de programación no es conmutativa en los efectos de redondeo, lo que genera efectos del orden de expresión visible en pequeñas diferencias del resultado calculado (pequeñas diferencias iniciales pueden sin embargo convertirse en cascada en diferencias arbitrariamente grandes en un cálculo más largo).
Si al programador le preocupa el desbordamiento de enteros o los efectos de redondeo en punto flotante, el mismo programa puede codificarse en el nivel alto original de la siguiente manera:
suma = a + b; suma = suma + c;
Efectos de orden de programa que involucran llamadas a funciones
Muchos lenguajes tratan el límite de la declaración como un punto de secuencia , lo que obliga a que todos los efectos de una declaración se completen antes de que se ejecute la siguiente. Esto obligará al compilador a generar código correspondiente al orden de instrucción expresado. Sin embargo, las declaraciones suelen ser más complicadas y pueden contener llamadas a funciones internas .
suma = f (a) + g (b) + h (c);
A nivel de máquina, llamar a una función generalmente implica configurar un marco de pila para la llamada a la función, lo que implica muchas lecturas y escrituras en la memoria de la máquina. En mayoría de lenguajes compilados, el compilador es libre de ordenar las llamadas de función f
, g
y h
si lo considera conveniente, lo que resulta en cambios a gran escala de orden memoria de programa. En un lenguaje de programación funcional puro, se prohíbe que las llamadas a funciones tengan efectos secundarios en el estado visible del programa (aparte de su valor de retorno ) y la diferencia en el orden de la memoria de la máquina debido al orden de las llamadas a funciones no tendrá consecuencias para la semántica del programa. En los lenguajes de procedimiento, las funciones llamadas pueden tener efectos secundarios, como realizar una operación de E / S o actualizar una variable en el alcance del programa global, los cuales producen efectos visibles con el modelo del programa.
Una vez más, un programador preocupado por estos efectos puede volverse más pedante al expresar el programa fuente original:
suma = f (a); suma = suma + g (b); suma = suma + h (c);
En los lenguajes de programación donde el límite declaración se define como un punto de secuencia, las llamadas a funciones f
, g
y h
ahora debe ejecutar en ese orden preciso.
Problemas específicos del orden de la memoria
Efectos de orden de programa que involucran expresiones de puntero
Ahora considere la misma suma expresada con direccionamiento indirecto de punteros, en un lenguaje como C / C ++ que admite punteros :
suma = * a + * b + * c;
La evaluación de la expresión *x
se denomina " desreferenciar " a un puntero e implica leer de la memoria en una ubicación especificada por el valor actual de x
. Los efectos de la lectura de un puntero están determinados por el modelo de memoria de la arquitectura . Cuando se lee desde el almacenamiento de programa estándar, no hay efectos secundarios debido al orden de las operaciones de lectura de la memoria. En la programación de sistemas embebidos , es muy común tener E / S mapeadas en memoria donde las lecturas y escrituras en la memoria desencadenan operaciones de E / S, o cambios en el modo operativo del procesador, que son efectos secundarios muy visibles. Para el ejemplo anterior, suponga por ahora que los punteros apuntan a la memoria del programa normal, sin estos efectos secundarios. El compilador es libre de reordenar estas lecturas en el orden del programa como lo crea conveniente, y no habrá efectos secundarios visibles en el programa.
¿Qué pasa si el valor asignado también es indirecto del puntero?
* suma = * a + * b + * c;
Aquí es poco probable que la definición del lenguaje permita al compilador dividir esto de la siguiente manera:
// según lo reescrito por el compilador // generalmente prohibido * suma = * a + * b; * suma = * suma + * c;
Esto no se consideraría eficiente en la mayoría de los casos, y las escrituras de puntero tienen efectos secundarios potenciales en el estado visible de la máquina. Dado que al compilador no se le permite esta transformación de división en particular, la única escritura en la ubicación de memoria de sum
debe seguir lógicamente las lecturas de tres punteros en la expresión de valor.
Sin embargo, suponga que el programador está preocupado por la semántica visible del desbordamiento de enteros y divide la declaración en el nivel del programa de la siguiente manera:
// según la autoría directa del programador // con problemas de aliasing * suma = * a + * b; * suma = * suma + * c;
La primera instrucción codifica dos lecturas de memoria, que deben preceder (en cualquier orden) a la primera escritura *sum
. La segunda instrucción codifica dos lecturas de memoria (en cualquier orden) que deben preceder a la segunda actualización de *sum
. Esto garantiza el orden de las dos operaciones de suma, pero potencialmente introduce un nuevo problema de alias de direcciones : cualquiera de estos punteros podría potencialmente referirse a la misma ubicación de memoria.
Por ejemplo, supongamos en este ejemplo que *c
y *sum
tienen un alias en la misma ubicación de memoria, y reescribamos ambas versiones del programa *sum
sustituyendo ambas.
* suma = * a + * b + * suma;
Aquí no hay problemas. El valor original de lo que escribimos originalmente *c
se pierde en la asignación *sum
, y también el valor original de, *sum
pero esto se sobrescribió en primer lugar y no es de especial interés.
// en qué se convierte el programa con * cy * sum alias * suma = * a + * b; * suma = * suma + * suma;
Aquí el valor original de *sum
se sobrescribe antes de su primer acceso, y en su lugar obtenemos el equivalente algebraico de:
// equivalente algebraico del caso con alias anterior * suma = (* a + * b) + (* a + * b);
que asigna un valor completamente diferente *sum
debido a la reordenación de la declaración.
Debido a los posibles efectos de alias, las expresiones de puntero son difíciles de reorganizar sin arriesgar los efectos visibles del programa. En el caso común, es posible que no haya ningún alias en efecto, por lo que el código parece ejecutarse normalmente como antes. Pero en el caso límite en el que hay aliasing, pueden producirse errores graves en el programa. Incluso si estos casos extremos están completamente ausentes en la ejecución normal, abre la puerta para que un adversario malintencionado idee una entrada donde exista un alias, lo que podría conducir a una vulnerabilidad de seguridad informática .
Un reordenamiento seguro del programa anterior es el siguiente:
// declara una variable local temporal 'temp' de tipo adecuado temp = * a + * b; * suma = temp + * c;
Finalmente, considere el caso indirecto con llamadas a funciones agregadas:
* suma = f (* a) + g (* b);
El compilador puede optar por evaluar *a
y *b
antes de la llamada a la función, puede aplazar la evaluación de *b
hasta después de la llamada a la función f
o puede aplazar la evaluación de *a
hasta después de la llamada a la función g
. Si la función f
y g
están libres de efectos secundarios visibles del programa, las tres opciones producirán un programa con los mismos efectos de programa visibles. Si la implementación de f
o g
contiene el efecto secundario de cualquier escritura de puntero sujeto a alias con punteros a
o b
, las tres opciones pueden producir diferentes efectos de programa visibles.
Orden de memoria en la especificación del idioma
En general, los lenguajes compilados no están lo suficientemente detallados en su especificación para que el compilador determine formalmente en el momento de la compilación qué punteros tienen un alias potencial y cuáles no. El curso de acción más seguro es que el compilador asuma que todos los punteros tienen un alias potencial en todo momento. Este nivel de pesimismo conservador tiende a producir un desempeño terrible en comparación con la suposición optimista de que nunca existe el aliasing.
Como resultado, muchos lenguajes compilados de alto nivel, como C / C ++, han evolucionado para tener especificaciones semánticas intrincadas y sofisticadas sobre dónde se permite al compilador hacer suposiciones optimistas en el reordenamiento del código en busca del mayor rendimiento posible, y dónde el Se requiere que el compilador haga suposiciones pesimistas en el reordenamiento del código para evitar peligros semánticos.
Con mucho, la clase más grande de efectos secundarios en un lenguaje procedimental moderno implica operaciones de escritura en la memoria, por lo que las reglas sobre el ordenamiento de la memoria son un componente dominante en la definición de la semántica del orden del programa. El reordenamiento de las llamadas de funciones anteriores puede parecer una consideración diferente, pero esto generalmente se convierte en preocupaciones sobre los efectos de memoria internos a las funciones llamadas que interactúan con las operaciones de memoria en la expresión que genera la llamada de función.
Dificultades y complicaciones adicionales
Optimización bajo como si
Los compiladores modernos a veces llevan esto un paso más allá por medio de una regla como si , en la que se permite cualquier reordenamiento (incluso entre declaraciones) si no se produce ningún efecto en la semántica del programa visible. Según esta regla, el orden de las operaciones en el código traducido puede variar enormemente del orden del programa especificado. Si al compilador se le permite hacer suposiciones optimistas sobre distintas expresiones de puntero que no tienen superposición de alias en un caso donde tal alias existe realmente (esto normalmente se clasificaría como un programa mal formado que exhibe un comportamiento indefinido ), los resultados adversos de un código agresivo- La transformación de optimización es imposible de adivinar antes de la ejecución del código o la inspección directa del código. El ámbito del comportamiento indefinido tiene manifestaciones casi ilimitadas.
Es responsabilidad del programador consultar la especificación del lenguaje para evitar escribir programas mal formados donde la semántica puede cambiar como resultado de cualquier optimización legal del compilador. Fortran tradicionalmente coloca una gran carga en el programador para estar al tanto de estos problemas, y los lenguajes de programación de sistemas C y C ++ no se quedan atrás.
Algunos lenguajes de alto nivel eliminan por completo las construcciones de punteros, ya que este nivel de alerta y atención al detalle se considera demasiado alto para mantenerlo de manera confiable incluso entre programadores profesionales.
Una comprensión completa de la semántica del orden de la memoria se considera una especialización arcana incluso entre la subpoblación de programadores de sistemas profesionales que suelen estar mejor informados en esta área temática. La mayoría de los programadores se conforman con una comprensión adecuada de estos temas dentro del dominio normal de su experiencia en programación. En el extremo extremo de la especialización en semántica de orden de memoria se encuentran los programadores que crean marcos de software en apoyo de modelos informáticos concurrentes .
Aliasing de variables locales
Tenga en cuenta que no se puede suponer que las variables locales estén libres de alias si un puntero a dicha variable se escapa a la naturaleza:
suma = f (& a) + g (a);
No se sabe qué f
podría haber hecho la función con el puntero proporcionado a
, incluido dejar una copia en el estado global a la que la función g
accede más tarde. En el caso más simple, f
escribe un nuevo valor en la variable a
, haciendo que esta expresión esté mal definida en el orden de ejecución. f
se puede evitar de manera notoria que haga esto aplicando un calificador const a la declaración de su argumento de puntero, lo que hace que la expresión esté bien definida. Por lo tanto, la cultura moderna de C / C ++ se ha vuelto algo obsesiva sobre el suministro de calificadores const a las declaraciones de argumentos funcionales en todos los casos viables.
C y C ++ permiten que las partes internas de f
al tipo moldeado el atributo constness de distancia como un expediente peligroso. Si f
hace esto de una manera que pueda romper la expresión anterior, no debería declarar el tipo de argumento de puntero como constante en primer lugar.
Otros lenguajes de alto nivel se inclinan hacia un atributo de declaración de este tipo que equivale a una garantía sólida sin lagunas para violar esta garantía proporcionada dentro del propio lenguaje; Todas las apuestas están cerradas en esta garantía de lenguaje si su aplicación vincula una biblioteca escrita en un lenguaje de programación diferente (aunque esto se considera un diseño atrozmente malo).
Implementación de barrera de memoria en tiempo de compilación
Estas barreras evitan que un compilador reordene las instrucciones durante el tiempo de compilación; no evitan que la CPU las reordene durante el tiempo de ejecución.
- La declaración del ensamblador en línea de GNU
asm volatile ("" ::: "memoria");
o incluso
__asm__ __volatile__ ("" ::: "memoria");
prohíbe al compilador GCC reordenar comandos de lectura y escritura a su alrededor. [1]
- La función C11 / C ++ 11
atomic_signal_fence (memory_order_acq_rel);
prohíbe al compilador reordenar comandos de lectura y escritura a su alrededor. [2]
- El compilador Intel ICC utiliza "valla de compilador completo"
__memory_barrier ()
- Compilador de Microsoft Visual C ++ : [5]
_ReadWriteBarrier ()
Barreras combinadas
En muchos lenguajes de programación, se pueden combinar diferentes tipos de barreras con otras operaciones (como carga, almacenamiento, incremento atómico, comparación atómica e intercambio), por lo que no se necesita una barrera de memoria adicional antes o después (o ambos). Dependiendo de la arquitectura de la CPU a la que se dirija, estas construcciones de lenguaje se traducirán en instrucciones especiales, en instrucciones múltiples (es decir, barrera y carga), o en instrucción normal, dependiendo de las garantías de pedido de la memoria del hardware.
Orden de memoria en tiempo de ejecución
En sistemas de microprocesador de multiprocesamiento simétrico (SMP)
Hay varios modelos de consistencia de memoria para sistemas SMP :
- Consistencia secuencial (todas las lecturas y escrituras están en orden)
- Consistencia relajada (se permiten algunos tipos de reordenamiento)
- Las cargas se pueden reordenar después de las cargas (para un mejor funcionamiento de la coherencia de la caché, mejor escalado)
- Las cargas se pueden reordenar después de las tiendas
- Las tiendas se pueden reordenar después de las tiendas
- Las tiendas se pueden reordenar después de las cargas
- Consistencia débil (las lecturas y escrituras se reordenan arbitrariamente, limitadas solo por barreras de memoria explícitas )
En algunas CPU
- Las operaciones atómicas se pueden reordenar con cargas y almacenes. [6]
- Puede haber una canalización de caché de instrucciones incoherente, lo que evita que el código de modificación automática se ejecute sin instrucciones especiales de descarga / recarga de caché de instrucciones.
- Las cargas dependientes se pueden reordenar (esto es exclusivo de Alpha). Si el procesador obtiene un puntero a algunos datos después de este reordenamiento, es posible que no obtenga los datos en sí, sino que use datos obsoletos que ya ha almacenado en caché y que aún no ha invalidado. Permitir esta relajación hace que el hardware de caché sea más simple y rápido, pero conduce al requisito de barreras de memoria para lectores y escritores. [7] En hardware Alpha (como los sistemas multiprocesador Alpha 21264 ), las invalidaciones de línea de caché enviadas a otros procesadores se procesan de forma diferida de forma predeterminada, a menos que se solicite explícitamente que se procesen entre cargas dependientes. La especificación de la arquitectura Alpha también permite otras formas de reordenación de cargas dependientes, por ejemplo, utilizando lecturas de datos especulativos antes de saber que el puntero real se desreferencia.
Tipo | Alfa | ARMv7 | MIPS | RISC-V | PA-RISC | ENERGÍA | SPARC | x86 [a] | AMD64 | IA-64 | z / Arquitectura | |||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
OMM | TSO | RMO | PSO | TSO | ||||||||||
Las cargas se pueden reordenar después de las cargas | Y | Y | dependen de la implementación | Y | Y | Y | Y | Y | ||||||
Las cargas se pueden reordenar después de las tiendas | Y | Y | Y | Y | Y | Y | Y | |||||||
Las tiendas se pueden reordenar después de las tiendas | Y | Y | Y | Y | Y | Y | Y | Y | ||||||
Las tiendas se pueden reordenar después de las cargas | Y | Y | Y | Y | Y | Y | Y | Y | Y | Y | Y | Y | Y | |
Atomic se puede reordenar con cargas | Y | Y | Y | Y | Y | Y | ||||||||
Atomic se puede reordenar con las tiendas | Y | Y | Y | Y | Y | Y | Y | |||||||
Las cargas dependientes se pueden reordenar | Y | |||||||||||||
Canalización de caché de instrucciones incoherentes | Y | Y | Y | Y | Y | Y | Y | Y | Y | Y |
- ^ Esta columna indica el comportamiento de la gran mayoría de procesadores x86. Algunos procesadores x86 especializados raros (IDT WinChip fabricado alrededor de 1998) pueden tener un orden de memoria de "almacenamiento" más débil. [10]
Modelos de pedido de memoria RISC-V:
- OMM
- Orden de memoria débil (predeterminado)
- TSO
- Pedido total de la tienda (solo compatible con la extensión Ztso)
Modos de pedido de memoria SPARC:
- TSO
- Pedido total de la tienda (predeterminado)
- RMO
- Orden de memoria relajada (no compatible con CPU recientes)
- PSO
- Pedido de tienda parcial (no compatible con CPU recientes)
Implementación de barrera de memoria de hardware
Muchas arquitecturas con soporte SMP tienen instrucciones de hardware especiales para descargar lecturas y escrituras durante el tiempo de ejecución .
- x86 , x86-64
lfence (asm), void _mm_lfence (vacío)sfence (asm), void _mm_sfence (vacío) [11] mfence (asm), void _mm_mfence (vacío) [12]
- PowerPC
sincronizar (asm)
- MIPS
sincronizar (asm)
- Itanium
mf (asm)
- ENERGÍA
dcs (asm)
- ARMv7 [13]
dmb (asm)dsb (asm)isb (asm)
Soporte del compilador para barreras de memoria de hardware
Algunos compiladores admiten incorporaciones que emiten instrucciones de barrera de memoria de hardware:
- GCC , [14] versión 4.4.0 y posteriores, [15] tiene
__sync_synchronize
. - Desde C11 y C ++ 11
atomic_thread_fence()
se agregó un comando. - El compilador de Microsoft Visual C ++ [16] tiene
MemoryBarrier()
. - Sun Studio Compiler Suite [17] tiene
__machine_r_barrier
,__machine_w_barrier
y__machine_rw_barrier
.
Ver también
- Modelo de memoria (programación)
Referencias
- ^ GCC compiler-gcc.h Archivado el 24 de julio de 2011 en la Wayback Machine.
- ^ "std :: atomic_signal_fence" . ccpreference .
- ^ ECC compiler-intel.h Archivado el 24 de julio de 2011 en la Wayback Machine.
- ^ Referencia de intrínsecos del compilador Intel (R) C ++
Crea una barrera a través de la cual el compilador no programará ninguna instrucción de acceso a datos. El compilador puede asignar datos locales en registros a través de una barrera de memoria, pero no datos globales.
- ^ Referencia del lenguaje Visual C ++ _ReadWriteBarrier
- ^ Victor Alessandrini, 2015. Programación de aplicaciones de memoria compartida: conceptos y estrategias en la programación de aplicaciones multinúcleo. Ciencia de Elsevier. pag. 176. ISBN 978-0-12-803820-8 .
- ^ Reordenar en un procesador Alpha por Kourosh Gharachorloo
- ^ Orden de memoria en microprocesadores modernos por Paul McKenney
- ^ Barreras de memoria: una vista de hardware para piratas informáticos , figura 5 en la página 16
- ^ Tabla 1. Resumen de ordenamiento de memoria , de "Orden de memoria en microprocesadores modernos, Parte I"
- ^ SFENCE - Valla de la tienda
- ^ MFENCE - Cerca de la memoria
- ^ Barrera de memoria de datos, barrera de sincronización de datos y barrera de sincronización de instrucciones.
- ^ Builtins atómicos
- ^ "36793 - x86-64 no obtiene __sync_synchronize correctamente" .
- ^ Macro MemoryBarrier
- ^ Manejo de pedidos de memoria en aplicaciones multiproceso con Oracle Solaris Studio 12 Update 2: Parte 2, Barreras de memoria y valla de memoria [1]
Otras lecturas
- Arquitectura informática: un enfoque cuantitativo . 4ª edición. J Hennessy, D Patterson, 2007. Capítulo 4.6
- Sarita V.Adve, Kourosh Gharachorloo, Modelos de consistencia de memoria compartida: un tutorial
- Informe técnico sobre pedidos de memoria de la arquitectura Intel 64
- Orden de memoria en microprocesadores modernos parte 1
- Orden de memoria en microprocesadores modernos, parte 2
- Solicitud de memoria IA (arquitectura Intel) en YouTube - Google Tech Talk