Em ciência da computação, sincronização é a coordenação de eventos em processos. Um exemplo é o handshake.

Motivação A necessidade de sincronização existe em sistemas com mais de um processador e também entre processos concorrentes executados em um único processador. Entre as situações que exigem sincronização estão a divisão e reunião de tarefas, a relação entre produtores e consumidores e o acesso a recursos de uso exclusivo.

No modelo fork-join, um trabalho é dividido em N subtrabalhos ao chegar a um ponto de bifurcação. Esses subtrabalhos são executados por n tarefas. Cada um, ao terminar, aguarda a conclusão dos demais. Em seguida, os resultados são reunidos e o trabalho deixa o sistema. A programação paralela exige essa sincronização quando o prosseguimento de uma tarefa depende da conclusão de outras.

Na relação produtor-consumidor, o processo consumidor depende do produtor e precisa aguardar a produção dos dados de que necessita.

Quando processos precisam acessar simultaneamente um recurso de uso exclusivo, o sistema operacional deve garantir que apenas um deles tenha acesso por vez. Essa restrição reduz a concorrência.

Requisitos miniaturadaimagem|Figura 1: três processos tentam acessar simultaneamente um recurso compartilhado por meio de uma região crítica.

A sincronização de threads pode impedir que dois ou mais processos ou threads concorrentes executem simultaneamente um trecho do programa chamado região crítica. Técnicas de sincronização controlam o acesso a esse trecho, cuja execução deve ocorrer de forma serializada. Quando uma thread começa a executá-lo, outra que precise entrar na mesma região deve aguardar a sua saída. Sem a sincronização adequada, pode ocorrer uma condição de corrida, na qual os valores das variáveis se tornam imprevisíveis e dependem dos momentos em que ocorrem as trocas de contexto entre processos ou threads.

Por exemplo, três processos, numerados de 1 a 3, são executados de forma concorrente e precisam acessar um recurso compartilhado, como na figura 1. A sincronização evita conflitos de acesso a esse recurso. Se os processos 1 e 2 tentarem acessá-lo ao mesmo tempo, apenas um deles deverá receber a permissão. Caso o processo 1 a receba, o processo 2 terá de aguardar até que ele libere o recurso, como na figura 2.

miniaturadaimagem|Figura 2: um processo acessa um recurso compartilhado quando ele está disponível, com o acesso controlado por uma técnica de sincronização.

Outro requisito é a ordem de execução de determinados processos ou threads. É preciso comprar uma passagem antes de embarcar em um avião. Da mesma forma, a consulta a e-mails pode exigir a validação de credenciais, como nome de usuário e senha, e um caixa eletrônico exige o código de identificação pessoal correto antes de permitir uma operação. Esses exemplos correspondem a restrições de ordem entre eventos.

Além da exclusão mútua, a sincronização envolve outros problemas: Impasse, ou deadlock, que ocorre quando processos aguardam recursos mantidos uns pelos outros, formando uma espera da qual nenhum deles consegue sair. Os processos permanecem bloqueados e não avançam. Inanição, que ocorre quando um processo aguarda a entrada na região crítica, mas outros processos monopolizam o acesso e o obrigam a esperar indefinidamente. Inversão de prioridade, que ocorre quando um processo de prioridade alta fica bloqueado por outro de prioridade baixa que mantém um recurso necessário. Se um processo de prioridade intermediária interromper o de prioridade baixa, a espera do processo de prioridade alta pode se prolongar. Isso pode levar à perda de prazos em sistemas de tempo real. Espera ativa, que ocorre quando um processo verifica repetidamente se já pode acessar uma região crítica. Essas verificações consomem tempo de processamento que poderia ser usado por outros processos.

Minimização Reduzir a necessidade de sincronização é um dos desafios do projeto de algoritmos para a computação em exaescala. A sincronização pode consumir mais tempo que os próprios cálculos, sobretudo na computação distribuída. Sua redução é estudada há décadas, e o problema se acentua à medida que a capacidade de cálculo avança mais rapidamente que a redução da latência. Em experimentos com métodos iterativos para sistemas esparsos em supercomputadores distribuídos, as comunicações globais necessárias à sincronização consumiram a maior parte do tempo. O teste de desempenho High Performance Conjugate Gradient, ou HPCG, passou a avaliar esse tipo de cálculo e comunicação em supercomputadores, como complemento ao teste usado na classificação TOP500.

Problemas Entre os problemas clássicos de sincronização estão: O problema do produtor-consumidor, também chamado de problema do buffer limitado. O problema dos leitores e escritores. O problema do jantar dos filósofos.

Esses problemas são usados para avaliar propostas de mecanismos e primitivas de sincronização.

Sobrecarga A sobrecarga de sincronização pode reduzir o desempenho em ambientes de computação paralela. Reunir dados de processos distintos exige comunicação entre processos e operações de sincronização, o que pode tornar o custo maior que o processamento dos mesmos dados em uma única thread. Quando a região crítica contém pouco trabalho, o custo da sincronização pode superar o da execução desse trecho em duas ou mais ordens de grandeza.

Sincronização por hardware Há sistemas que oferecem suporte de hardware para proteger a execução de regiões críticas.

Um sistema com um único processador pode desabilitar interrupções para permitir que o código em execução prossiga sem preempção. Em sistemas com mais de um processador, desabilitar as interrupções de um processador não impede que os demais acessem o mesmo recurso, e estender esse controle a todos eles é ineficiente.

Para implementar a sincronização em multiprocessadores, são usadas primitivas de hardware capazes de ler e modificar uma posição de memória de forma atômica. Sem esse recurso, o custo de construir primitivas básicas de sincronização seria elevado e cresceria com a quantidade de processadores. Há diferentes formas de realizar essas operações. Elas permitem ler e modificar uma posição de memória e verificar se a operação ocorreu de forma atômica. A partir dessas primitivas, são construídos mecanismos de sincronização disponíveis aos programas, como bloqueios e barreiras. Em geral, os projetistas de computadores esperam que programadores de sistemas usem as primitivas básicas para construir bibliotecas de sincronização. Essa implementação exige cuidado e pode ser difícil.

Entre as instruções atômicas disponíveis no hardware estão test-and-set, que atua sobre uma palavra de memória, e compare-and-swap, que compara o valor armazenado com um valor esperado e, se forem iguais, o substitui por um novo valor.

Suporte em linguagens de programação Em Java, uma forma de evitar interferências entre threads e erros de consistência da memória é acrescentar a palavra-chave synchronized à declaração de um método de instância. Nesse caso, o bloqueio do objeto ao qual o método pertence controla a sincronização. Outra forma é envolver um trecho de código em um bloco synchronized(someObject) { ... }, o que permite um controle mais preciso. Para executá-lo, a thread precisa adquirir o bloqueio de someObject. O bloqueio é liberado automaticamente quando a thread sai do bloco. As alterações nas variáveis ficam visíveis a outras threads que adquiram o mesmo bloqueio. Qualquer objeto pode ser usado para isso, pois todo objeto Java tem um bloqueio intrínseco, também chamado de bloqueio de monitor.

Os blocos synchronized também permitem que as threads que os executam sinalizem eventos às que aguardam uma condição dentro do bloco. Ao chamar wait(), uma thread libera o bloqueio e espera. Outra thread pode notificá-la por meio de notify() ou notifyAll(). Antes de prosseguir, a thread notificada precisa adquirir o bloqueio novamente. Esse mecanismo combina as funções de mutexes e eventos em um monitor de sincronização.

O .NET Framework também oferece primitivas de sincronização. A sincronização exige cooperação, pois todas as threads precisam seguir o mesmo mecanismo antes de acessar recursos protegidos para obter resultados consistentes. Entre os mecanismos do .NET estão bloqueios, sinalização, tipos leves de sincronização, espera ativa e operações atômicas da classe Interlocked.

Há suporte à sincronização em muitas linguagens de programação. Também foram criadas linguagens síncronas para desenvolver aplicações embarcadas que exigem comportamento estritamente determinístico.

Implementação Spinlocks

Outra forma de implementar a sincronização é usar spinlocks. Antes de acessar um recurso compartilhado ou um trecho de código, o processador verifica um indicador. Se ele estiver livre, o processador o altera de forma atômica para sinalizar o bloqueio e prossegue com a execução da thread. Se estiver ocupado, a thread permanece em um laço, verificando repetidamente se o bloqueio foi liberado. Os spinlocks são adequados quando a espera dura poucos ciclos. Esperas longas desperdiçam ciclos do processador e podem prejudicar o desempenho.

Barreiras

As barreiras são simples de implementar e oferecem boa capacidade de resposta. Elas usam ciclos de espera para sincronizar as threads em pontos definidos do programa. Considere três threads executadas simultaneamente a partir da barreira 1. Após um intervalo t, a thread 1 chega à barreira 2, mas ainda precisa aguardar as threads 2 e 3 para que os dados necessários estejam disponíveis. Quando todas chegam à barreira 2, a execução pode prosseguir. Após outro intervalo t, a thread 1 chega à barreira 3 e precisa aguardar novamente as demais threads e os dados de que depende.

Nesse tipo de sincronização, as threads que chegam primeiro à barreira aguardam as outras. No exemplo, a thread 1 espera pelas threads 2 e 3. Essa espera pode reduzir o desempenho do processo.

O tempo de espera da i-ésima thread em uma barreira pode ser expresso como

,

em que é o tempo de espera, é a quantidade de threads que já chegaram e é a taxa de chegada das threads.

Nos experimentos de Meng e seus colaboradores, a espera nas barreiras consumiu até 35% do tempo total de execução.

Semáforos

Os semáforos são mecanismos de sinalização que permitem controlar o acesso de uma ou mais threads ou processos a um trecho do programa. Um semáforo mantém um contador inicializado com determinado valor. Quando uma thread obtém permissão para entrar, esse valor é decrementado. Ao sair, a thread o incrementa. Se o contador estiver em zero, uma nova thread não pode entrar e fica bloqueada caso opte por aguardar.

Os semáforos que permitem o acesso de apenas uma thread ou processo por vez são chamados de semáforos binários e se assemelham aos mutexes. O valor 1 permite a entrada, enquanto o valor 0 a impede.

Transação distribuída Em arquiteturas orientadas a eventos, transações síncronas podem usar o modelo de requisição e resposta. Há duas formas de implementá-lo: Criar duas filas de mensagens separadas, uma para as requisições e outra para as respostas. O produtor do evento deve aguardar a resposta. Criar uma fila temporária exclusiva para cada requisição.

Fundamentos matemáticos Na sincronização baseada em bloqueios, um processo adquire um bloqueio sobre um objeto para controlar o acesso a ele. Esse mecanismo é usado em bancos de dados e arquivos. Os bloqueios de arquivos podem permitir acesso compartilhado para leitura ou acesso exclusivo para escrita. O bloqueio compartilhado permite leitores simultâneos, enquanto o exclusivo impede que outros processos adquiram bloqueios incompatíveis sobre a mesma região.