c++ - que - politicas de planificacion sistemas operativos
¿Es el reordenamiento de memoria visible para otros subprocesos en un uniprocesador? (8)
Es común que las arquitecturas modernas de CPU empleen optimizaciones de rendimiento que pueden resultar en una ejecución fuera de orden. En aplicaciones de un solo hilo, también se puede reordenar la memoria, pero es invisible para los programadores como si se accediera a la memoria en el orden del programa. Y para SMP, las barreras de memoria vienen al rescate que se utilizan para imponer algún tipo de orden de memoria.
Lo que no estoy seguro es sobre los subprocesos múltiples en un uniprocesador. Considere el siguiente ejemplo: cuando se ejecuta el subproceso 1, la tienda a f podría tener lugar antes de la tienda a x . Digamos que el cambio de contexto ocurre después de que se escribe f , y justo antes de que se escriba x . Ahora el hilo 2 comienza a ejecutarse, y finaliza el bucle e imprime 0, lo cual no es deseable, por supuesto.
// Both x, f are initialized w/ 0.
// Thread 1
x = 42;
f = 1;
// Thread 2
while (f == 0)
;
print x;
¿Es posible el escenario descrito anteriormente? ¿O existe una garantía de que la memoria física se comprometa durante el cambio de contexto de subproceso?
Según esta wiki ,
Cuando un programa se ejecuta en una máquina con una sola CPU , el hardware realiza la contabilidad necesaria para garantizar que el programa se ejecute como si todas las operaciones de memoria se realizaran en el orden especificado por el programador (orden del programa), por lo que las barreras de memoria no son necesarias.
Aunque no mencionó explícitamente las aplicaciones multiproceso de uniprocesador, incluye este caso.
No estoy seguro de que sea correcto / completo o no. Tenga en cuenta que esto puede depender en gran medida del hardware (modelo de memoria débil / fuerte). Así que es posible que desee incluir el hardware que sabe en las respuestas. Gracias.
PD. Dispositivo de E / S, etc. no son mi preocupación aquí. Y es un uniprocesador de un solo núcleo.
Edición : gracias a Nitsan por el recordatorio, asumimos que aquí no se está reordenando el compilador (solo se está reordenando el hardware), y el bucle en el subproceso 2 no se ha optimizado. Una vez más, el diablo está en los detalles.
Como una pregunta de C ++, la respuesta debe ser que el programa contiene una carrera de datos, por lo que el comportamiento no está definido. En realidad eso significa que podría imprimir algo más que 42.
Eso es independiente del hardware subyacente. Como se ha señalado, el bucle se puede optimizar y el compilador puede reordenar las asignaciones en el subproceso 1, por lo que el resultado puede ocurrir incluso en las máquinas con un solo procesador.
[Asumiré que con la máquina "uniprocesador", te refieres a los procesadores con un solo núcleo y un subproceso de hardware.]
Ahora dice, que quiere asumir que la reordenación del compilador o la eliminación del bucle no ocurre. Con esto, hemos abandonado el reino de C ++ y realmente estamos preguntando sobre las instrucciones correspondientes de la máquina. Si desea eliminar la reordenación del compilador, probablemente también podamos descartar cualquier forma de instrucciones SIMD y considerar solo las instrucciones que operan en una sola ubicación de memoria a la vez.
Básicamente, thread1 tiene dos instrucciones de almacenamiento en el orden store-to-x store-to-f, mientras que thread2 tiene test-f-and-loop-if-not-zero (esto puede ser varias instrucciones, pero implica una carga desde -f) y luego un load-from-x.
En cualquier arquitectura de hardware que conozca o pueda imaginar razonablemente, el subproceso 2 se imprimirá 42.
Una razón es que, si las instrucciones procesadas por un solo procesador no son secuencialmente coherentes entre sí, difícilmente se podría afirmar algo sobre los efectos de un programa.
El único evento que podría interferir aquí, es una interrupción (como se usa para desencadenar un cambio de contexto preventivo). Una máquina hipotética que almacena todo el estado de su estado actual de la tubería de ejecución en una interrupción y la restaura al regresar de la interrupción, podría producir un resultado diferente, pero tal máquina no es práctica y no existe un afaik. Estas operaciones crearían un poco de complejidad adicional y / o requerirían buffers o registros redundantes adicionales, todo esto sin ninguna razón, excepto para interrumpir su programa. Los procesadores reales pueden vaciar o hacer retroceder la tubería actual al interrumpirse, lo cual es suficiente para garantizar la coherencia secuencial de todas las instrucciones en un solo hilo de hardware.
Y no hay problema de modelo de memoria que preocuparse. Los modelos de memoria más débiles se originan en los búferes y cachés separados que separan los procesadores de hardware separados de la memoria principal o del caché de nivel n que realmente comparten. Un solo procesador no tiene recursos particionados de manera similar y no es una buena razón para tenerlos para múltiples hilos (puramente software). Nuevamente, no hay razón para complicar la arquitectura y desperdiciar recursos para que el procesador y / o el subsistema de memoria conozcan algo así como contextos de subprocesos separados, si no hay recursos de procesamiento separados (procesadores / subprocesos de hardware) para mantener estos recursos ocupados.
Desde mi punto de vista, el procesador obtiene las instrucciones una por una. En su caso, si "f = 1" se ejecutó de manera especulativa antes de "x = 42", eso significa que estas dos instrucciones ya están en la línea del procesador. La única forma posible de programar el subproceso actual es la interrupción. Pero el procesador (al menos en X86) desechará las instrucciones de la tubería antes de dar servicio a la interrupción. Así que no hay que preocuparse por la reordenación en un uniprocesador.
En lo que respecta al x86, los almacenes fuera de orden se hacen consistentes desde el punto de vista del código de ejecución con respecto al flujo del programa. En este caso, "flujo de programa" es solo el flujo de instrucciones que ejecuta un procesador, no algo restringido a un "programa que se ejecuta en un subproceso". Todas las instrucciones necesarias para el cambio de contexto, etc. se consideran parte de este flujo, por lo que la coherencia se mantiene en todos los subprocesos.
Es posible que este código nunca termine (en el subproceso 2), ya que el compilador puede decidir elevar la expresión completa fuera del bucle (esto es similar a usar un indicador isRunning que no es volátil). Dicho esto, debes preocuparte por dos tipos de reordenamientos aquí: el compilador y la CPU, ambos son libres de mover las tiendas. Consulte aquí: http://preshing.com/20120515/memory-reordering-caught-in-the-act para ver un ejemplo. En este punto, el código que describe anteriormente está a la merced del compilador, los indicadores del compilador y la arquitectura particular. El wiki citado es engañoso, ya que puede sugerir que el reordenamiento interno no está a merced de la CPU / compilador, lo cual no es el caso.
Esto no es realmente una pregunta de C o C ++, ya que se ha asumido explícitamente que no se debe volver a ordenar / almacenar, y que los compiladores de ambos idiomas están perfectamente autorizados.
Al permitir esa suposición por el bien del argumento, tenga en cuenta que, de todos modos, el bucle nunca puede salir, a menos que usted:
- dar al compilador alguna razón para creer que
fpuede cambiar (por ejemplo, al pasar su dirección a alguna función que no se puede alinear y que podría modificarla) - marcarlo volátil, o
- Conviértelo en un tipo explícitamente atómico y solicita semántica.
En lo que respecta al hardware, su preocupación por la "confirmación" de la memoria física durante un cambio de contexto no es un problema. Ambos subprocesos de software comparten el mismo hardware de memoria y caché, por lo que no existe riesgo de inconsistencia, independientemente del protocolo de coherencia / coherencia que exista entre los núcleos.
Digamos que se emitieron ambas tiendas y el hardware de memoria decide reordenarlas. ¿Qué significa esto realmente? Quizás la dirección de f ya está en el caché, por lo que puede escribirse inmediatamente, pero la tienda de x se aplaza hasta que se recupera la línea del caché. Bueno, una lectura de x depende de la misma dirección, así que:
- la carga no puede ocurrir hasta que se realice la recuperación, en cuyo caso una implementación sensata debe emitir el almacén en cola antes de la carga en cola
- o la carga puede asomarse a la cola y obtener el valor de x sin esperar la escritura
De todos modos, considere que la prioridad del kernel requerida para cambiar los hilos emitirá las barreras de carga / almacenamiento necesarias para mantener la coherencia del estado del programador del kernel, y debería ser obvio que el reordenamiento de hardware no puede ser un problema en esta situación.
El problema real (que está tratando de evitar) es su suposición de que no hay un reordenamiento del compilador: esto simplemente es incorrecto.
Un conmutador de contexto debe almacenar el estado completo de la máquina para que pueda restaurarse antes de que el hilo suspendido reanude la ejecución. Los estados de la máquina incluyen los registros del procesador, pero no la tubería del procesador.
Si asume que no se debe reordenar el compilador, esto significa que todas las instrucciones de hardware que están "sobre la marcha" deben completarse antes de que se produzca un cambio de contexto (es decir, una interrupción), de lo contrario, se pierden y no son almacenados por el interruptor de contexto mecanismo. Esto es independiente de la reordenación de hardware.
En su ejemplo, incluso si el procesador intercambia las dos instrucciones de hardware "x = 42" y "f = 1", el indicador de instrucción ya está después de la segunda, y por lo tanto ambas instrucciones deben completarse antes de que comience el cambio de contexto. de no ser así, ya que el contenido de la tubería y del caché no forman parte del "contexto", se perderían.
En otras palabras, si la interrupción que causa el cambio de ctx ocurre cuando el registro de IP apunta a la instrucción que sigue a "f = 1", todas las instrucciones anteriores a ese punto deben haber completado todos sus efectos.
Un orden de memoria sólido ejecuta las instrucciones de acceso a la memoria exactamente con el mismo orden definido en el programa, a menudo se lo denomina "orden de programa".
Se puede emplear una ordenación de memoria más débil para permitir el acceso de la memoria a la reordenación del procesador para un mejor rendimiento, a menudo se denomina "ordenación del procesador".
AFAIK, el escenario descrito anteriormente NO es posible en la arquitectura Intel ia32, cuyo pedido del procesador prohíbe estos casos. Las reglas relevantes son (manual de desarrollo de software intel ia-32 Vol3A 8.2 Orden de memoria):
las escrituras no se reordenan con otras escrituras, con la excepción de las tiendas de transmisión por secuencias, CLFLUSH y las operaciones de cadena.
Para ilustrar la regla, da un ejemplo similar a esto:
ubicación de memoria x, y, inicializada a 0;
hilo 1:
mov [x] 1
mov [y] 1
hilo 2:
mov r1 [y]
mov r2 [x]
r1 == 1 y r2 == 0 no está permitido
En su ejemplo, el hilo 1 no puede almacenar f antes de almacenar x.
@Eric en responder a tus comentarios.
La instrucción "stosd" del almacenamiento rápido de cadenas, puede almacenar cadenas fuera de orden dentro de su operación. En un entorno de multiprocesador, cuando un procesador almacena una cadena "str", otro procesador puede observar que str [1] se escribe antes que str [0], mientras que el orden lógico se supone que escribe str [0] antes de str [1];
Pero estas instrucciones no se reordenan con ninguna otra tienda. y debe tener un manejo preciso de excepciones. Cuando se produce una excepción en medio de stosd, la implementación puede optar por retrasarla, de modo que todas las sub-tiendas fuera de orden (no significa necesariamente toda la instrucción stosd) deben confirmarse antes del cambio de contexto.
Editado para abordar las reclamaciones realizadas como si se tratara de una pregunta de C ++:
Incluso esto se considera en el contexto de C ++, como entiendo, un compilador de confirmación estándar NO debe reordenar la asignación de x y f en el subproceso 1.
$ 1.9.14 Cada cálculo de valor y efecto secundario asociado con una expresión completa se secuencia antes de cada cálculo de valor y efecto secundario asociado con la siguiente expresión completa que se evaluará.
Sólo necesitarías una cerca de compilador. De los documentos del kernel de Linux en Barreras de memoria ( link ):
Las barreras de memoria SMP se reducen a las barreras del compilador en sistemas compilados con un solo procesador porque se supone que una CPU parecerá autoconsistente y ordenará los accesos superpuestos correctamente con respecto a sí misma.
Para ampliar eso, la razón por la que no se requiere la sincronización en el nivel de hardware es que:
Todos los subprocesos en un sistema uniprocesador comparten la misma memoria y, por lo tanto, no hay problemas de coherencia de caché (como la latencia de propagación) que pueden ocurrir en los sistemas SMP, y
Cualquier instrucción de carga / almacenamiento fuera de orden en la tubería de ejecución de la CPU se confirmaría o revertiría por completo si la tubería se vaciara debido a un cambio de contexto preventivo.