multithreading - lock - ¿Los algoritmos sin bloqueo realmente funcionan mejor que sus contrapartes de bloqueo total?
lock c# español (9)
Más allá de los casos simples de las funciones de InterlockedXxx, parece que el patrón predominante con todos estos es que implementan sus propios bloqueos.
Ninguna de las respuestas aquí parece llegar al corazón de la diferencia entre un loop CAS "libre de bloqueo" y un mutex o spin-lock.
La diferencia importante es que se garantiza que los algoritmos sin bloqueo progresen por sí solos , sin la asistencia de otros hilos. Con un bloqueo o bloqueo de giro, cualquier hilo defectuoso que no pueda adquirir un bloqueo está completamente a merced del hilo que posee el bloqueo. El hilo pobre que no puede adquirir el bloqueo no puede hacer nada excepto esperar (ya sea a través de una espera ocupada o un sueño asistido por el sistema operativo).
Con los algoritmos de bloqueo que activan un CAS, se garantiza que cada subproceso progresará independientemente de lo que estén haciendo otros subprocesos contendientes. Cada hilo está, esencialmente, en control de su propio destino. Sí, aún puede tener que repetirse varias veces, pero el número de veces que se bucles está limitado por la cantidad de hilos contendientes. No puede bucle infinito, en su mayor parte. (En la práctica, es posible que se produzca bloqueo en vivo debido, por ejemplo, a un ciclo LL/SC que sigue fallando debido a la compartición falsa), pero nuevamente las medidas pueden ser tomadas por el propio hilo para lidiar con esto; no está a merced de otro hilo sosteniendo un candado.
En cuanto a rendimiento, depende. He visto ejemplos flagrantes de algoritmos sin bloqueo totalmente superados por sus contrapartes de bloqueo, incluso bajo la contención de alto hilo. En una máquina x86-64 con Debian 7, comparé el rendimiento entre la cola C ++ Boost.Lockfree (basada en el algoritmo de Michael / Scott) y un entorno simple std::queue por un std::mutex . Bajo alta contención de hilos, la versión sin cerradura fue casi dos veces más lenta.
Entonces, ¿por qué es eso? Bueno, el rendimiento de los algoritmos de lockfree finalmente se reduce a los detalles de implementación. ¿Cómo el algoritmo evita ABA? ¿Cómo logra la recuperación de memoria segura? Hay tantas variantes ... punteros etiquetados, recuperación basada en época, RCU / estado de reposo, indicadores de peligro, recolección general de basura en todo el proceso, etc. Todas estas estrategias tienen implicaciones de rendimiento, y algunas también imponen restricciones sobre cómo su aplicación en general puede ser diseñado. En general, los enfoques de recuento de referencias (o enfoques de punteros etiquetados) tienden a tener un rendimiento pobre, en mi experiencia. Pero las alternativas pueden ser mucho más complejas de implementar y requieren mucha más infraestructura de recuperación de memoria basada en el almacenamiento local de subprocesos o la recolección de basura generalizada.
Raymond Chen ha estado haciendo una huge series on algorithms lockfree . Más allá de los casos simples de las funciones de InterlockedXxx , parece que el patrón predominante con todos estos es que implementan sus propios bloqueos . Claro, no hay bloqueos de procesador, pero el concepto de bucle repetitivo en cada CPU para garantizar la coherencia es muy parecido a un spinlock. Y al ser un spinlock, van a ser menos eficientes que los bloqueos generales que vienen con el sistema operativo porque no ceden el control de sus cuantos mientras esperan otros hilos. Por lo tanto, cada vez que alguien acude a mí y me dice "pero mi algoritmo está libre de bloqueos", ¿mi respuesta general es "así"?
Tengo curiosidad: ¿hay puntos de referencia disponibles que muestren algoritmos sin bloqueo para tener una ventaja sobre sus contrapartes de bloqueo completo?
En Java, al menos, el bloqueo por sí mismo puede ser muy rápido. La palabra clave sincronizada no agrega mucha sobrecarga. Puede compararlo usted mismo simplemente llamando a un método sincronizado en un bucle.
El bloqueo solo se vuelve lento cuando hay conflicto, y el proceso que se bloquea no es instantáneo.
En Windows en x64, un libre-lock libre (sin combinar array frente a los freelist) es aproximadamente un orden de magnitud más rápido que un libre-libre mutex.
En mi computadora portátil (Core i5), para un solo hilo, sin bloqueo consigo aproximadamente 31 millones de operaciones libres por segundo, frente a mutex, alrededor de 2,3 millones de operaciones por segundo.
Para dos subprocesos (en núcleos físicos separados), con el sistema sin bloqueos obtengo aproximadamente 12.4 millones de operaciones freelist por hilo. Con un mutex, obtengo unas 80 MIL operaciones por segundo.
En general, los algoritmos de bloqueo libre son menos eficientes por hilo; usted está haciendo más trabajo, como usted mencionó, para implementar un algoritmo de bloqueo libre que un simple bloqueo.
Sin embargo, tienden a mejorar drásticamente el rendimiento global del algoritmo en su conjunto frente a la discordia. La latencia de conmutación de subprocesos y los cambios de contexto , que son rápidos en muchos subprocesos, ralentizan drásticamente el rendimiento de su aplicación. Los algoritmos de bloqueo libre están implementando efectivamente sus propios "bloqueos", pero lo hacen de una manera que previene o reduce el número de conmutadores de contexto, por lo que tienden a realizar sus contrapartes de bloqueo.
Dicho eso, la mayor parte de esto depende del algoritmo (y la implementación) en cuestión. Por ejemplo, tengo algunas rutinas que logré cambiar a las nuevas colecciones concurrentes de .NET 4 en lugar de usar los mecanismos de bloqueo anteriores, y he medido mejoras de más del 30% en la velocidad total de mi algoritmo. Dicho esto, hay muchos puntos de referencia que puede encontrar que muestran un rendimiento reducido con algunas de estas mismas colecciones en comparación con un bloqueo básico. Como con todas las optimizaciones de rendimiento, realmente no lo sabes hasta que lo midas .
La principal ventaja de los algoritmos genuinamente libres de bloqueo es que son robustos incluso si una tarea se embauca (tenga en cuenta que el bloqueo es una condición más difícil que "no usar bloqueos" (*)). Si bien existen ventajas de rendimiento para evitar bloqueos innecesarios, las estructuras de datos de mejor rendimiento son a menudo las que pueden operar bloqueando en muchos casos, pero que pueden usar bloqueos para minimizar la vibración.
(*) He visto algunos intentos de colas multiproducto "sin bloqueo", en las que un productor que se atropelló en el momento equivocado evitaría que los consumidores vean artículos nuevos hasta que complete su trabajo); tales estructuras de datos realmente no deberían llamarse "sin bloqueo". Un productor que se bloquea no impedirá que otros productores progresen, pero puede bloquear arbitrariamente a los consumidores.
Lock-free también tiene la ventaja de que no duerme. Hay lugares en núcleos donde no se permite que duerman (el kernel de Windows tiene muchos de ellos) y eso restringe de manera dolorosa su capacidad para usar estructuras de datos.
Los algoritmos sin bloqueo pueden ser absolutamente más rápidos que su contraparte de bloqueo. Pero, por supuesto, lo inverso también es cierto. Suponiendo que la implementación funciona mejor que la parte del contador de bloqueo, el único factor limitante es la contención.
Tome las dos clases de Java, ConcurrentLinkedQueue y LinkedBlockingQueue. Bajo un conteo moderado del mundo real, el CLQ supera al LBQ en una buena cantidad. Con gran controversia, el uso de hilos suspendidos permitirá que el LBQ funcione mejor.
No estoy de acuerdo con user237815. La palabra clave sincronizada no requiere tanta sobrecarga como antes, pero en relación con un algoritmo sin bloqueo, tiene una buena cantidad de sobrecarga asociada a ella en comparación con un solo CAS.
Recientemente, el empleado de JavaOne Russia Oracle (que se especializa en rendimiento y puntos de referencia de Java) ha mostrado algunas medidas sobre operaciones por segundo dentro del acceso paralelo al contador simple simple, utilizando CAS (locklock libre, spinlock de alto nivel de hecho) y bloqueos clásicos (java .util.concurrent.locks.ReentrantLock)
http://dl.dropbox.com/u/19116634/pics/lock-free-vs-locks.png // lo siento, no puedo pegar imágenes
De acuerdo con esto, los bloqueos giratorios tienen un mejor rendimiento solo hasta que la cantidad de subprocesos intenta acceder al monitor.
Sin necesidad de bloqueo no es necesariamente más rápido, pero puede eliminar la posibilidad de bloqueo o bloqueo en tiempo real, por lo que puede garantizar que su programa siempre progresará hacia el acabado. Con las cerraduras, es difícil hacer una garantía de este tipo: es muy fácil pasar por alto una posible secuencia de ejecución que resulta en un punto muerto.
Pasado eso, todo depende. Al menos en mi experiencia, las diferencias en la velocidad tienden a depender más del nivel de habilidad implementado en la implementación que de si usa bloqueos o no.