thesis

Algoritmos de Sincronizac~ao de Relogios
por Converg^encia n~ao Ponderada
em Redes de Difus~ao
Relatorio do
Trabalho Final de Curso
Antonio Casimiro Costa, no 30506
Setembro 1991
Agradecimentos
Ao Professor Paulo Verssimo e ao Engenheiro Lus Rodrigues. A sua orientac~ao, o seu
apoio e a sua crtica constituiram um incentivo imprescindvel para a realizac~ao deste trabalho.
A minha equipa de trabalho no INESC: Eng. Jose Ru
no, Eng. Henrique Fonseca e
Eng. Sergio Marcos, pelo esprito de camaradagem que demonstraram e pelas sugest~oes que
contribuiram para o enriquecimento deste trabalho.
Aos meus colegas de curso que sempre se disponibilizaram no sentido de me permitir uma
maior dedicac~ao a este trabalho, Alvaro Azevedo e Miguel Lopes e tambem aos meus colegas
Jo~ao Beleza, Jo~ao Almeida e Helder Leong.
Finalmente, aos meus pais, a minha irm~a e a Elisabete Soalheiro pelo apoio que sempre me
prestaram.
Indice
Indice
i
Lista das guras
iii
Lista das tabelas
v
1 Introduc~ao
1
2 Algoritmos de sincronizac~ao de relogios
3
2.1 De
nic~ao de conceitos : : : : : : : : : :
2.2 Sincronizac~ao interna : : : : : : : : : : :
2.2.1 Os problemas da ressincronizac~ao
2.2.2 Sincronizac~ao por software : : : :
2.2.3 Sincronizac~ao por hardware : : :
2.2.4 Sincronizac~ao Hbrida : : : : : :
2.3 Sincronizac~ao externa : : : : : : : : : : :
3 Algoritmo de Srikanth
3.1 Descric~ao do algoritmo : : : :
3.1.1 Algoritmo n~ao optimo
3.1.2 Algoritmo optimo : : :
3.2 Inicializac~ao e integrac~ao : : :
3.3 Sincronizac~ao contnua : : : :
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
4 Algoritmo de Acordo \a posteriori"
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
3
6
7
10
10
11
11
13
13
13
15
16
17
19
i
4.1 Melhoria da precis~ao : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19
4.2 Descric~ao do algoritmo : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20
4.3 O servico de tempo do xAMp : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23
5 Realizac~ao
5.1 Ambiente de suporte : : : : : : : : : : : : :
5.1.1 Sistema operativo e rede distribuda :
5.1.2 Ambiente de suporte local : : : : : :
5.1.3 dclock : : : : : : : : : : : : : : : : :
5.1.4 Outras aplicac~oes : : : : : : : : : : :
5.2 Descric~ao da realizac~ao : : : : : : : : : : : :
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
27
27
27
28
29
30
30
6 Resultados
33
7 Conclus~oes
37
Bibliograa
39
A Servico de tempo do xAMp - Manual do utilizador
41
A.1 Introduction : : : : : : : : : : : :
A.2 General concepts : : : : : : : : :
A.3 User interface : : : : : : : : : : :
A.3.1 Initialization : : : : : : : :
A.3.2 Reading the time : : : : :
A.3.3 Stopping synchronization :
A.4 Implementation notes : : : : : : :
A.5 An application example : : : : : :
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
ii
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
41
41
42
42
45
46
46
47
Lista de Figuras
2.1 Relogios fsicos e virtuais na sincronizac~ao interna. : : : : : : : : : : : : : : : : : 7
2.2 Relogios fsicos e virtuais na sincronizac~ao externa. : : : : : : : : : : : : : : : : 12
3.1 Sincronizac~ao instant^anea e contnua. : : : : : : : : : : : : : : : : : : : : : : : : 17
5.1 Monitorizaca~o dos relogios virtuais atraves do utilitario dclock. : : : : : : : : : : 29
iii
iv
Lista de Tabelas
6.1 Valores obtidos nas medic~oes efectuadas no nvel exterior a interface com a rede. 34
6.2 Valores obtidos nas medic~oes efectuadas no nvel da interface com a rede. : : : : 34
6.3 Erros na precis~ao dos timers dos LSE. : : : : : : : : : : : : : : : : : : : : : : : : 35
v
vi
Captulo 1
Introduc~ao
A sincronizac~ao de relogios e o processo pelo qual podemos assegurar que o tempo apresentado por cada elemento de um sistema distribudo, permanece proximo do tempo apresentado
por todos os outros elementos desse sistema.
Considera-se que um sistema distribudo e constituido por um conjunto de processadores
ligados entre si com a capacidade de troca de informac~ao. A cada um dos processadores do
sistema esta associado um relogio. A sincronizac~ao de relogios pode ser conseguida a custa da
troca de mensagens entre os processadores que constituem o sistema distribudo. O tratamento
das mensagens trocadas entre os processadores e feito utilizando algoritmos de sincronizac~ao
de relogios.
Embora a proximidade entre o tempo apresentado por dois elementos seja limitada, podemos falar num tempo global comum a todos os elementos da rede. Esta noc~ao de tempo
global do sistema distribuido sera particularmente util a aplicac~oes que tenham de utilizar os
tempos fornecidos por maquinas sicamente distintas. Como exemplo, podemos pensar numa
aplicaca~o que pretenda determinar o tempo de durac~ao de uma dada acc~ao, sendo o instante
inicial dessa acc~ao lido num processador e o instante nal registado num outro processador.
Se houver uma disparidade no tempo apresentado pelos dois relogios envolvidos, o tempo de
durac~ao da acc~ao medido n~ao corresponde ao tempo real da sua duraca~o. Um outro exemplo
da utilidade do tempo global ser~ao as aplicac~oes onde e exigida a coordenac~ao temporal entre
elementos de uma rede distribuda na execuc~ao de acc~oes interdependentes. O sucesso global
destas acc~oes so sera conseguido se os relogios dos elementos da rede estiverem sincronizados.
Neste trabalho propomo-nos estudar dois exemplos de uma classe de algoritmos de sincronizaca~o de relogios, conhecidos por algoritmos de converg^encia n~ao ponderada: o algoritmo
de Srikanth Srikanth 87] e o algoritmo de Acordo a posterioriRodrigues 91b]. As raz~oes que
levaram a escolha destes algoritmos relacionam-se directamente com o facto de o nosso trabalho
ser desenvolvido no seio do projecto Delta-41. A participac~ao do INESC neste projecto envolve
O projecto Delta-4 e um consorcio CEC Esprit II, formado pela Ferranti-CSL (GB), Bull (F), Credit Agricole
(F), IEI (I), IITB (D), INESC (P), LAAS (F), LGI (F), MARI (GB), NCSR (GB), Renault (F), SEMA (F),
Un. of Newcastle (GB).
1
1
a realizac~ao de um servico de tempo2 baseado num algoritmo de sincronizaca~o de relogios. Para
realizar o servico de tempo era necessaria a escolha de um algoritmo de sincronizac~ao ja existente
ou a concepc~ao de um novo. Prevaleceu esta segunda soluc~ao, tendo sido concebido o algoritmo
de Acordo a posteriori que, naturalmente, se tornou objecto do nosso estudo. Como preparac~ao para este estudo, decidimos estudar previamente um algoritmo que envolvesse conceitos
e apresentasse caractersticas semelhantes, mas cuja realizac~ao fosse mais simples. Foi ent~ao
escolhido o algoritmo de Srikanth.
A realizac~ao destes algoritmos e a veri
cac~ao do seu correcto funcionamento constituem o
principal objectivo deste trabalho. Esta realizac~ao sera feita sobre dois ambientes de execuc~ao distintos: o sistema operativo UNIX e o executivo de tempo real SPART. A percepc~ao das
vantagens e desvantagens inerentes a utilizac~ao de cada um destes sistemas pode ser considerada
outro objectivo do trabalho.
De uma forma geral, o objectivo deste trabalho e assim a compreens~ao dos conceitos,
tecnicas e propriedades relativos a sincronizac~ao de relogios.
Este trabalho esta organizado do seguinte modo: no captulo 2 sera feita uma abordagem
dos conceitos que est~ao directamente ligados a sincronizac~ao de relogios. Veremos quais s~ao
as limitac~oes, impostas por um sistema generico de processadores ligados em rede, ao sincronismo dos relogios destes processadores. Veremos, tambem, como pode ser caracterizado
genericamente um algoritmo de sincronizac~ao de relogios. Finalmente, veremos que tipos de
sincronizac~ao podem ser considerados e como poder~ao ser classi
cados. Os dois algoritmos
que s~ao estudados neste trabalho, v^em descritos nos captulos 3 e 4. O captulo 5 aborda a
realizac~ao dos algoritmos e tudo o que com ela esta relacionado, como sejam o ambiente de
suporte e as aplicaco~es utilizadas para o desenvolvimento e teste do software. No captulo 6 s~ao
apresentados alguns resultados obtidos e no ultimo captulo, alem de referidas as perspectivas
futuras, s~ao esbocadas algumas conclus~oes referentes ao trabalho realizado.
2
Este servico de tempo constitui uma parte integrante de um conjunto bastante mais vasto de software, o
xAMp, que iremos referir com mais relevo na secc~ao 4.3.
2
Captulo 2
Algoritmos de sincronizac~ao de relogios
Nos sistemas de processamento distribudo, e muitas vezes necessario o sincronismo entre
relogios do sistema. A falta de sincronismo e um problema que se deve ao facto de os relogios
fsicos apresentarem taxas de desvio n~ao nulas em relac~ao ao tempo real.
Existem varias abordagens possveis ao problema. Os estudos efectuados podem ser classi
cados em sincronizac~ao por software Lamport 85, Lundelius 84, Halpern 84, Srikanth 87] ou
por hardware Kopetz 87]. Existem tambem aproximac~oes que utilizam um esquema hbrido de
sincronizac~ao por software com monitorizac~ao por hardware Ramanathan 90, Kopetz 87].
Todos estes tipos de sincronizac~ao s~ao considerados tipos de sincronizac~ao interna, ou
seja, todos os elementos utilizados na sincronizac~ao s~ao elementos internos a rede. Tambem e
possvel realizar uma sincronizaca~o externa, que se baseia na utilizac~ao de um indicador externo
de tempo, acessvel a todos os nos da rede. Estudos sobre sincronizaca~o externa podem ser
encontrados em Cristian 89] e Kopetz 89]. Nas secc~oes 2.2 e 2.3 sera feita uma abordagem
destes dois tipos de sincronizac~ao. Na secc~ao seguinte s~ao de
nidos termos e conceitos basicos
relativos aos algoritmos de sincronizac~ao de relogios.
2.1 Denic~ao de conceitos
Os sistemas cujos relogios se pretendem sincronizar podem apresentar faltas. Estas faltas
podem ser classi
cadas em tr^es tipos Verissimo 89b]:
Faltas arbitrarias
As faltas arbitrarias correpondem a n~ao execuc~ao de acc~oes especi
cadas ou a sua incorrecta execuc~ao.
Estas faltas s~ao tambem conhecidas como do tipo BizantinoLamport 82].
Faltas temporais
3
As faltas temporais acontecem quando as acc~oes s~ao executadas correctamente mas com
avanco ou atraso em relac~ao a especi
cac~ao.
Faltas de omiss~ao
Estas faltas admitem que determinadas acc~oes n~ao sejam executadas. No entanto, as
acco~es executadas s~ao-no correctamente.
Dependendo do tipo de faltas que se pretende tolerar, s~ao impostos requisitos relativamente ao numero de nos necessarios para atingir a sincronizac~ao. Lamport e Melliar-Smith
Lamport 85] mostraram que na presenca de um unico processador com faltas arbitrarias n~ao
e possvel garantir a sincronizac~ao dos relogios correctos num sistema com tr^es nos1. Para tal,
s~ao necessarios 3f + 1 relogios, sendo f o numero de faltas que se admitem.
Note-se que a maior parte dos algoritmos existente e tolerante a todos os tipos de faltas,
uma vez que este e um dos objectivos importantes na sincronizac~ao de relogios.
Apesar das diferencas existentes entre os varios tipos de sincronizac~ao, ha muitos conceitos
e de
nic~oes comuns a maioria deles. Convem, portanto, de
nir estes conceitos, que estar~ao
subjacentes ao longo de todo o trabalho.
Relogio fsico
Entende-se por relogio fsico o relogio que faz parte do hardware do sistema em utilizac~ao.
Ao tempo apresentado por este relogio chama-se tempo local. Por tempo real de
ne-se um
tempo n~ao directamente observavel, de
nido segundo uma norma internacional.
Relogio virtual
O objectivo dos algoritmos de sincronizac~ao de relogios e criar uma noc~ao de tempo
global em toda a rede. Este objectivo e atingido com a criac~ao de um relogio virtual em
cada no, o qual esta sincronizado com todos os relogios correctos do sistema. Considera-se o relogio virtual como uma func~ao que aplica o tempo real no tempo virtual. Assim,
a express~ao RVp (t) = T signi
ca que, no instante real t, o tempo lido no relogio virtual
RV do no p e T .
Utilizamos a nomenclatura RV para relogio virtual e RF para relogio fsico.
Taxa de desvio
Os relogios fsicos apresentam uma taxa de desvio n~ao nula em relac~ao ao tempo real.
Representa-se por a taxa maxima de desvio de todos os relogios correctos do sistema.
Se considerarmos o relogio fsico de um no i qualquer (RFi), temos que, para qualquer
t2 t1,
; RFi (t1 )
(1 + );1 RFi(t2t) ;
(1 + )
t
2
1
Considerando que n~ao existe autenticac~ao de mensagens.
4
1
(2.1)
De modo a tornar mais clara a leitura do texto decidimos designar 1 + ' por factor
de progress~ao, sendo ' a taxa de desvio. Assim, um relogio que tenha uma taxa de
desvio nula tera um factor de progress~ao unitario, ou seja, a cada unidade de tempo real
correspondera uma unidade de tempo local (medida nesse relogio).
Alguns autores apresentam como limite inferior para o factor de progress~ao o valor 1 ; em vez de (1+ );1 . Esta aproximac~ao e valida para valores tpicos de 10;6 , porque os
termos de ordem superior a primeira do desenvolvimento em serie de Taylor de (1 + );1
podem ser desprezados Ramanathan 90]:
(1 + );1 = 1 ; + 2 ; 3 + 4 ; ::: 1 ; (2.2)
Precis~ao
A diferenca maxima () permitida entre dois tempos virtuais e uma imposic~ao (dentro
de certos limites) do utilizador. A precis~ao resultante da aplicac~ao de um algoritmo sera
tanto maior quanto menor for a diferenca maxima permitida entre dois tempos virtuais.
Dependendo da aplicac~ao que fara uso dos relogios sincronizados, as exig^encias em relac~ao
a precis~ao poder~ao variar. Como veremos adiante, para aplicac~oes que exijam uma grande
precis~ao sera necessario utilizar algoritmos de sincronizac~ao por hardware. Considerando
dois processos correctos quaisquer, i e j , e um instante qualquer t, temos que:
jRVi (t) ; RVj (t)j (2.3)
Exactid~ao
A exactid~ao refere-se a diferenca que existe entre um tempo virtual e o tempo real absoluto.
A semelhanca da express~ao 2.1, de
ne-se uma express~ao para o desvio dos relogios virtuais
em relaca~o ao tempo real. Sendo RVi (t) o relogio virtual do no i e a sua maxima taxa
de desvio, temos que, para qualquer t2 t1:
RVi (t1) (1 + )
(1 + );1 RVi (t2t) ;
;t
(2.4)
jRVi (t) ; tj (2.5)
2
1
Note-se que e uma medida da exactid~ao dos relogios virtuais.
No caso da sincronizaca~o externa e possvel garantir que o tempo virtual se mantenha
proximo do tempo real uma vez que existe uma fonte externa de tempo. Assim e valida
a seguinte propriedade:
onde RVi (t) e o relogio virtual do no i e o valor maximo da diferenca entre o tempo
virtual e o tempo real absoluto.
Processo incorrecto
Visto considerar-se a exist^encia de uma taxa maxima de desvio, n~ao e possvel, numa
situac~ao normal, a exist^encia de um relogio fsico que se afaste do tempo real a uma taxa
5
superior a essa. Se tal acontecer, diz-se que o processo ao qual esta associado o relogio
e um processo incorrecto2. Um processo incorrecto e tambem aquele que n~ao executa as
acc~oes segundo a especi
cac~ao.
Ressincronizac~ao, Intervalo de ressincronizac~ao
Devido a taxa de desvio dos relogios virtuais, e necessario realizar uma ressincronizac~ao
periodica destes relogios. A ressincronizac~ao consiste num ajuste que e efectuado aos
relogios virtuais, de modo a que estes se voltem a aproximar. Ao intervalo de tempo
entre duas ressincronizac~oes consecutivas da-se o nome de intervalo de ressincronizac~ao.
A durac~ao deste intervalo depende fundamentalmente do afastamento maximo permitido
entre dois tempos virtuais e da taxa maxima de desvio dos relogios fsicos ().
Tempo de entrega
Quando se envia uma mensagem atraves da rede existe um intervalo de tempo associado
a preparac~ao, envio e recepc~ao desta mensagem. A este intervalo de tempo da-se o nome
de tempo de entrega, ;e . A import^ancia do tempo de entrega deve-se ao facto de ele n~ao
ser constante. Em certos algoritmos, a variac~ao do tempo de entrega limita a precis~ao
que e possvel atingir.
2.2 Sincronizac~ao interna
Nos algoritmos de sincronizac~ao interna n~ao e utilizada nenhuma refer^encia do tempo real.
Assim, a exactid~ao dos relogios virtuais e limitada pela taxa de desvio dos relogios fsicos.
Existem algoritmos que garantem uma taxa de desvio maxima para os relogios virtuais igual
a maxima taxa de desvio dos relogios fsicos ( = ). Nesta situac~ao os relogios virtuais
apresentam uma exactid~ao optimaSrikanth 87]. Srikanth prova que n~ao e possvel garantir
uma taxa de desvio dos relogios virtuais inferior a .
Em relaca~o a precis~ao pode dizer-se que esta depende fundamentalmente de dois par^ametros: do intervalo de ressincronizac~ao, pois a diferenca entre os relogios virtuais aumenta
proporcionalmente a este intervalo e da variac~ao do tempo de entrega ;e , ja que esta variac~ao
introduz um erro desconhecido na leitura de um relogio remoto.
A sincronizac~ao interna tem ent~ao como objectivos a exactid~ao optima e a maxima precis~ao
possvel, de modo a criar a noc~ao de um tempo global.
Na gura 2.1 e possvel identi
car uma situac~ao de sincronizac~ao interna.
A ressincronizaca~o processa-se da seguinte forma: seja ti o instante em que devera ser
realizada a iesima ressincronizac~ao no no p. Neste instante e calculado o ajuste AJFpi a efectuar
ao relogio fsico, para o voltar a aproximar dos outros relogios do sistema. Este ajuste e
traduzido na criac~ao de um novo relogio virtual RVpi , inicializado com o valor RFpi(ti) + AJFpi
e que sera utilizado pelo processador durante o proximo intervalo de ressincronizaca~o.
2
Muitos autores n~ao fazem distinc~ao entre processo e relogio correcto.
6
Tempo lido nos relogios
Recta do
tempo "real"
RF1
RV1
Diferenca maxima
do tempo virtual
RV2
RF2
Instante de
ressincronizacao
Intervalo de
ressincronizacao
Tempo "real"
Figura 2.1: Relogios fsicos e virtuais na sincronizac~ao interna.
Relativamente ao relogio virtual que estava a ser utilizado (RVpi;1 ) e tambem feito um ajuste
AJVpi que corresponde a diferenca RVpi(ti) ; RVpi;1(ti), dependendo portanto de AJFpi. Se o
relogio RVpi re ectir imediatamente o ajuste AJVpi podem existir descontinuidades no tempo
virtual, denominando-se esta sincronizac~ao instant^anea. Alem disso, se o ajuste for negativo,
a sincronizac~ao pode levar a inconsist^encias do tempo local uma vez que RVpi e atrasado em
relac~ao a RVpi;1. Para que tal n~ao aconteca e necessario distribuir AJVpi por todo o intervalo
de ressincronizac~ao, devendo garantir-se que este intervalo e superior ao ajuste a efectuar. Este
tipo de sincronizac~ao designa-se contnua.
O ajuste ao relogio fsico a efectuar e calculado a partir de uma func~ao de converg^encia
tolerante a faltas, FC:
i
i
i
AJFpi+1 = FC (RVpi(ti) RVpi 1(ti) ::: RVpN
;1(t )) ; RFp (t )
(2.6)
RVpki (ti) e o valor do relogio virtual k lido pelo processador p, e N e o numero total de nos
da rede.
2.2.1 Os problemas da ressincronizac~ao
A especi
cac~ao de um algoritmo de sincronizac~ao de relogios envolve a resoluc~ao de tr^es
problemas Schneider 87]:
O modo como se decide dar incio a ressincronizac~ao.
7
O modo como s~ao lidos os relogios virtuais dos nos da rede.
A escolha da func~ao de converg^encia que permite o calculo do ajuste a efectuar ao relogio
virtual.
As diferencas entre os algoritmos existentes est~ao condicionadas pelas soluc~oes encontradas
na resoluc~ao destes tr^es problemas.
~o
Incio da ressincronizaca
O incio da ressincronizac~ao coincide, em determinados algoritmos, com um instante previamente determinado (por exemplo, quando RVi (t) = T ) Schneider 87]. Noutros casos e enviada
uma mensagem quando RVi (t) = T , mas a ressincronizac~ao so comeca quando se recebem f +1
mensagens do mesmo tipo (sendo f o numero maximo de processos incorrectos) Srikanth 87].
Ao intervalo de tempo que se inicia no instante em que o primeiro processador correcto decide
ressincronizar e que termina no instante em que e feita a ultima ressincronizac~ao da-se o nome
de perodo de ressincronizaca~o.
gios virtuais
Leitura dos relo
Como exemplo de diferentes formas de leitura dos relogios virtuais, temos que alguns algoritmos disseminam o seu tempo virtual por toda a rede Srikanth 87], ao passo que outros fornecem o seu tempo virtual a medida que e pedido por cada um dos outros nos Ramanathan 90,
Schneider 87].
O modo de leitura dos tempos pode tambem ser diferente conforme o tipo de faltas que
se pretende tolerar. De qualquer forma, e conveniente que os algoritmos sejam tolerantes a
todos os tipos de faltas. A toler^ancia a faltas e considerada uma caracterstica indispensavel
dos algoritmos de sincronizac~ao Kopetz 87].
~ es de converg^encia
Funco
As func~oes de converg^encia utilizam os tempos virtuais lidos nos processadores remotos
para calcular o ajuste a efectuar ao relogio fsico local.
Consideremos uma rede com N processadores dos quais f podem ser incorrectos. Diz-se
que FC e uma func~ao de converg^encia se veri
car as seguintes propriedades Schneider 87]:
Monotonia
Esta propriedade garante que um aumento de todos os N ; 1 argumentos, correspondentes
aos processadores remotos, leva a um aumento do valor da func~ao FC (para um mesmo
valor de tempo local, nos dois calculos de FC ).
8
Invari^ancia na translaca~o
Se a todos os N argumentos da func~ao for adicionada uma constante (incluindo o primeiro,
que corresponde ao tempo local), o resultado da func~ao n~ao sera alterado. Isto signi
ca
que para o calculo do ajuste AJFpi apenas interessam as diferencas relativas entre os
tempos virtuais e n~ao o seu valor absoluto.
Melhoria da precis~ao
Quando FC e calculada por dois processadores distintos e N ; f argumentos correspondentes s~ao semelhantes (apresentando diferencas inferiores a ) os resultados obtidos est~ao
mais proximos que os seus argumentos.
Preservac~ao da exactid~ao
Esta propriedade indica que o valor da funca~o FC se mantem proximo do valor do tempo
local. E necessario que cada um dos N ; f argumentos se encontre numa vizinhanca dos restantes N ; f ; 1.
A caracterizac~ao da melhoria da precis~ao e da preservac~ao da exactid~ao e feita atraves de
duas funco~es, respectivamente, ( ) e (). E assim possvel classi
car diversas func~oes de
converg^encia.
Como exemplos de func~oes de converg^encia utilizadas em algoritmos de sincronizac~ao podemos referir as seguintes Schneider 87]:
Media egoc^entrica Lamport 85]
FCME(p q1:::qN ;1) e a media de todos os argumentos q1 a qN ;1 que se encontram numa
vizinhanca de p.
Algoritmo de converg^encia rapida Mahaney 85]
FCACR(p q1:::qN ;1) e a media de todos os argumentos q1 a qN ;1 que se encontram numa
vizinhanca de pelo menos outros N ; f .
Mediana tolerante a faltas Dolev 83]
FCMedi(p q1:::qN ;1) e a mediana de todos os argumentos q1 a qN ;1, depois de terem sido
desprezados os f maiores e os f menores valores.
Media tolerante a faltas Dolev 83, Lundelius 84]
FCMTF (p q1:::qN ;1) e a media de todos os argumentos q1 a qN ;1 , depois de terem sido
desprezados os f maiores e os f menores valores.
Um estudo comparativo de varias func~oes de converg^encia (em termos das func~oes ( )
e ()) pode ser encontrado em Schneider 87].
9
2.2.2 Sincronizac~ao por software
A sincronizac~ao por software e a mais largamente analisada e discutida, ja que e a que apresenta maior facilidade de realizac~ao e mais baixos custos. No entanto, este tipo de sincronizac~ao
apresenta tambem algumas desvantagens inerentes ao facto de a troca de mensagens ser o seu
suporte essencial: havera uma sobrecarga adicional da rede e as diferencas entre os relogios
sincronizados ir~ao depender do tempo maximo de entrega das mensagens.
Note-se que apesar destas desvantagens poderem ser atenuadas (se o intervalo de ressincronizac~ao for longo e se a variac~ao maxima do tempo de entrega for bastante inferior a
diferenca maxima desejada para os relogios virtuais) s~ao elas que limitam o uso deste tipo de
sincronizac~ao.
E possvel classi
car os diferentes algoritmos de sincronizac~ao por software da seguinte
forma Ramanathan 90]:
(
8>
< Converg^encia ponderada
n~ao ponderada
>:
Consist^encia
A diferenca existente entre os algoritmos de converg^encia ponderada (exemplos em
Lamport 85, Lundelius 84]) e os de converg^encia n~ao ponderada (exemplos em Halpern 84,
Srikanth 87]) consiste no modo como e determinado o ajuste a efectuar periodicamente aos
relogios virtuais. Nos algoritmos de converg^encia ponderada o ajuste e determinado por aplicac~ao de uma func~ao de converg^encia aos tempos lidos nos relogios remotos. Assim, todos os
relogios virtuais entram em conta na escolha do ajuste. Na sincronizac~ao por converg^encia
n~ao ponderada cada processador tenta impor-se como sincronizador do sistema. Em cada
ressincronizaca~o apenas um dos processadores correctos se torna o sincronizador, ou seja, o
ajuste a efectuar aos relogios virtuais e calculado apenas em func~ao do tempo fornecido pelo
relogio do processador sincronizador.
Os algoritmos de converg^encia ponderada diferem na func~ao de converg^encia tolerante a
faltas a aplicar enquanto que os de converg^encia n~ao ponderada diferem no modo como e feita
a escolha do processador sincronizador (que e um processador correcto).
Uma vantagem dos algoritmos por converg^encia n~ao ponderada e n~ao exigirem a exist^encia
de uma rede totalmente ligada. No entanto, nestes algoritmos e necessaria a exist^encia de um
mecanismo de autenticaca~o de mensagens, o qual n~ao devera permitir a alterac~ao de mensagens
nem a sua imitac~ao por parte de um no que n~ao o emissor da mensagem original.
2.2.3 Sincronizac~ao por hardware
A grande vantagem da sincronizac~ao por hardware reside no facto de esta conduzir a extrema
concord^ancia entre todos os nos da rede. Tem, no entanto, algumas desvantagens:
E necessaria uma rede paralela para troca de mensagens.
10
Os custos s~ao superiores a sincronizac~ao por software.
A realizac~ao e mais difcil.
A sincronizac~ao por hardware e utilizada nos casos em que a sincronizac~ao por software n~ao
consegue garantir a precis~ao desejada. Segundo Ramanathan 90], utilizando a sincronizac~ao
por hardware e possvel garantir diferencas maximas entre os relogios virtuais da ordem das
dezenas de nanosegundos, contrastando com diferencas da ordem das dezenas de milisegundos
no caso de sincronizac~ao por software.
2.2.4 Sincronizac~ao Hbrida
Este tipo de sincronizac~ao pretende aproveitar as vantagens das sincronizac~oes por software
e por hardware, aliando o custo reduzido da primeira a precis~ao proporcionada pela segunda.
Utiliza-se um algoritmo convencional de sincronizac~ao por software para sincronizar periodicamente os relogios mas, por forma a tornar negligvel a in u^encia do tempo de entrega variavel
na execuc~ao desse algoritmo, usa-se a sincronizac~ao por hardware que permite determinar com
exactid~ao o tempo de tr^ansito das mensagens na rede. Apenas e necessario que alguns dos nos
estejam ligados em rede paralela executando a sincronizac~ao por hardware para garantir uma
melhoria substancial do desempenho do sistema, sem elevar consideravelmente o custo total.
No esquema de sincronizaca~o hbrida proposto em Ramanathan 90] obt^em-se melhorias,
no que se refere ao afastamento dos relogios virtuais, da ordem do dobro ou triplo relativamente
a sincronizac~ao por software.
2.3 Sincronizac~ao externa
A sincronizac~ao externa permite que os relogios virtuais sejam mais exactos do que os
relogios fsicos correspondentes.
Este tipo de sincronizaca~o pressup~oe a exist^encia de uma fonte externa de tempo real
que e utilizada na execuc~ao do algoritmo. Normalmente, para que os custos da sincronizaca~o n~ao sejam muito elevados, apenas alguns processadores t^em acesso a fonte externa. Estes
processadores ter~ao que disseminar o tempo lido na fonte externa, de modo a que seja mantida
a exactid~ao de todos os relogios virtuais.
A gura 2.2 ilustra uma hipotetica situac~ao de sincronizac~ao externa. Podemos observar
que durante o intervalo de ressincronizaca~o a taxa de desvio do relogio fsico e do relogio virtual
correspondente s~ao iguais3. Observa-se tambem que a diferenca entre os tempos virtuais nunca
A aplicac~ao da express~ao 2.4 para t1 e t2 pertencentes ao mesmo intervalo de ressincronizac~ao n~ao revela
melhoria da exactid~ao. Neste caso, seria conveniente substituir esta express~ao por outra em que t1 = 0, ou seja,
denir a taxa de desvio relativamente ao instante inicial da sincronizac~ao e n~ao num intervalo de tempo.
3
11
e superior a e que estes tempos se mant^em sempre proximos do tempo real (veri
cando, assim,
a express~ao 2.5).
Neste exemplo, o tempo virtual no instante apos a ressincronizac~ao e igual ao tempo real.
Na verdade, existe sempre um erro na leitura da fonte externa de tempo, o que se traduz
numa pequena diferenca que n~ao e ilustrada nesta gura. Da mesma forma, o instante da
ressincronizac~ao e o mesmo para os dois processadores o que podera n~ao acontecer na realidade.
Recta do
tempo "real"
Tempo lido nos relogios
RF1
RV1
Diferenca maxima
do tempo virtual
RV
2
RF
Instante de
ressincronizacao
Intervalo de
ressincronizacao
2
Tempo "real"
Figura 2.2: Relogios fsicos e virtuais na sincronizac~ao externa.
Comparando com a gura 2.1 referente a sincronizac~ao interna, observa-se que a maior
diferenca se veri
ca na pouca exactid~ao daquela: ao m de algum tempo, e ainda que tenha
havido um acerto inicial, veri
ca-se um grande afastamento em relac~ao ao tempo real. Apenas
se mantem a precis~ao.
Normalmente a sincronizac~ao externa e utilizada como um complemento a sincronizac~ao
interna Kopetz 89]. Assim, sera possvel obter um esquema de sincronizac~ao com extrema
precis~ao e exactid~ao e, ao mesmo tempo, com um custo n~ao muito elevado.
Nos captulos que se seguem iremos descrever os algoritmos de Srikanth e de Acordo a posteriori. Estes dois algoritmos s~ao classi
cados como algoritmos por converg^encia n~ao ponderada,
justi
cando o ttulo deste relatorio.
12
Captulo 3
Algoritmo de Srikanth
Este algoritmo e, segundo os autores, o primeiro a apresentar uma exactid~ao para os relogios
virtuais t~ao boa quanto a dos relogios fsicos. Srikanth e Toueg mostram tambem que n~ao e
possvel atingir uma exactid~ao para os relogios virtuais superior a dos relogios fsicos.
O algoritmo prev^e todos os tipos de faltas, mesmo quando n~ao se considera a exist^encia de
autenticac~ao de mensagens. Neste ultimo caso, a autenticaca~o e substituida por uma primitiva
de comunicac~ao, tambem descrita por Srikanth. Com autenticac~ao de mensagens e possvel
atingir a sincronizac~ao desde que mais de metade dos processadores sejam correctos. Sem
autenticac~ao s~ao necessarios 3f + 1 processadores.
3.1 Descric~ao do algoritmo
A descric~ao que se segue do algoritmo e, naturalmente, baseada no artigo publicado por
Srikanth e TouegSrikanth 87].
3.1.1 Algoritmo n~ao optimo
Considere-se um sistema com N processadores que permite, no maximo, f processos incorrectos. O algoritmo imp~oe que
N 2f + 1
(3.1)
e que as mensagens sejam autenticadas.
Seja P o intervalo de ressincronizac~ao. Um processador espera pelo instante iP (lido no seu
relogio virtual) para poder comecar a iesima ressincronizaca~o. Assim, quando RVpi;1(t) = iP o
processador do no p envia a mensagem hreadyi pi indicando que esta pronto para o comeco da
ressincronizaca~o.
13
Designa-se por readyi o instante em que o primeiro processador correcto envia uma mensagem hreadyi, no iesimo ciclo de ressincronizac~ao.
Uma vez que podem existir f processadores faltosos, so apos receber f + 1 mensagens se
podera garantir que pelo menos um processador correcto esta pronto para ressincronizar.
Assim, apos receber a (f + 1)esima mensagem (que podera ser qualquer uma de entre
ent~ao criado
hready i 1i : : : hready i N i), esta e aceite dando-se incio a ressincronizac~ao. E
um novo relogio virtual, RV i, inicializado com o valor iP + (sendo uma constante).
Para que todos os processadores que ainda n~ao ressincronizaram1 o possam fazer, s~ao reenviadas, apos a ressincronizac~ao, as f + 1 mensagens recebidas. Desta forma garante-se que
em todos os nos sera lancado um novo relogio virtual, sendo o ultimo relogio lancado com
um intervalo maximo de ;e apos o primeiro. Na hipotese de uma toler^ancia mais restrita
a faltas (por exemplo, apenas faltas por omiss~ao) n~ao e necessario reenviar todas as f + 1
mensagens recebidas. Basta enviar uma unica mensagem, que, segundo Srikanth, poderia ser
hechoi, indicando implicitamente aos outros processadores para ressincronizarem.
O instante em que o primeiro processador correcto aceita uma mensagem hreadyi, iniciando
RV i, designa-se por begini. O ultimo ressincroniza no instante endi.
Como ja foi dito, RV i e inicializado com o valor iP + . A constante e dimensionada
de forma a impedir que RV i, quando inicializado, esteja atrasado em relaca~o a RV i;1. Assim,
tera de ser superior ao maior intervalo de tempo que pode decorrer desde readyi ate endi,
medido no relogio virtual do processador mais rapido.
No nal do perodo de ressincronizaca~o, ou seja, em endi, todos os relogios virtuais se
encontram proximos uns dos outros, isto e, dentro de um intervalo de amplitude igual ao
tempo que decorre desde begini ate endi (medido tambem no relogio virtual mais veloz).
Devido ao facto de esta sincronizac~ao ser instant^anea poder~ao existir descontinuidades do
tempo virtual lido num determinado relogio o que n~ao implica, no entanto, que n~ao haja monotonicidade (crescente) do tempo lido2. Como veremos e possvel evitar estas descontinuidades
mantendo a simplicidade do algoritmo.
Srikanth prova que este algoritmo veri
ca as propriedades da precis~ao (2.3) e da exactid~ao
(2.4). Esta prova sai fora do ^ambito deste relatorio n~ao sendo, portanto, aqui apresentada.
No caso de n~ao haver autenticac~ao das mensagens o algoritmo exige 3f + 1 processadores
para garantir a sincronizac~ao na presenca de f faltas. O envio de mensagens e realizado por uma
primitiva que veri
ca as propriedades necessarias para a prova de correcc~ao do algoritmo. Esta
primitiva funciona da seguinte forma: apos a recepc~ao das f + 1 mensagens hreadyii e enviada
uma mensagem hechoii. O incio da ressincronizac~ao corresponde ao instante de recepc~ao da
Esta situac~ao pode vericar-se no caso de haver omiss~oes. Se a (f +1)esima mensagem n~ao for recebida por
alguns processadores estes n~ao ressincronizam.
2 Apenas poderia n~
ao haver monotonicidade se RVp (t2) < RVp (t1 ) sendo t2 > t1 , o que se garante que n~ao
acontece ao dimensionar o valor de .
1
14
(f + 1)esima mensagem hechoi. Nesse instante e enviada outra mensagem hechoi para garantir
a ressincronizac~ao dos outros elementos (enquanto que com autenticac~ao eram reenviadas as
f + 1 mensagens recebidas). Note-se que a (f + 1)esima mensagem hreadyi n~ao e aceite (como
o era anteriormente), originando apenas o incio da troca de uma nova serie de mensagens.
3.1.2 Algoritmo optimo
O objectivo do algoritmo optimo e obter uma exactid~ao dos relogios virtuais t~ao boa quanto
a dos relogios fsicos. Assim, comecemos por examinar qual a taxa de desvio dos relogios mais
rapido e mais lento, no caso do algoritmo n~ao optimo.
Para tal convem relembrar que a taxa de desvio de um relogio virtual relaciona um intervalo
de tempo medido no relogio virtual com o correspondente intervalo de tempo real (express~ao
2.4).
No caso do relogio virtual mais rapido, o intervalo de tempo virtual que passa entre duas
ressincronizac~oes consecutivas e P ; , correspondendo a um incremento de P desse relogio.
O tempo real efectivo que decorre entre as ressincronizac~oes e (P ; )=(1 + ) sendo a taxa de
desvio resultante3
P (1 + ) ; 1
P ;
(3.2)
Para o relogio virtual mais lento o tempo virtual maximo que passa entre duas ressincronizac~oes e P ; + ;e (1 + );1 donde a taxa de desvio e
P
;1
P ; + ;e (1 + );1 (1 + ) ; 1
(3.3)
Com estes limites na taxa de desvio dos relogios virtuais n~ao e possvel obter uma sincronizac~ao optima. O factor de atraso que seria necessario aplicar ao relogio mais rapido para que este
n~ao se desviasse a uma taxa superior a faria com que o relogio mais lento n~ao fosse optimo.
Srikanth prop~oe um esquema em que os processos, ao aceitarem uma mensagem hreadyi,
comparam o seu relogio com iP + (sendo = ;e =2(1 + )). Se veri
carem que a mensagem
foi aceite cedo, o lancamento do novo relogio virtual sera retardado de caso contrario sera
antecipado de . Desta forma, o tempo real de durac~ao de um perodo de ressincronizac~ao sera,
em ambos os casos, P ; + , estando os relogios virtuais enquadrados na envolvente
P (1 + );1 t
P ;+
RVpi(t)
P (1 + )t
P ;+
(3.4)
Note-se que poderiamos apresentar a express~ao do factor de progress~ao em vez da taxa de desvio. Neste
caso o factor de progress~ao seria P (1 + )=(P ; ), ou seja, taxa de desvio + 1.
3
15
Aplicando o factor de atraso4 = P ; + consegue obter-se uma exactid~ao optima. Na
pratica, o processador ira utilizar um relogio RLp (t) = RVp(t)=. Note-se que a precis~ao dos
relogios virtuais n~ao e alterada uma vez que > 1. Em termos do algoritmo, o relogio RVp (t)
continuara a ser utilizado.
Este algoritmo optimo podera ser simpli
cado no caso de ser utilizada a sincronizac~ao
contnua. Como veremos, e possvel tornar = 1 passando o processador a utilizar directamente
o relogio RVp (t) em vez de RLp (t).
3.2 Inicializac~ao e integrac~ao
A inicializac~ao do protocolo, ou seja, a forma como e obtida a sincronizac~ao inicial, e feita
recorrendo ao algoritmo ja descrito, da mesma forma que uma sincronizac~ao normal. Assim, o
processador p envia a mensagem hready0 pi indicando a pretens~ao de iniciar a sincronizac~ao.
Apos a recepc~ao de su
cientes mensagens hready0i o processador inicializa o primeiro relogio
virtual fazendo RVp0 = . No instante end0 os relogios virtuais apresentar~ao uma diferenca
maxima de ;e (1 + ) entre eles, o que garante o futuro bom funcionamento do protocolo (em
particular, sera respeitada a precis~ao).
Note-se que um processador correcto podera car inde
nidamente a espera que pelo menos
um outro processador correcto pretenda tambem iniciar o protocolo, o que n~ao altera a forma
como e realizada a sincronizac~ao inicial.
Quando um processo p pretende juntar-se a um grupo de processos que est~ao ja sincronizados entre eles envia uma mensagem hjoin pi. Recebera ent~ao respostas indicando o numero
do ciclo de ressincronizac~ao (i) relativo aos outros processadores. Uma vez que as respostas
podem ser enviadas durante um perodo de ressincronizac~ao, o processador n~ao ira executar o
protocolo de sincronizac~ao relativo ao ciclo i. So ira sincronizar com os outros processadores
ao aceitar uma mensagem hreadyi+1i.
Este metodo apresenta a desvantagem do tempo de espera que podera ser necessario para
concluir a integrac~ao (no pior caso, dois intervalos de ressincronizac~ao completos). E proposto
por Srikanth pelo facto de prevenir a possvel intromiss~ao de processos faltosos no sistema.
Um outro metodo Rodrigues 91a], de realizac~ao mais simples e apresentando menor tempo
de espera (apenas um intervalo de ressincronizac~ao), consiste em car simplesmente a espera
de f + 1 mensagens hreadyi respeitantes ao mesmo ciclo. E ent~ao possvel saber o numero do
ciclo de ressincronizac~ao (i) de modo a inicializar o novo relogio virtual (fazendo RV i = iP ).
Apesar de n~ao ser abordado por Srikanth, este metodo de integrac~ao de processos pode ser
utilizado em conjugac~ao com o algoritmo de sincronizac~ao por ele proposto. Por isso mesmo e
aqui apresentado.
Com pequenas modi
cac~oes destes metodos consegue garantir-se tambem uma exactid~ao
4
A aplicac~ao de um factor de atraso n~ao signica que os relogios virtuais possam n~ao ser monotonicos. Se
RVp (t1) RVp (t2 ), com t1 < t2 , ent~ao RVp (t1 )= RVp (t2 )=.
16
optima dos novos relogios integrados no sistema.
3.3 Sincronizac~ao contnua
Como ja foi visto (secc~ao 2.2), os relogios virtuais utilizados em cada intervalo de ressincronizac~ao s~ao obtidos por calculo de um ajuste (AJF i) a efectuar ao relogio fsico. Por
sua vez, entre dois relogios virtuais consecutivos e feito tambem um ajuste (AJV i), que pode
conduzir a descontinuidade do tempo virtual apresentado.
Se o ajuste AJV i n~ao for aplicado instantaneamente, mas sim distribudo ao longo de todo
o intervalo de ressincronizac~ao, obtem-se a continuidade do tempo virtual e a noca~o de um
unico relogio virtual em vez de varios relogios consecutivos. Alem disso, desde que o intervalo
de continuidade5 seja superior ao ajuste maximo a efectuar, torna-se possvel fazer ajustes
negativos, ou seja, atrasar os relogios. Veri
ca-se que a distribuic~ao do ajuste corresponde a
uma alterac~ao do factor de progress~ao durante o intervalo de continuidade, o qual aumenta no
caso de um avanco e diminui no caso contrario.
Sincronizacao
instantanea
RV(t)
RF(t)
Sincronizacao
continua
Relogio
fisico
Ajuste
t
Figura 3.1: Sincronizac~ao instant^anea e contnua.
No que diz respeito ao algoritmo de Srikanth, a utilizac~ao da sincronizac~ao contnua torna
bastante mais simples a realizaca~o desse algoritmo uma vez que deixa de ser necessario determinar o valor a atribuir a constante . A func~ao de e garantir a monotonicidade do tempo
virtual (veri
cando-se AJV i > 0), o que n~ao e necessario havendo continuidade.
No caso particular da sincronizac~ao optima e possvel fazer = , passando o factor de
atraso a ser unitario ( = 1). Desta forma, o relogio utilizado para fazer a leitura do tempo
virtual e sempre RV , cuja exactid~ao permanece inalterada.
No caso da sincronizac~ao n~ao optima podemos ter, por exemplo, = 0, o que implica
apenas uma menor taxa de progress~ao dos relogios virtuais.
5
Designamos assim o intervalo de tempo durante o qual e feita a distribuica~o do ajuste.
17
Na gura 3.1 pode observar-se a diferenca existente entre as duas soluc~oes: um relogio virtual em cada intervalo de ressincronizac~ao (i.e. sincronizaca~o instant^anea) ou apenas um unico
relogio virtual com distribuic~ao do ajuste por todo o intervalo (i.e. sincronizac~ao contnua).
Facilmente constatamos que no caso da sincronizac~ao contnua a taxa de desvio dos relogios
virtuais pode variar em intervalos consecutivos. Assim, convem de
nir duas taxas de desvio
para os relogios virtuais Rodrigues 91a]: uma taxa interperiodica que corresponde a taxa entre
duas sincronizac~oes consecutivas, e uma taxa adaptativa que e calculada em relac~ao ao instante
inicial da execuc~ao do protocolo e que varia (continuamente) ao longo do tempo. A taxa
adaptativa converge, quando t ! 1, para a taxa propria do relogio virtual que, no caso da
sincronizac~ao optima, n~ao e superior a .
18
Captulo 4
Algoritmo de Acordo \a posteriori"
A novidade do algoritmo de Acordo a posteriori reside na melhoria da precis~ao que e possvel
atingir. Neste algoritmo a sincronizac~ao e efectuada por converg^encia n~ao ponderada, tendo
por isso algumas semelhancas com outros algoritmos, em particular com o de Srikanth.
Em termos da toler^ancia a faltas este algoritmo e tambem completo, prevendo todos os
tipos de faltas nos processadores (inclusivamente faltas do tipo Bizantino) e faltas associadas
a rede de comunicac~oes.
O algoritmo pressup~oe que a autenticac~ao de mensagens e garantida pela rede.
Neste captulo e feita a descric~ao do algoritmo, bem como das suas principais caractersticas.
E reservada uma secc~ao para abordagem deste algoritmo como suporte do servico de tempo do
xAMp. A descrica~o pormenorizada deste algoritmo pode ser encontrada em Rodrigues 91a].
4.1 Melhoria da precis~ao
Como foi visto no captulo anterior, a maxima precis~ao dos relogios virtuais que o algoritmo
de Srikanth permite atingir depende da variac~ao do tempo maximo de entrega, ;e. Na secc~ao
seguinte, veremos que no caso do algoritmo de Acordo a posteriori a precis~ao n~ao depende da
variac~ao do tempo de entrega, mas sim da desfasagem maxima na recepc~ao de uma mesma
mensagem, ;desf . Vejamos, ent~ao, qual a diferenca entre ;e e ;desf .
O tempo maximo de entrega e constituido pelos quatro termos seguintesKopetz 89]:
;env , tempo maximo de envio.
;acesso , tempo maximo de acesso.
;prp , tempo maximo de propagaca~o.
;rec ,
tempo maximo de recepca~o.
Por outro lado, a desfasagem maxima de recepca~o depende apenas dos tempos variaveis de
propagac~ao e de recepc~ao (;prp e ;rec). Assim, como a in u^encia relativa de todos estes
19
termos n~ao e a mesmaKopetz 89], e natural que haja diferencas entre ;desf e ;e , uma vez
que estes n~ao dependem dos mesmos termos.
Segundo RodriguesRodrigues 91a], os tempos de envio e de propagaca~o s~ao praticamente
constantes e, para a maioria das redes de comunicac~ao existentes, ;rec ;acesso . Assim, e
como a desfasagem maxima n~ao depende da variac~ao do tempo de acesso, e valida a relac~ao
;desf
;e
(4.1)
o que nos permite obter uma precis~ao superior no caso do algoritmo de Acordo a posteriori.
Os resultados de medic~oes efectuadas, apresentados no captulo 6, demonstram a validade
desta relac~ao.
4.2 Descric~ao do algoritmo
Como ja foi assinalado, este algoritmo e tolerante a faltas nos processadores e no meio fsico
de comunicac~ao. Considera-se que o numero maximo de faltas arbitrarias nos processadores e
fp. Considera-se ainda como uma falha do processador o mau funcionamento do relogio fsico
que lhe esta associado1 . As faltas que se veri
cam no meio fsico podem ser devidas quer a
perdas de informac~ao nas ligac~oes aos processadores quer a omiss~oes no canal de comunicac~ao.
As perdas de informac~ao nas ligac~oes podem ser vistas, sem perda de generalidade, como faltas
por omiss~ao. Assim, admite-se que o numero maximo de faltas no meio (por omiss~ao) e fo .
O numero de processadores necessarios para assegurar a sincronizac~ao de todos os processadores correctos do sistema depende de fp e de fo. Rodrigues mostra que tem que se veri
car
a relac~ao
N (fp + 1)(fo + 1)
(4.2)
Quando o relogio virtual de um processador p atinge o valor ti = iP e enviada a mensagem
hstart i pi na tentativa de gerar um acontecimento simult^aneo em todos os nos. Entende-se
por acontecimento simult^aneo a recepc~ao em todos os nos de uma mesma mensagem que dara
origem a realizaca~o de uma acca~o. Note-se que uma mensagem n~ao chega no mesmo instante a
todos os receptores, mas sim com uma desfasagem maxima igual a ;desf , o que signi
ca que
a simultaneidade do acontecimento n~ao e absoluta.
Uma vez que o numero de mensagens enviadas e su
ciente para mascarar o grau de omiss~ao
da rede sera gerado pelo menos um acontecimento simult^aneo.
No instante da recepc~ao de uma mensagem hstarti e lancado um relogio candidato, ou seja,
um relogio que podera vir a ser utilizado no intervalo de ressincronizac~ao seguinte (note-se que
1
O mau funcionamento de um relogio fsico verica-se quando este apresenta uma taxa de desvio superior a
ou quando indica valores errados ao ser lido.
20
os relogios candidatos s~ao lancados com um desfasamento maximo, em tempo real, de ;desf ).
E tambem enviada uma con
rmaca~o de recepc~ao dessa mensagem. Esta con
rmac~ao tem a
forma hack i pi para as primeiras (fp)esimas mensagens e hcandidate i pi para as restantes.
Desta forma, garante-se que a resposta e hcandidatei apenas quando ja foi recebida pelo menos
uma mensagem de um processador correcto.
Por inspecc~ao das con
rmac~oes das mensagens hstarti e possvel identi
car tr^es situac~oes
distintas:
i) se foram recebidas todas as respostas dos processadores correctos2 e pelo menos f + 1
s~ao do tipo hcandidatei ent~ao o relogio candidato podera ser utilizado no intervalo de
ressincronizac~ao seguinte.
ii) se foram recebidas todas as respostas e no maximo f s~ao hcandidatei ent~ao o relogio
candidato sera ignorado.
iii) se n~ao foram recebidas todas as respostas isso podera levar a detecc~ao de falhas de
processadores3 . Na ressincronizac~ao seguinte esses processadores ser~ao ignorados. Note-se que existe um intervalo de tempo maximo para recepc~ao de todas as con
rmac~oes,
relacionado com o tempo maximo de entrega.
Finalmente, para a escolha do relogio candidato a ser utilizado, e necessario executar um
protocolo de acordo, uma vez que podem existir varios relogios candidatos (mesmo apesar da
selecc~ao ja feita). Uma possvel realizac~ao deste protocolo consistiria na difus~ao dos relogios
candidatos gerados em cada processador e, por aplicac~ao de uma func~ao especi
ca aos varios
conjuntos de relogios candidatos gerados, seria escolhido um desses relogios. Como este protocolo so e executado apos se ter gerado o evento simult^aneo, o algoritmo e denominado de
Acordo a posteriori.
~o
Precisa
A precis~ao deste algoritmo depende, como ja se viu, de ;desf . Medida no relogio virtual
do processador mais veloz, esta desfasagem traduz-se numa diferenca inicial maxima entre dois
relogios candidatos de (1 + );desf . No entanto, ate a escolha do relogio candidato a ser
utilizado os relogios v~ao-se afastando a uma taxa maxima de 2. Assim, e tendo em conta que
o tempo maximo para executar o protocolo de acordo e ;acordo , a melhor precis~ao obtida para
os relogios virtuais sera
(1 + );desf + 2;acordo
(4.3)
Cada processador tera de saber o numero total de processadores correctos do sistema e, portanto, o numero
de respostas que tera de receber. A actualizac~ao deste numero e efectuada quando e detectada a integraca~o ou
a falha de um processador.
3 Conv
em referir que a falha de um processador so e detectada se o numero de respostas em falta desse
processador for superior ao grau de omiss~ao da rede.
2
21
~o
Exactida
Da forma como foi descrito, o algoritmo apenas garante a propriedade da precis~ao. Relembremos que o algoritmo de Srikanth, numa das suas vers~oes, permite a obtenc~ao da exactid~ao
optima para os relogios virtuais. No algoritmo de Acordo a posteriori e inviavel a aplicac~ao da
tecnica usada por Srikanth, uma vez que se perderia a precis~ao. No entanto, e ainda possvel
obter uma boa aproximac~ao da exactid~ao optima.
O facto de os relogios candidatos serem inicializados sempre com o mesmo valor (iP ),
permite que as taxas de desvio dos relogios virtuais possam ser superiores a . A melhoria da exactid~ao obtem-se garantindo que os relogios candidatos s~ao inicializados com um valor proximo
do valor lido num relogio virtual correcto. Isto equivale a dizer que em cada ressincronizac~ao
um dos relogios correctos mantem a sua progress~ao constante (sem realizar ajustes) e os outros aproximam-se dele. Para tal, o valor inicial dos relogios candidatos n~ao sera iP mas sim
iP + AJpi, sendo AJpi a diferenca entre o valor lido no relogio virtual do processador correcto p
e o valor iP (o relogio virtual do processador p n~ao sera alterado).
No momento em que lancam os relogios candidatos, os processadores n~ao conhecem o valor
de AJ i, pois este sera determinado durante a realizac~ao do protocolo de acordo. Vejamos como
e determinado o ajuste AJ i (associado ao relogio candidato eleito por acordo). Ao receberem
uma mensagem hstarti os processadores registam a diferenca entre o seu relogio virtual e o valor
iP , devolvendo essa diferenca na resposta. Assim, e possvel manter um registo de todas as
diferencas associadas a cada um dos eventos simult^aneos. Como so um dos relogios candidatos
sera escolhido, apenas o conjunto de diferencas associadas a criac~ao desse relogio interessa.
Desse conjunto s~ao rejeitadas as fp diferencas mais altas e as fp mais baixas e e escolhida, de
forma n~ao aleatoria, uma das restantes. A diferenca escolhida corresponde ao ajuste AJ i.
Esta tecnica n~ao garante uma exactid~ao optima porque o evento que da origem ao relogio
candidato n~ao e absolutamente simult^aneo: a desfasagem maxima com que o evento pode ser
gerado e igual a ;desf . Assim, um ajuste AJ i determinado num instante real t pode ser
utilizado na inicializac~ao de um relogio candidato criado num instante real t ;desf . A taxa
maxima de desvio de um relogio virtual e ent~ao
+ ;desfP(1 + )
(4.4)
~ o e integraca
~o
Inicializaca
No que respeita a inicializac~ao da sincronizac~ao, esta efectua-se sem alterac~ao do algoritmo
(tal como no caso do algoritmo de Srikanth). Um processador envia hstarti e espera pelas
respostas. So quando houver su
cientes processadores que pretendam inicializar e que havera
su
cientes respostas do tipo hcandidatei para permitir a execuc~ao do protocolo de acordo e
consequente \adopc~ao" de um dos relogios candidatos.
Note-se que as f + 1 respostas hcandidatei, necessarias para tolerar faltas Bizantinas, so
se conseguem obter quando existirem 2f + 1 processadores a tentarem inicializar o seu relogio
22
virtual. No algoritmo de Srikanth bastavam f + 1 processadores para iniciar a sincronizac~ao.
A forma como e feita a integrac~ao de novos processadores ja foi referida na secc~ao 3.2. Um
processador espera passivamente pela recepc~ao de mensagens hstarti e responde como especi
cado pelo algoritmo, lancando um relogio candidato por cada mensagem recebida. Atraves do
protocolo de acordo sera escolhido um desses relogios candidatos, que estara sincronizado com
todos os outros.
Convem notar que tanto na inicializac~ao como na integrac~ao, e no caso do algoritmo modi
cado para permitir uma melhor exactid~ao, a diferenca que e includa nas respostas as mensagens
hstarti n~ao podera vir a ser escolhida, uma vez que n~ao corresponde a nenhum relogio virtual
em uso. Assim, na inicializac~ao esta diferenca podera ter o valor zero (sendo tambem zero o
valor que sera escolhido) e na integrac~ao este valor tera de ser extremo (por exemplo, superior
a diferenca maxima permitida entre os relogios virtuais) de modo a ser rejeitado durante a
escolha do ajuste a aplicar.
4.3 O servico de tempo do xAMp
O xAMp4 e um versatil servico de comunicac~ao em grupo concebido para suportar o desenvolvimento de aplicac~oes em sistemas distribudos. A versatilidade deste protocolo e devida
as varias qualidades de servico5 oferecidas, ou seja, as diferentes formas de comunicac~ao em
grupo que e possvel utilizar. Das qualidades de servico oferecidas destacamos a QOS atomic, a qual garante que uma mensagem ou e recebida por todos os elementos de um grupo
ou n~ao e recebida por nenhum. A descric~ao de todos os servicos do xAMp pode ser encontrada em Rodrigues 91b]. Re
ra-se que o xAMp corresponde a uma evoluc~ao relativamente ao
AMpVerissimo 89a] que apenas apresentava a QOS atomic.
A sincronizac~ao de relogios apresenta uma serie de vantagens ja descritas no incio deste
relatorio. Assim, e dado que o xAMp oferece varias possibilidades de comunicac~ao, e vantajoso
integrar no xAMp um servico de tempo realizado atraves de um algoritmo de sincronizac~ao. O
facto da realizac~ao deste servico de tempo se efectuar nas camadas mais baixas traz tambem
vantagens relativamente a precis~ao. Por outro lado, a exist^encia de um servico de tempo
integrado no xAMp permite a construc~ao de novas qualidades de servico que o utilizem.
O algoritmo de Acordo a posteriori foi concebido e desenvolvido explicitamente para ser
utilizado como suporte deste servico de tempo. As desvantagens que o algoritmo generico
apresenta s~ao praticamente anuladas quando e feita a sua integrac~ao no xAMp. A complexidade que a realizac~ao do algoritmo poderia oferecer e muito reduzida neste caso, gracas as
primitivas de comunicac~ao ja existentes. O algoritmo utiliza duas qualidades de servico, que
facilitam o envio de mensagens para um grupo espec
co de nos da rede e a realizac~ao do
protocolo de Acordo a posteriori.
4 xAMp, Extended Atomic Multicast protocol.
5
Em ingl^es, Quality of service - QOS.
23
No xAMp e dedicado um grupo exclusivo ao servico de tempo. Gracas a exist^encia de um
mecanismo que executa a monitorizac~ao do grupo e possvel manter uma vista actualizada da
sua composic~ao. Assim, quando existe uma alterac~ao de um grupo (por entrada ou sada de
novos elementos) todos os componentes deste grupo s~ao informados, sendo possvel saber em
cada momento quandos elementos constituem o grupo.
Gracas a este \servico de informac~ao", quando um processador pretende iniciar a sincronizac~ao do seu relogio n~ao necessita de saber antecipadamente se vai executar o protocolo de
inicializac~ao (caso n~ao hajam ainda processadores su
cientes para realizar o algoritmo) ou o
de integrac~ao (caso contrario). Existe apenas uma primitiva, utilizada para este efeito, que
funciona da seguinte forma: quando um novo elemento entra no grupo de processadores que
executam o algoritmo de sincronizac~ao, o mecanismo de monitorizac~ao de grupos (ao qual foi
feito o pedido de integrac~ao no grupo) informa todos os elementos desse grupo, incluindo o novo
elemento. A informac~ao fornecida pelo monitor consiste na indicac~ao dos elementos actuais,
dos novos elementos e dos elementos retirados. Com esta informac~ao os processadores podem
decidir a acc~ao que devem realizar:
i) se o algoritmo ja estava a ser executado ent~ao os novos processadores efectuam o protocolo
de integrac~ao e os restantes n~ao realizam qualquer acc~ao.
ii) se ainda n~ao existiam su
cientes elementos para iniciar a sincronizac~ao (neste caso s~ao
necessarios f + 1 elementos) e, com a entrada dos novos, passaram a existir, ent~ao todos
os processadores realizam o protocolo de inicializac~ao.
iii) se, apesar da entrada de novos elementos no grupo, o seu numero total ainda e insu
ciente
para iniciar a sincronizac~ao (ou seja, inferior a f +1), ent~ao todos os processadores car~ao
passivos, aguardando a entrada de mais elementos.
Convem realcar que esta primitiva e de extrema import^ancia, pois do ponto de vista do
utilizador que pertende criar e utilizar um relogio sincronizado, a inicializac~ao ou integrac~ao
s~ao transparentes. Uma outra vantagem relaciona-se com o menor numero de processadores
necessario para iniciar a execuc~ao da sincronizac~ao, que deixa de ser 2f + 1 passando agora a
f + 1.
Sempre que determinados elementos falham, ou deixam de fazer parte do grupo, o monitor
informa todos os elementos restantes. Assim, se o numero de processadores passar a ser inferior
ao exigido, e possvel parar a execuc~ao do algoritmo e voltar a um \estado inicial" de espera
pela entrada de novos elementos (voltando, nesse momento, a executar o protocolo de inicializac~ao). Desta forma, e introduzido um novo conceito que corresponde a nalizac~ao do protocolo,
o qual n~ao existia no algoritmo de Srikanth. Nesse algoritmo, se o numero de processadores
deixasse de ser su
ciente para assegurar a sincronizac~ao periodica dos relogios, nenhuma acc~ao
seria tomada com vista a reinicializar os relogios virtuais, mantendo-se estes em progress~ao e
afastando-se gradualmente uns dos outros.
No algoritmo de Acordo a posteriori, e se o numero de elementos se torna insu
ciente,
a exist^encia de uma primitiva de nalizac~ao permite parar os relogios virtuais do sistema
(atribuindo-lhes o valor zero) impedindo que estes, ao serem lidos, fornecam tempos virtuais
n~ao sincronizados. Alem disto, no momento em que novos elementos pretendam realizar a
sincronizac~ao, esta podera recomecar imediatamente uma vez que que todos os processadores
24
est~ao preparados para tal.
A forma particular de realizac~ao do protocolo de acordo, aproveitando as caractersticas
do xAMp, permite uma simpli
cac~ao do algoritmo no que respeita a detecc~ao dos relogios
candidatos que poder~ao vir a ser utilizados. No algoritmo generico, todos os processadores
recebem as respostas as mensagens hstarti podendo seleccionar os relogios candidatos validos.
Neste caso, o protocolo de acordo pode ser realizado fazendo com que cada um dos processadores
correctos dissemine o conjunto dos relogios candidatos validos, aplicando, posteriormente, uma
determinada func~ao aos varios conjuntos recebidos.
No xAMp a con
rmac~ao de recepc~ao da mensagem hstarti e enviada apenas para o remetente. Cada remetente, pela observac~ao das respostas recebidas, determina a validade do acontecimento simult^aneo gerado pela sua mensagem hstarti. Se foram recebidas su
cientes respostas
hcandidatei e difundida uma mensagem para validar o acontecimento simult^aneo e, portanto,
os relogios candidatos criados nesse instante. Esta mensagem tem a forma hchose AJ ii, sendo
AJ i o ajuste a efectuar ao relogio candidato eleito (para melhorar a exactid~ao). O ajuste AJ i
e determinado a partir dos tempos de recepc~ao (Trec) da mensagem hstarti, includos nas respostas a essa mensagem: rejeitam-se os fp mais altos e os fp mais baixos tempos de recepc~ao
e aplica-se a func~ao
ifP +1 ; iP : : : T iN ;fP ;1 )
AJ i = min ( Trec
rec
(4.5)
sendo N o numero de processadores correctos.
Dos relogios candidatos validados pela recepc~ao de uma mensagem hchosei sera eleito aquele que tiver sido lancado em primeiro lugar. Dado que para o envio das mensagens hstarti e
utilizada a QOS atomic (que garante a mesma ordem de recepc~ao das mensagens em todos os
elementos do grupo), os relogios candidatos s~ao lancados pela mesma ordem em todos os processadores e, portanto, os relogios candidatos eleitos corresponder~ao ao mesmo acontecimento
simult^aneo. O valor do ajuste contido na mensagem hchosei que validou o relogio eleito e o
ajuste aplicado e e o mesmo em todos os elementos do grupo.
25
26
Captulo 5
Realizac~ao
Um dos objectivos do nosso trabalho foi, alem do estudo dos algoritmos de sicronizac~ao de
relogios, a sua realizac~ao.
Neste captulo abordaremos todos os factores directamente relacionados com a realizac~ao
dos algoritmos descritos anteriormente, desde os sistemas operativos ate as aplicac~oes para
monitorizac~ao do seu funcionamento. Faremos tambem uma descric~ao da realizac~ao em termos
da interacc~ao com outras aplicac~oes ou com o ambiente de suporte.
Pensamos que sera mais interessante e mais importante dar uma ideia dos problemas que
surgiram durante a materializac~ao dos algoritmos, em vez da descric~ao exaustiva do codigo
desenvolvido.
5.1 Ambiente de suporte
Entendemos por ambiente de suporte todos os componentes (hardware e software) que, de
alguma forma, est~ao relacionados com a realizac~ao dos algoritmos. Dado que os assuntos aqui
abordados s~ao, na sua maioria, comuns aos dois algoritmos, decidimos dedicar apenas uma
secc~ao para tal abordagem. Os casos pontuais onde tenha havido diferencas em termos do
ambiente de suporte ser~ao devidamente assinalados.
5.1.1 Sistema operativo e rede distribuda
Os algoritmos foram realizados em dois sistemas operativos: o UNIX e o SPART. A realizaca~o dos algoritmos no UNIX tem duas raz~oes fundamentais:
este nucleo e o mais acessvel dentro dos que oferecem as primitivas necessarias para uma
realizac~ao deste tipo.
neste sistema existem varias aplicaco~es que garantem um bom ambiente de trabalho.
27
Alem disso, uma das vers~oes existentes do xAMp foi realizada neste sistema operativo,
donde, como um dos objectivos do trabalho e a utilizac~ao de um algoritmo de sincronizac~ao
como base do servico de tempo do xAMp, os algoritmos foram tambem realizados em UNIX.
Os testes realizados aos algoritmos foram efectuados utilizando 5 estac~oes SUN correndo o
sistema UNIX SunOS Release 4.1. As estac~oes utilizadas estavam ligadas atraves de uma rede
Ethernet. Apos realizados no UNIX, os algoritmos foram portados para o sistema operativo
SPART uma vez que o xAMp utiliza tambem este sistema.
Convira referir aqui, para que se compreenda o motivo do uso do sistema SPART, que
o xAMp foi desenvolvido como suporte do sistema de comunicac~oes da arquitectura Delta-4.
Esta arquitectura e um suporte para domnios de aplicac~oes que necessitem de soluc~oes em
sistemas distribuidos com varios graus de con
anca no funcionamento1 e com requisitos de
tempo realPowell 91].
O hardware utilizado pela arquitectura Delta-4 inclui uma interface entre cada processador
e a rede local, constituda por um sistema de falha silenciosa para controlo do acesso a rede.
Este sistema, denominado de NAC (network attachment controller), utiliza o sistema SPART,
sobre o qual se desenvolveu o software de comunicac~oes, ou seja, o xAMp.
Re
ra-se ainda que a nossa realizac~ao do servico de tempo do xAMp foi utilizada no ^ambito
do projecto Delta-4. A realizac~ao de um algoritmo de sincronizac~ao num nucleo de tempo
real (como o SPART), permite obter melhorias da precis~ao relativamente a um sistema como o
UNIX, dado que n~ao existem atrasos variaveis e que e possvel realizar o algoritmo nas camadas
mais baixas do sistema (podendo ser feito uso de interrupc~oes).
Na realizac~ao do algoritmo no sistema SPART a rede de comunicaca~o utilizada foi uma
rede Token-Bus. Os testes foram realizados numa rede com quatro processadores.
5.1.2 Ambiente de suporte local
O ambiente de suporte localFonseca 90] (em ingl^es designado por Local Support Environment - LSE) oferece um conjunto de primitivas que funcionam como uma interface ao sistema
operativo. Se uma aplicac~ao for desenvolvida sobre um LSE n~ao tera que ser alterada quando
transportada para outro sistema onde tambem exista um LSE.
No nosso trabalho foram utilizadas muitas das primitivas proporcionadas pelo LSE dos
dois sistemas operativos. Em particular, foram utilizadas primitivas de alocac~ao e operac~oes
sobre memoria, mailboxes, bu#ers genericos, pools e timers. As primitivas de timers sofreram
alterac~oes durante a realizac~ao dos algoritmos, uma vez que o grau de exig^encia destes n~ao
era previamente suportado. Na secc~ao 5.2 ser~ao referidas as alterac~oes efectuadas. Assim,
exceptuando alguns casos particulares n~ao previstos nos LSE, o codigo foi o mesmo nos dois
sistemas operativos.
O conceito de conanca no funcionamento e um conceito geral que engloba os seguintes atributos de um
sistema: abilidade disponibilidade seguranca relativamente a faltas acidentais seguranca relativamente a faltas
intencionais.
1
28
A utilizac~ao dos LSE foi devida n~ao so ao facto de estes apresentarem as vantagens ja
indicadas, mas tambem porque s~ao utilizados no xAMp.
5.1.3 dclock
A monitorizac~ao do funcionamento dos algoritmos poderia ser efectuada simplesmente com
a impress~ao periodica do valor dos relogios virtuais no terminal de cada no. Naturalmente que
este procedimento n~ao permitiria a veri
cac~ao do funcionamento rigoroso dos algoritmos, mas
apenas uma constataca~o do seu funcionamento.
O dclock e um programa utilitario que, recorrendo a um servidor de X, a
xa no terminal
um relogio com uma resoluca~o de segundos. Dado que as estac~oes SUN utilizadas para realizar
os testes permitem o lancamento de um servidor de X, decidimos utilizar este utilitario por
permitir uma facil visualizac~ao dos relogios e por permitir testar a interface com o utilizador
oferecida pela nossa realizaca~o. Convem realcar, no entanto, que as restric~oes ja indicadas se
mant^em, pois para uma veri
cac~ao rigorosa do funcionamento s~ao necessarias outras tecnicas
e ferramentas.
Figura 5.1: Monitorizac~ao dos relogios virtuais atraves do utilitario dclock.
No SPART n~ao foi utilizada nenhuma aplicac~ao que apresentasse continuamente o valor dos
relogios, tendo apenas sido utilizado um sistema de menus ao qual foram adicionadas algumas
opc~oes para permitir a leitura dos relogios.
Na gura 5.1 e apresentado um exemplo de utilizac~ao do dclock, onde se visualizam
os relogios virtuais de tr^es processadores sincronizados entre si atraves de um algoritmo de
sincronizac~ao de relogios.
Se as diferencas forem de ordem inferior a um segundo n~ao sera possvel a veri
cac~ao do
funcionamento correcto do algoritmo. Note-se que o tempo apresentado n~ao tem qualquer relac~ao com o tempo real, uma vez que os relogios virtuais s~ao sincronizados a partir do valor zero
(para o programa dclock o valor zero corresponde ao dia 1 de janeiro de 1970).
29
5.1.4 Outras aplicaco~es
Numa primeira fase do nosso trabalho foi utilizado algum software que, apesar de na sua
ess^encia n~ao constituir um suporte local de interface ao sistema operativo, facilitou a realizac~ao
do algoritmo de Srikanth. Entre as rotinas disponveis salientamos as relacionadas com timers,
envio e recepc~ao de mensagens e construc~ao de listas. Posteriormente, todo este software foi
substituido pelo LSE.
Como o codigo foi todo escrito na linguagem C, foram apenas utilizados compiladores para
esta linguagem.
Para debug de codigo no ambiente UNIX foram utilizadas as seguintes aplicac~oes: dbx,
xdbx e ups. Devido a natureza do nosso trabalho (que n~ao permite uma monitorizaca~o passo-a-passo) estas aplicac~oes n~ao se revelaram muito uteis. A correcca~o de erros foi realizada, em
grande medida, por observac~ao de cheiros de debug criados durante a execuca~o dos algoritmos.
5.2 Descric~ao da realizac~ao
O algoritmo de Srikanth foi realizado em tr^es fases consecutivas e nas duas primeiras funcionou totalmente independente do xAMp. Assim, so a ultima vers~ao foi transportada para o
sistema SPART. A primeira vers~ao permitia sincronizar os relogios dos processadores existentes mas, como a interface com o utilizador ainda n~ao estava de
nida, era impossvel a leitura
externa do tempo virtual. Nesta primeira realizac~ao o LSE n~ao era utilizado e a visualizac~ao
dos relogios era feita atraves da impress~ao periodica do seu valor no terminal de vdeo.
Na segunda fase foi de
nida a interface com o utilizador, o que permitiu o uso do dclock
para a visualizaca~o dos relogios. Uma grande parte do codigo desenvolvido na primeira fase foi
substitudo por novo codigo, mais simples gracas ao LSE.
Finalmente, o algoritmo foi integrado no xAMp, funcionando numa camada externa sem fazer uso directo das primitivas daquele protocolo. De certa forma foi feita apenas uma acoplagem
dos codigos ja existentes, apenas com alterac~oes na inicializac~ao e na interface com o utilizador.
Esta interface foi totalmente modi
cada quando o codigo ent~ao existente foi transportado para
o sistema SPART.
No que respeita ao algoritmo de Acordo a posteriori, este foi realizado directamente no
nucleo do xAMp. O trabalho realizado relativamente ao transporte para o sistema SPART foi
id^entico ao do algoritmo de Srikanth.
A realizac~ao de um algoritmo de sincronizac~ao levanta alguns problemas que n~ao s~ao perceptveis na sua descric~ao teorica. No caso dos algoritmos que realizamos (sem distinc~ao, uma
vez que apresentam caractersticas relativamente semelhantes) podem ser problemas, por exemplo, o modo como as mensagens s~ao enviadas, o incio de uma ressincronizac~ao ou a forma
como podera ser lido o tempo virtual externamente. Re
ra-se que a realizac~ao do algoritmo de
30
Srikanth foi a primeira a ser efectuada. Assim, durante a realizac~ao do algoritmo de Acordo a
posteriori muitos dos problemas estavam ja resolvidos. O principal problema que a realizac~ao
deste algoritmo levantou foi a necessidade do conhecimento do xAMp que, apesar do estudo
efectuado n~ao ter sido aprofundado, nos obrigou a desenvolver um esforco adicional.
A determinac~ao do instante em que se deve iniciar uma ressincronizac~ao constitui um
obstaculo a realizac~ao do algoritmo. Uma soluc~ao imediata seria a leitura constante do relogio
virtual de modo a poder determinar, em cada momento, se esse instante teria sido atingido.
Esta soluc~ao e inviavel pois levaria a um desperdcio desnecessario de recursos. Optamos pela
utilizaca~o de um timer que permite determinar facilmente o incio da ressincronizac~ao. Em cada
ressincronizaca~o o timer e inicializado com o valor correspondente ao intervalo de ressincronizac~ao, o que permite manter a regularidade deste intervalo.
Os timers inicialmente oferecidos pelo LSE apenas permitiam uma granularidade da ordem
do segundo. Do ponto de vista da sincronizac~ao estes timers n~ao poderiam ser utilizados, uma
vez que iriam afectar de
nitivamente a precis~ao atingida. Assim, foram efectuadas algumas
alterac~oes nos timers do LSE de modo a permitir granularidades aproximadamente2 da ordem
do milesimo de segundo (no UNIX). No sistema SPART a granularidade do relogio interno e
das dezenas de milisegundos o que se re ecte nos timers do LSE para este sistema. Convem
ainda referir que a precis~ao destes timers n~ao e garantida o que pode provocar atrasos no incio
da ressincronizac~ao e uma consequente perda de precis~ao dos relogios virtuais. Os erros que os
timers podem apresentar s~ao apresentados no captulo 6.
Apesar da exist^encia do LSE, que tornou possvel transportar o codigo do sistema UNIX
para o SPART sem nele realizar qualquer alterac~ao, foi encontrado um ponto de depend^encia
em relac~ao ao sistema. A func~ao de leitura do relogio fsico n~ao e emulada pelo LSE, o que
nos obrigou a utilizar uma func~ao dependente do sistema. Em futuras vers~oes do LSE talvez
esta lacuna venha a ser preenchida, o que tornara possvel obter uma realizac~ao totalmente
independente do sistema.
A realizac~ao do algoritmo de Srikanth no xAMp oferece uma primitiva para parar a execuc~ao da sincronizac~ao. Achamos conveniente ressalvar que esta primitiva, ao contrario daquela
oferecida pela realizac~ao do algoritmo de Acordo a posteriori, apenas pode ser util do ponto de
vista do processador que a executa, pois esse processador podera continuar a executar o xAMp
apos ter acabado a execuc~ao do algoritmo de sincronizac~ao. Do ponto de vista de qualquer um
dos outros processadores e detectada uma falha e n~ao uma nalizac~ao.
Note-se que o UNIX n~ao e um sistema de tempo real e, portanto, podem ocorrer atrasos no scheduling de
um processo.
2
31
32
Captulo 6
Resultados
Em termos teoricos observamos que um algoritmo de sincronizac~ao de relogios pode ser
caracterizado pela precis~ao que permite obter. Existem, no entanto, outros factores que podem
caracterizar um algoritmo tais como os custos ou o grau de di
culdade da sua realizac~ao pratica.
Em relac~ao aos dois algoritmos estudados, podemos compara-los, sobretudo, atraves da
avaliac~ao da precis~ao que estes permitem efectivamente atingir.
Foi na tentativa de medic~ao da precis~ao dos algoritmos que deparamos com grandes di
culdades. A determinaca~o de valores para a precis~ao no sistema UNIX revelou-se impossvel
utilizando apenas as ferramentas disponveis. Por outro lado, como no sistema SPART a granularidade do relogio interno e de dezenas de milisegundos, a precis~ao maxima de qualquer um
dos algoritmos e limitada por este valor, o que n~ao permite fazer uma comparac~ao valida (e
pratica) dos dois algoritmos.
A medica~o da precis~ao dos relogios poderia ser feita das seguintes formas:
amostragem contnua e simult^anea dos relogios virtuais, com registo de valores temporais
lidos.
registo dos valores lidos nos relogios virtuais no instante anterior a sincronizac~ao e medic~ao
da desfasagem de sincronizac~ao.
determinaca~o da desfasagem no momento da sincronizac~ao e calculo teorico do valor de
desfasagem maximo previsto (com base na taxa de desvio e no perodo de ressincronizac~ao).
No sistema UNIX n~ao e possvel aplicar nenhuma destas soluc~oes, dado que n~ao temos acesso
ao hardware para medir as desfasagens. No SPART, apesar de termos acesso ao hardware (o
que possibilita a medica~o de desfasagens), os valores temporais resgistados s~ao afectados pela
granularidade do relogio fsico, o que signi
ca que a precis~ao determinada tera uma margem de
erro da ordem das dezenas de milisegundos. Note-se, no entanto, que a ultima soluc~ao e viavel
no sistema SPART dado que n~ao implica a leitura dos relogios virtuais. Esta soluc~ao apenas
33
peca por se basear em pressupostos teoricos, que podem n~ao coincidir com a realidade pratica,
o que a inviabiliza na medida em que os resultados seriam pouco aveis.
Decidimos, ent~ao, con
rmar os pressupostos em que se baseia o algoritmo de Acordo a
posteriori, ou seja, con
rmar a relac~ao ;desf ;e . As medic~oes foram efectuadas no sistema
SPART dado que neste sistema temos acesso ao hardware. Como suporte fsico para efectuar as
medic~oes utilizamos um analisador digital de sinais ao qual foram ligados dois processadores.
Foi realizado o software necessario para gerar e enviar sinais para o analisador no momento de
envio ou recepc~ao de uma mensagem.
As primeiras medic~oes foram efectuadas durante a execuc~ao do algoritmo de sincronizac~ao,
estando o algoritmo a ser executado num nvel exterior a interface com o controlador da rede.
Os valores obtidos s~ao apresentados na tabela 6.1.
Mnimo Maximo
Medio
;desf
0
6.5 ms 2.4 ms
;e 4.8 ms 13.1 ms 8.6 ms
Tabela 6.1: Valores obtidos nas medico~es efectuadas no nvel exterior a interface com a rede.
Por observac~ao dos valores obtidos n~ao e possvel chegar a conclus~ao desejada. O facto de a
execuc~ao do algoritmo n~ao se efectuar no nvel da interface conduz a obtenc~ao de valores para
;desf que se podem considerar extremamente elevados. Estes valores devem-se tambem ao facto
de a rede se encontrar em carga, provocada pelas mensagens do algoritmo de sincronizac~ao.
Tendo em vista uma hipotetica melhoria dos resultados, foram realizadas medic~oes no nvel
da interface com a rede. Note-se que o algoritmo n~ao foi transportado para este nvel neste
nvel apenas foi utilizado o codigo de envio de sinais para o analizador digital. A determinac~ao
dos valores foi feita sem carga na rede dado que era enviada apenas uma mensagem para cada
medic~ao. Se a rede estivesse em carga n~ao haveriam alterac~oes signi
cativas dos resultados,
pois a chegada de uma mensagem origina uma interrupc~ao que e imediatamente1 atendida. Se
o algoritmo estivesse em execuc~ao neste nvel os resultados e as conclus~oes obtidas seriam as
mesmas. Na tabela 6.2 podem observar-se os valores obtidos.
Mnimo Maximo
Medio
;desf
0
99 s 40 s
;e 4.2 ms 6.0 ms 4.6 ms
Tabela 6.2: Valores obtidos nas medic~oes efectuadas no nvel da interface com a rede.
Veri
ca-se agora que os presupostos que servem de base ao algoritmo de Acordo a posteriori
s~ao validos, visto que ;desf e nitidamente inferior a ;e .
Comparando os valores de ;e obtidos nas duas situac~oes podemos concluir que o atendimento das mensagens no nvel da interface traz tambem vantagens. Relembremos que no algoritmo
de Srikanth a precis~ao depende do valor maximo de ;e , valor este que foi reduzido a metade.
A rapidez de atendimento depende de alguns factores como sejam o estado presente das interrupc~oes (habilitadas/desabilitadas) ou a ocupac~ao/desocupac~ao do processador no atendimento de outras interrupc~oes.
1
34
Sintetizando os valores expressos na tabela 6.2 podemos estabelecer a seguinte ordem de
valores:
;me ax = 6:0ms > ;e = 1:8ms > ;desf = 99s
(6.1)
Assim, sera possivel ordenar os algoritmos de sincronizac~ao, relativamente a precis~ao que
proporcionam, de acordo com a depend^encia de cada um em relac~ao aos tempos escalonados
na express~ao 6.1.
Como ja foi referido os timers utilizados na realizac~ao dos algoritmos podem apresentar
erros que in uenciam a precis~ao dos relogios virtuais. Para que pudessemos ter uma ideia da
ordem de grandeza destes erros, realizamos alguns testes cujos resultados s~ao expostos na tabela
6.3
Sistema operativo Mnimo
Maximo
UNIX
10 ms 500 ms - 1000 ms
SPART
10 ms 50 ms - 100 ms
Tabela 6.3: Erros na precis~ao dos timers dos LSE.
Os valores mnimo e maximo no sistema UNIX foram determinados respectivamente nas
situac~oes do sistema sem carga e com carga. O valor mnimo obtido no sistema SPART corresponde a granularidade maxima do relogio interno. Veri
ca-se que os erros associados aos
timers podem tomar valores elevados, os quais originam uma diminuica~o da precis~ao dos relogios
virtuais.
Este resultado revela-nos a import^ancia que tem que ser dada a concretizac~ao de um algoritmo de sincronizac~ao. As vantagens que alguns algoritmos apresentam relativamente a
outros podem tornar-se completamente irrelevantes face as limitaco~es que uma concretizac~ao
do algoritmo possa implicar.
O facto de os erros mais relevantes se veri
carem no sistema UNIX, podera ser explicado
pelo facto de este sistema n~ao ser um executivo de tempo real.
35
36
Captulo 7
Conclus~oes
Pensamos ter alcancado os objectivos do trabalho, ja que os algoritmos foram realizados e,
pelo menos ate onde foi possvel fazer a sua veri
cac~ao, funcionaram bem.
Como desenvolvimentos futuros pretendemos efectuar uma modi
cac~ao no algoritmo de
Acordo a posteriori de modo a permitir uma exibilidade total no que respeita ao numero de
processadores necessarios para a execuc~ao do algoritmo. Recordemos que este numero depende
da quantidade de processadores que se admite poderem falhar, fp. A modi
cac~ao que pretendemos efectuar permitira um ajuste de fp ao numero de processadores que est~ao a executar o
algoritmo, ou seja, se o numero de processadores for N a quantidade de faltas de processadores
admitidas nessa situac~ao sera (N ; 1)=2.
Estudos futuros poder~ao incidir sobre a possibilidade da realizac~ao de um dos algoritmos
estudados neste trabalho em redes locais separadas. Este trabalho envolveria a concepc~ao de um
algoritmo que permitisse manter os tempos globais de cada uma das redes locais sincronizados
entre si.
Pretendemos ainda aprofundar os resultados obtidos neste trabalho, realizando medidas do
desempenho dos algoritmos no sistema operativo UNIX. Estes resultados poder~ao ser obtidos
utilizando as portas serie das estac~oes SUN onde se executam os algoritmos em conjugac~ao com
um analisador digital de sinais e algum hardware adicional.
Finalmente, pensamos que a realizac~ao do algoritmo de Acordo a posteriori no nucleo do
sistema UNIX seria extremamente vantajosa, ja que teriamos um valor de ;desf muito reduzido
e, consequentemente, uma optima precis~ao dos relogios virtuais. Por outro lado, a realizac~ao
de um servico de tempo sincronizado no nucleo do UNIX, facultaria o desenvolvimento de uma
vasta gama de aplicaco~es que zessem uso desse servico.
37
38
Bibliograa
Cristian 89]
Dolev 83]
Fonseca 90]
Halpern 84]
Kopetz 87]
Kopetz 89]
Lamport 82]
Lamport 85]
Lundelius 84]
Mahaney 85]
Powell 91]
Flaviu Cristian. Probabilistic clock synchronization. Distributed Computing,
Springer Verlag, 1989(3), 1989.
D. Dolev and R. Strong. Authenticated Algorithms for Byzantine agreement.
SIAM J. on Comput., (12), November 1983.
H. Fonseca, L. Rodrigues, J. Ru
no, and Paulo Verssimo. Local Support Environment: User Speci
cation. Technical Report RT/50-90, INESC, Lisboa,
Portugal, August 1990.
Joseph Y. Halpern, Barbara Simons, and Ray Strong. Fault-tolerant clock
syncronization. In 3Rd ACM Sump. Principl. of Distributed Computing,
Vancouver Canada, August 1984.
Hermann Kopetz. Clock syncronization in distributed real-time systems.
IEEE Transactions on Computers, C-36(8), August 1987.
Hermann Kopetz and Wolfgang Schwabl. Global Time in Distributed RealTime Systems. Technical Report 15/89, Technische Universitat Wien, Treitlstrasse 3/182/1 A-1040 Wien Austria, October 1989.
L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem.
ACM Transactions on Prog. Lang. and Systems, 4(3), July 1982.
L. Lamport and P. Melliar-Smith. Synchronizing clocks in the presence of
faults. Journal of the ACM, 32(1), January 1985.
Jennifer Lundelius. A new fault-tolerant algorithm for clock syncronization.
In 3rd ACM SIGACT-SIGOPS Symp. on Principles of Distrib. Computing,
Vancouver-Canada, August 1984.
Stephen R. Mahaney. Inexact agreement: accuracy, precision, and graceful degradation. In Procs. 4th Symposium Princ. Distributed Computing,
Montreal-Canada, August 1985.
David Powell, Marc Chereque, Peter Barret, Douglas Seaton, Gottfried
Bonn, and Paulo Verssimo. The Delta-4 Distributed Fault-Tolerant Architecture. Technical Report, LAAS-CNRS/Esprit Delta-4, 1991.
39
Ramanathan 90] Parameswaran Ramanathan, Kang G. Shin, and Ricky W. Butler. Faulttolerant clock synchronization in distributed systems. IEEE,Computer, 33{
42, October 1990.
Rodrigues 91a] L. Rodrigues and P. Verssimo. A posteriori agreement for clock synchronization on broadcast networks. Technical Report, INESC, March 1991.
Rodrigues 91b] L. Rodrigues and P. Verssimo. xAMp: a multi-primitive group communications service. Technical Report, INESC, March 1991.
Schneider 87] Fred B. Schneider. Understanding Protocols for Byzantine Clock Synchronization. Technical Report, Department of Computer Science, Cornell University, Cornell University, Ithaca,New York 14853, August 1987.
Srikanth 87]
T. K. Srikanth and Sam Toueg. Optimal clock synchronization. Journal of
the Association for Computing Machinery, 34(3), July 1987.
Verissimo 89a] P. Verssimo, L. Rodrigues, and M. Baptista. AMp: a highly parallel atomic multicast protocol. In SIGCOM'89 Symposium, ACM, Austin-USA,
September 1989.
Verissimo 89b] Paulo Jorge Verssimo. Comunicac~ao em Grupo Fiavel, em Sistemas Distribuidos sobre Rede Local. PhD thesis, Universidade Tecnica - IST, Lisboa Portugal, Dezembro 1989.
40
Ap^endice A
Servico de tempo do xAMp - Manual
do utilizador
Neste ap^endice apresentamos integralmente o relatorio utilizado no projecto Delta-4, descrevendo o servico de tempo do xAMp e a interface com o utilizador por ele oferecida. O texto
foi mantido na lngua em que foi escrito originalmente, uma vez que a sua traduc~ao implicava
um grande e (pensamos) desnecessario disp^endio de tempo.
O servico de tempo descrito baseia-se no algoritmo de Srikanth. A vers~ao nal do servico
de tempo oferece, alem deste algoritmo, o algoritmo de Acordo a posteriori. As interfaces com
o utilizador s~ao id^enticas para cada um dos algoritmos, sendo apenas diferentes os nomes das
primitivas e as express~oes para o calculo dos par^ametros.
A.1 Introduction
The goal of the Time Service is to o#er a reliable time source which can be used by any
user in the distributed network. The clock synchronization algorithm proposed by Srikanth
Srikanth 87] is used in order to establish a global time base along the network.
In this document we explain the Time Service user interface. The previous implementation
of this service presented some limitations. These limitations were suppressed and now, the
existing ones are only due to hardware and network characteristics.
A.2 General concepts
In a distributed network the concept of global time does not exist. This is due to the fact
that each hardware clock in the network shows a di#erent time from the other clocks. Even if
we could set instantly all the clocks to the same time, they would drift apart because of their
drift rate, and again they would present di#erent times. To overcome this problem a clock
41
synchronization algorithm can be used.
With such an algorithm we create a virtual clock in each node of the distributed network.
Each of them is synchronized with all the other virtual clocks in the system, thus, creating a
global time base.
Clock synchronization algorithms are based on the exchange of messages between all processors in the network. This messages are exchanged periodically to guarantee the synchronization
of virtual clocks. The so called resynchronization period (Tr) is a constant in the network. The
time interval used to prepare, send and process a message is called the delivery time (tdel).
The physical limitations imposed to the algorithm used, are the upper bound of hardware
clocks drift rate (), and the upper bound of the delivery time (tdel). Later we will see that the
better precision we can achieve depends on these two parameters.
The precision property states that the maximum di#erence between two virtual clocks is
always smaller than some constant Dmax .
The accuracy property states that the drift rate of any virtual clock is smaller than some
constant . The accuracy of virtual clocks can not be better than that of physical clocks.
If a processor deviates from its algorithm or if its physical clock has a drift rate higher than
then the processor is faulty. The algorithm is able to tolerate faulty processors as long as
there are su&cient non-faulty processors in the network.
Finally, it is important to note that this synchronization algorithm is an internal one and
so the global virtual time in the system is an abstract time. The virtual clock can be viewed as
a continuously incremented value, starting from zero. So, its absolute value is not related with
the external \real time". However, the running rate of the virtual clock is related to the rate of
a \real time" clock by the constant . To relate the absolute value of virtual time to the value
of \real time" it would be necessary to use an additional external synchronization algorithm.
A.3 User interface
The interface o#ers three functions which allows the user to make the best use of the Time
Service. One is to initialize the algorithm in the local node, other is to read either the physical
or the virtual local clocks and the last is to stop the algorithm when it is no longer needed in
the local node.
A.3.1 Initialization
Declaration and Usage
type
type
SyncPars
SyncStatus
42
SyncStatus portSyncInit ( SyncPars* parameters )
Description
This function is used to initialize the algorithm. Because there is not a single mode of
synchronization we must specify some parameters that indicate how the algorithm will run. If
it is detected some kind of error with these parameters then an error status will be set.
parameters is a pointer to the structure that contains the initialization parameters. This
structure is named SyncPars and contains the following elds which must always be set:
SyncType
SyncType
SyncType
SyncType
int
Bool
Bool
max_dev_rate
t_del
max_dif
period
faulty
is_joining
do_sync
In the current implementation the type SyncType is of standard type double, capable of
handling oating point positive and negative numbers. Variables of type Bool can take either
the value TRUE or the value FALSE. int is the integer type.
max dev rate, t del
These two parameters are imposed by physical layers. max dev rate is an upper bound of
physical clocks drift rate and t del is an upper bound of delivery time.
For a maximum drift rate of 0.1% we must set max dev rate to 0.001. Delivery time must
be supplied in seconds.
max dif
The maximum di#erence allowed between two virtual clock times must obey to the following condition:
Dmax tdel (1 + )3 + tdeldr
in which dr is the rate of drift between two virtual clocks:
Dmax must be supplied in seconds.
+ )
dr = (2
1+
43
(A.1)
(A.2)
period
Knowing the precision of virtual clocks (Dmax ), it is possible to determine the resynchronization period which must be smaller them Trmax:
Trmax = (1D+max
)d
r
;
tdel ; tdel
dr 1 + (A.3)
and higher than Trmin:
Trmin = 2tdel(1 + ) + Dmax(1 + )2
(A.4)
Higher resynchronization periods are better because they imply a lower number of exchanged messages in the network.
This parameter is also speci
ed in seconds.
faulty
If the network has N processors and f of them are faulty, then the algorithm will only
work if
N 2f + 1
(A.5)
If f = 0 then only one non-faulty process will be necessary to proceed with the synchronization 1. Usually, it is used f 1.
is joining
When f = 1 there must be two non-faulty processes to begin the algorithm. If there is a
third process who wants to initialize, then, because the algorithm is already running, this
process must join the processes running. To do this we must set parameter is joining to
TRUE 2.
The rst f + 1 processes to initialize must set is joining to FALSE.
do sync
If this parameter is set to TRUE then the algorithm will work normally, and a virtual
clock will be created. If it is set to FALSE then then algorithm will not run. In this case
the physical time will be always returned by user request.
This parameter works in a preventive way. It is used to guarantee that the physical time
will always be supplied, even if the implementation of the algorithm does not work well.
There are still two parameters, not included in the stated list which are:
1 It makes no sense to have f = 0 because synchronization is associated to a group of processes and in this
case there is synchronization with only one process. Note that 2 processes are enough to assure synchronization
when f = 1.
2 In a future implementation we will try to make the dierence between start and join transparent to the
user.
44
Bool
SyncType
optim_sync
dev_rate
They are used for debugging and, in order to preserve a good performance, optim sync
must be set to FALSE and dev rate must be set to 0 (zero).
The error status can take the following values:
ME OK if successful initialization.
ME INT if violation of conditions A.1, A.3 or A.4.
MRE ALROPEN if algorithm was already initialized. Note that this does not a#ect
the normal proceeding of the algorithm. This could be only a warning.
A.3.2 Reading the time
Declaration and Usage
type
type
SyncType
SyncReqType
SyncType
portSyncRequest ( SyncReqType request )
Description
This function permits to read either the physical or the virtual clocks. To read the physical
clock request must be PC REQ and it must be VC REQ to read the virtual clock.
If the algorithm is not yet initialized then it will be returned the value ZERO for both the
requests. This value will also be returned if less than f + 1 processes have initialized.
If the parameter do sync is set to FALSE then both request types will return the physical
time.
The time value returned is in seconds. So, as SyncType can handle oating point numbers,
the integer part of the returned value contains the seconds, and we can obtain an increased
granularity if we use the fractional part of this value. Note that even apparently having a
granularity as high as that allowed by double precision numbers, there is always a limitation
imposed by the hardware clock granularity.
45
A.3.3 Stopping synchronization
Declaration and Usage
type
SyncStatus
SyncStatus
portSyncStop ()
Description
When there is no more need to use the xAMp Time Service, this function should be called
to free resources in use by this service. Super uous exchanged messages are saved.
When synchronization is stopped in some node, nothing guarantees that the algorithm will
continue running in the other nodes of the network because the number of nodes still remaining
may be less than the required (this depends on faulty parameter speci
cation).
This function returns an error status which can take one of the two following values:
ME OK on successful completion.
MRE NOTOPEN if initialization is not yet performed.
A.4 Implementation notes
- The xAMp Time Service has been already implemented and tested on SUN Workstations
running SunOS Release 4.1, and on NAC boards.
- When we rst tried to implement this service on the NAC boards, some problems were
found when using double type variables. These problems do not exist anymore and so the
Time Service is running without restrictions.
- The only restrictions still existing are related to hardware limitations as speci
ed in
section A.3.1 and so they have nothing to do with the algorithm itself.
- The parameters that must be speci
ed are passed to the xAMp using an icb block. The
format of the icb will be speci
ed on a future release of this document.
- The le syncpar.h must be included because it de
nes the types used.
46
A.5 An application example
As we have seen, to use the xAMp Time Service it is necessary to initialize it (using
portSyncInit function). Thus, some parameters must be calculated so that synchronized clocks
accuracy can take the value we want to our system.
The rst step consists on assuming a consistent value to parameters max dev rate () and
t del 3. Let's suppose that physical clocks deviate, at most, a second for each 24 hours. This
gives = 0:00001157. Allowing a security margin we can assume that
= 0:00002
Let's assume also that
tdel = 0:1sec:
Using equation A.1 we calculate the maximum accuracy we can achieve, which is
0:100008sec:. Because we do not need the clocks to be extremely synchronized, we set max dif
to a higher value:
Dmax = 0:5sec:
Finally, we calculate the bounds to resynchronization period (using equations A.3 and A.4).
Trmax 10000sec: Trmin 0:7sec:
Then, the value for resynchronization period can be 7200 seconds (2 hours).
When initializing, parameters are set as follows:
max_dev_rate
t_del
max_dif
period
3
=
=
=
=
0.00002
0.1
0.5
7200
Normally, manuals provide these values!
47