La sincronización sin bloqueo es un enfoque en la programación paralela en sistemas multiprocesador simétricos que rompe con las primitivas de bloqueo tradicionales como semáforos , mutexes y eventos . El acceso compartido entre subprocesos se produce a expensas de operaciones atómicas y mecanismos de bloqueo especiales desarrollados para una tarea específica.
La ventaja de los algoritmos sin bloqueo es una mejor escalabilidad en términos de número de procesadores. Además, si el sistema operativo interrumpe uno de los subprocesos con una tarea en segundo plano, el resto hará su trabajo sin tiempo de inactividad, o incluso se hará cargo del trabajo pendiente.
Del más débil al más fuerte:
Sin obstáculos ( ing. Obstrucción libre ) La más débil de las garantías. Un subproceso progresa si no encuentra obstáculos de otros subprocesos. El algoritmo funciona sin obstáculos si un subproceso que se ejecuta en cualquier momento (suponiendo que todos los subprocesos que obstruyen están suspendidos) completa su trabajo en un número determinista de pasos. La sincronización con exclusión mutua ni siquiera cumple con este requisito: si un subproceso se detiene después de adquirir la exclusión mutua, otros subprocesos que necesitan la exclusión mutua estarán inactivos. Sin cerraduras ( ing. lock-free ) Para los algoritmos sin bloqueo, se garantiza el progreso del sistema de al menos un subproceso. Por ejemplo, un subproceso que realiza una operación de " comparación con intercambio " en un bucle teóricamente podría ejecutarse indefinidamente, pero cada iteración significa que algún otro subproceso ha progresado, lo que significa que el sistema en su conjunto está progresando. Sin expectativas ( ing. wait-free ) La mayor garantía de progreso. El algoritmo funciona sin esperas si cada operación se realiza en un cierto número de pasos, independientemente de otros hilos.Al crear aplicaciones de subprocesos múltiples, a menudo es necesario compartir el acceso a un recurso compartido. El enfoque tradicional le permite otorgar acceso secuencial mediante un mecanismo de sincronización, como bloqueos . Las primitivas de sincronización, como mutexes , semáforos y secciones críticas , le permiten escribir un fragmento de código que se garantiza que no se ejecutará simultáneamente cuando se accede desde subprocesos paralelos: el acceso simultáneo a una parte de la memoria compartida puede provocar daños en el contenido. Un intento por parte de uno de los subprocesos de adquirir un bloqueo que ya está en manos de otro subproceso hace que la ejecución del primer subproceso se suspenda hasta que se libera el bloqueo en el segundo subproceso.
El mutex más simple [1] se implementa usando el llamado spinlock 'a - un ciclo vacío con operaciones atómicas. Las primitivas de colas más complejas se realizan con una operación costosa llamada " cambio de contexto " y el mismo spinlock en el núcleo ( KiDispatcherLocken Windows ) que asegura la cola de prioridad . Cuando la carga en las primitivas de sincronización es baja (la interfaz de usuario imprime el progreso general de otro subproceso; un subproceso da tareas para descargar a través de la red, el segundo descarga...), la sobrecarga de bucles y conmutadores vacíos es pequeña.
Si procesan una gran cantidad de datos en un procesador multinúcleo, la interacción entre subprocesos aumenta. Las estructuras de datos ordinarias, como un árbol de búsqueda , solo se pueden cercar con un mutex en su totalidad, y si los subprocesos acceden constantemente, el trabajo se vuelve casi secuencial. Además, una computadora personal ordinaria con un sistema operativo de propósito general realiza otras tareas, por ejemplo, un usuario, que espera la ejecución, abre un navegador , y se le otorga parte del tiempo del procesador, y los hilos computacionales se suspenden en momentos aleatorios. . Los algoritmos de no bloqueo garantizan que dichas paradas de uno de los subprocesos no generarán tiempo de inactividad en los demás. La ausencia de tiempo de inactividad es especialmente importante si uno de los subprocesos está realizando una tarea de alta prioridad o una tarea en tiempo real .
La sincronización sin bloqueo le permite deshacerse por completo de los interbloqueos . Sin embargo, los algoritmos sin bloqueo tienen sus propios errores: bucles ( livelock ) y " carreras ".
Los algoritmos sin bloqueo se basan en operaciones atómicas , por ejemplo, lectura-modificación-escritura y el más importante de ellos es la comparación con el intercambio (CAS). La implementación de una sección crítica generalmente se basa en el uso de una de las primitivas. Hasta hace poco, todas las implementaciones de algoritmos sin bloqueo tenían que realizarse en un nivel de hardware "bajo" para garantizar un rendimiento aceptable. Sin embargo, el desarrollo de mecanismos de memoria transaccional proporciona abstracciones estándar para escribir código eficiente sin bloqueo.
También se han desarrollado estructuras de datos básicas como la pila , la cola , el conjunto y la tabla hash . Tales estructuras hacen posible simplificar el intercambio de datos asíncronos entre subprocesos de programa. Algunas estructuras de datos son bastante simples y se pueden usar sin bloqueos atómicos especiales, por ejemplo: