SD 09 - Coordenação e Acordo

Prévia do material em texto

Sistemas Distribuídos
Coordenação e Acordo
Joinvile Batista Junior
UFGD - SD 09 - Joinvile Batista Junior 2
Coordenação e Acordo
 A : Algoritmos de Exclusão Mútua Distribuída
 B : Algoritmos de Eleições
 C : Algoritmos Multicast
 D : Algoritmos de Consenso
UFGD - SD 09 - Joinvile Batista Junior 3
A : Algoritmos de Exclusão Mútua Distribuída
1. Conceitue Coordenação e Acordo. Conceitue Exclusão Mútua 
Distribuída.
2. Comente as condições e os critérios de avaliação de um algoritmo de 
exclusão mútua.
3. Defina Algoritmo de Exclusão Mútua Distribuída: Servidor Central.
4. Defina Algoritmo de Exclusão Mútua Distribuída baseado em Anel.
5. Defina Algoritmo de Exclusão Mútua Distribuída usando Multicast e 
Relógio Lógico.
6. Defina Algoritmo de Exclusão Mútua Distribuída: Votação de 
Maekawa.
UFGD - SD 09 - Joinvile Batista Junior 4
Coordenação e Acordo
• Coordenação e Acordo
– um dos problemas fundamentais em sistemas distribuídos
• coordenação e acordo entre os diversos processos sobre a 
utilização dos recursos
– para solucionar esta questão existem vários algoritmos
• mas a solução de hierarquia dos processos é sempre evitada
• Suposições de Falhas
– cada par de processos está conectado por canais confiáveis
– os processos usam um protocolo de comunicação confiável que 
mascara as falhas
– nenhum dos processos depende do outro para encaminhar 
mensagens
– entrega das mensagens dentro de um limite de tempo especificado
– para todos os efeitos: os processos e as mensagens nunca falham 
• a não ser que seja especificado o contrário
UFGD - SD 09 - Joinvile Batista Junior 5
Coordenação e Acordo
• Detector de Falha
– é um serviço que os processos consultam
• para saber se um processo em particular falhou
– é implementado em um objeto local
• para cada processo que executa um algoritmo de falha
• Confiabilidade
– um detector de falha não é exatamente preciso
• a maioria são detectores de falha não confiáveis
– eles identificam cada processo como suspeito ou não 
suspeito
• os detectores não confiáveis com certas propriedades bem 
definidas
– podem auxiliar no encontro de soluções para os problemas 
de coordenação de processos quando existem falhas
» mesmo que de forma imprecisa
UFGD - SD 09 - Joinvile Batista Junior 6
Exclusão Mútua Distribuída
• Conceituação
– os processos distribuídos precisam coordenar suas atividades
– se um conjunto de processos partilham um recurso
• freqüentemente é necessário a exclusão mútua para acessar o 
recurso
– em sistemas operacionais
• o problema é conhecido como seção crítica
– a solução para sistemas distribuídos
• exige obrigatoriamente a troca de mensagens
UFGD - SD 09 - Joinvile Batista Junior 7
Exclusão Mútua Distribuída
• Exemplo
– um estacionamento de veículos com diversas entradas e saídas
• tenta manter o controle da quantidade de vagas disponíveis no 
estacionamento
– sem a necessidade de um servidor central
– mantém um contador local do número de vagas
• toda saída: registra a adição de uma vaga
• toda entrada: registra a subtração de uma vaga
UFGD - SD 09 - Joinvile Batista Junior 8
Algoritmo de Exclusão Mútua
• operações
– enter: entrar na seção critica
– resourceAccesses: utilizar o recurso
– exit: sair da seção critica
• condições
– segurança
• apenas um processo entra na seção critica por vez
– subsistência
• os pedidos para entrar e sair no sistema nunca falham
– ordenação
• a ordem dos pedidos garante a ordem de entrada
UFGD - SD 09 - Joinvile Batista Junior 9
Algoritmo de Exclusão Mútua
• critérios de avaliação
– largura de banda consumida
• proporcional ao número de mensagens enviadas em cada 
operação de entrada e saída
– atraso do cliente
• acarretado por um processo em cada operação de entrada e 
saída
– efeito do algoritmo sobre a taxa de rendimento do sistema
• velocidade com que o conjunto de processos como um todo 
pode acessar a seção crítica
UFGD - SD 09 - Joinvile Batista Junior 10
Algoritmo do Servidor Central
• utilizar um servidor para conceder permissão para entrar na seção crítica
– é o modo mais simples de exclusão mútua
• algoritmo em alto nível
– o servidor retorna um token
• dando permissão para um processo entrar na seção crítica
– se nenhum processo tiver o token
• o servidor responderá emitindo um
– se o token estiver com algum processo
• o servidor não responderá e enfileirará o pedido
• o processo mais antigo em espera
– entra na seção crítica primeiro
– quando um processo sai da seção crítica
• uma mensagem é enviada para o servidor
UFGD - SD 09 - Joinvile Batista Junior 11
Algoritmo do Servidor Central
UFGD - SD 09 - Joinvile Batista Junior 12
Algoritmo Baseado em Anel
• algoritmo
– cada processo P tem um canal de comunicação
• com o processo seguinte no anel
– a exclusão é concedida pela obtenção de um token
• na forma de mensagem passada de processo para processo
• em uma única direção em torno do anel
– se um processo não pede para entrar na seção crítica
• ao receber o token: ele o encaminha para seu vizinho
– um processo que solicita o token: espera até recebê-lo
– para sair da seção crítica: processo envia o token para seu vizinho 
• avaliação
– algoritmo consome largura de banda continuamente
UFGD - SD 09 - Joinvile Batista Junior 13
Algoritmo usando Multicast e Relógio Lógico
• processos solicitam a entrada em uma seção crítica
– difundindo seletivamente (multicast) uma mensagem de pedido
• processos só podem entrar na região crítica
– quando todos os processos tiverem respondido essa mensagem
• as condições de resposta são projetadas para satisfazer as condições 
de segurança e ordenação
• os processos apresentam identificadores númericos distintos
• canais de comunicação de um processo para o outro
– mantém um relógio de Lamport atualizado
• cada processo registra seu estado em uma variável
– fora da seção crítica
– querendo entrar
– na seção crítica
UFGD - SD 09 - Joinvile Batista Junior 14
Algoritmo usando Multicast e Relógio Lógico
• se dois processos solicitarem a entrada ao mesmo tempo
– o pedido do processo que apresentar a indicação de tempo mais 
baixa
• será o primeiro a coletar n - 1 respostas e garantir sua entrada
• se apresentarem tempo igual
– serão ordenados de acordo com o índice dos processos
• vantagem desse algoritmo
– atraso de sincronização é o tempo de transmissão de uma 
mensagem
• mensagem de resposta dos processos consultados
– pois a mensagem de solicitação é única (multicast)
– os dois algoritmos anteriores
• apresentavam atraso de viagem de ida e volta
UFGD - SD 09 - Joinvile Batista Junior 15
Algoritmo de Votação de Maekawa
• baseado em votação
– para o obter acesso à seção crítica
• nem todos os processos precisam concordar
– é necessário apenas
• dividir o conjunto de processos em subconjuntos
– conjuntos de votação que se sobrepõem
• que haja consenso em todo subconjunto
• para entrar na seção crítica
– o processo deve obter a quantidade de votos do subconjunto - 1
• na saída da seção crítica
– processo envia uma mensagem de liberação
• para todos os membros do conjunto votante
UFGD - SD 09 - Joinvile Batista Junior 16
Tolerância a Falhas dos Algoritmos
• nenhum dos algoritmos descritos toleraria a perda de mensagens
– o algoritmo do servidor central
• pode tolerar a falha por colapso
– de um processo que nem tenha solicitado o token
– o algoritmo baseado em anel
• não toleraria nem mesmo uma falha por colapso de um único 
processo
– o algoritmo usando multicast e relógios lógicos
• pode ser adaptado para tolerar falha por colapso
– oalgoritmo Maekawa
• pode tolerar falha por colapso
– desde que o processo não esteja em um conjunto votante
UFGD - SD 09 - Joinvile Batista Junior 17
B : Algoritmos de Eleições
1. Defina o objetivo de uma eleição e seus requisitos de execução.
2. Explique o Algoritmo de Eleições baseado em Anel.
3. Qual o desempenho de pior caso do Algoritmo de Eleições baseado 
em Anel. Justique.
4. Explique o Algoritmo de Eleições Valentão.
5. Qual o melhor e o pior caso de desempenho do Algoritmo de Eleições 
Valentão. Justique.
UFGD - SD 09 - Joinvile Batista Junior 18
Eleições
• é um algoritmo para escolher um único processo
– para desempenhar uma função em particular
• cada processo tem um identificador
– que pode ser qualquer valor
• desde que sejam únicos e ordenados
• em uma eleição: cada processo pode ser participante ou não 
participante
– caso um processo seja participante
• ele altera seu “eleito” para “┴” (vazio)
– após a eleição de um processo
• todos os outros participantes armazenam o indicador do 
processo eleito
UFGD - SD 09 - Joinvile Batista Junior 19
Eleições
• requisitos de execução de algoritmos de eleição
– segurança
• um processo participante Pi tem “eleito” = ┴ ou “eleito” = Pj
• Pj é escolhido como o processo não falho com maior 
identificador
– subsistência
• todos processos Pi participam e configuram “eleito” ≠ ┴ ou 
falham
• a medição de desempenho de algoritmos de eleição
– é feita a partir a utilização de banda da rede total
– e pelo tempo do ciclo de rotação do algoritmo
UFGD - SD 09 - Joinvile Batista Junior 20
Algoritmo Baseado em Anel
• cada processo Pi
– tem um canal de comunicação com o processo Pi+1 
• e todas mensagens são enviadas em sentido horário
• o objetivo deste algoritmo é eleger um único processo
– chamado de processo coordenador
• inicialmente todos processos estão como não participantes
– e qualquer processo pode iniciar a eleição
• o processo iniciante marca-se como participante
– e envia seu identificador em uma mensagem ao seu vizinho
• sempre no sentido horário
• ao receber uma mensagem de eleição
– o processo compara o seu identificador com o contido na 
mensagem
UFGD - SD 09 - Joinvile Batista Junior 21
Algoritmo Baseado em Anel
• caso o identificador contido na mensagem seja maior que o seu próprio
– ele encaminha a mensagem ao vizinho
• caso o identificador contido na mensagem seja menor
– ele substitui o identificador da mensagem pelo seu e encaminha
• em qualquer caso, no recebimento de uma mensagem de eleição
– o processo marca a si mesmo como participante
• no entanto, se o identificador recebido for igual ao seu
– então o processo é o maior e torna-se o coordenador
• o coordenador marca-se como não participante
– e encaminha ao seu vizinho uma mensagem “eleito”
• anunciando sua eleição junto com seu identificador
• todos processos então marcam-se como não participantes
– e ajustam seu “eleito” para o coordenador
UFGD - SD 09 - Joinvile Batista Junior 22
Algoritmo Baseado em Anel
• pior caso de desempenho: quando vizinho do processo iniciante, no 
sentido anti-horário tem o identificador mais alto
– para chegar a este vizinho: N – 1 mensagens
– o qual não anunciará sua eleição até que seu identificador tenha 
completado outro ciclo: + N mensagens
– mais um ciclo para enviar a mensagem “eleito”: + N mensagens
• portanto, para N participantes: gasto = 3N - 1
• embora o algoritmo baseado em anel seja útil para se entender as 
propriedades dos algoritmos de eleição em geral
– o fato de ele não tolerar falhas o torna limitado quanto ao seu valor 
prático
• falha de um processo interrompe o ciclo de mensagens no anel
• porém, com um detector de falhas confiável
– é possível, em princípio, reconstruir o anel após uma falha
UFGD - SD 09 - Joinvile Batista Junior 23
Algoritmo Baseado em Anel
UFGD - SD 09 - Joinvile Batista Junior 24
Algoritmo Valentão (Bully)
• ao contrário do algoritmo baseado em Anel este algoritmo presume 
– que o sistema seja síncrono
• ele usa limites de tempo para detectar uma falha
– que cada processo sabe quais processos têm identificadores mais 
altos
• e que todos processos podem se comunicar
• existem três tipos de mensagens nestes algoritmos
– uma mensagem de eleição
• é enviada para anunciar uma eleição
– uma mensagem de resposta
• é enviada em retorno à mensagem de eleição
– uma mensagem de coordenador
• é enviada para anunciar a identidade do processo eleito
• uma nova eleição é solicitada quando o antigo coordenador falha
UFGD - SD 09 - Joinvile Batista Junior 25
Algoritmo Valentão
• por se tratar de um algoritmo síncrono
– podem ser construídos detectores de falhas confiáveis
• como os processos conhecem o maior identificador
– este pode se eleger como coordenador simplesmente enviando 
uma mensagem de coordenador
• um processo de identificador baixo pode enviar mensagem de eleição
– e caso não haja resposta em tempo T: torna-se o coordenador
• ao receber uma mensagem do coordenador
– o processo ajusta seu “eleito” para o novo processo
• é impossível dois processos decidirem que são o coordenador
– pois o processo com identificador mais baixo descobrirá que o outro 
existe e o acatará
UFGD - SD 09 - Joinvile Batista Junior 26
Algoritmo Valentão
• em relação ao desempenho
– no melhor caso: o processo com o segundo identificador mais alto
nota primeiro a falha do coordenador
• ele pode eleger-se simplesmente enviando N mensagens de 
coordenador
– no pior caso: o processo com o menor identificador nota primeiro a 
falha do coordenador
• neste caso, N – 1 processos iniciam as eleições enviando 
mensagens para os processos com identificadores mais altos
– O(N²) mensagens são necessárias
UFGD - SD 09 - Joinvile Batista Junior 27
C : Algoritmos Multicast
1. Conceitue eficiência na comunicação multicast.
2. Conceitue as propriedades do multicast confiável.
3. Conceitue ordem FIFO, causal e total no multicast ordenado.
UFGD - SD 09 - Joinvile Batista Junior 28
Comunicação Multicast
• toda mensagem de multicast exige coordenação e acordo
– objetivo: todos os processos de um grupo devem receber cópias 
das mensagens enviadas
• os processos podem pertencer a vários grupos
– recebendo informações de várias fontes
• o modelo de sistema consiste em um conjunto de processos
– que podem se comunicar com confiabilidade por meio de canais
• processos só falham por colapso
• um processo ao receber uma mensagem
– pode distribuí-la ou apenas recebê-la
• a mensagem transporta um identificador do seu emissor
UFGD - SD 09 - Joinvile Batista Junior 29
Comunicação Multicast
• eficiência
– a mesma mensagem será enviada a todos os processos de um 
grupo
• permitindo que a implementação seja eficiente em sua largura 
de banda
– se compararmos o envio de mensagem entre um PC de Londres 
para 2 computadores em Palo Alto
• por UDP: necessita envio de 2 mensagens
– o envio da segunda mensagem requer a conclusão da 
primeira
» retardando o processo
• por multicast
– um conjunto de roteadores com capacidade de multicast 
encaminha uma única cópia da mensagem
UFGD - SD 09 - Joinvile Batista Junior 30
Comunicação Multicast
• garantias de entrega
– em múltiplos envios independentes para vários remetentes
• não há como garantir a entrega que afetem o grupo como um 
todo
– pois um remetente pode falhar na metade do processo de 
envio
• nem como garantir a ordem de entrega
– em multicast
• também não há uma garantia de ordem de recebimento
– porém há métodos de garantias que podem ser 
implementados
UFGD - SD 09 - Joinvile Batista Junior 31
Multicast Básico
• garante que umprocesso correto finalmente distribuirá a mensagem: 
desde que o difusor não falhe
• uma maneira simples de implementar B-multicast 
– usando uma operação send confiável de um para um
• a implementação pode usar threads para executar as operações de 
send: diminuindo o tempo gasto
• porém a utilização de threads pode causar uma explosão de 
confirmações
– caso o número e processo seja grande
• recebendo assim várias confirmações de recebimentos quase 
ao mesmo tempo
• este recebimento simultâneo causa exaustão dos buffers dos 
processos
– podendo levar à perda de confirmações de entrega dos processos
• que resulta em reenvio de mensagens
– acarretando cada vez mais confirmação de recebimento
UFGD - SD 09 - Joinvile Batista Junior 32
Multicast Confiável
• o multicast confiável deve satisfazer as seguintes propriedades
– integridade
• um processo correto p entrega uma mensagem m no máximo 
uma vez
– validade
• se um processo correto executa um multicast da mensagem m
– então: ele finalmente entregará m
– acordo
• se um processo correto entrega a mensagem m
– então todos os outros processos corretos do grupo
» finalmente entregarão m
UFGD - SD 09 - Joinvile Batista Junior 33
Multicast Ordenado
• problema no multicast básico: falta de garantia de ordem
– que não é satisfatória para muitas aplicações
• requisitos de ordenação comum
– ordem: FIFO, causal, total
• ordem FIFO
– se um processo correto executa multicast (g,m) e depois multicast 
(g,m’)
• todo processo correto que entregar m’ entregará m antes de m’
– a camada de comunicação é forçada a entregar as mensagens que 
chegam do mesmo processo
• na mesma ordem em que elas foram enviadas
UFGD - SD 09 - Joinvile Batista Junior 34
Multicast Ordenado
• Ordem Causal
– se multicast (g,m) → multicast (g,m’)
• onde → é a relação do acontecido induzida apenas pelas 
mensagens enviadas entre os membros de g
• então todo processo correto que entrega m’ entregará m antes m’
– se m precede uma outra mensagem m’ por causalidade
• independentemente de terem sido enviadas por processos 
diferentes
• a camada de aplicação sempre entregara m’
– apos ter recebido e entregado m
– ordem causal implica ordem FIFO
• Ordem Total
– se um processo correto entregar a mensagem m antes de entregar m’
• qualquer outro processo correto que entregue m’
– entregará m antes de m’
– permite que a distribuição de mensagens seja ordenada 
arbitrariamente
• desde que a ordem seja a mesma em diferentes processos
UFGD - SD 09 - Joinvile Batista Junior 35
D : Algoritmos de Consenso
1. Defina o problema de Consenso e os requisitos de um algoritmo de
Consenso.
2. Explique porque não há consenso para o problema dos 3 generais 
bizantinos.
3. Explique porque há consenso para o problema dos 4 generais 
bizantinos.
UFGD - SD 09 - Joinvile Batista Junior 36
Consenso
• Consenso X Generais
– em que o problema dos generais bizantinos difere do consenso?
• problema dos generais bizantinos
– um processo distinto pode fornecer um valor com o qual os 
outros devem concordar
• problema do consenso
– cada um dos processos propõem um valor
– integridade do problema dos generais
• depende do valor proposto pelo comandante
UFGD - SD 09 - Joinvile Batista Junior 37
Consenso
• problema: processos concordarem com um valor
– após um, ou mais, processos terem proposto qual deve ser esse 
valor
– ex: todos os computadores corretos de uma nave espacial devem 
decidir entre prosseguir ou cancelar
• definindo consenso relacionando-o com outro problema de acordo
– Generais Bizantinos
• definição do problema de consenso
– sejam 3 processos: P1, P2 e P3
• cada processo começa no estado “indeciso”
• cada processo propõe um único valor vi
– extraído de um conjunto D(i=1,2,...,N)
• os processos se comunicam podendo trocar seus valores
• cada processo entra no estado “decidido”
– configurando um valor de uma variável de decisão di
UFGD - SD 09 - Joinvile Batista Junior 38
Consenso
Requisitos de um algoritmo de consenso
• Término
– cada processo correto acaba configurando sua variável de decisão
• Acordo
– o valor da decisão de todos os processos corretos é o mesmo
• Integridade
– se todos os processos corretos propuseram o mesmo valor
• qualquer processo correto no estado decidido escolheu esse 
valor
UFGD - SD 09 - Joinvile Batista Junior 39
Consenso
• Problema dos generais bizantinos
– três ou mais generais devem concordar com: ataque ou retirada
– comandante dá a ordem
• os comandados decidem: atacar ou recuar
– um, ou mais, pode ser traidor (processo falho)
• se o traidor for o comandante
– ele pode propor ordens contraditórias para seus 
comandados
• se o traidor for um comandado
– ele repassa a ordem incorreta para os outros comandados
– todos os generais devem tomar a mesma ação
• o exército não pode tomar decisões distintas mesmo que haja 
generais traidores
• a decisão precisa ser consenso: não pode ser aleatória
UFGD - SD 09 - Joinvile Batista Junior 40
Sem consenso para 3 generais bizantinos
Comandado (p3) traidor Comandante (p1) traidor
p1 (Comandante)
p2 p3
AA
A
R
p1 (Comandante)
p2 p3
RA
A
R
UFGD - SD 09 - Joinvile Batista Junior 41
Consenso para 4 generais bizantinos
Comandado (p3) traidor Comandante (p1) traidor
X = { A | R }
p1 (Comandante)
p2 p3
AA
A
R
p4
A
A
A R
A
p1 (Comandante)
p2 p3
XA
A
X
p4
R
R
A X
R