Sincronização em SDs II
Bruno M. Carvalho
Sala: 3B2
Horário: 35T34
Exclusão Mútua
• Sistemas que usam múltiplos processos são mais facilmente
implementados usando regiões críticas
• Quando um processo tem de usar certas estruturas de dados
compartilhadas, ele entra em uma região crítica para garantir
exclusão mútua, isto é, que nenhum outro processo usará
estas estruturas de dados ao mesmo tempo
• Em sistemas uniprocessadores ou multiprocessadores com
memória compartilhada, exclusão mútua pode ser
conseguida usando-se semáforos ou monitores, que não são
suficientes no caso de multicomputadores
Algoritmo Centralizado
• Processo coordenador recebe mensagens solicitando entrada
em regiões críticas e permite ou não entradas de acordo com
tabelas internas
• Processo solicita ao coordenadador entrada na região crítica
e espera por permissão. Caso algum outro processo esteja
usando a região crítica, o número do processo é posto em
uma fila a espera da finalização da região crítica do outro
processo
• Mensagens REQ-OK-REL
• Coordenador também pode enviar mensagem negando
acesso no momento
Algoritmo Centralizado
• Processo solicitador pode estar bloqueado esperando pela
permissão, senão terá que examinar mensagens que chegam
após solicitação ou bloquear depois
• Garante exclusão mútua, evita inanição, simples e requer
somente três mensagens
• Coordenador é um ponto único de falha, e pode se tornar um
gargalo em sistemas grandes
Algoritmo Distribuído
• Requer ordenação total de eventos
• Processo que quer entrar em uma região crítica monta
mensagem com seu número, timestamp e o nome da região
crítica, e envia a todos os outros processos
• Processos que recebem uma mensagem deste tipo podem
– Enviar mensagem OK para o processo solicitante
– Não enviar nada caso esteja na região crítica desejada (e enviar após
sair da mesma)
– Comparar seu timestamp com o da mensagem e enviar OK caso seu
timestamp tenha o maior valor dos dois, no caso de estar tentando
entrar na mesma região crítica
Algoritmo Distribuído
• Após receber OKs de todos os outros processos, processo pode entrar na
região crítica
• Exclusão mútua garantida sem deadlock ou inanição
• Número de mensagens necessárias é de 2(n-1)
• Ponto único de falha foi trocado por múltiplos pontos de falha!!!!
• Qualquer máquina pode se tornar um gargalo, já que todas se envolvem
nas decisões de entrada em regiões críticas!
• Pode-se pedir permissão de uma fração dos processos somente (menos
ineficiente)
• Estranho: Algoritmo distribuído é menos robusto que o centralizado
Algoritmo Token Ring
• Anel virtual é criado usando-se alguma ordenação, como por
exemplo o número de endereço na rede
• Na inicialização do anel, o processo 0 recebe o token, e se
deseja entrar em alguma região crítica, o faz (no máximo
uma por vez) e envia o token para o próximo processo do
anel após sair
• É simples de se ver que o algoritmo garante exclusão mútua
e que inanição não ocorre
• Problema quando mensagem com o token se perde. Como
detectar se um processo ainda está usando o token ou
falhou?
Algoritmo Token Ring
• Quebra de processos pode ser detectada através de envio de
mensagens ACK e temporizadores
• Algoritmo centralizado é menos sensível a quebra de
processos que os distribuídos!!
Algoritmos de Eleição
• Vários algoritmos distribuídos utilizam um processo como
coordenador, e algoritmos de eleição são utilizados para
fazer esta escolha
• Processos tem um número único. Geralmente, algoritmos de
eleição tentam localizar o processo com o maior número e o
designam como coordenador
• Algoritmos também assumem que todos os processos sabem
o número de todos os outros processos, mas que não sabem
quais estão funcionando e quais não estão
• O objetivo é que ao final de sua execução, todos os
processos concordem em quem é o novo coordenador
Algoritmo do Brigão(Bully)
• Um processo P, ao detectar a falha do coordenador, inicia a
eleição do seguinte modo
– P envia uma mensagem de eleição para todos os processor com
números maiores que o seu
– Se ninguém responde, P vence a eleição e se torna coordenador
– Se um dos processos responde, ele assume a eleição e P espera
• Qunado um processo vence a eleição, ele envia uma
mensagem coordenador para todos os processos
• Se um processo que não estava funcionando volta a
funcionar, ele inicia uma eleição e se tiver o maior número,
assume a coordenação (daí o nome do algoritmo)
Algoritmo de Anel
• Assim que um processo P detecta a falha do coordenador,
ele monta uma mensagem que contém seu número
• Caso o seu sucessor na rede não esteja funcionando, ele
envia para o posterior. A cada vez que um processo recebe
uma mensagem de eleição, ele adiciona seu número e passa
a frente
• Após uma volta completa no anel a mensagem é recebida
por P que examina seu conteúdo e envia uma mensagem
para todos os processos do anel informando a identidade do
novo coordenador
Transações Atômicas
• Abstração de mais alto-nível que permite que
programadores abstraiam detalhes técnicos de como
exclusão mútua é obtida, como deadlocks são prevenidos,
etc.
• Implementam a semântica de ou-tudo-ou-nada em sua
execução, isto é, se a transação é cancelada antes de sua
finalização, os objetos e arquivos do sistema alterados por
esta transação atômica voltam ao estado anterior ao início da
mesma
• Implementação é complicada pelo fato que transação pode
estar sendo executada em várias máquinas simultaneamente
O Modelo Transacional
• O modelo transacional garante exclusão mútua e suporta
operações atômicas
• Considere uma transação composta das seguintes operações:
– Retirada de R$100 da conta 1
– Depósito de R$100 na conta 2
• A interrupção da transação após a execução da operação 1 e
antes da execução da operação 2 faz com que o dinheiro
desapareça
• Armazenamento estável – Projetado para suportar quebras
de computadores, é implementado usando-se discos backup
(exemplo: RAID)
Primitivas de Transações
Primitiva
Descrição
BEGIN_TRANSACTION
Marca o início de uma transação
END_TRANSACTION
Finaliza a transação e tenta aprová-la
ABORT_TRANSACTION
Aborta a transação e restaura valores antigos
READ
Lê dados de um arquivo, tabela, etc.
WRITE
Escreve dados em um arquivo, tabela, etc.
Exemplo: Reserva de Vôos
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 a reserva dos três vôos é aceita
Transação para a reserva dos três vôos é abortada quando
o terceiro vôo está cheio
Propriedades de Transações [ACID]
1) Atomicidade: Transações são indivisíveis para o
resto do sistema
2) Consistência: Invariantes do sistema não são
violadas
3) Isolamento: Transações concorrentes não
interferem com as outras (serialização)
4) Durabilidade: Quando uma transação é aceita, as
mudanças são permanentes (requer um
mecanismo de aceitação distribuído)
Serialização
Permite execução paralela, mas o resultado final tem de ser
igual a uma ordem sequencial de execução das transações
BEGIN_TRANSACTION
x = 0;
x = x + 1;
END_TRANSACTION
BEGIN_TRANSACTION
x = 0;
x = x + 2;
END_TRANSACTION
(a)
BEGIN_TRANSACTION
x = 0;
x = x + 3;
END_TRANSACTION
(b)
Schedule 1
x = 0;
x = x + 1;
Schedule 2
x = 0;
Schedule 3
x = 0;
(c)
x = 0;
x = x + 2;
x = 0;
x = x + 3
Legal
x = 0;
x = x + 1;
x = x + 2;
x = 0;
x = x + 3;
Legal
x = 0;
x = x + 1;
x = 0;
x = x + 2;
x = x + 3;
Ilegal
Classificação de Transações
• Transações Planas (Flat)
– Limitadas – Resultados parciais não podem ser aceitos
– Exemplo: Manter primeiros dois trechos do vôo do
exemplo anterior
• Transações aninhadas
– Transações iniciam subtransações, que por sua vez podem
iniciar sub-subtransações
• Transações distribuídas
– Transações planas mas distribuídas em relação ao acesso
aos dados
Transações Aninhadas X
Transações Distribuídas
• Transações aninhadas permitem uma organização hierárquica do sua transação
mas complicam as operações de aborto e aceitação
• Transações distribuídas são planas mas usam dados distribuídos (exemplo:
bancos de dados do JFK e do aeroporto de Nairobi)
Áreas de Trabalho Privadas
• Nesta técnica para implementação de transações atômicas,
os arquivos e outros objetos que serão utilizados pela
transação são copiados para uma área de trabalho local
• Área pública só é atualizada após aceitação da transação, e
no caso de aborto da transação, sua área privada é removida
• O problema desta técnica é o custo computacional de se
copiar os arquivos e objetos para todas as transações quando
em geral poucas são abortadas
• Opções são a cópia somente dos arquivos e objetos a serem
modificados, ou ainda somente as partes de objetos ou
arquivos que são modificadas
Áreas de Trabalho Privadas
a)
b)
c)
Descritor de arquivos original e blocos de disco
Cópia do descritor soment. Cópia de blocos somente quando escritos
•
Exemplo: Bloco 0 modificado e bloco 3 adicionado. Blocos novos são
chamados de shadow blocks
Substituição do arquivo original (novos blocos mais descritor) após
aceitação
Writeahead Log
x = 0;
Log
Log
Log
[x = 0 / 1]
[x = 0 / 1]
[x = 0 / 1]
[y = 0/2]
[y = 0/2]
y = 0;
BEGIN_TRANSACTION;
x = x + 1;
y=y+2
x = y * y;
[x = 1/4]
END_TRANSACTION;
(a)
(b)
(c)
(d)
b) – d) Log grava valores antigos e novos antes de cada operação ser
executada
•
Se transação é aceita não é necessário se fazer nada
•
Se a transação é abortada, usa-se o log para fazer um rollback
(restauração dos valores antigos)
Protocolo de Aceitação de
Duas Fases
• Execução do protocolo é iniciada pelo coordenador após a
última operação da transação ter sido iniciada
• Coordenador (geralmenteo processo que iniciou a transação)
escreve uma entrada no log informando que vai iniciar o
protocolo de aceitação e envia mensagens para todos os
processos envolvidos (subordinados) na execução da transação
informando-os que se preparem para a aceitação
• Subordinado checa se está pronto para aceitação, escreve em um
log local, e envia a resposta para o coordenador
• Coordenador decide pela aceitação ou não e envia mensagem
informando sua decisão
Controle de Concorrência
• Necessário para que transações não interfiram com as
execuções de outras transações
• Método mais simples é o controle de concorrência
otimista, onde cada transação pode fazer o que quiser, e
caso ocorra algum problema, o sistema tenta solucioná-lo
• Mantém tabelas contendo informações sobre arquivos e
objetos alterados pelas transações. Na fase de aceitação,
caso uma transação não tenha conflitos, é aceita
• Funciona melhor com áreas de trabalho privadas
• Como não usa locks, não existem deadlocks
Locking em Duas Fases
• Granularidade menor dos locks permite maior paralelismo
mas usa mais recursos e aumenta a probabilidade da
ocorrência de deadlocks
• Locking em duas fases faz com que transação tenha que
obter todos os locks antes de atualizar arquivos destes
locks. Dividido em fase de crescimento e diminuição
• A não obtenção de algum lock acarreta na liberação de
todos os outros locks. Se todas as transações usam locking
em duas fases, elas são serializáveis
Locking em Duas Fases
Locking Estrito em Duas Fases
• A fase de encolhimento só começa após aceitação ou
aborto da transação
• Outras transações só acessam valores escritos por
transações aceitas
• Elimina a necessidade de abortos em cascata, onde
transações que acessaram arquivos que foram alterados por
transações que posteriormente não foram aceitas, são
abortados também
• Diminui paralelismo
• Ordenação de locks pode ser usada para impedir a criação
de deadlocks
Locking Estrito em Duas Fases
Deadlocks
• Quatro estratégias para se lidar com deadlocks são:
– Ignorar
– Detecção: Permitir que deadlocks ocorram, detectá-los e
tentar se recuperar do problema
– Prevenção: Estaticamente fazer com que deadlocks sejam
estruturamente impossíveis de acontecer
– Evitar: Evitar a ocorrência de dealocks através de uma
alocação de recursos cuidadosa (não é utilizada, já que
algoritmos precisam saber antes de executar quais
recursos precisam)
Detecção de Deadlocks
Centralizada
• Máquinas locais mantém grafos de recursos para seus
processos e uma máquina coordenadora mantém um grafo
global do sistema
• Ao detectar um ciclo, coordenador mata um dos processos
• Atualizações podem ser feitas uma a uma, em blocos (em
intervalos de tempo regulares) ou ser solicitadas
explicitamente pelo coordenador
• Mensagens perdidas ou desordenadas podem levar a
detecção de falsos deadlocks, acarretando na eliminação
desnecessária de processos.
Detecção de Deadlocks
Centralizada
• Uso do algoritmo de Lamport para eliminar problema de
desordenação e até de mensagens perdidas
• Coordenador, ao detectar um deadlock, pode perguntar aos
processos envolvidos no deadlock se algum lock foi
liberado antes do tempo marcado no lock que fechou um
ciclo no grafo de recursos
Detecção de Deadlocks
Distribuída
• Em um algoritmo desta classe (Chandy-Misra-Haas) processos
que suspeitam que um deadlock está acontecendo enviam
mensagens “sondas” para investigar
• Mensagens incluem o número do processo que iniciou a
sondagem, o número do processo que a está reenviado agora, e o
número do processo para o qual está se enviando a mensagem
• Deadlock é detectado caso sondagem retorna ao processo que a
iniciou, que pode, então, cometer suicídio. Caso mais de um
processo detecte o deadlock, todos eles se suicidariam
(desnecessariamente)
• Solução – solicitar que o processo com maior número
identificador se suicide
Prevenção de Deadlocks
Distribuída
• Uma abordagem é a de se ordenar recursos globalmente e
exigir que processos os adquiram em ordem
• Em sistemas com tempo global e transações atômicas dois
outros algoritmos são possíveis
• Cada transação tem um tempo global associado, que indica
seu início
• No primeiro algoritmo, se um processo mais antigo quer um
recurso de um processo mais novo, ele espera, e no caso de
um processo mais novo querer um recurso de um processo
mais antigo ele é terminado (wait-die)
Prevenção de Deadlocks
Distribuída
• No segundo
algoritmo, se um
processo mais antigo
quer um recurso de
um processo mais
novo, ele preempta
(toma o recurso), e no
caso de um processo
mais novo querer um
recurso de um
processo mais antigo
ele espera (woundwait)