Linux 3.0:¿Error de interbloqueo de futex-lock?

Question

// SubFetch(x,y) = atomically x-=y and return x (__sync_sub_and_fetch)
// AddFetch(x,y) = atomically x+=y and return x (__sync_add_and_fetch)
// CompareWait(x, y) = futex(&x, FUTEX_WAIT, y) wait on x if x == y
// Wake(x, y) = futex(&x, FUTEX_WAKE, y) wake up y waiters

struct Lock
{
Lock() : x(1) {}

void lock()
{
    while (true)
    {
        if (SubFetch(x, 1) == 0)
            return;

        x = -1;

        CompareWait(x, -1);
    }
}

void unlock()
{
    if (AddFetch(x, 1) == 1)
        return;

    x = 1;

    Wake(x, 1);
}

private:
    int x;
};

Linux 3.0 proporciona una llamada al sistema llamada futex, en el que se basan muchas utilidades de concurrencia, incluidas implementaciones recientes de pthread_mutex.Siempre que escriba código, siempre debe considerar si utilizar una implementación existente o escribirla usted mismo es la mejor opción para su proyecto.

Arriba se muestra una implementación de un bloqueo (mutex, 1 semáforo de conteo de permisos) basado en futex y la descripción semántica en hombre futex(7)

Parece contener un error de interbloqueo por el cual después de que varios subprocesos intentan bloquearlo y desbloquearlo unos miles de veces, los subprocesos pueden entrar en un estado en el que x == -1 y todos los subprocesos se atascan en CompareWait, sin embargo, nadie sostiene el cerrar con llave.

¿Alguien puede ver dónde está el error?

Actualizar: Estoy un poco sorprendido de que futex(7)/semantics esté tan roto.Reescribí completamente Lock de la siguiente manera...¿Es esto correcto ahora?

// CompareAssign(x,y,z) atomically: if (x == y) {x = z; ret true; } else ret false;

struct Lock
{
Lock() : x(0) {}

void lock()
{
    while (!CompareAssign(x, 0, 1))
        if (x == 2 || CompareAssign(x, 1, 2))
            CompareWait(x, 2);
}

void unlock()
{
    if (SubFetch(x, 1) == 0)
        return;

    x = 0;

    Wake(x, 1);
}

private:
int x;
};

La idea aquí es que x tiene los siguientes tres estados:

0: unlocked
1: locked & no waiters
2: locked & waiters

Answer 1

El problema es que asignas explícitamente -1 a x Si el SubFetch no logra adquirir el candado.Esto corre con el desbloqueo.

1. El hilo 1 adquiere el bloqueo. x==0.
2. El hilo 2 intenta adquirir el candado.El SubFetch conjuntos x a -1, y luego se suspende el hilo 2.
3. El hilo 1 libera el bloqueo.El AddFetch conjuntos x a 0, por lo que el código establece explícitamente x al 1 y llama Wake.
4. El hilo 2 se despierta y se establece. x a -1, y luego llama CompareWait.

El hilo 2 ahora está atascado esperando, con x establecido en -1, pero no hay nadie cerca para despertarlo, ya que el hilo 1 ya ha liberado el bloqueo.

Answer 2

La implementación adecuada de un mutex basado en Futex se describe en el papel de Ulrich Drepper "Futexes es complicado"

http://people.redhat.com/drepper/futex.pdf

Incluye no solo el código, sino también una explicación muy detallada de por qué es correcta.El código del documento:

class mutex
{
 public:
 mutex () : val (0) { }
 void lock () {
   int c;
   if ((c = cmpxchg (val, 0, 1)) != 0)
     do {
       if (c == 2 || cmpxchg (val, 1, 2) != 0)
         futex_wait (&val, 2);
     } while ((c = cmpxchg (val, 0, 2)) != 0);
 }
 void unlock () {
//NOTE: atomic_dec returns the value BEFORE the operation, unlike your SubFetch !
   if (atomic_dec (val) != 1) {
     val = 0;
     futex_wake (&val, 1);
   }
 }
 private:
   int val;
};

Comparando el código en el documento con su código, veo una diferencia

tienes

if (x== 2 || ComparaciónSign (X, 1, 2))

Uso del valor de FUTEX directamente, mientras que DreperPE utiliza el valor de retorno de la comparación anterior ().Esa diferencia probablemente afectará el rendimiento solamente.

El código de su desbloqueo también es diferente, pero parece ser semánticamente equivalente.

En cualquier caso, le recomendaría encarecidamente que siga el código de Drepper a la carta.Ese papel ha resistido la prueba del tiempo y recibió mucha revisión por pares.No ganas nada de rodar tu propio.

Answer 3

¿Qué tal este escenario con tres subprocesos, A, B y C?

El estado inicial de este escenario tiene:

• hilo A sujetando la cerradura
• El hilo B aún no compite por el bloqueo.
• hilo C en CompareWait()
• x == -1 desde cuando C no pudo adquirir el bloqueo

        A                  B                C
    ==============   ================  ===============
     AddFetch()
     (so x == 0)
                       SubFetch()
                       (so x == -1)

     x = 1

                       x = -1

     Wake()

En este punto, ya sea que B o C estén desbloqueados, no obtendrán el resultado de 0 Cuando ellos SubFetch().