El multihilo sin bloqueo es para verdaderos expertos en enhebrado

86

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

vdhant
fuente
Utilizo plataformas gcc, linux y X86 / X68. ¡Sin bloqueo no es tan difícil como todos lo hacen parecer! Las incorporaciones atómicas de gcc tienen barreras de memoria en Intel, pero eso no importa en la vida real. Lo que importa es que la memoria se modifica atómicamente. Cuando diseña estructuras de datos "libres de bloqueos" se nota que no importa cuando otro hilo ve un cambio. Las listas de enlaces individuales, las listas de omisión, las tablas hash, las listas gratuitas, etc.son bastante fáciles de bloquear sin bloquear. Lock free no es para todo. Es solo otra herramienta adecuada para determinadas situaciones.
johnnycrash
2
1024cores.net
Mankarse
Votar para cerrar como recomendación de recurso, o no aclarar lo que está pidiendo.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Respuestas:

100

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).

Andras Vass
fuente
1
Si bien esta respuesta tiene mucha buena información, la idea principal de que los algoritmos sin bloqueo y las estructuras de datos son esencialmente solo una colección de bloqueos giratorios muy finos es incorrecta. Aunque normalmente verá bucles de reintento en estructuras sin bloqueos, el comportamiento es muy diferente: los bloqueos (incluidos los bloqueos giratorios) adquieren exclusivamente algunos recursos y otros subprocesos no pueden avanzar mientras se mantienen. El "reintento" en ese sentido es simplemente esperar a que se libere el recurso exclusivo.
BeeOnRope
1
Los algoritmos sin bloqueo, por otro lado, no usan CAS u otras instrucciones atómicas para adquirir un recurso exclusivo, sino para completar alguna operación. Si fallan, se debe a una carrera de grano fino temporal con otro hilo, y en ese caso el otro hilo progresó (completó su operación). Si un hilo es indefinidamente sospechoso, todos los demás hilos aún pueden progresar. Esto es tanto cualitativa como de rendimiento muy diferente de las cerraduras exclusivas. El número de "reintentos" suele ser muy bajo para la mayoría de los bucles CAS incluso en
situaciones de
1
... pero eso, por supuesto, no implica un buen escalado: la contención por una única ubicación de memoria siempre será bastante lenta en las máquinas SMP, solo debido a las latencias entre núcleos entre sockets, incluso si el número de fallas CAS es bajo.
BeeOnRope
1
@AndrasVass - Supongo que depende también del código sin bloqueo "bueno" frente al "malo". Ciertamente, cualquiera puede escribir una estructura y llamarla sin bloqueo, mientras que en realidad solo usa un bloqueo de giro en modo de usuario y ni siquiera cumple con la definición. También animaría a los lectores interesados ​​a consultar este artículo de Herlihy y Shavit que analiza de manera formal las diversas categorías de algoritmos basados ​​en bloqueos y sin bloqueos. También se recomienda leer cualquier cosa de Herlihy sobre este tema.
BeeOnRope
1
@AndrasVass - No estoy de acuerdo. La mayoría de las estructuras clásicas sin bloqueo (listas, colas, mapas concurrentes, etc.) no tenían ningún giro ni siquiera para estructuras mutables compartidas, y las implementaciones prácticas existentes de las mismas en, por ejemplo, Java siguen el mismo patrón (no soy tan familiarizado con lo que está disponible en C o C ++ compilado de forma nativa y es más difícil debido a que no hay recolección de basura). Quizás tú y yo tenemos una definición diferente de girar: no considero que el "reintento CAS" que encuentras en las cosas sin cerrojo sea "girar". En mi opinión, "girar" implica esperar en caliente.
BeeOnRope
27

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.

Eric Lippert
fuente
38
Entonces, si tanto Eric Lippert como Jon Skeet piensan que la programación sin bloqueo es solo para personas más inteligentes que ellos, entonces huiré humildemente gritando de la idea de inmediato. ;-)
dodgy_coder
20

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.

Hans Passant
fuente
2
@ Davy8: la composición lo hace todavía difícil. Si tengo dos tablas hash sin bloqueo y, como consumidor, accedo a ambas, esto no garantizará la coherencia del estado en su conjunto. Lo más cerca que puede llegar hoy son los STM, donde puede colocar los dos accesos, por ejemplo, en un solo atomicbloque. Con todo, consumir estructuras sin cerrojos puede ser igualmente complicado en muchos casos.
Andras Vass
4
Puede que me equivoque, pero creo que ha explicado mal cómo funciona la coherencia de la caché. La mayoría de los procesadores multinúcleo modernos tienen cachés coherentes, lo que significa que el hardware de caché se encarga de asegurarse de que todos los procesos tengan la misma vista del contenido de la RAM, bloqueando las llamadas de "lectura" hasta que se hayan completado todas las llamadas de "escritura" correspondientes. La documentación de Thread.MemoryBarrier () ( msdn.microsoft.com/en-us/library/… ) no dice nada sobre el comportamiento de la caché en absoluto; es simplemente una directiva que evita que el procesador reordene las lecturas y escrituras.
Brooks Moses
7
"No existe tal cosa como" roscado sin bloqueo "en estos días". Dígaselo a los programadores de Erlang y Haskell.
Julieta
4
@HansPassant: "No existe tal cosa como 'subprocesamiento sin bloqueo' en estos días". F #, Erlang, Haskell, Cilk, OCaml, Task Parallel Library (TPL) de Microsoft y Threaded Building Blocks (TBB) de Intel fomentan la programación multiproceso sin bloqueos. Rara vez uso bloqueos en el código de producción en estos días.
JD
5
@HansPassant: "una llamada barrera de memoria. Es una primitiva de CPU de bajo nivel que garantiza que todas las cachés de CPU estén en un estado coherente y tengan una vista actualizada de la RAM. Todas las escrituras pendientes deben vaciarse en la RAM, el los cachés deben actualizarse ". Una barrera de memoria en este contexto evita que el compilador o la CPU reordenen las instrucciones de memoria (cargas y almacenes). Nada que ver con la consistencia de los cachés de CPU.
JD
0

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.

fanfarrón
fuente
Existen numerosas bibliotecas que proporcionan semántica de subprocesos sin bloqueos. STM es de particular interés, del cual existen bastantes implementaciones.
Marcelo Cantos
Veo ambos lados de este. Obtener un rendimiento eficaz de una biblioteca sin bloqueos requiere un conocimiento profundo de los modelos de memoria. Pero un programador que no tenga ese conocimiento aún puede beneficiarse de las ventajas de la corrección.
Ben Voigt
0

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.

dodgy_coder
fuente