Sincronização em SDs II

Bruno M. CarvalhoSala: 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

a) Transação para a reserva dos três vôos é aceita

b) Transação para a reserva dos três vôos é abortada quando o terceiro vôo está cheio

BEGIN_TRANSACTION reserve WP -> JFK; reserve JFK -> Nairobi; reserve Nairobi -> Malindi;END_TRANSACTION

(a)

BEGIN_TRANSACTION reserve WP -> JFK; reserve JFK -> Nairobi; reserve Nairobi -> Malindi full =>ABORT_TRANSACTION (b)

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

BEGIN_TRANSACTION x = 0; x = x + 1;END_TRANSACTION

(a)

BEGIN_TRANSACTION x = 0; x = x + 2;END_TRANSACTION

(b)

BEGIN_TRANSACTION x = 0; x = x + 3;END_TRANSACTION

(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; Ilegal

Permite execução paralela, mas o resultado final tem de ser igual a uma ordem sequencial de execução das transações

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 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)

Transações Aninhadas X Transações Distribuídas

Á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) Descritor de arquivos original e blocos de disco

b) 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

c) Substituição do arquivo original (novos blocos mais descritor) após aceitação

Writeahead Log

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)

x = 0;

y = 0;

BEGIN_TRANSACTION;

x = x + 1;

y = y + 2

x = y * y;

END_TRANSACTION;

(a)

Log

[x = 0 / 1]

(b)

Log

[x = 0 / 1]

[y = 0/2]

(c)

Log

[x = 0 / 1]

[y = 0/2]

[x = 1/4]

(d)

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 (wound-wait)