Qual a eficiência do bloqueio de um mutex desbloqueado? Qual é o custo de um mutex?

Em uma linguagem de baixo nível (C, C ++ ou o que for): eu tenho a opção entre ter um monte de mutexes (como o que pthread me fornece ou o que a biblioteca do sistema nativo fornece) ou um único para um objeto.

Quão eficiente é bloquear um mutex? Ou seja, quantas instruções do assembler existem e quanto tempo elas levam (no caso em que o mutex está desbloqueado)?

Quanto custa um mutex? É um problema ter realmente muitos mutexes? Ou posso apenas lançar tantas variáveis ​​mutex no meu código quanto eu tenho intvariáveis ​​e isso realmente não importa?

(Não tenho certeza de quantas diferenças existem entre diferentes hardwares. Se houver, também gostaria de saber sobre eles. Mas, principalmente, estou interessado em hardware comum.)

O ponto é que, usando muitos mutexs, cada um cobrindo apenas uma parte do objeto, em vez de um único mutex para todo o objeto, eu poderia proteger muitos blocos. E estou me perguntando até onde devo ir sobre isso. Ou seja, devo tentar proteger qualquer bloco possível, na verdade, na medida do possível, não importa quanto mais complicado e quantas mutexes isso signifique?

A publicação no blog do WebKits (2016) sobre bloqueio está muito relacionada a essa pergunta e explica as diferenças entre um spinlock, bloqueio adaptável, futex etc.

Eu tenho a escolha entre ter um monte de mutexes ou um único para um objeto.

Se você tiver muitos threads e o acesso ao objeto ocorrer com frequência, vários bloqueios aumentariam o paralelismo. À custa da manutenção, uma vez que mais travamento significa mais depuração do travamento.

Qual é a eficiência para bloquear um mutex? Ou seja, quantas instruções do assembler existem e quanto tempo elas levam (no caso em que o mutex está desbloqueado)?

As instruções precisas do montador são as despesas gerais mínimas de um mutex - as garantias de coerência de memória / cache são as despesas gerais principais. E com menos frequência um bloqueio específico é realizado - melhor.

O mutex é composto de duas partes principais (simplificação excessiva): (1) um sinalizador indicando se o mutex está bloqueado ou não e (2) fila de espera.

A mudança da bandeira é apenas algumas instruções e normalmente é feita sem a chamada do sistema. Se o mutex estiver bloqueado, o syscall incluirá o thread de chamada na fila de espera e iniciará a espera. O desbloqueio, se a fila de espera estiver vazia, é barato, mas precisa de um syscall para ativar um dos processos em espera. (Em alguns sistemas, syscalls baratos / rápidos são usados ​​para implementar os mutexes, eles se tornam lentos (normais) nas chamadas do sistema apenas em caso de contenção.)

Bloquear mutex desbloqueado é muito barato. Desbloquear o mutex sem contenção também é barato.

Quanto custa um mutex? É um problema ter realmente muitos mutexes? Ou posso apenas lançar tantas variáveis ​​mutex no meu código quanto as variáveis ​​int e isso realmente não importa?

Você pode lançar tantas variáveis ​​mutex em seu código quanto desejar. Você está limitado apenas pela quantidade de memória que seu aplicativo pode alocar.

Resumo. Os bloqueios de espaço do usuário (e os mutexes em particular) são baratos e não estão sujeitos a nenhum limite do sistema. Mas muitos deles significam pesadelo para depuração. Tabela simples:

1. Menos bloqueios significam mais contenções (chamadas lentas, paradas da CPU) e menor paralelismo
2. Menos bloqueios significam menos problemas na depuração de problemas com vários threads.
3. Mais bloqueios significa menos contendas e maior paralelismo
4. Mais bloqueios significa mais chances de encontrar impasses indefiníveis.

Um esquema de bloqueio balanceado para aplicação deve ser encontrado e mantido, geralmente equilibrando o nº 2 e o nº 3.

(*) O problema com mutexes bloqueados com menos frequência é que, se você tiver muito bloqueio em seu aplicativo, isso causará que grande parte do tráfego entre CPU / núcleo liberte a memória mutex do cache de dados de outras CPUs para garantir a coerência do cache. As liberações do cache são como interrupções leves e tratadas por CPUs transparente - mas eles introduzem os chamados barracas (procure por "tenda").

E as barracas são o que faz com que o código de bloqueio seja executado lentamente, geralmente sem nenhuma indicação aparente do motivo pelo qual o aplicativo é lento. (Alguns arch fornecem estatísticas de tráfego entre CPU / núcleo, outros não.)

Para evitar o problema, as pessoas geralmente recorrem a um grande número de bloqueios para diminuir a probabilidade de contenção de bloqueios e evitar a paralisação. Essa é a razão pela qual existe o bloqueio de espaço do usuário barato, não sujeito aos limites do sistema.

Eu queria saber a mesma coisa, então medi-a. Na minha caixa (processador AMD FX (tm) -8150 de oito núcleos a 3.612361 GHz), bloquear e desbloquear um mutex desbloqueado que está em sua própria linha de cache e já está armazenado em cache leva 47 relógios (13 ns).

Devido à sincronização entre dois núcleos (usei a CPU n ° 0 e n ° 1), eu só poderia chamar um par de bloqueio / desbloqueio uma vez a cada 102 ns em dois threads, assim como uma vez a cada 51 ns, do qual se pode concluir que são necessários aproximadamente 38 ns para recuperar depois que um thread faz um desbloqueio antes que o próximo thread possa bloqueá-lo novamente.

O programa que eu usei para investigar isso pode ser encontrado aqui: https://github.com/CarloWood/ai-statefultask-testsuite/blob/b69b112e2e91d35b56a39f41809d3e3de2f9e4b8/src/mutex_test.cxx

Observe que ele possui alguns valores codificados específicos para minha caixa (xrange, yrange e rdtsc overhead), portanto, você provavelmente precisará experimentá-la antes que ela funcione para você.

O gráfico que produz nesse estado é:

Isso mostra o resultado das execuções de benchmark no seguinte código:

uint64_t do_Ndec(int thread, int loop_count)
{
  uint64_t start;
  uint64_t end;
  int __d0;

  asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (start) : : "%rdx");
  mutex.lock();
  mutex.unlock();
  asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (end) : : "%rdx");
  asm volatile ("\n1:\n\tdecl %%ecx\n\tjnz 1b" : "=c" (__d0) : "c" (loop_count - thread) : "cc");
  return end - start;
}

As duas chamadas rdtsc medem o número de relógios necessários para bloquear e desbloquear o `mutex '(com uma sobrecarga de 39 relógios para as chamadas rdtsc na minha caixa). O terceiro asm é um loop de atraso. O tamanho do loop de atraso é 1 contagem menor para o segmento 1 do que para o segmento 0, portanto, o segmento 1 é um pouco mais rápido.

A função acima é chamada em um loop apertado de tamanho 100.000. Apesar de a função ser um pouco mais rápida para o encadeamento 1, os dois loops são sincronizados devido à chamada para o mutex. Isso é visível no gráfico pelo fato de o número de relógios medidos para o par de bloqueio / desbloqueio ser um pouco maior para o encadeamento 1, para explicar o menor atraso no loop abaixo dele.

No gráfico acima, o ponto inferior direito é uma medida com um atraso loop_count de 150 e, seguindo os pontos na parte inferior, em direção à esquerda, o loop_count é reduzido em um a cada medição. Quando se torna 77, a função é chamada a cada 102 ns nos dois threads. Se subsequentemente loop_count for reduzido ainda mais, não será mais possível sincronizar os encadeamentos e o mutex começará a ser realmente bloqueado a maior parte do tempo, resultando em uma quantidade maior de relógios necessários para o bloqueio / desbloqueio. Além disso, o tempo médio da chamada da função aumenta por causa disso; então os pontos da trama agora sobem e voltam para a direita.

A partir disso, podemos concluir que bloquear e desbloquear um mutex a cada 50 ns não é um problema na minha caixa.

Em suma, minha conclusão é que a resposta à pergunta do OP é que adicionar mais mutexes é melhor, desde que isso resulte em menos contenção.

Tente bloquear os mutexes o mais curto possível. O único motivo para colocá-los - digamos - fora de um loop seria se esse loop fizesse loops mais rápido que uma vez a cada 100 ns (ou melhor, número de threads que desejam executar esse loop ao mesmo tempo 50 ns) ou 13 vezes ns o tamanho do loop é mais atraso do que o atraso que você recebe por contenção.

Edição: Eu tenho muito mais conhecimento sobre o assunto agora e começo a duvidar da conclusão que apresentei aqui. Primeiro de tudo, a CPU 0 e 1 são hiperencadeadas; embora a AMD afirme ter 8 núcleos reais, certamente há algo muito suspeito porque os atrasos entre outros dois núcleos são muito maiores (ou seja, 0 e 1 formam um par, como 2 e 3, 4 e 5 e 6 e 7 ) Em segundo lugar, o std :: mutex é implementado de forma a girar os bloqueios um pouco antes de realmente fazer chamadas do sistema quando falha em obter imediatamente o bloqueio em um mutex (o que sem dúvida será extremamente lento). Portanto, o que eu medi aqui é a situação ideal mais absoluta e, na prática, o bloqueio e desbloqueio podem levar drasticamente mais tempo por bloqueio / desbloqueio.

Bottom line, um mutex é implementado com atômica. Para sincronizar átomos entre núcleos, um barramento interno deve ser bloqueado, o que congela a linha de cache correspondente por várias centenas de ciclos de clock. No caso de não ser possível obter um bloqueio, é necessário executar uma chamada do sistema para colocar o encadeamento em suspensão; isso é obviamente extremamente lento (as chamadas do sistema são da ordem de 10 mircosegundos). Normalmente, isso não é realmente um problema, porque esse segmento precisa dormir de qualquer maneira - mas pode ser um problema com alta contenção, em que um segmento não pode obter o bloqueio pelo tempo em que normalmente gira e o sistema chama, mas PODE pegue a fechadura logo depois. Por exemplo, se vários encadeamentos bloqueiam e desbloqueiam um mutex em um loop apertado e cada um mantém o bloqueio por 1 microssegundo, então eles podem ser desacelerados enormemente pelo fato de serem constantemente adormecidos e acordados novamente. Além disso, uma vez que um thread dorme e outro thread precise ativá-lo, esse thread precisa fazer uma chamada de sistema e atrasa ~ 10 microssegundos; esse atraso ocorre durante o desbloqueio de um mutex quando outro encadeamento aguarda esse mutex no kernel (após a rotação demorou muito).

Isso depende do que você realmente chama de "mutex", modo SO e etc.

No mínimo , é um custo de uma operação de memória intertravada. É uma operação relativamente pesada (em comparação com outros comandos primitivos do assembler).

No entanto, isso pode ser muito maior. Se o que você chama de "mutex" um objeto do kernel (ou seja, objeto gerenciado pelo sistema operacional) e é executado no modo de usuário, todas as operações nele levam a uma transação no modo do kernel, que é muito pesada.

Por exemplo, no processador Intel Core Duo, Windows XP. Operação intertravada: leva cerca de 40 ciclos da CPU. Chamada no modo kernel (ou seja, chamada do sistema) - cerca de 2000 ciclos de CPU.

Se for esse o caso, considere usar seções críticas. É um híbrido de um mutex do kernel e acesso à memória intertravada.

O custo variará dependendo da implementação, mas você deve ter em mente duas coisas:

• o custo provavelmente será mínimo, pois é uma operação bastante primitiva e será otimizado o máximo possível devido ao seu padrão de uso (usado muito ).
• não importa o quão caro seja, pois você precisará usá-lo se desejar uma operação multithread segura. Se você precisar, precisa.

Em sistemas de processador único, geralmente é possível desativar as interrupções por tempo suficiente para alterar dados atomicamente. Os sistemas com vários processadores podem usar uma estratégia de teste e configuração .

Nos dois casos, as instruções são relativamente eficientes.

Se você deve fornecer um único mutex para uma estrutura de dados massiva ou ter muitos mutexes, um para cada seção, é um ato de equilíbrio.

Por ter um único mutex, você tem um risco maior de contenção entre vários threads. Você pode reduzir esse risco tendo um mutex por seção, mas não deseja entrar em uma situação em que um encadeamento precise bloquear 180 mutexes para fazer seu trabalho :-)

Sou completamente novo em pthreads e mutex, mas posso confirmar por experimentação que o custo de bloquear / desbloquear um mutex é quase zero quando não há contenção, mas quando existe, o custo do bloqueio é extremamente alto. Eu executei um código simples com um pool de threads no qual a tarefa era apenas calcular uma soma em uma variável global protegida por um bloqueio de mutex:

y = exp(-j*0.0001);
pthread_mutex_lock(&lock);
x += y ;
pthread_mutex_unlock(&lock);

Com um thread, o programa soma 10.000.000 valores virtualmente instantaneamente (menos de um segundo); com dois threads (em um MacBook com 4 núcleos), o mesmo programa leva 39 segundos.