Sistemas Distribuídos - Aula 10 - Exclusão mútua e Acesso à Região Crítica

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


• 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


O processo 1 solicita ao coordenador permissão para acessar um recurso compartilhado.

A permissão é concedida.

8


Depois o processo 2 solicita permissão para acessar o mesmo recurso. O coordenador não responde.

9


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


O processo 0 tem a marca de tempo mais baixa, portanto

vence.

15


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


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


(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


(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

Technology

Sistemas Distribuídos - Aula 10 - Exclusão mútua e Acesso à Região Crítica