Spinlock - Spinlock

Na engenharia de software , um spinlock é um bloqueio que faz com que uma thread tentando adquiri-lo simplesmente espere em um loop ("giro") enquanto verifica repetidamente se o bloqueio está disponível. Uma vez que o encadeamento permanece ativo, mas não está realizando uma tarefa útil, o uso de tal bloqueio é uma espécie de espera ocupada . Uma vez adquiridos, os spinlocks normalmente serão mantidos até que sejam explicitamente liberados, embora em algumas implementações eles possam ser liberados automaticamente se a thread em espera (aquela que mantém o bloqueio) bloquear ou "entrar em suspensão".

Como eles evitam sobrecarga de reprogramação de processos do sistema operacional ou troca de contexto , os spinlocks são eficientes se os threads provavelmente ficarão bloqueados apenas por curtos períodos. Por esse motivo, os kernels do sistema operacional costumam usar spinlocks. No entanto, spinlocks tornam-se um desperdício se mantidos por períodos mais longos, pois podem impedir a execução de outros threads e exigir reprogramação. Quanto mais tempo um encadeamento mantém um bloqueio, maior o risco de o encadeamento ser interrompido pelo agendador do sistema operacional enquanto mantém o bloqueio. Se isso acontecer, outros threads ficarão "girando" (tentando repetidamente adquirir o bloqueio), enquanto o thread que está segurando o bloqueio não está progredindo para liberá-lo. O resultado é um adiamento indefinido até que o fio que segura o bloqueio possa terminar e soltá-lo. Isso é especialmente verdadeiro em um sistema de processador único, onde cada thread em espera com a mesma prioridade provavelmente desperdiçará seu quantum (tempo alocado em que um thread pode ser executado) girando até que o thread que mantém o bloqueio seja finalmente concluído.

Implementar os bloqueios giratórios corretamente é desafiador porque os programadores devem levar em consideração a possibilidade de acesso simultâneo ao bloqueio, o que pode causar condições de corrida . Geralmente, tal implementação só é possível com instruções especiais em linguagem assembly , como operações de teste e conjunto atômicas , e não pode ser facilmente implementado em linguagens de programação que não oferecem suporte a operações verdadeiramente atômicas. Em arquiteturas sem tais operações, ou se a implementação de linguagem de alto nível for necessária, um algoritmo de bloqueio não atômico pode ser usado, por exemplo, o algoritmo de Peterson . No entanto, tal implementação pode exigir mais memória do que um spinlock, ser mais lenta para permitir o progresso após o desbloqueio e pode não ser implementável em uma linguagem de alto nível se a execução fora de ordem for permitida.

Implementação de exemplo

O exemplo a seguir usa a linguagem assembly x86 para implementar um spinlock. Ele funcionará em qualquer processador compatível com Intel 80386 . 

; Intel syntax

locked:                      ; The lock variable. 1 = locked, 0 = unlocked.
     dd      0

spin_lock:
     mov     eax, 1          ; Set the EAX register to 1.
     xchg    eax, [locked]   ; Atomically swap the EAX register with
                             ;  the lock variable.
                             ; This will always store 1 to the lock, leaving
                             ;  the previous value in the EAX register.
     test    eax, eax        ; Test EAX with itself. Among other things, this will
                             ;  set the processor's Zero Flag if EAX is 0.
                             ; If EAX is 0, then the lock was unlocked and
                             ;  we just locked it.
                             ; Otherwise, EAX is 1 and we didn't acquire the lock.
     jnz     spin_lock       ; Jump back to the MOV instruction if the Zero Flag is
                             ;  not set; the lock was previously locked, and so
                             ; we need to spin until it becomes unlocked.
     ret                     ; The lock has been acquired, return to the calling
                             ;  function.

spin_unlock:
     xor     eax, eax        ; Set the EAX register to 0.
     xchg    eax, [locked]   ; Atomically swap the EAX register with
                             ;  the lock variable.
     ret                     ; The lock has been released.

Otimizações significativas

A implementação simples acima funciona em todas as CPUs que usam a arquitetura x86. No entanto, várias otimizações de desempenho são possíveis:

Em implementações posteriores da arquitetura x86, spin_unlock pode usar com segurança um MOV desbloqueado em vez do XCHG bloqueado mais lento. Isso se deve a regras sutis de ordenação de memória que oferecem suporte a isso, embora o MOV não seja uma barreira de memória total . No entanto, alguns processadores (alguns processadores Cyrix , algumas revisões do Intel Pentium Pro (devido a bugs) e sistemas Pentium e i486 SMP anteriores ) farão a coisa errada e os dados protegidos pelo bloqueio podem ser corrompidos. Na maioria das arquiteturas não x86, deve-se usar barreira de memória explícita ou instruções atômicas (como no exemplo). Em alguns sistemas, como IA-64 , existem instruções especiais de "desbloqueio" que fornecem a ordenação de memória necessária.

Para reduzir o tráfego de barramento entre CPU , o código que tenta adquirir um bloqueio deve fazer um loop de leitura sem tentar escrever nada até ler um valor alterado. Por causa dos protocolos de cache MESI , isso faz com que a linha de cache para o bloqueio se torne "Compartilhada"; então, notavelmente, não há tráfego de ônibus enquanto a CPU espera pelo bloqueio. Essa otimização é eficaz em todas as arquiteturas de CPU que possuem um cache por CPU, porque o MESI é muito difundido. Em CPUs Hyper-Threading, pausar com rep nopdá desempenho adicional, sugerindo ao núcleo que ele pode funcionar na outra thread enquanto o bloqueio gira em espera.

As extensões de sincronização transacional e outros conjuntos de instruções de memória transacional de hardware servem para substituir os bloqueios na maioria dos casos. Embora os bloqueios ainda sejam necessários como fallback, eles têm o potencial de melhorar muito o desempenho, pois o processador lida com blocos inteiros de operações atômicas. Este recurso está embutido em algumas implementações de mutex, por exemplo em glibc . O Hardware Lock Elision (HLE) no x86 é uma versão enfraquecida, mas compatível com versões anteriores, do TSE, e podemos usá-lo aqui para bloquear sem perder nenhuma compatibilidade. Nesse caso específico, o processador pode optar por não bloquear até que dois threads realmente entrem em conflito um com o outro.

Uma versão mais simples do teste pode usar a cmpxchginstrução em x86 ou __sync_bool_compare_and_swapembutida em muitos compiladores Unix.

Com as otimizações aplicadas, um exemplo ficaria assim: 

; In C: while(!__sync_bool_compare_and_swap(&locked, 0, 1)) while(locked) __builtin_ia32_pause();
spin_lock:
    mov     ecx, 1             ; Set the ECX register to 1.
retry:
    xor     eax, eax           ; Zero out EAX, because cmpxchg compares against EAX.
    XACQUIRE lock cmpxchg [locked], ecx
                               ; atomically decide: if locked is zero, write ECX to it.
                               ;  XACQUIRE hints to the processor that we are acquiring a lock.
    je      out                ; If we locked it (old value equal to EAX: 0), return.
pause:
    mov     eax, [locked]      ; Read locked into EAX.
    test    eax, eax           ; Perform the zero-test as before.
    jz      retry              ; If it's zero, we can retry.
    rep nop                    ; Tell the CPU that we are waiting in a spinloop, so it can
                               ;  work on the other thread now. Also written as the "pause".
    jmp     pause              ; Keep check-pausing.
out:
    ret                        ; All done.

spin_unlock:
    XRELEASE mov [locked], 0   ; Assuming the memory ordering rules apply, release the 
                               ;  lock variable with a "lock release" hint.
    ret                        ; The lock has been released.

Alternativas

A principal desvantagem de um spinlock é que, enquanto espera para adquirir um bloqueio, ele perde tempo que poderia ser gasto produtivamente em outro lugar. Existem duas maneiras de evitar isso:

  1. Não adquira o bloqueio. Em muitas situações, é possível projetar estruturas de dados que não requerem bloqueio , por exemplo, usando dados por thread ou por CPU e desativando interrupções .
  2. Mude para um tópico diferente enquanto espera. Isso normalmente envolve anexar o encadeamento atual a uma fila de encadeamentos aguardando o bloqueio, seguido pela troca para outro encadeamento que está pronto para fazer algum trabalho útil. Esse esquema também tem a vantagem de garantir que a privação de recursos não ocorra, desde que todos os encadeamentos eventualmente abandonem os bloqueios adquiridos e as decisões de agendamento possam ser tomadas sobre qual encadeamento deve progredir primeiro. Spinlocks que nunca envolvem troca, utilizáveis ​​por sistemas operacionais em tempo real , às vezes são chamados de spinlocks brutos .

A maioria dos sistemas operacionais (incluindo Solaris , Mac OS X e FreeBSD ) usa uma abordagem híbrida chamada " mutex adaptativo ". A ideia é usar um spinlock ao tentar acessar um recurso bloqueado por um thread em execução no momento, mas dormir se o thread não estiver em execução. (O último é sempre o caso em sistemas de processador único.)

O OpenBSD tentou substituir spinlocks por tickets locks que impunham o comportamento first-in-first-out , no entanto, isso resultou em mais uso da CPU no kernel e em aplicativos maiores, como o Firefox , tornando-se muito mais lentos.

Veja também

Referências

  1. ^ Silberschatz, Abraham; Galvin, Peter B. (1994). Conceitos do sistema operacional (quarta edição). Addison-Wesley. pp. 176–179. ISBN 0-201-59292-4.
  2. ^ "gcc - x86 spinlock usando cmpxchg" . Stack Overflow .
  3. ^ "Novas tecnologias na arquitetura do braço" (PDF) .
  4. ^ Jonathan Corbet (9 de dezembro de 2009). "Nomenclatura de Spinlock resolvida" . LWN.net . Retirado em 14 de maio de 2013 .
  5. ^ Silberschatz, Abraham; Galvin, Peter B. (1994). Conceitos do sistema operacional (quarta edição). Addison-Wesley. p. 198. ISBN 0-201-59292-4.
  6. ^ Ted Unangst (01/06/2013). "src / lib / librthread / rthread.c - Revisão 1.71" .
  7. ^ Ted Unangst (06/05/2016). "tedu comment on Locking in WebKit - Lobsters" .

links externos