Sincronização de um sistema distribuído

Sincronização de um

Sistema Distribuído

www.trsampaio.com

Tiago R. Sampaio

http://www.trsampaio.com/

Sumário

Motivação

Sincronização de Relógio

Relógios Lógicos

Relógio Físico

Relógios Sincronizados

Sincronização Física de Relógios◦ Algoritmos de Christian’s

◦ Algoritmos de Berkeley

◦ Clock Lógico

◦ Algoritmo de Lamport

◦ Algoritmo de Eleição

◦ Algoritmo “Bully’

◦ Algoritmo do Anel

◦ Exclusão Mútua

◦ Algoritmo Token Ring

Conclusão

Motivação da Sincronização

Necessário pois informações

centralizadas não é desejável

Tão importante quanto a Comunicação

Sincronização é fazer a coisa certa na

hora certa

Para tratar problemas como região

crítica, exclusão mútua

Técnicas convencionais para sistemas de

CPU única não resolvem o problema


Necessário o uso de algoritmos

distribuídos

Algoritmos distribuídos possuem as

seguintes propriedades:

◦ 1− A informação relevante está espalhada em

múltiplas máquinas

◦ 2− Processos tomam decisões baseadas

somente nas informações locais

◦ 3− Um único ponto de falha no sistema deve

ser evitado

◦ 4− Não existe um relógio em comum ou outro

tipo preciso de tempo global


Atingir a sincronização sem

centralização requer fazer coisas de

um modo diferente dos sistemas

operacionais tradicionais.

Nos sistemas centralizados, o tempo

não é ambíguo

Atingir a concordância do tempo não é

trivial


Exemplo: Make do Unix

Objeto no tempo 2144 desatualizado

Editado no tempo 2143

Relógio Lógico

Com um único computador e clock, não

importa se o relógio estiver fora do tempo

Tudo o que realmente importa são os

tempos relativos

Em sistema com n computadores, os

relógios podem ficarem gradualmente

fora de sincronismo

Para muitos propósitos, é suficiente que

todas as máquinas estejam no mesmo

tempo

Relógio Físico

Em alguns sistemas (sistemas de

tempo real), o tempo real é

importante

Relógios físicos externos são

necessários.

Multiplos relógios são desejáveis por:

◦ Eficiência

◦ Redundância

Relógio Físico

Problemas:

(1) Como será feito a sincronização

deles com os relógios do mundo real

(2) Como sincronizar os relógios entre

si

Hoje o tempo medido

astronomicamente. Com relógio

atômico

Relógios Sincronizados

Novos algoritmos que fazem uso da

sincronização

Sincronização física

Para uma aplicação local o que vale é

a sequência em que os eventos

ocorrem

Problemas:

◦ Um relógio não pode voltar atrás

◦ Não se pode determinar com precisão o

delay de transmissão da rede.

Algoritmo de Christian’s

Para sistemas com Servidor de

Tempo

Periodicamente cada máquina envia

uma mensagem para o Servidor de

Tempo perguntando pelo tempo

corrente.

Essa responde o mais rápido

possível o tempo corrente

Algoritmo de Christian’s

Algoritmo de Berkeley

Servidor de Tempo é sempre ativo e

requer, periodicamente de cada

máquina, o tempo do seu relógio

O Sevidor de Tempo calcula a média

dos tempos e diz para cada máquina

como ajustar seu relógio

Algoritmo de Berkeley

(a) O servidor envia sua hora para todas as máquinas (b)

As máquinas retornam o quanto estão adiantadas ou

atrasadas (c) O servidor calcula uma média e retorna o

quanto o horário deve ser adiado ou atrasado

Clock Lógico

Lamport mostra que:

Se dois processos não interagem, não

é necessário que seus clocks sejam

sincronizados

Usualmente, o que importa é que os

processos concordem com a ordem

em que os eventos ocorreram

Clock Lógico

Clock Lógico: Consistencia interna é o

que importa

Clock Físico: Os clocks não podem

divergir de mais que uma certa

quantidade

Algoritmo de Lamport

Relação “acontece antes” ab (a

acontece antes de b)

Todos os processos concordam que

primeiro o evento a ocorreu e depois o b

“acontece antes” é uma relação transitiva:

Se a b e bc então ac

Precisamos medir o tempo onde todo

evento a, assumimos que ele ocorreu em

um tempo C(a) e que todos os processos

concordem.

Se a b, então C(a) < C(b)




Cada mensagem carrega o tempo de

envio, de acordo com o clock do

processo que a enviou

Quando a mensagem chega e o

relógio do receptor mostra um valor

anterior, o receptor avança o seu

relógio para :

◦ o tempo de envio da mensagem mais um

Algoritmo de Eleição

Muitos algoritmos distribuídos requerem um processo como coordenador

Muito utilizado para seleção de coordenador e seleção de superpares em sistemas P2P

Não importa quem seja o coordenador, mas é necessário haver um

Algoritmo Bully (Garcia e Molina1982)◦ Quando um processo nota que o

coordenador não está respondendo a uma requisição, inicia-se uma ELEIÇÃO

Algoritmo Bully

Quando um processo nota que o

coordenador não responde:

1. P envia uma mensagem de Eleição

para os processos maiores que ele

2. Se nenhum responde, P ganha a

eleição

3. Se um processo com o número

maior responde, ele assume a

coordenação

Algoritmo Bully

Quando um processo recebe uma mensagem de eleição de um processo menor, ele envia um OK indicando que vai tomar o comando

Depois ele inicia uma eleição

Eventualmente todos os processos abandonam a disputa, com exceção do novo coordenador

Ele envia uma mensagem a todos avisando que é o novo coordenador

Se um processo que estava “fora do ar” volta, ele inicia uma eleição

Algoritmo Bully

Algoritmo Bully

Algoritmo do Anel

Baseado no uso do anel mas sem o ‘token’

Quando um processo nota que o coordenador não está funcionando ele envia uma mensagem de eleição para o seu sucessor, com o numero do seu processo

A mensagem segue e a cada passo é incluido o numero do processo na lista

Quando a mensagem dá a volta no anel o novo coordenador é determinado

Uma mensagem circula informando quem é o novo coordenador

Algoritmo do Anel

Exclusão Mútua

Assim como em um sistema

centralizado:

Um processo é eleito como coordenador

Quando um processo quer entrar na

região crítica, ele envia uma mensagem

de requisição

Se nenhum outro está na região, o

coordenador permite

Quando a resposta chega, o processo

entra na região

Exclusão Mútua

Supondo que outro processo peça

permissão, o coordenador não envia

resposta a ele, bloqueando a entrada

Quando o processo deixa a região ele

envia uma mensagem ao coordenador

liberando a região

Exclusão Mútua

(a) O processo 1 solicita ao coordenador permissão para acessar o

recurso (b) O processo 2 solicita permissão para acessar o mesmo

recurso, o Coordenador não responde (c) Quando o processo 1 libera

o recurso, informa ao coordenador, que então responde ao 2

Exclusão Mútua - Distribuído

Quando um processo quer entrar na

região crítica ele constrói uma

mensagem com o nome da região, n° do

processo e tempo corrente e envia a

todos

Quando um processo recebe a

requisição de outro:

1. Se o receptor não está na região e não

quer entrar, ele envia OK de volta

2. Se o receptor está na região ele não

responde e coloca a requisição na fila


3. Se o receptor quer entrar mas ainda

não o fez, ele compara os tempos e o

menor vence. Se for menor ele envia

OK.

Após pedir permissão um processo

espera que todos deem permissão

Quando todas chegam, ele entra na

região

Quando ele sai, envia OK para todos os

processos na sua fila


(a) Dois processos querem acessar um recurso compartilhado no

mesmo momento. (b) O processo 0 tem a marca de tempo mais

baixa, portanto vence. (c) Quando o processo 0 conclui, também

envia uma mensagem OK, portanto agora o processo 2 pode

acessar o recurso.

Algoritmo “Token Ring”

É construido um anel lógico por SW

onde cada processo recebe uma

posição

Quando é inicializado, o processo 0

ganha o token

O token circula o anel, e quem o

recebe verifica se quer entrar na

região, se sim, ele entra. Se não,

passa o token

Se nenhum quiser, o token fica


Problemas:

Se o token é perdido ele precisa ser regenerado

A detecção de perca é difícil

Se um processo falha, ocorrem problemas

É necessário confirmar o recebimento do token

O processo que falhou é retirado

Todos os processos precisam conhecer o anel


a) Um grupo de processos não ordenado em uma rede

b) Um anel lógico é construído em software

Conclusão

Necessário conhecer os vários tipos de

algoritmos de sincronização para

aplicação correta no cenário ideal

Existem algoritmos centralizados e

distribuídos, cada um tem suas

desvantagens (falta de segurança vs

falhas de comunicação e processo)

Software

Sincronização de um sistema distribuído