Você pode explicar por que vários threads precisam de bloqueios em uma CPU de núcleo único?

Suponha que esses threads sejam executados na CPU de núcleo único. Como uma CPU, execute apenas uma instrução em um ciclo. Dito isto, mesmo que eles compartilhem o recurso da CPU. mas o computador garante que uma vez uma instrução. Portanto, o bloqueio não é necessário para a leitura múltipla?

Isso é melhor ilustrado com um exemplo.

Suponha que tenhamos uma tarefa simples que queremos executar várias vezes em paralelo e que desejemos acompanhar globalmente o número de vezes que a tarefa foi executada, por exemplo, contando ocorrências em uma página da web.

Quando cada encadeamento chega ao ponto em que está incrementando a contagem, sua execução terá a seguinte aparência:

1. Leia o número de ocorrências da memória em um registro do processador
2. Incremente esse número.
3. Escreva esse número de volta à memória

Lembre-se de que todo encadeamento pode ser suspenso a qualquer momento deste processo. Portanto, se o segmento A executar a etapa 1 e for suspenso, seguido pelo segmento B, executando as três etapas, quando o segmento A for reiniciado, seus registros terão o número errado de ocorrências: seus registros serão restaurados e incrementarão felizmente o número antigo de hits e armazene esse número incrementado.

Além disso, qualquer número de outros encadeamentos poderia ter sido executado durante o tempo em que o encadeamento A foi suspenso; portanto, o encadeamento de contagem A gravado no final pode estar bem abaixo da contagem correta.

Por esse motivo, é necessário garantir que, se um encadeamento executa a etapa 1, ele deve executar a etapa 3 antes que qualquer outro encadeamento possa executar a etapa 1, o que pode ser realizado por todos os encadeamentos que esperam obter um único bloqueio antes de iniciar esse processo e liberando o bloqueio somente após a conclusão do processo, para que esta "seção crítica" do código não possa ser intercalada incorretamente, resultando em uma contagem incorreta.

Mas e se a operação fosse atômica?

Sim, na terra de unicórnios mágicos e arco-íris, onde a operação de incremento é atômica, o bloqueio não seria necessário para o exemplo acima.

É importante perceber, no entanto, que passamos muito pouco tempo no mundo dos unicórnios mágicos e arco-íris. Em quase todas as linguagens de programação, a operação de incremento é dividida nas três etapas acima. Isso porque, mesmo que o processador suporte uma operação de incremento atômico, essa operação é significativamente mais cara: ela precisa ler da memória, modificar o número e gravá-lo na memória ... e geralmente a operação de incremento atômico é uma operação que pode falhar, o que significa que a sequência simples acima deve ser substituída por um loop (como veremos abaixo).

Como, mesmo no código multithread, muitas variáveis ​​são mantidas locais em um único thread, os programas são muito mais eficientes se eles assumem que cada variável é local em um único thread e permitem que os programadores cuidem da proteção do estado compartilhado entre os threads. Especialmente porque as operações atômicas geralmente não são suficientes para resolver problemas de encadeamento, como veremos mais adiante.

Variáveis ​​voláteis

Se quisermos evitar bloqueios para esse problema em particular, primeiro precisamos entender que as etapas descritas em nosso primeiro exemplo não são realmente o que acontece no código compilado moderno. Como os compiladores assumem que apenas um thread está modificando a variável, cada thread manterá sua própria cópia em cache da variável, até que o registro do processador seja necessário para outra coisa. Contanto que tenha a cópia em cache, ela pressupõe que não precisa voltar à memória e lê-la novamente (o que seria caro). Eles também não gravam a variável na memória, desde que ela seja mantida em um registro.

Podemos voltar à situação que fornecemos no primeiro exemplo (com os mesmos problemas de encadeamento identificados acima), marcando a variável como volátil , o que informa ao compilador que essa variável está sendo modificada por outras pessoas e, portanto, deve ser lida em ou gravado na memória sempre que for acessado ou modificado.

Portanto, uma variável marcada como volátil não nos levará à terra das operações de incremento atômico, apenas nos aproxima tão perto como pensávamos que já estávamos.

Tornando o incremento atômico

Uma vez que estamos usando uma variável volátil, podemos tornar nossa operação de incremento atômica usando uma operação de conjunto condicional de baixo nível que a maioria das CPUs modernas suporta (geralmente chamadas de comparar e configurar ou comparar e trocar ). Essa abordagem é adotada, por exemplo, na classe AtomicInteger do Java :

197       /**
198        * Atomically increments by one the current value.
199        *
200        * @return the updated value
201        */
202       public final int incrementAndGet() {
203           for (;;) {
204               int current = get();
205               int next = current + 1;
206               if (compareAndSet(current, next))
207                   return next;
208           }
209       }

O loop acima executa repetidamente as seguintes etapas, até que a etapa 3 seja bem-sucedida:

1. Leia o valor de uma variável volátil diretamente da memória.
2. Incremente esse valor.
3. Altere o valor (na memória principal) se, e somente se, o valor atual na memória principal for o mesmo que lemos inicialmente, usando uma operação atômica especial.

Se a etapa 3 falhar (porque o valor foi alterado por um thread diferente após a etapa 1), ela lê novamente a variável diretamente da memória principal e tenta novamente.

Embora a operação de comparação e troca seja cara, é um pouco melhor do que usar o bloqueio nesse caso, porque se um encadeamento for suspenso após a etapa 1, outros encadeamentos que atingem a etapa 1 não precisarão bloquear e aguardar o primeiro encadeamento, que pode impedir a troca de contexto dispendiosa. Quando o primeiro encadeamento continuar, ele falhará em sua primeira tentativa de gravar a variável, mas poderá continuar relendo a variável, o que provavelmente é mais barato do que a troca de contexto que seria necessária com o bloqueio.

Assim, podemos chegar a terra de incrementos atômicos (ou outras operações em uma única variável) sem usar bloqueios reais, via comparação e troca.

Então, quando o bloqueio é estritamente necessário?

Se você precisar modificar mais de uma variável em uma operação atômica, o bloqueio será necessário, você não encontrará uma instrução especial do processador para isso.

Contanto que você esteja trabalhando em uma única variável e esteja preparado para qualquer trabalho que tenha falhado e que precise ler a variável e começar de novo, a comparação e troca será boa o suficiente.

Vamos considerar um exemplo em que cada thread adiciona primeiro 2 à variável X e depois multiplica X por dois.

Se X é inicialmente um e dois threads são executados, esperamos que o resultado seja (((1 + 2) * 2) + 2) * 2 = 16.

No entanto, se os encadeamentos se intercalarem, poderíamos, mesmo com todas as operações atômicas, fazer com que ambas as adições ocorram primeiro e as multiplicações ocorram depois, resultando em (1 + 2 + 2) * 2 * 2 = 20.

Isso acontece porque multiplicação e adição não são operações comutativas.

Portanto, as próprias operações sendo atômicas não são suficientes, precisamos tornar a combinação de operações atômica.

Podemos fazer isso usando o bloqueio para serializar o processo ou podemos usar uma variável local para armazenar o valor de X quando iniciamos nosso cálculo, uma segunda variável local para as etapas intermediárias e, em seguida, comparar e trocar para defina um novo valor apenas se o valor atual de X for igual ao valor original de X. Se falharmos, teríamos que começar novamente lendo X e realizando os cálculos novamente.

Existem várias compensações envolvidas: à medida que os cálculos se tornam mais longos, é muito mais provável que o encadeamento em execução seja suspenso e o valor seja modificado por outro encadeamento antes de retomarmos, o que significa que as falhas se tornam muito mais prováveis, levando ao desperdício. tempo do processador. No caso extremo de um grande número de threads com cálculos de execução muito longos, podemos ter 100 threads lendo a variável e participar de cálculos; nesse caso, apenas o primeiro a concluir terá sucesso ao escrever o novo valor, os outros 99 ainda conclua seus cálculos, mas descubra que eles não podem atualizar o valor ... nesse ponto, cada um lerá o valor e iniciará o cálculo novamente. Provavelmente, os 99 threads restantes repetem o mesmo problema, desperdiçando grandes quantidades de tempo do processador.

A serialização completa da seção crítica via bloqueios seria muito melhor nessa situação: 99 threads seriam suspensos quando não obtivessem o bloqueio, e executaríamos cada thread na ordem de chegada ao ponto de bloqueio.

Se a serialização não for crítica (como no nosso caso de incremento), e os cálculos que seriam perdidos se a atualização do número falhar forem mínimos, pode haver uma vantagem significativa a ser obtida com o uso da operação de comparação e troca, porque essa operação é mais barato que travar.

Considere esta citação:

Algumas pessoas, quando confrontadas com um problema, pensam: "Eu sei, vou usar threads" e, depois, duas elas têm poblesms.

você vê, mesmo que uma instrução seja executada em uma CPU a qualquer momento, os programas de computador compreendem muito mais do que apenas instruções de montagem atômica. Por exemplo, gravar no console (ou em um arquivo) significa que você precisa bloquear para garantir que funcione como você deseja.

Parece que muitas respostas tentaram explicar o bloqueio, mas acho que o OP precisa de uma explicação sobre o que realmente é a multitarefa.

Quando você tem mais de um encadeamento em execução em um sistema, mesmo com uma CPU, existem duas metodologias principais que determinam como esses encadeamentos serão agendados (ou seja, colocados para executar em sua CPU de núcleo único):

• Multitarefa cooperativa - usada no Win9x exigia que cada aplicativo desistisse explicitamente do controle. Nesse caso, você não precisaria se preocupar com o bloqueio, desde que o Thread A esteja executando algum algoritmo, você garante que ele nunca será interrompido
• Multitarefa preemptiva - Usado na maioria dos sistemas operacionais modernos (Win2k e posterior). Isso usa timeslices e interrompe os threads, mesmo se eles ainda estiverem trabalhando. Isso é muito mais robusto, porque um único thread nunca pode travar toda a máquina, o que era uma possibilidade real com multitarefa cooperativa. Por outro lado, agora você precisa se preocupar com bloqueios porque, a qualquer momento, um de seus threads pode ser interrompido (isto é, antecipado) e o SO pode agendar um thread diferente para execução. Ao codificar aplicativos multithread com esse comportamento, você DEVE considerar que entre todas as linhas de código (ou mesmo todas as instruções) um thread diferente pode ser executado. Agora, mesmo com um único núcleo, o bloqueio se torna muito importante para garantir um estado consistente dos seus dados.

O problema não está nas operações individuais, mas nas tarefas maiores que as operações realizam.

Muitos algoritmos são escritos com a suposição de que eles estão no controle total do estado em que operam. Com um modelo de execução ordenada intercalada como o que você descreve, as operações podem ser intercaladas arbitrariamente entre si e, se compartilharem estado, há o risco de que o estado esteja em uma forma inconsistente.

Você pode compará-lo com funções que podem interromper temporariamente uma invariante para fazer o que elas fazem. Enquanto o estado intermediário não for observável de fora, eles podem fazer o que quiserem para realizar sua tarefa.

Ao escrever código simultâneo, você precisa garantir que o estado contido seja considerado inseguro, a menos que você tenha acesso exclusivo a ele. A maneira comum de obter acesso exclusivo é sincronizar em uma primitiva de sincronização, como segurar uma trava.

Outra coisa que as primitivas de sincronização tendem a resultar em algumas plataformas é que elas emitem barreiras de memória, o que garante a consistência de memória entre CPU.

Exceto para definir 'bool', não há garantia (pelo menos em c) que a leitura ou gravação de uma variável leve apenas uma instrução - ou melhor, não pode ser interrompida no meio da leitura / gravação.

Memoria compartilhada.

É a definição de ... threads : um monte de processos simultâneos, com memória compartilhada.

Se não houver memória compartilhada, eles geralmente são chamados de processos UNIX da velha escola .
Eles podem precisar de um bloqueio, de vez em quando, ao acessar um arquivo compartilhado.

(a memória compartilhada nos kernels do tipo UNIX geralmente era implementada usando um descritor de arquivo falso que representa o endereço da memória compartilhada)

Uma CPU executa uma instrução por vez, mas e se você tiver duas ou mais CPUs?

Você está certo de que os bloqueios não são necessários, se você pode escrever o programa de forma a tirar proveito das instruções atômicas: instruções cuja execução não é interrompível no processador fornecido e livre de interferências de outros processadores.

Bloqueios são necessários quando várias instruções precisam ser protegidas contra interferências e não há instrução atômica equivalente.

Por exemplo, inserir um nó em uma lista duplamente vinculada requer a atualização de vários locais de memória. Antes da inserção, e após a inserção, certos invariantes mantêm a estrutura da lista. No entanto, durante a inserção, esses invariantes são interrompidos temporariamente: a lista está no estado "em construção".

Se outro encadeamento percorrer a lista enquanto os invariantes, ou também tentar modificá-lo quando estiver nesse estado, a estrutura de dados provavelmente ficará corrompida e o comportamento será imprevisível: talvez o software trava ou continue com resultados incorretos. Portanto, é necessário que os threads concordem de alguma forma ficar fora do caminho um do outro quando a lista estiver sendo atualizada.

Listas projetadas adequadamente podem ser manipuladas com instruções atômicas, para que não sejam necessários bloqueios. Algoritmos para isso são chamados de "sem bloqueio". No entanto, observe que as instruções atômicas são realmente uma forma de bloqueio. Eles são especialmente implementados em hardware e funcionam via comunicação entre processadores. Eles são mais caros do que instruções semelhantes que não são atômicas.

Em multiprocessadores que não têm o luxo de instruções atômicas, primitivas para exclusão mútua precisam ser construídas com simples acessos à memória e loops de pesquisa. Tais problemas foram trabalhados por pessoas como Edsger Dijkstra e Leslie Lamport.