TIME, CLOCK’S
and EVENTS
Lamport 1978
por
João Paulo Ribeiro
Mário Luís Guimarães
Introdução
> O conceito do TEMPO é fundamental no nosso modo de viver.
> É derivado dum conceito mais básico relativo à ordem em
que os acontecimentos ocorrem.
> Num Sistema Distribuído tem-se:
- Vários processos separados espacialmente;
- Comunicam por troca de mensagens;
- Mensagens são eventos;
- Mensagens podem gerar outros eventos.
Novembro 1998
Sistemas Operativos Distribuidos
2
Introdução (cont.)
> Num SD examina-se a ordem de ocorrência dos eventos.
> Definição de ORDEM PARCIAL.
> Algoritmo distribuído para ordenação lógica dos eventos.
> ORDEM TOTAL dos eventos.
> Problemática da ordenação total - solução:
- RELÓGIOS FÍSICOS e algoritmo de sincronização.
Novembro 1998
Sistemas Operativos Distribuidos
3
Relação de Ordem Parcial
> Relação ACONTECE-ANTES (HAPPENS-BEFORE ):
- Relação a  b : a acontece-antes de b
- Verifica as seguintes condições:
- Se a e b são eventos dum mesmo processo e a ocorre
antes de b, então a  b é verdadeiro;
- Se a é o envio duma mensagem por um processo e b
é a recepção da mesma mensagem por outro processo,
então a  b é verdadeira;
Novembro 1998
Sistemas Operativos Distribuidos
4
Propriedades da relação Ordem Parcial
> TRANSITIVIDADE:
- Se a  b e b  c, então a  c
> CONCORRÊNCIA DE EVENTOS:
- Se os eventos a e b acontecem em processos que não se
comunicam, então a  b e b  a não são verdade;
- Eventos a e b são ditos concorrentes.
> A relação “ACONTECE-ANTES” implementa a única ordem
parcial de eventos.
Novembro 1998
Sistemas Operativos Distribuidos
5
Exemplo: eventos entre P, Q e R
Processo P
P4
Processo Q
Q7
Processo R
R4
Q6
P3
Q5
R3
Q4
P2
Q3
R2
Q2
P1
Novembro 1998
Q1
Sistemas Operativos Distribuidos
R1
6
Da Ordem Parcial à Ordem Total
> “RELÓGIOS” LÓGICOS:
- Define-se Ci como relógio lógico do processo Pi
- Ci(a) é a leitura de Ci quando ocorre a em Pi
- Define-se C(a) = Ci(a) se a for evento de Pi
> Condição do Relógio Lógico C(evento):
- Se a  b então C(a) < C(b)
> C(evento) é sempre incrementado entre eventos a e b : a  b
Novembro 1998
Sistemas Operativos Distribuidos
7
Resultados da Condição de Relógio
> C1:
Se a e b ocorrem em Pi e a  b, então Ci(a) < Ci(b)
> C2:
Se a e b ocorrem em Pi e b é a sua recepção em Pj,
então Ci(a) < Cj(b)
> R1:
Cada processo Pi incrementa Ci entre dois eventos
consecutivos;
> R2.a: Evento a é envio da msg. m por Pi; m contém Tm = Ci(a)
R2.b: Quando da recepção de m , Pj altera Cj para Cj > Tm
> FICA VERIFICADA A CONDIÇÃO DE RELÓGIO <
Novembro 1998
Sistemas Operativos Distribuidos
8
Exemplo: relógios lógicos de Lamport
PROCESSO
PROCESSO
PROCESSO
0
1
2
0
0
0
6
8
10
12
16
20
18
24
30
24
32
40
30
40
50
36
48
60
A
B
C
42
61
70
48
69
80
70
77
90
76
85
100
D
Novembro 1998
Sistemas Operativos Distribuidos
9
Ordem Total
• Com o algoritmo anterior obtem-se ordem total entre eventos,
a => b, sse:
Ci(a) < Cj(b) ou
Ci(a) = Cj(b) e Pi  Pj (precedência entre processos)
• No entanto, ordem total ainda não é solução:
Exemplo:
Maria envia msga da máquina A;
Maria telefona a Manuel para este enviar msgb de B;
Apesar de msga  telef.  msgb, o sistema pode ordenar
em primeiro lugar msgb e só depois msga (depende de
C(evento)), pois telef. é exterior ao sistema.
Novembro 1998
Sistemas Operativos Distribuidos
10
Solução para o problema
•Soluções:
 Maria e Manuel estampilham manualmente as mensagens;
 Sistema de relógios que verifique sempre a “Condição
Relógio” anterior:
Se msga  msgb então C(a) < C(b)
• Vamos optar pela segunda solução !
Novembro 1998
Sistemas Operativos Distribuidos
11
Relógios Físicos
• Define-se Ci(t) como o valor do relógio físico de Pi no instante
real t;
• Propriedades:
dCi t 
Exactidão (P1): dt 1  k (k  10-6 rel. de cristais),
é a medida do desvio dos relógios físicos em relação a t;
Precisão (P2): i, j : Ci t   C j t    é a medida máxima
do afastamento entre os relógios do sistema.
• É necessário algoritmo distribuído para garantir:
– Condição de Relógio (a  b então C(a) < C(b));
– Precisão (P2).
Novembro 1998
Sistemas Operativos Distribuidos
12
Algoritmo de sincronização
•  é a duração mínima no envio de uma msg entre dois
processos Pi e Pj, e  é a variação máxima dessa duração
• cada relógio Ci avança ao ritmo de P1
• quando é recebida msga com estamp. Ta=Ci(ta), no instante tb em
Pj, Cj(tb) = máx(Cj(tb), Ta +  )
• admitindo um grafo ligando os vários processos, o diâmetro d
desse grafo é o número mínimo de arcos ligando
quaisquer dois processos.
• então, se com período  »  +  fôr enviada msg para todos os
arcos, Cond. Rel. e P2 são satisfeitas com   d.(2k +  )
Novembro 1998
Sistemas Operativos Distribuidos
13
Conclusões
• Importância de ordenação de eventos num sistema distribuído;
• Ordenação “happened-before” define ordem parcial única entre
eventos;
• Ordem total depende de C(evento), ou seja, dos relógios lógicos;
• Ordem total pode resultar em ordenação incoerente com os
eventos observados;
• Relógios físicos resolvem o problema anterior;
• Algoritmo para realização e sincronização dos relógios físicos;
Novembro 1998
Sistemas Operativos Distribuidos
14
Processo P
P4
Processo Q
Q7
Processo R
R4
Q6
P3
Q5
R3
Q4
P2
Q3
R2
Q2
P1
Novembro 1998
Q1
Sistemas Operativos Distribuidos
R1
15