5 - Sincronizacao

Prévia do material em texto

Instru
tor's Guide for Colouris et al.
Sistemas Distribuídos
Guilherme Bertoni Ma
hado
Fa
uldades SENAC
Análise e Desenvolvimento de Sistemas
2011/2
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Modelo de Interação (Clo
ks e Eventos)
Em SDs é difí
il estabele
er limites de tempo sobre o tempo
tomado para exe
ução de pro
essos, entrega de mensagens ou
lo
ks's drifts.
Duas posições extremas, opostas, propor
ionam um par de
modelos simples: o primeiro, tendo uma forte hipótese sobre o
tempo e o segundo, não fazendo nenhuma hipótese sobre o
mesmo.
Sistemas Distribuídos Sín
ronos
Sistemas Distribuídos Assín
ronos
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Sistemas Distribuídos Sín
ronos
Hadzila
os e Toueg [1994℄ de�nem um SD sín
rono, 
omo
sendo um sistema 
om os seguintes limites de�nidos:
o tempo para exe
utar 
ada etapa de um pro
esso tem limites
inferiores e superiores 
onhe
idos;
ada mensagem transmitida sobre um 
anal é re
ebida dentro
de um tempo limitado 
onhe
ido;
ada pro
esso tem um 
lo
k lo
al 
uja drift rate de tempo real
tem um limite 
onhe
ido.
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Sistemas Distribuídos Sín
ronos
É possível sugerir limites inferiores e superiores para o tempo
de exe
ução de pro
essos, retardo de mensagens e 
lo
k drift
em um SD.
Mas, é difí
il 
hegar em valores realísti
os e prover garantia
dos valores es
olhidos.
A menos que os valores dos limites possam ser garantidos,
qualquer projeto baseado sobre os valores es
olhidos, não
poderá ser 
on�ável.
Contudo, modelando um algoritmo 
omo um sistema sín
rono,
pode ser útil para dar uma idéia de 
omo ele se 
omportará em
um sistema distribuído real.
Em um SD sín
rono é possível usar timeouts, por exemplo,
para dete
tar a falha de um pro
esso, 
omo mostrado na seção
sobre modelo de falhas.
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Sistemas Distribuídos Sín
ronos
SDs sín
ronos podem ser 
onstruídos.
O que é requerido é que os pro
essos realizem tarefas 
om
requisitos de re
ursos 
onhe
idos para os quais eles possam ser
garantidos 
i
los de pro
essador su�
ientes e 
apa
idade de
rede, bem 
omo, os pro
essos serem supridos 
om 
lo
ks 
om
drift rates limitados.
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Sistemas Distribuídos Assín
ronos (De�nição)
Muitos SDs, por exemplo, a Internet, são muitos úteis sem
serem quali�
ados 
omo SDs sín
ronos.
Portanto, ne
essitamos um modelo alternativo: um SD
assín
rono é um sistema no qual não existem limites sobre:
Rapidez na exe
ução de pro
essos
Por exemplo, uma etapa de um pro
esso pode tomar 1
pi
o-segundo (1seg x 10E-12) e uma outra etapa 1
nano-segundo (1 seg x 10E-9); tudo o que se pode dizer é que
ada etapa pode levar um tempo longo arbitrariamente.
Atraso na transmissão de mensagens
Por exemplo, uma mensagem de um pro
esso A para um
pro
esso B pode ser entregue em tempo mínimo e uma outra
pode tomar alguns minutos ou horas. Em outras palavras,
uma mensagem pode ser re
ebida após um tempo longo
arbitrário.
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Sistemas Distribuídos Assín
ronos (De�nição)
Drift Rates dos 
lo
ks - A drift rate de um 
lo
k é arbitrária.
O modelo assín
rono não permite nenhuma hipótese sobre
intervalos de tempo envolvida em qualquer exe
ução.
Isto, exatamente modela a Internet, na qual não existe nenhum
limite intrínse
o sobre 
arga de servidores e 
arga de rede, e
portanto, sobre quanto tempo ela leva para transferir um
arquivo usando FTP. Algumas vezes uma mensagem de email
pode levar dias para 
hegar ao destinatário.
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Sistemas Distribuídos Assín
ronos
Alguns problemas de projeto podem ser resolvidos mesmo 
om
estas hipóteses.
Por exemplo, embora a Web não possa sempre prover uma
resposta parti
ular dentro de um limite de tempo razoável,
browsers tem sido projetados para permitir usuários fazerem
outras 
oisas enquanto eles estão esperando.
Qualquer solução que é válida para um sistema distribuído
assín
rono é também válida para um sistema sín
rono.
SDs reais são muito frequentemente assín
ronos por 
ausa da
ne
essidade para pro
essos 
ompartilharem pro
essadores e
para 
anais de 
omuni
ação 
ompartilharem a rede (o meio de
transmissão).
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Sistemas Distribuídos Assín
ronos
Por exemplo, se vários pro
essos de 
aráter des
onhe
ido estão
ompartilhando um pro
essador, então a performan
e
resultante de qualquer um deles não pode ser garantida.
Mas, existem muitos problemas de projeto que não podem ser
resolvidas para SDs Assín
ronos, mas que podem ser resolvidas
quando alguns aspe
tos de tempo são usados.
Por exemplo, a ne
essidade de um stream de dados multimídia
para ser entregue antes do seu deadline é um desses
problemas. Para problemas tais 
omo este, um modelo
sin
ronizado é requerido.
A impossibilidade de se sin
ronizar 
lo
ks em um sistema
assín
rono
Ordenação de Eventos
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Ordenação de Eventos (Event Ordering)
Em muitos 
asos estamos interessados em saber se um evento
(envio ou re
ebimento de uma mensagem) em um pro
esso,
o
orreu antes, após ou 
on
orrentemente a um outro evento
em um outro pro
esso.
A exe
ução de um SD pode ser des
rita em termos de eventos
e sua ordenação, apesar da falta de 
lo
ks pre
isos.
Considere um grupo de usuários em uma lista de emails: X, Y,
Z e A.
1
Usuário X envia um mensagem 
om o assunto Meeting;
2
Usuário Y e Z respondem enviando uma mensagem 
om o
assunto Re:Meeting;
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Ordenação de Eventos (Event Ordering)
Em tempo real, a mensagem de X foi primeiro enviada, Y lê ela
e responde; Z lê ambas as mensagens de X e Y e então envia
uma outra resposta que referen
ia as mensagens de X e de Y.
Mas, devido aos atrasos nas entregas das mensagens, essas
podem ser entregues 
omo na �gura no próximo slide, e alguns
usuários poderiam ver estas mensagens de resposta (replies) na
ordem errada, 
omo por exemplo, o usuário A poderia ver:
Inbox do usuário A:
From: Subje
t:
Z Re:Meeting
X Meeting
Y Re:Meeting
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Ordenação de Eventos (Event Ordering)
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Ordenação de Eventos (Event Ordering)
Se os 
lo
ks dos 
omputadores de X, Y e Z pudessem estar
sin
ronizados, então 
ada mensagem poderia portar o tempo
do 
lo
k do 
omputador lo
al (um rótulo de tempo), quando
ela fosse enviada.
Por exemplo, mensagens m1, m2 e m3 poderiam portar os
tempos t1, t2 e t3, onde t1<t2<t3.
As mensagens re
ebidas seriam entregues aos usuários de
a
ordo as suas ordens de tempo.
Se os 
lo
ks são aproximadamente sin
ronizados, então esses
rótulos de tempo, frequentemente estarão na ordem 
orreta.
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Ordenaçãode Eventos (Event Ordering)
Dado que 
lo
ks não podem ser sin
ronizados perfeitamente
através de um SD, Lamport [1978℄ prop�s um modelo de
tempo lógi
o que pode ser usado para prover uma ordenação
entre vários eventos em pro
essos rodando em diferentes
omputadores em um SD.
Tempo lógi
o permite a ordem na qual as mensagens são
enviadas/re
ebidas, sem re
orrer a 
lo
ks físi
os das máquinas.
Como o modelo de tempo lógi
o pode ser apli
ado ao Exemplo
da Lista e Emails?
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Ordenação de Eventos (Event Ordering) usando o Modelo
de Tempo Lógi
o
Exemplo: Lista de Emails Logi
amente, sabemos que uma
mensagem é re
ebida após ela ser enviada, e portanto
podemos estabele
er uma ordem lógi
a de pares de eventos,
mostrada na �gura anterior, 
onsiderando somente os eventos
rela
ionados a X e Y:
X envia m1 antes de Y re
eber m1;
Y envia m2 antes de X re
eber m2.
Guilherme Bertoni Ma
hado Sistemas Distribuídos
Instru
tor's Guide for Colouris et al.
Ordenação de Eventos (Event Ordering) usando o Modelo
de Tempo Lógi
o
Também sabemos que as respostas (replies) são enviadas após
re
eber mensagens, portanto, temos a seguinte ordem lógi
a
para Y:
Y re
ebe m1 antes de enviar m2.
O Modelo de Tempo Lógi
o atribui um número a 
ada evento,
orrespondendo a sua ordenação lógi
a, de modo que eventos
o
orrendo mais tarde têm números mais altos do que os
eventos que o
orrem mais 
edo. Por exemplo, a �gura anterior
mostra os números de 1 a 4 sobre os eventos em X e Y
(representando a ordem dos eventos).
Guilherme Bertoni Ma
hado Sistemas Distribuídos
	Instructor's Guide for Colouris et al.