En ingeniería de software , un bloqueo de giro es un bloqueo que hace que un hilo que intenta adquirirlo simplemente espere en un bucle ("giro") mientras verifica repetidamente si el bloqueo está disponible. Dado que el hilo permanece activo pero no realiza una tarea útil, el uso de dicho bloqueo es una especie de espera ocupada . 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 pone en suspensión".
Debido a que evitan la sobrecarga de la reprogramación del proceso 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 del sistema operativo a menudo usan spinlocks. Sin embargo, los spinlocks se vuelven un desperdicio si se mantienen durante períodos más prolongados, ya que pueden evitar que se ejecuten otros hilos y requieran reprogramación. Cuanto más tiempo mantenga un hilo un bloqueo, mayor será el riesgo de que el programador del sistema operativo interrumpa el hilo mientras mantiene el bloqueo. Si esto sucede, otros hilos se dejarán "girando" (tratando repetidamente de adquirir el bloqueo), mientras que el hilo que sujeta el bloqueo no avanza hacia la liberación. El resultado es un aplazamiento indefinido hasta que el hilo que sujeta el candado pueda terminar y liberarlo. Esto es especialmente cierto en un sistema de un solo procesador, donde es probable que cada subproceso en espera de la misma prioridad desperdicie su quantum (tiempo asignado en el que se puede ejecutar un subproceso) girando hasta que el subproceso que mantiene el bloqueo finalmente finalice.
Implementar bloqueos de giro 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, una implementación de este tipo solo es posible con instrucciones especiales en lenguaje ensamblador, como operaciones atómicas de prueba y configuración , y no se puede implementar fácilmente en lenguajes de programación que no admiten 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, una implementación de este tipo puede requerir más memoria que un spinlock, ser más lenta para permitir el progreso después del desbloqueo y es posible que no se pueda implementar en un lenguaje de alto nivel si se permite la ejecución fuera de orden .
Implementación de ejemplo
El siguiente ejemplo usa 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 0spin_lock: mov eax , 1 ; Establezca el registro EAX en 1. xchg eax , [ bloqueado ] ; Cambie atómicamente el registro EAX con ; la variable de bloqueo. ; Esto siempre almacenará 1 en la cerradura, dejando ; el valor anterior en el registro EAX. prueba eax , eax ; Pruebe EAX consigo mismo. Entre otras cosas, esta voluntad ; establezca el indicador de cero del procesador si EAX es 0 .; Si EAX es 0, entonces el bloqueo se desbloqueó y ; simplemente lo cerramos. ; De lo contrario, EAX es 1 y no adquirimos el bloqueo. jnz sp in_lock ; Vuelva a la instrucción MOV si el indicador de cero es ; no establecido la cerradura estaba previamente bloqueada, y así ; tenemos que girar hasta que se desbloquee. ret ; Se ha adquirido la cerradura, vuelva a la llamada ; función.spin_unlock: xor eax , eax ; Establezca el registro EAX en 0. xchg eax , [ bloqueado ] ; Cambie atómicamente el registro EAX con ; la variable de bloqueo. ret ; Se ha liberado el bloqueo.
Optimizaciones significativas
La implementación simple anterior funciona en todas las CPU que utilizan la arquitectura x86. Sin embargo, es posible realizar una serie de optimizaciones de rendimiento:
En implementaciones posteriores de la arquitectura x86, spin_unlock puede usar de forma segura un MOV desbloqueado en lugar del XCHG bloqueado más lento. Esto se debe a las sutiles reglas de ordenación de la memoria que lo respaldan, 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 anteriores Pentium e i486 SMP ) harán lo incorrecto y los datos protegidos por el candado podrían dañarse. En la mayoría de las arquitecturas que no son x86, se deben utilizar barreras de memoria explícitas o instrucciones atómicas (como en el ejemplo). En algunos sistemas, como IA-64 , hay instrucciones especiales de "desbloqueo" que proporcionan el orden de memoria necesario.
Para reducir el tráfico de bus entre CPU , el código que intenta adquirir un bloqueo debe realizar un ciclo de lectura sin intentar escribir nada hasta que lea un valor modificado. Debido a los protocolos de almacenamiento en caché de MESI , esto hace que la línea de caché del bloqueo se convierta en "Compartida"; entonces, notablemente, no hay tráfico de autobuses mientras una CPU espera el bloqueo. Esta optimización es efectiva en todas las arquitecturas de CPU que tienen un caché por CPU, porque MESI está muy extendido. En las CPU Hyper-Threading, pausar con rep nop
proporciona un rendimiento adicional al insinuar al núcleo que puede funcionar en el otro hilo mientras el bloqueo gira en espera. [2]
Las extensiones de sincronización transaccional y otros conjuntos de instrucciones de memoria transaccional de hardware sirven para reemplazar bloqueos en la mayoría de los casos. Aunque todavía se requieren bloqueos como alternativa, tienen el potencial de mejorar en gran medida el rendimiento al hacer que el procesador maneje bloques completos de operaciones atómicas. Esta característica está incorporada en algunas implementaciones de mutex, por ejemplo en glibc . Hardware Lock Elision (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 optar por no bloquearse hasta que dos subprocesos entren en conflicto entre sí. [3]
Una versión más simple de la prueba puede usar la cmpxchg
instrucción en x86, o la __sync_bool_compare_and_swap
integrada en muchos compiladores de Unix.
Con las optimizaciones aplicadas, una muestra se vería así:
; En C: while (! __ sync_bool_compare_and_swap (& bloqueado, 0, 1)) while (bloqueado) __builtin_ia32_pause (); spin_lock: mov ecx , 1 ; Establezca el registro ECX en 1. reintentar: xor eax , eax ; Ponga a cero EAX, porque cmpxchg se compara con EAX. XACQUIRE lock cmpxchg ecx , [ bloqueado ] ; Decida atómicamente: si bloqueado es cero, escriba ECX en él. ; XACQUIRE le sugiere al procesador que estamos adquiriendo un bloqueo. je a cabo ; Si lo bloqueamos (valor anterior igual a EAX: 0), regrese. pausa: mov eax , [ bloqueado ] ; Leer bloqueado en EAX. prueba eax , eax ; Realice la prueba cero como antes. jz reintentar ; Si es cero, podemos volver a intentarlo. rep nop ; Dígale a la CPU que estamos esperando en un spinloop, para que pueda ; trabajar en el otro hilo ahora. También escrito como "pausa". pausa jmp ; Sigue comprobando y haciendo una pausa. fuera: ret ; Todo listo. spin_unlock: XRELEASE mov [ bloqueado ], 0 ; Suponiendo que se apliquen las reglas de ordenación de la memoria, suelte el ; variable de bloqueo con una sugerencia de "liberación de bloqueo". ret ; Se ha liberado el bloqueo.
Alternativas
La principal desventaja de un candado giratorio es que, mientras espera adquirir un candado, desperdicia tiempo que podría gastarse productivamente en otra parte. Hay dos formas de evitar esto:
- No adquiera el candado. En muchas situaciones, es posible diseñar estructuras de datos que no requieran bloqueo , por ejemplo, utilizando datos por subproceso o por CPU y deshabilitando interrupciones .
- Cambie a un hilo diferente mientras espera. Por lo general, esto implica adjuntar el hilo actual a una cola de hilos que esperan el bloqueo, seguido de cambiar a otro hilo que esté listo para realizar un trabajo útil. Este esquema también tiene la ventaja de que garantiza que la falta de recursos no ocurra siempre que todos los subprocesos abandonen eventualmente los bloqueos que adquieren y se puedan tomar decisiones de programación sobre qué subproceso debe progresar primero. Los spinlocks que nunca implican un cambio, utilizables por sistemas operativos en tiempo real , a veces se denominan spinlocks sin procesar . [4]
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 usar un spinlock cuando se intenta acceder a un recurso bloqueado por un hilo que se está ejecutando actualmente , pero dormir si el hilo no se está ejecutando actualmente. (Este último es siempre el caso de los sistemas de un solo procesador). [5]
OpenBSD intentó reemplazar los bloqueos giratorios con bloqueos de tickets que imponían el comportamiento de primero en entrar, primero en salir , sin embargo, esto resultó en un mayor uso de CPU en el kernel y aplicaciones más grandes, como Firefox , volviéndose mucho más lentas. [6] [7]
Ver también
- Sincronización
- Giro ocupado
- Punto muerto
- Seqlock
- Bloqueo de entradas
Referencias
- ^ Silberschatz, Abraham; Galvin, Peter B. (1994). Conceptos del sistema operativo (Cuarta ed.). Addison-Wesley. págs. 176-179. ISBN 0-201-59292-4.
- ^ "gcc - spinlock x86 usando cmpxchg" . Desbordamiento de pila .
- ^ "Nuevas tecnologías en la arquitectura del brazo" (PDF) .
- ^ Jonathan Corbet (9 de diciembre de 2009). "Nombramiento de Spinlock resuelto" . LWN.net . Consultado el 14 de mayo de 2013 .
- ^ Silberschatz, Abraham; Galvin, Peter B. (1994). Conceptos del sistema operativo (Cuarta ed.). Addison-Wesley. pag. 198. ISBN 0-201-59292-4.
- ^ Ted Unangst (1 de junio de 2013). "src / lib / librthread / rthread.c - Revisión 1.71" .
- ^ Ted Unangst (6 de mayo de 2016). "comentario de tedu sobre bloqueo en WebKit - Langostas" .
enlaces externos
- Documentación de pthread_spin_lock de The Open Group Base Especificaciones Edición 6, IEEE Std 1003.1, Edición 2004
- Variedad de implementaciones de spinlock del kit de simultaneidad
- Artículo " Bloqueos de giro a nivel de usuario: subprocesos, procesos e IPC " por Gert Boddaert
- Ejemplo de bloqueo de giro de artículo en Java
- Documento " El rendimiento de las alternativas de bloqueo de giro para multiprocesadores de memoria compartida " por Thomas E. Anderson
- Documento " Algoritmos para la sincronización escalable en multiprocesadores de memoria compartida " por John M. Mellor-Crummey y Michael L. Scott . Este artículo recibió el Premio Dijkstra de Informática Distribuida 2006 .
- Bloqueo giratorio-espera de Jeffrey Richter
- Referencia de clase de SpinLock de C ++ de Austria
- Acceso variable entrelazado (Windows)
- Sistemas operativos: tres piezas sencillas (capítulo: cerraduras)