Spinlock versus Semaphore

Quais são as diferenças básicas entre um semáforo e um spin-lock?

Quando usaríamos um semáforo sobre um spin-lock?

Spinlock e semáforo diferem principalmente em quatro coisas:

1. O que são
Um spinlock é uma implementação possível de um bloqueio, a saber, aquele que é implementado por espera ocupada ("girando"). Um semáforo é a generalização de um bloqueio (ou, ao contrário, um bloqueio é um caso especial de semáforo). Normalmente, mas não necessariamente , spinlocks são válidos apenas dentro de um processo, enquanto os semáforos também podem ser usados ​​para sincronizar entre diferentes processos.

Um bloqueio funciona para exclusão mútua, ou seja, um encadeamento de cada vez pode adquirir o bloqueio e prosseguir com uma "seção crítica" do código. Normalmente, isso significa código que modifica alguns dados compartilhados por vários threads.
Um semáforo tem um contador e se permite ser adquirido por um ou vários threads, dependendo do valor que você postar nele e (em algumas implementações) dependendo de qual é o seu valor máximo permitido.

Na medida em que, pode-se considerar um bloqueio um caso especial de um semáforo com valor máximo de 1.

2. O que eles fazem
Conforme afirmado acima, um spinlock é um mecanismo de bloqueio e, portanto, de exclusão mútua (estritamente 1 para 1). Ele funciona consultando e / ou modificando repetidamente uma localização de memória, geralmente de maneira atômica. Isso significa que adquirir um spinlock é uma operação "ocupada" que possivelmente queima os ciclos da CPU por um longo tempo (talvez para sempre!), Enquanto efetivamente atinge "nada".
O principal incentivo para tal abordagem é o fato de que uma mudança de contexto tem uma sobrecarga equivalente a girar algumas centenas (ou talvez milhares) de vezes, então se um bloqueio pode ser adquirido queimando alguns ciclos girando, isso pode muito bem ser mais eficiente. Além disso, para aplicativos de tempo real, pode não ser aceitável bloquear e esperar que o planejador volte a eles em algum momento distante no futuro.

Um semáforo, por outro lado, ou não gira de todo, ou gira apenas por um período muito curto (como uma otimização para evitar o overhead do syscall). Se um semáforo não puder ser adquirido, ele será bloqueado, cedendo o tempo da CPU para uma thread diferente que está pronta para ser executada. Isso pode significar que alguns milissegundos se passam antes que seu thread seja agendado novamente, mas se isso não for problema (geralmente não é), pode ser uma abordagem muito eficiente e conservadora da CPU.

3. Como eles se comportam na presença de congestionamento
É um equívoco comum que spinlocks ou algoritmos sem bloqueio são "geralmente mais rápidos", ou que eles só são úteis para "tarefas muito curtas" (idealmente, nenhum objeto de sincronização deve ser mantido por mais tempo do que o absolutamente necessário, nunca).
A única diferença importante é como as diferentes abordagens se comportam na presença de congestionamento .

Um sistema bem projetado normalmente tem baixo ou nenhum congestionamento (isso significa que nem todos os threads tentam adquirir o bloqueio ao mesmo tempo). Por exemplo, normalmente não se escreveria um código que adquire um bloqueio, depois carrega meio megabyte de dados compactados zip da rede, decodifica e analisa os dados e, finalmente, modifica uma referência compartilhada (anexar dados a um contêiner, etc.) antes de liberar o bloqueio. Em vez disso, seria adquirido o bloqueio apenas com o propósito de acessar o recurso compartilhado .
Visto que isso significa que há consideravelmente mais trabalho fora da seção crítica do que dentro dela, naturalmente a probabilidade de um fio estar dentro da seção crítica é relativamente baixa e, portanto, poucos fios estão disputando o bloqueio ao mesmo tempo. Claro que de vez em quando dois threads tentarão obter o bloqueio ao mesmo tempo (se isso não pudesse acontecer, você não precisaria de um bloqueio!), Mas isso é mais a exceção do que a regra em um sistema "saudável" .

Nesse caso, um spinlock supera em muito um semáforo porque, se não houver congestionamento de bloqueio, a sobrecarga de adquirir o spinlock é uma mera dúzia de ciclos em comparação com centenas / milhares de ciclos para uma mudança de contexto ou 10-20 milhões de ciclos para perder o restante de uma fração de tempo.

Por outro lado, devido ao alto congestionamento, ou se o bloqueio estiver sendo mantido por longos períodos (às vezes você simplesmente não consegue evitar!), Um spinlock queima uma quantidade insana de ciclos de CPU sem atingir nada.
Um semáforo (ou mutex) é uma escolha muito melhor neste caso, pois permite que um thread diferente execute tarefas úteis durante esse tempo. Ou, se nenhum outro thread tiver algo útil para fazer, permite que o sistema operacional reduza a velocidade da CPU e reduza o calor / conserve energia.

Além disso, em um sistema de núcleo único, um spinlock será bastante ineficiente na presença de congestionamento de bloqueio, pois um thread giratório desperdiçará seu tempo completo esperando por uma mudança de estado que não pode acontecer (não até que o thread de liberação seja agendado, o que não é está acontecendo enquanto o thread de espera está em execução! Portanto, dada qualquer quantidade de contenção, adquirir o bloqueio leva cerca de 1 1/2 fatias de tempo no melhor caso (assumindo que o thread de liberação seja o próximo a ser agendado), o que não é um comportamento muito bom.

4. Como eles são implementados
Hoje em dia, um semáforo normalmente envolve o sys_futexLinux (opcionalmente com um spinlock que sai após algumas tentativas).
Um spinlock é normalmente implementado usando operações atômicas e sem usar nada fornecido pelo sistema operacional. No passado, isso significava usar intrínsecos do compilador ou instruções assembler não portáteis. Enquanto isso, tanto o C ++ 11 quanto o C11 têm operações atômicas como parte da linguagem, portanto, além da dificuldade geral de escrever código sem bloqueio comprovadamente correto, agora é possível implementar código livre de bloqueio de uma forma totalmente portátil e (quase) maneira indolor.

muito simplesmente, um semáforo é um objeto de sincronização "produtivo", um spinlock é um 'busywait'. (há um pouco mais de semáforos porque eles sincronizam vários threads, ao contrário de um mutex ou guarda ou monitor ou seção crítica que protege uma região de código de um único thread)

Você usaria um semáforo em mais circunstâncias, mas use um spinlock onde irá bloquear por um período muito curto - há um custo para bloquear, especialmente se você bloquear muito. Nesses casos, pode ser mais eficiente fazer o spinlock por um pouco enquanto espera que o recurso protegido seja desbloqueado. Obviamente, há um impacto no desempenho se você girar por muito tempo.

normalmente, se você girar por mais tempo do que um quantum de thread, deverá usar um semáforo.

Além do que Yoav Aviram e gbjbaanb disseram, o outro ponto-chave costumava ser que você nunca usaria um spin-lock em uma máquina de CPU única, enquanto um semáforo faria sentido em tal máquina. Hoje em dia, você é frequentemente pressionado para encontrar uma máquina sem múltiplos núcleos, ou hyperthreading, ou equivalente, mas nas circunstâncias em que você tem apenas uma única CPU, você deve usar semáforos. (Acredito que o motivo seja óbvio. Se a única CPU estiver ocupada esperando por outra coisa para liberar o bloqueio de rotação, mas estiver em execução na única CPU, é improvável que o bloqueio seja liberado até que o processo ou thread atual seja interrompido por o O / S, que pode demorar um pouco e nada de útil acontecerá até que a preempção ocorra.)

De drivers de dispositivo Linux por Rubinni

Ao contrário dos semáforos, spinlocks podem ser usados ​​em código que não pode dormir, como manipuladores de interrupção

Não sou um especialista em kernel, mas aqui estão alguns pontos:

Mesmo a máquina com um processador pode usar spin-locks se a preempção do kernel estiver habilitada durante a compilação do kernel. Se a preempção do kernel estiver desabilitada, o spin-lock (talvez) se expande para uma instrução void .

Além disso, quando estamos tentando comparar o Semaphore vs Spin-lock, acredito que o semáforo se refere ao usado no kernel - NÃO ao usado para IPC (userland).

Basicamente, o spin-lock deve ser usado se a seção crítica for pequena (menor que a sobrecarga de dormir / acordar) e a seção crítica não chamar nada que possa dormir! Um semáforo deve ser usado se a seção crítica for maior e puder dormir.

Raman Chalotra.

Spinlock se refere a uma implementação de bloqueio entre threads usando instruções de montagem dependentes da máquina (como teste e ajuste). É chamado de spinlock porque a thread simplesmente espera em um loop ("gira"), verificando repetidamente até que o bloqueio esteja disponível (espera ocupada). Spinlocks são usados ​​como um substituto para mutexes, que são um recurso fornecido pelos sistemas operacionais (não pela CPU), porque spinlocks têm melhor desempenho, se bloqueados por um curto período de tempo.

Um Semaphor é um recurso fornecido por sistemas operacionais para IPC, portanto, seu objetivo principal é a comunicação entre processos. Por ser um recurso fornecido pelo sistema operacional, seu desempenho não será tão bom quanto o de um spinlock para travamento inter-thead (embora possível). Os semáforos são melhores para travar por longos períodos de tempo.

Dito isso - implementar splinlocks na montagem é complicado e não portátil.

Eu gostaria de adicionar minhas observações, mais gerais e não muito específicas do Linux.

Dependendo da arquitetura de memória e dos recursos do processador, você pode precisar de um spin-lock para implementar um semáforo em um sistema multi-core ou multiprocessador, porque em tais sistemas uma condição de corrida pode ocorrer quando dois ou mais threads / processos desejam para adquirir um semáforo.

Sim, se sua arquitetura de memória oferece o bloqueio de uma seção de memória por um núcleo / processador atrasando todos os outros acessos, e se seus processadores oferecem um teste e conjunto, você pode implementar um semáforo sem um spin-lock (mas com muito cuidado! )

No entanto, como os sistemas multi-core simples / baratos são projetados (estou trabalhando em sistemas embarcados), nem todas as arquiteturas de memória suportam esses recursos multi-core / multiprocessador, apenas teste e ajuste ou equivalente. Então, uma implementação poderia ser a seguinte:

• adquirir o spin-lock (ocupado em espera)
• tente adquirir o semáforo
• libere o bloqueio de rotação
• se o semáforo não foi adquirido com sucesso, suspenda o segmento atual até que o semáforo seja liberado; caso contrário, continue com a seção crítica

A liberação do semáforo precisaria ser implementada da seguinte forma:

• adquirir o spin-lock
• libere o semáforo
• libere o bloqueio de rotação

Sim, e para semáforos binários simples no nível do sistema operacional, seria possível usar apenas um spin-lock como substituição. Mas apenas se as seções de código a serem protegidas forem realmente muito pequenas.

Como disse antes, se e quando você implementar seu próprio sistema operacional, tome cuidado. Depurar esses erros é divertido (minha opinião, não compartilhada por muitos), mas principalmente muito tedioso e difícil.

Um "mutex" (ou "bloqueio de exclusão mútua") é um sinal que dois ou mais processos assíncronos podem usar para reservar um recurso compartilhado para uso exclusivo. O primeiro processo que obtém a propriedade do "mutex" também obtém a propriedade do recurso compartilhado. Outros processos devem esperar que o primeiro processo libere sua propriedade do "mutex" antes de tentarem obtê-lo.

A primitiva de bloqueio mais comum no kernel é o spinlock. O spinlock é um bloqueio de suporte único muito simples. Se um processo tentar adquirir um spinlock e ele não estiver disponível, o processo continuará tentando (girando) até que possa adquirir o bloqueio. Essa simplicidade cria um bloqueio pequeno e rápido.

Spinlock é usado se e somente se você tiver certeza de que o resultado esperado acontecerá muito em breve, antes que o tempo de execução do segmento expire.

Exemplo: No módulo de driver de dispositivo, o driver escreve "0" no registro de hardware R0 e agora precisa esperar que o registro R0 se torne 1. O H / W lê o R0 e faz algum trabalho e escreve "1" em R0. Isso geralmente é rápido (em microssegundos). Agora girar é muito melhor do que dormir e ser interrompido pelo H / W. É claro que, ao girar, a condição de falha de H / W precisa ser cuidada!

Não há absolutamente nenhuma razão para um aplicativo de usuário girar. Não faz sentido. Você vai girar para que algum evento aconteça e esse evento precisa ser concluído por outro aplicativo de nível de usuário, o que nunca é garantido que aconteça em um período de tempo rápido. Portanto, não vou girar no modo de usuário. É melhor dormir () ou mutexlock () ou bloqueio de semáforo () no modo de usuário.

De qual é a diferença entre bloqueios de rotação e semáforos? por Maciej Piechotka :

Ambos gerenciam um recurso limitado. Descreverei primeiro a diferença entre semáforo binário (mutex) e bloqueio de rotação.

Os bloqueios de rotação realizam uma espera ocupada - ou seja, ele continua executando o loop:

while (try_acquire_resource ()); 
 ...  
liberação();

Ele executa um bloqueio / desbloqueio muito leve, mas se o encadeamento de bloqueio for interrompido por outro que tentará acessar o mesmo recurso, o segundo simplesmente tentará adquirir o recurso até esgotar os quanta da CPU.
Por outro lado, mutex se comporta mais como:

if (! try_lock ()) {
    add_to_waiting_queue ();
    esperar();
}
...
processo * p = get_next_process_from_waiting_queue ();
p-> wakeUp ();

Portanto, se o encadeamento tentar adquirir o recurso bloqueado, ele será suspenso até que esteja disponível para ele. Bloquear / desbloquear é muito mais pesado, mas a espera é 'gratuita' e 'justa'.

O semáforo é um bloqueio que pode ser usado várias vezes (conhecido desde a inicialização) - por exemplo, 3 threads podem conter o recurso simultaneamente, mas não mais. É usado, por exemplo, no problema do produtor / consumidor ou em geral em filas:

P (resources_sem)
resource = resources.pop ()
...
resources.push (recursos)
V (recursos_sem)

Diferença entre semáforo, mutex e spinlock?

Travando em Linux

o bloqueio de rotação pode ser mantido por apenas um processo, enquanto o semáforo pode ser mantido por um ou mais processos. O bloqueio de rotação aguarde até que o processo libere um bloqueio e, em seguida, obtenha um bloqueio. O semáforo está dormindo, ou seja, espera e vai dormir.