Notas de Aula - MAC 5755 - Sistemas Operacionais Distribuídos

Aula 17 - 24/10/2001

Relógios são fundamentais não só nas nossas vidas mas também para o bom funcionamento de sistemas computacionais
Implementação de relógios em um computador é baseada em:

um cristal de quartzo (oscila milhares de vezes por segundo)
um registrador contador (soma um cada vez que o cristal oscila)
um registrador constante ( cada vez que o contador chega na constante, gera uma interrupção)
um timestamp de início fixo (e.g., 0:00 horas do dia 1 de janeiro de 1970)
um contador de tiques do relógio (quando ocorre um interrupção do relógio, soma um tique do relógio)

Para se obter hora basta somar o número de tiques ao timestamp do início dos tempos
Muitos algoritmos se baseiam no tempo marcado pelo relógio. Exemplos:

make do UNIX
uso de leases para consistência do cache do cliente em sistemas de arquivos distribuídos
medição de quanto tempo uma mensagem demora para ir do cliente ao servidor
medição de quanto tempo um agente móvel demora para migrar

Em sistemas como o SPRITE que realiza migração de processos de forma transparente ao processo, relógios não sincronizados podem levar a erros no comportamento do processo

Para a maior parte das aplicações, os relógios não precisam estar totalmente sincronizados.
Em geral, precisamos apenas de que o sistema nos forneça uma visão consistente do tempo

nunca podemos ter a impressão de que o tempo andou para trás
se sabemos que um evento aconteceu depois do outro, o tempo de um tem que vir depois do outro também

Lamport, 1978: um dos artigos mais citados em Sistemas Distribuídos e em Ciência da Computação!
Definição da relação acontece-antes:

Se a e b são eventos na mesma máquina e a ocorre antes de b, então a -> b
Se a é o evento correspondente ao envio de uma mensagem e b é o evento correspondente ao recebimento desta mesma mensagem, então a -> b

acontece-antes é uma relação transitiva
A partir desta definição, Lamport definiu um algoritmo para implementação de relógios lógicos:

as diversas máquinas mantém seus relógios locais
quando uma mensagem é enviada de uma máquina para outra, a mensagem carrega o timestamp de envio
se quando uma mensagem chega ao destinatário, a hora de chegada é <= a hora de envio, o relógio do destinatário é adiantado para uma unidade de tempo depois da hora de envio

Uma limitação disso é que muitos eventos podem acabar acontecendo "ao mesmo tempo", i.e., o algoritmo define apenas uma ordem parcial
Se se deseja uma ordem total, uma alternativa é concatenar o número do processador ao final do tempo do relógio.
Assim, se dois eventos nos processadores 1 e 2 acontecem no instante 32 do relógio lógico, agora eles passam a acontecer nos instantes 32.1 e 32.2, respectivamente

Relógios lógicos não medem o tempo real
Muitas aplicações precisam saber do tempo real, seres humanos gostam de saber o tempo real
Inicialmente, tempo real era determinado pelos astrônomos

toma-se tempo entre 2 vezes consecutivas nas quais o sol atinge o ponto mais alto no céu
divide por 24*60*60 (ou seja, 86400) e obtém-se o segundo solar

o movimento de rotação da Terra não é constante devido às marés e ao atrito com a atmosfera
a rotação da Terra está ficando mais lenta; estudos com corais mostram que há 300M anos o ano tinha 400 dias!

Por isso, em 1948 com a invenção do relógio atômico, os físicos ganharam o trabalho de guardiões do tempo mundial
50 laboratórios ao redor do mundo tem relógios de Césio 133 e enviam, periodicamente, as suas horas para o Bureau International de l'Heure (BIU) em Paris. A médias desses tempos é o Tempo Atômico Internacional (TAI)
Mais um problema: como o segundo solar está ficando mais lento, o TAI tende a defasar do tempo real percebido pelos humanos
Solução: acrescenta-se um segundo bissexto de vez em quando para resincronizá-los
Esse tempo ajustado é chamado de Tempo Universal Coordenado (UTC)
O National Institute of Standard Time dos EUA tem uma estação de ondas curtas de alcance mundial que emite um pulso curto no início de cada segundo UTC
Alguns satélites ao redor da Terra também emitem estes pulsos
É possível comprar hardware que capta esses pulsos e sincronizam o relógio da sua máquina com o relógio oficial mundial
Depois de ter uma máquina na sua organização com a hora correta, é preciso passar essa informação para as outras máquina

periodicamente, um cliente manda uma pergunta "que horas são" para o servidor de tempo
o servidor de tempo responde o mais rápido possível com a nova hora
é necessário descontar o tempo que a resposta demorou para chegar de volta ao cliente
não dá prá saber ao certo, então usa-se a estimativa (T1 - T0)/2 onde T0 é quando a msg saiu do cliente e T1 quando a resposta chegou
melhor ainda: (T1-T0-I)/2 +I onde I é o tempo para o S.O. tratar da interrupção de chegada das mensagens
pode-se repetir isso N vezes e pegar a média. Ou então pegar o que resultou no menor tempo de envio da mensagem

não é prudente fazer o tempo voltar, é melhor tornar o relógio mais lento por algum tempo
não é prudente fazer o relógio saltar de uma vez, pode ser melhor acelerá-lo durante um certo tempo

todas máquinas dão broadcasts periódicos dizendo a hora no seu relógio
cada máquina faz uma média dos broadcasts que recebeu e acerta o seu relógio
pode-se melhorar o algoritmo descartando-se os m relógios mais atrasados e os m mais adiantados (tolerância a m relógios quebrados)

Protocolo para sincronização de relógios via Internet
Desenvolvido pela University of Delaware no Network Time Synchronization Project
baseado em hierarquias de máquinas com conexões ponto-a-ponto e/ou multicast
utiliza criptografia de chave pública para autenticação mútua
resolução de

1 ou 2 ms em redes locais
algumas poucas dezenas de ms em redes mundiais
quando há um suporte especial no núcleo do SO, a precisão pode chegar até a 1 nanosegundo

a versão atual estável e utilizada no mundo todo em vários SOs é a NTP 3
o NTP 4 está em desenvolvimento e aborda configuração automática: descoberta automática de servidores e autenticação segura automática
com isso, o NTP 4 será capaz de se proteger de ataques digitais em grande escala.
para maiores informações veja www.ntp.org

Relógios sincronizados espalhados mundialmente se tornaram possíveis nos últimos 10 anos
Com a diminuição do atraso nas redes modernas, a precisão da sincronia aumentou ainda mais
Assim, é possível que mais e mais aplicações vão começar a utilizar relógios sincronizados... (???)