View
341
Download
2
Category
Preview:
DESCRIPTION
Sistemas Distribuídos - Exclusão mútua e Acesso à Região Crítica
Citation preview
1
SISTEMAS DISTRIBUÍDOS
EXCLUSÃO MÚTUA, COORDENAÇÃO E ACORDO
ARTHUR EMANUEL DE OLIVEIRA CAROSIA
2
EXCLUSÃO MÚTUA• Concorrência e colaboração são pontos chave em
sistemas distribuídos.
• Em muitos casos processos precisam acessar os mesmos recursos.
• É preciso evitar que recursos fiquem corrompidos ou inconsistentes.
• Garantir acesso mutuamente exclusivo a recursos por parte dos processos.
3
SINCRONIZAÇÃO EM SISTEMAS DISTRIBUÍDOS
• Para tratamento de exclusão mútua e deadlocks
• Algoritmos de Ficha• Algoritmo Centralizado• Algoritmo Descentralizado• Algoritmo Distribuído• Algoritmo Token Ring
• Coordenação de acesso a regiões críticas - Algoritmos de Eleição
• Algoritmo do Ditador• Algoritmo do Anel
4
EXCLUSÃO MÚTUA
Soluções baseadas em ficha
• Processos trocam mensagem especial, chamada ficha.• Quem possuir a ficha, possui acesso ao recurso. • Solução simples e eficaz, sem inanição ou deadlocks. • Desvantagem quando o processo que detém a ficha falha.
Soluções baseadas em permissão
• Algoritmo Centralizado • Algoritmo Descentralizado • Algoritmo Distribuído • Algoritmo Token Ring
5
ALGORITMO CENTRALIZADO
• Simular exclusão mútua como é feita em sistemas
centralizados.
• Um processo é escolhido como coordenador.
• Outros processos enviam mensagens ao coordenador
declarando que recursos querem usar.
6
ALGORITMO CENTRALIZADO
• Se o recurso estiver livre o coordenador concede acesso
ao recurso.
• Se o recurso estiver ocupado, nega por omissão ou
enviando mensagem.
• Ponto falho: se o coordenador falhar todo o sistema cai.
7
ALGORITMO CENTRALIZADO
O processo 1 solicita ao coordenador permissão para acessar um recurso compartilhado.
A permissão é concedida.
8
ALGORITMO CENTRALIZADO
Depois o processo 2 solicita permissão para acessar o mesmo recurso. O coordenador não responde.
9
ALGORITMO CENTRALIZADO
Quando o processo 1 libera o recurso. Informa ao coordenador , que então responde 2.
10
ALGORITMO DESCENTRALIZADO
• Um único coordenador costuma ser uma abordagem ruim.
• Solução: coordenador descentralizado.
• Assume-se (hipoteticamente) que cada recurso está
replicado.
• Cada processo coordena o acesso ao recurso.
• Processo interessado no recurso deve ter m > n/2 votos
concedendo acesso.
• Corretude do algoritmo baseado em probabilidade de acerto.
11
ALGORITMO DISTRIBUÍDO• Exclusão Mútua no acesso de recursos compartilhados em sistemas distribuídos
• Para qualquer evento no sistema não deve haver ambiguidade sobre qual processo solicitou o recurso ocorreu primeiro.
• Quando um processo quer acessar um recurso compartilhado, monta uma mensagem com:
• Nome do recurso• O número do processo• Hora corrente
• Depois, envia a mensagem a todos os outros processos e para ele mesmo
12
ALGORITMO DISTRIBUÍDOTrês situações podem ocorrer:
• Se o receptor não estiver acessando o recurso e não quiser acessá-lo:
• Devolve uma mensagem OK ao remetente.
• Se o receptor já tiver acesso ao recurso:
• Coloca a requisição em uma fila.
• Se o receptor também quiser acessar o recurso, mas ainda não acessou:
• Compara a marca de tempo da mensagem que chegou com a marca de tempo contida na mensagem que enviou para todos.
• A mais baixa vence. • Se a marca de tempo da mensagem acabou de chegar for mais baixa, o
receptor devolve uma mensagem OK. • Se a marca de tempo de sua própria mensagem for mais baixa, o
receptor enfileira a requisição que está chegando e nada envia.
13
ALGORITMO DISTRIBUÍDO
Dois processos querem acessar um recurso compartilhado no mesmo momento.
14
ALGORITMO DISTRIBUÍDO
O processo 0 tem a marca de tempo mais baixa, portanto
vence.
15
ALGORITMO DISTRIBUÍDO
Quando o processo 0 conclui, também envia uma
mensagem OK, portanto, agora 2 pode seguir adiante.
16
ALGORITMO TOKEN RING• Admite-se uma “rede de barramento” de processos sem
ordenação.
• Anel lógico é construído via software, cada processo é atribuído a uma posição no anel.
• Não importa a ordenação, apenas que cada processo saiba qual processo vem depois dele.
• Na inicialização do anel o processo 0 recebe uma “ficha”.
• A “ficha” trafega pelo anel do processo “k”para o processo “k+1”.
• Quando um processo adquire o token de seu vizinho, ele verifica se necessita acessar a região.
17
ALGORITMO TOKEN RING
(a) Grupo de processos não ordenados em uma rede.
(b) Um anel lógico é construído em software.
18
COMPARATIVO ENTRE OS ALGORITMOS
19
SINCRONIZAÇÃO EM SISTEMAS DISTRIBUÍDOS•Coordenação de acesso a regiões críticas - Algoritmos de Eleição
• Algoritmo do Ditador• Algoritmo do Anel
20
ALGORITMOS DE ELEIÇÃO
• Muitos algoritmos distribuídos requerem um coordenador.• Qualquer processo pode ser escolhido, no entanto um
deles precisa ser escolhido.• Premissas:
• Cada processo tem um número de processo exclusivo.• Um processo por máquina. • Todo processo sabe o número de todos os outros.
• Algoritmos tradicionais • Algoritmo do Ditador (ou Maioral) • Algoritmo do Anel
21
ALGORITMO DO DITADOR
Assume-se que cada processo conhece o número dos demais processos
• Casa processo sabe quem é o seu sucessor.• Quando um processo P, nota que o coordenador não está
respondendo, ele inicia uma eleição.
22
ALGORITMO DO DITADOR
P envia uma mensagem de ELEIÇÃO para todo processo com número maior que o seu.
• Se ninguém responde o processo P vence a eleição e se torna coordenador.
• Se um com número mais alto responde, P sai do processo.
23
ALGORITMO DO DITADOR
(a) O processo 4 convoca uma eleição.
(b) Os processos 5 e 6 respondem e mandam 4 parar.
(c) Agora cada um 5 e 6 convoca uma eleição.
24
ALGORITMO DO DITADOR
(d) Processo 6 manda 5 parar.
(e) Processo 6 vence e avisa ao demais.
25
ALGORITMO DO ANEL
Diferente da maioria, este algoritmo de anel não usa ficha e considera a ordenação
Quando um processo nota que não há coordenador
• Processo envia mensagem “ELEIÇÃO” para sucessor (no anel)
• Se PID do remetente > PID do destinatário, mensagem é passada adiante
• Se PID do remetente < PID do destinatário, este passa a participar da eleição
• A certa altura a mensagem volta ao último processo que entrou na disputa (maior PID), que será o novo coordenador
26
ALGORITMO DO ANEL
27
SISTEMAS DISTRIBUÍDOS
EXCLUSÃO MÚTUA, COORDENAÇÃO E ACORDO
ARTHUR EMANUEL DE OLIVEIRA CAROSIA
Recommended