En informática , un algoritmo se denomina sin bloqueo si la falla o suspensión de cualquier hilo no puede causar la falla o suspensión de otro hilo; [1] para algunas operaciones, estos algoritmos proporcionan una alternativa útil a las implementaciones de bloqueo tradicionales . Un algoritmo sin bloqueo no tiene bloqueos si hay un progreso garantizado en todo el sistema y no tiene esperas si también hay un progreso garantizado por subproceso. "Sin bloqueo" se utilizó como sinónimo de "sin bloqueo" 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" (ver Red Clos ). Además, si la central telefónica "no está defectuosa, siempre podrá establecer la conexión" (ver interruptor de mínima amplitud sin bloqueo ).
El enfoque tradicional de la programación multiproceso es utilizar bloqueos para sincronizar el acceso a recursos compartidos . Las primitivas de sincronización, como mutex , semáforos y secciones críticas, son mecanismos mediante los cuales un programador puede garantizar que ciertas secciones de código no se ejecuten simultáneamente, si hacerlo corrompería las estructuras de memoria compartida. Si un subproceso intenta adquirir un candado que ya tiene otro subproceso, el subproceso se bloqueará hasta que el candado esté libre.
Bloquear un hilo puede ser indeseable por muchas razones. Una razón obvia es que mientras el hilo está bloqueado, no puede lograr nada: si el hilo bloqueado hubiera estado realizando una tarea de alta prioridad o en tiempo real , sería muy indeseable detener su progreso.
Otros problemas son menos obvios. Por ejemplo, ciertas interacciones entre bloqueos pueden provocar condiciones de error como interbloqueo , bloqueo activo 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 sufren estos inconvenientes y, además, son seguros para su uso en manejadores de interrupciones : aunque el hilo interrumpido no se puede reanudar, el progreso aún es 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 controlador de interrupciones, ya que el subproceso reemplazado puede ser el que mantiene el bloqueo, pero esto se puede rectificar fácilmente enmascarando la solicitud de interrupción durante la sección crítica. [3]
Se puede utilizar una estructura de datos sin bloqueos para mejorar el rendimiento. Una estructura de datos sin bloqueo aumenta la cantidad de 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 , porque no es necesario serializar el acceso a la estructura de datos compartida para mantener la coherencia. [4]
Con pocas excepciones, los algoritmos sin bloqueo utilizan primitivas atómicas de lectura, modificación y 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 se bloquearán, incluso cuando se implementen con estas primitivas). En la década de 1990, todos los algoritmos sin bloqueo debían 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 eficiente sin bloqueo. [5] [6]
También se han realizado muchas investigaciones para proporcionar estructuras de datos básicas como pilas , colas , conjuntos y tablas hash . Estos permiten que los programas intercambien datos fácilmente entre subprocesos de forma asincrónica.
Además, algunas estructuras de datos sin bloqueo son lo suficientemente débiles como para implementarse sin primitivas atómicas especiales. Estas excepciones incluyen:
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 sin bloqueo generalmente implican una serie de instrucciones de lectura, lectura-modificación-escritura y escritura en un orden cuidadosamente diseñado. La optimización de los compiladores puede 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 utilice una barrera de memoria para indicarle a la CPU que no reordene. Los programadores de C++ 11 pueden usar std::atomicin <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 e 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 libertad de hambre . Un algoritmo no requiere espera si cada operación tiene un límite en el número de pasos que dará el algoritmo antes de que se complete la operación. [15] Esta propiedad es crítica 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 del código en serie, llamadas construcciones universales . Sin embargo, el rendimiento resultante en general no coincide ni siquiera con 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 libres de hambre 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 subproceso en la memoria compartida no se considera demasiado costoso para los sistemas prácticos (normalmente la cantidad de almacenar lógicamente requerido 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 físicamente requerido [ cita necesaria ] es mayor).
Los algoritmos sin espera eran raros 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 candados de Michael y Scott, [19], que es una cola eficiente que se utiliza 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 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 hay implementaciones sin espera disponibles para muchas estructuras de datos.
Bajo suposiciones razonables, Alistarh, Censor-Hillel y Shavit demostraron que los algoritmos sin bloqueo prácticamente no requieren espera. [22] Por lo tanto, la complejidad algorítmica adicional de un algoritmo sin espera podría no valer la pena, si no hay plazos estrictos que cumplir.
La libertad de bloqueo permite que los subprocesos individuales mueran de hambre, 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 progresa (para alguna definición sensata de progreso). Todos los algoritmos sin espera están libres de bloqueos.
En particular, si se suspende un subproceso, un algoritmo sin bloqueo garantiza que los subprocesos restantes aún puedan progresar. Por lo tanto, si dos subprocesos pueden competir por el mismo bloqueo mutex o bloqueo giratorio, entonces el algoritmo no está libre de bloqueos. (Si suspendemos un hilo que sostiene el candado, entonces el segundo hilo se bloqueará).
Un algoritmo está libre de bloqueos si la operación infinitamente frecuente de algunos procesadores tiene éxito en un número finito de pasos. Por ejemplo, si N procesadores están intentando ejecutar una operación, algunos de los N procesos lograrán 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 sin espera y sin bloqueo es que se garantiza que la operación sin espera de cada proceso tendrá éxito en un número finito de pasos, independientemente de los otros procesadores.
En general, un algoritmo sin bloqueo se puede ejecutar en cuatro fases: completar la propia operación, ayudar a una operación de obstrucción, abortar una operación de obstrucción y esperar. Completar la propia operación es complicado por la posibilidad de asistencia y aborto simultáneos, pero es invariablemente el camino más rápido hacia su finalización.
La decisión sobre cuándo ayudar, abortar o esperar cuando se encuentra una obstrucción es responsabilidad del administrador de contención . Esto puede ser muy simple (ayudar a 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 bloqueo y, a menudo, muy costosa de ejecutar: no sólo el hilo de asistencia se ralentiza, sino que gracias a la mecánica de la memoria compartida, el hilo que recibe asistencia también se ralentizará. , si todavía está ejecutándose.
La libertad de obstrucciones es la garantía natural de progreso sin bloqueos más débil. Un algoritmo está libre de obstrucciones si, en algún momento, un único subproceso ejecutado de forma aislada (es decir, con todos los subprocesos obstructivos suspendidos) durante un número limitado de pasos completa su operación. [15] Todos los algoritmos sin bloqueo están libres de obstrucciones.
La libertad de obstrucción sólo exige que cualquier operación parcialmente completada pueda abortarse y revertirse los cambios realizados. Eliminar la asistencia simultánea a menudo puede dar como resultado algoritmos mucho más simples y más fáciles de validar. Evitar que el sistema se bloquee continuamente es tarea de un administrador de contención.
Algunos algoritmos sin obstrucciones utilizan un par de "marcadores de coherencia" 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.