Sincronizao emSistemas Distribudos

Universidade Federal do ABC

Turma:Cincia da Computao

Prof. Dr. Francisco Isidro Massetto

Sincronizaoz Como as regies crticas so implementadas em um

SD?z Como os recursos so alocados aos processos?z Em SO, os problemas de excluso mtua e regio

crtica so solucionados atravs de semforos ou monitores.

z Tais mtodos utilizam memria compartilhada para implementar a soluo, portanto, impossvel de ser feito em um SD.

z Pergunta: como promover a sincronizao em um ambiente distribudo?

Sincronizao atravs do CLOCKz Os Sistemas Distribudos utilizam algoritmos

distribudos na implementao de servios e aplicaes.

z Geralmente no desejvel ter todas as informaes sobre o sistema em um nico lugar.

z Os algoritmos distribudos apresentam as seguintes propriedades:z As informaes relevantes so espalhadas pelas mltiplas

mquinas;z Os processos tomam as decises baseadas somente em

informaes locais;z Um ponto de falha que paralise todo o sistema deve ser

evitado;z No existe relgio comum ou um tempo global.

Clock Lgicoz Em Lamport (1978) - Time, Clocks, and the

Ordering of Events in a Distributed System provada que a sincronizao dos relgios possvel e apresenta o algoritmo para se conseguir isto.

z Posteriormente, em outro artigo ele defende que a sincronizao dos clocks no precisa ser absoluta, pelos seguintes motivos:z Se dois processos no interagem, no necessrio que

seus clocks sejam sincronizados.z Usualmente o que importa no que todos os processos

concordem com o exato tempo em que os eventos aconteceram, mas que concordem na ordem em que os eventos ocorreram.

Clock Lgico

z Clock Lgico - consistncia interna o que importa e no quanto eles esto prximos do tempo real.

z Clock Fsico - os clocks no podem diferir do tempo real mais que um determinado valor.

Clock Lgico Algoritmo de Lamportz Lamport definiu a seguinte relao: acontece-antes:

a b (a acontece antes de b)z Significa que todos os processos concordam que

primeiro o evento a ocorreu e depois disto, o evento bocorreu. Esta relao pode ser observada em duas situaes:z Se a e b so eventos no mesmo processo, e a ocorre antes

de b, ento ab verdadeiro.z Se a o evento de uma mensagem sendo enviada por um

processo, e b o evento da mensagem sendo recebida por outro processo, ento ab tambm verdadeiro.

Algoritmo de Lamportz A relao acontece-antes transitiva, logo:

se ab e bc, ento acz Se dois eventos x e y, acontecem em

diferentes processos que no trocam mensagens, ento xy no verdadeiro, nem yx verdadeiro.

z Estes eventos so ditos concorrentes, o que significa que nada pode ser dito sobre quando eles aconteceram.

Algoritmo de Lamport

z necessrio um modo de medio de tal forma que para todo evento a, possa ser assumido que ele ocorreu em um tempo C(a) no qual todos os processos concordem.

Se ab, ento C(a) < C(b).

Algoritmo de Lamport

z O que acontece de estranho entre as trocas de mensagens?

Algoritmo de Lamport

Algoritmo pra Sincronizao de CLOCK Algoritmo de Berkeley

z Nenhuma mquina tem um receptor de Tempo Universal Coordenado.

z O Servidor de Tempo ativo, e requer, periodicamente de cada mquina, o tempo do seu relgio.

z O Servidor de Tempo calcula a mdia dos tempos (considerando o tempo dele mesmo) e diz para cada mquina como ajustar seu relgio para ter seu tempo igual mdia calculada.

Algoritmo de Berkeley

Excluso Mtua AlgoritmoCentralizadoz A melhor maneira de se conseguir excluso mtua

em um sistema distribudo imitar o que feito no sistema centralizado (com um nico processador).

z Um processo eleito como Coordenador. Quando um processo quer entrar na regio crtica, ele envia uma mensagem requisitando ao Coordenador permisso para isso.

z Se nenhum outro processo est na regio crtica, o Coordenador envia uma resposta dando permisso.

Algoritmo Centralizadoz Ao receber a mensagem o processo requisitante

entra na regio crtica.z Caso outro processo pea permisso para entrar na

regio crtica, e o Coordenador sabendo que outro processo est na regio, no envia resposta bloqueando este processo at que ele possa entrar na regio.

z Uma outra opo enviar uma mensagem negando a solicitao.

z Quando o processo deixa a regio, ele envia para o Coordenador uma mensagem liberando a regio crtica.

Algoritmo Centralizado

Excluso Mtua AlgoritmoDistribudoz O Algoritmo centralizado tem o problema de uma

falha no Coordenador inviabilizar o mecanismo (todo elemento centralizador um ponto crtico de falhas).

z Algoritmo distribudo - Quando um processo quer entrar na regio crtica, ele constri uma mensagem contendo o nome da regio, nmero do processo e o tempo corrente.

z A mensagem enviada para todos os outros processos. Quando um processo recebe uma mensagem de requisio de outro processo sua ao vai depender de sua situao relativa regio crtica

Algoritmo Distribudo

z Possibilidades:z Se o receptor no est na regio crtica e no

quer entrar, ele envia de volta uma msg OK;z Se o receptor j est na regio, ele no

responde e coloca a requisio na fila;z Se o receptor quer entrar na regio crtica, mas

ainda no o fez, ele compara o tempo da msgque chegou com o tempo da msg que ele enviou para os outros processos. O menor tempo vence.

Algoritmo Distribudoz Quando todas as permisses chegam o processo pode

entrar na regio crtica. Quando ele sai da regio crtica, ele envia uma msg OK para todos os processos na sua fila.

z Qual o problema deste algoritmo??

Excluso Mtua AlgoritmoToken Ringz construdo um anel lgico por software no qual a cada

processo atribudo uma posio no anel.z Quando o anel inicializado, o processo 0 ganha o token. O

token circula no anel (passa do processo k para o k+1). Quando o processo ganha o token ele verifica se ele quer entrar na regio crtica. Caso positivo, ele entra na regio, realiza o seu trabalho e ao deixar a regio passa o token para o elemento seguinte do anel.

z No permitido entrar em uma segunda regio crtica com o mesmo token.

z Se o processo no quer entrar na regio crtica ele simplesmente passa o token. Como conseqncia quando nenhum processo quer entrar na regio crtica o token fica circulando pelo anel.

Algoritmo Token Ring

0 2 4 9 7 1 6 5 8 3

Processos

12

3

4

5

67

8

9

0

Tokenn

Algoritmo Token Ring

z Problemas:z Se o token perdido ele precisa ser regenerado.

A deteco de um token perdido difcil.z Se um processo falhar tambm ocorrem

problemas. A soluo fazer o processo que recebe o token confirmar o recebimento. O processo que falhou pode ser retirado do anel, e o token enviado para o processo seguinte. Essa soluo requer que todos os processos conheam a configurao do anel.

Comparao dos Algoritmos

Perda do Token0 a n-11 a infinitoToken Ring

Falha de QualquerProcesso

2.(n-1)2.(n-1)Distribudo

Falha do Coordenador

23Centralizado

ProblemasAtrasosMensagensAlgoritmo

Eleio do Coordenador

z Muitos algoritmos distribudos requerem um processo como coordenador.

z Geralmente no importa qual seja o processo coordenador, mas um deles tem que exercer esta funo.

Algoritmo do Ditadorz Quando um processo nota que o coordenador no

est respondendo a uma requisio, ele inicia uma eleio. A eleio convocada por um processo P da seguinte forma:z P envia uma mensagem de ELEIO para todos os

processos com nmeros maiores que o seu;z Se nenhum responde, P ganha a eleio e se torna

coordenador;z Se um processo com nmero maior responder, ele

assume a coordenao.

Algoritmo do Ditadorz Quando um processo recebe uma mensagem de

ELEIO de um processo de menor nmero, ele envia uma mensagem OK de volta indicando que ele vai tomar o comando. Depois disso ele inicia uma eleio.

z Eventualmente todos os processos abandonam a disputa, com exceo de um que o novo coordenador.

z Ele envia uma mensagem a todos os processos avisando que o novo coordenador.

z Se um processo que estava fora do ar volta, ele inicia uma eleio. Caso ele seja o processo ativo de nmero mais alto rodando no sistema, ele ganha a eleio e assume a coordenao.