sistemas multihilos ejemplo c# .net multithreading lock-free

c# - multihilos - El multihilo sin bloqueo es para expertos en enhebrado real



ejemplo de multihilos (6)

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

Como ejemplo, solo di que necesitas hacer un thread de colección seguro. No se limite ciegamente a bloquear un método iterando sobre la colección si realiza alguna tarea intensiva de CPU en cada elemento. Es posible que solo necesite bloquear la creación de una copia superficial de la colección. Iterando sobre la copia podría funcionar sin un bloqueo. Por supuesto, esto depende en gran medida de los detalles de su código, pero he podido solucionar un problema de convoy de bloqueo con este enfoque.

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

En lo que a mí respecta, el multi-threading sin bloqueo es para expertos en hilos reales, de los cuales no soy uno.

No es la primera vez que escucho esto, pero encuentro muy poca gente hablando de cómo lo hace en realidad si está interesado en aprender a escribir código multihilo sin bloqueos.

Por lo tanto, mi pregunta es, además de aprender todo lo que pueda sobre el uso de subprocesos, etc., ¿dónde comienza a tratar de aprender a escribir específicamente código multihilo sin bloqueo y cuáles son algunos buenos recursos?

Aclamaciones

Cuando se trata de multi-threading tienes que saber exactamente lo que estás haciendo. Me refiero a explorar todos los posibles escenarios / casos que pueden ocurrir cuando trabajas en un entorno de subprocesos múltiples. El multihilo sin bloqueo no es una biblioteca o clase que incorporamos, es un conocimiento / experiencia que ganamos durante nuestro viaje por hilos.

El libro de Joe Duffy:

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

Él también escribe un blog sobre estos temas.

El truco para lograr que los programas de bloqueo bajo sean adecuados es comprender a 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 tiempo de ejecución.

Personalmente, no estoy lo suficientemente inteligente como para hacer una correcta programación de bloqueo bajo más allá de InterlockedIncrement, pero si lo estás, genial, ve por ello. 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.

En estos días, no existe el "enhebrado sin bloqueo". Fue un patio de recreo interesante para la academia y demás, 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 a pastar. Ya no funciona.

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

El problema de velocidad de RAM requirió que los diseñadores de chips pusieran un buffer en el chip de la CPU. El búfer almacena código y datos, a los que puede acceder rápidamente el núcleo de la CPU. Y puede leerse y escribirse desde / a la RAM a un ritmo mucho más lento. Este búfer se denomina memoria caché de la CPU, la mayoría de las CPU tienen al menos dos de ellos. El primer nivel de caché es pequeño y rápido, el segundo es grande y más lento. Siempre que la CPU pueda leer datos e instrucciones de la memoria 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á en la segunda caché y necesita ser leída desde RAM.

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

Eso es dramáticamente incompatible con el enhebrado. Siempre te importa cuál es el estado de otro hilo cuando debes leer datos escritos por otro hilo. Para garantizar esto, debe programar explícitamente una barrera de memoria. Es una primitiva de CPU de bajo nivel que garantiza que todas las memorias caché de la CPU estén en un estado constante y tengan una vista actualizada de la RAM. Todas las escrituras pendientes deben enjuagarse en la memoria RAM, las cachés deben actualizarse.

Esto está disponible en .NET, el método Thread.MemoryBarrier () implementa uno. Dado que esto es el 90% del trabajo que hace la instrucción de bloqueo (y el 95% o más del tiempo de ejecución), simplemente no se adelanta al evitar las herramientas que .NET le brinda e intentando implementar la suya propia.

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

  • * leer un estado y hacer una copia de él **
  • * modificar copia **
  • hacer una operación entrelazada
  • vuelva a intentar si falla

(* opcional: depende de la estructura / algoritmo de 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 interconectadas utilizadas en el multihilo sin bloqueo está dominado por las tareas de caché y coherencia de memoria que debe llevar a cabo .

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

El truco la mayoría de las veces es que no tiene bloqueos dedicados, sino que trata, por ejemplo, a todos los elementos de una matriz o todos los nodos de una lista vinculada como un "bloqueo por giro". Usted lee, modifica y trata de actualizar si no hubo actualizaciones desde su última lectura. Si hubo, lo vuelves a intentar.
Esto hace que su "bloqueo" (oh, lo siento, sin bloqueo :) sea de grano muy fino, sin introducir requisitos adicionales de memoria o recursos.
Hacerlo de grano más fino disminuye la probabilidad de esperas. Hacerlo lo más preciso posible sin introducir requisitos de recursos adicionales suena genial, ¿no?

Sin embargo, la mayor parte de la diversión puede provenir de garantizar el orden correcto de carga / almacén .
Contrariamente a las intuiciones propias, las CPU pueden reordenar las lecturas / escrituras de memoria, son muy inteligentes, por cierto: le resultará difícil observar esto desde un único hilo. Sin embargo, se encontrará con problemas cuando empiece a hacer múltiples hilos en múltiples núcleos. Sus intuiciones se romperán: el hecho de que una instrucción sea anterior en su código no significa que realmente suceda antes. Las CPU pueden procesar las instrucciones fuera de servicio: y especialmente les gusta 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 bien, es seguro contra la intuición de que una secuencia de código no fluye "de arriba hacia abajo", sino que se ejecuta como si no existiera ninguna secuencia en absoluto, y puede llamarse "campo de juegos del diablo". Creo que no es factible dar una respuesta exacta en cuanto a las reordenaciones de carga / tienda que tendrán lugar. En cambio, uno siempre habla en términos de mayúsculas, mimos y latas y se prepara para lo peor. "Oh, la CPU podría reordenar esta lectura para que aparezca antes de esa escritura, por lo que es mejor poner una barrera de memoria aquí mismo, en este punto".

Las cuestiones se complican por el hecho de que incluso estos mayas y mights pueden diferir en las arquitecturas de la CPU. Podría ser el caso, por ejemplo, de que algo que está garantizado que no ocurra en una arquitectura puede ocurrir en otra.

Para obtener un multihilo correcto "sin bloqueo", debe comprender los modelos de memoria.
Sin embargo, no es trivial obtener el modelo de memoria y las garantías correctas, como lo demuestra esta historia, por el cual Intel y AMD hicieron algunas correcciones a la documentación de MFENCE causando un gran revuelo entre los desarrolladores de JVM . Resultó que la documentación de la que dependían los desarrolladores 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 de usarlos (la mayoría de las veces, es decir ... vea por ejemplo este Joe Duffy - Brad Abrams - Vance Morrison grandeza en la inicialización lenta, bloqueos, volátiles y memoria barreras. :) (Asegúrese de seguir los enlaces en esa página).

Como una ventaja adicional, serás introducido al modelo de memoria .NET en una misión secundaria . :)

También hay un "viejo pero dorado" de Vance Morrison: Lo que cada 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 fino y probablemente proporcione un rendimiento que esté cerca o esté 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 exclusivo de .NET, Doug Lea hizo un gran trabajo en JSR-166 .
Cliff Click tiene una interesante visión de las tablas hash que no depende de las bloqueos (como lo hacen las tablas hash simultáneas de Java y .NET) y parece que se adapta bien a 750 CPU.

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

@Ben hizo muchos comentarios sobre MPI: Acepto sinceramente 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.

Sin embargo, MPI tiene sus propios costos y sus propios problemas cuando se ejecuta en un solo 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 núcleo, los sistemas MPI generalmente implementan un tipo de programación cooperativa N: M para "procesos livianos". Esto, por ejemplo, significa que hay un inevitable cambio de contexto entre procesos ligeros. Es cierto que no se trata de un "cambio de contexto clásico" sino principalmente de una operación de espacio de usuario y puede acelerarse; sin embargo, dudo sinceramente que pueda llevarse a cabo dentro de los 20-200 ciclos que toma una operación interconectada . El cambio de contexto del modo de usuario es ciertamente más lento incluso en la biblioteca Intel McRT. La programación N: M con procesos ligeros no es nueva. Los LWP estuvieron allí en Solaris durante mucho tiempo. Ellos fueron abandonados. Había fibras en NT. En su mayoría son una reliquia ahora. Hubo "activaciones" en NetBSD. Ellos fueron abandonados. Linux tenía su propia visión sobre el tema de enhebrado N: M. Parece estar algo muerto ahora.
De vez en cuando, hay nuevos contendientes: 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 planificador N: M MPI. Erlang, o cualquier sistema MPI, podría beneficiarse enormemente en los sistemas SMP explotando el nuevo UMS .

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