Sistemas Distribuidos - Parte 05 - Sincronizacao

Prévia do material em texto

Sincronização
OBSERVAÇÃO:
Para mudar a imagem deste slide, selecione a imagem e exclua-a. Em seguida, clique no ícone Imagens do espaço reservado pra inserir sua própria imagem.
‹nº›
SINCRONIZAÇÃO
O tempo é um problema importante para sistemas distribuídos
É uma quantidade que frequentemente desejamos medir precisamente para saber quando um evento específico ocorreu.
É necessário sincronizar o relógio com uma fonte de tempo confiável e aceita por todos.
Para vários problemas de distribuição foram desenvolvidos algoritmos que dependem da sincronização do relógio.
Manutenção da consistência dos dados distribuídos.
Verificação da autenticidade de uma requisição.
Eliminação do processamento de atualizações replicadas.
Etc.
‹nº›
SINCRONIZAÇÃO
Medir o tempo pode ser problemático.
Einstein demonstrou as consequências resultantes da observação de que a velocidade da luz é constante para todos os observadores, independentemente de sua velocidade relativa.
Ele provou que dois eventos considerados simultâneos em um ponto de referência não são necessariamente simultâneos de acordo com os observadores em outros pontos de referência.
‹nº›
SINCRONIZAÇÃO
A ordem relativa de dois eventos pode ser até invertida para dois observadores diferentes, mas isso não poderia acontecer se um evento tivesse causado a ocorrência do outro.
Nesse caso, o efeito físico acompanha a causa física para todos os observadores, embora o tempo decorrido entre causa e efeito possa variar.
A temporização de eventos físicos mostrou-se relativa ao observador, e a noção de Newton de tempo físico absoluto mostrou-se sem fundamento.
Não existe no universo nenhum relógio físico especial ao qual possamos recorrer quando queremos medir intervalos de tempo.
‹nº›
SINCRONIZAÇÃO
A noção de tempo físico também é problemática em um sistema distribuído.
Isso não se deve aos efeitos da teoria da relatividade.
O problema é baseado em uma limitação em nossa capacidade de registrar o tempo de eventos, em diferentes nós, de modo suficientemente preciso, para saber a ordem em que quaisquer dois eventos ocorreram, ou se eles ocorreram simultaneamente.
Não existe um tempo global absoluto ao qual possamos recorrer.
‹nº›
SINCRONIZAÇÃO
É importante que vários processos não acessem simultaneamente um recurso compartilhado, mas cooperem para garantir um ao outro acesso temporário exclusivo.
Outro exemplo de sincronização é que vários processos às vezes podem concordar com a ordenação de eventos.
Por exemplo, se a mensagem do processo P foi enviada antes ou depois da mensagem do processo Q.
O problema é que a sincronização em sistemas distribuídos costuma ser muito mais difícil em comparação com a sincronização em sistemas monoprocessadores ou multiprocessadores.
‹nº›
SINCRONIZAÇÃO DE RELÓGIOS
‹nº›
Sincronização de Relógios
Sistema centralizado
O tempo não é ambíguo.
Quando um processo necessitar saber a hora, faz uma chamada de sistema e o núcleo responde.
Sistema distribuído
Conseguir acordo nos horários não é trivial.
‹nº›
Relógio Físicos
‹nº›
Sincronização de Relógios
Relógios Físicos
Praticamente todos os computadores têm um circuito para monitorar a passagem do tempo.
Um temporizador de computador usualmente é um cristal de quartzo lapidado e usinado com precisão.
Quando mantidos sob tensão, cristais de quartzo oscilam a uma frequência bem definida.
Associados com cada cristal há dois registradores, um contador e um registrador de retenção.
Cada oscilação do cristal reduz uma unidade do contador.
Quando o contador chega a zero é gerada uma interrupção e o contador é recarregado pelo registrador de retenção.
Cada interrupção é denominada ciclo de relógio.
‹nº›
Sincronização de Relógios
Relógios Físicos
A maioria dos computadores possuem uma RAM CMOS especial suportada por bateria.
A cada ciclo de relógio, o procedimento do serviço de interrupção soma uma unidade à hora armazenada na memória.
Desse modo o relógio (de software) é mantido atualizado.
Com um único computador e um único relógio, não há problema se esse relógio estiver um pouco defasado.
Todos os processos na máquina usam o mesmo relógio.
‹nº›
Sincronização de Relógios
Relógios Físicos
É impossível garantir que todos os cristais em diferentes computadores funcionem exatamente à mesma frequência.
Tem-se que os relógios de software gradativamente saem de sincronia e informem valores diferentes quando lidos.
Essa diferença é denominada defasagem de relógio.
Programas que esperam que o horário associado com um arquivo, objeto, processo ou uma mensagem esteja correto e seja independente da máquina na qual foi gerado podem falhar.
‹nº›
Sincronização de Relógios
Relógios Físicos
Em alguns sistemas a hora real marcada pelo relógio é importante.
São necessários relógios físicos externos.
Por razões de eficiência e redundância, em geral considera-se desejável ter vários relógios físicos, o que resulta em dois problemas:
Como sincronizá-los com relógios do mundo real?
Como sincronizar os relógios um com o outro?
‹nº›
Sincronização de Relógios
Relógios Físicos
1948  Invenção do relógio atômico.
Possível medir o tempo com muito mais exatidão, independentemente dos movimentos erráticos da Terra.
Um segundo foi definido como o tempo que o átomo de césio 133 leva para fazer exatamente 9.192.631.770 transições.
Vários laboratórios ao redor do mundo têm relógios de césio 133 e cada um deles informa periodicamente ao Bureau International de l'Heure (BIH), em Paris, quantas vezes seu relógio pulsou.
O BIH calcula a média desses valores e produz a hora atômica internacional (International Atomic Time) ou TAI (Temps Atomique International).
‹nº›
Sincronização de Relógios
Relógios Físicos
O BIH introduz segundos extras sempre que a discrepância entre a hora TAI e a hora solar alcança 800 ms.
Essa correção dá origem a um sistema de medição do tempo que fica em fase com o movimento aparente do sol.
É denominado hora coordenada universal (Universal Coordinated Time), ou UTC.
É a base de toda a moderna medição civil do tempo.
Substituiu o antigo padrão, o Greenwich Mean Time – GMT.
‹nº›
Sincronização de Relógios
Relógios Físicos
1 segundo é um intervalo perceptível para computadores.
Um sistema operacional que precisa manter horários exatos durante certo período de anos deve ter um software especial para lidar com segundos extras quando eles são anunciados.
Para fornecer UTC a quem precisa da hora exata, o National Institute of Standard Time (Nist) opera uma estação de rádio de ondas curtas cujo prefixo é WWV.
Transmite um pulso curto no início de cada segundo UTC.
A precisão da própria WWV é de ±1 ms.
Devido a flutuações atmosféricas aleatórias, a precisão não é melhor do que ±10 ms.
Estações situadas em vários países oferecem um serviço semelhante.
‹nº›
Sincronização de Relógios
Relógios Físicos
Há satélites que também oferecem serviço UTC.
O satélite operacional ambiental geoestacionário (Geostationary Environment Operational Satellite - Geos) pode oferecer UTC com exatidão de até 0,5 ms.
Usar serviços de rádio de ondas curtas ou de satélites requer conhecer a exata posição relativa entre remetente e receptor.
Radiorreceptores para WWV, Geos e outras fontes UTC estão disponíveis no comércio.
‹nº›
Algoritmos de Sincronização de Relógios
‹nº›
Sincronização de Relógios
Algoritmos de Sincronização de Relógios
Se uma máquina tiver um receptor WWV, a meta é manter todas as outras máquinas sincronizadas com ela.
Se nenhuma máquina tiver receptores WWV, cada uma monitora seu próprio horário, e o objetivo é manter todas as máquinas o mais próximas possível.
‹nº›
Sincronização de Relógios
Algoritmos de Sincronização de Relógios
Cada máquina deve ter um temporizador que provoca uma interrupção H vezes por segundo.
Vamos denominar C o valor do relógio.
Quando a hora UTC é t, o valor do relógio na máquina p é Cp(t).
Seria perfeito que Cp´(t) = dC/dt fosse 1.
Cp´(t) é denominado frequência do relógio de p no tempo t.
A defasagem do relógio é definida como Cp´(t) - 1 e denotaa magnitude da diferença entre a frequência do relógio de p e a frequência de um relógio perfeito.
O deslocamento em relação a uma hora específica t é Cp(t) - t.
‹nº›
Sincronização de Relógios
Algoritmos de Sincronização de Relógios
Temporizadores reais não interrompem exatamente H vezes por segundo.
O erro relativo que se obtém com modernos chips temporizadores é de aproximadamente 10-5.
Se existir alguma constante ρ tal que
		1 - ρ ≤ dC/dt ≤ 1 + ρ
pode-se dizer que o temporizador está funcionando dentro de sua especificação.
A constante ρ é especificada pelo fabricante e é conhecida como taxa máxima de deriva.
Especifica até que ponto a defasagem de um relógio pode chegar.
‹nº›
Sincronização de Relógios
Algoritmos de Sincronização de Relógios
‹nº›
Sincronização de Relógios
Algoritmos de Sincronização de Relógios
Se dois relógios derivarem em direções opostas em relação à UTC, passado um tempo Δt após a sincronização entre os dois, eles podem apresentar uma defasagem de até 2ρΔt.
Se os projetistas de sistemas operacionais quiserem garantir que a defasagem entre dois relógios nunca seja maior do que δ, eles devem ser sincronizados novamente (em software) no mínimo a cada δ/2ρ segundos.
A diferença entre os vários algoritmos encontra-se na maneira como essa sincronização periódica é feita.
‹nº›
Network Time Protocol (NTP)
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
O NTP (Network Time Protocol) define uma arquitetura para um serviço de tempo e um protocolo para distribuir informações de tempo pela Internet.
Os principais objetivos de projeto e as características do NTP são:
Fornecer um serviço que permita aos clientes na Internet serem sincronizados precisamente com o UTC.
Fornecer um serviço confiável que possa sobreviver a longas perdas de conectividade.
Permitir que os clientes sejam sincronizados de forma suficientemente frequente para compensar as taxas de deriva encontradas na maioria dos computadores.
Fornecer proteção contra interferência no serviço de tempo, seja mal-intencionada ou acidental
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
O serviço NTP é fornecido por uma rede de servidores localizados na Internet.
Os servidores primários são conectados diretamente a uma fonte de tempo, como um relógio de rádio recebendo UTC.
Os servidores secundários são sincronizados com os servidores principais.
Os servidores são conectados em uma hierarquia lógica chamada sub-rede de sincronização, cujos níveis são chamados de estratos (strata).
Os servidores primários ocupam o stratum 1.
Os servidores do stratum 2 são secundários, sincronizados diretamente com os servidores primários.
Os servidores do stratum 3 são sincronizados com os servidores do stratum 2, e assim por diante.
Os servidores de nível mais baixo (folha) são executados nas estações de trabalho dos usuários.
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
Os relógios pertencentes aos servidores com números de stratum mais altos estão sujeitos a serem menos precisos do que aqueles com números de stratum baixos.
O NTP também leva em conta, na avaliação da qualidade dos dados de temporização mantidos por um servidor em particular, os atrasos da viagem de ida e volta total da mensagem até a raiz.
A sub-rede de sincronização pode ser reconfigurada quando servidores se tornam inatingíveis ou quando ocorrem falhas.
Se, por exemplo, a fonte de UTC de um servidor falha, ele pode ser sincronizado com outro servidor.
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
Estratos do NTP:
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
Os servidores NTP são sincronizados entre si de três maneiras:
O modo multicast se destina a ser utilizado em uma rede local de alta velocidade. Periodicamente, um ou mais servidores de tempo enviam via multicast a informação de tempo para servidores que estão em execução em outros computadores conectados na rede local, os quais configuram seus relógios pressupondo um pequeno atraso.
No modo de chamada de procedimento um servidor aceita requisições de outros computadores, os quais ele processa respondendo com seu carimbo de tempo. Esse modo é conveniente quando é exigida uma precisão melhor do que a que pode ser obtida com o multicast.
O modo simétrico se destina a ser utilizado pelos servidores que fornecem informações de tempo em redes locais e pelos níveis hierarquicamente mais altos, em que uma maior precisão necessita ser obtida. Dois servidores operando no modo simétrico trocam mensagens com informações de temporização. Esses dados são armazenados como parte de uma associação entre os servidores que são mantidos para melhorar a precisão de sua sincronização com o passar do tempo.
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
Em todos os modos, as mensagens são enviadas de maneira não confiável, usando o protocolo de transporte UDP.
No modo de chamada de procedimento e no modo simétrico, os processos trocam pares de mensagens.
Cada mensagem carrega carimbos de tempo de eventos de mensagem recentes.
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
Existem quatro tempos, Ti-3, Ti-2, Ti-1, e Ti para as mensagens m e m' enviadas entre os servidores A e B. Pode haver um atraso não desprezível entre a chegada de uma mensagem e o envio da próxima. As mensagens podem ser perdidas, mas os três carimbos de tempo transportados em cada mensagem são válidos.
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
Para cada par de mensagens enviadas entre dois servidores, o NTP calcula:
Uma compensação ci, que é uma estimativa da compensação real entre os dois relógios.
Um atraso ai, que é o tempo de transmissão total das duas mensagens.
Se o valor real da compensação do relógio em B, relativa à de A, for c e, se os tempos de transmissão reais de m e m' forem t e t' respectivamente, então temos:
Ti-2 = Ti-3 + t + c
Ti = Ti-1 + t' - c
ai = t + t' = Ti-2 - Ti-3 + Ti - Ti-1
ci = (t - t')/2 = (Ti-2 - Ti-3 + Ti-1 - Ti)/2
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
Pode-se mostrar que:
Assim:
ci é uma estimativa da compensação.
ai é uma medida da precisão dessa estimativa.
Os servidores NTP aplicam um algoritmo de filtragem de dados em sucessivos pares <ci,ai>, para fazer uma estimativa da compensação c e calcular a qualidade dessa estimativa com base em uma quantidade estatística chamada filtro de dispersão.
Uma dispersão relativamente alta representa dados relativamente não confiáveis.
Os oito pares <ci,ai> mais recentes são mantidos. O valor de cj que corresponde ao valor mínimo aj é escolhido para fazer a estimativa de c.
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
Em geral, um servidor NTP se envolve nas trocas de mensagem com vários pares.
Além da filtragem de dados aplicada nas trocas com cada par, o NTP examina os valores obtidos das trocas com cada um dos vários pares, procurando valores relativamente não confiáveis.
Esse algoritmo pode fazer um servidor mudar o par que normalmente utiliza para obter sincronismo.
Os pares com números de stratum mais baixos são mais favorecidos do que os que possuem números de stratum mais altos, pois estão mais próximos das fontes de tempo principais.
‹nº›
Sincronização de Relógios
Network Time Protocol (NTP)
O NTP modifica a frequência de atualização do relógio local de acordo com observações de sua taxa de deriva.
Se é descoberto um relógio que sempre avança no tempo na taxa de, digamos, quatro segundos por hora, então sua frequência pode ser reduzida ligeiramente (no software ou no hardware) para compensar isso.
‹nº›
Algoritmo de Berkeley
‹nº›
Sincronização de Relógios
Algoritmo de Berkeley
Em muitos algoritmos como o NTP, o servidor de tempo é passivo.
No Unix de Berkeley o servidor de tempo é ativo e consulta todas as máquinas de tempos em tempos para perguntar qual é a hora que cada uma está marcando.
Com base nas respostas, calcula um horário médio e diz a todas as outras máquinas que adiantem ou atrasem seus relógios.
Métodoadequado para um sistema no qual nenhuma máquina tenha receptor WWV.
‹nº›
Sincronização de Relógios
Algoritmo de Berkeley
A hora do daemon de tempo tem de ser ajustada manualmente pelo operador de tempos em tempos.
Para muitas finalidades é suficiente que todas as máquinas concordem com a mesma hora.
Não é essencial que essa hora também esteja de acordo com a hora real anunciada por rádio a cada hora.
‹nº›
RELÓGIOS LÓGICOS
‹nº›
Relógios Lógicos
Até aqui consideramos que a sincronização de relógios está naturalmente relacionada com a hora real.
Pode ser suficiente que cada nó concorde com uma hora corrente, sem que essa hora seja a mesma que a hora real.
Lamport (1978)
Mostrou que, embora a sincronização entre relógios seja possível, ela não precisa ser absoluta.
Se dois processos não interagirem, não é necessário que seus relógios sejam sincronizados.
De modo geral, o que importa não é que todos os processos concordem com a hora exata, mas com a ordem em que os eventos ocorrem.
‹nº›
Relógios Lógicos de Lamport
‹nº›
Relógios Lógicos
Relógios Lógicos de Lamport
Para sincronizar relógios lógicos, Lamport definiu uma relação denominada acontece antes.
A expressão ab é lida como “a acontece antes de b” e significa que todos os processos concordam que primeiro ocorre um evento a e, depois, um evento b.
A relação “acontece antes” pode ser observada diretamente em duas situações:
Se a e b são eventos do mesmo processo, e a ocorre antes de b, então ab é verdadeira.
Se a é o evento de uma mensagem sendo enviada por um processo, e b é o evento da mensagem sendo recebida por um outro processo, então ab também é verdadeira.
A relação “acontece antes” é transitiva, portanto se ab e bc, então ac.
‹nº›
Relógios Lógicos
Relógios Lógicos de Lamport
Se dois eventos, x e y, acontecem em processos diferentes que não trocam mensagens (nem mesmo indiretamente via terceiros), então xy não é verdadeira, mas yx também não é.
Diz-se que esses eventos são concorrentes.
Nada pode ser dito sobre quando os eventos aconteceram ou qual evento aconteceu em primeiro lugar. 
‹nº›
Relógios Lógicos
Relógios Lógicos de Lamport
É preciso um modo de medir uma noção de tempo tal que, para cada evento a, possa ser designado um valor de tempo C(a) com o qual todos os processos concordam.
Esses valores de tempo devem ter a seguinte propriedade:
	Se ab, então C(a) < C(b).
O tempo de relógio, C, deve sempre correr para a frente (aumentar).
Os tempos podem ser corrigidos pela adição de um valor positivo, nunca por subtração.
‹nº›
Relógios Lógicos
Relógios Lógicos de Lamport
Considere os três processos que executam em máquinas diferentes, cada uma com seu próprio relógio, que funciona a sua própria velocidade.
‹nº›
Relógios Lógicos
Relógios Lógicos de Lamport
Para implementar relógios lógicos de Lamport, cada processo Pi mantém um contador local Ci.
Atualização dos contadores:
Antes de executar um evento, Pi executa Ci  Ci + 1.
Quando o processo Pi envia uma mensagem m a Pj, ajusta a marca de tempo de m, ts(m), para o valor de Ci.
Ao receber uma mensagem m, o processo Pj ajusta seu próprio contador local para
Cj  max {Cj, ts(m)} e, depois disso, executa a primeira etapa e entrega a mensagem à aplicação.
‹nº›
Relógios Lógicos
Relógios Lógicos de Lamport
Em algumas situações, é desejável um requisito adicional: dois eventos nunca ocorrem exatamente ao mesmo tempo.
Podemos anexar o número do processo no qual o evento ocorre à extremidade menos significativa do tempo, separado por um ponto decimal.
‹nº›
EXCLUSÃO MÚTUA
‹nº›
EXCLUSÃO MÚTUA
Uma questão fundamental em sistemas distribuídos é a concorrência e a colaboração entre vários processos.
Normalmente significa que processos vão precisar acessar simultaneamente os mesmos recursos.
São necessárias soluções que garantam acesso mutuamente exclusivo pelos processos.
Sistemas locais resolvem bem com soluções como semáforos e monitores.
‹nº›
EXCLUSÃO MÚTUA
Algoritmos distribuídos de exclusão mútua podem ser classificados em duas categorias diferentes:
Soluções baseadas em ficha.
Abordagem baseada em permissão. 
‹nº›
EXCLUSÃO MÚTUA
Nas soluções baseadas em ficha, consegue-se a exclusão mútua com a passagem de uma mensagem especial entre os processos, conhecida como ficha.
Há só uma ficha disponível, e quem quer que a tenha pode acessar o recurso compartilhado.
Ao terminar, a ficha é passada adiante para o processo seguinte.
Dependendo do modo como os processos são organizados, pode-se garantir, com razoável facilidade, que todo processo terá oportunidade de acessar o recurso.
A ficha evita a inanição.
Também fica fácil evitar deadlocks, quando vários processos ficam esperando uns pelos outros para prosseguir.
‹nº›
EXCLUSÃO MÚTUA
A principal desvantagem de soluções baseadas em fichas é quando ela se perde.
É preciso iniciar um complicado procedimento distribuído para assegurar a criação de uma nova ficha.
Na abordagem baseada em permissão, um processo que quiser acessar o recurso deve antes solicitar a permissão de outros processos.
Estudaremos os algoritmos:
Centralizado
Descentralizado
Distribuído
Token ring
‹nº›
Algoritmo Centralizado
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Centralizado
O algoritmo centralizado é o modo mais direto de conseguir exclusão mútua em um sistema distribuído.
Simula como ela é feita em um sistema monoprocessado.
Um processo é eleito como o coordenador e, sempre que um processo (processo 1) quiser acessar um recurso compartilhado, envia uma mensagem de requisição ao coordenador.
Se nenhum outro processo estiver acessando aquele recurso, o coordenador devolve uma resposta concedendo a permissão.
Quando a resposta chega, o processo requisitante pode seguir adiante.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Centralizado
E se outro processo (processo 2) pedir permissão para acessar o recurso?
O coordenador sabe que um outro processo diferente já o está utilizando.
Não dará a permissão.
O método exato usado para negar permissão é dependente do sistema.
O coordenador pode apenas se abster de responder, bloqueando o processo 2.
O coordenador pode enviar uma resposta dizendo “permissão negada”.
Independentemente do caso, ele coloca a requisição do segundo processo na fila e aguarda mais mensagens.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Centralizado
Quando o processo 1 conclui a utilização do recurso, envia uma mensagem ao coordenador a fim de liberar seu acesso exclusivo.
O coordenador retira o primeiro item da fila de requisições adiadas e envia ao processo requisitante uma mensagem de concessão de permissão.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Centralizado
O algoritmo garante exclusão mútua, pois o coordenador só permite o acesso de um processo por vez ao recurso.
Também é justo, visto que as permissões são concedidas na ordem em que as requisições foram recebidas.
Nenhum processo jamais esperará para sempre.
Sua simplicidade o torna uma solução atraente para muitas situações práticas.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Centralizado
A abordagem centralizada também tem deficiências.
O coordenador é um ponto de falha único. Se ele falhar, todo o sistema pode cair.
Se os processos normalmente bloquearem após emitir uma requisição, não podem distinguir um coordenador inativo de uma “permissão negada”.
Em um sistema de grande porte, um coordenador único pode se tornar um gargalo de desempenho.
Ainda assim, em muitos casos os benefícios proporcionados por sua simplicidade compensam as desvantagens potenciais.
‹nº›
Algoritmo DESCentralizado
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Descentralizado
Ter um único coordenador costuma ser uma abordagem ruim.
Outra solução é usar um algoritmo de votação que pode ser executado usando um sistema baseado em DHT.
Adota-se como premissa que cada recurso é replicado n vezes.
Toda réplica tem seu próprio coordenador para controlar o acesso por processos concorrentes.
Sempre que um processo quiser acessar o recurso, ele vai precisar apenas obter um voto majoritário de m > n/2 coordenadores.
Quando um coordenador não derpermissão para acessar um recurso, ele informará ao requisitante.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Descentralizado
Torna a solução centralizada original menos vulnerável a falhas de um único coordenador.
Quando um coordenador falhar, ele se recuperará rapidamente, mas esquecerá qualquer voto que tenha dado antes de falhar.
Um reinício fará o coordenador esquecer que, antes, já tinha concedido permissão para algum processo acessar o recurso.
Em decorrência, após o reinício ele poderá conceder essa mesma permissão incorretamente, mais uma vez, a um outro processo.
Não há problemas pois os demais coordenadores não concederão a permissão.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Descentralizado
Para implementação é utilizado um sistema baseado em DHT no qual um recurso é replicado n vezes.
Considere que o recurso é conhecido sob seu nome exclusivo rname.
O nome da i-ésima réplica é rname-i, que então é usada para calcular uma única chave por meio de uma função de hash conhecida.
Assim todo processo pode gerar as n chaves dado o nome de um recurso e, na sequência, consultar cada nó responsável por uma réplica.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Descentralizado
Se a permissão para acessar o recurso for negada (o processo obtiver menos do que m votos), ele desistirá durante um período de tempo escolhido aleatoriamente e fará nova tentativa mais tarde.
‹nº›
Algoritmo Distribuído
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Distribuído
O algoritmo distribuído requer que haja uma ordenação total de todos os eventos no sistema.
Para qualquer par de eventos não pode haver ambiguidade sobre qual realmente aconteceu em primeiro lugar.
O algoritmo de Lamport é um modo de conseguir essa ordenação e pode ser usado para fornecer marcas de tempo para exclusão mútua distribuída.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Distribuído
Quando um processo quer acessar um recurso compartilhado, monta uma mensagem que contém:
Nome do recurso
Seu número de processo
Hora corrente (lógica)
Depois, envia a mensagem a todos os outros processos.
Adota-se como premissa que o envio de mensagens é confiável.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Distribuído
Quando um processo recebe uma mensagem de requisição de um outro processo, a ação que ele executa depende de seu próprio estado em relação ao recurso nomeado na mensagem.
Três casos têm de ser claramente distinguidos:
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, simplesmente não responde. Em vez disso, coloca a requisição em uma fila.
Se o receptor também quiser acessar o recurso, mas ainda não o fez, ele 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 que 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.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Distribuído
Após enviar requisições que peçam permissão, um processo se detém e espera até que todos tenham dado permissão.
Logo que todas as permissões tenham entrado, ele pode seguir adiante.
Quando conclui, envia mensagens OK para todos os processos que estão em sua fila e limpa a fila.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Distribuído
E se 2 processos tentarem acessar o mesmo recurso ao mesmo tempo?
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Distribuído
A exclusão mútua é garantida sem deadlock nem inanição.
O número de mensagens requeridas por entrada nessa circunstância é 2(n-1), onde n é o número total de processos no sistema.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Distribuído
O ponto de falha único foi substituído por n pontos de falha.
Se qualquer processo falhar, não responderá às requisições.
Esse silêncio será interpretado como recusa de permissão e bloqueará todas as tentativas subsequentes.
O algoritmo pode ser melhorado.
Quando uma requisição chega, o receptor sempre envia uma resposta, concedendo ou recusando permissão.
Se uma requisição ou uma resposta se perder, o remetente esgota a temporização de espera e continua tentando até que uma resposta volte ou que o remetente conclua que o destinatário está morto.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Distribuído
Ou uma primitiva de comunicação multicast deve ser usada, ou cada processo deve manter a lista de associação ao grupo, incluindo processos que entram no grupo, saem do grupo e caem.
O método funciona melhor com pequenos grupos de processos que nunca mudam seus grupos de associação.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Distribuído
No algoritmo distribuído, todos os processos estão envolvidos em todas as decisões referentes ao acesso ao recurso compartilhado.
Se um processo for incapaz de manipular a carga, é improvável que forçar todos a fazer exatamente a mesma coisa em paralelo ajudará muito.
‹nº›
Algoritmo Token Ring
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Token Ring
O algoritmo token ring é uma abordagem diferente para conseguir exclusão mútua.
Sua ideia é construir um anel lógico em software e a cada processo é designada uma posição no anel.
As posições no anel podem ser alocadas em ordem numérica de endereços de rede ou por alguns outros meios.
Não importa qual é a ordenação, o que importa é que cada processo saiba de quem é a vez depois dele mesmo.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Token Ring
Quando o anel é inicializado, o processo 0 recebe uma ficha.
A ficha circula ao redor do anel.
Quando um processo adquire a ficha, verifica se precisa acessar o recurso compartilhado.
Caso necessite, o processo segue adiante, faz todo o trabalho e libera o recurso.
Após concluir, passa a ficha ao longo do anel.
Não é permitido acessar o recurso novamente, de imediato, usando a mesma ficha.
‹nº›
EXCLUSÃO MÚTUA
Algoritmo Token Ring
Se a ficha se perder, precisa ser regenerada.
Detectar que ela se perdeu é difícil, visto que a quantidade de tempo entre aparições sucessivas da ficha na rede é ilimitada.
O algoritmo também encontra dificuldade se um processo cair.
Se for exigido que um processo que recebe a ficha reconheça o recebimento, um processo morto será detectado quando seu antecessor tentar lhe passar a ficha.
Nesse ponto, o processo morto pode ser removido do grupo.
Isso requer que todos mantenham a configuração corrente do anel.
‹nº›
ALGORITMOS DE ELEIÇÃO
‹nº›
ALGORITMOS DE ELEIÇÃO
Muitos algoritmos distribuídos requerem que um processo aja como coordenador, iniciador ou desempenhe algum papel especial.
Algoritmos de eleição são utilizados para eleger um coordenador.
Se todos os processos forem exatamente iguais, sem nenhuma característica distintiva, não haveria nenhum modo de selecionar um deles.
Consideraremos que cada processo tem um número exclusivo (por exemplo, seu endereço de rede).
Em geral, algoritmos de eleição tentam localizar o processo que tenha o número de processo mais alto e designá-lo como coordenador.
‹nº›
ALGORITMOS DE ELEIÇÃO
Vamos considerar também que todo processo sabe qual é o número de processo de todos os outros.
O que os processos não sabem é quais estão funcionando e quais estão inativos no momento considerado.
A meta de um algoritmo de eleição é garantir que, quando uma eleição começar, ela terminará com todos os processos concordando com o novo coordenador escolhido.
‹nº›
Algoritmo do Valentão
‹nº›
ALGORITMOS DE ELEIÇÃO
Algoritmo do Valentão
Quando qualquer processo nota que o coordenador não está mais respondendo às requisições, ele inicia uma eleição.
Um processo P convoca uma eleição como segue:
P envia uma mensagem ELEIÇÃO a todos os processos de números mais altos.
Se nenhum responder, P vence a eleição e se torna coordenador.
Se um dos processos de número mais alto responder, ele toma o poder e o trabalho de P está concluído.
‹nº›
ALGORITMOS DE ELEIÇÃO
Algoritmo do Valentão
A qualquer momento, um processo pode receber uma mensagem ELEIÇÃO de um de seus colegas de números mais baixos.
Quando tal mensagem chega, o receptor enviauma mensagem OK de volta ao remetente para indicar que está vivo e tomará o poder.
Então, o receptor convoca uma eleição, a menos que já tenha convocado uma.
A certa altura, todos os processos desistem, exceto um, e este é o novo coordenador.
Ele anuncia sua vitória enviando a todos os processos uma mensagem informando que a partir daquele instante ele é o novo coordenador.
‹nº›
ALGORITMOS DE ELEIÇÃO
Algoritmo do Valentão
Se um processo que antes estava inativo voltar, convoca uma eleição.
Se acaso ele for o processo de número mais alto que está executando naquele instante, ganhará a eleição e assumirá a tarefa de coordenador.
O indivíduo mais poderoso da cidade sempre ganha.
‹nº›
Algoritmo de Anel
‹nº›
ALGORITMOS DE ELEIÇÃO
Algoritmo de Anel
Diferente de alguns algoritmos de anel, esse não usa uma ficha.
Adotamos como premissa que os processos estão ordenados por ordem física ou por ordem lógica.
Quando qualquer processo nota que o coordenador não está funcionando, monta uma mensagem ELEIÇÃO que contém seu próprio número de processo e envia a mensagem a seu sucessor.
Se o sucessor tiver caído, o remetente pula o sucessor e vai até o próximo membro ao longo do anel, ou até o próximo depois deste, até localizar um processo em funcionamento.
‹nº›
ALGORITMOS DE ELEIÇÃO
Algoritmo de Anel
A cada etapa ao longo do caminho, o remetente adiciona seu próprio número de processo à lista na mensagem.
A mensagem então volta ao processo que começou tudo.
Nesse ponto, o tipo de mensagem é mudado para COORDENADOR e circulado novamente, desta vez para informar a todos quem é o coordenador (o membro da lista que tem o número mais alto) e quem são os membros do novo anel.
Quando essa mensagem circula uma vez, é removida e todos voltam a trabalhar.
‹nº›
Bibliografia
OBSERVAÇÃO:
Para mudar a imagem deste slide, selecione a imagem e exclua-a. Em seguida, clique no ícone Imagens do espaço reservado pra inserir sua própria imagem.
‹nº›
Bibliografia
Tanenbaum, A. S. & Steen, M. V., “Sistemas Distribuídos – princípios e paradigmas”, 2ª ed, Ed. Pearson, 2007.
Coulouris, G., Dollimore, J., Kindberg, T., Blair, G., “Sistemas Distribuídos – Conceitos e Projeto”, 5ª ed, Bookman, Porto Alegre, 2013.
Machado, F. B. & Maia, L. P., “Arquitetura de Sistemas Operacionais”, 4a ed, LTC Editora, Rio de Janeiro, 2012.
Silberschatz, A. & Galvin, P. B., “Sistemas Operacionais – Conceitos”, 5a ed, Prentice Hall, São Paulo, 2000.
Tanenbaum, A. S. & Woodhull, A. S., “Sistemas Operacionais – Projeto e Implementação”, 2a ed, Ed. Bookman, Porto Alegre, 2000.
Tanenbaum, A. S., “Sistemas Operacionais Modernos”, LTC Editora, Rio de Janeiro, 1995.
Tanenbaum, A. S., “Structured Computer Organization”, 3rd ed, Prentice Hall International, 1990.
Soares, L. F. G. et alii, “Redes de Computadores – Das LANs, MANs e WANS às Redes ATM”, 2a ed, Ed. Campus, Rio de Janeiro, 1995.
Tanenbaum, A. S., “Redes de Computadores”, 3a ed, Ed. Campus, Rio de Janeiro, 1997.
‹nº›
89