Linux 3.0:Bug de impasse 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 fornece uma chamada de sistema chamada futex, no qual muitos utilitários de simultaneidade são baseados, incluindo implementações recentes de pthread_mutex.Sempre que você escreve código, você deve sempre considerar se usar uma implementação existente ou escrevê-lo você mesmo é a melhor escolha para o seu projeto.

Acima está uma implementação de um Lock (mutex, semáforo de contagem de 1 permissão) baseado em futex e na descrição semântica em homem futex (7)

Parece conter um bug de deadlock em que, depois que vários threads tentam bloqueá-lo e desbloqueá-lo alguns milhares de vezes, os threads podem entrar em um estado em que x == -1 e todos os threads ficam presos no CompareWait, no entanto, ninguém está segurando o trancar.

Alguém pode ver onde está o bug?

Atualizar: Estou um pouco surpreso que futex(7)/semantics esteja tão quebrado.Eu reescrevi Lock completamente da seguinte maneira ...isso está correto agora?

// 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;
};

A ideia aqui é que x tem os três estados a seguir:

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

Answer 1

O problema é que você atribui explicitamente -1 a x se o SubFetch não consegue adquirir o bloqueio.Isso corre com o desbloqueio.

1. Thread 1 adquire o bloqueio. x==0.
2. O thread 2 tenta adquirir o bloqueio.O SubFetch conjuntos x para -1 e o thread 2 será suspenso.
3. O fio 1 libera a trava.O AddFetch conjuntos x como 0, então o código define explicitamente x para 1 e chama Wake.
4. Thread 2 acorda e define x para -1 e então chama CompareWait.

Thread 2 agora está parado esperando, com x definido como -1, mas não há ninguém por perto para ativá-lo, pois o thread 1 já liberou o bloqueio.

Answer 2

A implementação adequada de um Mutex baseado em futex é descrita no artigo de Ulrich Drepper "Futexes are tricky"

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

Inclui não apenas o código, mas também uma explicação muito detalhada de por que está correto.O código do papel:

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 o código no papel com o seu código, vejo uma diferença

Você tem

if (x == 2 || CompareAssign(x, 1, 2))

usando o valor do futex diretamente, enquanto o Drepper usa o valor de retorno do CompareAssign() anterior.Essa diferença provavelmente afetará apenas o desempenho.

Seu código de desbloqueio também é diferente, mas parece ser semanticamente equivalente.

De qualquer forma, eu recomendo fortemente que você siga o código de Drepper ao pé da letra.Esse artigo resistiu ao teste do tempo e recebeu muitas revisões por pares.Você não ganha nada rolando o seu próprio.

Answer 3

Que tal este cenário com três threads, A, B e C.

O estado inicial deste cenário tem:

• fio A segurando a fechadura
• thread B ainda não está disputando o bloqueio
• fio C em CompareWait()
• x == -1 desde quando C não conseguiu adquirir o bloqueio

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

     x = 1

                       x = -1

     Wake()

Neste ponto, quer B ou C estejam desbloqueados, eles não obterão um resultado de 0 quando eles SubFetch().