Sistemas Distribuídos
Sincronização
e
Coordenação
Instituto de Informática – UFG
Verão 2005
Baseado em: Tanenbaum, cap. 5
Sincronização de Relógios
Quando cada máquina tem seu próprio relógio, um
evento que ocorreu depois de outro pode, não
obstante, ser associado a um tempo anterior.
Relógios Físicos (1)
Computação do dia solar médio.
Relógios Físicos (2)
Segundos TAI são de duração constante,
diferentemente de segundos solares. Segundos
“bissextos” são introduzidos quando necessário
para manter em fase com o sol.
Algoritmos de Sincronização de Relógios
A relação entre tempo de relógio e o tempo UTC quando os relógios “ticam” com taxas
diferentes.
Algoritmo de Cristian's
Obtendo o tempo atual a partir de um servidor de tempo.
O Algoritmo de Berkeley
a)
b)
c)
O daemon de tempo pergunta a todas as máquinas os valores de seus
relógios locais
As máquinas respondem
O daemon de tempo instrui todas as máquinas a atualizarem seus relógios
Marcas de Tempo de Lamport
a)
b)
Três processos, cada um com seu próprio relógio. Os relógios
“correm” a taxas diferentes.
O algoritmo de Lamport corrige os relógios (relógios lógicos).
Exemplo: Multicast Totalmente Ordenado
Atualização de um banco de dados replicado deixando-o em
um estado inconsistente.
Estado Global (1)
a) Um corte consistente
b) Um corte inconsistente
Estado Global (2)
a) Organização de um processo e canais para um
“instantâneo” distribuído
Estado Global (3)
b)
c)
d)
Processo Q recebe um marcador pela primeira vez e registra seu
estado local
Q registra todas as mensagens que chegam
Q recebe um marcador para seu canal entrante e pára de registrar o
estado do canal entrante
Eleição de Líder:
O Algoritmo de “Bullying” (1)
O algoritmo de eleição de bullying
•
Processo 4 inicia a eleição (após detectar a falha do antigo líder)
•
Processos 5 e 6 respondem, dizendo ao processo 4 para parar
•
Agora os processos 5 e 6 cada um iniciam suas eleições
Eleição de Líder:
O Algoritmo de “Bullying” (2)
d)
e)
Processo 6 diz ao processo 5 para parar
Processo 6 vence a eleição e avisa a todos os demais
O Algoritmo do Anel
Eleição utilizando um anel lógico de processos.
Exclusão Mútua:
Um Algoritmo Centralizado
a)
b)
c)
Processo 1 pede permissão ao coordenador para entrar em uma região
crítica. A permissão é concedida.
Processo 2 então pede permissão para entrar na mesma região crítica.
O coordenador não responde.
Quando o processo 1 sai da região crítica, ele informa ao coordenador,
que então responde ao processo 2.
Exclusão Mútua:
Um Algoritmo Distribuído
a)
b)
c)
Dois processos desejam entrar na mesma região crítica (RC) ao
mesmo tempo.
Processo 0 tem a marca de tempo mais baixa; portanto, ele vence.
Quando o processo 0 conclui o uso da RC, ele envia um OK para
o processo pendente, de forma que 2 possa agora entrar na RC.
Exclusão Mútua:
Um Algoritmo de Anel de Token
a) Um grupo não-ordenado de processos em uma rede.
b) Um anel lógico construído em software.
Comparação
Messages per
entry/exit
Delay before entry
(in message times)
Problems
Centralized
3
2
Coordinator crash
Distributed
2(n–1)
2(n–1)
Crash of any
process
Token ring
1 to 
0 to n – 1
Lost token,
process crash
Algorithm
Uma comparação de três algoritmos de exclusão mútua.
O Modelo de Transações (1)
Atualização de um registro mestre com tolerância a falhas.
O Modelo de Transações (2)
Primitive
Description
BEGIN_TRANSACTION
Make the start of a transaction
END_TRANSACTION
Terminate the transaction and try to commit
ABORT_TRANSACTION
Kill the transaction and restore the old values
READ
Read data from a file, a table, or otherwise
WRITE
Write data to a file, a table, or otherwise
Exemplos de primitivas para transações.
O Modelo de Transações (3)
BEGIN_TRANSACTION
reserve WP -> JFK;
reserve JFK -> Nairobi;
reserve Nairobi -> Malindi;
END_TRANSACTION
(a)
a)
b)
BEGIN_TRANSACTION
reserve WP -> JFK;
reserve JFK -> Nairobi;
reserve Nairobi -> Malindi full =>
ABORT_TRANSACTION
(b)
Transação para reservar três vôos concluída com sucesso,
i.e., commit
Transação é abortada quando a reserva do terceiro vôo falha
Transações Distribuídas
a)
b)
Uma transação aninhada
Uma transação distribuída
Espaço de Trabalho Privativo
a)
b)
c)
O índice de arquivos e blocos de disco para um arquivo de três blocos
Situação após uma transação ter modificado o bloco 0 e concatenado
o bloco 3
Após o commit da transação
Writeahead Log
x = 0;
y = 0;
BEGIN_TRANSACTION;
x = x + 1;
y=y+2
x = y * y;
END_TRANSACTION;
(a)
Log
Log
Log
[x = 0 / 1]
[x = 0 / 1]
[y = 0/2]
[x = 0 / 1]
[y = 0/2]
[x = 1/4]
(b)
(c)
a) Uma transação
b) – d) O log antes de cada sentença ser executada
(d)
Controle de Concorrência (1)
Organização geral de gerentes para tratar transações.
Controle de Concorrência (2)
Organização geral dos
gerentes para tratar
transações distribuídas.
Serializabilidade
BEGIN_TRANSACTION
x = 0;
x = x + 1;
END_TRANSACTION
(a)
BEGIN_TRANSACTION
x = 0;
x = x + 2;
END_TRANSACTION
BEGIN_TRANSACTION
x = 0;
x = x + 3;
END_TRANSACTION
(b)
(c)
Schedule 1
x = 0; x = x + 1; x = 0; x = x + 2; x = 0; x = x + 3
Legal
Schedule 2
x = 0; x = 0; x = x + 1; x = x + 2; x = 0; x = x + 3;
Legal
Schedule 3
x = 0; x = 0; x = x + 1; x = 0; x = x + 2; x = x + 3;
Illegal
(d)
a) – c) Três transações: T1, T2, e T3
d) Possíveis escalonamentos
Two-Phase Locking (1)
Aquisição e liberação de locks no algoritmo de two-phase
locking.
Two-Phase Locking (2)
Two-phase locking estrito – todos os locks são liberados ao
mesmo tempo.
Ordenação com Marcas de Tempo
Pessimista
Controle de concorrência usando marcas de tempo.