En mi aplicación multiproceso y 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?
¿Cómo puedo escribir una estructura sin bloqueo?
La respuesta corta es:
No se puede.
respuesta larga es:
Si está haciendo esta pregunta, usted no sabe probablemente lo suficiente como para ser capaz de crear una estructura libre de 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 utiliza, 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 de bloqueo libre correspondiente a la estructura que está utilizando en ese momento, mejor adapte el algoritmo para que pueda usar uno existente.
Si todavía insiste en la creación de su propia estructura libre de bloqueo, asegúrese de:
Más lectura:
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 artículo 13 de Effective Java explica esta técnica.
Bueno, depende del tipo de estructura, pero tienes que hacer la estructura para que detecte cuidadosamente y silenciosamente y maneje posibles conflictos.
Dudo que pueda hacer una que esté 100% libre de bloqueos, pero de nuevo, depende de qué tipo de estructura necesite construir.
Es posible que también necesite fragmentar la estructura para que varios hilos funcionen en elementos individuales y luego sincronizar/recombinar.
Escribir código libre de bloqueo de hilo es difícil; pero this article from Herb Sutter lo ayudará a comenzar.
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.
La inmutabilidad es un enfoque para evitar el bloqueo. Consulte Eric Lippert's discussion y la implementación de cosas como pilas y colas inmutables.
Utilice una biblioteca como Intel's Threading Building Blocks, contiene bastantes estructuras y algoritmos sin bloqueo. Realmente no recomendaría intentar escribir código de bloqueo usted mismo, es extremadamente propenso a errores y difícil de corregir.
Reduce o elimina el estado mutable compartido.
El principio básico para la sincronización sin bloqueo es la siguiente:
cuando lea la estructura, se sigue la lectura con una prueba para ver si la estructura se mutó desde que empezó la lectura, y vuelva a intentarlo hasta que logre leer sin que surja algo más y mute mientras lo hace;
siempre que esté mutando la estructura, organiza su algoritmo y datos de modo que haya un solo paso atómico que, si se toma, hace que todo el cambio se vuelva visible para los otros hilos, y arregle las cosas para que ninguno de el cambio es visible a menos que se tome ese paso. 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.
Existen numerosos ejemplos de estructuras sin traba en la web; sin saber más sobre lo que está implementando y sobre qué plataforma es difícil ser más específico.
La mayoría de los algoritmos o estructuras sin bloqueo comienzan con alguna operación atómica, es decirun cambio en alguna ubicación de memoria que una vez que se inició con un subproceso se completará antes de que cualquier otro subproceso pueda realizar la misma operación. ¿Tienes una operación de este tipo en tu entorno?
Ver here para el documento canónico sobre este tema.
También pruebe este artículo wikipedia article para obtener más ideas y enlaces.
Esta "operación atómica" suena sospechosamente como un bloqueo. ¿Cual es la diferencia? – cHao
acantilado Click tiene cúpula de una investigación importante sobre las estructuras de datos libres de bloqueo mediante la utilización de máquinas de estados finitos y también ha escrito mucho de implementaciones para Java. Puede encontrar sus papeles, diapositivas e implementaciones en su blog: http://blogs.azulsystems.com/cliff/
Un nuevo enlace del blog de cliff: http://www.cliffc.org/blog/ –
Como sblundy señaló, si todos los objetos son inmutables, de sólo lectura, no es necesario que preocuparse de bloqueo, sin embargo, esto significa puede tener que copiar objetos mucho. Por lo general, copiar utiliza malloc y malloc para bloquear las asignaciones de memoria entre subprocesos, por lo que los objetos inmutables pueden comprarle menos de lo que cree (malloc se escala bastante mal y malloc es lento; si realiza una gran cantidad de malloc en una sección de rendimiento crítico , no esperes buen rendimiento).
Cuando solo necesita actualizar variables simples (por ejemplo, 32 o 64 bit int o punteros), realizar simplemente operaciones de suma o resta en ellas o simplemente intercambiar los valores de dos variables, la mayoría de las plataformas ofrecen "operaciones atómicas" para eso (además, GCC ofrece estos también). Atomic no es lo mismo que thread-safe.Sin embargo, atomic se asegura de que si un subproceso escribe un valor de 64 bits en una ubicación de memoria, por ejemplo, y otro hilo lo lee, el de lectura obtiene el valor antes de la operación de escritura o después de la operación de escritura, pero nunca un roto. valor entre la operación de escritura (por ejemplo, una donde los primeros 32 bits ya son los nuevos, los últimos 32 bits siguen siendo el valor anterior! Esto puede suceder si no 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 ya actualizado y dos no actualizados. 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 utilizando 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 con el hilo es no compartir ningún dato entre los 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 manera rápida de mover datos entre hilos si realmente tiene que hacerlo (ITC, Inter Thread Communication). 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. P.ej. si dos hilos 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.
"Aquí necesitarás un candado si debes asegurarte" ... No, mutes una nueva copia de la estructura en lugar de hacer en su lugar, y cambiar cuál está activo como su operación atómica. – moonshadow
Pero eso significa que tendrá que malloc de nuevo, suponiendo que no se trata de datos apilados (lo que probablemente no será así) y como he dicho, malloc puede ser un enorme cuello de botella. En uno de nuestros software, reutilizar el mismo bloque de memoria cada vez en comparación con el uso de malloc cada vez causaba una ganancia de velocidad del 80%. – Mecki
Podría haber cambiado a utilizar un malloc optimizado para hilos, uno que usa un campo por hilo. –
En Java, utilice los paquetes java.util.concurrent en JDK 5+ en lugar de escribir el suyo. 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.
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 investigar las técnicas Software Transaction Memory.
Usar una implementación existente, ya que esta área de trabajo es el reino de los expertos de dominio y doctores (si quieres que se haga bien!)
Por ejemplo, hay una biblioteca de código aquí:
¿Puedes aclarar a qué te refieres con estructura?
En este momento, supongo que se refiere a la arquitectura general. Puede lograrlo no compartiendo memoria entre procesos y utilizando un modelo de actor para sus procesos.
Tome un vistazo a mi link ConcurrentLinkedHashMap para 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 aplicación hace uso de un ConcurrentHashMap, que es un algoritmo de bloqueo-por-cubo, pero no se basa en que los detalles 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 de multiprocesador" es un gran imprimació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.
En "concurrentlinkedhashmap" hay un comentario interesante escrito ahora: Nota: Greg Luck (Ehcache) descubrió una rara condición de carrera. Este algoritmo está en desuso. Supongo que esto muestra qué esperar al desarrollar datos sin bloqueo por su cuenta. – Suma
Ese comentario ha estado allí durante siglos. El comentario de que el proyecto fue para fines educativos personales para la comprensión de algoritmos concurrentes ha estado allí desde el principio. Intenta utilizar la libertad de bloqueo para su crecimiento personal e intenta evitarlo para la producción. Eso es más o menos lo que dije en mi publicación original. –
in re. La respuesta de Suma, Maurice Herlithy muestra en The Art of Multiprocessor Programming que en realidad cualquier cosa 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 multi-hilo es sorprendentemente duro (comprobar el ABA problem). 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 el CAS puede ayudar al desarrollo, aunque debe usar buena prueba y herramientas tal vez más potentes (tal vez SKETCH, Kendo próxima MIT, o spin?) Para comprobar la corrección si se puede reducir a una estructura simple.
Por favor, publique más sobre su problema. Es difícil dar una buena respuesta sin detalles.
editar immutibility es bueno pero su aplicabilidad es limitada, si lo estoy entendiendo 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 ve la contención de bloqueo, me gustaría en primer lugar tratar de utilizar las cerraduras más granulares en sus estructuras de datos en lugar de algoritmos completamente libre de bloqueo.
Por ejemplo, actualmente trabajo en una aplicación 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.
Como mi profesor (Nir Shavit de "El arte de la programación multiprocesador") dijo 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: use las bibliotecas existentes. Joe Duffy's blog encuestas 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 se lee varias implementaciones y documentos en relación con el tema, se dará cuenta de que hay el siguiente tema común:
1) objetos de estado son compartidas Lisp/estilo clojure inmutable: 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 a partir 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. Inmutabilidad se puede optimizar el uso de Copy-on-Write semántica para objetos grandes y complejos, pero eso es otro árbol de frutos secos
2) que especifique claramente lo que les permite transiciones entre el estado actual y el siguiente son válidos: Luego de validar que el algoritmo es válido convertirse en órdenes de magnitud más fáciles
3) Manejar las referencias descartadas en las listas de punteros de peligro por el hilo. Después de que los objetos de referencia son seguros, reutilizar si es posible
Ver otro post relacionado de mina donde algún código implementado con semáforos y mutex es (parcialmente) reimplementada en un estilo libre de bloqueo: Mutual exclusion and semaphores
Creo que significa una estructura libre de bloqueo de hilo. –
¿Qué idioma estás usando? –