multithreading - ¿Cuándo son las estructuras de datos libres de bloqueo menos eficaces que la exclusión mutua(exclusión mutua)?
scheduling mutex (6)
Leí en algún lugar (ya no puedo encontrar la página) que las estructuras de datos de bloqueo libre son más eficientes "para ciertas cargas de trabajo", lo que parece implicar que a veces son más lentas o la ganancia de ellas puede ser cero en algunas situaciones. Tomar el golpe de ~ 100 ciclos de una instrucción de bloqueo para hacer una operación atómica me suena mucho más rápido que irme a dormir y esperar a que el programador vuelva a activar el proceso, por lo que no es obvio en qué circunstancias una estructura de datos sin bloqueo Sería menos preferible que las mutex antiguas. Si el bloqueo está disponible el 99% del tiempo y el proceso no tiene que irse a dormir, ¿es un mutex más rápido? ¿Existe una buena regla general para saber qué camino tomar, suponiendo que haya disponible una estructura de datos sin bloqueo adecuada?
La eficiencia depende de la métrica. Los algoritmos de bloqueo o de espera son importantes en los sistemas en los que la anticipación puede introducir un punto muerto o afectar los plazos de programación. En esos casos, el procesamiento es menos importante que la corrección.
El OP considera el bloqueo como una alternativa a mutexes. Algunos algoritmos no requieren ni acceder a una estructura de datos compartida. En estos casos, tanto el productor como el consumidor pueden acceder a la misma estructura de datos simultáneamente sin tener en cuenta la otra. Un ejemplo de una cola compartida permite que un solo lector y un solo escritor actúen simultáneamente en una instancia compartida. Esto satisface la necesidad común de que un controlador de dispositivo escriba datos a los que un proceso de consumidor puede acceder a pedido.
Se pueden permitir relaciones más complejas entre los procesos (consulte Herlihy (1991) para un análisis) con diferentes niveles de soporte de hardware. Concluye que la sincronización sin espera representa una ruptura cualitativa con las técnicas tradicionales basadas en bloqueo para implementar objetos concurrentes .
Lo que significa es que sigue habiendo una compensación, pero que no se trata simplemente de elegir entre mutexes y spinlocks.
Queda una regla de oro para centrarse en la corrección en lugar del rendimiento. El rendimiento generalmente se puede lograr arrojando dinero al problema, mientras que cumplir con los requisitos suele ser más difícil.
Las estructuras de datos sin bloqueo utilizarán, de una forma u otra, la semántica atómica de su arquitectura para realizar sus operaciones principales. Al hacer esto, puede utilizar los mecanismos de exclusión internos completos de la máquina para garantizar el orden correcto o el cercado de datos. Un mutex o sección crítica también hace esto, pero solo lo hace una vez para una sola bandera. Donde el mutex o la sección crítica es lenta, es cuando falla la adquisición del bloqueo (hay disputa). En este caso, el sistema operativo también invoca al programador para suspender el subproceso hasta que se libere el objeto de exclusión.
Por lo tanto, parece lógico que cada vez que su estructura de datos sin bloqueo utilice múltiples operaciones atómicas por método central cuando un solo bloqueo que protege una sección crítica podría proporcionar la misma semántica Y , en la práctica, suele haber muy poca contención para la estructura de datos en cuestión En realidad, tiene más sentido utilizar un mecanismo de bloqueo provisto por el sistema operativo que intentar construir uno propio.
Me gustaría agregar un punto a esta parte de la respuesta: "Cuando el mutex o la sección crítica es lenta, es cuando falla la adquisición del bloqueo (hay disputa). En este caso, el sistema operativo también invoca al programador para suspender el hilo hasta que el objeto de exclusión ha sido liberado ".
Parece que los diferentes sistemas operativos pueden tener diferentes enfoques en cuanto a qué hacer cuando falla la adquisición del bloqueo. Yo uso HP-UX y, por ejemplo, tiene un enfoque más sofisticado para bloquear mutexes. Aquí está su descripción:
... Por otro lado, cambiar de contexto es un proceso costoso. Si la espera va a ser corta, preferimos no cambiar el contexto. Para equilibrar estos requisitos, cuando intentamos obtener un semáforo y lo encontramos bloqueado, lo primero que hacemos es esperar un poco. Se llama a la rutina psema_spin_1 () para girar hasta 50,000 ciclos de reloj tratando de obtener el bloqueo. Si no conseguimos el bloqueo después de 50,000 ciclos, llamamos a psema_switch_1 () para abandonar el procesador y dejar que otro proceso asuma el control.
Tenga en cuenta que un mutex puede implementarse como una estructura de datos sin bloqueo, en el sentido de que utiliza uno o unos pocos objetos atómicos para representar su estado. Es una falsa dicotomía.
Lo mejor es considerar si necesita permitir que varios subprocesos esperen para acceder a algún conjunto de operaciones o bloquear hasta que se indique. Cada uno requiere una cola de hilos en espera. Los hilos de colas anteriores en espera de acceso al área sincronizada, mientras que los hilos de colas anteriores esperan una señal. Las clases Java AbstractQueuedSynchronizer y AbstractQueuedLongSynchronizer proporcionan una cola de este tipo, en particular una cola CLH, a partir de la cual se pueden crear mutex, condiciones y otras primitivas basadas en la cola.
Si sus requisitos favorecen, en cambio, solo un subproceso realiza un conjunto exclusivo de trabajo, mientras que otros permanecen libres para continuar con otro trabajo, en lugar de esperar hasta que ellos también puedan realizar el mismo trabajo, entonces es posible utilizar técnicas sin bloqueo. Si hacerlo otorgará tiempos de ejecución más rápidos a la evaluación comparativa, estará sujeto a la frecuencia y la cantidad de subprocesos que contendrán a través de estos controles de sincronización, y si hay otro trabajo para que los subprocesos se realicen de forma independiente.
Un enfoque común para implementar una estructura de datos sin bloqueo es tener una referencia mutable a un objeto inmutable, y hacer que cualquier cosa que quiera cambiar la estructura tome la referencia, produzca una nueva versión del objeto con los cambios adecuados aplicados y luego CompareExchange La referencia para apuntar al nuevo objeto. Si el CompareExchange funciona, genial. De lo contrario, abandone el nuevo objeto, vuelva a tomar la referencia y comience de nuevo.
Esto puede funcionar bien si producir el nuevo objeto es barato y el nivel de contención es lo suficientemente bajo para que el CompareExchange generalmente funcione. Si hay una contención considerable, y si la producción del nuevo objeto es lenta, los intentos simultáneos de actualizaciones de N subprocesos pueden tardar N ^ 2 en completarse. Como ejemplo extremo, supongamos que se ejecutan 100 subprocesos en una CPU, una actualización toma 100 ms de tiempo de CPU (poco más de un intervalo de tiempo) y los 100 subprocesos intentan actualizar un objeto a la vez. Durante los primeros diez segundos, cada hilo producirá un nuevo objeto basado en el original. Uno de los subprocesos realizará satisfactoriamente el CompareExchange, mientras que los otros fallarán. Luego, durante los siguientes 9,9 segundos, 99 subprocesos generarán nuevas versiones del objeto, después de lo cual uno publicará con éxito su actualización y 98 fallarán. El efecto neto será que el método sin bloqueo tomará un tiempo de CPU de 505 segundos para realizar 100 actualizaciones, cuando un sistema de bloqueo podría haberlos hecho en unos 10 segundos.
No sé cómo hacerlo más lento , pero ciertamente hace que sea más difícil hacerlo bien. En los muchos casos en que los dos enfoques son virtualmente idénticos en rendimiento (o cuando simplemente no importa si toma 500 pico-segundos en lugar de 100 pico-segundos), elija el enfoque más simple, generalmente el lock .
Hay muy pocos casos en que ese bit extra de rendimiento es clave; y si es así , sospecho que harías bien en usar las implementaciones de patrones pre-enrollados de bibliotecas establecidas. Hacer que el código sin bloqueo funcione correctamente (y demostrar que funciona correctamente en todas las condiciones ) a menudo es muy difícil.
Tenga en cuenta también que algunos entornos ofrecen un nivel de bloqueo por encima del mutex proporcionado por el sistema operativo; comportamiento de exclusión mutua, pero sin algunos de los gastos generales (por ejemplo, Monitor en .NET).