Sd05 (si) relógios e sincronização

Sistemas Distribuídos II

Parte 02Relógios e Sincronização

O Problema da Sincronia de Tempo

• Não há garantias de que dois ou mais processos cooperantes interpretem a contagem de tempo igualmente

– Cada processo pode estar em uma máquina diferente, o que significa que cada um pode estar usando um relógio físico diferente

– Não há como garantir que os dois relógios estão exatamente sincronizados (na verdade, isso é quase impossível)

O Problema da Sincronia de Tempo

• Que problemas isso pode gerar?– Não há como garantir a troca de mensagens

síncrona• A execução de eventos em determinada de sequência

pode ser comprometida– Não há como garantir a exclusão mútua• A alocação de recursos compartilhados pode falhar

– O monitoramento de eventos se turna mais complexo• Não há como determinar quando exatamente um

determinado evento ocorreu, o que pode comprometer a reação desejada

O Problema da Sincronia de Tempo (cont.)

• Como solucionar o problema?–Opção 1: Solução Centralizada• Funcionamento: Todos os processos envolvidos

em determinada atividade usam como referência uma única fonte de tempo (um relógio único, um processo,...)• Vantagem: – A garantia de que todos estão obtendo a informação

de tempo no mesmo lugar, o que evita informações inconsistentes

O Problema da Sincronia de Tempo (cont.)

• Como solucionar o problema?–Opção 1: Solução Centralizada• Problemas:– A fonte única de tempo também é um ponto único de

falha, ou seja, diante de uma pane na fonte de tempo todos os processos são comprometidos– Dependendo da quantidade de processos envolvidos, a

fonte de tempo pode se sobrecarregar com a quantidade de mensagens de/para ela– As mensagens com informações de tempo podem

sofrer atrasos imprevisíveis durante seu tráfego na rede, comprometendo a exatidão

O Problema da Sincronia de Tempo (cont.)• Como solucionar o problema? (cont.)– Opção 2: Solução Distribuída• Funcionamento: • Vários processos se encarregam de regular as

informações de tempo, comparando e fazendo ajustes entre si

O Problema da Sincronia de Tempo (cont.)• Como solucionar o problema? (cont.)– Opção 2: Solução Distribuída• Vantagem:

– Não há um ponto único de falha. A queda de um único processo não interfere na sincronização do tempo entre os demais

– Maior disponibilidade da informação de tempo, já que não há uma fonte única

• Problemas:– Maior complexidade para implementar a solução – Quantidade variável de mensagens (nem sempre previsível)

O Problema da Sincronia de Tempo (cont.)• Como solucionar o problema? (cont.)– A opção distribuída (opção 2) é a mais adequada

para ambientes distribuídos porque:

• As informações relevantes ao processo estão dispersas por várias máquinas• Cada processo deve tomar decisões baseado somente

em informações locais• A existência de um ponto único de falha deve ser

evitada sempre que for póssível• Não existe um relógio único para todas as máquinas

Relógios Lógicos

• Em algumas tarefas distribuídas, o tempo real não é importante. – O foco do controle de tempo é voltado para a

correta sequência de eventos que deve acontecer• A informação de tempo neste caso é usada

como um contador de eventos, que determina o que deve acontecer a cada momento

Relógios Lógicos

• A solução de Lamport– Em 1978, Leslie Lamport publicou uma proposta de

ordenação de eventos baseada em tempo, onde:– Não há tempo absoluto – toda a informação de

tempo é relativa entre os procesos que trocam mensagens– Se dois processos não interagem entre si, não há

necessidade de sincronização de tempo entre eles– Na maioria das vezes é necessário que os processos

concordem com a informação de tempo entre eles, mas este tempo não precisa ser real

Algoritmo de Lamport• Funcionamento do algoritmo:

• Cada processo cooperante tem seu próprio relógio lógico (independente do tempo real), que serve como contador de eventos– Cada evento ocorrido incrementa uma unidade de tempo no

contador• Cada mensagem trocada entre dois processos cooperantes contém uma

informação de tempo (relógio lógico) fornecida pelo emissor da mensagem

• O processo receptor compara a informação de tempo contida na mensagem com seu próprio relógio lógico:– Se seu relógio lógico possuir um valor maior que o tempo contido na

mensagem, o relógio permanece com o mesmo valor– Se seu relógio lógico possuir um valor menor ou igual que o tempo

contido na mensagem, o relógio é ajustado e passa a ter o valor da mensagem mais um

• Isso garante que dois eventos nunca aconteçam ao mesmo tempo

Algoritmo de Lamport (exemplo)

• Imagine três processos (P1, P2 e P3) localizados em máquinas diferentes que iniciam algum tipo de interação sincronizada– Os 3 processos iniciam seus relógios lógicos, mas cada

clock físico oscila em frequencias diferentes• Suponha:

– O clock lógico de P1 varia de 6 em 6 unidades– O clock lógico de P2 varia de 8 em 8 unidades– O clock lógico de P3 varia de 10 em 10 unidades

• No primeiro instante, todos os relógios estão zerados• No segundo instante, os relógios lógicos já não estão iguais (P1=6,

P2=8 e P3=10)• Esta variação aumenta conforma os instantes se passam

(exemplo: no instante 5 P1=24, P2=32 e P3=40)


– Cada mensagem trocada entre os processos precisa conter o valor que o relógio físico de seu emissor para que o receptor faça os ajustes necessários

• No instante 2 a mensagem A é enviada de P1 para P2• No instante 4 a mensagem B é enviada de P2 para P3• No instante 7 a mensagem C é enviada de P3 para P2• No instante 9 a mensagem D é enviada de P2 para P1

– Considere que cada mensagem enviada chega a seu destino no instante seguinte ao que foi enviada

• As mensagens A e B chegam a seus destinos sem causar impacto, pois o relógio lógico de cada receptor contém um valor maior que aquele que consta em cada mensagem

• As mensagens C e D obrigam seus receptores a efetuar um ajuste nos relógios lógicos para garantir a correta sincronia dos eventos


Instante Relógio P1 Relógio P2 Relógio P3

1 0 0 0

2 6 8 10

3 12 16 20

4 18 24 30

5 24 32 40

6 30 40 50

7 36 48 60

8 42 61 70

9 48 69 80

10 70 77 90

11 76 85 100

Mensagem A (6)

Mensagem B (24)

Mensagem C (60)

Mensagem D (69)

Não necessitade ajusteno relógio

Necessitade ajusteno relógio

Problema no Algoritmo de Lamport• Considere:

– R(e1) o valor do relógio lógico para o evento “e1”– R(e2) o valor do relógio lógico para o evento “e2”– A solução porposta por Lamport não garante que se R(e1) < R(e2)

então o evento “e1” acontece antes que o evento “e2”

• Exemplo:

– Se compararmos os valores de relógio em cada mensgaem, temos:• Msg-A (1) < Msg-B(4) então Msg-A ocorreu antes de Msg-B (correto)• Msg-C (3) < Msg-B(4) então Msg-C ocorreu antes de Msg-B (incorreto)

Processo P1 Processo P2 Processo P3

0 0 0

1 3 2

2 6 4

3 9 6

4 12 8

Msg A (1)

Msg B (4)

Msg C (3)

Solução Vetorial (Mattern e Fidge)

• Solução proposta por Mattern e Fidge:– O relógio lógico passa a ser um vetor contador de eventos– Se existem N processos cooperando, o vetor terá N posições

inteiras, onde cada posição corresponde a um contador de eventos

– Cada processo terá um vetor para si– Cada mensagem enviada contém a versão atualizada do vetor

do emissor

• Esta solução é muito usada em:– Verificação de consistência de estados em SD– Controle de checkpoints– Recuperação de erros– Rollbacks

Solução Vetorial (Mattern e Fidge)

• Funcionamento– Antes de cada evento em um processo, este incrementa mais 1 no valor de

sua posição no vetor– Sempre que uma mensagem é enviada, o processo inclui uma cópia de seu

vetor na mensagem– No recebimento de uma mensagem, o processo atualiza o seu vetor a partir

do vetor da mensagem.• Ao receber uma mensagem, o processo faz uma operação de integração

(merge) entre o vetor recebido e seu próprio vetor local, atualizando os dados deste último

– Sua posição no vetor assume o valor máximo existente no vetor da mensagem

– O valor do contador correspondente ao emissor é incrementado em uma unidade caso seu valor local já não seja maior que o recebido;

– Uma vez atualizado o vetor local, é possível determinar a ordem dos eventos comparando-se o valor de cada posição dos vetores em cada evento

Solução Vetorial (Exemplo)

Solução Vetorial

• Desvantagem da solução:– Ocupa-se mais espaço de armazenamento e carga útil da

mensagem

• Uma solução derivada dos relógios vetoriais:– “Relógios de matriz”

• Além de seu próprio vetor, cada processo mantém estimativas do tempo vetorial dos outros processos

Relógios Físicos

• O algoritmo de Lamport e as demais soluções de relógios lógicos se preocupam apenas com a ordenação de eventos– Os instantes de tempo associados a cada evento não são

necessariamente próximos do tempo em que os eventos realmente aconteceram

• Em alguns sistemas o conhecimento do instante de tempo real é muito importante (exemplo: sistemas de tempo real)– Para este tipo de sistema são necessários clocks físicos externos

• Em certos casos, é desejável a existência de mais de um clock externo, para garantir eficiência e redundância

– Problemas:• Como sincronizá-los com o tempo real?• Como sincronizar esses clocks entre si?

Evolução da Marcação de Tempo

• Primeiras soluções para marcação de tempo– Relógios de sol, estações do ano, ...– Dia solar: intervalo decorrido entre duas

passagens consecutivas do Sol em determinado ponto do céu

• Século XVII: primeiros relógios mecânicos– Quanto maior a qualidade do processo de

fabricação, mais preciso o processo de marcação do tempo

– Ainda era muito difícil garantir uma sincronia de tempo eficiente


• Década de 1940: Ajustes para compensar imprecisões– Foram feitos ajustes artificiais na marcação

oficial de tempo para compensar imprecisões resultantes de fenômenos naturais que influenciam diretamente nas fontes de tempo utilizadas

• Descobriu-se que a rotação da terra não é constante, devido às marés e a atmosfera (desaceleram a rotação da Terra)

• A duração do ano (em dias) diminuiu (os dias ficaram mais longos)

• O turbulências no núcleo do planeta influenciam no comprimento do dia


• Em 1948: invenção do relógio atômico– Contagem de segundos a partir

das transições de elétrons de um átomo de Césio 133• É uma medida mais precisa

e constante, que não sofre influências externas


• Atualmente:– TAI (Tempo Atômico Internacional)

• Média de tempo dos relógios atômicos• É mais preciso, porém ainda é necessário ajustá-lo a contagem de

tempo solar adotada no dia-a-dia

• Ajuste do TAI (Tempo Atômico Internacional)

– UTC (Tempo Universal Coordenado)• É o TAI ajustado ao tempo solar• O ajuste é feito inserindo-se segundos “bissextos”• Vem gradativamente substituindo o uso do GMT• Acesso: NIST (rádio WWV) e GEOS (Satélite)


• Relógio Atômico Brasileiro (USP)


• NIST – National Institute of Standards and Technology


• GEOS

Algoritmo de Cristian

• Funcionamento:• Usa um servidor de tempo, que é um computador equipado com receptor

UTC• As demais máquinas enviam mensagens para o servidor de tempo

perguntando pelo tempo corrente• O servidor de tempo responde o mais rápido possível, com uma

mensagem contendo o tempo UTC corrente• Cada máquina, ao obter a resposta, ajusta seu clock• O servidor de tempo é PASSIVO. O ajuste depende da inciativa das demais

máquinas

• Problemas:• O tempo nunca pode andar para trás (os ajustes são sempre progressivos)• A consulta ao servidor de tempo gasta um tempo não-nulo (o retardo

pode vir a ser grande)

Algoritmo de Cristian (cont.)

• Mais um problema:– É uma solução altamente centralizada

• Para minimizar a centralização, pode-se adotar os seguintes caminhos:– Ter vários servidores com receptor UTC– As demais máquinas passam a solicitar a hora por meio de mensagens

multicast

• Esta solução é um algorítmo probabilístico, ou seja:– Só se obtém uma sincronização aceitável se o tempo de ida e volta

das mensagens forem curtos o suficiente se comparados a precisão desejada


• Solução para os ajustes sempre progressivos• A mudança no clock deve ser feita de forma gradativa e

sempre avançando o relógio• Se o ajuste é de 10 ms, basta adicionar 9 ms para

atrazar ou 11 ms para adiantar


• Solução para o retardo na mensagem • Tentar medir (estimativa) o tempo de transmissão

T0 .................. tempo de envio da requisição

T1 .................. recebimento da resposta

(T1 - T0)/2 ....... tempo aproximado de propagação da mensagem

I .................... tempo de tratamento da interrupção

(T1 - T0 - I)/2 ... estimativa ainda mais precisa

• Outra solução:– Realizar várias medidas e calcular a médias de tempo

(descartando valores fora de um certo limite)

Algoritmo de Berkeley

• Funcionamento• O servidor de tempo é uma entidade ATIVA, que consulta periodicamente cada

uma das máquinas do sistema para saber o tempo corrente em cada uma delas• Baseado nas respostas obtidas:

– Calcula o tempo médio e o ajuste que cada máquina terá que fazer

– Informa às demais máquinas para adiantar ou atrasar seus clocks, tornando-se iguais ao tempo médio calculado

– Não informa a hora corrente e sim o ajuste a ser feito– O cálculo que o servidor faz também leva em conta a

existência de respostas “absurdas” (muito fora da média das demais máquinas).

– Estas repostas “absurdas” são descartadas do cáculo de ajuste para evitar um desvio indesejado dos resultados

Algoritmo de Berkeley

• A precisão deste algoritmo também depende do tempo máximo gasto pelas mensagens de ida e volta

• Indicado para:– Quando nenhuma das máquinas tem um receptor

UTC– A necessidade de precisão no ambiente é

pequena

Algoritmo de Berkeley (cont.)

• Problemas:– O ajuste do servidor de tempo deve ser feito

periodicamente por um operador (de forma manual)

– É uma solução altamente centralizada• Para contornar esta fragilidade, ao se perceber que o

servidor de tempo falhou, elege-se outro servidor para o seu lugar• O problema agora passa a ser como determinar que o

servidor de tempo falhou

Network Time Protocol

• Os algorítmos de Cristian e Berkeley , embora eficientes, se dedicam mais a redes pequenas e intranets– Em ambientes com uma grande quantidade de

máquinas, como a Internet, é quase impossível garantir o bom funcionamento destas duas soluções• Pela natureza assíncrona das operações

desempenhadas na web• Pela ausência de garantia de entrega de mensagens em

um tempo razoável

Network Time Protocol (cont.)

• O NTP foi projetado como um serviço e protocolo para distribuir informações de tempo pela Internet

• Objetivos:– Ser um serviço para clientes internet se sincronizarem

pelo UTC, superando atrasos e perdas de mensagens• Isso é feito por meio de técnicas estatísticas de

filtragem da informação– Fornecer um serviço confiável que sobreviva a longas

perdas de conectividade• Usando servidores e rotas redundantes para circulação

das mensagens


• Características:– Permite sincronização razoavelmente frequente

dos clientes• Para compensar falhas originadas na

quantidade de clientes e servidores interagindo– Fornece proteção ao serviço de tempo contra

interferências acidentais ou intencionais• Autenticação, validação de mensagens


• Funcionamento:– O NTP é formado por uma rede de servidores na

internet divididos pela seguinte hierarquia:• Servidores Primários

– São máquinas conectadas diretamente a uma fonte de tempo UTC

• Servidores Secundários– Servidores que se sincronizam com os servidores primários

• Demais servidores– Organizados em uma estrutura de árvore– Cada “galho” se sincroniza com sua “raiz”– A “árvore” é composta de sub-redes de sincronização


• Funcionamento:– Cada nível da árvore é chamado de “stratum”

• Stratum 1: servidores primários (raiz)• Stratum 2: servidores secundários• Stratum 3: outros servidores• Stratum 4: mais servidores• e assim por diante...

– Quanto mais alto o número do stratum, a tendência é que a precisão seja menor neste nível

– É possível realizar alterações na hierarquia para superar indisponibilidade de serviço. Por exemplo:• “Promover” máquinas mapa um stratum mais alto• Deslocar “galhos” inteiros para se sincronizarem com outros servidores


• Como a sincronia é feita?– As mensagens são transmitidas via protocolo UDP

– A mensagem pode ser enviada de 3 modos:• Modo 1: Multicast – Ideal para redes locais de alta velocidade– Servidores de tempo enviam mensagem e as demais

máquinas ajustam seus relógios– Possui uma margem de erro grande, que resulta em

baixa precisão


• Modo 2: RPC– Usa a solução de Cristian para sincronizar– É mais preciso que a opção de multicast

• Modo 3: Simétrico – Adotado em máquinas cujo stratum é baixo– É a opção mais precisa–Os servidores trocam mesagens de tempo entre si e

as informações são armazenadas para uso posterior visando melhorar cada vez mais a sincronia

Documents

Sd05 (si) relógios e sincronização