rotacion - ¿Mi implementación de bloqueo de giro es correcta y óptima?

rotacion de pantalla samsung j7 prime

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 el 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 en x86_64 también? En todos los sistemas operativos?
• ¿Es óptimo?
  • He visto implementaciones de bloqueo de giro utilizando 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 utilizar esto en lugar de __sync_synchronize .
  • Estoy optimizando para el caso en el que no hay contienda.

No me importa para nada la discordia. Puede haber 1, quizás 2 otros hilos tratando de bloquear el bloqueo de giro una vez cada pocos días .

Answer 1

En el caso específico de x86 (32/64), no creo que necesite 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 de asm para evitar reorganizaciones 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 pthread_spin_lock usando lock decl lockvar; jne spinloop; lock decl lockvar; jne spinloop; en lugar de usar xchg (que es lo que usa __sync_lock_test_and_set ), pero no sé si realmente hay una diferencia de rendimiento.

Answer 2

En respuesta a sus preguntas:

1. Me parece bien
2. Suponiendo que el sistema operativo admite 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 GCC admita, 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 de 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

Entonces me pregunto:

* Is it correct?

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

* Is it optimal?

Esa es una pregunta cargada. Al reinventar la rueda también está reinventando muchos problemas que han sido resueltos por otras implementaciones

• Esperaría un bucle inútil 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, para que pueda obtener 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 hay una disputa de que quieres 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 le compra lo suficientemente mal como para mantener este código, tiene mucho 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 x86, sync_lock_test_and_set se correlacionará con 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 4

Hay algunas suposiciones equivocadas.

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, bloquear 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 tu caso, sugiero usar mutexes.

Answer 5

Luce bien para mi. Por cierto, aquí está la implementación del textbook que es más eficiente incluso en el caso contencioso.

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

Answer 6

Me pregunto si la siguiente implementación CAS es la correcta en x86_64. Es casi dos veces más rápido en mi laptop 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 7

No puedo comentar sobre la corrección, pero el título de su pregunta levantó una bandera roja antes de que siquiera leí el cuerpo de la pregunta. Las primitivas de sincronización son diabólicamente difíciles de asegurar la corrección ... si es posible, es mejor que uses una biblioteca bien diseñada / mantenida, quizás pthreads o boost::thread .

Answer 8

Si tiene una versión reciente de Linux, puede usar un futex , un "mutex de espacio de usuario rápido":

Un bloqueo basado en Futex correctamente programado no usará las llamadas al sistema, excepto cuando se contemple el bloqueo

En el caso no disputado, con el que intenta optimizar con su spinlock, el futex se comportará como un spinlock, sin requerir un syscall de kernel. Si se disputa el bloqueo, la espera se lleva a cabo en el kernel sin estar ocupado esperando.

Answer 9

Su procedimiento de desbloqueo no necesita la barrera de memoria; la asignación a la exclusión es atómica siempre que esté dword alineado en el x86.

Answer 10

Una mejora es sugerir el uso de TATAS (test-and-test-and-set). 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 será finalmente resuelto por el programador usa 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 ...)