tiempo threads threading python3 programacion mismo metodos manejo hilos entre eliminar ejecutar datos con compartir argumentos multithreading multicore lock-free

multithreading - threads - ¿Cómo puedo escribir una estructura sin bloqueo?



python3 multithreading (21)

¿Puedes aclarar a qué te refieres con estructura?

En este momento, supongo que te refieres a la arquitectura general. Puede lograrlo no compartiendo memoria entre procesos y utilizando un modelo de actor para sus procesos.

En mi aplicación multiproceso, veo una gran contención de bloqueo en ella, lo que impide una buena escalabilidad en varios núcleos. He decidido usar la programación sin bloqueo para resolver esto.

¿Cómo puedo escribir una estructura sin bloqueo?

Bueno, depende del tipo de estructura, pero tienes que hacer la estructura para que detecte cuidadosa y silenciosamente y maneje posibles conflictos.

Dudo que pueda hacer uno que esté 100% libre de bloqueos, pero nuevamente, depende del tipo de estructura que necesite construir.

Es posible que también necesite fragmentar la estructura para que varios hilos funcionen en elementos individuales y luego sincronizar / recombinar.

Cliff Click ha realizado algunas investigaciones importantes sobre estructuras de datos libres de bloque mediante la utilización de máquinas de estados finitos y también ha publicado muchas implementaciones para Java. Puede encontrar sus documentos, diapositivas e implementaciones en su blog: http://blogs.azulsystems.com/cliff/

Como se mencionó, realmente depende del tipo de estructura de la que está hablando. Por ejemplo, puede escribir una cola limitada sin bloqueos, pero no una que permita el acceso aleatorio.

Como señaló Sblundy , si todos los objetos son inmutables, de solo lectura, no necesita preocuparse por el bloqueo, sin embargo, esto significa que puede tener que copiar mucho los objetos. Por lo general, copiar utiliza Malloc y malloc para bloquear la sincronización de las asignaciones de memoria entre subprocesos, por lo que los objetos inmutables pueden comprarle menos de lo que cree (malloc escasea bastante y malloc es lento ; si realiza una gran cantidad de malloc en una sección de rendimiento crítico, no no esperes buen desempeño).

Cuando solo necesita actualizar variables simples (por ejemplo, int o punteros de 32 o 64 bit), realice simplemente operaciones de suma o resta en ellas o simplemente cambie los valores de dos variables, la mayoría de las plataformas ofrecen "operaciones atómicas" para eso (más GCC ofrece estos también). Atomic no es lo mismo que hilo seguro . Sin embargo, atomic se asegura de que si un hilo escribe un valor de 64 bits en una ubicación de memoria, por ejemplo, y otro hilo lo lee, la lectura obtiene el valor antes de la operación de escritura o después de la operación de escritura, pero nunca un valor roto . entre la operación de escritura (por ejemplo, una en la que los primeros 32 bits ya son nuevos, los últimos 32 bits aún son el valor anterior). Esto puede suceder si no se utiliza el acceso atómico en dicha variable).

Sin embargo, si tiene una estructura C con 3 valores, que desea actualizar, incluso si actualiza los tres con operaciones atómicas, estas son tres operaciones independientes, por lo tanto, un lector puede ver la estructura con un valor que ya se está actualizando y dos no actualizado. Aquí, si necesita asegurarse, necesitará un candado; el lector verá que todos los valores de la estructura son antiguos o nuevos.

Una forma de hacer que los bloqueos se escalen mucho mejor es usando bloqueos R / W. En muchos casos, las actualizaciones de datos son bastante infrecuentes (operaciones de escritura), pero el acceso a los datos es muy frecuente (leer los datos), pensar en colecciones (hashtables, árboles). En ese caso, los bloqueos R / W le comprarán una gran ganancia de rendimiento, ya que muchos hilos pueden contener un bloqueo de lectura al mismo tiempo (no se bloquearán entre sí) y solo si un hilo desea un bloqueo de escritura, todos los otros hilos están bloqueados por el tiempo que se realiza la actualización.

La mejor manera de evitar problemas de hilos es no compartir ningún dato entre hilos. Si cada hilo trata la mayor parte del tiempo con datos a los que no tiene acceso ningún otro hilo, no necesitará en absoluto el bloqueo de esos datos (tampoco operaciones atómicas). Intente compartir la menor cantidad de datos posible entre los hilos. Entonces solo necesita una forma rápida de mover datos entre hilos si realmente tiene que hacerlo (ITC, comunicación entre hilos). Dependiendo de su sistema operativo, plataforma y lenguaje de programación (desafortunadamente no nos contó ninguno de estos), podrían existir varios métodos poderosos para ITC.

Y, por último, otro truco para trabajar con datos compartidos pero sin ningún bloqueo es asegurarse de que los subprocesos no accedan a las mismas partes de los datos compartidos. Por ejemplo, si dos subprocesos comparten una matriz, pero uno solo tendrá acceso incluso, el otro solo índices impares, no necesitará bloqueo. O si ambos comparten el mismo bloque de memoria y uno solo usa la mitad superior, el otro solo el inferior, no necesita bloqueo. Aunque no se dice, esto conducirá a un buen rendimiento; especialmente no en CPU multinúcleo. Escribir operaciones de un subproceso en estos datos compartidos (ejecutar un núcleo) puede forzar el caché para que se vacíe otro subproceso (ejecutándose en otro núcleo) y estos flujos de caché son a menudo el cuello de botella para aplicaciones de múltiples subprocesos que se ejecutan en CPU multinúcleo modernas.

El principio básico para la sincronización sin bloqueo es este:

  • cada vez que lees la estructura, sigues la lectura con una prueba para ver si la estructura estaba mutada desde que comenzaste a leer, y vuelves a intentar hasta que logras leer sin que surja otra cosa y mutes mientras lo haces;

  • cada vez que mutes la estructura, organizas tu algoritmo y datos de modo que haya un único paso atómico que, si se toma, hace que todo el cambio sea visible para los otros hilos, y arregle las cosas para que ninguno de los cambios sea visible a menos que ese paso es tomado. Se utiliza el mecanismo atómico sin bloqueo que exista en su plataforma para ese paso (por ejemplo, comparar y establecer, con conexión de carga + condicional de tienda, etc.). En ese paso, debe verificar si algún otro hilo ha mutado el objeto desde que comenzó la operación de mutación, confirmar si no lo ha hecho y comenzar de nuevo si lo ha hecho.

Hay muchos ejemplos de estructuras sin bloqueo en la web; sin saber más sobre lo que está implementando y sobre qué plataforma es difícil ser más específico.

En Java, utilice los paquetes java.util.concurrent en JDK 5+ en lugar de escribir los suyos propios. Como se mencionó anteriormente, este es realmente un campo para expertos, y a menos que tenga un año o dos de repuesto, hacer rodar el suyo no es una opción.

La inmutabilidad es un enfoque para evitar el bloqueo. Vea la discusión e implementación de cosas como pilas y colas inmutables de Eric Lippert .

La inmutabilidad tendría este efecto. Los cambios en el objeto dan como resultado un nuevo objeto. Lisp funciona de esta manera bajo las sábanas.

El ítem 13 de Java efectivo explica esta técnica.

La mayoría de los algoritmos o estructuras sin bloqueo comienzan con alguna operación atómica, es decir, un cambio en la ubicación de la memoria que una vez iniciada por un hilo se completará antes de que cualquier otro hilo pueda realizar esa misma operación. ¿Tienes una operación de este tipo en tu entorno?

Vea aquí el documento canónico sobre este tema.

Pruebe también este artículo de artículo de wikipedia para obtener más ideas y enlaces.

La respuesta corta es:

No puedes.

La respuesta larga es:

Si hace esta pregunta, probablemente no sepa lo suficiente como para poder crear una estructura sin bloqueo. Crear estructuras libres de bloqueo es extremadamente difícil, y solo los expertos en este campo pueden hacerlo. En lugar de escribir el suyo, busque una implementación existente. Cuando lo encuentre, verifique cuán ampliamente se usa, qué tan bien está documentado, si está bien probado, cuáles son las limitaciones, incluso algunas estructuras sin cerradura que otras personas publicaron están rotas.

Si no encuentra una estructura libre de bloqueo correspondiente a la estructura que está utilizando en ese momento, mejor adapte el algoritmo para que pueda usar uno existente.

Si aún insistes en crear tu propia estructura sin cerradura, asegúrate de:

  • comenzar con algo muy simple
  • comprender el modelo de memoria de su plataforma de destino (incluidas las restricciones de reordenamiento de lectura / escritura, qué operaciones son atómicas)
  • estudiar mucho sobre los problemas que otras personas encontraron al implementar estructuras sin cerradura
  • no adivine si funcionará, pruébelo
  • poner a prueba el resultado

Más lectura:

Bloquee algoritmos gratuitos y de espera en Wikipedia

Herb Sutter: Código sin bloqueo: un falso sentido de seguridad

Reduzca o elimine el estado mutable compartido.

Si está escribiendo sus propias estructuras de datos sin bloqueo para una CPU de núcleo múltiple, ¡no se olvide de las barreras de memoria! Además, considere estudiar las técnicas de memoria de transacciones de software .

Utilice una biblioteca como el Threading Building Blocks de Intel , que contiene bastantes algoritmos y estructuras libres de bloqueo. Realmente no recomendaría intentar escribir código de bloqueo usted mismo, es extremadamente propenso a errores y difícil de corregir.

Eche un vistazo a mi enlace ConcurrentLinkedHashMap para ver un ejemplo de cómo escribir una estructura de datos sin bloqueo. No se basa en ningún documento académico y no requiere años de investigación como otros implican. Simplemente requiere una ingeniería cuidadosa.

Mi implementación utiliza un ConcurrentHashMap, que es un algoritmo de bloqueo por segmento, pero no depende de ese detalle de implementación. Podría ser reemplazado fácilmente con la implementación sin bloqueo de Cliff Click. Tomé prestada una idea de Cliff, pero usé mucho más explícitamente, es modelar todas las operaciones de CAS con una máquina de estado. Esto simplifica enormemente el modelo, ya que verás que tengo bloqueos de psuedo a través de los estados. Otro truco es permitir la pereza y resolver según sea necesario. Verá esto a menudo con retroceder o dejar que otros hilos "ayuden" a la limpieza. En mi caso, decidí permitir que los nodos muertos en la lista fueran desalojados cuando llegaran a la cima, en lugar de lidiar con la complejidad de eliminarlos del medio de la lista. Puedo cambiar eso, pero no confiaba del todo en mi algoritmo de retroceso y quería posponer un cambio importante como adoptar un enfoque de bloqueo de 3 nodos.

El libro "El arte de la programación multiprocesador" es una excelente introducción. En general, sin embargo, recomendaría evitar diseños sin bloqueo en el código de la aplicación. Muchas veces es simplemente excesivo donde otras técnicas menos propensas a errores son más adecuadas.

Como dijo mi profesor (Nir Shavit de "The Art of Multiprocessor Programming") a la clase: Por favor, no lo haga. La razón principal es la capacidad de prueba: no se puede probar el código de sincronización. Puede ejecutar simulaciones, incluso puede realizar pruebas de estrés. Pero es una aproximación aproximada en el mejor de los casos. Lo que realmente necesitas es una prueba matemática de corrección. Y muy pocos capaces de entenderlos, y mucho menos de escribirlos. Entonces, como otros habían dicho: usa las bibliotecas existentes. El blog de Joe Duffy estudia algunas técnicas (sección 28). El primero que debes probar es dividir árboles: divide en tareas más pequeñas y combínalos.

Si ve una contención de bloqueo, primero trataré de usar más bloqueos granulares en sus estructuras de datos en lugar de algoritmos completamente libres de bloqueos.

Por ejemplo, actualmente trabajo en aplicaciones multiproceso, que tiene un sistema de mensajería personalizado (lista de colas para cada subproceso, la cola contiene mensajes para que el subproceso procese) para pasar información entre subprocesos. Hay un bloqueo global en esta estructura. En mi caso, no necesito tanta velocidad, así que realmente no importa. Pero si este bloqueo se convirtiera en un problema, podría ser reemplazado por bloqueos individuales en cada cola, por ejemplo. Luego agregar / quitar elemento a / de la cola específica no afectaría otras colas. Todavía habría un bloqueo global para agregar nueva cola y tal, pero no sería tan disputado.

Incluso una sola cola de producción múltiple / consumidor puede escribirse con bloqueo granular en cada elemento, en lugar de tener un bloqueo global. Esto también puede eliminar la contención.

en re. La respuesta de Suma, Maurice Herlithy, muestra en The Art of Multiprocessor Programming que en realidad todo se puede escribir sin bloqueos (ver capítulo 6). iirc, Esto esencialmente implica dividir tareas en elementos de nodo de procesamiento (como el cierre de una función) y encaminar cada uno. Threads calculará el estado siguiendo todos los nodos del último en caché. Obviamente, esto podría, en el peor de los casos, dar como resultado un rendimiento secuencial, pero tiene importantes propiedades sin cerradura, lo que evita escenarios en los que los hilos podrían programarse durante periodos largos de tiempo cuando tienen bloqueos. Herlithy también logra un rendimiento teórico sin esperar, lo que significa que un hilo no terminará esperando para siempre la conquista atómica (este es un código muy complicado).

Una cola / pila de subprocesos múltiples es sorprendentemente difícil (consulte el problema de ABA ). Otras cosas pueden ser muy simples. Acostúmbrate a while (true) {atomicCAS hasta que lo cambie} bloques; ellos son increíblemente poderosos. Una intuición de lo que es correcto con CAS puede ayudar al desarrollo, aunque debería usar buenas pruebas y quizás herramientas más potentes (tal vez SKETCH , próximo MIT Kendo o spin ?) Para verificar la corrección si puede reducirla a una estructura simple.

Por favor publique más sobre su problema. Es difícil dar una buena respuesta sin detalles.

editar la inmutabilidad es bueno, pero su aplicabilidad es limitada, si lo entiendo bien. En realidad, no supera los riesgos de escribir después de leer; considere dos subprocesos ejecutando "mem = NewNode (mem)"; ambos podrían leer mem, luego ambos escribirlo; no es el correcto para una función de incremento clásica. Además, es probable que sea lenta debido a la asignación de montón (que debe sincronizarse entre subprocesos).

Si lee varias implementaciones y documentos sobre el tema, notará que existe el siguiente tema común:

1) Los objetos de estado compartidos son inmutables al estilo lisp / clojure : es decir, todas las operaciones de escritura se implementan copiando el estado existente en un nuevo objeto, realizando modificaciones al nuevo objeto y luego tratando de actualizar el estado compartido (obtenido de un puntero alineado que se puede actualizar con la primitiva CAS). En otras palabras, NUNCA JAMÁS modificará un objeto existente que pueda leer más que el hilo actual. La inmutabilidad se puede optimizar usando la semántica de Copiar-Escribir para objetos grandes y complejos, pero ese es otro árbol de nueces

2) especifica claramente qué son válidas las transiciones permitidas entre el estado actual y el siguiente : luego validar que el algoritmo es válido se convierte en órdenes de magnitud más fáciles

3) Maneje referencias descartadas en listas de punteros de peligro por hilo . Después de que los objetos de referencia sean seguros, reutilícelos si es posible

Ver otra publicación relacionada mía donde algún código implementado con semáforos y mutexes es (parcialmente) reimplementado en un estilo libre de bloqueo: exclusión mutua y semáforos