Relogio logicos

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1055 palavras )
  • Download(s) : 0
  • Publicado : 13 de outubro de 2011
Ler documento completo
Amostra do texto
Relógios Lógicos

November 27, 2009

Sumário

Relação Happened-Before

Relógios de Lamport

Relógios Vectoriais

Eventos
Nem sempre é necessário ter relógios sincronizados: Muitas vezes, é suficiente estabelecer uma ordem entre eventos. Um evento é a ocorrência duma acção executada por um processo: Ao longo da sua execução, um processo pode executar uma dada acção múltiplas vezes, acada uma dessas ocorrências corresponde um evento. Assim, a execução dum processo Pi consiste numa sequência de eventos: ei0 , ei1 , ei2 , . . .

Relação Happened-Before (1/2)

Eventos num sistema distribuído podem ser ordenados usando a relação happened-before, proposta por Lamport, denotada → e definida como se segue:
HB1 se e e e são eventos que ocorrem no mesmo processo por aquela ordem,então: e → e ; HB2 se e é a transmissão duma mensagem e e a recepção dessa mensagem, então e → e ; HB3 se e → e e e → e , então e → e .

Relação Happened-Before (2/2)
p1 p p
2

a

b m1 e c d m2 f

3

A relação happened-before é uma relação parcial: ¬ (a → e) ∧ ¬ (e → a) Eventos como a e e dizem-se concorrentes: a||e. A relação → captura o fluxo de informação entre eventos:
indicapotencial causalidade entre eventos; atenção a canais de comunicação externos/ocultos.

Lamport Clocks and Timestamps (1/3)

Além da relação →, Lamport propôs:
o uso dum relógio lógico por processo, conhecido por Lamport clock ; a associação de timestamps geradas por esse relógio, Lamport timestamps, a cada evento.

A relação entre a relação → e Lamport timestamps é: e → e ⇒ L(e) < L(e ) Relógios Físicos e a Relação HB
P1 0 6 12 18 24 30 36 42 48 54 60 P2 0 8 16 24 32 40 48 56 64 72 80 (a) P3 0 10 20 30 40 50 60 70 80 90 100 P1 0 6 m1 12 18 24 30 P2 adjusts 36 its clock 42 48 m4 70 76 P1 adjusts its clock P2 0 8 16 24 32 40 48 61 69 77 85 (b) P3 0 10 20 30 40 50 60 70 80 90 100

m1

m2

m2

m3

m3

m4

Relógios físicos não sincronizados não podem ser usados para gerar aLamport timestamps.

Lamport Clocks and Timestamps (2/3)

As Lamport timestamps são geradas em cada processo, pi pelo Lamport clock local, Li . A actualização de Li é feita de acordo com as seguintes regras: LC1 Li é incrementado antes de pi executar um evento; LC2 a) Quando um processo pi envia uma mensagem m, anexa-lhe o valor t = Li ; b) Quando um processo pj recebe uma mensagem (m, t),actualiza o seu relógio Lj = max(Lj , t) e depois aplica LC1 antes de atribuir uma timestamp ao evento receive(m).

Lamport Clocks and Timestamps (3/3)
p1 p p
2

a 1 e 1

b 2 m1 c 3 d 4 m2 f 5

3

Pode usar-se pares: (L(e), i) onde i é o identificador do processo para definir uma ordem total entre eventos. Porém, esta ordem é arbitrária. A principal limitação de Lamport timestamps é: L(e)< L(e ) / e → e ⇒

Uso de Lamport Clocks and Timestamps (1/3)
Problema Como garantir ordem total em comunicação multicast? Solução Usar Lamport clocks e usar as Lamport timestamps para ordenar as mensagens. Importante distinguir entre entrega e recepção duma mensagem.
Application layer

Application sends message

Message is delivered to application

Adjust local clock and timestampmessage

Adjust local clock

Middleware layer

Middleware sends message

Message is received

Network layer

Uso de Lamport Clocks and Timestamps (2/3)
Os únicos eventos que interessam são o envio de mensagens:
pi incrementa Li antes de fazer o multicast; pj ajusta Lj quando entrega a mensagem, mas não precisa de a incrementar previamente.

Problemas
E se os emissores pertenceremtambém ao grupo? Como garantir que mensagens enviadas ao mesmo tempo são consideradas por todos os destinatários? E falhas na comunicação?

Uso de Lamport Clocks and Timestamps (3/3)
O processo pj insere cada mensagem recebida numa fila de mensagens ordenadas por ordem crescente das suas timestamps; O processo pj entrega a mensagem mi à aplicação se:
1. mi está à cabeça da fila; 2. tiver...
tracking img