En informática , un algoritmo se denomina no 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 que esperar 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 usaba 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", consulte la red Clos . Además, si la central telefónica "no está defectuosa, siempre puede realizar la conexión", ver interruptor de expansión mínima sin bloqueo .
Motivación
El enfoque tradicional de la programación de subprocesos múltiples es utilizar bloqueos para sincronizar el acceso a los recursos compartidos . Las primitivas de sincronización como mutex , semáforos y secciones críticas son todos mecanismos mediante los cuales un programador puede asegurarse de que ciertas secciones de código no se ejecuten al mismo tiempo, si hacerlo corrompería las estructuras de memoria compartida. Si un subproceso intenta adquirir un bloqueo que ya está retenido por otro subproceso, el subproceso se bloqueará hasta que el bloqueo 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 altamente indeseable detener su progreso.
Otros problemas son menos obvios. Por ejemplo, ciertas interacciones entre bloqueos pueden dar lugar a condiciones de error como interbloqueo , bloqueo activo e inversión de prioridad . El uso de cerraduras 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 no bloqueantes no sufren de estos inconvenientes, y, además, son seguros para su uso en el manejador de interrupciones : a pesar de que la REEMPLAZARON hilo no se puede reanudar, el progreso sigue siendo posible sin él. En contraste, las estructuras de datos globales protegidas por exclusión mutua no pueden ser accedidas de manera segura en un manejador de interrupciones, ya que el subproceso sustituido 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 bloqueo 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 de varios núcleos , porque el acceso a la estructura de datos compartidos no necesita serializarse para mantener la coherencia. [4]
Implementación
Con pocas excepciones, los algoritmos sin bloqueo utilizan primitivas atómicas de lectura-modificación-escritura que debe proporcionar el hardware, 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 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 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 a los programas intercambiar 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:
- a-solo escritor de un solo lector de anillo tampón FIFO , con un tamaño que divide de manera uniforme el desbordamiento de uno de los tipos de enteros sin signo disponibles, de manera incondicional puede ser implementado de forma segura utilizando sólo una barrera de memoria
- Leer-copiar-actualizar con un solo escritor y cualquier número de lectores. (Los lectores no tienen que esperar; el escritor normalmente no tiene bloqueos, hasta que necesita recuperar memoria).
- Leer-copiar-actualizar con varios escritores y cualquier número de lectores. (Los lectores no tienen que esperar; varios escritores generalmente se serializan con un candado 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]
Libertad de espera
La libertad de espera es la garantía de progreso sin bloqueos más sólida , que combina el rendimiento garantizado en todo el sistema con la libertad por inanición . Un algoritmo está libre de espera si cada operación tiene un límite en el número de pasos que tomará el algoritmo antes de que se complete la operación. [14] 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.
Se demostró en la década de 1980 [15] que todos los algoritmos se pueden implementar sin esperar, y se han demostrado muchas transformaciones del código serial, llamadas construcciones universales . Sin embargo, el rendimiento resultante no coincide en general ni siquiera con los diseños de bloqueo ingenuos. Desde entonces, varios papeles 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 esperas. Por ejemplo, se ha demostrado [16] 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 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 almacenar lógicamente requerido es una palabra, pero las operaciones CAS físicamente en la misma línea de caché colisionarán, y las operaciones LL / SC en el mismo gránulo de reserva exclusiva colisionarán, por lo que la cantidad de tienda requerida físicamente [ cita requerida ] es mayor).
Los algoritmos sin esperas eran raros hasta 2011, tanto en la investigación como en la práctica. Sin embargo, en 2011 Kogan y Petrank [17] presentaron una construcción de colas sin espera en la primitiva CAS , generalmente disponible en hardware común. Su construcción amplió la cola sin candados de Michael y Scott, [18] que es una cola eficiente que se usa a menudo en la práctica. Un documento de seguimiento de Kogan y Petrank [19] proporcionó un método para hacer que los algoritmos sin esperas sean rápidos y utilizó este método para hacer que la cola sin esperas sea prácticamente tan rápida como su contraparte sin bloqueos. Un artículo posterior de Timnat y Petrank [20] proporcionó un mecanismo automático para generar estructuras de datos sin espera a partir de estructuras sin bloqueo. Por lo tanto, las implementaciones sin esperas ahora están disponibles para muchas estructuras de datos.
Libertad de bloqueo
La libertad de bloqueo permite que los subprocesos individuales se 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 avanza (para una definición sensata de progreso). Todos los algoritmos sin espera están libres de bloqueos.
En particular, si se suspende un subproceso, entonces 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 de mutex o bloqueo de giro, entonces el algoritmo no está libre de bloqueos. (Si suspendemos un hilo que mantiene el bloqueo, el segundo hilo se bloqueará).
Un algoritmo está libre de bloqueos si, con mucha frecuencia, la operación 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 pueden fallar y reintentar 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 puede ejecutarse 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 simultánea y aborto, pero es invariablemente el camino más rápido para completarla.
La decisión sobre cuándo ayudar, abortar o esperar cuando se cumple una obstrucción es responsabilidad de un gerente de contención . Esto puede ser muy simple (ayudar a las operaciones de mayor prioridad, cancelar 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 subproceso de asistencia, sino que, gracias a la mecánica de la memoria compartida, también se ralentiza el subproceso asistido. , si todavía se está ejecutando.
Libertad de obstrucción
La libertad de obstrucción es la garantía de progreso natural sin bloqueo más débil. Un algoritmo está libre de obstrucciones si en cualquier punto, un solo hilo ejecutado de forma aislada (es decir, con todos los hilos obstructores suspendidos) para un número limitado de pasos completará su operación. [14] Todos los algoritmos sin bloqueo están libres de obstrucciones.
La libertad de obstrucción exige solo que se pueda abortar cualquier operación parcialmente completada y deshacer los cambios realizados. La eliminación de la asistencia simultánea a menudo puede resultar en algoritmos mucho más simples que son más 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 coherencia" en la estructura de datos. Los procesos que leen la estructura de datos primero leen un marcador de coherencia, 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.
Ver también
- Punto muerto
- Java ConcurrentMap # Atomicidad sin bloqueo
- Vivacidad
- Lock (ingeniería de software)
- Exclusión mutua
- Inversión de prioridad
- Hambre de recursos
Referencias
- ^ Göetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). Simultaneidad de Java en la práctica . Upper Saddle River, Nueva Jersey: Addison-Wesley. pag. 41 . ISBN 9780321349606.
- ^ Herlihy, M .; Luchangco, V .; Moir, M. (2003). Sincronización sin obstáculos: ejemplo de colas de doble final (PDF) . XXIII Congreso Internacional de Sistemas de Computación Distribuida . pag. 522.
- ^ Butler W. Lampson ; David D. Redell (febrero de 1980). "Experiencia con Procesos y Monitores en Mesa" . Comunicaciones de la ACM . 23 (2): 105-117. CiteSeerX 10.1.1.142.5765 . doi : 10.1145 / 358818.358824 .
- ^ Guillaume Marçais y Carl Kingsford. "Un enfoque rápido y sin bloqueos para el conteo paralelo eficiente de ocurrencias de k-mers" . Bioinformática (2011) 27 (6): 764-770. doi : 10.1093 / bioinformatics / btr011 " Contador de mercurio de medusas" .
- ^ Harris, Tim; Fraser, Keir (26 de noviembre de 2003). "Soporte de idiomas para transacciones ligeras" (PDF) . Avisos ACM SIGPLAN . 38 (11): 388. CiteSeerX 10.1.1.58.8466 . doi : 10.1145 / 949343.949340 .
- ^ Harris, Tim; Marlow, S .; Peyton-Jones, S .; Herlihy, M. (15 a 17 de junio de 2005). "Transacciones de memoria componible". Actas del Simposio ACM SIGPLAN de 2005 sobre los principios y la práctica de la programación paralela, PPoPP '05: Chicago, Illinois . Nueva York, NY: ACM Press. págs. 48–60. doi : 10.1145 / 1065944.1065952 . ISBN 978-1-59593-080-4.
- ^ libcds : biblioteca C ++ de contenedores sin bloqueo y esquema de recuperación de memoria segura
- ^ liblfds : una biblioteca de estructuras de datos sin bloqueo, escrita en C
- ^ Kit de simultaneidad : biblioteca de CA para el diseño y la implementación de sistemas sin bloqueo
- ^ Herb Sutter. "Código sin bloqueo: una falsa sensación de seguridad" . Archivado desde el original el 1 de septiembre de 2015.
- ^ Herb Sutter. "Escribir código sin bloqueo: una cola corregida" . Archivado desde el original el 5 de diciembre de 2008.
- ^ Herb Sutter. "Escribir una cola concurrente generalizada" .
- ^ Herb Sutter. "El problema con las cerraduras" .
- ^ a b Anthony Williams. "Safety: off: Cómo no pegarse un tiro en el pie con atomics C ++" . 2015. p. 20.
- ^ Herlihy, Maurice P. (1988). Resultados de imposibilidad y universalidad para la sincronización sin esperas . Proc. Séptimo Simposio Anual de ACM. sobre Principios de Computación Distribuida. págs. 276–290. doi : 10.1145 / 62546.62593 . ISBN 0-89791-277-2.
- ^ Fich, Faith ; Hendler, Danny; Shavit, Nir (2004). Sobre la debilidad inherente de las primitivas de sincronización condicional . Proc. 23º Simposio Anual de ACM sobre Principios de Computación Distribuida (PODC). págs. 80–87. doi : 10.1145 / 1011767.1011780 . ISBN 1-58113-802-4.
- ^ Kogan, Alex; Petrank, Erez (2011). Colas sin espera con múltiples enqueuers y dequeuers (PDF) . Proc. 16º ACM SIGPLAN Symp. sobre Principios y Práctica de la Programación Paralela (PPOPP). págs. 223-234. doi : 10.1145 / 1941553.1941585 . ISBN 978-1-4503-0119-0.
- ^ Michael, Maged; Scott, Michael (1996). Algoritmos de cola simultánea de bloqueo y no bloqueo simples, rápidos y prácticos . Proc. 15º Anual ACM Symp. sobre Principios de Computación Distribuida (PODC). págs. 267-275. doi : 10.1145 / 248052.248106 . ISBN 0-89791-800-2.
- ^ Kogan, Alex; Petrank, Erez (2012). Un método para crear estructuras de datos rápidas y sin esperas . Proc. 17º ACM SIGPLAN Symp. sobre Principios y Práctica de la Programación Paralela (PPOPP). págs. 141–150. doi : 10.1145 / 2145816.2145835 . ISBN 978-1-4503-1160-1.
- ^ Timnat, Shahar; Petrank, Erez (2014). Una práctica simulación sin espera para estructuras de datos sin bloqueo . Proc. 17º ACM SIGPLAN Symp. sobre Principios y Práctica de la Programación Paralela (PPOPP). págs. 357–368. doi : 10.1145 / 2692916.2555261 . ISBN 978-1-4503-2656-8.
enlaces externos
- Introducción a la programación sin bloqueo
- Algoritmos sin bloqueo