Sincronismo de Sistemas

Prévia do material em texto

9
Centro Universitário Sant’Anna
Sincronismo em Sistemas Distribuidos
São Paulo
2020
Erik Israel Bastos
Sincronismo em Sistemas Distribuidos
Trabalho apresentado como requisito parcial para a obtenção da nota na matéria de Sistemas Distribuidos do curso Engenharia da Computação ministrada pelo Prof.º Roberto Coutinho.
São Paulo
2020
Sumário
1. Introdução ....................................................................................................... 1
2. Relógios Físicos ............................................................................................. 2
3. Relógios Lógicos - Lamport e Vetorial ........................................................ 4
4. Exclusão Mutua .............................................................................................. 6
5. Algoritmos de Eleição .................................................................................... 7
6. Conclusão ....................................................................................................... 9
7. Referências ..................................................................................................... 9
1. Introdução
A sincronização entre processos é tão importante quanto a comunicação entre processos em sistemas distribuídos. Por exemplo, como as regiões críticas são implementadas em um sistema distribuído, e como estes recursos são alocados?
 Em sistemas de uma única CPU, regiões críticas, exclusão mútua, e outros problemas de sincronização são geralmente resolvidos usando métodos como semáforos e monitores. Estes métodos não são recomendados para serem usados em sistemas distribuídos porque eles invariavelmente contam (implicitamente) com a existência de uma memória compartilhada. Por exemplo, dois processos que estão interagindo usando um semáforo, ambos devem ser capazes de acessar o semáforo. Se eles estão rodando na mesma máquina, eles podem compartilhar o semáforo tendo−o armazenado no Kernel, e executar chamadas de sistema (system calls) para acessá−lo. Se, entretanto, eles estiverem rodando em diferentes máquinas, este método não mais funcionará, e outras técnicas devem ser utilizadas. Mesmo parecendo problemas simples, como determinar se o evento A aconteceu antes ou depois do evento B, requer bastante cuidado.
A sincronização em sistemas distribuídos é mais complicada do que em sistemas centralizados porque em sistemas distribuídos é necessário utilizar algoritmos distribuídos. Não é usualmente possível (ou desejável) coletar todas as informações sobre o sistema em um único lugar, e depois deixar que alguns processos examinem−na e tomem uma decisão como é feito no caso centralizado. Em geral, algoritmos distribuídos possuem as seguintes propriedades: 
1. A informação relevante está espalhada em múltiplas máquinas 
2. Processos tomam decisões baseadas somente nas informações locais 
3. Um único ponto de falha no sistema deve ser evitado 
4. Não existe um relógio em comum ou outro tipo preciso de tempo global
1
 Os primeiros três pontos significa dizer que é inaceitável colecionar todas as informações em um único local para o processamento. Por exemplo, para fazer alocação de recursos, não é aceitável enviar todas as requisições para um único processo gerenciador, o qual examina as requisições e permite ou nega as 
requisições baseadas nas informações contidas em suas tabelas. Em sistemas grandes, esta solução coloca uma carga pesada neste único processo. 
Além do mais, tendo um único ponto de falha como este torna o sistema não confiável. Idealmente, um sistema distribuído deve ser mais confiável do que as máquinas individuais. Se uma máquina sair do ar, o restante deve ser capaz de continuar funcionando. Atingir a sincronização sem centralização requer fazer coisas de um modo diferente dos sistemas operacionais tradicionais.
2. Relógios Físicos
Para algumas aplicações o tempo real é importante, nesse caso, relógios físicos externos são necessários por razões de eficiência, redundância e tolerância a falhas sendo que múltiplos relógios físicos são utilizados. Normalmente é feita a utilização do relógio atômico, todavia as oscilações do átomo de césio 133 podem causar problemas na sincronização desses relógios. 
Outro método de sincronização de relógios físicos é o UTC (Universal Coordinated Time) onde o tempo é preciso e trabalha em conjunto com a NIST (National Institute of Standard Time) que envia por broadcast um pulso no começo de cada segundo UTC. Alguns algoritmos foram propostos para tentar minimizar os problemas de sincronização em relógios físicos.
O Algoritmo de Cristian pressupõe a existência de um servidor de Tempo que possui um servidor WWV em que demais máquinas enviam pedidos perguntando a hora corrente sendo que o servidor responde com a hora atual “C”, o atraso da rede é mensurado “l”, o transmissor registra o intervalo de tempo em que fez o pedido “(T0)” e obteve a resposta ”(T1)”. A Hora atual pode ser calculada por: C + (T1-T0)/2.
2
Figura 1 – Diagrama com o Algoritmo de Cristian
Já no Algoritmo de Berkeley o servidor pergunta pelo tempo das demais máquinas e calcula o tempo médio fazendo a solicitação para outras máquinas adiantarem seus relógios.
Figura 2 – Diagrama com o Algoritmo de Berkeley
3
3. Relógios Lógicos – Lamport e Vetorial
Relógios lógicos são inteiros monotonamente crescentes conservados pelos sítios, usados para etiquetar mensagens e para estabelecer prioridades onde o valor da etiqueta de uma mensagem - seu timestamp - é o valor corrente do relógio lógico no momento do envio.
A prioridade de uma requisição é o valor corrente do relógio lógico no momento da operação sendo que empates são costumeiramente resolvidos pelo número único do sítio e podem ser incrementados a qualquer momento. Eles devem ser atualizados para permanecerem maiores que a etiqueta de qualquer mensagem recebida e devem ser incrementados entre certos eventos.
Nesses algoritmos cada processo do sistema distribuído mantém um contador crescente e monotônico C (relógio lógico) e cada evento a possui uma marca temporal C(a) na qual todos os processos concordam. Dessa forma, os eventos estão sujeitos às seguintes propriedades derivadas da relação happens-before:
1. Se a acontece antes de b no mesmo processo, então C(a) < C(b).
2. Se a e b representam, respectivamente, o envio e o recebimento de uma mensagem, então C(a) < C(b).
3. Sejam a e b eventos quaisquer, então C(a) ≠ C(b)
Ordenação total dos eventos se dá quando é possível definir a ordem de quaisquer dois eventos. De acordo com as propriedades dos contadores (timers) Lamport nenhum par de eventos terá uma mesma marcação temporal, pois basta ordenar os eventos de acordo com o tempo que eles ocorrem em seus processos e desfazer empates comparando uma propriedade arbitrária dos processos, como por exemplo, seu identificador. Quando este empate não é desfeito, uma ordenação parcial é obtida.
4
Como em vários algoritmos distribuídos a ordenação total é necessária para evitar ambiguidades, o algoritmo de Lamport é bastante citado na literatura. Nos algoritmos de disputa a recursos compartilhados, apenas um processo pode usar um recurso por vez, então os processos devem sincronizar para evitar conflitos, dessa forma ordenação total é um requisito para esse algoritmo.
Os relógios de Lamport obedecem as seguintes regras:
1. Um processo incrementa seu contador antes de cada evento daquele processo;
2. Quando um processo envia uma mensagem, esse inclui o valor de seu contador junto da mensagem;
3. No recebimento de uma mensagem, o processo atualiza seu contador para o valor maior entre o próprio valor e o valor do contador recebido na mensagem;
Os Relógios vetoriais são mecanismos usados em algoritmos de sistemas distribuídos que se baseiam na ordenação de eventos. Diferentemente dos relógios de Lamport, os relógios vetoriais são capazes de decidir se há causalidade entre os eventos. Esses mecanismos se interessam na ordenação parcial dos eventos. O algoritmode relógios vetoriais foi desenvolvido independentemente por Colin Fidge e Friedemann Mattern em 1988.
Por usar inteiros simples como marcas de tempo, o algoritmo de Lamport acaba perdendo informações de vários ordenamentos válidos. Apesar de consistente, a relação definida no algoritmo de Lamport define apenas uma de várias ordenações possíveis dada uma certa computação distribuída. De acordo com Lamport, se a → b então C(b) > C(a), porém o contrário não é verdadeiro.
Problemas que se preocupam com o estado global do sistema muitas vezes precisam de todas as ordenações potenciais. Os relógios vetoriais resolvem esse problema fazendo com que cada processo mantenha um array de contadores, sendo cada posição do array, um contador para cada processo no sistema.
O algoritmo de relógios lógicos reconhece que os eventos de comunicação (envio e recebimento de mensagens) formam "fronteiras" que separam a possibilidade de concorrência entre eventos. Como alguns eventos só ocorrem como decorrência do recebimento de mensagens, pode-se notar o conceito de causa e efeito entre os eventos em um sistema distribuído. Na ordenação parcial, mensagens sem causalidade não são mais ordenadas, o que acaba sendo menos custoso que a ordenação total.
5
Para a comunicação entre os processos, os arrays de marcas temporais são mantidos da seguinte forma:
1. Todos os valores do array são iniciados com zero;
2. O contador local é incrementado em uma unidade antes de cada evento atômico;
3. Sempre que o processo se prepara para enviar uma mensagem, ele incrementa o valor no array correspondente ao seu relógio lógico em uma unidade e envia todo o array junto da mensagem;
4. No recebimento de uma mensagem, o processo atualiza o seu atual para o máximo entre os valores do array recebido na mensagem e os valores de seu array. Porém, o valor do contador correspondente ao emissor é incrementado em uma unidade caso seu valor local já não é maior que o recebido;
5. Os valores de um array de marcas temporais nunca são decrementados.
Para a comunicação síncrona, deve haver um troca dos arrays de marcas temporais durante o evento de comunicação, devido a natureza simétrica da comunicação síncrona. Caso contrário o algoritmo falha, pois espera que a comunicação tome um tempo finito. Quando há um número variável de processos no sistema, os "arrays" de marcas temporais devem ser implementados como listas dinâmicas, sendo redimensionadas na entrada e saída de processos no sistema.
Ao comparar as marcas temporais, se nenhuma entrada existe para um determinado processo, deve-se considerar esse valor como zero para efeito de comparação.	
4. Exclusão Mutua
6
Exclusão mútua é a propriedade de um programa que garante que somente um processo tem acesso a determinada variável compartilhada em cada momento quando isso for necessário à correção do programa. É a solução mais simples para se obter a semântica não-determinística de um programa paralelo. A sua utilização permite que trechos do código que tratam variáveis em conflito sejam executados de forma atômica (isto é, não influenciada por outros processos).
Dado um recurso que pode ser acessado por diferentes processos ao mesmo tempo, somente um processo por vez pode acessar esse recurso. Contudo, um processo que ganha acesso a um recurso deve liberá-lo para que outro processo ganhe acesso ao mesmo.
 Qualquer processo que requisita um recurso deve recebê-lo em qualquer momento. Um processo do sistema é indicado como coordenador para controlar o acesso a um região crítica (RC). Qualquer processo que deseja entrar em uma RC deve pedir ao coordenador. Se o coordenador verificar que nenhum processo está acessando a RC então, o processo solicitante obtém o acesso. Caso contrário, este processo deve esperar até que o processo que está acessando a RC libere o recurso e avise o coordenador.
5. Algoritmos de Eleição
Muitas aplicações distribuídas requerem sempre um (processo) coordenador, com isso, é importante adotar algoritmos que determinam quando um processo será um coordenador. Essa determinação pode ser feita de diversas maneiras: Processo com maior ID, Número de Rede, Mais antigo, etc.
De forma geral, o objetivo de um algoritmo de eleição é garantir que todos os processos concordam na posse de um novo coordenador .
7
No Algoritmo bully (autoritário/valente) quando um processo nota que o coordenador não responde, uma eleição é iniciada, “P” envia uma mensagem de ELEIÇÃO para todos os processos com número maior que o seu, se ninguém responde, “P” ganha a eleição e se torna o coordenador. Se alguém responde, a tarefa de “P” está terminada e a eleição pode continuar a partir dos processos com maior número. Quando a eleição termina, o ganhador envia uma mensagem para todos os processos informando quem é o novo coordenador.
Figura 3 – Algoritmo Bully
No Algoritmo do anel os processos podem ser fisicamente ou logicamente ordenados, os mesmos processos sabem que é o seu sucessor, quando um processo nota que o coordenador não responde, constrói uma mensagem de ELEIÇÃO, inclui seu número e envia para seu sucessor. A mensagem circula pelo anel e cada processo inclui seu número, o iniciador da eleição recebe a mensagem de volta e determina quem é o coordenador baseado em qual processo possui o maior número. Após isso, envia a mensagem COORDENADOR pelo anel.
Figura 4 – Algoritmo do Anel
8
6. Conclusão
Ao construir um sistema distribuído é de suma importância que os processos e aplicações estejam de alguma maneira sincronizados, e o principal método para esse tipo de função é através de relógios, sejam eles lógicos ou físicos. Ambos os processos possuem pontos negativos e positivos, sendo que cabe ao desenvolvedor decidir qual será utilizado da melhor maneira e melhor se adequa ao projeto.
7. Referencias
https://www.cin.ufpe.br/~avmm/arquivos/provas%20software/resuminho3.pdf
http://www.facom.ufms.br/~ricardo/Courses/DisSys/Material/SD-Aula-08.PDF
Acesso em 03/12/2020 às 14:30 (Ambos os links)