¿Spinlock ligeros construidos a partir de las operaciones atómicas de GCC?

Question

Me gustaría minimizar la sincronización y escribir código bloqueable cuando sea posible en un proyecto mío. Cuando sea absolutamente necesario, me encantaría sustituir las suspensiones de spinlocks livianas construidas a partir de operaciones atómicas por las cerraduras mutex pthread y win32. Según entiendo, se trata de llamadas al sistema que se encuentran debajo y que podrían provocar un cambio de contexto (que puede ser innecesario para secciones críticas muy rápidas en las que sería preferible girar varias veces).

Las operaciones atómicas que me refiero están bien documentados aquí: http://gcc.gnu.org/onlinedocs/gcc-4.4.1/gcc/Atomic-Builtins.html

Aquí se muestra un ejemplo para ilustrar lo que estoy hablando. Imagine un árbol RB con múltiples lectores y escritores posible. RBTree :: exists() es de solo lectura y seguro para subprocesos, RBTree :: insert() requerirá acceso exclusivo de un solo escritor (y ningún lector) para estar seguro. Algunos código:

class IntSetTest 
{ 
private: 
    unsigned short lock; 
    RBTree<int>* myset; 

public: 
    // ... 

    void add_number(int n) 
    { 
     // Aquire once locked==false (atomic) 
     while (__sync_bool_compare_and_swap(&lock, 0, 0xffff) == false); 

     // Perform a thread-unsafe operation on the set 
     myset->insert(n); 

     // Unlock (atomic) 
     __sync_bool_compare_and_swap(&lock, 0xffff, 0); 
    } 

    bool check_number(int n) 
    { 
     // Increment once the lock is below 0xffff 
     u16 savedlock = lock; 
     while (savedlock == 0xffff || __sync_bool_compare_and_swap(&lock, savedlock, savedlock+1) == false) 
      savedlock = lock; 

     // Perform read-only operation  
     bool exists = tree->exists(n); 

     // Decrement 
     savedlock = lock; 
     while (__sync_bool_compare_and_swap(&lock, savedlock, savedlock-1) == false) 
      savedlock = lock; 

     return exists; 
    } 
}; 

(supongamos que no tiene por qué ser una excepción de fallos)

¿Es este código de hecho flujos seguros? ¿Hay algún pros/contras para esta idea? ¿Algún consejo? ¿El uso de spinlocks como este es una mala idea si los hilos no son verdaderamente concurrentes?

Gracias de antemano. ;)

Answer 1

Necesita un calificador volatile en lock, y yo también lo convertiría en sig_atomic_t. Sin la volatile calificador, este código:

u16 savedlock = lock; 
    while (savedlock == 0xffff || __sync_bool_compare_and_swap(&lock, savedlock, savedlock+1) == false) 
     savedlock = lock; 

no puede releer lock al actualizar savedlock en el cuerpo del bucle while. Considere el caso de que lock es 0xffff. Luego, savedlock será 0xffff antes de verificar la condición de bucle, por lo que la condición while se cortocircuitará antes de llamar al __sync_bool_compare_and_swap. Como no se invocó __sync_bool_compare_and_swap, el compilador no encuentra una barrera de memoria, por lo que podría suponer razonablemente que el valor de lock no ha cambiado debajo de usted y evitar volver a cargarlo en savedlock.

Re: sig_atomic_t, hay una discusión decente here. Las mismas consideraciones que se aplican a los manejadores de señal también se aplicarían a los hilos.

Con estos cambios, supongo que su código sería seguro para subprocesos. Aun así, recomendaría usar mutexes, ya que realmente no sabe cuánto tiempo tomará su inserción de RB-tree en el caso general (según mis comentarios anteriores en la pregunta).

Answer 2

Vale la pena señalar que si está utilizando los mutexes de Win32, desde Vista en adelante se le proporciona un grupo de subprocesos. Dependiendo de para qué use el árbol RB, podría reemplazarlo con eso.

Además, lo que debe recordar es que las operaciones atómicas no son particularmente rápidas. Microsoft dijo que eran un par de cientos de ciclos, cada uno.

En lugar de tratar de "proteger" la función de esta manera, probablemente sería mucho más eficiente simplemente sincronizar los hilos, ya sea cambiando a un enfoque SIMD/grupo de hilos, o simplemente usar un mutex.

Pero, por supuesto, sin ver su código, realmente no puedo hacer más comentarios. El problema con el multihilo es que tienes que ver el modelo completo de alguien para entenderlo.