Es mi implementación bloqueo de giro correcta y óptima?

StackOverflow https://stackoverflow.com/questions/1383363

Pregunta

Estoy usando un bloqueo de bucle para proteger una sección muy pequeña crítica. Contención sucede muy raramente por lo que un bloqueo de bucle 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;
}

Así que me pregunto:

  • ¿Es correcto este código? ¿Garantiza correctamente exclusión mutua?
  • ¿Funciona en todos los sistemas operativos x86?
  • ¿Funciona en x86_64 también? En todos los sistemas operativos?
  • ¿Es óptima?
    • He visto implementaciones bloqueo de bucle utilizando-y-canje de comparar, pero no estoy seguro de que es mejor.
    • De acuerdo con la documentación de órdenes internas atómica 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 las barreras de memoria así que no estoy seguro de si está bien para mí utilizar esto en vez de __sync_synchronize.
    • Estoy optimización para el caso en el que no hay contención.

No me importa en absoluto sobre la contención. Puede haber 1, 2 tal vez otros hilos tratando de bloquear el bloqueo de bucle una vez cada pocos días .

¿Fue útil?

Solución

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 sólo debe contar con la semántica de liberación (por eso tendrá que utilizar __sync_lock_release, por lo que no puedes encontrar en Itanium st1.rel en lugar de mf, o una lwsync en PowerPC, ...). Si realmente sólo se preocupan por x86 o x86_64 los tipos de barreras utilizadas aquí o no, no importa tanto (pero si usted dónde dar el salto a Intel Itanium para un puerto HP-IPF entonces usted no quiere que esto).

  • usted no tiene la instrucción de pausa () que normalmente había puesto antes de su bucle de residuos.

  • cuando hay contención desea algo , la llamada al sistema, o incluso un sueño tonto en la desesperación. Si realmente necesita la actuación que esta compra A continuación, la sugerencia futex es probablemente una buena idea. Si necesita el rendimiento de esta compra que mal lo suficiente para mantener este código tiene una gran cantidad de investigación que debe hacer.

Tenga en cuenta que hubo un comentario diciendo que no era necesaria la barrera de liberación. Eso no es cierto incluso en x86 debido a que la barrera de liberación también sirve como una instrucción para que el compilador no barajar otros accesos a memoria en torno a la "barrera". Muy parecido a lo que se obtendría si se ha utilizado asm ( "" ::: "memoria"). 

* on compare and swap

En la 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 (esp., Si se utiliza un byte para la "palabra de bloqueo" en lugar de un int), pero no menos correcta que si se utiliza BLOQUEO cmpxchg. El uso de comparar y de intercambio puede ser utilizado para algorthims más elegantes (como poner un no-cero puntero a los metadatos para el primer "camarero" en el lockword en caso de fallo).

Otros consejos

se ve bien para mí. Por cierto, aquí está el libro de texto aplicación 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)
            ;
}

En respuesta a sus preguntas:

  1. se ve bien para mí
  2. Suponiendo que el OS 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 se apoyan en una plataforma determinada.
  3. No hay nada específico x86-64 aquí, así que no veo por qué no. Esto puede aplicarse también a cualquier arquitectura que soporta GCC, sin embargo, hay maneras tal vez más óptimas para lograr esto en arquitecturas x86 no.
  4. Usted puede ser un poco mejor con el uso de __sync_lock_release() en el caso unlock(); ya que esto disminuir el bloqueo y añadir una barrera de memoria en una sola operación. Sin embargo, en el supuesto de que su afirmación de que no raras veces será la contención; se ve bien a mí.

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 utilizará las llamadas al sistema, excepto cuando se sostiene el bloqueo

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 pone en duda la cerradura, la espera tiene lugar en el núcleo sin ocupados en espera.

Me pregunto si la siguiente aplicación de la EAP es la correcta en x86_64. Es casi dos veces más rápido en mi i7 portátil 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");
}

No puede hacer comentarios sobre la corrección, pero el título de tu pregunta planteada una señal de alerta antes incluso de leer el cuerpo cuestión. primitivas de sincronización son endiabladamente difícil de garantizar la corrección ... si es posible, es mejor usar una biblioteca bien diseñado / mantenido, tal vez o href="http://www.boost.org/doc/libs/1_40_0/doc/html/thread.html" rel="nofollow noreferrer"> impulso: :. rosca

Una mejora es sugerir está utilizando TATAS (test-y-test -y establecer). Uso de las operaciones CAS se consideran bastante caro para el procesador, por lo que es mejor evitarlos si es posible. Otra cosa, asegúrese de que no va a sufrir de inversión de prioridades (lo que si un hilo de la máxima prioridad intentos para adquirir el bloqueo, mientras que un hilo con tries de baja prioridad para liberar el bloqueo? En Windows, por ejemplo, este problema será resuelto por última instancia por el programador mediante un aumento de prioridad, pero le puede dar explícitamente intervalo de tiempo de su hilo en caso de que no tuvo éxito en la adquisición de la cerradura en la última vez 20 intentos (por ejemplo ..)

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

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. X 86 no hace ningún reordenamiento, excepto que las tiendas son de primera puesta en una memoria intermedia de almacenamiento y así ellos se hace visible puede ser retrasado por otros hilos. Y un hilo que hace una tienda y luego se lee de la misma variable leerá de su memoria intermedia de almacenamiento si aún no se ha limpiado la memoria. Así que todo lo que necesita es una declaración asm para evitar reordenamientos del compilador. Se corre el riesgo de un hilo que mantiene el bloqueo un poco más largo de lo necesario desde la perspectiva de otros hilos, pero si no se preocupan por afirmación de que no debería importar. De hecho, pthread_spin_unlock se implementa como esa en mi sistema (Linux x86_64).

Mi sistema también implementa utilizando pthread_spin_lock lock 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.

Hay algunas suposiciones erróneas.

En primer lugar, SpinLock sólo tiene sentido si ressource está bloqueado en otra CPU. Si ressource está bloqueado en la misma CPU (que es siempre el caso en los sistemas de un solo procesador), que necesita para relajarse planificador en ressource fin de desbloqueo. Usted código actual va a trabajar en el sistema monoprocesador porque programador de tareas cambiará de forma automática, pero es una pérdida de ressource.

El sistema multiprocesador, mismas happends cosa puede, pero tarea puede migrar de una CPU a otra. En resumen, el uso de bloqueo de giro es correcto si garantizamos que sus tareas se pueden ejecutar en diferentes CPU.

En segundo lugar, el bloqueo de un mutex es rápido (tan rápido como spinlock) cuando se está desbloqueado. Mutex de bloqueo (y desbloqueo) es lento (muy lento) sólo si mutex ya está bloqueado.

Así que, en su caso, sugiero a los mutex uso.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top