El multihilo sin bloqueo es para verdaderos expertos en enhebrado

Estaba leyendo una respuesta que Jon Skeet dio a una pregunta y en ella mencionó esto:

En lo que a mí respecta, el subproceso múltiple sin bloqueo es para verdaderos expertos en subprocesos, de los cuales yo no soy uno.

No es la primera vez que escucho esto, pero encuentro muy pocas personas hablando sobre cómo lo hace realmente si está interesado en aprender a escribir código de subprocesos múltiples sin bloqueos.

Entonces, mi pregunta es además de aprender todo lo que pueda sobre subprocesos, etc., ¿dónde empezar a intentar aprender a escribir específicamente código de subprocesos múltiples sin bloqueos y cuáles son algunos buenos recursos?

Salud

Las implementaciones actuales "sin bloqueo" siguen el mismo patrón la mayor parte del tiempo:

• * leer algún estado y hacer una copia **
• * modificar copia **
• hacer una operación enclavada
• reintentar si falla

_{(* opcional: depende de la estructura / algoritmo de los datos)}

El último bit es inquietantemente similar a un spinlock. De hecho, es un spinlock básico . :)
Estoy de acuerdo con @nobugz en esto: el costo de las operaciones entrelazadas utilizadas en el multihilo sin bloqueo está dominado por la caché y las tareas de coherencia de memoria que debe realizar .

Sin embargo, lo que gana con una estructura de datos que está "libre de bloqueos" es que sus "bloqueos" son muy finos . Esto reduce la posibilidad de que dos subprocesos simultáneos accedan al mismo "bloqueo" (ubicación de memoria).

El truco la mayoría de las veces es que no tiene bloqueos dedicados; en su lugar, trata, por ejemplo, todos los elementos de una matriz o todos los nodos de una lista vinculada como un "bloqueo de giro". Usted lee, modifica e intenta actualizar si no hubo ninguna actualización desde su última lectura. Si lo hubo, vuelva a intentarlo.
Esto hace que su "bloqueo" (oh, lo siento, no bloqueo :) es muy fino, sin introducir requisitos adicionales de memoria o recursos.
Hacerlo más detallado disminuye la probabilidad de esperas. Hacerlo lo más detallado posible sin introducir requisitos de recursos adicionales suena genial, ¿no es así?

Sin embargo, la mayor parte de la diversión puede provenir de garantizar la correcta carga / pedido en la tienda .
Contrariamente a las intuiciones, las CPU son libres de reordenar las lecturas / escrituras de la memoria; por cierto, son muy inteligentes: le resultará difícil observar esto desde un solo hilo. Sin embargo, se encontrará con problemas cuando comience a realizar subprocesos múltiples en varios núcleos. Sus intuiciones se romperán: el hecho de que una instrucción sea anterior en su código no significa que realmente sucederá antes. Las CPU pueden procesar instrucciones fuera de orden: y les gusta especialmente hacer esto con instrucciones con acceso a la memoria, para ocultar la latencia de la memoria principal y hacer un mejor uso de su caché.

Ahora, contra la intuición, es seguro que una secuencia de código no fluye "de arriba hacia abajo", sino que se ejecuta como si no hubiera ninguna secuencia en absoluto, y puede llamarse "campo de juego del diablo". Creo que no es factible dar una respuesta exacta sobre qué pedidos de carga / tienda se realizarán. En cambio, uno siempre habla en términos de mays y mights y latas y se prepara para lo peor. "Oh, la CPU podría reordenar esta lectura para que venga antes de la escritura, por lo que es mejor colocar una barrera de memoria aquí, en este lugar".

La situación se complica por el hecho de que incluso estos mays y mights pueden diferir a través de arquitecturas de CPU. Que podría ser el caso, por ejemplo, que algo que está garantizado que no ocurrirá en una arquitectura que podría ocurrir en otro.

Para obtener un subproceso múltiple "sin bloqueo", debe comprender los modelos de memoria.
Sin embargo, lograr que elMFENCE modelo de memoria y las garantías sean correctos no es trivial, como lo demuestra esta historia, en la que Intel y AMD hicieron algunas correcciones a la documentación que causaron cierto revuelo entre los desarrolladores de JVM . Al final resultó que, la documentación en la que los desarrolladores confiaron desde el principio no era tan precisa en primer lugar.

Los bloqueos en .NET dan como resultado una barrera de memoria implícita, por lo que está seguro al usarlos (la mayoría de las veces, es decir ... vea, por ejemplo, esta grandeza de Joe Duffy - Brad Abrams - Vance Morrison en inicialización lenta, bloqueos, volátiles y memoria barreras. :) (Asegúrese de seguir los enlaces en esa página).

Como ventaja adicional, se le presentará el modelo de memoria .NET en una misión secundaria . :)

También hay un "viejo pero dorado" de Vance Morrison: Lo que todo desarrollador debe saber sobre las aplicaciones multiproceso .

... y por supuesto, como mencionó @Eric , Joe Duffy es una lectura definitiva sobre el tema.

Un buen STM puede acercarse lo más posible al bloqueo de grano fino y probablemente proporcionará un rendimiento cercano o a la par con una implementación hecha a mano. Uno de ellos es STM.NET de los proyectos DevLabs de MS.

Si no eres un fanático de .NET, Doug Lea hizo un gran trabajo en JSR-166 .
Cliff Click tiene una versión interesante de las tablas hash que no se basa en la creación de bandas de bloqueo, como lo hacen las tablas hash concurrentes de Java y .NET, y parece escalar bien a 750 CPU.

Si no tiene miedo de aventurarse en el territorio de Linux, el siguiente artículo proporciona más información sobre los aspectos internos de las arquitecturas de memoria actuales y cómo el intercambio de líneas de caché puede destruir el rendimiento: Lo que todo programador debe saber sobre la memoria .

@Ben hizo muchos comentarios sobre MPI: Estoy de acuerdo sinceramente en que MPI puede brillar en algunas áreas. Una solución basada en MPI puede ser más fácil de razonar, más fácil de implementar y menos propensa a errores que una implementación de bloqueo a medias que intenta ser inteligente. (Sin embargo, subjetivamente, también es cierto para una solución basada en STM.) También apostaría a que es años luz más fácil escribir correctamente una aplicación distribuida decente en, por ejemplo, Erlang, como sugieren muchos ejemplos exitosos.

MPI, sin embargo, tiene sus propios costos y sus propios problemas cuando se ejecuta en un único sistema de múltiples núcleos . Por ejemplo, en Erlang, hay problemas que resolver en torno a la sincronización de la programación de procesos y las colas de mensajes .
Además, en su esencia, los sistemas MPI generalmente implementan una especie de programación N: M cooperativa para "procesos ligeros". Esto, por ejemplo, significa que hay un cambio de contexto inevitable entre procesos ligeros. Es cierto que no es un "cambio de contexto clásico", sino principalmente una operación de espacio de usuario y se puede hacer rápido; sin embargo, dudo sinceramente que pueda llevarse a los 20-200 ciclos que requiere una operación entrelazada . El cambio de contexto en modo de usuario es ciertamente más lentoincluso en la biblioteca Intel McRT. La programación N: M con procesos ligeros no es nueva. Los LWP estuvieron presentes en Solaris durante mucho tiempo. Fueron abandonados. Había fibras en NT. En su mayoría son ahora una reliquia. Hubo "activaciones" en NetBSD. Fueron abandonados. Linux tenía su propia opinión sobre el tema de los subprocesos N: M. Parece estar algo muerto a estas alturas.
De vez en cuando, hay nuevos competidores: por ejemplo, McRT de Intel , o más recientemente User-Mode Scheduling junto con ConCRT de Microsoft.
En el nivel más bajo, hacen lo que hace un programador MPI N: M. Erlang, o cualquier sistema MPI, podría beneficiarse enormemente de los sistemas SMP al explotar el nuevo UMS .

Supongo que la pregunta del OP no es sobre los méritos y los argumentos subjetivos a favor / en contra de cualquier solución, pero si tuviera que responder eso, supongo que depende de la tarea: para construir estructuras de datos básicas de bajo nivel y alto rendimiento que se ejecutan en un Un solo sistema con muchos núcleos , ya sea técnicas de bloqueo bajo / "sin bloqueo" o un STM producirá los mejores resultados en términos de rendimiento y probablemente superaría a una solución MPI en cualquier momento en cuanto al rendimiento, incluso si se eliminan las arrugas anteriores. por ejemplo, en Erlang.
Para construir algo moderadamente más complejo que se ejecute en un solo sistema, quizás elegiría el bloqueo de grano grueso clásico o, si el rendimiento es una gran preocupación, un STM.
Para construir un sistema distribuido, un sistema MPI probablemente sería una elección natural.
Tenga en cuenta que también hay implementaciones de MPI para .NET (aunque parecen no estar tan activas).

El libro de Joe Duffy:

http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html

También escribe un blog sobre estos temas.

El truco para lograr que los programas de bloqueo bajo sean correctos es comprender a un nivel profundo con precisión cuáles son las reglas del modelo de memoria en su combinación particular de hardware, sistema operativo y entorno de ejecución.

Personalmente, no soy lo suficientemente inteligente como para hacer una programación correcta de bloqueo bajo más allá de InterlockedIncrement, pero si lo eres, genial, hazlo. Solo asegúrese de dejar mucha documentación en el código para que las personas que no son tan inteligentes como usted no rompan accidentalmente uno de los invariantes de su modelo de memoria e introduzcan un error imposible de encontrar.

No existe tal cosa como "roscado sin bloqueo" en estos días. Era un campo de juego interesante para la academia y similares, a fines del siglo pasado, cuando el hardware de las computadoras era lento y costoso. El algoritmo de Dekker siempre fue mi favorito, el hardware moderno lo ha puesto en práctica. Ya no funciona.

Dos desarrollos han terminado con esto: la creciente disparidad entre la velocidad de la RAM y la CPU. Y la capacidad de los fabricantes de chips para colocar más de un núcleo de CPU en un chip.

El problema de la velocidad de la RAM requería que los diseñadores de chips pusieran un búfer en el chip de la CPU. El búfer almacena código y datos, rápidamente accesibles por el núcleo de la CPU. Y se puede leer y escribir desde / hacia la RAM a una velocidad mucho más lenta. Este búfer se llama caché de la CPU, la mayoría de las CPU tienen al menos dos de ellos. El caché de primer nivel es pequeño y rápido, el segundo es grande y más lento. Siempre que la CPU pueda leer datos e instrucciones del caché de primer nivel, se ejecutará rápidamente. Una falta de caché es realmente costosa, pone a la CPU a dormir hasta 10 ciclos si los datos no están en la primera caché, hasta 200 ciclos si no están en la segunda caché y es necesario leerlos. RAM.

Cada núcleo de CPU tiene su propia caché, almacenan su propia "vista" de RAM. Cuando la CPU escribe datos, la escritura se realiza en la caché, que luego, lentamente, se vacía en la RAM. Inevitable, cada núcleo ahora tendrá una vista diferente del contenido de la RAM. En otras palabras, una CPU no sabe lo que ha escrito otra CPU hasta que se completa el ciclo de escritura de la RAM y la CPU actualiza su propia vista.

Eso es dramáticamente incompatible con el enhebrado. Siempre le importa realmente cuál es el estado de otro hilo cuando debe leer datos que fueron escritos por otro hilo. Para garantizar esto, debe programar explícitamente una llamada barrera de memoria. Es una primitiva de CPU de bajo nivel que asegura que todos los cachés de CPU estén en un estado consistente y tengan una vista actualizada de la RAM. Todas las escrituras pendientes deben vaciarse en la RAM, luego las cachés deben actualizarse.

Esto está disponible en .NET, el método Thread.MemoryBarrier () implementa uno. Dado que este es el 90% del trabajo que hace la instrucción de bloqueo (y más del 95% del tiempo de ejecución), simplemente no está por delante al evitar las herramientas que le brinda .NET e intentar implementar las suyas propias.

Google para bloquear estructuras de datos libres y memoria transaccional de software .

Estaré de acuerdo con John Skeet en este; el enhebrado sin bloqueo es el campo de juego del diablo, y es mejor dejarlo en manos de personas que saben lo que necesitan saber.

Cuando se trata de subprocesos múltiples, debe saber exactamente lo que está haciendo. Me refiero a explorar todos los escenarios / casos posibles que pueden ocurrir cuando trabaja en un entorno de subprocesos múltiples. El subproceso múltiple sin bloqueo no es una biblioteca o una clase que incorporamos, es un conocimiento / experiencia que obtenemos durante nuestro viaje en subprocesos.

Aunque el subproceso sin bloqueo puede ser difícil en .NET, a menudo puede hacer mejoras significativas al usar un bloqueo al estudiar exactamente lo que debe bloquearse y minimizar la sección bloqueada ... esto también se conoce como minimizar la granularidad del bloqueo .

Como ejemplo, diga que necesita hacer que un hilo de colección sea seguro. No se limite a bloquear ciegamente un método que itera sobre la colección si realiza alguna tarea intensiva de CPU en cada elemento. Es posible que solo necesite poner un candado para crear una copia superficial de la colección. La iteración sobre la copia podría funcionar sin un candado. Por supuesto, esto depende en gran medida de los detalles de su código, pero he podido solucionar un problema de bloqueo del convoy con este enfoque.