Serviço de tempo,
Exclusão Mútua,
Eleição e Acordo
Prof. Dr. Norian Marranghello
Grupo 5
Anuar Mamede Neto
Eduardo Hitoshi Aoki
Tópicos Abordados
Serviço de Tempo
Exclusão Mútua distribuída
- Exclusão mútua por passagem de ficha
- Exclusão mútua por disputa
- Exclusão mútua controlada
- Votação
- Estrutura lógica fixa
- Compressão de caminho
Eleição
- eleição do líder
- topologias
- algoritmo de Bully
- algoritmo do convite
Acordo
- adversários
- acordo bizantino
- impossibilidade de consenso
- acordo distribuído aleatório
Serviço de Tempo
• Clock lógico
• Clock físico
• Lamport propôs a sincronização dos clocks lógicos baseado na
relação acontecimento/anterioridade (ab):
a = mke  {mie}
P
b = mkr  {mjr}
a,b  P  a < b  ab
Sincronização do clock lógico
0
1
2
0
1
2
A
B
C
D
C
D
Exclusão Mútua
Exclusão Mútua por passagem de ficha ou Token Ring
•
Todo processo sabe quem é o próximo da seqüência
•
O detentor do token pode entrar na R.C. ou passar o token
•
Problemas:
- perda do token



- algum processo pára


Exclusão Mútua
Exclusão Mútua por disputa
•
Necessidade de ordenação total de todos os eventos no sistema
•
A mensagem de requisição contém:
- nome da R.C.
- número processo
- tempo corrente
•
Quando um processo recebe uma requisição de outro processo, a
ação que esse processo toma depende do seu estado com relação a
R.C. nomeada na mensagem:
- executando uma R.C.
- não executando e não quer uma R.C.
- não executando mas ainda vai executar uma R.C.
Exclusão Mútua
Exclusão mútua por disputa
•Se dois processos quiserem entrar na R.C. ao mesmo tempo:
8
A
8
A
12
OK
8
B
C
12
(1)
12
B
A
OK
OK
OK
(2)
C
B
C
(3)
Exclusão Mútua
Votação
(1)
(2)
A
A
OK
8
B
B
C
(3)
C
(4)
A
A
msg
desistência
B
5
C
B
C
Exclusão Mútua
Votação
• Se A não estiver executando a R.C. :
A
A
Msg de conf.
desistência
B
•
B
C
Muda de
C
voto
Se A estiver executando a R.C., ele espera até A terminar de usar o
recurso:
Terminei o uso
do recurso
B
A
A
C
B
OK
C
Exclusão Mútua Controlada
Objetivo:
Evitar sobrecarga de mensagens
Utiliza uma das estruturas topológicas:
• Estrutura em Anel
• Estrutura em Árvore
Estrutura em Anel
•
Processos em um anel lógico
•
Simples
•
Sem Bloqueios
•
Justa
Desvantagens:
•
Demora no recebimento do recurso
-Anel muito grande
-Todos processos querendo usar o recurso
Tenta-se correção:
Mensagem de controle com “status”:
-Níveis de prioridade
-Marcação de tempo
Estrutura em Árvore
Processos em um árvore dinâmica lógica
• Ponteiro para nó antecessor
• Fila FIFO de requisições de recurso
Raiz com mensagem de controle
Compressão de Caminho
• Diminui passagens de requisição;
• Aponta para processo que requisitou;
• Mapa dos outros que também requisitaram;
• Atualiza apontador após passagem de recurso.
Demonstração da
Compressão de Caminho
Antes
Depois
Processo que contem
mensagem de controle
E
E
D
D
Requisição de “A” marcada
C
B
C
B
A
A
Requisição de recurso
Eleição
•
Escolha de um coordenador entre um grupo de processos
•
Topologia Completa
- contato direto entre cada um dos nós de um grupo
- n.º de identificação de um processo é único e conhecido por todos
- comunicação na rede é confiável
Eleição
•
Topologia em anel
- processos ordenados e todos sabem que é o seu respectivo sucessor
Não
responde
0
3
4
5
5
1
3
4
4
3
3
3
4
5
1
2
2
5 é o novo coordenador
3
4
5
1
Eleição
• Topologia em árvore
A
B
E
Coordenador
D
C
F
G
J
I
H
M
N
O
L
Eleição
•
Algoritmo de Bully
- Cada processo tem a sua identidade como sua prioridade.
- Maior prioridade = coordenador
- Quando processo nota falta de um coordenador, convoca eleições
aos processos com prioridade maiores que o seu.
0
5
1
O coordenador
anterior está
fora do ar 5
0
1
eleição
4
eleição
3
OK
2
eleição
4
OK
3
2
Eleição
•
Algoritmo de Bully (continuação)
(1)
(2)
0
5
eleição
0
1
5
2
4
1
eleição
4
eleição
3
3
(3)
0
5
4
2
OK
coordenador 1
coordenador
2
coordenador
coordenador
3
Eleição
Algoritmo do Convite:
- Assíncrono;
- Melhor quando existem pequenas falhas de contagem de tempo;
- Um processo “A” convida os outros se processo líder não responde;
- Os outros processos aceitam este convite em até um determinado tempo;
- Processo “A” envia sinal de pronto aos outros processos;
- Processo “A” é agora o novo coordenador.
Acordo
•
Objetivo:
- Obter consenso de informações entre processos
•
Adversário
•
Falhas Bizantinas
•
Impossibilidade de Consenso
•
Consenso Distribuído Aleatório
Adversários
- Cria situações inesperadas pelo protocolo;
- Destrói mensagens;
- Modifica mensagens;
- Seu poder é controlável;
- Não criar situações impossíveis ou irreais.
Falhas Bizantinas
Resolve problemas de “acordo”
- sistema síncrono;
- processos devem concordar pelo menos 75%;
- possibilidade de perda de mensagem ou seu corrompimento;
- não muito eficiente;
- nem útil em processadores com mal funcionamento;
- existe muita pesquisa para torna-lo eficiente;
Impossibilidade de
Consenso
- Sistema distribuído assíncrono;
- Sem tempo definido para receber respostas;
- Não existem algoritmos que garantem o consenso;
- Sistemas são muito desenvolvidos e utilizados;
- Sistemas reais não garantem 100% de funcionamento;
- Admitem falhas em casos raros;
- Detecção e correção de problemas é feita pelo homem.
Consenso
Distribuído Aleatório
 Busca do consenso sem determinismo;
 Aguardam, pelas respostas, um número de passos;
 Utiliza conceito de memória compartilhada;
 O consenso é consagrado se:
- vetor de preferências, em qualquer momento, tiver valores iguais;
Problemas
 Admite sistema síncrono:
- associa ciclos dos processadores;
- quando ciclos iguais e preferências iguais, temos o consenso;
 Algum processador falhar:
- não atualiza seu número de ciclos;
- inviabiliza acordo;
Tentativa de correção:
- concentram-se esforços nos processadores mais rápidos;
- apenas estes podem discordar;
- processadores mais lentos sempre concordam;