SISOP - respostas lista 2

Prévia do material em texto

<p>Sistemas Operacionais II Exercícios de Acompanhamento 1 Exercícios de Acompanhamento 2 Exercícios de Acompanhamento 3 Exercícios de Acompanhamento 4 Exercícios Área 2 Sistemas Operacionais 1</p><p>Exercícios de Acompanhamento 1 [Questão 1] Discorra sobre programação paralela e concorrente, e aplicações multi-thread, paralelas e distribuídas. Cite e comente duas das principais dificuldades na implementação de aplicações concorrentes. Programação paralela e concorrente são dois conceitos distintos. Na programação paralela temos a execução de tarefas FISICAMENTE ao mesmo tempo; como, por exemplo, dois processos executando simultaneamente em processadores paralelos. A programação concorrente, por sua vez, conta com tarefas executando LOGICAMENTE ao mesmo tempo. Isso significa que não necessariamente há paralelismo de fato. Falando agora sobre aplicações, podemos ter aplicações multi-thread, paralelas e distribuidas. Nas aplicações multi-thread normalmente há tarefas sendo executadas em mais de uma thred, normalmente compartilhando a CPU, com a finalidade de aproveitar melhor o uso da CPU e diminuir momentos de ócio. Aplicações paralelas, por sua vez, são aplicações que contam com processos executando fisicamente ao mesmo tempo em processadores diferentes; esse tipo de aplicação é particularmente útil para resolver um problema mais rápido ou usar uma abordagem "dividir para conquistar" e resolver um problema maior diminuindo sua complexidade. Por fim, aplicações concorrentes se referem a aplicações envolvem processos em diferentes hosts que se comunicam através de uma rede; essas aplicações são úteis para distribuir trabalho ou fazer computação paralela em larga escala sobre a rede. Duas dificuldades na implementação de aplicações concorrentes são garantir a consistência de dados e evitar deadlocks e starvation. No primeiro caso, é fundamental garantir que a intercalação de processos gere um estado conscistente, ou seja, o resultado obtido ao final da execução dos processos de forma concorrente deve ser igual a algum dos resultados obtidos ao se executar os processos de forma sequencial. segundo problema, por sua vez, envolve evitar que os processos se bloqueem mutuamente e nenhum processo possa ser executado; ou que um processo acabe Exercícios de Acompanhamento 1 1</p><p>ficando sempre bloqueado esperando outros serem executados e nunca consiga acesso ao recurso desejado. [Questão 2] Discorra sobre a necessidade de sincronização de processos e explique quais as propriedades que sistemas concorrentes e distribuídos devem satisfazer. A sincronização de processos é essencial para coordenar a execução de ações entre processos, tanto em memória compartilhada quanto em memória distribuída e garantir que duas situações sejam verdadeiras: exclusão mútua e condição. Sistemas concorrentes e distribuídos deve garantir duas propriedades: Safety e Liveness. Safety diz respeito a um programa nunca entrar em um estado ruim, ou seja, em um estado inconsistente. Já liveness siginifica que um programa chegará a um estado bom, ou consistente. Essas propriedades devem ser cumpridas em todas as execuções do programa. [Questão 3] Comente as principais características das implementações baseadas em software e hardware para o operador de exclusão mútua. Em particular, quais os motivos que tornam implementações baseadas em software pouco apropriadas para uso em programação concorrente? A implementação de operador de exclusão com apoio de hardware é baseado habilitar/desabilitar interrupção e uso de instruções atômicas, como test-and-set e o swap. Já a implementação de operador de exclusão mútua baseada puramente em software não faz uso de serviços providos pelo kernel ou instruções especiais do processador para controlar os processos e seus acessos a recursos. A principal vantagem dessa abordagem é garantir uma solução independente de sistema operacional. No entanto, suas principais desvatagens envolvem o aumento da complexidade do programa, diminuição do desempenho e a introdução de busy- waiting, ou seja, a tarefa ocupa o processamento, mas não faz algo de fato útil, pois Exercícios de Acompanhamento 1 2</p><p>está esperando ser desbloqueada para continuar sua execução. São essas desvantagens que tornam o emprego de implementações puramente em software pouco apropriadas para programação concorrente. [Questão 4] Idealize (de forma breve) um sistema simples com múltiplos processos concorrentes com necessidade de controle de acesso a um recurso comum, e explique como o conceito de semáforos contadores pode ser utilizado para resolver o problema de acesso a seção crítica nesse sistema. Em particular, comente por que o uso de semáforo contador é mais conveniente no sistema idealizado em comparação ao uso de semáforo binário ou mutex. sistema possui um semáforo que é inicializado com n, sendo n o valor que indica quantos processos podem acessar esse recurso ao mesmo tempo. Dessa forma, um processo, ao chegar em sua seção crítica e com a disponibilidade de uma "vaga" livre para o acesso ao recurso ou seja com o valor do semáforo maior que 0 bloqueia uma das "vagas" disponíveis decrementa o semáforo. Terminada a seção crítica, o recurso é liberado - o semáforo é incrementado. Nesse sistema, o uso de semáforo contador é mais conveniente que o mutex e o semáforo binário, pois, nesse caso, deseja-se permitir o acesso de múltiplos processos a um recurso comum e, tanto o mutex quanto o semáforo binário, tratam-se de um caso onde apenas um processo tem acesso ao recurso por vez. [Questão 5] que são e para que servem as primitivas wait e signal? Enumere e explique as estratégias de sinalização empregadas na implementação de monitores. As primitivas signal e wait são primitivas que permitem o acesso as variáveis de condição dos monitores. No wait, o processo bloqueia a variável de condição, retirando-o do monitor e o adicionando no final da fila associada à variável de condição. Exercícios de Acompanhamento 1 3</p><p>signal, por sua vez, acorda um processo da fila associada à condição que recebeu o sinal. Se a fila estiver vazia, o signal é perdido. As estratégias de sinalização nos monitores são: Signal and continue: o processo sinalizador continua sua execução e o sinalizado passa para a fila de entrada do monitor Signal and wait: o processo sinalizador vai para o final da fila de entrada do monitor e o processo sinalizado inicia sua execução Signal and urgent wait: o processo sinalizador vai para o inicio da fila de entrada do monitor e o processo sinalizado inicia sua execução Exercícios de Acompanhamento 1 4</p><p>Exercícios de Acompanhamento 2 [Questão 1] Considere a especificação de um sistema para troca de mensagens entre pessoas, usando uma arquitetura na qual uma aplicação servidor coordena a troca de mensagens, e várias aplicações clientes interagem com o servidor para envio e recebimento de mensagens. Cada aplicação executa em um dispositivo diferente. Para viabilizar a troca de mensagens entre as aplicações cliente e servidor, a implementação desse sistema deverá usar um ou mais mecanismos para comunicação inter-processo. Explique por que mecanismos de pipe e de memória compartilhada não podem ser usados na implementação da comunicação inter-processos nesse sistema. Para a implementação desse sistema, qual (ou quais) mecanismos de IPC seriam mais apropriados? Justifique. Mecanismos como pipe e memória compartilhada não são adequados para esse sistema, pois o sistema envolve comunicação entre processos em diferentes máquinas, ou seja, não existe uma memória compartilhada ou processos relacionados, no caso do pipe. Dessa forma, para esse sistema, seria mais apropriado o uso do modelo send e receive, que é usado em sockets, por exemplo. [Questão 2] Defina comunicação síncrona e assíncrona de processos. É possível implementar comunicação assíncrona sem uso de mecanismos de buferização? Por quê? Quanto à comunicação síncrona, discorra um cenário simples na qual ela poderia levar a deadlock. Exercícios de Acompanhamento 2 1</p><p>A comunicação é dita síncrona se tanto send quanto receive são bloqueantes. A comunicação assíncrona, por sua vez, trata-se de quando pelo menos uma das primitivas é não bloqueante, embora, na prática, a primitiva send é não bloqueante e a receive é bloqueante. Uma implementação sem buferização necessita de um send bloqueante, o que torna impossível fazer uma implementação de comunicação assíncrona sem mecanismos de bufferização. Quanto a comunicação síncrona é possível causar um deadlock da forma: temos dois processos P1 e P2 que querem se comunicar e os dois chamam um receive bloqueante. Assim, ambos ficam esperando o send do outro processo e causamos um deadlock. [Questão 3] Considere a especificação de um sistema para o envio de arquivos de um computador a outro, através da internet. sistema será formado por uma aplicação servidor, que aguarda o recebimento do arquivo, e uma aplicação cliente, que faz o envio do arquivo ao servidor. Quais as três dificuldades adicionais que o programador desse sistema enfrentará ao implementar essa aplicação usando o protocolo UDP ao invés do TCP? As três dificuldades são: As mensagens no UDP tem um tamanho limitado e, portanto, pode ser necessário e envio de múltiplos datagramas em um request As mensagens não tem garantia de entrega, o que faz com que o programador precise implementar todas as garantias necessárias em nível de aplicação Por ser necessário implementar garantias dentro da aplicação, o código se torna mais difícil de ser implementado e mais complexo [Questão 4] Considere um sistema para o envio de arquivos entre dois dispositivos que se comunicam Exercícios de Acompanhamento 2 2</p><p>pela internet. o sistema é formado por duas aplicações A e B. A aplicação A envia o arquivo dividindo o mesmo em blocos, e enviando cada bloco para a aplicação B, usando UDP. Para a implementação desse sistema, pode-se imaginar o envio dos blocos dos arquivos entre A e B usando as semânticas at most once, at least once, e exactly once. Qual dessas semânticas é a mais apropriada para a implementação desse sistema? Cite os problemas que as demais semânticas podem trazer para a implementação operação do sistema. Por se tratar do envio de um arquivo, onde mensagens duplicadas podem ter efeitos indesejados, a semântica mais apropriada seria a semantica exactly once. Na semântica at most once, não há garantia de envio dos pacotes, o que não é desejável. Já na semântica as least once, pode haver o envio de pacotes duplicados. Isso é um problema, pois o arquivos é dividido em vários pacotes, então receber um pacote duplicado compromete a reorganização do arquivo no destino. [Questão 5] Na chamada remota de procedimentos, discorra sobre as funções do stub no programa cliente e no programa servidor. Cite e comente alguns dos problemas que podem ocorrer durante a chamada remota de procedimentos. As funções do stub no programa cliente incluem: Executar o marshalling/unmarshalling dos argumentos que saem/vão para a aplicação Envio de uma requisição ao processo servidor Bloqueio enquanto espera a resposta da requisição Já as funções do stub no programa servidor incluem: Exercícios de Acompanhamento 2 3</p><p>Selecionar qual procedimento stub executar, usando um dispatcher e o ID da requisição Faz o unmarshalling/marshalling dos argumentos recebidos/resultados obtidos Faz a chamada do procedimento escolhido e envia a mensagem para o processo cliente Alguns dos problemas que podem acontecer durante uma chamada remota de procedimentos, incluem: Mensagens, tanto requests quanto replys, podem ser perdidas Servidor ou cliente podem pendurar e não é possível saber em que ponto chegaram na execução A rede pode colapsar e haver perda de pacotes Exercícios de Acompanhamento 2 4</p><p>Exercícios de Acompanhamento 3 1. Considere a especificação de um sistema que processa transações de forma distribuída em uma rede local. Esse sistema possui um app cliente e outro servidor. o app cliente é responsável por iniciar as transações, e executará em vários computadores, com computadores entrando e saindo do sistema constantemente (via instalação/desinstalação do app). o app servidor é responsável por receber e registrar as transações, e executará em apenas um computador. servidor deve manter as transações em uma lista, na mesma ordem em que foram iniciadas pelos clientes. Por uma questão de projeto, decidiu-se que a ordenação será feita pelo horário em que foi iniciada, de acordo com o relógio do cliente. Para lidar com clock skew e clock drift, o sistema deverá contar com uma funcionalidade para sincronizar periodicamente o relógio dos computadores participantes do sistema. Que problema o uso do Algoritmo Berkeley para a sincronização dos relógios pode causar na operação consistente desse sistema? Tolerância a falhas. Uma máquina precisa ser escolhida como líder para fazer a sincronização. Nesse sistema, o servidor seria escolhido, já que os clientes podem ou não ficar ativos. Porém, o servidor se torna um ponto único de falhas e se, falhar fudeu. A precisão depende de um RTT máximo nominal. Se a rede estiver muito congestionada, o desempenho e precisão será afetado. 2. Seja L(x) o timestamp do evento X pelo relógio lógico de Lamport, e V(x) o relógio vetorial do evento X. Considere agora: "Dados dois eventos ei e ej, se V(ei) V (ej) então L(ei) Essa afirmação é verdadeira? Justifique. Por que não é possível afirmar que, se L(ei) então V(ei) <V (ej)? Exercícios de Acompanhamento 3 1</p><p>A afirmação é verdadeira, pois se é possível determinar que V(ei) < V(ej), significa que ei aconteceu antes de ej e, por definição, se um evento ei acontece antes de ej, L(ei) < L(ej). Por outro lado, o contrário não é verdadeiro, ou seja, se L(ei) < L(ej), não é possível determinar se o evento ei aconteceu antes de ej, eles podem ser concorrentes. Dessa forma, não se pode afirmar que V(ei) < V(ej). 3. No algoritmo valentão para eleição de líder em sistemas distribuídos, por que a premissa de entrega confiável de mensagens é importante? Qual a vantagem que se assumir que cada processo sabe quais outros processos tem identificador maior? algoritmo de eleição do valentão tem como uma das etapas, uma máquina iniciar a eleição e ser apenas respondida caso alguma outra máquina tenha um PID maior. Dessa forma, o não recebimento de mensagens implica que a máquina pode se eleger como novo líder. Por esse, motivo, é necessário garantir que as mensagens tenham sido entregues e que o não recebimento de um mensagem de resposta implique EXCLUSIVAMENTE que a máquina tem um PID menor do que a máquina que iniciou o processo de eleição. Ao saber quais processos tem um PID maior, o processo que iniciou a eleição sabe que não assumirá como líder e seu papel, então, é aguardar o encerramento da eleição. 4. Considere um sistema distribuído de streaming de video com um processo produtor do vídeo e vários processos consumidores. o streaming é entregue em um mecanismo baseado em mensagens, com cada mensagem contendo um frame do vídeo. A perda de frames é tolerada pelos consumidores. Qual mecanismo de comunicação em grupo é o mais apropriado para implementar esse sistema, entre multicast básico, confiável e ordenado? Justifique. Considerando uma implementação do sistema usando multicast ordenado, discorra sobre qual seria o tipo de ordenação mais apropriado para a implementação. mecanismo de comunicação mais adequado é usando o grupo aberto usando a confiabilidade 0-confiável, já que é tolerada a perda de frames pelos consumidores. Se fosse utilizado um sistema com multicast ordenado, o tipo de ordenação mais Exercícios de Acompanhamento 3 2</p><p>apropriado seria a ordenação causal, para garantir que os frames que acontecem antes sejam entregues antes. 5. Cite e discorra sobre os principais problemas dos algoritmos baseados em modelo cliente-servidor, em tokens de permissão e e fila distribuída, e comente sobre as características de cada um quanto ao ordering, client delay e synchronization delay. No algoritmo baseado no modelo cliente-servidor, o principal problema está na existência de um ponto único de falha. Se o processo controlador falhar, é necessário a eleição de um novo controlador. No modelo cliente-servidor, não é satisfeita propriedade de ordering; o client delay é dado pelo round-trip time do request e do grant (na entrada na SC) e, no caso de release assíncrono, não há delay (na saída da SC); o syncronization delay se dá com uma mensagem de release e de grant. Considerando o algoritmo baseado em tokens de permissão, o principal problema está no consumo de bandwidth, já que, mesmo que nenhum processo queira transmitir uma mensagem, o token deve ser repassado. Nesse algortimo também não é respeitado o ordering, já que um processo pode acabar recebendo o token antes devido a ordem do anel; o client delay pode ser entre 0 e N mensagens, para a entrada na SC, e de 1 mensagem para a saída da SC; o syncronization delay é entre 1 e N mensagens. Por fim, no algoritmo baseado em fila distribuída, os principais problemas incluem a complexidade da implementação do algoritmo e a grande quantidade de troca de mensagens necessária. Nesse algoritmo é garantido o ordering através de relógios lógicos; o client delay é o round trip time; o syncronization delay é o tempo de transmissão de uma mensagem. 6. Cite e discorra sobre as quatro condições que devem ser satisfeitas simultaneamente para a ocorrência de deadlock. A satisfação dessas condições simultaneamente garante a ocorrência de deadlocks em sistemas que possuem múltiplas instâncias de um mesmo recurso? Justifique. Qual dessas condições não é necessariamente satisfeita no caso de um deadlock fantasma? Por quê? As quatro condições necessárias são: Exercícios de Acompanhamento 3 3</p><p>Exclusão somente um processo pode usar o recurso em um dado momento Segura/espera na posse de um recurso, um processo espera para alocar outro recurso Recurso não preemptível uma vez que um processo seja alocado, não é possível retirar o recurso Espera circular - uma sequência de processo onde um processo têm pelo menos um recurso que é necessário para o outro processo. A satisfação das condições garante o deadlock para múltiplas instâncias de um mesmo recurso no caso em que todos os recursos estejam alocados. Porém, enquanto tiver um recurso disponível, é possível evitar o deadlock. No caso de um deadlock fantasma, condição de espera circular não necessariamente é satisfeita, já que atrasos na computação dstribuída podem fazer com que detecte a alocação de um recurso por um processo que, na verdade, não existe. Exercícios de Acompanhamento 3 4</p><p>Exercícios de Acompanhamento 4 1. Equivalência serial é um critério para execução concorrente correta de transações. Equivalência serial corresponde a uma intercalação de operações na qual a combinação dos efeitos é o mesmo que seria obtido caso as transações tivessem sidos executadas uma de cada vez, em uma determinada ordem. Considere duas transações T e U abaixo: T: y=read(j); x=read(i); write(k,17); U: write(j,10); z=read(k); write(i,20); Apresente uma possível intercalação de operações das transações T e U que satisfaça a propriedade de equivalência serial. Explique a sua resposta. Considerando os pares de transações conflitantes, temos: y = read(j) e write(j, 10) X = read(i) e write (i, 20) write(k, 17) e Para garantir a equivalência serial, é necessário que os pares conflitantes sejam executados na mesma ordem nas duas transações Dessa forma, uma intercalação possível é: y = read(j) write (j, 10) X = read(i) write(k, 17) Z = read(k) Exercícios de Acompanhamento 4 1</p><p>write(i, 20) 2. No modelo de replicação ativa, as requisições de operações sobre os gerenciadores de réplicas devem ser feitas utilizando qual tipo de multicast? Explique a sua resposta. Multicast precisa ter garantia de entrega de mensagens, com entrega em ordem, porque a mensagens devem ser entregues para todos os processo, para garantir a consistência, e devem ser ordenadas para que os resultados sejam sempre os mesmos. 3. Alice e Bob desejam obter as propriedades de confidencialidade e integridade em sua comunicação. Explique como essas partes poderiam atingir essas objetivos utilizando a) criptografia simétrica b) criptografia assimétrica c) um protocolo híbrido de criptografia. Quais as vantagens e desvantagens de cada abordagem? Uma criptografia simétrica é bem mais simples de ser implementada, porém a distribuição e armazenamento é difícil. A criptografia assimétrica, por sua vez, é bem mais custosa de ser implementada, mas tem distribuição e armazenamento mais fácil. A confidencialidade pode ser atingida cifrando a mensagem, assim protegendo a mensagem durante sua transmissão. A ideia é que apenas quem tem a chave correta pode codificar e decodificar a mensagem. Normalmente, é utilizado um algoritmo híbrido, que usa uma criptografia assimétrica para negociar uma chave de sessão simétrica usada para cifrar os dados. Já a integridade pode ser resolvida com o uso de uma assinatura digital. Ela serve para garantir a autenticidade do documento. 4. Explique os diferentes tipos de interfaces existentes em um sistema Exercícios de Acompanhamento 4 2</p><p>computacional e a relação entre essas interfaces e diferentes tipos de virtualização. Há três interfaces principais: Conjunto de instruções ISA interface básica entre hardware e software, ela inclui instruções de máquina aceitas pelo processador e operações de acesso aos recursos de hardware. Chamadas de sistema interface que contém o conjunto de operações oferecidas pelo núcleo do sistema operacional aos processos. Nessa interface pode fazer o acesso aos periféricos, memória e instruções privilegiadas do processador. Chamadas de biblioteca encapsulam um conjunto de funções para serem usadas em programas, muitas sendo chamadas do SO. Já com relação as virtualizações, temos: Emulação de hardware o hipervisor divide o hardware do sistema operacional convidado e suas aplicações para uma plataforma, que são executadas sobre outra plataforma distinta. Emulação de sistema operacional o sistema operacional convidado e suas aplicações são executadas sobre outro sistema operacional Otimização dinâmica as instruções de máquina são traduzidas durante a execução em instruções mais eficientes para a mesma plataforma. Replicação de hardware há várias instância virtuais de um hardware real, cada uma das instâncias executando seu próprio sistema operacional e suas aplicações Exercícios de Acompanhamento 4 3</p><p>Exercícios Área 2 Sincronização de relógios físicos 1. Descreva brevemente o que são e como ocorrem os problemas de clock skew e clock drift, citando um exemplo prático onde cada um destes problemas pode ocorrer. clock skew se trata da diferença instantânea entre leitura de dois relógios. Ela ocorre entre quaisquer dois relógios físicos, já que relógios físicos enfrentam problemas de clock drift. clock drift, por sua vez, ocorre em relógios com cristais, já que os osciladores estão sujeitos a variações físicas, mudanças de temperatura etc. Esse problema é muito comum com relógios de quartz de cristal. 2. Quais são os dois principais modos de sincronização de relógios físicos? Descreva formalmente cada um. Os dois principais modos de sincronização são externa e interna. Na sincronização externa, os relógios são sincronizados com relação a uma fonte externa. Já na sincronização interna, os relógios são ajustados em função dos relógios dos outros. 3. Descreva o funcionamento dos algoritmos de sincronização servidor passivo (Cristian, 1989) e servidor ativo (Berkeley, 1989) vistos em aula, discutindo em que cenário cada um deve ser aplicado. algoritmo de sincronização servidor passivo utiliza um servidor de hora para sincronizar computadores. Uma máquina solicita a hora para o servidor, que fornece sua hora local. A nova hora do cliente passa ser a hora oferecida pelo servidor somada a média da diferenças das horas de solicitação e recebimento da hora do servidor. Já no algoritmo de sincronização servidor ativo, a sincronização é interna entre um grupo de máquinas. Uma das máquinas é escolhida como servidor e pergunta, periodicamente, a hora aos clientes. Calcula a média dos valores obtidos e informa a difernça entre a média e os relógios locais. Assim, as máquinas clientes ajustam seu relógio com base na diferença respondida. Exercícios Área 2 1</p><p>4. Quais as vantagens na utilização de uma estrutura hierárquica para sincronização de relógios, como a apresentada pelo NTP? As vantagens da utilização de uma estrutura hierárquica incluem a escalabilidade do projeto para grandes sistemas distribuídos, o oferecimento de um que pode oferecer uma resposta rápida e precisa aos clientes e um sistema mais tolerante a falhas. 5. Um cliente tenta sincronizar com um servidor de horário. Ele registra os tempos de ida e volta e os timestamps devolvidos pelo servidor na tabela abaixo. Qual destes tempos ele deve utilizar para definir o seu relógio? Para que horas ele deve defini-lo? Estime a precisão do ajuste em relação ao relógio do servidor. Se é sabido que o tempo entre o envio e recepção de uma mensagem no sistema em questão é de pelo menos 8ms, suas respostas mudariam? Tempo de ida e volta (round-trip) [ms] Hora (hr:min:seg.miliseg) 22 10:54:23.674 25 10:54:25.450 20 10:54:28.342 Um RTT menor implica em uma precisão maior, logo a melhor escolha seria o tempo oferecido com o RTT de 20ms. Usando o Algoritmo de Cristian, a nova hora seria calculada com o tempo retornado pelo servidor somado ao tempo de espera desde o envio até o recebimento da requisição sobre 2. Logo, o horário seria 10:54:28.342 + 20/2 = 10:54:28.352. A precisão é do RTT utilizado sobre 2 para mais ou para menos. Não mudaria, pois o cálculo já é feito usando um valor superior a 8ms. 6. Um servidor NTP B recebe uma mensagem de um servidor A às 16:34:23,480, levando um timestamp de envio dessa mensagem igual a 16:34:13,430. A mensagem é respondida pelo servidor B, e o servidor A recebe essa resposta às 16:34:15,725, com timestamp de envio igual a 16:34:25,7, além dos timestamps de envio e recebimento da Exercícios Área 2 2</p><p>mensagem anterior. Estimar o offset entre B e A e a precisão da estimativa. onde oi = (Ti-2 - Ti)/2 oi = (16:34:23,480 - 16:34:13,430 + 16:34:25,7 - 16:34:15,725) + (9,975 - 10,05)/2 0.0375 = 19.9875 S De acordo com o que foi visto em aula, se for uma LAN, a precisão é de 1ms. Caso, contrário a precisão é de algumas dezenas de ms. 7. Utilizando o algoritmo de Berkeley, calcular a nova hora para um grupo de clientes da tabela abaixo conectados ao servidor com hora 15:55:4,200. Cliente # Hora (hr:min:seg.miliseg) Cliente 1 15:55:4,356 Cliente 2 15:55:4,100 Cliente 3 15:55:4,100 Cliente 4 15:55:4,152 Cliente 5 15:55:3,100 Servidor: 15:55:4,200 (S) 15:55:4,200 - 15:55:4,200 = 0 (C1) ) 15:55:4,356 - 15:55:4,200 = 156 ms (C2) 15:55:4,100 - 15:55:4,200 = -100 ms Exercícios Área 2 3</p><p>(C3) 15:55:4,100 - 15:55:4,200 = -100 ms (C4) 15:55:4,152 - 15:55:4,200 = -48 ms (C5) = 1100 ms 1 valor muito diferente média = (156 - 100 - 100 - ms (S): => 15:55:4,177 (C1): -23 (156) = -179 ms 15:55:4,177 (C2): -23 - (-100) = ms => 15:55:4,177 (C3): -23 (-100) = ms 15:55:4,177 (C4): -23 15:55:4,177 (C5): - 23 (-1100) = 1077 ms => 15:55:4,177 Relógios lógicos e algoritmos de eleição: 1. Qual é a definição de relógio lógico e porque ele é importante para o sincronismo em sistemas distribuídos? Um relógio lógico é uma forma de capturar numericamente uma relação de happened before, ou seja, uma forma de atribuir um valor à eventos que defina qual evento aconteceu antes. Eles são importantes para sincronismo em sistemas distribuídos, pois é impossível sincronizar perfeitamente relógios físicos em sistemas distribuídos e, dessa forma, pode não ser possível ordenar pares de evento utilizando esse método. 2. Descreva sucintamente a relação happened-before definida por Leslie Lamport e como esta relação pode ser "capturada" numericamente. A relação de happened-before é a relação de um evento a ocorrer antes de b. Dessa forma, isso pode ser quantificado com o uso de contadores que atualizam monotonicamente da forma: se a aconteceu antes de b, L(a) < L(b). Exercícios Área 2 4</p><p>3. Qual é a principal deficiência encontrada no relógio lógico de Lamport e como ela pode ser resolvida? Represente graficamente um exemplo de situação onde ela pode ocorrer. A principal deficiência do relógio lógico de Lamport é que se a < (happened before) b, L(a) < L(b). Porém, o contrário não é necessariamente verdadeiro. Um exemplo onde isso é claro é o exemplo: 1 2 P3 a b 3 4 . Tempo físico C d m2 1 5 P3 e f Embora L(e) < L(b), os dois eventos são concorrentes. Uma forma de solucionar isso é usar relógios vetoriais. 4. Considere a ocorrência de eventos em três processos distribuídos, P1, P2 e P3. Apresente o valor do relógio vetorial marcado em cada processo na ocorrência de cada evento no diagrama abaixo. o valor inicial dos relógios vetoriais de P1, P2 e P3 são L1=(6,2,0), L2=(2,7,0) e L3=(0,1,2), respectivamente. Valores iniciais e11 e13 m1 m4 m5 L3=(0,1,2) P3 e31 e32 e33 e11 (7, e12 (8,2,3) Exercícios Área 2 5</p><p>e13 (9, 11, 3) e21 (2, 8, 0) e22 (7, 9, 0) e23 (7, 10, 0) e24 (7, 11, 0) e25 (7, 12, 6) e31 (0, 1, 3) e32 (0, 1, 4) e33 (7, 10, 5) e34 (7, 10, 6) 5. Qual é a principal desvantagem no uso do algoritmo valentão (bully) em relação ao algoritmo em anel? Cite um exemplo de cenário de pior caso na troca de mensagens decorrida pela falha do coordenador. A principal desvantagem do algoritmo do valentão é a sua complexidade. Como o algoritmo assume que os processos podem falhar a qualquer estágio da eleição, é necessária a implementação de diversos timeouts para a detecção de falhas, além de implementar uma entrega confiável de menagens. Comunicação em grupo 1. Cite dois cenários práticos reais onde a comunicação de grupo ocorre. Exponha a principal vantagem na utilização deste tipo de comunicação em cada um dos casos selecionados. A comunicação em grupo pode acontecer em aplicações como Dropbox ou WhatsApp, por exemplo. A comunicação em grupo permite que certas máquinas consigam se comunicar e manter atualizadas dentro daquele grupo em específico. 2. Explique se o algoritmo para multicast confiável sobre IP multicast funciona para grupos abertos assim como para grupos fechados. Dado qualquer algoritmo para grupos fechados, como, Exercícios Área 2 6</p><p>de maneira simples, podemos derivar um algoritmo para grupos abertos? Exclusão mútua 1. Quais são as três propriedades básicas de algoritmos de exclusão mútua? Explique cada uma delas, elencando sua importância durante o processo de divisão de tarefas em sistemas distribuídos. As três propriedades são: Safety deve ter no máximo um processo por vez na sessão crítica Liveness os pedidos para a entrada e saída na sessão crítica devem ter sucesso Ordering se um pedido para entrar na sessão crítica aconteceu antes de outro, então a entrada na sessão crítica deve respeitar essa ordem 2. Adapte o algoritmo centralizado de exclusão mútua para lidar com a falha de qualquer cliente (em qualquer estado), assumindo que o servidor está funcionando corretamente e dado um detector de falhas confiável. Comente se o sistema resultante é tolerante a falhas. o que aconteceria se um cliente que possui o token é injustamente suspeito de ter falhado? Troca de mensagem 'are you alive?' Se não responder inativo; libera os recursos O sistema ainda não seria tolerante a falhas, pois o servidor ainda é um ponto único de falha. Se um token é injustamente suspeito de ter falhado, ele perderá injustamente seus recursos, afetando a propriedade de não preempção. Deadlocks Exercícios Área 2 7</p><p>1. Qual é a definição de deadlock e quais os principais casos onde eles ocorrem? Cite condições que levem a ocorrência de deadlocks. Deadlock é uma situação onde um processo fica bloqueado permanentemente esperando pela liberação de um recurso. principal caso de ocorrência de deadlock se dá na semântica bloqueante do send/receive. Um exemplo comum é quando dois processos mandam um para o outro um send ou um receive. 2. Quais as principais formas de tratamento de deadlocks? Para tratar um deadlock, a estratégia costuma ser quebrar pelo menos uma das quatro situações que devem acontecer simultaneamente para gerar um. Dentre as principais formas de tratar um deadlock, temos: ignorar, prevenir que uma das quatro situações aconteça por definição do sistema, evitar o deadlock antes que ele ocorra ou detectar e recuperar o sistema quando um deadlock ocorrer. 3. A sua empresa está construindo uma rede de computadores e você foi chamado para desenvolver um esquema para lidar com o problema de deadlocks. a) Você usaria um esquema de detecção de deadlocks ou um esquema de prevenção de deadlocks? A decisão depende de qual tipo de sistema será construído, pois ambas estratégias possuem vantagens e desvantagens. Um sistema de prevenção de deadlocks é vantajoso por não permitir que deadlocks ocorram na própria construção do sistema. Porém, criar um sistema com prevenção de deadlock pode ser muito complexo, dependendo das características. Escolher a detecção, por outro lado, também tem seus desafios, pois detectar um dealock em sistemas distribuídos não é tão simples, ainda mais levando em consideração a existência de deadlocks fantasmas. Porém, ao detectar o deadlock, quebrar o ciclo em grafo não é tão complicado. b) Se você tivesse que usar um esquema de prevenção de deadlocks, qual você usaria? Explique sua escolha. Em ambas as estratégias, wound-wait e wait-die, o processo mais novo é abortado, com a intenção de diminuir os prejuízos. Porém, no wound-wait o processo mais novo é Exercícios Área 2 8</p><p>reiniciado enquanto no wait-die, o processo mais novo é morto. A estratégia de wound- wait parece menos drástica, já que o processo não é encerrado, além de oferecer, conforme os processos envelhecem, um tempo médio de espera menor. Dessa forma, parece ser uma boa estratégia a ser adotada. c) Se você tivesse que usar um esquema de detecção de deadlocks, qual você usaria? Explique sua escolha. A escolha, em geral, melhor para detecção de deadlocks costuma ser o esquema distribuído. Isso, porque, o esquema centralizado oferece várias desvantagens como baixa escalabilidade, ponto único de falha e trade-off sobre frequência de mensagens. Essas desvantagens costumam superar a maior complexidade de gerenciamento do esquema distribuído. 4. Considere abordagem de detecção de deadlocks centralizada e totalmente distribuídas. Compare os dois algoritmos em termos de complexidade de mensagens. Em um algoritmo centralizado, é necessária a construção de um grafo global no processo coordenador. Isso envolve troca de mensagens com os participantes com uma frequência que pode variar de a cada atualização para apenas quando demandado pelo coordenador. Em uma abordagem distribuída, por sua vez, a troca de mensagem é feita através de probes (para detecção de deadlock). Essa mensagem é encaminhada para seu sucessor e, caso volte a quem inicalizou a processo de detecção, um deadlock é identificado. No caso do algoritmo centralizado, as mensagens tendem a ser mais complexas, já que precisa ser enviada uma mensagem para compor um grafo, com as atualizações do grafo. No caso distribuído, a mensagem pode ser muito simples, já que basta que ela volte a origem para que o deadlock seja detectado. Transações 1. Quais as principais diferenças entre transações e os mecanismos de sincronização? Cite os três problemas atendidos Exercícios Área 2 9</p><p>por transações, bem como exemplos de cenários onde problemas de transações podem ocorrer. A principal diferença é que os mecanismos de sincronização atendem somente o problema de acessos concorrentes. Além disso, nas transações, há a inclusão do conceito de roll back, ou seja, ações realizadas de forma não adequada podem ser desfeitas. Os três problemas atendidos por transações são: Tratamento de acessos concorrentes, ou seja, acesso de múltiplos clientes Tratamento de falhas lógicas em cado de objetos que devem ser persistente Tratamento de falhas de hardware Um exemplo clássico onde problemas de transação podem ocorrer são operações bancárias de transferência de fundos. Isso, porque, há duas operações em uma transferência: a retirada do dinheiro da conta A e o depósito do dinheiro na conta B. As duas operações devem ocorrer de forma atômica. 2. Equivalência serial é um critério para execução concorrente correta de transações, que corresponde a uma intercalação de operações na qual a combinação dos efeitos é o mesmo que seria obtido caso as transações tivessem sido executadas uma de cada vez, em uma determinada ordem. Considere duas transações T e U abaixo: T: write(k,18); y=read(j); x=read(i); U: write(j,23); z=read(k); write(i,17); Apresente duas possíveis intercalações que satisfaçam a propriedade de equivalência serial Primeiro, é necessário determinar os pares de transações conflitantes write(k, 18) e Z y = read(j) e write(j, 23) X = read(i) e write(i, 17) Exercícios Área 2 10</p><p>Para garantir a equivalência serial, é necessário que os pares executem na mesma ordem nas duas transações Intercalação possível 1 write(k,18) y = read(j) write(j, 23) Z read(k) X = read(i) write(i, 17) Intercalação possível 2 write(j, 23) Z read(k) write(k, 28) y = read(i) write(i, 17) Replicação 1. o que é replicação? Cite 3 exemplos de aplicação de replicação com o intuito de melhorar alguma característica de um sistema. Replicação é a manutenção de várias réplicas dos dados ou serviços em vários computadores distribuídos. Três exemplos de aplicação são o Dropbox, o Twitter e o Youtube. 2. Explique a diferença entre linearizability e consistência sequencial e por que o último é de implementação mais prática de maneira em geral. Tanto linearizability quanto sequential consistency tem como um de seus critérios que a série de operações intercaladas deve atender a especificação de uma única cópia Exercícios Área 2 11</p><p>correta. A diferença está, então, no segundo critério: na linearizability, a intercalação deve ser consistente com os tempos reais que as operações ocorreram na execução; esse critério é mais relaxado no sequential consistency, onde a intercalação deve ser consistente com a oderm do programa executado por cada cliente. De forma geral, opta-se pelo uso de consistência sequencial, porque a linearizability adiciona a noção de tempo real, o que é muito difícil de ser obtido na prática em sistemas distribuídos. 3. Explique por que permitir que backups processem operações de leitura leva a execuções sequencialmente consistentes, ao invés de linearizáveis, em um sistema de replicação passiva. Podemos garantir, em sistema de replicação passiva, execuções sequencialmente consistentes, pois o resultado obtido na leitura será consistente, ou seja, o resultado obtido é um resultado possível ao se executar os processos em serialmente em alguma ordem. Porém, não é possível garantir que ele seja linearizável, pois uma alteração pode ter sido feita instantes antes em uma máquina diferente da máquina que faz a leitura, porém essa alteração ainda não foi propagada. Logo, o valor lido não estaria de acordo com a ordenação global dos eventos. Exercícios Área 2 12</p>