Sincronização (ciência da computação) - Synchronization (computer science)

Na ciência da computação , a sincronização se refere a um de dois conceitos distintos, mas relacionados: sincronização de processos e sincronização de dados . Sincronização processo refere-se à idéia de que vários processos estão a juntar-se ou aperto de mão em um determinado ponto, a fim de chegar a um acordo ou se comprometer com uma determinada seqüência de ação. A sincronização de dados refere-se à ideia de manter várias cópias de um conjunto de dados coerentes entre si ou para manter a integridade dos dados . As primitivas de sincronização de processos são comumente usadas para implementar a sincronização de dados.

A necessidade de sincronização

A necessidade de sincronização não surge apenas em sistemas multiprocessados, mas para qualquer tipo de processo simultâneo; mesmo em sistemas de processador único. A seguir mencionadas estão algumas das principais necessidades de sincronização:

Forquilhas e junções : quando um trabalho chega a um ponto de bifurcação, ele é dividido em N subtrabalhos que são atendidos por n tarefas. Depois de ser atendido, cada subtrabalho espera até que todos os outros subtrabalhos concluam o processamento. Em seguida, eles são unidos novamente e saem do sistema. Assim, a programação paralela requer sincronização, pois todos os processos paralelos esperam que vários outros processos ocorram.

Produtor-Consumidor: em uma relação produtor-consumidor, o processo do consumidor depende do processo do produtor até que os dados necessários tenham sido produzidos.

Recursos de uso exclusivo: quando vários processos dependem de um recurso e precisam acessá-lo ao mesmo tempo, o sistema operacional precisa garantir que apenas um processador o acesse em um determinado momento. Isso reduz a simultaneidade.

Sincronização de thread ou processo

Figura 1 : Três processos acessando um recurso compartilhado ( seção crítica ) simultaneamente.

A sincronização de threads é definida como um mecanismo que garante que dois ou mais processos ou threads simultâneos não executem simultaneamente algum segmento de programa específico conhecido como seção crítica . O acesso dos processos à seção crítica é controlado por meio de técnicas de sincronização. Quando um thread começa a executar a seção crítica (segmento serializado do programa), o outro thread deve esperar até que o primeiro thread termine. Se as técnicas de sincronização adequadas não forem aplicadas, isso pode causar uma condição de corrida em que os valores das variáveis ​​podem ser imprevisíveis e variam dependendo dos tempos de alternância de contexto dos processos ou threads.

Por exemplo, suponha que haja três processos, a saber, 1, 2 e 3. Todos os três estão executando simultaneamente e precisam compartilhar um recurso comum (seção crítica), conforme mostrado na Figura 1. A sincronização deve ser usada aqui para evite quaisquer conflitos para acessar este recurso compartilhado. Portanto, quando os processos 1 e 2 tentam acessar esse recurso, ele deve ser atribuído a apenas um processo por vez. Se for atribuído ao Processo 1, o outro processo (Processo 2) precisa esperar até que o Processo 1 libere esse recurso (conforme mostrado na Figura 2).

Figura 2 : Um processo acessando um recurso compartilhado, se disponível, com base em alguma técnica de sincronização.

Outro requisito de sincronização que deve ser considerado é a ordem em que determinados processos ou threads devem ser executados. Por exemplo, não se pode embarcar em um avião antes de comprar uma passagem. Da mesma forma, não se pode verificar e-mails antes de validar as credenciais apropriadas (por exemplo, nome de usuário e senha). Da mesma forma, um caixa eletrônico não fornecerá nenhum serviço até que receba um PIN correto.

Além da exclusão mútua, a sincronização também lida com o seguinte:

  • deadlock , que ocorre quando muitos processos estão esperando por um recurso compartilhado (seção crítica) que está sendo mantido por algum outro processo. Nesse caso, os processos simplesmente continuam esperando e não são mais executados;
  • fome , que ocorre quando um processo está esperando para entrar na seção crítica, mas outros processos monopolizam a seção crítica, e o primeiro processo é forçado a esperar indefinidamente;
  • inversão de prioridade , que ocorre quando um processo de alta prioridade está na seção crítica e é interrompido por um processo de média prioridade. Essa violação das regras de prioridade pode acontecer em certas circunstâncias e pode levar a sérias consequências em sistemas de tempo real;
  • ocupado esperando , que ocorre quando um processo pesquisa frequentemente para determinar se ele tem acesso a uma seção crítica. Esta pesquisa frequente rouba o tempo de processamento de outros processos.

Minimizando a sincronização

Um dos desafios para o projeto do algoritmo exascale é minimizar ou reduzir a sincronização. A sincronização leva mais tempo do que a computação, especialmente na computação distribuída. A redução da sincronização atraiu a atenção dos cientistas da computação por décadas. Considerando que se torna um problema cada vez mais significativo recentemente, à medida que a lacuna entre a melhoria da computação e o aumento da latência. Os experimentos mostraram que as comunicações (globais) devido à sincronização em computadores distribuídos têm uma participação dominada em um solucionador iterativo esparso. Esse problema está recebendo cada vez mais atenção após o surgimento de uma nova métrica de referência, o High Performance Conjugate Gradient (HPCG), para classificar os 500 melhores supercomputadores.

Problemas clássicos de sincronização

A seguir estão alguns problemas clássicos de sincronização:

Esses problemas são usados ​​para testar quase todos os esquemas de sincronização ou primitivos recentemente propostos.

Sincronização de hardware

Muitos sistemas fornecem suporte de hardware para código de seção crítica .

Um único processador ou sistema uniprocessador pode desabilitar interrupções executando o código atualmente em execução sem preempção , o que é muito ineficiente em sistemas multiprocessadores . "A capacidade principal que exigimos para implementar a sincronização em um multiprocessador é um conjunto de primitivos de hardware com a capacidade de ler e modificar atomicamente um local de memória. Sem esse recurso, o custo de construção de primitivos de sincronização básicos será muito alto e aumentará conforme a contagem do processador aumenta. Há uma série de formulações alternativas dos primitivos de hardware básicos, todos os quais fornecem a capacidade de ler e modificar atomicamente um local, junto com alguma maneira de dizer se a leitura e gravação foram realizadas atomicamente. Esses primitivos de hardware são os blocos de construção básicos usados ​​para construir uma ampla variedade de operações de sincronização no nível do usuário, incluindo coisas como travas e barreiras . Em geral, os arquitetos não esperam que os usuários empreguem os primitivos de hardware básicos, mas, em vez disso, esperam que os primitivos ser usado por programadores de sistema para construir uma biblioteca de sincronização, um processo que geralmente é complexo e complicado. " Muitos hardwares modernos fornecem instruções especiais de hardware atômico testando e configurando a palavra de memória ou comparando e trocando o conteúdo de duas palavras de memória.

Estratégias de sincronização em linguagens de programação

Em Java , para evitar interferência de encadeamento e erros de consistência de memória, blocos de código são agrupados em seções sincronizadas (lock_object) . Isso força qualquer thread a adquirir o referido objeto de bloqueio antes de executar o bloco. O bloqueio é automaticamente liberado quando o thread que adquiriu o bloqueio, e então está executando o bloco, sai do bloco ou entra no estado de espera dentro do bloco. Quaisquer atualizações de variáveis, feitas por uma thread em um bloco sincronizado, tornam-se visíveis para outras threads quando elas adquirem o bloqueio e executam o bloco de maneira semelhante.

Os blocos sincronizados Java , além de permitir exclusão mútua e consistência de memória, permitem a sinalização - ou seja, o envio de eventos de threads que adquiriram o bloqueio e estão executando o bloco de código para aqueles que estão aguardando o bloqueio dentro do bloco. Isso significa que as seções sincronizadas do Java combinam a funcionalidade de mutexes e eventos. Essa primitiva é conhecida como monitor de sincronização .

Qualquer objeto pode ser usado como bloqueio / monitor em Java. O objeto declarante é um objeto de bloqueio quando todo o método é marcado com synchronized .

O .NET Framework tem primitivos de sincronização. "A sincronização é projetada para ser cooperativa, exigindo que cada thread ou processo siga o mecanismo de sincronização antes de acessar recursos protegidos (seção crítica) para resultados consistentes." No .NET, bloqueio, sinalização, tipos de sincronização leves, spinwait e operações interlocked são alguns dos mecanismos relacionados à sincronização.

Implementação de Sincronização

Spinlock

Artigo principal: Spinlock

Outra maneira eficaz de implementar a sincronização é usando spinlocks. Antes de acessar qualquer recurso compartilhado ou parte do código, cada processador verifica um sinalizador. Se o sinalizador for redefinido, o processador definirá o sinalizador e continuará executando a thread. Mas, se o sinalizador estiver definido (bloqueado), os threads continuarão girando em um loop e verificarão se o sinalizador está definido ou não. Mas, spinlocks são eficazes apenas se o sinalizador for redefinido para ciclos mais baixos, caso contrário, pode levar a problemas de desempenho, pois desperdiça muitos ciclos do processador esperando.

Barreiras

Artigo principal: Barreira (ciência da computação)

As barreiras são simples de implementar e oferecem boa capacidade de resposta. Eles são baseados no conceito de implementação de ciclos de espera para fornecer sincronização. Considere três threads em execução simultaneamente, começando da barreira 1. Após o tempo t, o thread1 atinge a barreira 2, mas ainda tem que esperar que os threads 2 e 3 cheguem à barreira2, pois não possui os dados corretos. Assim que todos os fios alcançam a barreira 2, todos começam novamente. Após o tempo t, o encadeamento 1 atinge a barreira3, mas terá que esperar pelos encadeamentos 2 e 3 e pelos dados corretos novamente.

Portanto, na sincronização de barreira de vários encadeamentos, sempre haverá alguns encadeamentos que acabarão esperando por outros encadeamentos, pois no exemplo acima, o encadeamento 1 continua esperando os encadeamentos 2 e 3. Isso resulta em grave degradação do desempenho do processo.

A função de espera de sincronização de barreira para i th thread pode ser representada como:

(Wbarrier) i = f ((Tbarrier) i, (Rthread) i)

Onde Wbarrier é o tempo de espera por um encadeamento, Tbarrier é o número de encadeamentos que chegaram e Rthread é a taxa de chegada de encadeamentos.

Os experimentos mostram que 34% do tempo total de execução é gasto na espera de outros threads mais lentos.

Semáforos

Artigo principal: Semáforo (programação)

Os semáforos são mecanismos de sinalização que podem permitir que um ou mais threads / processadores acessem uma seção. Um Semaphore possui um sinalizador que possui um determinado valor fixo associado a ele e cada vez que um thread deseja acessar a seção, ele diminui o sinalizador. Da mesma forma, quando o thread sai da seção, o sinalizador é incrementado. Se o sinalizador for zero, o encadeamento não poderá acessar a seção e será bloqueado se escolher esperar.

Alguns semáforos permitiriam apenas um segmento ou processo na seção de código. Esses semáforos são chamados de semáforos binários e são muito semelhantes ao Mutex. Aqui, se o valor do semáforo for 1, o thread tem permissão para acessar e se o valor for 0, o acesso é negado.

Fundamentos matemáticos

A sincronização era originalmente um conceito baseado em processo pelo qual um bloqueio poderia ser obtido em um objeto. Seu uso principal era em bancos de dados. Existem dois tipos de bloqueio (arquivo) ; somente leitura e leitura / gravação. Os bloqueios somente leitura podem ser obtidos por muitos processos ou threads. Os bloqueios de leitor / gravador são exclusivos, pois só podem ser usados ​​por um único processo / thread por vez.

Embora os bloqueios tenham sido derivados para bancos de dados de arquivos, os dados também são compartilhados na memória entre processos e threads. Às vezes, mais de um objeto (ou arquivo) é bloqueado ao mesmo tempo. Se eles não forem bloqueados simultaneamente, eles podem se sobrepor, causando uma exceção de conflito.

Java e Ada têm apenas bloqueios exclusivos porque são baseados em encadeamento e dependem da instrução do processador de comparação e troca .

Uma base matemática abstrata para primitivas de sincronização é dada pelo monóide histórico . Existem também muitos dispositivos teóricos de nível superior, como cálculos de processo e redes de Petri , que podem ser construídos sobre o monóide histórico.

Exemplos de sincronização

A seguir estão alguns exemplos de sincronização com relação a diferentes plataformas.

Sincronização no Windows

O Windows oferece:

Sincronização em Linux

Linux oferece:

A ativação e desativação da preempção do kernel substituiu os spinlocks em sistemas com um processador. Antes da versão 2.6 do kernel, o Linux desabilitava a interrupção para implementar seções críticas curtas. Desde a versão 2.6 e posterior, o Linux é totalmente preventivo.

Sincronização em Solaris

Solaris fornece:

Sincronização de Pthreads

Pthreads é uma API independente de plataforma que fornece:

  • mutexes;
  • variáveis ​​de condição;
  • bloqueios leitor-escritor;
  • spinlocks;
  • barreiras .

Sincronização de dados

Artigo principal: Sincronização de dados
Figura 3: As alterações do servidor e do (s) cliente (s) são sincronizadas.

Um conceito distintamente diferente (mas relacionado) é o da sincronização de dados . Isso se refere à necessidade de manter várias cópias de um conjunto de dados coerentes entre si ou para manter a integridade dos dados , Figura 3. Por exemplo, a replicação de banco de dados é usada para manter várias cópias de dados sincronizadas com servidores de banco de dados que armazenam dados em diferentes locais .

Exemplos incluem:

Desafios na sincronização de dados

Alguns dos desafios que o usuário pode enfrentar na sincronização de dados:

  • complexidade dos formatos de dados;
  • pontualidade real;
  • segurança de dados;
  • qualidade de dados;
  • atuação.

Complexidade de formatos de dados

Os formatos de dados tendem a se tornar mais complexos com o tempo, conforme a organização cresce e evolui. Isso resulta não apenas na construção de interfaces simples entre os dois aplicativos (origem e destino), mas também na necessidade de transformar os dados ao passá-los para o aplicativo de destino. As ferramentas ETL (carregamento de transformação de extração) podem ser úteis neste estágio para gerenciar complexidades de formato de dados.

Tempo real

Em sistemas em tempo real, os clientes querem ver o status atual de seu pedido no e-shop, o status atual de uma entrega de pacote - um rastreamento de pacote em tempo real -, o saldo atual em sua conta, etc. Isso mostra a necessidade de um sistema em tempo real, que também está sendo atualizado para permitir um processo de manufatura tranquilo em tempo real, por exemplo, solicitar material quando a empresa está ficando sem estoque, sincronizar os pedidos do cliente com o processo de manufatura, etc. Na vida real, existem tantos exemplos em que o processamento em tempo real oferece vantagem competitiva e de sucesso.

Segurança de dados

Não existem regras e políticas fixas para garantir a segurança dos dados. Isso pode variar dependendo do sistema que você está usando. Mesmo que a segurança seja mantida corretamente no sistema de origem que captura os dados, os privilégios de segurança e de acesso às informações também devem ser aplicados nos sistemas de destino para evitar qualquer uso indevido potencial das informações. Este é um problema sério, especialmente quando se trata de lidar com informações secretas, confidenciais e pessoais. Portanto, devido à sensibilidade e confidencialidade, a transferência de dados e todas as informações intermediárias devem ser criptografadas.

Qualidade de dados

A qualidade dos dados é outra restrição séria. Para um melhor gerenciamento e para manter a boa qualidade dos dados, a prática comum é armazenar os dados em um local e compartilhá-los com pessoas diferentes e sistemas e / ou aplicativos diferentes de locais diferentes. Ajuda na prevenção de inconsistências nos dados.

atuação

Existem cinco fases diferentes envolvidas no processo de sincronização de dados:

Cada uma dessas etapas é crítica. No caso de grandes quantidades de dados, o processo de sincronização precisa ser cuidadosamente planejado e executado para evitar qualquer impacto negativo no desempenho.

Veja também

Referências

  • Schneider, Fred B. (1997). Na programação simultânea . Springer-Verlag New York, Inc. ISBN 978-0-387-94942-0.

links externos