Sincronização em Sistemas Distribuidos

UNIVERSIDADE ESTADUAL DO MARANHÃO - UEMA
CENTRO DE CIÊNCIAS TECNOLÓGICAS
ENGENHARIA DA COMPUTAÇÃO
SISTEMAS DISTRIBUIDOS
VINICIUS ANDRÉ MATOS SILVA
SINCRONIZAÇÃO EM SISTEMAS DISTRIBUIDOS
SÃO LUÍS-MA
2019
1. INTRODUÇÃO
Na definição de sistema distribuídos, tem-se que se trata de um conjunto de

unidades de processamentos independentes, que através da troca de comunicação
e gerenciamento de sincronização pode processar uma aplicação de diferentes
localidades em sistemas com características próprias diferentes. O conceito de
sincronização em sistema distribuído ocorre através da troca de mensagens.
A sincronização entre processos é tão importante quanto a comunicação entre

processos em sistemas distribuídos. A sincronização dos dados armazenados é um
ponto crucial em um sistema de dados distribuído, os servidores destes sistemas
muitas vezes precisam executar operações onde o tempo é muito importante.
A sincronização dos relógios dos servidores é muito importante, devido ao fato

de se houver divergência de horários entre os servidores, pode-se ter erros graves
nos processos, como a não compilação de um arquivo que não foi alterado após a
ultima compilação.
2. ALGORITMO DE CRISTIAN
O algoritmo de Cristian é um algoritmo de sincronização de relógio usado para
sincronizar a hora com um servidor de horas pelos processos do cliente. Esse
algoritmo funciona bem com redes de baixa latência, nas quais o tempo de
transferência é curto em comparação a precisão, enquanto os sistemas distribuídos,
propensos a redundância, não andam de mãos dadas com esse algoritmo
O algoritmo funciona da seguinte forma: a rede dispõe de um timer server
(receptor WWV). Uma maquina cliente envia uma mensagem pedindo a hora certa
ao “Time Server” e ao receber a mensagem resposta, o cliente adiciona o tempo
médio de envio de mensagens à hora recebida. Esse tempo médio é calculado pelo
próprio cliente considerando as horas de envio e recebimento as mensagens e ainda
o tempo gasto pelo “Time Server” para processar o pedido. Na figura 1 é mostrada
um exemplo de como funciona.
Figura 1. Algoritmo de Cristian
Fonte: http://www.ricardobarcelar.com.br/aulas/sd/7-sincronizacao.pdf
3. ALGORITMO DE BERKELEY
O algoritmo de Berkeley é uma técnica de sincronização de relógio usada em

sistemas distribuídos. O algoritmo assume que cada nó da máquina na rede, ou não
tem uma fonte de tempo preciso ou não possuir um servidor de UTC. Nesse
algoritmo, o “servidor de tempo” é ativo e consulta periodicamente cada uma das
maquina sobre os valores de seus relógios. Então calcula uma media das leituras
realizadas e informa cada maquina para que se ajuste, adiantando ou atrasando seu
relógio. Essa média pode ser simples ou ajustada, desprezando-se valores
extremos, o que permite contornar eventuais falhas em alguns relógios. Também é
possível considerar o tempo de comunicação entre as maquinas.
O algoritmo funciona da seguinte forma: Um nó individual é escolhido como nó

principal em um nó da rede. Este nó é o nó principal da rede que atua como mestre
e o restante dos nós atua como escravos. O nó mestre é escolhido usando um
processo de eleição (Leader Election Algorithm). O nó mestre periodicamente faz
“ping” nos nós dos escravos e busca a hora do relógio neles usando o algoritmo de
Cristian. E, por último, o nó mestre calcula a diferença de tempo média entre todos
os horários recebidos e a hora fornecida pelo próprio relógio do sistema
mestre. Essa diferença de tempo média é adicionada à hora atual no relógio do
sistema principal e transmitida pela rede. A figura a seguir (Figura 2) ilustra o
funcionamento do algoritmo de Berkeley
Figura 2. (a) O “Time Daemon” pede a todas as outras máquinas seus
valores de relógio. (b) As maquinas respondem. (c) O “Time” diz a todos como
ajustar seus relógios
Fonte: https://slideplayer.com/slide/13406711/
4. ALGORITMO DE LAMPORT
O algoritmo de exclusão mutua distribuída de Lamport é um algoritmo

baseado em permissão proposto por Lamport como uma ilustração de seu esquema
de sincronização para sistemas distribuídos.
Na permissão “timestamp” é usada para ordenar os pedidos de seção crítica e
para resolver qualquer conflito entre os pedidos.
No algoritmo de Lamport, as solicitações de seção crítica são executadas na
ordem crescente de registros de data e hora, ou seja, uma solicitação com registro
de data e hora menor recebe permissão para executar a seção crítica primeiro do
que uma solicitação com registro de data e hora maior.
O funcionamento do algoritmo se dá pela seguinte forma: Três tipos de

mensagens (request, reply e release) são usados e os canais de comunicação
assumem a ordem FIFO; Um site envia uma mensagem de “request” a todos os
outros sites para obter permissão para entrar na seção crítica; Um site envia
uma mensagem de “reply” ao site solicitante para dar sua permissão para entrar na
seção crítica; Um site envia uma mensagem de “release” para todos os outros sites
ao sair da seção crítica; Cada site S i , mantém uma fila para armazenar solicitações
de seção crítica ordenados por suas marcas de tempo; Request_queue i indica a fila
do site S i; Um registro de data e hora é fornecido para cada solicitação de seção
crítica usando o relógio lógico de Lamport; O registro de “timestamp” é usado para
determinar a prioridade de solicitações de seção críticas. Uma permissão
“timestamp” menor recebe alta prioridade sobre uma permissão “timestamp” maior e
a execução da solicitação de seção crítica está sempre na ordem da permissão
“timestamp”. Na figura seguinte é possível verificar um pouco o funcionamento
desse algoritmo (Figura 3).
Figura 3. Algoritmo de Lamport

Fonte: http://www.cs.fsu.edu/~xyuan/cop5611/lecture8.html
5. RELÓGIOS VETORIAIS
Os Relógios vetoriais podem ser definidos como um meio para determinar se
pares de eventos estão relacionados causalmente. Usando Relógios vetoriais os
“timestamp” são gerados para cada evento no sistema e seu relacionamento causal é
determinado pela comparação do mesmo.
O “timestamp” de um evento é uma n-tupla de números inteiros, em que n é
o número de processos.
Cada processo atribui um registro de data e hora para cada evento. O
“timestamp” é composto pelo tempo lógico desse processo e pelo último horário
conhecido de todos os outros processos
REFERÊNCIAS
MITCHELL, Donna. Vector Clocks. Disponível em:
http://courses.cs.vt.edu/~cs5204/fall00/vector_clocks.html#:~:targetText=Definition
%3A,determined%20by%20comparing%20those%timestamps. Acesso em: 07 nov.
2019.
FSU. Lecture #6: Dsitrbuted Mutual Exclusion. Disponível em:
http://www.cs.fsu.edu/~xyuan/cop5611/lecture8.html. Acesso em: 07 nov. 2019.
GeeksforGeeks. Lamport’s Algorithm for Matual Exclusion in Distributed System.

Disponível em: https://www.geeksforgeeks.org/lamports-algorithm-for-mutual-
exclusion-in-distributed-system/#:~:targetText=Lamport's%20Distributed%20Mutual
%20Exclusion%20Algorithm,resolve%20any%20conflict%20between%20requests.
Acesso em: 07 nov. 2019.
KALIM, Umar. Distributed Computing. Disponível em:

https://slideplayer.com/slide/13406711/. Acesso em: 07 nov. 2019.
SAINI, Harshit. Cristian’s Algorithm. Disponível em:

https://www.geeksforgeeks.org/cristians-algorithm/. Acesso em: 07 nov. 2019.
SAINI, Harshit. Berkeley’s Algorithm. Disponível em:

https://www.geeksforgeeks.org/berkeleys-algorithm/. Acesso em: 07 nov. 2019.
SEMIGHINI, Dirceu. Sincronização em Sistemas Distribuídos. Disponível em:

http://dirceuprofessor.blogspot.com/2014/04/sincronizacao.html. Acesso em: 07 nov.
2019.
BARCELAR, Ricardo. Sincronização. Disponível em:

http://www.ricardobarcelar.com.br/aulas/sd/7-sincronizacao.pdf. Acesso em: 07 nov.
2019.

Sincronização em Sistemas Distribuidos

Enviado por

Direitos autorais:

Formatos disponíveis

Sincronização em Sistemas Distribuidos

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Sincronização em Sistemas Distribuidos

Enviado por

Direitos autorais:

Formatos disponíveis

UNIVERSIDADE ESTADUAL DO MARANHÃO - UEMA

CENTRO DE CIÊNCIAS TECNOLÓGICAS

VINICIUS ANDRÉ MATOS SILVA

SINCRONIZAÇÃO EM SISTEMAS DISTRIBUIDOS

Na definição de sistema distribuídos, tem-se que se trata de um conjunto de

A sincronização entre processos é tão importante quanto a comunicação entre

A sincronização dos relógios dos servidores é muito importante, devido ao fato

O algoritmo de Berkeley é uma técnica de sincronização de relógio usada em

O algoritmo funciona da seguinte forma: Um nó individual é escolhido como nó

O algoritmo de exclusão mutua distribuída de Lamport é um algoritmo

O funcionamento do algoritmo se dá pela seguinte forma: Três tipos de

Figura 3. Algoritmo de Lamport

GeeksforGeeks. Lamport’s Algorithm for Matual Exclusion in Distributed System.

KALIM, Umar. Distributed Computing. Disponível em:

SAINI, Harshit. Cristian’s Algorithm. Disponível em:

SAINI, Harshit. Berkeley’s Algorithm. Disponível em:

SEMIGHINI, Dirceu. Sincronização em Sistemas Distribuídos. Disponível em:

BARCELAR, Ricardo. Sincronização. Disponível em:

Você também pode gostar