O que é um spinlock no Linux?

32

Eu gostaria de saber sobre os spinlocks do Linux em detalhes; alguém poderia me explicar?

Sen
fonte

Respostas:

34

Um bloqueio de rotação é uma maneira de proteger um recurso compartilhado de ser modificado por dois ou mais processos simultaneamente. O primeiro processo que tenta modificar o recurso "adquire" o bloqueio e continua seu caminho, fazendo o que é necessário com o recurso. Quaisquer outros processos que subsequentemente tentam obter o bloqueio são interrompidos; é dito que eles "giram no lugar", aguardando a liberação do bloqueio pelo primeiro processo, portanto, o nome bloqueio de rotação.

O kernel do Linux usa bloqueios de rotação para muitas coisas, como ao enviar dados para um periférico específico. A maioria dos periféricos de hardware não foi projetada para lidar com várias atualizações de estado simultâneas. Se duas modificações diferentes tiverem que acontecer, uma deve seguir rigorosamente a outra, elas não poderão se sobrepor. Um bloqueio de rotação fornece a proteção necessária, garantindo que as modificações ocorram uma de cada vez.

Os bloqueios de rotação são um problema porque a rotação impede que o núcleo da CPU desse thread faça qualquer outro trabalho. Embora o kernel do Linux forneça serviços de multitarefa para os programas espaciais do usuário em execução, esse recurso de multitarefa de uso geral não se estende ao código do kernel.

Essa situação está mudando e tem sido na maior parte da existência do Linux. No Linux 2.0, o kernel era quase um programa de tarefa única: sempre que a CPU executava o código do kernel, apenas um núcleo era usado, porque havia um único bloqueio de rotação protegendo todos os recursos compartilhados, chamado Big Kernel Lock (BKL ) A partir do Linux 2.2, o BKL está lentamente sendo dividido em muitos bloqueios independentes, cada um protegendo uma classe de recursos mais focada. Hoje, com o kernel 2.6, o BKL ainda existe, mas é usado apenas por códigos realmente antigos que não podem ser facilmente movidos para um bloqueio mais granular. Agora é bem possível que uma caixa multicore tenha toda CPU executando código útil do kernel.

Há um limite para a utilidade de dividir o BKL porque o kernel do Linux não possui multitarefa geral. Se um núcleo da CPU for bloqueado na rotação em um bloqueio de rotação do kernel, ele não poderá ser retocado novamente, para fazer outra coisa até que o bloqueio seja liberado. Ele apenas fica e gira até que a trava seja liberada.

Os bloqueios de rotação podem transformar efetivamente uma caixa monstro de 16 núcleos em uma caixa de núcleo único, se a carga de trabalho for tal que cada núcleo esteja sempre esperando por um único bloqueio de rotação. Esse é o principal limite para a escalabilidade do kernel do Linux: dobrar os núcleos da CPU de 2 para 4 provavelmente dobrará a velocidade de uma caixa Linux, mas dobrar de 16 para 32 provavelmente não, com a maioria das cargas de trabalho.

Warren Young
fonte
@ Warren: Algumas dúvidas - eu gostaria de saber mais sobre esse Big Kernel Lock e suas implicações. Eu também entendo o último parágrafo "dobrar os núcleos da CPU de 2 para 4 provavelmente dobrará a velocidade de uma caixa Linux, mas dobrar de 16 para 32 provavelmente não"
Sen
2
Re: implicações do BKL: Eu pensei que deixei isso claro acima. Com apenas um bloqueio no kernel, sempre que dois núcleos tentam fazer algo protegido pelo BKL, um núcleo é bloqueado enquanto o primeiro termina o uso de seu recurso protegido. Quanto mais refinado o bloqueio, menor a chance de que isso aconteça, maior a utilização do processador.
Warren Young
2
Re: duplicação: quero dizer que existe uma lei de retornos decrescentes ao adicionar núcleos de processador a um computador. À medida que o número de núcleos aumenta, aumenta também a chance de que dois ou mais deles precisem acessar um recurso protegido por um bloqueio específico. O aumento da granularidade do bloqueio reduz as chances de tais colisões, mas também há sobrecarga na adição de muitos. Você pode ver isso facilmente nos supercomputadores, que costumam ter milhares de processadores atualmente: a maioria das cargas de trabalho é ineficiente, porque não podem evitar a ociosidade de muitos processadores devido à contenção de recursos compartilhados.
Warren Young
1
Embora essa seja uma explicação interessante (+1 para isso), não acho que seja eficaz transmitir a diferença entre spinlocks e outros tipos de bloqueios.
Gilles 'SO- stop be evil'
2
Se alguém quiser saber a diferença entre um bloqueio de rotação e, digamos, um semáforo, essa é uma pergunta diferente. Outra pergunta boa, mas tangencial, é: o que é o design do kernel Linux que faz com que os bloqueios de rotação sejam boas escolhas em vez de algo mais comum no código da terra do usuário, como um mutex. Esta resposta divaga bastante como é.
Warren Young
11

Um bloqueio de rotação é quando um processo pesquisa continuamente por um bloqueio a ser removido. É considerado ruim porque o processo está consumindo ciclos (geralmente) desnecessariamente. Não é específico do Linux, mas um padrão de programação geral. E, embora seja geralmente considerada uma má prática, é, de fato, a solução correta; há casos em que o custo do uso do planejador é mais alto (em termos de ciclos da CPU) do que o custo dos poucos ciclos que o spinlock deve durar.

Exemplo de um spinlock:

#!/bin/sh
#wait for some program to clear a lock before doing stuff
while [ -f /var/run/example.lock ]; do
  sleep 1
done
#do stuff

Existe frequentemente uma maneira de evitar um bloqueio de rotação. Neste exemplo em particular, há uma ferramenta Linux chamada inotifywait (geralmente não é instalada por padrão). Se estivesse escrito em C, você simplesmente usaria a API inotify que o Linux fornece.

O mesmo exemplo, usando inotifywait, mostra como realizar a mesma coisa sem um bloqueio de rotação:

#/bin/sh
inotifywait -e delete_self /var/run/example.lock
#do stuff
Shawn J. Goff
fonte
Qual é o papel do agendador lá? Ou tem algum papel?
Sen
1
No método de bloqueio de rotação, o planejador retoma o processo a cada ~ 1 segundo para executar sua tarefa (que é simplesmente verificar a existência de um arquivo). No exemplo inotifywait, o planejador somente retoma o processo quando o processo filho (inotifywait) sai. Inotifywait também está dormindo; o planejador apenas o reinicia quando o evento inotify acontece.
Shawn J. Goff
Então, como esse cenário é tratado em um sistema de processador de núcleo único?
Sen
@ Sen: Isso é explicado bastante bem nos drivers de dispositivos Linux .
Gilles 'SO- stop be evil'
1
Esse script bash é um mau exemplo de um spinlock. Você está pausando o processo para que ele entre no modo de suspensão. Um spinlock nunca dorme. Em uma máquina com um único núcleo, ele apenas suspende o agendador e continua (sem espera ocupada) #
Martin
7

Quando um encadeamento tenta adquirir um bloqueio, três coisas podem acontecer se falhar, tentar e bloquear, tentar e continuar, tentar dormir e dizer ao sistema operacional para ativá-lo quando algum evento acontecer.

Agora, tentar e continuar usa muito menos tempo que tentar e bloquear. Digamos por enquanto que uma "tentativa e continuação" levará i unidade de tempo e uma "tentativa e bloqueio" levará cem.

Agora, vamos supor que, em média, um segmento levará 4 unidades de tempo segurando a trava. É um desperdício esperar 100 unidades. Então, em vez disso, você escreve um loop de "tenta e continua". Na quarta tentativa, você normalmente adquirirá o bloqueio. Este é um bloqueio de rotação. É chamado assim porque o fio continua girando no lugar até que ele trava.

Uma medida de segurança adicional é limitar o número de vezes que o loop é executado. Portanto, no exemplo, você executa um loop for, por exemplo, seis vezes; se falhar, "tenta e bloqueia".

Se você souber que um encadeamento sempre manterá a trava por, digamos, 200 unidades, estará perdendo tempo do computador para cada tentativa e continuação.

Portanto, no final, um bloqueio de rotação pode ser muito eficiente ou desperdiçador. É um desperdício quando o tempo "típico" para segurar uma fechadura é maior que o tempo necessário para "tentar bloquear". É eficiente quando o tempo típico para segurar uma fechadura é muito menor que o tempo para "tentar bloquear".

Ps: O livro para ler sobre tópicos é "A Thread Primer", se você ainda pode encontrá-lo.

HandyGandy
fonte
o fio continua girando no lugar até que ele trava . Você poderia me dizer o que está girando? É como se tratasse do wait_queue e fosse executado pelo Scheduler? Talvez eu esteja tentando entrar no nível mais baixo, mas ainda não consigo segurar minha dúvida.
Sen
Girando entre as instruções 3-4 no loop, basicamente.
Paul Stelian 19/03
5

Um bloqueio é uma maneira de sincronizar duas ou mais tarefas (processos, threads). Especificamente, quando as duas tarefas precisam de acesso intermitente a um recurso que só pode ser usado por uma tarefa por vez, é uma maneira de organizar as tarefas para não usar o recurso ao mesmo tempo. Para acessar o recurso, uma tarefa deve executar as seguintes etapas:

take the lock
use the resource
release the lock

Não é possível bloquear um bloqueio se outra tarefa já tiver sido executada. (Pense no cadeado como um objeto de token físico. O objeto está em uma gaveta ou alguém o tem na mão. Somente a pessoa que está segurando o objeto pode acessar o recurso.) Portanto, "pegue o cadeado" significa realmente "espere até ninguém mais tem a fechadura, então pegue-a ”.

Do ponto de vista de alto nível, existem duas maneiras principais de implementar bloqueios: spinlocks e condições. With spinlocks , a trava significa apenas "girar" (ou seja, não fazer nada em loop) até que ninguém mais tenha a trava. Com condições, se uma tarefa tentar fechar o bloqueio, mas estiver bloqueada porque outra tarefa o mantém, o recém-chegado entra em uma fila de espera; a operação de liberação sinaliza para qualquer tarefa em espera que o bloqueio está disponível agora.

(Essas explicações não são suficientes para permitir que você implemente um bloqueio, porque eu não disse nada sobre atomicidade. Mas a atomicidade não é importante aqui.)

Os spinlocks são obviamente um desperdício: a tarefa em espera continua verificando se o bloqueio foi realizado. Então, por que e quando é usado? Spinlocks geralmente são muito baratos de obter no caso em que a trava não é realizada. Isso o torna atraente quando a chance de o bloqueio ser mantido é pequena. Além disso, os spinlocks são viáveis ​​apenas se a obtenção do bloqueio não demorar. Portanto, os spinlocks tendem a ser usados ​​em situações em que permanecerão retidos por um período muito curto, de modo que se espera que a maioria das tentativas seja bem-sucedida na primeira tentativa, e as que precisam de uma espera não demoram muito.

Há uma boa explicação sobre spinlocks e outros mecanismos de simultaneidade do kernel Linux em Linux Device Drivers , capítulo 5.

Gilles 'SO- parar de ser mau'
fonte
Qual seria uma boa maneira de implementar outras primitivas de sincronização? Faça um spinlock, verifique se outra pessoa tem o primitivo real sendo implementado e use o agendador ou conceda acesso? Podemos considerar o bloco sincronizado () em Java uma forma de spinlock, e nas primitivas implementadas corretamente, basta usar um spinlock?
Paul Stelian 19/03
@PaulStelian É realmente comum implementar bloqueios "lentos" dessa maneira. Não conheço Java suficiente para responder a essa parte, mas duvido que synchronizedisso fosse implementado por um spinlock: um synchronizedbloco poderia ser executado por um tempo muito longo. synchronizedé uma construção de linguagem para facilitar o uso de bloqueios em certos casos, não uma primitiva para criar primitivas de sincronização maiores.
Gilles 'SO- stop be evil'
3

Um spinlock é um bloqueio que opera desativando o planejador e possivelmente interrompe (variante irqsave) naquele núcleo específico em que o bloqueio é adquirido. É diferente de um mutex, pois desativa o agendamento, portanto, somente seu encadeamento pode ser executado enquanto o spinlock é mantido. Um mutex permite que outros threads de prioridade mais alta sejam agendados enquanto estiver em espera, mas não permite que eles executem simultaneamente a seção protegida. Como os spinlocks desativam a multitarefa, você não pode usar um spinlock e chamar outro código que tentará adquirir um mutex. Seu código dentro da seção spinlock nunca deve dormir (o código normalmente dorme quando encontra um mutex bloqueado ou um semáforo vazio).

Outra diferença com um mutex é que os threads normalmente fazem fila para um mutex, portanto, um mutex abaixo tem uma fila. Enquanto o spinlock apenas garante que nenhum outro thread seja executado, mesmo que seja necessário. Portanto, você nunca deve manter um spinlock ao chamar funções fora do seu arquivo que não tenha certeza de que não irá dormir.

Quando você deseja compartilhar seu spinlock com uma interrupção, deve usar a variante irqsave. Isso não apenas desabilita o agendador, mas também desativa as interrupções. Faz sentido certo? Spinlock funciona certificando-se de que nada mais será executado. Se você não deseja que uma interrupção seja executada, desative-a e prossiga com segurança para a seção crítica.

Na máquina multicore, um spinlock realmente gira enquanto espera por outro núcleo que segura a trava para liberá-la. Essa rotação ocorre apenas em máquinas com vários núcleos, porque em máquinas com um único núcleo isso não pode acontecer (você mantém o spinlock e continua ou nunca executa até que o bloqueio seja liberado).

Spinlock não é um desperdício onde faz sentido. Para seções críticas muito pequenas, seria um desperdício alocar uma fila de tarefas mutex em comparação com simplesmente suspender o planejador por alguns microssegundos necessários para concluir o trabalho importante. Se você precisar dormir ou manter o bloqueio pressionado durante uma operação io (que pode dormir), use um mutex. Certamente nunca bloqueie um spinlock e tente liberá-lo dentro de uma interrupção. Enquanto isso funcionar, será como a porcaria do arduino de while (flagnotset); nesse caso, use um semáforo.

Pegue um spinlock quando precisar de exclusão mútua simples para blocos de transações de memória. Pegue um mutex quando desejar que vários encadeamentos parem logo antes de um bloqueio de mutex e, em seguida, escolha o encadeamento de maior prioridade para continuar quando o mutex ficar livre e quando você bloquear e liberar no mesmo encadeamento. Pegue um semáforo quando pretende publicá-lo em um tópico ou uma interrupção e coloque-o em outro tópico. São três maneiras ligeiramente diferentes de garantir a exclusão mútua e são usadas para finalidades ligeiramente diferentes.

Martin
fonte