¿La implementación de mi bloqueo de giro es correcta y óptima?

Question

Estoy usando un bloqueo de giro para proteger una sección crítica muy pequeña. La contención ocurre muy raramente así que un bloqueo de giro es más apropiado que un mutex regular.

Mi código actual es la siguiente, y asume x86 y GCC:

volatile int exclusion = 0; 

void lock() { 
    while (__sync_lock_test_and_set(&exclusion, 1)) { 
     // Do nothing. This GCC builtin instruction 
     // ensures memory barrier. 
    } 
} 

void unlock() { 
    __sync_synchronize(); // Memory barrier. 
    exclusion = 0; 
} 

Entonces me pregunto:

• Es este código correcto? ¿Asegura correctamente la exclusión mutua?
• ¿Funciona en todos los sistemas operativos x86?
• ¿Funciona también en x86_64? En todos los sistemas operativos?
• ¿Es óptimo?
  • He visto implementaciones de bloqueo de giro usando compare-and-swap, pero no estoy seguro de cuál es mejor.
  • De acuerdo con la documentación de los edificios atómicos de GCC (http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html) también hay __sync_lock_release. No soy un experto en barreras de memoria, así que no estoy seguro de si puedo usar esto en lugar de __sync_synchronize.
  • Estoy optimizando para el caso en el que no hay contención.

no me importa en absoluto sobre la contención. Puede haber 1, tal vez otros 2 hilos que intenten bloquear el bloqueo de giro una vez cada días.

Answer 1

Así que me pregunto:

* Is it correct? 

En el contexto mencionado, yo diría que sí.

* Is it optimal? 

Esa es una pregunta cargada. Por reinventar la rueda también está reinventando una gran cantidad de problemas que han sido resueltos por otras implementaciones

• yo esperaría un bucle de residuos en caso de fallo en el que no está intentando acceder a la palabra de bloqueo.

• El uso de una barrera completa en el desbloqueo solo necesita tener semántica de liberación (es por eso que usaría __sync_lock_release, de modo que obtendría st1.rel en itanium en lugar de mf, o una lwsync en powerpc,. ..). Si realmente solo te importan los x86 o x86_64, los tipos de barreras que se usan aquí o no importan tanto (pero si quieres hacer el salto al itanium de Intel para un puerto HP-IPF, entonces no querrás esto).

• no tiene la instrucción de pausa() que normalmente pondría antes de su ciclo de desecho.

• cuando no hay contienda que desee algo, semop, o incluso un sueño tonto en la desesperación. Si realmente necesita el rendimiento que esto le compra, entonces la sugerencia futex es probablemente una buena. Si necesita el rendimiento que esto le compra lo suficientemente mal como mantener este código que tiene una gran cantidad de investigación que hacer.

Tenga en cuenta que hubo un comentario que decía que la barrera de liberación no era necesaria. Eso no es cierto incluso en x86 porque la barrera de liberación también sirve como una instrucción para el compilador de no mezclar otros accesos de memoria alrededor de la "barrera". Muy parecido a lo que obtendrías si usaras asm ("" ::: "memoria").

* on compare and swap 

En el sync_lock_test_and_set x 86 mapeará a una instrucción xchg que tiene un prefijo de bloqueo implícito. Definitivamente el código generado más compacto (especialmente si usa un byte para la "palabra de bloqueo" en lugar de un int), pero no menos correcto que si usó LOCK CMPXCHG. El uso de compare y swap se puede usar para algoritmos más sofisticados (como poner un puntero distinto de cero en metadatos para el primer "camarero" en la palabra de bloqueo en caso de falla).

Answer 2

En respuesta a sus preguntas:

1. se ve bien para mí
2. Suponiendo que el sistema operativo soporta GCC (y GCC tiene las funciones implementadas); esto debería funcionar en todos los sistemas operativos x86. La documentación de GCC sugiere que se producirá una advertencia si no son compatibles con una plataforma determinada.
3. No hay nada específico x86-64 aquí, así que no veo por qué no. Esto se puede ampliar para cubrir cualquier arquitectura que soporte GCC, sin embargo, hay formas más óptimas de lograr esto en arquitecturas no x86.
4. Es posible que esté un poco mejor con el uso de __sync_lock_release() en el caso unlock(); ya que esto disminuirá el bloqueo y agregará una barrera de memoria en una sola operación. Sin embargo, suponiendo que su afirmación de que raramente habrá disputas; se ve bien para mi.

Answer 3

No puedo hacer ningún comentario sobre la corrección, pero el título de su pregunta levantó una bandera roja incluso antes de leer el cuerpo de la pregunta. Las primitivas de sincronización son endiabladamente difíciles de garantizar la corrección ... si es posible, es mejor que utilices una biblioteca bien diseñada/mantenida, quizás pthreads o boost::thread.

Answer 4

Una mejora es sugerir está utilizando TATAS (prueba y prueba y conjunto). Usar las operaciones CAS se considera bastante caro para el procesador, por lo que es mejor evitarlas si es posible. Otra cosa, asegúrese de que no sufrirá la inversión de prioridad (¿qué pasa si un hilo con una alta prioridad intenta adquirir el bloqueo mientras que un hilo con baja prioridad intenta liberar el bloqueo? En Windows, por ejemplo, este problema finalmente será resuelto por el programador usando un aumento de prioridad, pero puede abandonar explícitamente el intervalo de tiempo de su hilo en caso de que no haya logrado obtener el bloqueo en los últimos 20 intentos (por ejemplo ...)

Answer 5

Me parece bien. , aquí es la implementación textbook que es más eficiente, incluso en el caso de contienda

void lock(volatile int *exclusion) 
{ 
    while (__sync_lock_test_and_set(exclusion, 1)) 
     while (*exclusion) 
      ; 
} 

Answer 6

Su procedimiento de desbloqueo no necesita la barrera de memoria;. la asignación a la exclusión es atómico mientras dword alineado en el x86.

Answer 7

Si estás en una versión reciente de Linux, es posible que pueda utilizar un futex - un "espacio de usuario mutex rápida":

Una cerradura basada en futex adecuadamente programado no va a utilizar las llamadas al sistema excepto cuando el bloqueo se sostiene

En el caso sin oposición, lo que usted está tratando de optimizar para con su spinlock, el futex se comportará como un spinlock, sin necesidad de una llamada al sistema del kernel. Si se disputa el bloqueo, la espera se lleva a cabo en el kernel sin estar ocupado esperando.

Answer 8

Me pregunto si la siguiente implementación CAS es la correcta en x86_64. Es casi dos veces más rápido en mi computadora portátil i7 X920 (fedora 13 x86_64, gcc 4.4.5).

inline void lock(volatile int *locked) { 
    while (__sync_val_compare_and_swap(locked, 0, 1)); 
    asm volatile("lfence" ::: "memory"); 
} 
inline void unlock(volatile int *locked) { 
    *locked=0; 
    asm volatile("sfence" ::: "memory"); 
} 

Answer 9

En el caso específico de x86 (32/64) no creo que necesita una valla de memoria en absoluto en el código de desbloqueo. x86 no realiza ningún reordenamiento, excepto que las tiendas se colocan primero en un almacenamiento intermedio de la tienda y, por lo tanto, se vuelven visibles para otros subprocesos. Y un hilo que hace una tienda y luego lee desde la misma variable leerá desde su búfer de tienda si aún no se ha descargado a la memoria. Entonces, todo lo que necesita es una declaración asm para evitar el reordenamiento del compilador. Usted corre el riesgo de que un hilo sostenga el bloqueo un poco más de lo necesario desde la perspectiva de otros hilos, pero si no le importa la contención, eso no debería importar. De hecho, pthread_spin_unlock se implementa así en mi sistema (linux x86_64).

Mi sistema también implementa utilizando pthread_spin_locklock decl lockvar; jne spinloop; en lugar de utilizar xchg (que es lo __sync_lock_test_and_set usos), pero no sé si hay realmente una diferencia de rendimiento.

Answer 10

Hay algunas suposiciones erróneas.

Primero, SpinLock tiene sentido solo si el recurso está bloqueado en otra CPU. Si el recurso está bloqueado en la misma CPU (que es siempre el caso en sistemas uniprocesador), necesita relajar el programador para desbloquear el recurso. Su código actual funcionará en un sistema uniprocesador porque el planificador cambiará las tareas de forma automática, pero es un desperdicio de recursos.

En el sistema multiprocesador, lo mismo puede suceder, pero la tarea puede migrar de una CPU a otra. En resumen, el uso del bloqueo de giro es correcto si se garantiza que sus tareas se ejecutarán en diferentes CPU.

En segundo lugar, el bloqueo de un mutex IS es rápido (tan rápido como un spinlock) cuando está desbloqueado. El bloqueo de Mutexes (y desbloqueo) es lento (muy lento) solo si mutex ya está bloqueado.

Entonces, en su caso, sugiero usar mutexes.