Resumo Cap Sistemas Distribuidos

2021/1 – Sistemas Distribuídos

Lucas Luis de Souza Barreto – 21850961

Capítulo 6 – Sincronização

6.1 -  Sincronização de Relógios

Quando um processo quer saber a hora, faz uma chamada de sistema, e o núcleo responde. Se o processo A perguntar a hora e, um pouco mais tarde, o processo B também perguntar a hora, o valor que B obtém será mais alto (ou possivelmente igual ao valor que A obteve. Porém, por certo, não será mais baixo. Em um sistema distribuído, conseguir acordo nos horários não é trivial.  Em Unix, programas grandes normalmente são divididos em vários arquivos-fonte, de modo que uma alteração em um arquivo-fonte requer que apenas um arquivo seja recompilado, e não todos os arquivos. Há muitos outros exemplos em que é necessário um controle exatos de horários.

Quase todos os computadores têm um circuito especializado na passagem do tempo. No geral, são um cristal de quartzo, que conseguem oscilar a uma frequência definida. Associados a ele, estão um contador e um registrador de retenção, em que cada oscilação reduz uma unidade do contador.

Quando a contagem chega a zero, uma interrupção (chamada de ciclo de relógio) é gerada e o contador é recarregado. Desse modo, é possível programar um temporizador para gerar uma interrupção 60 vezes por segundo ou a qualquer outra frequência desejada. Cada interrupção é denominada ciclo de relógio. Quando o sistema é inicializado, ele usualmente solicita ao usuário que digite a data e a hora, que então são convertidas para o número de ciclos de relógio após alguma data inicial conhecida e armazenada na memória. A cada ciclo de relógio, o procedimento do serviço de interrupção soma uma unidade à hora armazena- da na memória. Desse modo, o relógio (de software) é mantido atualizado. Com um único computador e um único relógio, não há problema se esse relógio estiver um pouco defasado. Uma vez que todos os processos na máquina usam o mesmo relógio, eles ainda serão internamente consistentes. Com a introdução de CPUs múltiplas cada uma com seu relógio, garantir que todos os cristais oscilem na mesma frequência se tornou um desafio. Embora a frequuência à qual um oscilador de cristal funciona seja em geral razoavelmente estável, é impossível garantir que todos os cristais em diferentes computadores funcionem exatamente à mesma frequência. Na prática, quando um sistema tem n computadores, todos os n cristais funcionarão a taxas ligeiramente diferentes, o que faz com que os relógios (de software) gradativamente saiam de sincronia e informem valores diferentes quando lidos. Essa diferença nos valores dos horários é denominada defasagem de relógio.

Esse problema de posicionamento é, em si, resolvido por meio de um sistema distribuído dedicado altamente específico denominado GPS, que é um acrônimo para global positioning system (sistema de posicionamento global). O GPS usa 29 satélites, cada um circulando em uma órbita a uma altura aproximada de 20.000 km. Cada satélite tem até quatro relógios atômicos que são calibrados periodicamente por estações especiais na Terra. Um satélite transmite continuamente sua posição em broadcast e anexa marcas de tempo a cada mensagem, informando sua hora local. Essa transmissão broadcast permite que todo receptor na Terra calcule com precisão sua própria posição usando, em princípio, somente três satélites. Para explicar, a princípio vamos considerar que todos os relógios, entre eles o do receptor, estejam sincronizados.

Diversos algoritmos foram propostos com o intuito de sincronizar relógios e todos seguem o mesmo princípio: cada máquina tem um temporizador que provoca interrupção H vezes por segundo. Quando o temporizador esgota o tempo fixado, o manipulador de interrupção soma 1 a um relógio de software que monitora o número de interrupções. O valor desse relógio é chamado de C. O ideal seria que a hora UTC seja igual a hora do relógio, porém temporizadores reais não interrompem exatamente H vezes por segundo: existe um erro relativo que depende do chip do computador e o fabricante especifica uma taxa máxima de deriva, que especifica até que ponto a defasagem do relógio pode chegar. Uma abordagem é permitir que os clientes consultem um servidor de tempo. O servidor pode informar a hora com exatidão, porém o problema decorre dos atrasos de mensagem na comunicação. Uma solução é estimar a diferença temporal entre o horário da requisição e a hora da resposta, porém isto poderia gerar problemas caso o cliente estivesse adiantado. No caso do protocolo de tempo de rede (NTP), o ajuste acontece com pares de servidores, ou seja, o servidor também consulta o cliente para saber sua hora. Em muitos algoritmos como o NTP, o servidor de tempo é passivo, onde outras máquinas lhe perguntam a hora e ele responde. Na abordagem de Berkeley, o servidor de tempo é ativo e consulta todas as máquinas para perguntar de cada uma qual hora está marcando. Com base nas respostas e na média, ele informa as máquinas sobre atrasos ou adiantamentos necessários. Estes algoritmos são vantajosos para SDs tradicionais, porém, em redes sem fio, os nós são restritos e o roteamento é caro, além de que são necessários algoritmos para otimizar energia. Um algoritmo é o de sincronização em broadcast de referência (RBS), que ao invés de adotar que há apenas um nó com o valor exato da hora, ele visa sincronizar os relógios no âmbito interno, além de manter o remetente fora do ciclo de comunicação. Em RBS, um remetente transmite uma mensagem de referência em broadcast que permite que os receptores ajustem seus relógios.

6.2 -  Relógios Lógicos

A sincronização de relógios está naturalmente relacionada com a hora real. Todavia, pode ser suficiente que cada nó concorde com uma hora corrente, sem que essa hora seja a mesma que a hora real, o convencional é denominar esses relógios como relógios lógicos. Lamport mostrou que, embora a sincronização entre relógios seja possível, não precisa ser absoluta, pois se dois processos não interagem, não há razão para que seus relógios sejam sincronizados. Desta maneira, não é fundamental que todos os processos concordem com a hora exata, mas com a ordem em que os eventos ocorrem. Para fazer a sincronização de relógios lógicos, Lamport definiu a relação conhecida como "acontece antes". A expressão "a acontece antes de b" significa que todos os processos concordam que o evento a ocorre e posteriormente o evento b ocorre. Um exemplo da aplicação desta expressão é no envio de uma mensagem por um processo, em que a é o evento de envio da mensagem e b é o evento de recebimento.