thesis
Transcrição
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