Curiosamente, eu descobri que muitos programadores acreditam erroneamente que "sem bloqueio" significa simplesmente "programação simultânea sem mutexes". Normalmente, há também um mal-entendido correlacionado de que o objetivo de escrever código sem bloqueio é para melhorar o desempenho simultâneo. Obviamente, a definição correta de bloqueio é realmente sobregarantias de progresso. Um algoritmo sem bloqueio garante que pelo menos um encadeamento possa progredir, independentemente do que os outros encadeamentos estejam fazendo.

Isso significa que um algoritmo sem bloqueio nunca pode ter código em que um segmento depende de outro segmento para prosseguir. Por exemplo, o código sem bloqueio não pode ter uma situação em que o Thread A define um sinalizador e, em seguida, o Thread B continua em loop enquanto aguarda o Thread A desmarcar o sinalizador. Código como esse está basicamente implementando um bloqueio (ou o que eu chamaria de mutex disfarçado).

No entanto, outros casos são mais sutis e, em alguns casos, honestamente, não sei dizer se um algoritmo se qualifica como livre de bloqueios ou não, porque a noção de "progredir" às vezes me parece subjetiva.

Um desses casos está na biblioteca de simultaneidade (bem considerada, afaik),liblfds. Eu estava estudando a implementação de uma fila limitada de múltiplos produtores / vários consumidores no liblfds - a implementação é muito direta, mas não sei dizer se ela deve se qualificar como livre de bloqueios.

O algoritmo relevante está emlfds711_queue_bmm_enqueue.c. O Liblfds usa barreiras atômicas e de memória personalizadas, mas o algoritmo é bastante simples para descrever em um parágrafo.

A fila em si é uma matriz contígua limitada (ringbuffer). Existe um compartilhamentoread_index ewrite_index. Cada slot na fila contém um campo para dados do usuário e umsequence_number valor, que é basicamente como um contador de época. (Isso evita problemas de ABA).

O algoritmo PUSH é o seguinte:

CARREGUE atomicamente owrite_indexTente reservar um slot na fila emwrite_index % queue_size usando um loop CompareAndSwap que tenta definirwrite_index parawrite_index + 1.Se o CompareAndSwap for bem-sucedido, copie os dados do usuário no slot reservado.Por fim, atualize osequence_index no slot, tornando-o igual awrite_index + 1.

O código-fonte real usa atômicas personalizadas e barreiras de memória, portanto, para maior clareza sobre esse algoritmo, traduzi-o brevemente em atômicos C ++ padrão (não testados) para melhor legibilidade, como a seguir:

bool mcmp_queue::enqueue(void* data)
{
    int write_index = m_write_index.load(std::memory_order_relaxed);

    for (;;)
    {
        slot& s = m_slots[write_index % m_num_slots];
        int sequence_number = s.sequence_number.load(std::memory_order_acquire);
        int difference = sequence_number - write_index;

        if (difference == 0)
        {
            if (m_write_index.compare_exchange_weak(
                write_index,
                write_index + 1,
                std::memory_order_acq_rel
            ))
            {
                break;
            }
        }

        if (difference < 0) return false; // queue is full
    }

    // Copy user-data and update sequence number
    //
    s.user_data = data;
    s.sequence_number.store(write_index + 1, std::memory_order_release);
    return true;
}

Agora, um encadeamento que deseja colocar um elemento do POP no slot emread_index não poderá fazê-lo até observar que o slot estásequence_number é igual aread_index + 1.

Ok, então não há mutex aqui, e o algoritmo provavelmente funciona bem (é apenas um único CAS para PUSH e POP), mas isso é livre de bloqueios? A razão pela qual não está claro para mim é porque a definição de "progredir" parece obscura quando existe a possibilidade de um PUSH ou POP sempre falhar se a fila estiver cheia ou vazia.

Mas o que é questionável para mim é que o algoritmo PUSH essencialmentereservas um slot, o que significa que o slot nunca pode ser POP até que o encadeamento de envio se atualize para atualizar o número de sequência. Isso significa que um encadeamento POP que deseja exibir um valordepende na rosca PUSH após concluir a operação. Caso contrário, o encadeamento POP sempre retornaráfalse porque acha que a fila está VAZIA. Parece-me discutível se isso realmente se enquadra na definição de "progredir".

Geralmente, algoritmos verdadeiramente sem bloqueio envolvem uma fase em que um encadeamento antecipado realmente tenta ASSISTIR o outro encadeamento na conclusão de uma operação. Portanto, para ser realmente livre de bloqueios, eu pensaria que um encadeamento POP que observa um PUSH em andamento precisaria realmente tentar concluir o PUSH e, somente depois disso, executar a operação POP original. Se o encadeamento POP simplesmente retornar que a fila está VAZIA quando um PUSH estiver em andamento, o encadeamento POP será basicamentebloqueado até que a linha PUSH conclua a operação. Se o encadeamento PUSH morrer, ou for adormecido por 1.000 anos, ou for agendado para o esquecimento, o encadeamento POP não poderá fazer nada, exceto informar continuamente que a fila está VAZIA.

Então, isso se encaixa na definição de livre de bloqueio? De uma perspectiva, você pode argumentar que o encadeamento POP sempre pode progredir, porque sempre pode relatar que a fila está VAZIA (que é pelo menos uma forma de progresso, eu acho.) Mas para mim, isso não está realmente progredindo , já que a única razão pela qual a fila é observada vazia é porque estamosbloqueado por uma operação simultânea PUSH.

Assim,minha pergunta é: esse algoritmo é realmente livre de bloqueios? Ou o sistema de reserva de índices é basicamente um mutex disfarçado?