Sincronização
Capítulo 5 – Tanenbaum
Capítulo 10,11,12 e 13 - Coulouris
1
Sumário






Introdução
Sincronização de Relógio
Relógios Lógicos
Estado Global
Algoritmos Distribuídos
Transações Distribuídas
2
Introdução

Em um sistema centralizado a noção de tempo é não-ambígua

Quando um processo quer saber do tempo, efetua uma chamada e o
kernel responde

Se um processo A pergunta o tempo e pouco depois o processo B faz o
mesmo, certamente haverá diferença entre as respostas

Em sistemas distribuídos esta tarefa não é trivial, pois não existe uma
noção de relógio compartilhado globalmente

Cada processo, em diferentes máquinas, possui sua própria idéia de
tempo e dificilmente existe acordo sobre isso

A comunicação entre processos em sistemas distribuídos está
fortemente relacionada a forma como estes processos sincronizam

Sincronização refere-se a “ fazer a coisa certa na hora certa”
3
Network
4
Sincronização de Relógio

Durante o envio e recebimento de mensagens o tempo é levado
em consideração

Existem várias formas de sincronizar relógios em sistemas
distribuídos, mas todos são essencialmente baseados em troca
de informações de tempo

Variações no atraso das comunicações e a forma como estas
variações são tratadas, determinam a precisão dos algoritmos
de sincronização de relógio

Em muitos casos, conhecer o tempo absoluto não é necessário,
o que conta é que os eventos relacionados a diferentes
processos ocorram na ordem correta
5
Relógio Lógicos


Relógio físico

TAI – International Atomic Time

UCT – Universal Coordination Time
Para muitos propósitos , é suficiente que todas as máquinas
concordem sobre o tempo

Contudo, este acordo não precisa ser sobre o tempo absoluto mas
sobre a ordem em que os eventos ocorrem (noção de relógio lógico)

Quando um processo recebe uma mensagem, ele a coloca em uma fila
local, ordenada de acordo com seu selo de tempo (timestamp)
6
Problemas de Inconsistência

Cenário de atualização de débito e crédito em
banco de dados replicados
7
Estado Global

Em muitas situações, é útil conhecer o estado global de um sistema distribuído

O estado global de um sistema distribuído consiste de:

estado local de cada processo

mensagens que estão atualmente em trânsito, ou seja, que foram enviadas mas ainda
não foram entregues

O que exatamente é o estado local de um processo depende no que estamos
interessados

No caso de banco de dados distribuídos, o estado pode consistir dos registros do
banco de dados e excluir registros temporários usados para processamento

Uma possível utilização do estado global é a detecção de deadlock (o estado
local não evolui)
8
Coordenação de Processos
Distribuídos

Muitos algoritmos distribuídos de sincronização requerem a eleição de um
processo coordenador

Em geral, não interessa qual dos processos tomará para si esta
responsabilidade

Se todos os processos são exatamente iguais, com nenhuma característica que
os diferencie, a escolha se baseia em critérios aleatórios

Em geral, algoritmos de eleição de coordenador tentam localizar o processo de
maior processID e designá-lo como coordenador

A diferença entre algoritmos está na forma de localização e identificação do
coordenador

Existem vários algoritmos de eleição de coordenador, dentre eles:

Algoritmo Bully

Algoritmo Ring
9
Algoritmo Bully

Proposto por Garcia-Molina
(1982)

Quando um processo qualquer
(P) percebe que o coordenador
não está respondendo a
requisições, ele inicia uma
eleição

P envia mensagem ELECTION
para todos os processos de
processID maiores

Se ninguém responder, P ganha
a eleição

Se alguém responder, a eleição
acaba e P efetua sua tarefa
10
Algoritmo Ring

Segue basicamente as mesmas orientações do algoritmo Bully

Diferencia pela circulação da mensagem ELECTION em forma de anel

Eventualmente, dois processo podem iniciar o processo de eleição no mesmo
momento, ocasionando problemas

Não usa passagem de token (diferente de outras abordagens)

É assumido que os processos estão ordenados fisicamente ou logicamente

Cada processo conhece seu sucessor

Se o o sucessor está inoperante a mensagem é enviada ao próximo da cadeia

Ganha eleição quem tiver o maior número e esteja ativo, obviamente
11
Exclusão Mútua em Sistemas
Distribuídos

Sistemas envolvendo múltiplos processos são mais facilmente
programados através do uso de regiões críticas

Quando um processo tem que ler ou alterar estrutura de dados
compartilhada, primeiro entra na região crítica para obter
exclusão mútua

Em sistemas mono-processados, regiões críticas são protegidas
por semáforos, monitores e construtores similares

Em sistemas distribuídos tais mecanismos devem sofrer
adaptações
12
Algoritmo centralizado







Forma mais direta para obter exclusão mútua em sistemas
distribuídos
Simula o ambiente mono-processado
Um processo é eleito coordenador
Sempre que um processo quer entrar na região crítica, envia
uma mensagem ao coordenador
Se não existe outro processo na região crítica, o coordenador
envia mensagem garantindo a permissão
Apesar de simples de implementar, o coordenador é um ponto
de falha
Mensagens podem sofrer atrasos e perdas (request, grant,
release
13
Algoritmo Centralizado

P1 solicita entrar na região crítica e coordenador concede permissão

P2 solicita o mesmo, mas fica aguardando com requisição em fila

Quando P1 libera a região crítica, P2 obtém permissão
14
Algoritmo Distribuído

Alternativa a um único ponto de falha (coordenador) em algoritmo
centralizado

Quando um processo deseja entrar na região crítica, envia mensagem
para todos (inclusive para si mesmo)

É assumida a comunicação confiável, através de ack

Quando um processo recebe a mensagem (request) de outro processo,
a ação depende do seu estado a respeito da região crítica identificada
na mensagem


Se o receptor não está na RC e não quer entrar, envia OK para emissor

Se o receptor está na RC, não responde a mensagem e enfileira a
requisição

Se o receptor deseja entrar na RC, compara timestamp na mensagem com
o tempo contido na mensagem que ele próprio enviou. O menor vence.
Desvantagens: mais lento, mais complexo, mais caro
15
Transações Distribuídas






Um conceito fortemente relacionado a exclusão mútua é o conceito de
transação
Transações têm em comum a proteção de um recurso compartilhado
contra acesso simultâneo por processos concorrentes
Em particular, transações permitem a um processo acessar e modificar
múltiplos itens de dados como uma única ação atômica
Se o processo falhar durante a transação, tudo é recuperado a um
ponto antes do início da transação (abordagem tudo ou nada)
Programação usando transações requer primitivas especiais que
devem ser fornecidas pelo ambiente de suporte ou pela linguagem
A lista de primitivas depende do tipo de objeto em uso na transação:


Mail system: SEND, RECEIVE, FORWARD
Sistema contábil: READ, WRITE
16
Transações Distribuídas

BEGIN_TRANSACTION e END_TRANSACTION são delimitadores da
transação

As operações entre estes delimitadores formam o corpo da transação

Todo o corpo da transação é completamente executado ou nenhuma
operação será (all-or-nothing)

Propriedades ACID das transações:

Atomic: para o exterior a transação é indivisível

Consistent: a transação não viola invariantes do sistema

Isolated: transações concorrentes não interferem entre si

Durable: uma vez que a transação conclui, as alterações são permanentes
17
Classificação de Transações
1.
Flat Transaction:

2.
Série de operações que satisfazem as propriedades ACID
Nested Transaction:

Transação construída a partir de um determinado número de
transações (que podem rodar em paralelo)

3.
Importante para sistemas distribuídos
Distributed Transaction:

Difere sutilmente de Nested Transactions
18
Comparação entre Transações

Nested Transaction: divisão lógica em uma hierarquia de sub-transações

Distributed Transaction: transações indivisíveis que operam sobre dados
distribuídos
19
Controle de Transações


Obter atomicidade na presença de falhas é um importante aspecto a considerar (a ser
tratado posteriormente)
As propriedades consistent e isolation são basicamente manipuladas por controle de
concorrência através de: Data manager, Scheduler e Transaction manager
20