Upload
maisa-cordeiro
View
218
Download
0
Embed Size (px)
Citation preview
8/16/2019 SD05 - Sincronização
1/41
SistemasDistribuídos
Parte 05Sincronização
8/16/2019 SD05 - Sincronização
2/41
O Problema daSincronia de Tempo
• Não há garantias de que dois ou maisprocessos cooperantes interpretem acontagem de tempo igualmente
– Cada processo pode estar em umamáquina diferente, o que signica quecada um pode estar usando um rel!giofísico diferente
– Não há como garantir que os dois rel!giosestão e"atamente sincroni#ados $na%erdade, isso & quase impossí%el'
8/16/2019 SD05 - Sincronização
3/41
O Problema daSincronia de Tempo
• (ue problemas isso pode gerar) – Não há como garantir a troca de
mensagens síncrona•
* e"ecu+ão de e%entos em determinada desequncia pode ser comprometida – Não há como garantir a e"clusão m-tua
• * aloca+ão de recursos compartilhados podefalhar
–
O monitoramento de e%entos se turnamais comple"o• Não há como determinar quando e"atamente
um determinado e%ento ocorreu, o que podecomprometer a rea+ão dese.ada
8/16/2019 SD05 - Sincronização
4/41
O Problema daSincronia de Tempo $cont/'• Como solucionar o problema)
–Opção 1: Solução Centralizada•
0uncionamento1 Todos os processosen%ol%idos em determinada ati%idade usamcomo referncia uma -nica fonte de tempo$um rel!gio -nico, um processo,///'
•
2antagem1 – * garantia de que todos estão obtendo a
informa+ão de tempo no mesmo lugar, o quee%ita informa+3es inconsistentes
8/16/2019 SD05 - Sincronização
5/41
O Problema daSincronia de Tempo $cont/'• Como solucionar o problema)
–Opção 1: Solução Centralizada• Problemas1
– * fonte -nica de tempo tamb&m & um ponto -nicode falha, ou se.a, diante de uma pane na fonte detempo todos os processos são comprometidos
– Dependendo da quantidade de processos
en%ol%idos, a fonte de tempo pode sesobrecarregar com a quantidade de mensagensde4para ela
– *s mensagens com informa+3es de tempo podemsofrer atrasos impre%isí%eis durante seu tráfego na
rede, comprometendo a e"atidão
8/16/2019 SD05 - Sincronização
6/41
O Problema daSincronia de Tempo $cont/'• Como solucionar o problema) $cont/'
– Opção 2: Solução Distribuída
• 0uncionamento1• 2ários processos se encarregam de regular
as informa+3es de tempo, comparando efa#endo a.ustes entre si
8/16/2019 SD05 - Sincronização
7/41
O Problema daSincronia de Tempo $cont/'• Como solucionar o problema) $cont/'
– Opção 2: Solução Distribuída• 2antagem1
– Não há um ponto -nico de falha/ * queda de um-nico processo não interfere na sincroni#a+ão dotempo entre os demais
– 5aior disponibilidade da informa+ão de tempo, .áque não há uma fonte -nica
• Problemas1 – 5aior comple"idade para implementar a solu+ão – (uantidade %ariá%el de mensagens $nem sempre
pre%isí%el'
8/16/2019 SD05 - Sincronização
8/41
O Problema daSincronia de Tempo $cont/'• Como solucionar o problema) $cont/'
– * op+ão distribuída $op+ão 6' & a maisadequada para ambientes distribuídos porque1
• *s informa+3es rele%antes ao processo estãodispersas por %árias máquinas
• Cada processo de%e tomar decis3es baseadosomente em informa+3es locais
• * e"istncia de um ponto -nico de falha de%e sere%itada sempre que for p!ssí%el
• Não e"iste um rel!gio -nico para todas as máquinas
8/16/2019 SD05 - Sincronização
9/41
7el!gios 8!gicos
• 9m algumas tarefas distribuídas, otempo real não & importante/ – O foco do controle de tempo & %oltado
para a correta sequncia de e%entos quede%e acontecer• * informa+ão de tempo neste caso &
usada como um contador de e%entos,que determina o que de%e acontecera cada momento
8/16/2019 SD05 - Sincronização
10/41
7el!gios 8!gicos
• 9m :; toda a informa+ão de
tempo & relati%a entre os processos que trocam
mensagens – Se dois processos não interagem entre si, não há
necessidade de sincroni#a+ão de tempo entre eles – Na maioria das %e#es & necessário que os
processos concordem com a informa+ão de tempoentre eles, mas este tempo não precisa ser real
8/16/2019 SD05 - Sincronização
11/41
*lgoritmo de 8amport• 0uncionamento do algoritmo1
• Cada processo cooperante tem seu pr!prio rel!gio l!gico $independentedo tempo real', que ser%e como contador de e%entos
– Cada e%ento ocorrido incrementa uma unidade de tempo no contador• Cada mensagem trocada entre dois processos cooperantes cont&m uma
informa+ão de tempo $rel!gio l!gico' fornecida pelo emissor damensagem• O processo receptor compara a informa+ão de tempo contida na
mensagem com seu pr!prio rel!gio l!gico1 – Se seu rel!gio l!gico possuir um %alor maior que o tempo contido na
mensagem, o rel!gio permanece com o mesmo %alor –
Se seu rel!gio l!gico possuir um %alor menor ou igual que o tempocontido na mensagem, o rel!gio & a.ustado e passa a ter o %alor damensagem mais um
• ?sso garante que dois e%entos nunca aconte+am ao mesmo tempo
8/16/2019 SD05 - Sincronização
12/41
*lgoritmo de 8amport
$e"emplo'• ?magine trs processos $P:, P6 e P@' locali#ados emmáquinas diferentes que iniciam algum tipo de intera+ãosincroni#ada – Os @ processos iniciam seus rel!gios l!gicos, mas cada
clocA físico oscila em frequencias diferentes• Suponha1 – O clocA l!gico de P: %aria de B em B unidades – O clocA l!gico de P6 %aria de = em = unidades – O clocA l!gico de P@ %aria de : em : unidades
•
No primeiro instante, todos os rel!gios estão #erados• No segundo instante, os rel!gios l!gicos .á não estão iguais
$P:B, P6= e P@:'• 9sta %aria+ão aumenta conforma os instantes se passam
$e"emplo1 no instante E P:6F, P6@6 e P@F'
8/16/2019 SD05 - Sincronização
13/41
*lgoritmo de 8amport
$e"emplo' – Cada mensagem trocada entre os processos precisaconter o %alor que o rel!gio físico de seu emissor paraque o receptor fa+a os a.ustes necessários
• No instante 6 a mensagem * & en%iada de P: para P6• No instante F a mensagem G & en%iada de P6 para P@• No instante < a mensagem C & en%iada de P@ para P6• No instante ; a mensagem D & en%iada de P6 para P:
– Considere que cada mensagem en%iada chega a seudestino no instante seguinte ao que foi en%iada
• *s mensagens * e G chegam a seus destinos sem causar impacto,pois o rel!gio l!gico de cada receptor cont&m um %alor maior queaquele que consta em cada mensagem
• *s mensagens C e D obrigam seus receptores a efetuar um a.ustenos rel!gios l!gicos para garantir a correta sincronia dos e%entos
8/16/2019 SD05 - Sincronização
14/41
*lgoritmo de 8amport
$e"emplo'Instante Relógio P1 Relógio P2 Relógio P:
6 B = :
@ :6 :B 6F := 6F @
E 6F @6 F
B @ F E
< @B F= B= F6 B:
8/16/2019 SD05 - Sincronização
15/41
Problema no*lgoritmo de 8amport• Considere1
– 7$e:' o %alor do rel!gio l!gico para o e%ento He:I – 7$e6' o %alor do rel!gio l!gico para o e%ento He6I – * solu+ão porposta por 8amport não garante que se 7$e:' J
7$e6' então o e%ento He:I acontece antes que o e%ento He6I• 9"emplo1
– Se compararmos os %alores de rel!gio em cada mensgaem, temos1• 5sgK* $:' J 5sgKG$F' então 5sgK* ocorreu antes de 5sgKG !"orreto#• 5sgKC $@' J 5sgKG$F' então 5sgKC ocorreu antes de 5sgKG !in"orreto#
Pro"esso P1 Pro"esso P2 Pro"esso P
: @ 6
6 B F
@ ; BF :6 =
M sg A ( 1)
Msg B ( 4 )
M sg C ( 3 )
8/16/2019 SD05 - Sincronização
16/41
Solu+ão 2etorial $5attern e 0idge'
• Solu+ão proposta por 5attern e 0idge1 – O rel!gio l!gico passa a ser um %etor contador de
e%entos – Se e"istem N processos cooperando, o %etor terá N
posi+3es inteiras, onde cada posi+ão corresponde a umcontador de e%entos
– Cada processo terá um %etor para si – Cada mensagem en%iada cont&m a %ersão atuali#ada do
%etor do emissor
• 9sta solu+ão & muito usada em1 – 2erica+ão de consistncia de estados em SD – Controle de checApoints – 7ecupera+ão de erros –
7ollbacAs
8/16/2019 SD05 - Sincronização
17/41
8/16/2019 SD05 - Sincronização
18/41
Solu+ão 2etorial $9"emplo'
8/16/2019 SD05 - Sincronização
19/41
Solu+ão 2etorial
• Des%antagem da solu+ão1 – OcupaKse mais espa+o de arma#enamento e
carga -til da mensagem
• Mma solu+ão deri%ada dos rel!gios%etoriais1 –
H7el!gios de matri#I• *l&m de seu pr!prio %etor, cada processo mant&m
estimati%as do tempo %etorial dos outros processos
8/16/2019 SD05 - Sincronização
20/41
7el!gios 0ísicos
• O algoritmo de 8amport e as demais solu+3es de rel!giosl!gicos se preocupam apenas com a ordena+ão dee%entos – Os instantes de tempo associados a cada e%ento não são
necessariamente pr!"imos do tempo em que os e%entos realmenteaconteceram
• 9m alguns sistemas o conhecimento do instante de temporeal & muito importante $e"emplo1 sistemas de tempo real' – Para este tipo de sistema são necessários clocAs físicos e"ternos
• 9m certos casos, & dese.á%el a e"istncia de mais de um clocA
e"terno, para garantir ecincia e redundncia – Problemas1
• Como sincroni#áKlos com o tempo real)• Como sincroni#ar esses clocAs entre si)
8/16/2019 SD05 - Sincronização
21/41
9%olu+ão da 5arca+ão de
Tempo• Primeiras solu+3es para marca+ãode tempo – 7el!gios de sol, esta+3es do ano, /// – Dia solar1 inter%alo decorrido entre
duas passagens consecuti%as do Solem determinado ponto do c&u
• S&culo 2??1 primeiros rel!giosmecnicos –
(uanto maior a qualidade do processode fabrica+ão, mais preciso o processode marca+ão do tempo
– *inda era muito difícil garantir umasincronia de tempo eciente
8/16/2019 SD05 - Sincronização
22/41
9%olu+ão da 5arca+ão de
Tempo• D&cada de :;F1 *.ustes paracompensar imprecis3es – 0oram feitos a.ustes articiais na
marca+ão ocial de tempo paracompensar imprecis3es resultantes defenmenos naturais que inQuenciamdiretamente nas fontes de tempoutili#adas
• DescobriuKse que a rota+ão da terranão & constante, de%ido Rs mar&s ea atmosfera $desaceleram a rota+ãoda Terra'
• * dura+ão do ano $em dias' diminuiu$os dias caram mais longos'
• O turbulncias no n-cleo do planetainQuenciam no comprimento do dia
8/16/2019 SD05 - Sincronização
23/41
9%olu+ão da 5arca+ão de
Tempo• 9m :;F=1 in%en+ão dorel!gio atmico – Contagem de segundos a
partir das transi+3es deel&trons de um átomo deC&sio :@@• uma medida mais
precisa e constante,que não sofreinQuncias e"ternas
8/16/2019 SD05 - Sincronização
24/41
9%olu+ão da 5arca+ão de
Tempo• *tualmente1 – T*? $Tempo *tmico ?nternacional'
• 5&dia de tempo dos rel!gios atmicos
• mais preciso, por&m ainda & necessário a.ustáKlo acontagem de tempo solar adotada no diaKaKdia
• *.uste do T*? $Tempo *tmico ?nternacional' – MTC $Tempo Mni%ersal Coordenado'
•
o T*? a.ustado ao tempo solar• O a.uste & feito inserindoKse segundos Hbisse"tosI• 2em gradati%amente substituindo o uso do 5T• *cesso1 N?ST $rádio UU2' e 9OS $Sat&lite'
8/16/2019 SD05 - Sincronização
25/41
9%olu+ão da 5arca+ão de
Tempo• 7el!gio *tmico Grasileiro $MSP'
8/16/2019 SD05 - Sincronização
26/41
8/16/2019 SD05 - Sincronização
27/41
9%olu+ão da 5arca+ão de
Tempo• 9OS
8/16/2019 SD05 - Sincronização
28/41
*lgoritmo de Cristian
• 0uncionamento1• Msa um ser%idor de tempo, que & um computador equipado
com receptor MTC• *s demais máquinas en%iam mensagens para o ser%idor de
tempo perguntando pelo tempo corrente• O ser%idor de tempo responde o mais rápido possí%el, com
uma mensagem contendo o tempo MTC corrente• Cada máquina, ao obter a resposta, a.usta seu clocA• O ser%idor de tempo & P*SS?2O/ O a.uste depende da
inciati%a das demais máquinas
• Problemas1• O tempo nunca pode andar para trás $os a.ustes são sempre
progressi%os'• * consulta ao ser%idor de tempo gasta um tempo nãoKnulo $o
retardo pode %ir a ser grande'
8/16/2019 SD05 - Sincronização
29/41
*lgoritmo de Cristian $cont/'
• 5ais um problema1 – uma solu+ão altamente centrali#ada
• Para minimi#ar a centrali#a+ão, podeKse
adotar os seguintes caminhos1 – Ter %ários ser%idores com receptor MTC – *s demais máquinas passam a solicitar a hora por meio de
mensagens multicast
• 9sta solu+ão & um algorítmo probabilístico, ouse.a1 – S! se obt&m uma sincroni#a+ão aceitá%el se o tempo de ida e
%olta das mensagens forem curtos o suciente secomparados a precisão dese.ada
8/16/2019 SD05 - Sincronização
30/41
*lgoritmo de Cristian $cont/'
• Solu+ão para os a.ustes sempreprogressi%os
• * mudan+a no clocA de%e ser feita de forma
gradati%a e sempre a%an+ando o rel!gio• Se o a.uste & de : ms, basta adicionar ; ms
para atra#ar ou :: ms para adiantar
8/16/2019 SD05 - Sincronização
31/41
*lgoritmo de Cristian $cont/'
• Solu+ão para o retardo na mensagem• Tentar medir $estimati%a' o tempo de
transmissão
T ////////////////// tempo de en%io da requisi+ão T: ////////////////// recebimento da resposta
$T: K T'46 /////// tempo apro"imado de propaga+ão damensagem
? //////////////////// tempo de tratamento da interrup+ão
$T: K T K ?'46 /// estimati%a ainda mais precisa• Outra solu+ão1
– 7eali#ar %árias medidas e calcular a m&dias de tempo$descartando %alores fora de um certo limite'
8/16/2019 SD05 - Sincronização
32/41
*lgoritmo de GerAeleV
• 0uncionamento• O ser%idor de tempo & uma entidade *T?2*, que consulta periodicamente cada
uma das máquinas do sistema para saber o tempo corrente em cada uma delas• Gaseado nas respostas obtidas1
– Calcula o tempo m&dio e o a.uste que cada máquina terá
que fa#er – ?nforma Rs demais máquinas para adiantar ou atrasar seus
clocAs, tornandoKse iguais ao tempo m&dio calculado – Não informa a hora corrente e sim o a.uste a ser feito – O cálculo que o ser%idor fa# tamb&m le%a em conta a
e"istncia de respostas HabsurdasI $muito fora da m&diadas demais máquinas'/ – 9stas repostas HabsurdasI são descartadas do cáculo de
a.uste para e%itar um des%io indese.ado dos resultados
8/16/2019 SD05 - Sincronização
33/41
*lgoritmo de GerAeleV
• * precisão deste algoritmo tamb&mdepende do tempo má"imo gastopelas mensagens de ida e %olta
• ?ndicado para1 – (uando nenhuma das máquinas tem um
receptor MTC – * necessidade de precisão no ambiente &
pequena
8/16/2019 SD05 - Sincronização
34/41
*lgoritmo de GerAeleV$cont/'• Problemas1
– O a.uste do ser%idor de tempo de%e serfeito periodicamente por um operador
$de forma manual' – uma solu+ão altamente centrali#ada
• Para contornar esta fragilidade, ao seperceber que o ser%idor de tempo falhou,elegeKse outro ser%idor para o seu lugar
• O problema agora passa a ser comodeterminar que o ser%idor de tempo falhou
8/16/2019 SD05 - Sincronização
35/41
NetWorA Time Protocol
• Os algorítmos de Cristian e GerAeleV ,embora ecientes, se dedicam mais aredes pequenas e intranets – 9m ambientes com uma grande quantidade
de máquinas, como a ?nternet, & quaseimpossí%el garantir o bom funcionamentodestas duas solu+3es•
Pela nature#a assíncrona das opera+3esdesempenhadas na Web• Pela ausncia de garantia de entrega de
mensagens em um tempo ra#oá%el
8/16/2019 SD05 - Sincronização
36/41
NetWorA Time Protocol$cont/'• O NTP foi pro.etado como um ser%i+o e
protocolo para distribuir informa+3es de tempopela ?nternet
•
Ob.eti%os1 – Ser um ser%i+o para clientes internet sesincroni#arem pelo MTC, superando atrasos e perdasde mensagens• ?sso & feito por meio de t&cnicas estatísticas de
ltragem da informa+ão – 0ornecer um ser%i+o coná%el que sobre%i%a a
longas perdas de conecti%idade• Msando ser%idores e rotas redundantes para
circula+ão das mensagens
8/16/2019 SD05 - Sincronização
37/41
NetWorA Time Protocol$cont/'• Características1
– Permite sincroni#a+ão ra#oa%elmentefrequente dos clientes
• Para compensar falhas originadas naquantidade de clientes e ser%idoresinteragindo
– 0ornece prote+ão ao ser%i+o de tempocontra interferncias acidentais ouintencionais• *utentica+ão, %alida+ão de mensagens
8/16/2019 SD05 - Sincronização
38/41
8/16/2019 SD05 - Sincronização
39/41
NetWorA Time Protocol$cont/'• 0uncionamento1
– Cada ní%el da ár%ore & chamado de HstratumI• Stratum :1 ser%idores primários $rai#'• Stratum 61 ser%idores secundários•
Stratum @1 outros ser%idores• Stratum F1 mais ser%idores• e assim por diante///
– (uanto mais alto o n-mero do stratum, a tendncia &que a precisão se.a menor neste ní%el
– possí%el reali#ar altera+3es na hierarquia para superarindisponibilidade de ser%i+o/ Por e"emplo1
• HPromo%erI máquinas mapa um stratum mais alto• Deslocar HgalhosI inteiros para se sincroni#arem com outros ser%idores
8/16/2019 SD05 - Sincronização
40/41
NetWorA Time Protocol$cont/'
• Como a sincronia & feita) – *s mensagens são transmitidas %ia
protocolo MDP
– * mensagem pode ser en%iada de @ modos1• 5odo :1 %ulti"ast
– ?deal para redes locais de alta %elocidade – Ser%idores de tempo en%iam mensagem e as
demais máquinas a.ustam seus rel!gios – Possui uma margem de erro grande, que
resulta em bai"a precisão
8/16/2019 SD05 - Sincronização
41/41
NetWorA Time Protocol$cont/'
• 5odo 61 RPC – Msa a solu+ão de Cristian para sincroni#ar – mais preciso que a op+ão de multicast
• 5odo @1 Sim&tri"o – *dotado em máquinas cu.o stratum & bai"o – a op+ão mais precisa –
Os ser%idores trocam mesagens de tempoentre si e as informa+3es são arma#enadaspara uso posterior %isando melhorar cada%e# mais a sincronia