Algoritmo sin bloqueo

En informática , un algoritmo se denomina no bloqueante si el fallo o la suspensión de cualquier hilo no puede provocar el fallo o la suspensión de otro hilo; ^{[ 1 ]} para algunas operaciones, estos algoritmos proporcionan una alternativa útil a las implementaciones bloqueantes tradicionales . Un algoritmo no bloqueante es libre de bloqueo si se garantiza el progreso en todo el sistema , y ​​libre de espera si también se garantiza el progreso por hilo. "No bloqueante" se utilizó como sinónimo de "libre de bloqueo" en la literatura hasta la introducción de la ausencia de obstrucciones en 2003. ^{[ 2 ]}

El término «sin bloqueo» se utilizaba tradicionalmente para describir las redes de telecomunicaciones que podían enrutar una conexión a través de un conjunto de repetidores «sin tener que reorganizar las llamadas existentes» (véase red Clos ). Asimismo, si la central telefónica «no está defectuosa, siempre puede establecer la conexión» (véase conmutador de extensión mínima sin bloqueo ).

El enfoque tradicional para la programación multihilo consiste en usar bloqueos para sincronizar el acceso a recursos compartidos . Primitivas de sincronización como mutexes , semáforos y secciones críticas son mecanismos que permiten al programador asegurar que ciertas secciones de código no se ejecuten simultáneamente, si esto pudiera dañar las estructuras de memoria compartida. Si un hilo intenta adquirir un bloqueo que ya está en manos de otro hilo, se bloqueará hasta que el bloqueo quede libre.

Bloquear un hilo puede ser indeseable por muchas razones. Una razón obvia es que, mientras el hilo está bloqueado, no puede realizar ninguna tarea: si el hilo bloqueado estuviera ejecutando una tarea de alta prioridad o en tiempo real , sería muy indeseable detener su progreso.

Otros problemas son menos evidentes. Por ejemplo, ciertas interacciones entre bloqueos pueden provocar errores como interbloqueos , bloqueos permanentes e inversión de prioridad . El uso de bloqueos también implica una compensación entre el bloqueo de grano grueso, que puede reducir significativamente las oportunidades de paralelismo , y el bloqueo de grano fino, que requiere un diseño más cuidadoso, aumenta la sobrecarga de bloqueo y es más propenso a errores.

A diferencia de los algoritmos de bloqueo, los algoritmos sin bloqueo no presentan estos inconvenientes y, además, son seguros para su uso en manejadores de interrupciones : aunque el hilo interrumpido no pueda reanudarse, el progreso sigue siendo posible sin él. Por el contrario, no se puede acceder de forma segura a las estructuras de datos globales protegidas por exclusión mutua en un manejador de interrupciones, ya que el hilo interrumpido podría ser el que mantiene el bloqueo. Si bien esto puede solucionarse enmascarando las solicitudes de interrupción durante la sección crítica, esto requiere que el código en la sección crítica tenga un tiempo de ejecución limitado (y preferiblemente corto), o podría observarse una latencia de interrupción excesiva. ^{[ 3 ]}

Una estructura de datos sin bloqueo puede utilizarse para mejorar el rendimiento. Una estructura de datos sin bloqueo aumenta el tiempo dedicado a la ejecución en paralelo en lugar de la ejecución en serie, lo que mejora el rendimiento en un procesador multinúcleo , ya que el acceso a la estructura de datos compartida no necesita serializarse para mantener la coherencia. ^{[ 4 ]}

Salvo contadas excepciones, los algoritmos no bloqueantes utilizan primitivas atómicas de lectura, modificación y escritura que debe proporcionar el hardware, la más notable de las cuales es la comparación e intercambio (CAS) . Las secciones críticas casi siempre se implementan utilizando interfaces estándar sobre estas primitivas (en general, las secciones críticas serán bloqueantes, incluso cuando se implementen con estas primitivas). En la década de 1990, todos los algoritmos no bloqueantes debían escribirse "nativa" con las primitivas subyacentes para lograr un rendimiento aceptable. Sin embargo, el campo emergente de la memoria transaccional de software promete abstracciones estándar para escribir código no bloqueante eficiente. ^{[ 5 ] [ 6 ]}

También se han realizado numerosas investigaciones para proporcionar estructuras de datos básicas como pilas , colas , conjuntos y tablas hash . Estas permiten que los programas intercambien datos fácilmente entre hilos de forma asíncrona.

Además, algunas estructuras de datos no bloqueantes son lo suficientemente débiles como para implementarse sin primitivas atómicas especiales. Estas excepciones incluyen:

• Un búfer circular FIFO de un solo lector y un solo escritor , con un tamaño que divide uniformemente el desbordamiento de uno de los tipos enteros sin signo disponibles, puede implementarse incondicionalmente de forma segura utilizando únicamente una barrera de memoria.
• Lectura, copia y actualización con un único escritor y cualquier número de lectores. (Los lectores no tienen que esperar; el escritor generalmente no tiene que bloquearse hasta que necesita recuperar memoria).
• Lectura, copia y actualización con múltiples escritores y cualquier número de lectores. (Los lectores no tienen tiempos de espera; los múltiples escritores generalmente serializan con un bloqueo y no están libres de obstrucciones).

Varias bibliotecas utilizan internamente técnicas sin bloqueo, ^{[ 7 ] [ 8 ] [ 9 ]} pero es difícil escribir código sin bloqueo que sea correcto. ^{[ 10 ] [ 11 ] [ 12 ] [ 13 ]}

Los algoritmos no bloqueantes generalmente implican una serie de instrucciones de lectura, lectura-modificación-escritura y escritura en un orden cuidadosamente diseñado. Los compiladores optimizadores pueden reordenar agresivamente las operaciones. Incluso cuando no lo hacen, muchas CPU modernas a menudo reordenan dichas operaciones (tienen un " modelo de consistencia débil "), a menos que se utilice una barrera de memoria para indicarle a la CPU que no las reordene. Los programadores de C++11 pueden usar std::atomicen , y los programadores de C11 pueden usar , ambos proporcionan tipos y funciones que le indican al compilador que no reordene dichas instrucciones y que inserte las barreras de memoria apropiadas. ^{[ 14 ]}<atomic><stdatomic.h>

La ausencia de espera es la garantía de progreso sin bloqueo más sólida, ya que combina un rendimiento garantizado en todo el sistema con la ausencia de inanición . Un algoritmo es libre de espera si cada operación tiene un límite en el número de pasos que el algoritmo tomará antes de completarse. ^{[ 15 ]} Esta propiedad es fundamental para los sistemas en tiempo real y siempre es deseable, siempre que el costo en términos de rendimiento no sea demasiado alto.

^{En la década de 1980 [ 16 ]} se demostró que todos los algoritmos pueden implementarse sin esperas, y se han demostrado numerosas transformaciones a partir de código secuencial, denominadas construcciones universales . Sin embargo, el rendimiento resultante no suele igualar ni siquiera el de los diseños de bloqueo más sencillos. Desde entonces, varios artículos han mejorado el rendimiento de las construcciones universales, pero aún así, su rendimiento está muy por debajo del de los diseños de bloqueo.

Varios artículos han investigado la dificultad de crear algoritmos sin espera. Por ejemplo, se ha demostrado ^{[ 17 ]} que las primitivas condicionales atómicas ampliamente disponibles , CAS y LL/SC , no pueden proporcionar implementaciones sin inanición de muchas estructuras de datos comunes sin que los costos de memoria crezcan linealmente en el número de hilos.

Sin embargo, estos límites inferiores no representan una barrera real en la práctica, ya que gastar una línea de caché o un gránulo de reserva exclusiva (hasta 2  KB en ARM) de almacenamiento por hilo en la memoria compartida no se considera demasiado costoso para los sistemas prácticos. Normalmente, la cantidad de almacenamiento lógicamente requerida es una palabra, pero físicamente las operaciones CAS en la misma línea de caché colisionarán, y las operaciones LL/SC en el mismo gránulo de reserva exclusiva también colisionarán, por lo que la cantidad de almacenamiento físicamente requerida es mayor.

Los algoritmos sin espera eran poco comunes hasta 2011, tanto en la investigación como en la práctica. Sin embargo, en 2011, Kogan y Petrank ^{[ 18 ]} presentaron una cola sin espera basada en la primitiva CAS , generalmente disponible en hardware común. Su construcción amplió la cola sin bloqueo de Michael y Scott ^{[ 19 ]} , que es una cola eficiente de uso frecuente en la práctica. Un artículo posterior de Kogan y Petrank ^{[ 20 ]} proporcionó un método para hacer que los algoritmos sin espera fueran rápidos y lo utilizó para lograr que la cola sin espera fuera prácticamente tan rápida como su contraparte sin bloqueo. Un artículo posterior de Timnat y Petrank ^{[ 21 ]} proporcionó un mecanismo automático para generar estructuras de datos sin espera a partir de estructuras sin bloqueo. Por lo tanto, ahora existen implementaciones sin espera para muchas estructuras de datos.

Bajo supuestos razonables, Alistahr, Censor-Hillel y Shavit demostraron que los algoritmos sin bloqueo son prácticamente libres de espera. ^{[ 22 ]} Por lo tanto, en ausencia de plazos estrictos, los algoritmos sin espera pueden no justificar la complejidad adicional que introducen.

La ausencia de bloqueos permite que los hilos individuales se queden sin recursos, pero garantiza el rendimiento general del sistema. Un algoritmo es libre de bloqueos si, cuando los hilos del programa se ejecutan durante un tiempo suficientemente largo, al menos uno de ellos progresa (según una definición razonable de progreso). Todos los algoritmos sin espera son libres de bloqueos.

En particular, si se suspende un hilo, un algoritmo sin bloqueo garantiza que los hilos restantes puedan seguir avanzando. Por lo tanto, si dos hilos pueden competir por el mismo bloqueo mutex o spinlock , el algoritmo no es libre de bloqueo. (Si suspendemos un hilo que posee el bloqueo, el segundo hilo se bloqueará).

Un algoritmo es libre de bloqueo si, con una frecuencia infinita, la operación realizada por algunos procesadores tendrá éxito en un número finito de pasos. Por ejemplo, si N procesadores intentan ejecutar una operación, algunos de ellos la completarán con éxito en un número finito de pasos, mientras que otros podrían fallar y reintentarla. La diferencia entre un algoritmo sin espera y uno libre de bloqueo radica en que, en el algoritmo sin espera, la operación de cada proceso tiene garantizado el éxito en un número finito de pasos, independientemente de los demás procesadores.

En general, un algoritmo sin bloqueo puede ejecutarse en cuatro fases: completar la propia operación, asistir a una operación que interfiere, abortar una operación que interfiere y esperar. Completar la propia operación se complica por la posibilidad de asistencia y aborto simultáneos, pero invariablemente es la vía más rápida para su finalización.

La decisión sobre cuándo asistir, abortar o esperar cuando se encuentra una obstrucción es responsabilidad del gestor de contención . Esto puede ser muy sencillo (asistir a las operaciones de mayor prioridad, abortar las de menor prioridad) o puede estar más optimizado para lograr un mejor rendimiento o reducir la latencia de las operaciones priorizadas.

La asistencia concurrente correcta suele ser la parte más compleja de un algoritmo sin bloqueos, y a menudo resulta muy costosa de ejecutar: no solo se ralentiza el hilo que presta asistencia, sino que, gracias a la mecánica de la memoria compartida, el hilo al que se presta asistencia también se ralentizará si aún se está ejecutando.

La ausencia de obstrucciones es la garantía de progreso no bloqueante natural más débil. Un algoritmo está libre de obstrucciones si, en cualquier momento, un único hilo ejecutado de forma aislada (es decir, con todos los hilos que causan obstrucciones suspendidos) durante un número limitado de pasos completará su operación. ^{[ 15 ]} Todos los algoritmos sin bloqueo están libres de obstrucciones.

La ausencia de obstrucciones solo exige que cualquier operación parcialmente completada pueda abortarse y que los cambios realizados puedan revertirse. Eliminar la asistencia concurrente suele dar como resultado algoritmos mucho más sencillos y fáciles de validar. Evitar que el sistema se bloquee continuamente es tarea de un gestor de contención.

Algunos algoritmos sin obstrucciones utilizan un par de "marcadores de consistencia" en la estructura de datos. Los procesos que leen la estructura de datos primero leen un marcador de consistencia, luego leen los datos relevantes en un búfer interno, después leen el otro marcador y, finalmente, comparan ambos. Los datos son consistentes si los dos marcadores son idénticos. Los marcadores pueden no ser idénticos si la lectura se interrumpe por otro proceso que actualiza la estructura de datos. En tal caso, el proceso descarta los datos del búfer interno e intenta leer de nuevo.

• Introducción a la programación sin bloqueo
• Algoritmos sin bloqueo