Minha implementação de bloqueio de spin está correta e ideal?

StackOverflow https://stackoverflow.com/questions/1383363

Pergunta

Estou usando um bloqueio de spin para proteger uma seção crítica muito pequena. A contenção acontece muito Raramente, uma trava de spin é mais apropriada do que um mutex regular.

Meu código atual é o seguinte e assume x86 e gcc:

volatile int exclusion = 0;

void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) {
        // Do nothing. This GCC builtin instruction
        // ensures memory barrier.
    }
}

void unlock() {
    __sync_synchronize(); // Memory barrier.
    exclusion = 0;
}

Então estou me perguntando:

  • Este código está correto? Ele garante corretamente a exclusão mútua?
  • Funciona em todos os sistemas operacionais X86?
  • Funciona no x86_64 também? Em todos os sistemas operacionais?
  • É ideal?
    • Vi implementações de bloqueio de spin usando o Compare-and-Swap, mas não tenho certeza de qual é melhor.
    • De acordo com a documentação do GCC Atomic Builtins (http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/atomic-builtins.html) há também __sync_lock_release. Não sou especialista em barreiras de memória, então não tenho certeza se está tudo bem para eu usar isso em vez de __sync_synchronize.
    • Estou otimizando para o caso em que não há disposição.

não me importo de forma alguma sobre contenção. Pode haver 1, talvez 2 outros fios tentando travar o bloqueio de spin uma vez a cada poucos dias.

Foi útil?

Solução

Então estou me perguntando:

* Is it correct?

No contexto mencionado, eu diria que sim.

* Is it optimal?

Essa é uma pergunta carregada. Ao reinventar a roda, você também está reinventando muitos problemas que foram resolvidos por outras implementações

  • Eu esperaria um loop de resíduos no fracasso, onde você não está tentando acessar a palavra de bloqueio.

  • O uso de uma barreira completa no desbloqueio só precisa ter a semântica de liberação (é por isso que você usaria __sync_lock_release, para que você recebesse o ST1.rel no Itanium em vez de MF ou um LWSYC no PowerPC, ...). Se você realmente se preocupa apenas com x86 ou x86_64, os tipos de barreiras usadas aqui ou não não importam tanto (mas se você for onde dar o salto para a Intel's Itanium para uma porta HP-IPF, não gostaria disso).

  • Você não tem a instrução pause () que normalmente colocaria antes do seu loop de resíduos.

  • Quando há disputa que você deseja algo, semop, ou mesmo um sono idiota em desespero. Se você realmente precisa do desempenho que isso compra, a sugestão da Futex é provavelmente boa. Se você precisar do desempenho, isso compra você o suficiente para manter Este código que você tem muita pesquisa a fazer.

Observe que houve um comentário dizendo que a barreira de liberação não era necessária. Isso não é verdade mesmo no x86, porque a barreira de liberação também serve como uma instrução ao compilador para não embaralhar outros acessos de memória em torno da "barreira". Muito parecido com o que você conseguiria se usasse ASM ("" ::: "memória").

* on compare and swap

No x86, o sync_lock_test_and_set mapeará para uma instrução XCHG que possui um prefixo de bloqueio implícito. Definitivamente, o código gerado mais compacto (especialmente se você usar um byte para a "palavra de bloqueio" em vez de um int), mas não menos correto do que se você usasse o bloqueio CMPXCHG. O uso de comparar e swap pode ser usado para algorthims mais sofisticados (como colocar um ponteiro diferente de zero em metadados para o primeiro "garçom" na palavra de trava na falha).

Outras dicas

Parece bem para mim. Btw, aqui está o livro didático implementação que é mais eficiente, mesmo no caso disputado.

void lock(volatile int *exclusion)
{
    while (__sync_lock_test_and_set(exclusion, 1))
        while (*exclusion)
            ;
}

Em resposta às suas perguntas:

  1. Parece bom para mim
  2. Assumindo que o sistema operacional suporta o GCC (e o GCC tem as funções implementadas); Isso deve funcionar em todos os sistemas operacionais X86. A documentação do GCC sugere que um aviso será produzido se eles não forem suportados em uma determinada plataforma.
  3. Não há nada específico x86-64 aqui, então não vejo por que não. Isso pode ser expandido para cobrir algum A arquitetura que o GCC suporta, no entanto, talvez existem maneiras mais ideais de conseguir isso em arquiteturas não x86.
  4. Você pode estar um pouco melhor com o uso __sync_lock_release() no unlock() caso; pois isso diminuirá a trava e adicionará uma barreira de memória em uma única operação. No entanto, assumindo que sua afirmação de que raramente haverá contenção; Parece bom para mim.

Se você estiver em uma versão recente do Linux, poderá usar um Futex - Um "Usuários Rápido Space Mutex":

Um bloqueio baseado em Futex corretamente programado não usará chamadas do sistema, exceto quando o bloqueio for contestado

No caso incontestado, que você está tentando otimizar com o seu spinlock, o Futex se comportará como um spinlock, sem exigir um syscall do kernel. Se a fechadura for contestada, a espera ocorre no kernel sem aguardar.

Gostaria de saber se a seguinte implementação do CAS é a correta no x86_64. É quase duas vezes mais rápido no meu laptop i7 x920 (Fedora 13 x86_64, GCC 4.4.5).

inline void lock(volatile int *locked) {
    while (__sync_val_compare_and_swap(locked, 0, 1));
    asm volatile("lfence" ::: "memory");
}
inline void unlock(volatile int *locked) {
    *locked=0;
    asm volatile("sfence" ::: "memory");
}

Não posso comentar sobre a correção, mas o título da sua pergunta levantou uma bandeira vermelha antes mesmo de ler o corpo da pergunta. Os primitivos de sincronização são diabolicamente difíceis de garantir a correção ... se possível, é melhor usar uma biblioteca bem projetada/mantida, talvez pthreads ou Boost :: Thread.

Uma melhoria é sugerida está usando Tatas (teste e teste). O uso das operações do CAS é considerado bastante caro para o processador, por isso é melhor evitá -las, se possível. Outra coisa, verifique se você não sofrerá de inversão prioritária (e se um tópico com uma alta prioridade tentar adquirir a trava, enquanto um tópico com baixa prioridade tentar libertar o bloqueio? No Windows, por exemplo, esse problema será resolvido por resolvido por resolvido por O agendador usando um impulso prioritário, mas você pode desistir explicitamente da fatia de tempo do seu tópico, caso não tenha conseguido adquirir o bloqueio nas últimas 20 tentativas (por exemplo ..)

Seu procedimento de desbloqueio não precisa da barreira da memória; A atribuição à exclusão é atômica, desde que o DWORD alinhado no x86.

No caso específico de x86 (32/64), acho que você não precisa de uma cerca de memória no código de desbloqueio. O X86 não faz nenhuma reordenação, exceto que as lojas são colocadas primeiro em um buffer de loja e, portanto, elas se tornam visíveis podem ser atrasadas para outros threads. E um thread que faz uma loja e depois lê da mesma variável lerá em seu buffer de loja se ainda não tiver sido liberado na memória. Então, tudo que você precisa é um asm declaração para impedir reordenações de compilador. Você corre o risco de um fio que mantém a trava um pouco mais do que o necessário da perspectiva de outros threads, mas se você não se importa com a contenção, isso não deve importar. Na verdade, pthread_spin_unlock é implementado assim no meu sistema (Linux x86_64).

Meu sistema também implementa pthread_spin_lock usando lock decl lockvar; jne spinloop; ao invés de usar xchg (que é o que __sync_lock_test_and_set usa), mas não sei se há realmente uma diferença de desempenho.

Existem algumas suposições erradas.

Primeiro, o spinlock faz sentido apenas se o Ressource estiver bloqueado em outra CPU. Se o Ressource estiver bloqueado na mesma CPU (que sempre é o caso dos sistemas uniprocessadores), você precisa relaxar o agendador para desbloquear o Ressource. Seu código atual funcionará no sistema Uniprocessor, porque o Scheduler mudará de tarefas automaticamente, mas é um desperdício de Ressource.

No sistema multiprocessador, a mesma coisa pode acontecer, mas a tarefa pode migrar de uma CPU para outra. Em suma, o uso do bloqueio de rotação está correto se você garante que suas tarefas serão executadas em diferentes CPU.

Em segundo lugar, travar um mutex é rápido (tão rápido quanto o spinlock) quando é desbloqueado. O bloqueio de mutexes (e desbloqueio) é lento (muito lento) apenas se o mutex já estiver bloqueado.

Então, no seu caso, sugiro usar mutexes.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top