Lockless Deque em Win32 C ++

Question

Eu sou muito novo para estruturas de dados Lockless, portanto, para um exercício que eu escrevi (O que eu espero funciona como) um deque lockless limitada (sem redimensionamento ainda, apenas deseja obter os casos base de trabalho). Eu só gostaria de ter alguma confirmação de pessoas que sabem o que estão fazendo para saber se eu tenho a idéia de direito e / ou como eu poderia melhorar esta situação.

class LocklessDeque
{
  public:

    LocklessDeque() : m_empty(false),
                      m_bottom(0),
                      m_top(0) {}


    ~LocklessDeque()
    {
      // Delete remaining tasks
      for( unsigned i = m_top; i < m_bottom; ++i )
        delete m_tasks[i];
    }


    void PushBottom(ITask* task)
    {
      m_tasks[m_bottom] = task;

      InterlockedIncrement(&m_bottom);
    }


    ITask* PopBottom()
    {
      if( m_bottom - m_top > 0 )
      {
        m_empty = false;

        InterlockedDecrement(&m_bottom);

        return m_tasks[m_bottom];
      }

      m_empty = true;

      return NULL;
    }


    ITask* PopTop()
    {
      if( m_bottom - m_top > 0 )
      {
        m_empty = false;

        InterlockedIncrement(&m_top);

        return m_tasks[m_top];
      }

      m_empty = true;

      return NULL;
    }


    bool IsEmpty() const
    {
      return m_empty;
    }

  private:

    ITask* m_tasks[16];

    bool m_empty;

    volatile unsigned m_bottom;
    volatile unsigned m_top;

};

Answer 1

Olhando para esta Eu acho que isso seria um problema:

void PushBottom(ITask* task)
{
  m_tasks[m_bottom] = task;
  InterlockedIncrement(&m_bottom);
}

Se isso for usado em um ambiente multithreaded real Eu acho que você colidem quando definir m_tasks[m_bottom]. Pense o que aconteceria se você tem dois tópicos que tentam fazer isso ao mesmo tempo -. Você não podia ter certeza de que um m_tasks realmente definidos [m_bottom]

Confira este artigo que é uma discussão razoável de uma fila de livre-lock.

Answer 2

O uso dos membros m_bottom e m_top para indexar a matriz é não bem. Você pode usar o valor de retorno de InterlockedXxxx () para obter um índice seguro. Você precisa perder IsEmpty (), ele nunca pode ser precisas em um cenário multi-threading. Mesmo problema com o cheque vazio no PopXxx. Eu não vejo como você poderia fazer esse trabalho sem um mutex.

Answer 3

A chave para fazer coisas quase impossíveis como este é usar InterlockedCompareExchange. (Este é o nome do Win32 usos, mas qualquer plataforma de vários segmentos com capacidade terá um equivalente InterlockedCompareExchange).

A idéia é, você faz uma cópia da estrutura (que deve ser pequeno o suficiente para realizar uma leitura atômica (64 ou se você pode lidar com alguns unportability, 128 bits em x86).

Você fazer outra cópia com a sua actualização proposta, fazer a sua lógica e atualizar a cópia, então você atualizar a estrutura "real" usando InterlockedCompareExchange. O que InterlockedCompareExchange faz é, atomicamente certifique-se o valor ainda é o valor que você começou com antes de sua atualização de estado, e se ainda é que o valor, atomicamente atualiza o valor com o novo estado. Geralmente este é envolto em um loop infinito que continua tentando até que alguém não mudou o valor no meio. Aqui é mais ou menos o padrão:

union State
{
    struct
    {
        short a;
        short b;
    };
    uint32_t volatile rawState;
} state;

void DoSomething()
{
    // Keep looping until nobody else changed it behind our back
    for (;;)
    {
        state origState;
        state newState;

        // It's important that you only read the state once per try
        origState.rawState = state.rawState;
        // This must copy origState, NOT read the state again
        newState.rawState = origState.rawState;

        // Now you can do something impossible to do atomically...
        // This example takes a lot of cycles, there is huge
        // opportunity for another thread to come in and change
        // it during this update
        if (newState.b == 3 || newState.b % 6 != 0)
        {
            newState.a++;
        }

        // Now we atomically update the state,
        // this ONLY changes state.rawState if it's still == origState.rawState
        // In either case, InterlockedCompareExchange returns what value it has now
        if (InterlockedCompareExchange(&state.rawState, newState.rawState,
                origState.rawState) == origState.rawState)
            return;
    }
}

(Por favor, perdoe se o código acima na verdade não compilar - Eu o escrevi em cima da minha cabeça)

Grande. Agora você pode fazer algoritmos Lockless fácil. ERRADO! O problema é que você está severamente limitada na quantidade de dados que você pode atualizar atomicamente.

Alguns algoritmos Lockless usar uma técnica onde "ajuda" threads simultâneos. Por exemplo, digamos que você tem uma lista vinculada que você quer ser capaz de atualizar a partir de múltiplas threads, outros tópicos pode "ajudar" através da realização de atualizações para o "primeiro" e "últimos" ponteiros se eles estão correndo através de e ver que eles são no nó apontado por "última", mas a "próxima" ponteiro no nó não é nulo. Neste exemplo, ao perceber que o "último" ponteiro está errado, eles atualizar o último ponteiro, somente se ele ainda aponta para o nó atual, usando um intertravado troca comparar.

Não cair em uma armadilha onde "spin" ou loop (como um spinlock). Enquanto não há valor em girando brevemente porque você espera o "outro" thread terminar algo - eles não podem. O "outro" thread pode ter sido contexto ligado e não pode estar executando mais. Você está apenas comer tempo de CPU, queimando energia elétrica (matando uma bateria de laptop talvez) girando até que uma condição é verdadeira. No momento em que você começa a rotação, assim como você pode atirar o seu código lockless e escrevê-lo com fechaduras. Bloqueios são melhores do que fiar sem limites.

Apenas para ir de difícil ridículo, considere a bagunça que você pode obter-se em com outras arquiteturas - as coisas são geralmente muito perdoando em x86 / x64, mas quando você entrar em outras arquiteturas "fracamente ordenados", você entrar em território onde acontecem coisas que não fazem sentido - atualizações de memória não vai acontecer no fim do programa, de modo que todo o seu raciocínio mental, sobre o que o outro thread está fazendo sai pela janela. (Mesmo x86 / x64 têm um tipo de memória chamado de "a combinação de escrita", que é muitas vezes usado quando a memória de vídeo atualizar, mas pode ser usado para qualquer hardware buffer de memória, onde você precisa de cercas) Essas arquiteturas exigem o uso de operações de "cerca de memória" para garantir que todas as leituras escritas / / antes da cerca será globalmente visível (por outros núcleos). Uma cerca de gravação garante que quaisquer gravações antes da cerca será globalmente visível antes de quaisquer gravações depois da cerca. Uma cerca de leitura irá garantir que não lê depois que o muro vai ser especulativamente executado antes da cerca. Uma cerca de leitura / escrita (aka cerca completo ou cerca de memória) fará com que ambas as garantias. Cercas são muito caros. (Alguns usam o termo "barreira" em vez de "cerca")

A minha sugestão é para implementá-lo primeiro com variáveis ??fechaduras / condição. Se você tiver qualquer problema com a obtenção de que trabalhar perfeitamente, é inútil tentar fazer uma implementação lockless. E sempre medir, medir, medir. Você provavelmente vai encontrar o desempenho da implementação usando bloqueios é perfeitamente bem - sem a incertainty de alguma implementação lockless escamosa com um natsy pendurar bug que só vai aparecer quando você'Está fazendo uma demo para um cliente importante. Talvez você possa corrigir o problema redefinindo o problema original em algo mais facilmente resolvido, talvez pela reestruturação do trabalho para itens maiores (ou lotes de itens) estão indo para a coleção, o que reduz a pressão sobre a coisa toda.

Escrita lockless algoritmos simultâneos é muito difícil (como você viu escrito 1000x em outros lugares tenho certeza). É muitas vezes não vale o esforço também.

Answer 4

abordar o problema apontado por Aaron, eu faria algo como:

void PushBottom(ITask *task) { 
    int pos = InterlockedIncrement(&m_bottom);
    m_tasks[pos] = task;
}

Da mesma forma, a pop:

ITask* PopTop() {
  int pos = InterlockedIncrement(&m_top);
  if (pos == m_bottom) // This is still subject to a race condition.
      return NULL;
  return m_tasks[pos];
}

Eu eliminar tanto m_empty e IsEmpty() do projeto completamente. O resultado retornado por IsEmpty está sujeita a uma condição de corrida, ou seja, no momento em que você olha para esse resultado, ele pode muito bem estar obsoleto (ou seja, o que ele diz sobre a fila pode estar errado no momento em que você olha para o que voltou). Da mesma forma, m_empty oferece nada além de um registro de informação que já está disponível sem ele, uma receita para a produção de dados obsoletos. Usando m_empty não garante ele não pode trabalhar bem, mas aumenta as chances de erros consideravelmente, IMO.

Eu estou supondo que é devido à natureza interina do código, mas agora você também tem alguns problemas sérios com os limites de matriz. Você não está fazendo nada para forçar seus índices de matriz para envolver, então assim que você tentar empurrar a tarefa 17 para a fila, você vai ter um grande problema.

Edit: Gostaria de salientar que a condição de corrida observado no comentário é muito sério - e não é o único também. Embora um pouco melhor do que o original, esta deve não ser confundido com o código que irá funcionar corretamente.

Eu diria que escrever código sem bloqueio correcto é consideravelmente mais difícil do que escrever código correto que usa bloqueios. Eu não sei de ninguém que tenha feito isso sem uma sólida compreensão do código que faz bloqueio uso. Com base no código original, eu diria que seria muito melhor para começar por escrito e código de entendimento para uma fila que faz uso de fechaduras, e somente quando você já usou isso para ganhar uma melhor compreensão das questões envolvidas realmente fazer uma tentativa de código livre-lock.