Relógio Lógico Relógio Lógico Relógio Físico Relógio Físico
Transcrição
Relógio Lógico Relógio Lógico Relógio Físico Relógio Físico
Relógio Lógico Relógio Lógico Algoritmo de Lamport Algoritmo de Lamport • Objetivo: Sincronização de clocks lógicos • Os tempos associados aos eventos não são necessariamente próximos ao tempo real. • Os processos executam em diferentes, cada uma com seu clock. • Os processos não precisam estar de acordo sobre o valor exato do tempo, mas sobre a ordem em que os eventos ocorrem. • Cada mensagem leva o valor do clock do transmissor. • Relação acontecimento-anterioridade: – Se a e b são eventos dentro do mesmo processo e se o evento “a” acontece antes do “b” então: C(a) < C(b) – Se a é o envio de uma mensagem para um processo e se b é a recepção desta mensagem por outro processo, então devem ser atribuídos valores a C(a) e C(b) de maneira que C(a) < C (b) máquinas • Se a mensagem traz um tempo superior ao do receptor, este adianta seu clock em uma unidade maior que o tempo recebido. Relógio Físico Relógio Físico Algoritmo Centralizado Algoritmo Centralizado • ALGORITMO DE CRISTIAN: • ALGORITMO DE BERKELEY: • Sistemas de tempo real: importante conhecer o tempo • Servidor de tempo ativo: periodicamente consulta cada máquina para saber o tempo corrente da cada uma. real dos eventos. • Existe um servidor de hora exata. Os clientes enviam mensagem ao servidor perguntando o tempo corrente e ajustam seus clocks. • PROBLEMAS: – Transmissor adiantado em relação ao servidor: não pode atrasar, pois geraria inconsistências. SOLUÇÃO: ajuste gradativo ( adiantar mais devagar). – Tempo não nulo de comunicação entre cliente-servidor. SOLUÇÃO: adicionar metade do tempo entre solicitação/resposta. • Cada máquina responde com seu tempo corrente. • Baseado nas respostas, o servidor calcula o tempo médio e informa a todas as máquinas para adiantar ou “atrasar” ( gradativamente) seus clocks. • Como o próprio servidor muda seu tempo, periodicamente o operador deve ajustá-lo manualmente. 1 Relógio Físico Exclusão Mútua Algoritmo DISTRIBUÍDO Algoritmo Distribuído • Dividem o tempo em intervalos fixos de “ressincronização” • No início de cada intervalo, cada máquina envia broadcast com seu tempo corrente. • Como os clocks são diferentes, estas mensagens não vão ser todas simultâneas. • Após enviar sua mensagem, cada máquina inicia um temporizador para receber as mensagens em broadcast das outras máquinas ( intervalo de aceitação das respostas). • Cada máquina roda um algoritmo que calcula a média dos valores de tempo de todas máquinas da rede, descartando os m valores mais baixos e mais altos. COM USO DO RELÓGIO LÓGICO • Processo deseja entrar numa RC: – envia mensagem para todos processos ( que deve confirmar o recebimento), com nome da região crítica, seu próprio número e o tempo corrente. • Processo só entra na RC se todos processos lhe dão permissão para executá-la. Exclusão Mútua Exclusão Mútua Algoritmo Distribuído Algoritmo Distribuído COM USO DO RELÓGIO LÓGICO (cont.) • Processo recebe mensagem de requisição a uma RC: – Se o receptor não está executando a RC e não deseja executála: envia OK de volta ao transmissor. – Se o receptor está executando a RC: ele não responde, e guarda a requisição em uma fila (envia OK após sair da RC). – Se o receptor deseja entrar na RC mas não o fez: compara o tempo da mensagem recebida com o que ele enviou (o seu). O valor mais baixo ganha. – Logo, se o tempo da mensagem recebida for mais baixo, o processo envia OK ao transmissor. – Se o tempo de sua própria mensagem (seu próprio tempo) for menor, o receptor coloca a requisição recebida em uma fila e não responde nada (envia OK após sair da RC). COM USO DO RELÓGIO LÓGICO (cont.) • PROBLEMAS: – Número de mensagens por entrada :2(n-1), onde n é o número de processos total do sistema. – N pontos de falha: destinatário fora do ar não responde OK. – Solução: Cada processo responder negando ou confirmando solicitação de permissão para entrar na RC. Se processo não responde após N tentativas: está fora do ar. 2 Exclusão Mútua Algoritmos de Eleição Algoritmo Distribuído COM PASSAGEM DE TOKEN • É constituído um anel lógico em software. • Cada processo conhece qual o próximo da sequência. • No início, processo “0” recebe o token e envia ao seu sucessor e assim por diante. • Quando o processo recebe o token: – Verifica se ele próprio está querendo entrar na RC. Se estiver, entra na RC e após terminá-la, envia o token ao seu sucessor. – Se não está querendo entrar na RC, passa o token para o seu sucessor. • Promovem eleição para escolha de um coordenador. • Cada processo é identificado por um número inteiro e conhece o número de identificação de todos os demais. • Processo com número de identificação mais alto é designado como coordenador. • Todos os processos do sistema devem saber quem é o novo coordenador ao terminar a eleição. Algoritmos de Eleição Algoritmos de Eleição Algoritmo do Mandão Algoritmo do Mandão • Processo P nota que o coordenador respondendo: inicia uma eleição não está • P inicia eleição: – Envia mensagem indicativa de eleição a todos processos com número de identificação superiores ao seu. • Fig 11.13 2 0 1 5 Ele içã o Eleição 7 3 – Se nenhum processo responde, P ganha a eleição e torna-se o novo coordenador. – Se um ou mais processos responderem, eles passam a controlar a eleição. – Processo com número de identificação mais alto, ganha a eleição e será o novo coordenador. 2 Eleição 4 2 6 0 O coordenador anterior está fora do ar 2 7 3 o çã ei El 0 3 7 3 5 Eleição 6 Eleição 1 5 Coordenador OK 6 0 1 4 6 4 5 2 5 OK 7 1 4 1 OK 4 6 0 7 3 Coordenador – Novo coordenador informa a todos os demais processos que é o novo coordenador. 3 Algoritmos de Eleição Algoritmo do Anel Lógico • Processos física ou logicamente ordenados: cada um conhece quem é seu sucessor. Não usa token • Processo nota que o coordenador não está respondendo: – Monta mensagem de convocação de eleição com seu próprio número e envia ao seu sucessor. – Se este estiver inativo, envia ao sucessor do mesmo e assim por diante até encontrar um processo ativo. – Este processo se repete novamente, até que a mensagem volte ao processo de origem. Cada processo coloca seu número de identificação na mensagem. – O processo com maior número de identificação será o novo sucessor. – O processo de origem envia uma outra mensagem informando o número de identificação do novo coordenador. Controle Otimista • A transação não se preocupa com conflitos. Nenhum objeto é bloqueado. • No ponto de aceitação da transação (validação), o algoritmo verifica as demais transações para ver se algum arquivo foi modificado desde o início da transação. • Caso positivo, a transação é abortada. Caso negativo, é aceita. Controle de Concorrência ALGORITMO DE CONTROLE DE CONCORRENCIA • Quando várias transações estiverem sendo executadas simultaneamente por diferentes processos, rodando em processadores diferentes, há a necessidade de mecanismos para que nenhum deles interfira no processamento do outro. • TRAVA: bloqueio de acesso a um arquivo. • O processo gerente de bloqueio rejeita todas as tentativas de bloquear arquivos já bloqueados por outros processos. • O bloqueio de acesso a um arquivo, antes do início de uma transação, garante que ele não vai ser modificado no decorrer da transação. Deteção de Deadlocks Algorimo Distribuído • Processo espera por um recurso bloqueado por outro processo: envia mensagem de sondagem para o(s) processo(s) detentor(es) do(s) recurso(s). • mensagem composta por três números: No. do processo bloqueado, No. do processo que enviou a mensagem, No. Do processo para o qual a mensagem está sendo enviada. • Mensagem chega ao destino: Receptor verifica se ele próprio está aguardando recursos de algum processo. 4 Deteção de Deadlocks Deteção de Deadlocks Algorimo Distribuído Algorimo Distribuído • Se estiver, atualiza a mensagem, mantendo o primeiro campo e substituindo os demais por seu próprio No. (origem) e pelo No. do destino. • DEADLOCK: mensagem volta à origem (ciclo). • DESFAZER DEADLOCK: – Processo que iniciou sondagem comete suicídio (0, 8, 0) Máquina 0 0 1 2 Máquina 1 (0, 2, 3) (0, 0,1) (0, 1, 2) • PROBLEMA: dois ou mais processos poderiam suicidar-se, sendo o problema resolvido com o suicídio de apenas um. 4 Máquina 2 (0, 4, 6) 6 8 3 5 (0, 5, 7) 7 – Cada processo coloca seu No. no final da mensagem. Quando a mensagem retorna ao transmissor, ele mata o processo com No. mais alto ou o convida a suicidar-se. Prevenção de Deadlocks Distribuídos Prevenção Estrutural • Cada transação leva um carimbo indicando o momento em que a transação se inicia. • WAIT-DIE – Processo está esperando por um recurso que outro processo detém: • Só poderão esperar os processos mais velhos (carimbo menor do que o do processo que ele está esperando, ou seja, que detém o recurso). • No caso inverso (processo mais jovem espera por um recurso que o mais velho detém), o processo mais jovem é assassinado. Prevenção de Deadlocks Distribuídos Prevenção Estrutural • WOUND-WAIT – Só poderão esperar os processos com carimbo maior ( mais jovem) que o processo esperado. Neste caso os carimbos decrescem ao longo da cadeia. – Processo velho deseja recurso que pertence a um mais jovem: O mais velho provoca preempção do mais jovem, cuja transação é assassinada. – Caso contrário, o processo mais jovem espera a liberação do recurso detido pelo mais velho. – Neste algoritmo, na cadeia de processos esperando, os carimbos vão sempre crescer, tornando impossível a formação de ciclos(deadlocks). 5