Algoritmos de sincronização de tempo são amplamente utilizados.
Por exemplo, em sistemas Unix, o comando Make é usado apenas para compilar arquivos de código recentemente modificados. O comando Make usa o relógio do cliente em execução para determinar quais arquivos foram modificados. No entanto, se o código for colocado no servidor de arquivos e o horário do host que executa o comando make for diferente daquele do servidor de arquivos, o comando make poderá não funcionar corretamente.
Por exemplo, ao jogar Dota, vários clientes precisam de um relógio sincronizado para manter a imagem de todos consistente. , Por exemplo, o tempo do servidor de sincronização do computador PC pode atingir uma precisão de sincronização muito alta.
Algoritmo de sincronização de tempo
O algoritmo de sincronização de tempo possui as seguintes soluções:
Algoritmo de Cristian
O pano de fundo da aplicação do algoritmo Algoritmo de Cristian é principalmente quando um processo P é como um servidor S solicitando tempo:
1. P envia um pacote de solicitação para S para solicitar a hora.
2. Depois que S recebe o pacote de solicitação de P, ele adiciona o horário S atual ao pacote e o envia de volta.
3. Após P receber o pacote de dados, ele define a hora atual para T+RTT/2.
RTT representa um Round Trip Time, que é o tempo desde o envio de P até o recebimento de um pacote de dados. O algoritmo assume que o envio e o recebimento de pacotes levam o mesmo tempo na rede. E também se assume que o tempo de S é insignificante no processamento de solicitações. Com base nas suposições acima, o algoritmo pode ser melhorado da seguinte forma:
Envie vários pacotes de solicitação de P para S e, em seguida, considere o menor RTT como o RTT dividido por dois e adicione-o ao tempo incluído neste pacote.
Análise de precisão do algoritmo: Suponha que min seja o menor tempo de S a P e T seja o tempo incluído no RTT definido acima. Então, a faixa de tempo de configuração P deve ser [T+min, T+RTT-min]. Desta forma, a faixa de desvio de tempo está dentro de RTT-2min. A precisão do algoritmo melhorado deve ser RTT/2 min.
algoritmo Algoritmo de Berkeley
O ambiente de uso do algoritmo Berkeley é diferente do algoritmo Cristian. O algoritmo Cristian é usado quando um cliente solicita a hora correta de um servidor. O algoritmo de Berkeley é um algoritmo para sincronizar relógios entre vários clientes. O algoritmo específico é o seguinte:
1. Primeiro selecione um nó de um anel como Mestre por meio de Mudança e Algoritmo de Robert.
2. Um Mestre utiliza o algoritmo Cristian para solicitar o horário de cada nó.
3. O Mestre avalia o desvio de tempo de cada nó registrando o RTT médio e eliminando os RTTs com grandes desvios.
4. O Mestre envia o desvio de tempo de cada nó para cada nó, permitindo que os nós se corrijam.
Após o cliente receber a hora, em geral, ele não ajustará a hora atual. Porque isso causará alguns erros inexplicáveis no programa. Porque em muitos algoritmos, é uma suposição básica que o tempo não será ajustado de volta. Por exemplo, faça o comando.
Existe uma solução: basta deixar o relógio andar mais devagar. Reserve algum tempo para se ajustar ao horário correto.
Além disso, o algoritmo Change e o Algoritmo de Robert precisam ser discutidos. Este algoritmo é igual ao algoritmo de sincronização de tempo e é necessário ao jogar Dota. Quando o dota é inicializado, os relógios de cada jogador precisam ser sincronizados. Depois de ficar offline, um algoritmo específico deve ser usado para encontrar um novo host:
Mudança e Algoritmo de Robert
O algoritmo Change and Robert's Algorithm assume que cada Processo possui um UID e que pode haver um canal de comunicação sem direção em uma rede em forma de anel. O algoritmo é o seguinte:
1. Primeiro, cada nó do anel se identifica como não participante.
2. Quando um processo descobre que o host está offline, ele primeiro se identifica como participante e depois envia um pacote selecionado pelo host contendo seu próprio UID para o vizinho.
3. Quando o pacote de dados chega ao vizinho, ele primeiro o compara com seu próprio UID. Se o seu próprio UID for maior que esse UID, ele se identifica como participante, modifica o UID no pacote de dados e também o envia no pacote de dados. dados no sentido horário.
4. Quando um processo recebe um pacote de dados e descobre que o UID no pacote de dados é igual ao seu próprio UID, ele inicia a segunda fase do algoritmo:
5. Este processo se identifica como não participante e envia informações sobre o host selecionado ao vizinho, incluindo informações UID.
6. Este ciclo continua até que o processo retorne ao Processo selecionado como host. Todo o processo termina.
Este é um algoritmo para selecionar um host em um sistema distribuído. É claro que, em circunstâncias específicas, você pode alterar as condições de seleção, como escolher aquele com a velocidade de rede mais rápida ou a CPU mais rápida como host. Ao mesmo tempo, esse algoritmo também pode evitar a situação em que vários processos descobrem que o host está offline ao mesmo tempo e vários processos procuram o host ao mesmo tempo.
O pseudocódigo deste algoritmo pode ser descrito da seguinte forma:
Início: M:= eu:
Envie <i> para o vizinho;
Ao receber a mensagem <j>;
Se M<j então M:=j;
Envie <j> para o vizinho;
Elseif M=j então líder;
Endif;
Para análise detalhada da complexidade, modelos matemáticos e tabelas estatísticas deste algoritmo, consulte este artigo:
http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf
Este artigo analisa apenas vários algoritmos de sincronização de tempo em sistemas centralizados e não analisa algoritmos de sincronização de transmissão de referência e protocolo de tempo de rede em sistemas distribuídos. Estudarei NTP quando tiver tempo no futuro.