Ordenación de la memoria

El orden de memoria es el orden en que la CPU accede a la memoria de la computadora . Este orden depende tanto del orden de las instrucciones generadas por el compilador en tiempo de compilación como del orden de ejecución de la CPU en tiempo de ejecución . ^[¹^]^[²^] Sin embargo, el orden de memoria es de poca importancia fuera del contexto de la programación multihilo y la E/S mapeada en memoria , ya que si el compilador o la CPU modifican el orden de alguna operación , deben asegurarse necesariamente de que la reordenación no altere la salida del código ordinario de un solo hilo . ^[¹^]^[²^]^[³^]

Se dice que el orden de memoria es fuerte o secuencialmente consistente cuando el orden de las operaciones no puede cambiar o cuando dichos cambios no tienen ningún efecto visible en ningún hilo. ^{[ 1 ]}^{[ 4 ]} Por el contrario, el orden de memoria se denomina débil o relajado cuando un hilo no puede predecir el orden de las operaciones que surgen de otro hilo. ^{[ 1 ]}^{[ 4 ]} Muchos algoritmos paralelos escritos ingenuamente fallan cuando se compilan o ejecutan con un orden de memoria débil. ^{[ 5 ]}^{[ 6 ]} El problema se resuelve con mayor frecuencia insertando instrucciones de barrera de memoria en el programa. ^{[ 6 ]}^{[ 7 ]}

Para aprovechar al máximo el ancho de banda de los distintos tipos de memoria, como las cachés y los bancos de memoria , pocos compiladores o arquitecturas de CPU garantizan un ordenamiento perfectamente estricto. ^{[ 1 ]}^{[ 5 ]} Entre las arquitecturas de uso común, los procesadores x86-64 tienen el ordenamiento de memoria más estricto, pero aun así pueden retrasar las instrucciones de almacenamiento en memoria hasta después de las instrucciones de carga en memoria. ^{[ 5 ]}^{[ 8 ]} En el otro extremo del espectro, los procesadores DEC Alpha prácticamente no ofrecen garantías sobre el ordenamiento de la memoria. ^{[ 5 ]}

Ordenación de memoria en tiempo de compilación

La mayoría de los lenguajes de programación tienen algún concepto de hilo de ejecución que ejecuta instrucciones en un orden definido. Los compiladores tradicionales traducen expresiones de alto nivel a una secuencia de instrucciones de bajo nivel en relación con un contador de programa a nivel de máquina.

Los efectos de la ejecución son visibles en dos niveles: dentro del código del programa, a un nivel superior, y a nivel de máquina, tal como lo ven otros hilos o elementos de procesamiento en la programación concurrente , o durante la depuración al usar una herramienta de depuración de hardware con acceso al estado de la máquina (a menudo, esta funcionalidad está integrada directamente en la CPU o el microcontrolador como un circuito funcionalmente independiente del núcleo de ejecución, que continúa operando incluso cuando el núcleo se detiene para la inspección estática de su estado de ejecución). El orden de memoria en tiempo de compilación se ocupa del primer caso y no de los otros.

Cuestiones generales del orden del programa

Efectos del orden del programa en la evaluación de la expresión

Durante la compilación, las instrucciones de hardware suelen generarse con un nivel de detalle mayor que el especificado en el código de alto nivel. El principal efecto observable en un lenguaje de programación procedimental es la asignación de un nuevo valor a una variable con nombre.

 suma = a + b + c; imprimir(suma);

La instrucción print sigue a la instrucción que asigna un valor a la variable sum, por lo que cuando la instrucción print hace referencia a la variable calculada, sumhace referencia a este resultado como un efecto observable de la secuencia de ejecución anterior. Según lo definen las reglas de secuencia de programas, cuando la printllamada a la función hace referencia a sum, el valor de sumdebe 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 de programación restringe al compilador a traducir la expresión de izquierda a derecha (por ejemplo), entonces el código generado se verá como si el programador hubiera escrito las siguientes instrucciones en el programa original:

 suma = a + b; suma = suma + c;

Si se permite al compilador 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;

Cabe señalar que el tipo de datos enteros en la mayoría de los lenguajes de programación solo sigue el álgebra de los 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 asociativa debido al redondeo intermedio, lo que hace que los efectos del orden de expresión sean visibles en pequeñas diferencias del resultado calculado (sin embargo, pequeñas diferencias iniciales pueden convertirse en diferencias arbitrariamente grandes a lo largo de un cálculo más prolongado).

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 del orden del programa que involucran llamadas a funciones

Muchos lenguajes tratan el límite de una instrucción como un punto de secuencia , lo que obliga a que todos los efectos de una instrucción se completen antes de que se ejecute la siguiente. Esto obliga al compilador a generar código que corresponda al orden de las instrucciones. Sin embargo, las instrucciones suelen ser más complejas 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 la mayoría de los lenguajes compilados, el compilador es libre de ordenar las llamadas a funciones fcomo gle hresulte conveniente, lo que resulta en cambios a gran escala en el orden de la memoria del programa. En un lenguaje de programación funcional puro , las llamadas a funciones tienen prohibido tener 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 será irrelevante para la semántica del programa. En los lenguajes procedimentales, las funciones llamadas pueden tener efectos secundarios, como realizar una operación de E/S o actualizar una variable en el ámbito global del programa, ambos produciendo efectos visibles en el modelo del programa.

Nuevamente, 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 de la instrucción se define como un punto de secuencia, las llamadas a la función f, g, y hahora deben ejecutarse en ese orden preciso.

Problemas específicos del orden de la memoria

Efectos del orden del programa que involucran expresiones de puntero

Ahora consideremos la misma suma expresada con indirección de punteros, en un lenguaje como C o C++ que admita punteros :

 suma = *a + *b + *c;

Evaluar la expresión *xse denomina " desreferenciar " un puntero e implica leer de la memoria en una ubicación especificada por el valor actual de x. Los efectos de leer de un puntero están determinados por el modelo de memoria de la arquitectura . Al leer desde el almacenamiento de programa estándar, no hay efectos secundarios debido al orden de las operaciones de lectura de memoria. En la programación de sistemas embebidos , es muy común tener E/S mapeada en memoria, donde las lecturas y escrituras en memoria desencadenan operaciones de E/S o cambios en el modo operativo del procesador, que son efectos secundarios muy visibles. Para el ejemplo anterior, supongamos por ahora que los punteros apuntan a la memoria de programa normal, sin estos efectos secundarios. El compilador puede reordenar estas lecturas en el orden del programa como mejor le parezca, y no habrá efectos secundarios visibles para el programa.

¿Qué ocurre si el valor asignado también es un puntero inferido?

 *suma = *a + *b + *c;

En este caso, es poco probable que la definición del lenguaje permita al compilador descomponerlo de la siguiente manera:

 // 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 punteros pueden tener efectos secundarios en el estado visible de la máquina. Dado que el compilador no tiene permitida esta transformación de división en particular, la única escritura en la ubicación de memoria sumdebe seguir lógicamente las tres lecturas de punteros en la expresión de valor.

Supongamos, sin embargo, que al programador le preocupa la semántica visible del desbordamiento de enteros y divide la instrucción a nivel de programa de la siguiente manera:

 // tal como lo escribió directamente el programador // con problemas de alias *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 en *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 introduce potencialmente 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 *cy *sumtienen alias para la misma ubicación de memoria, y reescribamos ambas versiones del programa con *sumen lugar de para ambas.

 *suma = *a + *b + *suma;

Aquí no hay problemas. El valor original de lo que escribimos originalmente como *cse pierde al asignarlo a *sum, y también el valor original de , *sumpero esto fue sobrescrito en primer lugar y no es motivo de especial preocupación.

 // en qué se convierte el programa con los alias *c y *sum *suma = *a + *b; *suma = *suma + *suma;

Aquí el valor original de *sumse 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);

lo que asigna un valor completamente diferente *sumdebido a la reorganización de la instrucción.

Debido a los posibles efectos de aliasing, las expresiones de puntero son difíciles de reorganizar sin riesgo de que el programa se vea afectado. En la mayoría de los casos, es posible que no haya aliasing, por lo que el código parece ejecutarse con normalidad. Sin embargo, en el caso excepcional de que exista aliasing, pueden producirse errores graves en el programa. Incluso si estos casos excepcionales están completamente ausentes en la ejecución normal, se abre la puerta a que un atacante malintencionado cree una entrada donde exista aliasing, lo que podría dar lugar a una vulnerabilidad de seguridad informática .

Una reordenación segura del programa anterior es la siguiente:

 // Declarar una variable local temporal 'temp' del tipo adecuado. temp = *a + *b; *suma = temp + *c;

Finalmente, consideremos el caso indirecto con llamadas a funciones adicionales:

 *suma = f(*a) + g(*b);

El compilador puede optar por evaluar *ay *bantes de cualquiera de las llamadas a funciones, puede aplazar la evaluación de *bhasta después de la llamada a la función fo puede aplazar la evaluación de *ahasta después de la llamada a la función g. Si las funciones fy gno tienen efectos secundarios visibles en el programa, las tres opciones producirán un programa con los mismos efectos visibles. Si la implementación de fo gcontiene el efecto secundario de alguna escritura de puntero sujeta a alias con punteros ao b, las tres opciones pueden producir diferentes efectos visibles en el programa.

Orden de memoria en la especificación del lenguaje

En general, las especificaciones de los lenguajes compilados no son lo suficientemente detalladas como para que el compilador determine formalmente, en tiempo de compilación, qué punteros pueden tener alias y cuáles no. Lo más seguro es que el compilador asuma que todos los punteros pueden tener alias en todo momento. Este nivel de pesimismo conservador suele resultar en un rendimiento pésimo en comparación con la suposición optimista de que no existe ningún alias.

Como resultado, muchos lenguajes compilados de alto nivel, como C/C++, han evolucionado hasta tener especificaciones semánticas complejas y sofisticadas sobre dónde se le permite al compilador hacer suposiciones optimistas en la reordenación del código en busca del mayor rendimiento posible, y dónde se le exige al compilador que haga suposiciones pesimistas en la reordenación del código para evitar riesgos semánticos.

En un lenguaje de programación procedimental moderno, la clase más frecuente de efectos secundarios son las operaciones de escritura en memoria, por lo que las reglas de ordenación de la memoria constituyen un componente fundamental en la definición de la semántica del orden del programa. La reordenación de las llamadas a funciones mencionadas anteriormente podría parecer una consideración distinta, pero esto suele derivar en problemas relacionados con 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 a la función.

Dificultades y complicaciones adicionales

Optimización bajo el supuesto

Los compiladores modernos a veces van un paso más allá mediante una regla de "como si" , en la que se permite cualquier reordenamiento (incluso entre sentencias) si no afecta a la semántica visible del programa. Según esta regla, el orden de las operaciones en el código traducido puede variar enormemente del orden especificado en el programa. Si se permite al compilador hacer suposiciones optimistas sobre la ausencia de solapamiento de alias entre distintas expresiones de puntero, en un caso en el que dicho solapamiento existe (lo que normalmente se clasificaría como un programa mal formado con comportamiento indefinido ), es imposible predecir los resultados adversos de una transformación agresiva de optimización del código antes de la ejecución o la inspección directa del mismo. El ámbito del comportamiento indefinido tiene manifestaciones prácticamente ilimitadas.

Es responsabilidad del programador consultar la especificación del lenguaje para evitar escribir programas mal formados cuya semántica pueda verse alterada por optimizaciones válidas del compilador. Fortran tradicionalmente impone una gran responsabilidad al programador en cuanto a la atención a estos aspectos, 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 con punteros, ya que este nivel de atención y precisión se considera demasiado elevado para mantenerlo de forma fiable incluso entre programadores profesionales.

Un conocimiento profundo de la semántica del orden de memoria se considera una especialización esotérica incluso entre el subgrupo de programadores de sistemas profesionales que suelen estar mejor informados en este tema. La mayoría de los programadores se conforman con un conocimiento práctico adecuado de estas cuestiones dentro del ámbito habitual de su experiencia en programación. En el extremo más avanzado de la especialización en semántica del orden de memoria se encuentran los programadores que desarrollan marcos de software para modelos de computación concurrente .

Alias de variables locales

Tenga en cuenta que no se puede asumir que las variables locales estén libres de alias si un puntero a dicha variable se escapa al exterior:

 suma = f(&a) + g(a);

No se sabe qué fpodría haber hecho la función con el puntero proporcionado a, incluyendo dejar una copia en el estado global a la que la función gaccede posteriormente. En el caso más simple, fescribe un nuevo valor en la variable a, lo que hace que esta expresión esté mal definida en el orden de ejecución. fSe puede evitar claramente que esto suceda 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 con respecto a proporcionar calificadores `const` a las declaraciones de argumentos de función en todos los casos posibles.

C y C++ permiten que las funciones internas eliminen el atributo de constancia mediante una conversión fde tipo, lo cual es una práctica peligrosa. Si festo ocurre de forma que pueda invalidar la expresión anterior, no debería declarar el tipo del argumento del puntero como constante en primer lugar.

Otros lenguajes de alto nivel tienden a utilizar un atributo de declaración de este tipo como una garantía sólida sin resquicios que permitan violarla; sin embargo, esta garantía del lenguaje queda invalidada si la aplicación enlaza una biblioteca escrita en un lenguaje de programación diferente (aunque esto se considera un diseño pésimo).

Implementación de barrera de memoria en tiempo de compilación

Estas barreras impiden que un compilador reordene las instrucciones durante el tiempo de compilación, pero no impiden que la CPU las reordene durante el tiempo de ejecución.

Cualquiera de estas instrucciones de ensamblador en línea de GNU prohíbe al compilador GCC reordenar los comandos de lectura y escritura a su alrededor: ^{[ 9 ]}

asm volatile("" ::: "memoria"); __asm__ __volatile__ ("" ::: "memoria");

Esta función de C11/C++11 prohíbe al compilador reordenar los comandos de lectura y escritura a su alrededor: ^{[ 10 ]}

atomic_signal_fence(memory_order_acq_rel);

El compilador Intel C++ (ICC/ICL) utiliza intrínsecas de "valla de compilador completa": ^{[ 11 ]}^{[ 12 ]}

__barrera_de_memoria()

El compilador Microsoft Visual C++ (MSVC) admite algunas funciones intrínsecas solo para x86/x64 (todas ellas están obsoletas): ^{[ 13 ]}

_ReadBarrier() _WriteBarrier() _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 ambas). Dependiendo de la arquitectura de la CPU, estas construcciones del lenguaje se traducirán en instrucciones especiales, en instrucciones múltiples (por ejemplo, barrera y carga) o en instrucciones normales, según las garantías de ordenación de memoria del hardware.