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 de bloqueo tradicionales . Un algoritmo no bloqueante no tiene bloqueos si hay un progreso garantizado en todo el sistema y no tiene esperas si también hay un progreso garantizado por hilo. "No bloqueante" se utilizó como sinónimo de "sin bloqueos" en la literatura hasta la introducción de la libertad de obstrucción en 2003. [2]
La palabra "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 relés "sin tener que reorganizar las llamadas existentes" (véase red Clos ). Además, si la central telefónica "no está defectuosa, siempre puede realizar la conexión" (véase conmutador de expansión mínima sin bloqueo ).
El enfoque tradicional de la programación multiproceso consiste en utilizar bloqueos para sincronizar el acceso a los recursos compartidos . Las primitivas de sincronización, como los mutex , los semáforos y las secciones críticas , son mecanismos mediante los cuales un programador puede garantizar que ciertas secciones de código no se ejecuten simultáneamente si al hacerlo se dañarían las estructuras de memoria compartida. Si un subproceso intenta adquirir un bloqueo que ya posee otro subproceso, el subproceso 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 podrá lograr nada: si el hilo bloqueado hubiera estado realizando una tarea de alta prioridad o en tiempo real , sería altamente indeseable detener su progreso.
Otros problemas son menos obvios. Por ejemplo, ciertas interacciones entre bloqueos pueden generar condiciones de error, como bloqueos muertos , bloqueos activos e inversión de prioridad . El uso de bloqueos también implica un equilibrio 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 no bloqueantes no sufren estos inconvenientes y, además, son seguros para su uso en controladores de interrupciones : aunque no se pueda reanudar el hilo interrumpido , aún es posible avanzar 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 controlador de interrupciones, ya que el hilo interrumpido puede ser el que mantiene el bloqueo. Si bien esto se puede rectificar 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 se puede observar una latencia de interrupción excesiva. [3]
Se puede utilizar una estructura de datos sin bloqueos para mejorar el rendimiento. Una estructura de datos sin bloqueos aumenta la cantidad de tiempo empleado en la ejecución paralela en lugar de la ejecución en serie, lo que mejora el rendimiento en un procesador de múltiples núcleos , porque el acceso a la estructura de datos compartida no necesita ser serializado para permanecer coherente. [4]
Con pocas excepciones, los algoritmos no bloqueantes utilizan primitivas atómicas de lectura-modificación-escritura que el hardware debe proporcionar, la más notable de las cuales es comparar e intercambiar (CAS) . Las secciones críticas casi siempre se implementan utilizando interfaces estándar sobre estas primitivas (en el caso general, las secciones críticas serán bloqueantes, incluso cuando se implementan con estas primitivas). En la década de 1990, todos los algoritmos no bloqueantes tenían que escribirse "de forma 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 muchas investigaciones para proporcionar estructuras de datos básicas , como pilas , colas , conjuntos y tablas hash , que permiten que los programas intercambien datos fácilmente entre subprocesos de forma asincrónica.
Además, algunas estructuras de datos no bloqueantes son lo suficientemente débiles como para implementarse sin primitivas atómicas especiales. Estas excepciones incluyen:
Varias bibliotecas utilizan internamente técnicas sin bloqueos, [7] [8] [9] pero es difícil escribir código sin bloqueos 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 reorganizar agresivamente las operaciones. Incluso cuando no lo hacen, muchas CPU modernas a menudo reorganizan dichas operaciones (tienen un " modelo de consistencia débil "), a menos que se use una barrera de memoria para indicarle a la CPU que no reordene. Los programadores de C++11 pueden usar std::atomicen <atomic>, y los programadores de C11 pueden usar <stdatomic.h>, los cuales proporcionan tipos y funciones que le indican al compilador que no reorganice dichas instrucciones y que inserte las barreras de memoria apropiadas. [14]
La libertad 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 libertad de inanición . Un algoritmo no tiene necesidad de espera si cada operación tiene un límite en la cantidad de pasos que dará antes de que se complete la operación. [15] Esta propiedad es fundamental para los sistemas en tiempo real y siempre es bueno tenerla siempre que el costo de rendimiento no sea demasiado alto.
En la década de 1980 [16] se demostró que todos los algoritmos se pueden implementar sin esperas, y se han demostrado muchas transformaciones a partir de código serial, llamadas construcciones universales . Sin embargo, el rendimiento resultante en general no coincide ni siquiera con los diseños de bloqueo ingenuos. Desde entonces, varios artículos han mejorado el rendimiento de las construcciones universales, pero aún así, su rendimiento está muy por debajo 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 escasez de muchas estructuras de datos comunes sin que los costos de memoria crezcan linealmente en el número de subprocesos.
Pero en la práctica, estos límites inferiores no presentan una barrera real, ya que gastar una línea de caché o un gránulo de reserva exclusivo (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 requerida lógicamente 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 exclusivo colisionarán, por lo que la cantidad de almacenamiento requerida físicamente [ cita 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 bloqueos de Michael y Scott [19] , que es una cola eficiente que se usa a menudo en la práctica. Un artículo de seguimiento de Kogan y Petrank [20] proporcionó un método para hacer que los algoritmos sin espera sean rápidos y utilizó este método para hacer que la cola sin espera sea prácticamente tan rápida como su contraparte sin bloqueos. Un artículo posterior de Timnat y Petrank [21] proporcionó un mecanismo automático para generar estructuras de datos sin espera a partir de otras sin bloqueos. Por lo tanto, ahora hay implementaciones sin espera disponibles para muchas estructuras de datos.
Bajo supuestos razonables, Alistarh, Censor-Hillel y Shavit demostraron que los algoritmos sin bloqueo prácticamente no requieren esperas. [22] Por lo tanto, la complejidad algorítmica adicional de un algoritmo sin esperas podría no valer la pena si no hay plazos estrictos que cumplir.
La ausencia de bloqueos permite que los subprocesos individuales se queden sin energía, pero garantiza el rendimiento de todo el sistema. Un algoritmo está libre de bloqueos si, cuando los subprocesos del programa se ejecutan durante un tiempo suficientemente largo, al menos uno de los subprocesos avanza (según una definición sensata de progreso). Todos los algoritmos sin esperas están libres de bloqueos.
En particular, si se suspende un subproceso, un algoritmo sin bloqueos garantiza que los subprocesos restantes puedan seguir avanzando. Por lo tanto, si dos subprocesos pueden competir por el mismo bloqueo mutex o spinlock, el algoritmo no está libre de bloqueos. (Si suspendemos un subproceso que mantiene el bloqueo, el segundo subproceso se bloqueará).
Un algoritmo no tiene bloqueos si una cantidad infinita de veces la operación de algunos procesadores tendrá éxito en un número finito de pasos. Por ejemplo, si N procesadores intentan ejecutar una operación, algunos de los N procesos tendrán éxito en finalizar la operación en un número finito de pasos y otros podrían fallar y volver a intentarlo en caso de falla. La diferencia entre un algoritmo sin esperas y un algoritmo sin bloqueos es que se garantiza que la operación sin esperas de cada proceso tendrá éxito en un número finito de pasos, independientemente de los otros procesadores.
En general, un algoritmo sin bloqueos puede ejecutarse en cuatro fases: completar la propia operación, ayudar a una operación que obstruye, abortar una operación que obstruye y esperar. La finalización de la propia operación es complicada por la posibilidad de asistencia y abortación simultáneas, pero es invariablemente la vía más rápida para completarla.
La decisión sobre cuándo ayudar, abortar o esperar cuando se encuentra una obstrucción es responsabilidad de un administrador de contención . Esto puede ser muy simple (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, 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 que recibe asistencia también se ralentizará si aún está en ejecución.
La ausencia de obstrucciones es la garantía natural más débil de progreso sin bloqueos. Un algoritmo está libre de obstrucciones si, en cualquier momento, un único hilo ejecutado de forma aislada (es decir, con todos los hilos que lo obstruyen suspendidos) durante un número limitado de pasos completará su operación. [15] Todos los algoritmos sin bloqueos están libres de obstrucciones.
La ausencia de obstrucciones exige únicamente que cualquier operación parcialmente completada pueda ser abortada y que los cambios realizados puedan revertirse. La eliminación de la asistencia simultánea puede dar lugar a algoritmos mucho más simples y fáciles de validar. Evitar que el sistema se bloquee continuamente es la tarea de un administrador 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, luego leen el otro marcador y luego comparan los marcadores. Los datos son consistentes si los dos marcadores son idénticos. Los marcadores pueden no ser idénticos cuando la lectura es interrumpida por otro proceso que actualiza la estructura de datos. En tal caso, el proceso descarta los datos en el búfer interno y vuelve a intentarlo.