En ingeniería de software , un spinlock es un bloqueo que hace que un hilo que intenta adquirirlo simplemente espere en un bucle ("gire") mientras verifica repetidamente si el bloqueo está disponible. Dado que el hilo permanece activo pero no está realizando una tarea útil, el uso de dicho bloqueo es una especie de espera activa . Una vez adquiridos, los spinlocks generalmente se mantendrán hasta que se liberen explícitamente, aunque en algunas implementaciones pueden liberarse automáticamente si el hilo en espera (el que mantiene el bloqueo) se bloquea o "se duerme".
Debido a que evitan la sobrecarga de la reprogramación de procesos del sistema operativo o el cambio de contexto , los spinlocks son eficientes si es probable que los subprocesos se bloqueen solo por períodos cortos. Por esta razón, los núcleos de los sistemas operativos a menudo usan spinlocks. Sin embargo, los spinlocks se vuelven inútiles si se mantienen durante períodos más largos, ya que pueden evitar que otros subprocesos se ejecuten y requieran una reprogramación. Cuanto más tiempo mantenga un subproceso un bloqueo, mayor será el riesgo de que el programador del sistema operativo lo interrumpa mientras mantiene el bloqueo. Si esto sucede, otros subprocesos quedarán "girando" (intentando repetidamente adquirir el bloqueo), mientras que el subproceso que mantiene el bloqueo no avanza hacia su liberación. El resultado es un aplazamiento indefinido hasta que el subproceso que mantiene el bloqueo pueda terminar y liberarlo. Esto es especialmente cierto en un sistema de un solo procesador, donde cada subproceso en espera de la misma prioridad probablemente desperdicie su quantum (tiempo asignado en el que un subproceso puede ejecutarse) girando hasta que el subproceso que mantiene el bloqueo finalmente termine.
Implementar spinlocks correctamente es un desafío porque los programadores deben tener en cuenta la posibilidad de acceso simultáneo al bloqueo, lo que podría causar condiciones de carrera . Generalmente, tal implementación es posible solo con instrucciones especiales en lenguaje ensamblador , como operaciones atómicas (es decir, ininterrumpibles) de prueba y configuración y no se puede implementar fácilmente en lenguajes de programación que no admitan operaciones verdaderamente atómicas. [1] En arquitecturas sin tales operaciones, o si se requiere una implementación de lenguaje de alto nivel, se puede usar un algoritmo de bloqueo no atómico, por ejemplo, el algoritmo de Peterson . Sin embargo, tal implementación puede requerir más memoria que un spinlock, ser más lenta para permitir el progreso después del desbloqueo y puede no ser implementable en un lenguaje de alto nivel si se permite la ejecución fuera de orden .
El siguiente ejemplo utiliza lenguaje ensamblador x86 para implementar un spinlock. Funcionará en cualquier procesador compatible con Intel 80386 .
; Sintaxis Intelbloqueado: ; La variable de bloqueo. 1 = bloqueado, 0 = desbloqueado. dd 0 spin_lock: mov eax , 1 ; Establece el registro EAX en 1. xchg eax , [ locked ] ; Intercambia atómicamente el registro EAX con la variable de bloqueo. Esto siempre almacenará 1 en el bloqueo, dejando el valor anterior en el registro EAX. test eax , eax ; Prueba EAX consigo mismo. Entre otras cosas, esto establecerá el indicador cero del procesador si EAX es 0. Si EAX es 0, entonces el bloqueo se desbloqueó y simplemente lo bloqueamos. De lo contrario, EAX es 1 y no adquirimos el bloqueo. jnz spin_lock ; Regresa a la instrucción MOV si el indicador cero no está establecido; el bloqueo se bloqueó anteriormente y, por lo tanto , necesitamos girar hasta que se desbloquee. ret ; Se adquirió el bloqueo, regresa a la función que lo llamó. spin_unlock: xor eax , eax ; Establece el registro EAX en 0. xchg eax , [ bloqueado ] ; Intercambia atómicamente el registro EAX con la variable de bloqueo. ret ; El bloqueo ha sido liberado. La sencilla implementación anterior funciona en todas las CPU que utilizan la arquitectura x86. Sin embargo, es posible realizar varias optimizaciones de rendimiento:
En implementaciones posteriores de la arquitectura x86, spin_unlock puede usar de manera segura un MOV desbloqueado en lugar del XCHG bloqueado más lento. Esto se debe a reglas sutiles de ordenamiento de memoria que lo admiten, aunque MOV no es una barrera de memoria completa . Sin embargo, algunos procesadores (algunos procesadores Cyrix , algunas revisiones del Intel Pentium Pro (debido a errores) y sistemas Pentium e i486 SMP anteriores ) harán lo incorrecto y los datos protegidos por el bloqueo podrían corromperse. En la mayoría de las arquitecturas que no son x86, se deben usar instrucciones explícitas de barrera de memoria o atómicas (como en el ejemplo). En algunos sistemas, como IA-64 , hay instrucciones especiales de "desbloqueo" que proporcionan el ordenamiento de memoria necesario.
Para reducir el tráfico de bus entre CPU , el código que intenta adquirir un bloqueo debe realizar un bucle de lectura sin intentar escribir nada hasta que lea un valor modificado. Debido a los protocolos de almacenamiento en caché MESI , esto hace que la línea de caché para el bloqueo se vuelva "compartida"; luego, notablemente, no hay tráfico de bus mientras una CPU espera el bloqueo. Esta optimización es efectiva en todas las arquitecturas de CPU que tienen una caché por CPU, porque MESI está muy extendido. En las CPU con Hyper-Threading, hacer una pausa con rep nopbrinda un rendimiento adicional al indicarle al núcleo que puede trabajar en el otro hilo mientras el bloqueo gira esperando. [2]
Las extensiones de sincronización transaccional y otros conjuntos de instrucciones de memoria transaccional de hardware sirven para reemplazar los bloqueos en la mayoría de los casos. Aunque los bloqueos aún son necesarios como una alternativa, tienen el potencial de mejorar en gran medida el rendimiento al hacer que el procesador maneje bloques enteros de operaciones atómicas. Esta característica está incorporada en algunas implementaciones de mutex, por ejemplo en glibc . La elisión de bloqueo de hardware (HLE) en x86 es una versión debilitada pero compatible con versiones anteriores de TSE, y podemos usarla aquí para bloquear sin perder ninguna compatibilidad. En este caso particular, el procesador puede elegir no bloquear hasta que dos subprocesos entren en conflicto entre sí. [3]
Una versión más simple de la prueba puede utilizar la cmpxchginstrucción en x86 o la __sync_bool_compare_and_swapincorporada en muchos compiladores de Unix.
Con las optimizaciones aplicadas, un ejemplo se vería así:
; En C: while (!__sync_bool_compare_and_swap(&locked, 0, 1)) while (locked) __builtin_ia32_pause(); spin_lock: mov ecx , 1 ; Establece el registro ECX en 1. retry: xor eax , eax ; Poner a cero EAX, porque cmpxchg compara con EAX. XACQUIRE lock cmpxchg [ locked ], ecx ; decide atómicamente: si bloqueado es cero, escribe ECX en él. ; XACQUIRE le indica al procesador que estamos adquiriendo un bloqueo. je out ; Si lo bloqueamos (valor anterior igual a EAX: 0), regresa. pause: mov eax , [ locked ] ; Lee bloqueado en EAX. test eax , eax ; Realiza la prueba de cero como antes. jz retry ; Si es cero, podemos volver a intentarlo. rep nop ; Indicarle a la CPU que estamos esperando en un bucle de giro, para que pueda trabajar en el otro hilo ahora. También se escribe como "pausa". jmp pause ; Continúa con la pausa de verificación. out: ret ; Listo. spin_unlock: XRELEASE mov [ bloqueado ], 0 ; Suponiendo que se aplican las reglas de ordenamiento de memoria, libere la variable de bloqueo con una sugerencia de "liberación de bloqueo". ret ; El bloqueo ha sido liberado. En cualquier sistema multiprocesador que utilice el protocolo de contención MESI , este tipo de bloqueo de prueba y prueba y configuración (TTAS) funciona mucho mejor que el enfoque simple de bloqueo de prueba y configuración (TAS). [4]
Con una gran cantidad de procesadores, agregar un retraso de retroceso exponencial aleatorio antes de volver a verificar el bloqueo funciona incluso mejor que TTAS. [4] [5]
Algunos procesadores multinúcleo tienen una instrucción de "bloqueo de giro consciente del consumo de energía" que pone al procesador en reposo y luego lo reactiva en el siguiente ciclo después de que se libera el bloqueo. Un bloqueo de giro que utiliza tales instrucciones es más eficiente y consume menos energía que los bloqueos de giro con o sin un bucle de retroceso. [6]
La principal desventaja de un spinlock es que, mientras se espera para adquirir un bloqueo, se pierde tiempo que podría emplearse de forma productiva en otras cosas. Hay dos formas de evitarlo:
La mayoría de los sistemas operativos (incluidos Solaris , Mac OS X y FreeBSD ) utilizan un enfoque híbrido llamado " mutex adaptativo ". La idea es utilizar un bloqueo de giro cuando se intenta acceder a un recurso bloqueado por un hilo que se está ejecutando en ese momento, pero ponerlo en suspensión si el hilo no se está ejecutando en ese momento. (Esto último siempre es el caso en sistemas de un solo procesador). [8]
OpenBSD intentó reemplazar los spinlocks con bloqueos de tickets que reforzaban el comportamiento de primero en entrar, primero en salir , sin embargo esto resultó en un mayor uso de CPU en el núcleo y aplicaciones más grandes, como Firefox , se volvieron mucho más lentas. [9] [10]