¿Cómo puedo escribir un bloqueo libre de la estructura?

Question

En mi aplicación multiproceso y veo pesado contención de bloqueo en ella, impidiendo una buena escalabilidad a través de múltiples núcleos.He decidido usar bloqueo de programación gratuito para resolver esto.

¿Cómo puedo escribir un bloqueo libre de la estructura?

Answer 1

Respuesta corta es:

Usted no puede.

Respuesta larga es:

Si estás haciendo esta pregunta, usted probablemente no sabe lo suficiente para ser capaz de crear un bloqueo libre de la estructura.La creación de bloqueo libre de estructuras es extremadamente difícil, y sólo los expertos en este campo, puede hacerlo.En lugar de escribir su propio, la búsqueda de una implementación existente.Cuando lo encuentre, comprobar cuán ampliamente se utiliza, cómo bien se documenta, si es bien demostrado, ¿cuáles son las limitaciones, e incluso de algunas de bloqueo libre de la estructura de otras personas publican están rotos.

Si usted no encuentra un bloqueo libre de la estructura correspondiente a la estructura que se está usando actualmente, en lugar de adaptar el algoritmo de modo que usted puede utilizar algunos existente.

Si aún así insisten en la creación de su propio bloqueo libre de la estructura, asegúrese de:

• empezar con algo muy sencillo
• entender el modelo de memoria de su plataforma de destino (incluyendo la lectura/escritura de la reordenación de las limitaciones, de las operaciones que se atómica)
• estudiar mucho acerca de los problemas de otras personas encontradas al momento de implementar bloqueo libre de estructuras
• no sólo adivinar si funciona, probarlo
• fuertemente probar el resultado

Leer más:

Lock libre y esperar libre de algoritmos en la Wikipedia

Herb Sutter:Libre De Bloqueo De Código:Una Falsa Sensación de Seguridad

Answer 2

El uso de una biblioteca, tales como Intel Threading Building Blocks, contiene muy pocos bloqueo libre de algoritmos y estructuras.Yo realmente no se recomienda intentar bloqueo de escritura de código libre de ti mismo, es muy propenso a errores y difícil de conseguir.

Answer 3

Escrito hilo de seguridad de bloqueo de código libre es duro;pero este artículo de Herb Sutter le ayudará a empezar.

Answer 4

Como sblundy señaló que, si todos los objetos son inmutables, sólo lectura, usted no necesita preocuparse acerca de los bloqueos, sin embargo, esto significa que usted puede tener para copiar objetos de mucho.Copia generalmente implica malloc y malloc usos de bloqueo para sincronizar las asignaciones de memoria a través de los subprocesos, por lo que los objetos inmutables puede comprar menos de lo que piensas (malloc sí escalas bastante mal y malloc es lento;si usted hace un montón de malloc en un rendimiento de la sección crítica, no es de esperar un buen rendimiento).

Cuando sólo se necesita la actualización de variables simples (por ejemplo,32 o 64 bits int o punteros), realizar simplemente la suma o la resta de las operaciones en ellos o simplemente intercambiar los valores de dos variables, la mayoría de los que ofrecen las plataformas de "operaciones atómicas" para que (más GCC ofrece estas así). Atómica no es el mismo thread-safe.Sin embargo, atómica asegura que si un subproceso escribe una de 64 bits de valor en una ubicación de memoria, por ejemplo, y otro hilo lee, la lectura de uno obtiene el valor antes de la operación de escritura o después de la operación de escritura, pero nunca un roto valor en el medio de la operación de escritura (por ejemplo,uno donde los primeros 32 bits ya están los nuevos, los últimos 32 bits sigue siendo el viejo valor!Esto puede suceder si usted no utiliza el acceso atómico en este tipo de variable).

Sin embargo, si usted tiene una estructura C con 3 valores, que desea actualizar, incluso si la actualización de todos los tres con operaciones atómicas, estas son las tres operaciones independientes, así, un lector puede ver que la estructura con un valor ya está la actualización y dos no se actualizan.Aquí usted necesitará un candado si usted debe asegurar, el lector ve todos los valores en la estructura, ya sea el antiguo o en los nuevos valores.

Una manera de hacer bloqueos escala mucho mejor es el uso de R/W bloqueos.En muchos casos, las actualizaciones son bastante poco frecuentes (operaciones de escritura), pero el acceso a los datos es muy frecuente (la lectura de los datos), creo que de colecciones (tablas hash, árboles).En ese caso R/W bloqueos va a comprar una enorme ganancia de rendimiento, como muchos hilos que pueden mantener una lectura de bloqueo al mismo tiempo (no bloquear cada uno de los otros) y sólo si un hilo quiere un bloqueo de escritura, todos los demás subprocesos están bloqueados para el momento en que se realizó la actualización.

La mejor manera de evitar el hilo de los problemas es no compartir los datos a través de los subprocesos.Si cada hilo de ofertas la mayoría del tiempo con datos de ningún otro hilo tiene acceso, no es necesario el bloqueo de los datos en todo (también hay operaciones atómicas).Así que trate de compartir como poco como sea posible entre los hilos.A continuación, usted sólo necesita una manera rápida de mover datos entre hilos si usted realmente tiene que (ITC, Entre el Hilo de la Comunicación).Dependiendo de su sistema operativo, plataforma y lenguaje de programación (por desgracia, se nos dijo que ninguno de estos), los diversos métodos de gran alcance para el ITC podría existir.

Y por último, otro truco para trabajar con datos compartidos, pero sin ningún tipo de bloqueo es para asegurarse de que los hilos no tienen acceso a las mismas partes de los datos compartidos.E. g.si dos hilos comparten una matriz, pero uno solo el acceso, incluso, el otro sólo impar índices, usted no necesita ninguna de bloqueo.O si ambos comparten el mismo bloque de memoria y sólo se utiliza la mitad superior de la misma, y el otro sólo la parte inferior, usted no necesita ninguna de bloqueo.Aunque no lo dijo, que esto conducirá a un buen rendimiento;especialmente no en la Cpu multi-core.Las operaciones de escritura de un hilo para esto los datos compartidos (ejecutando un núcleo) que podría obligar a que la memoria caché se vacía para otro hilo (que se ejecuta en otro núcleo) y estos vaciado de la caché a menudo son el cuello de botella para multithread de las aplicaciones que se ejecutan en las modernas Cpu multi-core.

Answer 5

Como mi profesor (Nir Shavit de "El Arte de Multiprocesador de Programación"), dijo a la clase:Por favor, no.La razón principal es la capacidad de prueba - no se puede probar el código de sincronización.Puede ejecutar simulaciones, puede incluso prueba de estrés.Pero es una aproximación.Lo que realmente necesita es matemático, la corrección de la prueba.Y muy pocos capaces comprensión de ellos, y mucho menos escribir.Así que, como otros, había dicho:la utilización de las bibliotecas. Joe Duffy blog las encuestas de algunas técnicas (sección 28).El primero que se debe tratar es el árbol de división de salto a tareas más pequeñas y combinar.

Answer 6

La inmutabilidad es un método para evitar el bloqueo.Ver Eric Lippert la discusión y la implementación de las cosas como inmutable pilas y colas.

Answer 7

en re.Suma de la respuesta, Maurice Herlithy muestra en El Arte de Multiprocesador de Programación que en realidad nada puede ser por escrito y sin bloqueos (véase el capítulo 6).si mal no recuerdo, Esta consiste esencialmente en la división de tareas en el procesamiento de elementos de nodo (como una función de cierre), y la colocación de cada uno.Hilos de calcular el estado siguiendo todos los nodos de la última caché uno.Obviamente, esto podría, en el peor de los casos, resultar en un rendimiento secuencial, pero tiene importantes lockless propiedades, la prevención de los escenarios donde los hilos podría conseguir programado por mucho tiempo peroids de tiempo cuando se mantiene bloqueos.Herlithy también logra teórico esperar un rendimiento libre, lo que significa que un hilo no va a esperar para siempre para ganar la atómica enqueue (esto es un montón de código complicado).

Multi-hilo de cola / pila es sorprendentemente duro (consulte el ABA problema).Otras cosas pueden ser muy simples.Acostumbrado a while(true) { atomicCAS hasta que he cambiado } bloques;ellos son increíblemente poderosos.Una intuición de lo que es correcto con CAS puede contribuir al desarrollo, a pesar de que deben hacer buen uso de las pruebas y tal vez más potentes herramientas (tal vez CROQUIS, próximos MIT Kendo, o spin?) para comprobar la corrección si se puede reducir a una simple estructura.

Por favor enviar más acerca de su problema.Es difícil dar una buena respuesta, sin más detalles.

editar immutibility es bonito, pero la aplicabilidad es limitada, si estoy entendiendo bien.Realmente no superar escribir-después de la lectura de los peligros;considere la posibilidad de dos hilos de ejecución "mem = NewNode(mem)";ambos pudieron leer mem, luego de tanto escribir;no son los correctos para un clásico de la función de incremento.También, probablemente lento debido a la asignación del montón (que tiene que estar sincronizado a través de los subprocesos).

Answer 8

Inmutability tendría este efecto.Los cambios en el objeto de resultado en un nuevo objeto.Lisp funciona de esta manera debajo de las cubiertas.

El artículo 13 de Efectivos De Java explica esta técnica.

Answer 9

Acantilado Clic tiene cúpula de algunas de las principales investigaciones sobre el bloqueo libre de estructuras de datos mediante la utilización de máquinas de estado finito y también ha publicado una gran cantidad de implementaciones de Java.Usted puede encontrar sus documentos, diapositivas y las implementaciones en su blog: http://blogs.azulsystems.com/cliff/

Answer 10

El uso de una implementación existente, ya que esta área de trabajo es el reino de los expertos de dominio y Doctorados (si quieres que lo haga a la derecha!)

Por ejemplo hay una biblioteca de código aquí:

http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

Answer 11

La mayoría de cierre libre de algoritmos o estructuras de comenzar con algunos operación atómica, es decir,un cambio a una ubicación de memoria que una vez comenzada por un hilo será completado antes de cualquier otro hilo puede realizar la misma operación.¿Tiene usted una operación de ese tipo en su entorno?

Ver aquí para el canónica documento sobre este tema.

También intente esto artículo de la wikipedia artículo para obtener más ideas y enlaces.

Answer 12

El principio básico para el bloqueo de sincronización libre es este:

• cada vez que usted está leyendo la estructura, que siga la lectura con una prueba para ver si la estructura fue mutado desde que empezaste a leer, y volver a intentar hasta que usted tenga éxito en la lectura sin algo más llegando a lo largo y mutando mientras que usted está haciendo;

• cada vez que se la mutación de la estructura, debe organizar su algoritmo y datos, por lo que no hay una sola atómica de paso que, si se toma, hace que todo cambio sea visible para los otros hilos, y arreglar las cosas para que ninguno de los cambios es visible a menos que el paso de la toma.Utilice cualquier lockfree atómica existe un mecanismo en su plataforma para que el paso (por ejemplo,comparar y establecer, de carga ligada+tienda-condicional, etc.).En que paso a continuación, debe comprobar para ver si cualquier otro hilo ha mutado el objeto debido a la mutación que se inició la operación, comprometerse si no ha y empezar de nuevo si es que tiene.

Hay un montón de ejemplos de bloqueo libre de estructuras en la web;sin saber más acerca de lo que va a implementar y en qué plataforma es duro para ser más específicos.

Answer 13

Si usted está escribiendo su propia libre de bloqueo de estructuras de datos para un multi-core cpu, no te olvides de barreras de memoria!También, considere la posibilidad de buscar en Software De Memoria De La Transacción técnicas.

Answer 14

Bien, esto depende del tipo de estructura, pero usted tiene que hacer la estructura, de modo que con cuidado y en silencio se detecta y controla los posibles conflictos.

Dudo que puedas hacer uno que es 100% libre de bloqueo, pero de nuevo, depende de qué tipo de estructura que usted necesita para construir.

Usted podría tener también un fragmento de la estructura, de modo que varios subprocesos de trabajo en los elementos individuales, y luego sincronizar/recombinar.

Answer 15

Como se ha mencionado, es realmente depende de qué tipo de estructura de la que estamos hablando.Por ejemplo, puede escribir un limitado sin bloqueo de cola, pero no uno que permite el acceso aleatorio.

Answer 16

Reducir o eliminar compartido el estado mutable.

Answer 17

En Java, utilizar el java.util.simultánea de los paquetes en el JDK 5+ en lugar de escribir su propio.Como se mencionó anteriormente, este es realmente un campo para los expertos, y a menos que usted tiene un repuesto o dos años, el rodar de su propio no es una opción.

Answer 18

Puede usted aclarar lo que entendemos por estructura?

Ahora, estoy suponiendo que te refieres a la arquitectura general.Usted puede lograr esto por no compartir la memoria entre procesos, y mediante el uso de un actor de modelo para sus procesos.

Answer 19

Echa un vistazo a mi enlace ConcurrentLinkedHashMap para obtener un ejemplo de cómo escribir un cierre libre de la estructura de datos.No está basado en ninguna de trabajos académicos y no requiere de años de investigación como a los demás implica.Simplemente se requiere de una cuidadosa ingeniería.

Mi aplicación hace uso de un ConcurrentHashMap, que es un bloqueo por cubo algoritmo, pero no confían en que los detalles de ejecución.Podría ser fácilmente reemplazado con Cliff haga Clic en bloqueo de la libre aplicación.Me prestaron una idea desde un Acantilado, pero de forma mucho más explícita, es modelo de todas las operaciones CAS con una máquina de estado.Esto simplifica en gran medida el modelo, como se verá a lo que me han pseudo bloqueos a través de la 'ing estados.Otro truco es permitir que la pereza y resolver como sea necesario.Usted verá esto, a menudo, con retrocesos o dejar que otros hilos de "ayuda" para la limpieza.En mi caso, me decidí a permitir a los muertos de los nodos en la lista de ser desalojado cuando llegan a la cabeza, en lugar de lidiar con la complejidad de la eliminación de ellos de la mitad de la lista.Puedo cambiar eso, pero yo no confiar plenamente mi algoritmo de retroceso y quería poner fuera de un cambio importante como la adopción de un 3-nodo de bloqueo de enfoque.

El libro "El Arte de Multiprocesador de Programación" es un manual muy bueno.En general, sin embargo, me gustaría recomendar evitar el bloqueo de diseños libres en el código de la aplicación.Muchas veces es simplemente una exageración donde otros, menos propenso a errores, las técnicas son las más adecuadas.

Answer 20

Si ves que la contención de bloqueo, en primer lugar, trate de usar más granular cerraduras de las estructuras de datos en lugar de cerrar completamente libre de algoritmos.

Por ejemplo, yo actualmente trabajo en la aplicación multiproceso, que tiene una costumbre de sistema de mensajería (lista de colas para cada uno de los subprocesos, la cola contiene mensajes para rosca a proceso) para transmitir información entre los hilos.Hay un bloqueo global en esta estructura.En mi caso, no necesito velocidad mucho, así que realmente no importa.Pero si este bloqueo podría convertirse en un problema, podría ser reemplazado por bloqueos individuales en cada cola, por ejemplo.A continuación, añadir/eliminar elemento de a/de la cola específica podría no afectar a otras colas.Habría aún un bloqueo global para la adición de nuevas cola y tal, pero no sería mucho problema.

Incluso un único multi-produce/consumidor de la cola puede ser escrito con granular de bloqueo en cada elemento, en lugar de tener un bloqueo global.Esto también puede eliminar la contención.

Answer 21

Si usted lee varias implementaciones y artículos sobre el tema, usted notará que hay es el siguiente tema en común:

1) El estado compartido objetos lisp/clojure estilo inmutable:es decir, todas las operaciones de escritura se implementan copiar el estado existente en un nuevo objeto, realizar modificaciones en el nuevo objeto y, a continuación, intente actualizar el estado compartido (obtenido a partir de un alineados puntero que puede ser actualizado con el CAS primitivo).En otras palabras, usted NUNCA modificar un objeto existente que pueda ser leído por más que el subproceso actual.Inmutability puede ser optimizado con Copy-on-Write semántica para grandes, objetos complejos, pero eso es otro árbol de los frutos secos

2) usted especifique claramente lo que permitió la transición entre el actual y el siguiente estado son válidos:Luego de la validación de que el algoritmo es válido se convierten en órdenes de magnitud más fácil

3) Manejar descarta referencias en peligro puntero listas por hilo.Después de los objetos de referencia son seguros, reutilizar si es posible

Ver otro post mío donde el código implementado con semáforos y los mutexes es (parcialmente) puesto en una cerradura-estilo libre:La exclusión mutua y semáforos