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

Sistemas Distribuídos - 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 1

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. 2

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 3

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 4

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. 5

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 . 6

7. Algoritmo centralizado O processo 1 solicita ao coordenador permissão para acessar um recurso compartilhado. A permissão é concedida. 7

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

9. Algoritmo centralizado Quando o processo 1 libera o recurso. Informa ao coordenador , que então responde 2. 9

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. 10

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 11

12. Algoritmo distribuído Três situações podem ocorrer: Se o receptor não estiver acessando o recurso e não quiser acessá-lo: D evolve 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: C ompara 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. 12

13. Algoritmo distribuído Dois processos querem acessar um recurso compartilhado no mesmo momento. 13

14. Algoritmo distribuído O processo 0 tem a marca de tempo mais baixa, portanto vence. 14

15. Algoritmo distribuído Quando o processo 0 conclui, também envia uma mensagem OK, portanto, agora 2 pode seguir adiante. 15

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 . 16

17. Algoritmo token ring (a) Grupo de processos não ordenados em uma rede. (b) Um anel lógico é construído em software. 17

18. Comparativo entre os algoritmos 18

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 19

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 20

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 . 21

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. 22

23. Algoritmo do ditador O processo 4 convoca uma eleição. Os processos 5 e 6 respondem e mandam 4 parar. Agora cada um 5 e 6 convoca uma eleição. 23

24. Algoritmo do ditador (d) Processo 6 manda 5 parar. (e) Processo 6 vence e avisa ao demais. 24

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 25

26. Algoritmo do anel 26

27. Sistemas Distribuídos exclusão mútua, coordenação e acordo Arthur Emanuel de Oliveira Carosia 27