Exercícios de Computação e Ciências da Computação

Prévia do material em texto

2
Pontifícia Universidade católica de goiás
Escola de Ciências Exatas e da Computação
Engenharia de Computação e Ciências da Computação
Pedro henrique mendes lima e silva
EXERCICIOS
GOIÂNIA,
2020/2
Pontifícia Universidade católica de goiás
Escola de Ciências Exatas e da Computação
Engenharia de Computação e Ciências da Computação
EXERCICIOS
Pedro henrique mendes lima e silva.
Atividade apresentada como requisito para aprovação na disciplina CMP 1190, sob orientação da Prof.(a) TALLES.
GOIÂNIA,
2020/2
Sumário
1	Capítulo 9	4
1.1	Cap. 9 (Coulouris et al.) exercícios: 9.1, 9.2, 9.12, 9.14, 9.15 e 9.16.	4
2	Capítulo 16 && 17	6
2.1	cap. 16 e cap. 17 (Coulouris et al.) exercícios 17.1- 17.4; 17.6 e 17.7.	6
3	Capítulo 14 e 6	9
3.1	cap. 14 (Coulouris et al.) e o cap. 6 (Tanenbaum) exercícios: 14.1, 14.2, 14.4, 14.5, 14.7, 14.8, 14.10-14.14	9
4	Capitulo 6 e 15	11
4.1	Exercícios 8-11 cap. 6 (Tanenbam) p. 164; cap. 15 (Coulouris et al.): 15.5-15.9	11
Capítulo 9
Cap. 9 (Coulouris et al.) exercícios: 9.1, 9.2, 9.12, 9.14, 9.15 e 9.16. 
9.1 Compare o protocolo de requisição-resposta descrito na Seção 5.2 com a implementação de comunicação cliente-servidor no SOAP. Cite dois motivos pelos quais o uso de mensagens assíncronas pelo SOAP é mais apropriado para uso na Internet. Até que ponto o uso de HTTP pelo SOAP reduz a diferença entre as duas estratégias? 
R: Pode ser usado mesmo quando as requisições exigem respostas, no caso em que o cliente envia uma requisição e posteriormente recebe a resposta de forma assíncrona e em um padrão de estilo evento, por exemplo, os clientes de um serviço de diretório podem se registrar nos eventos de interesse e serão notificados quando certos eventos ocorrerem. Para possibilitar o uso de uma variedade de padrões de comunicação, o protocolo SOAP é baseado no empacotamento de mensagens unidirecionais únicas, ele suporta interações de requisição-resposta usando pares de mensagens únicas e especificando como irá representar as operações, seus argumentos e resultados.
9.2 Compare a estrutura dos URLs, conforme usados pelos serviços Web, com a das referências de objeto remoto, conforme especificadas na Seção 4.3.4. Cite, em cada caso, como elas são usadas para executar um pedido do cliente. 
R: Um serviço Web tem uma interface que pode fornecer operações para acessar e atualizar os recursos de dados que gerencia. De forma superficial, a interação entre cliente e servidor é muito parecida com RMI, em que um cliente usa uma referência de objeto remoto para invocar uma operação em um objeto remoto. Para um serviço Web, o cliente usa um URI para invocar uma operação no recurso nomeado por esse URI.
Referências de objeto remoto vs URIs - O URI de um serviço Web pode ser comparado com a referência de objeto remoto de um único objeto, o destinatário dessas referências remotas pode usá-las para invocar operações nos objetos a que se referem.
Modelo de serviços Web - Os usuários dos serviços Web Java devem modelar seus programas que usam serviços Web considerando o fato de que não estão usando invocação remota transparente de Java para Java, mas sim usando o modelo de serviços Web, no qual objetos remotos não podem ser instanciados.
Serventes - No modelo de objeto distribuído, o programa servidor geralmente é modelado como um conjunto de serventes (potencialmente, objetos remotos), esses eram criados como instâncias das classes serventes ShapeList e Shape, respectivamente. Quando o servidor iniciava, sua função main criava a instância de ShapeList, e, sempre que o cliente chamava o método newShape, o servidor criava uma instância de Shape.
9.12 Descreva, em linhas gerais, a principal diferença entre TLS e segurança em XML. Explique por que a XML é particularmente conveniente para a função que desempenha, em termos dessas diferenças. Capítulo 11 e página 406
R: A segurança em XML consiste em um conjunto de projetos relacionados do W3C para assinatura, gerenciamento de chaves e criptografia. Ela se destina a ser usada no trabalho cooperativo pela Internet, envolvendo documentos cujo conteúdo talvez precise ser autenticado ou cifrado. Normalmente, os documentos são criados, trocados, armazenados e, depois, novamente trocados, possivelmente após serem modificados por uma série de usuários diferentes. Essas necessidades não podem ser atendidas pelo TLS, usado para criar um canal seguro para a comunicação de informações.
	Isso é possível em XML, pois, marcas (tags) XML podem ser usadas para definir as propriedades dos dados no documento. Em particular, a segurança em XML depende de novas tags que possam ser usadas para indicar o início e o fim de seções de dados cifrados, ou assinados, e de assinaturas. Uma vez que a segurança necessária tenha sido aplicada dentro de um documento, ele pode ser enviado para uma variedade de usuários diferentes, até por meio de multicast.
9.14 Explique a relevância da XML canônica nas assinaturas digitais. Quais informações contextuais podem ser incluídas na forma canônica? Dê um exemplo de brecha de segurança em que o contexto é omitido da forma canônica. página 409 
R: Quando um subconjunto de um documento XML se torna canônico, a forma canônica inclui o contexto ancestral, isto é, os espaços de nomes declarados e os valores dos atributos. Assim, quando a XML canônica for usada em conjunto com assinaturas digitais, a assinatura de um elemento não passará em sua validação, caso esse elemento seja colocado em um contexto diferente.
9.15 Um protocolo de coordenação poderia ser executado para coordenar as ações dos serviços Web. Descreva em linhas gerais uma arquitetura para (i) um protocolo centralizado e (ii) um protocolo de coordenação distribuída. Em cada caso, descreva as interações necessárias para estabelecer a coordenação entre dois serviços Web. página 411 
R:
1. O cliente solicita ao serviço de agente de viagens informações sobre voos;
2. O serviço de agente de viagens reúne as informações sobre preço e disponibilidade e as envia
 para o cliente, o qual escolhe uma das opções a seguir em nome do usuário:
(a) refinar a consulta, possivelmente envolvendo mais provedores para obter mais informações;
 e, em seguida, repetir o passo 2;
(b) fazer reservas;
(c) sair.
3. O cliente solicita uma reserva e o serviço de agente de viagens verifica a disponibilidade.
4. Ou todos estão disponíveis;
 ou para os serviços que não estão disponíveis;
ou são oferecidas alternativas para o cliente, que volta para o passo 3;
ou o cliente volta para o passo 1.
5. Faz o depósito.
6. Fornece ao cliente um número de reserva como confirmação.
7. Durante o período decorrido até o pagamento final, o cliente pode modificar ou cancelar
 as reservas.
9.16 Compare a semântica de chamada RPC com a semântica do WS-ReliableMessaging: i) Cite as entidades às quais cada uma se refere. ii) Compare os diferentes significados da semântica disponível (por exemplo, pelo menos uma vez, no máximo uma vez, exatamente uma vez). Capítulo 5 e página 392
R: WS-ReliableMessaging se preocupa com o envio de mensagens únicas e não deve ser confundida com a RPC, que se refere ao número de vezes que o servidor executa o procedimento remoto. O protocolo RPC pode ser implementado sobre diferentes tipos de protocolos de transporte, uma vez que é indiferente a maneira de como uma mensagem é transmitida entre os processos
Capítulo 16 && 17
cap. 16 e cap. 17 (Coulouris et al.) exercícios 17.1- 17.4; 17.6 e 17.7. 
17.1 Em uma variante descentralizada do protocolo de confirmação de duas fases, os participantes se comunicam diretamente uns com os outros, em vez de indiretamente por meio do coordenador. Na fase 1, o coordenador envia seu voto para todos os participantes. Na fase 2, se o voto do coordenador for Não, os participantes apenas cancelam a transação; se for Sim, cada participante envia seu voto para o coordenador e para os outros participantes, cada um dos quais decide sobre o resultado, de acordo com o voto, e o executa. Calcule o número de mensagens e o númerode rodadas necessárias para isso. Quais são as vantagens ou desvantagens, em comparação com a variante centralizada? página 732 
R: 
Total de mensagens = N*N;
Fase 1: Coordenador envia seu voto para N participantes = N; 
Fase 2: cada N participante envia seu voto para os outros (N-¬1) participantes + coordenador = N*(N-1);
Número de rodadas: Cada participante + coordenador = 2 rodadas;
Vantagens: O número de rodadas é menor;
Desvantagem: A quantidade de mensagens N*N ao invés de 3N.
17.2 Um protocolo de confirmação de três fases tem as seguintes partes: Fase 1: é igual à confirmação de duas fases. Fase 2: o coordenador reúne os votos e toma uma decisão; se ela for Não, ele cancela e informa aos participantes que votaram Sim; se a decisão for Sim, ele envia uma requisição preCommit para todos os participantes. Os participantes que votaram em Sim esperam por uma requisição preCommit ou doAbort. Eles reconhecem as requisições preCommit e executam requisições doAbort. Fase 3: o coordenador reúne as respostas. Quando todas foram recebidas, ele confirma (com commit) e envia a requisição doCommit aos participantes. Os participantes esperam por uma requisição doCommit. Quando a requisição chega, eles confirmam (com commit). Explique como esse protocolo evita o atraso para os participantes durante seu período de incerto, devido à falha do coordenador ou de outros participantes. Presuma que a comunicação não falhe. página 735 
R: O protocolo é um algoritmo distribuído que permite que todos os nós em um sistema distribuído concordem em confirmar uma transação. É um refinamento do protocolo de duas fases, que é mais resistente a falhas.
17.3 Explique como o protocolo de confirmação de duas fases para transações aninhadas garante que, se a transação de nível superior for confirmada, todas as descendentes corretas serão confirmadas ou canceladas. página 736 
R: O identificador de uma subtransação deve ser uma extensão do TID de sua ascendente construído da forma que o identificador da transação de nível superior, ou ascendente dessa subtransação, possa ser determinado a partir de seu próprio identificador de transação. Todos os identificadores de subtransação devem ser globalmente exclusivos. Termina-se um conjunto de transações aninhadas invocando closeTransaction, ou abortTransaction, no coordenador da transação de nível superior. Nesse meio-tempo, cada uma das transações aninhadas executa suas operações. Quando elas tiverem terminado, o servidor que estiver gerenciando a subtransação registrará informações quanto ao fato da subtransação ter sido confirmada provisoriamente ou ter sido cancelada. De modo que, se sua ascendente for cancelada, a subtransação também será obrigada a ser cancelada.
17.4 Dê um exemplo das interposições de duas transações serialmente equivalentes em cada servidor, mas não serialmente equivalentes globalmente. página 740
R:
	 
17.6 Amplie a definição do travamento de duas fases para aplicar nas transações distribuídas. Explique como isso é garantido pelas transações distribuídas usando travamento de duas fases restrito de forma local. página 740, Capítulo 16 
R: No bloqueio em duas fases todas as operações de bloqueio (read_lock e write_lock) precedem a primeira operação de desbloqueio (unlock). As transações são divididas em duas fases: Expansão: quando são emitidos todos os bloqueios; 
Contração: quando os desbloqueios são emitidos e nenhum novo bloqueio pode ser emitido.
 Cada servidor é responsável por aplicar controle de concorrência em seus próprios objetos. Os membros de um conjunto de servidores de transações distribuídas são conjuntamente responsáveis por garantir que elas sejam executadas de maneira serialmente equivalente. De modo que, se a transação T for executada antes da transação U em seu acesso conflitante aos objetos de um dos servidores, então elas deverão estar nessa ordem em todos os servidores cujos objetos forem acessados de maneira conflitante por T e U.
17.7 Supondo que esteja em uso o travamento de duas fases restrito, descreva como as ações do protocolo de confirmação de duas fases se relaciona com as ações de controle de concorrência de cada servidor individual. Como a detecção de impasse distribuído se encaixa nisso? páginas 732,740
R: No controle de concorrência ocorre o travamento, ordenação por carimbo de tempo e controle de concorrência otimista. A técnica de bloqueio em duas fases para controle de concorrência é baseada no bloqueio de itens de dados, sendo que, chamamos de bloqueio uma variável que fica atrelada ao item de dados. 
O impasse (deadlock) pode ocorrer porque as transações esperam uma pela outra. Uma transação está em impasse se está bloqueada e permanecerá assim até que ocorra uma intervenção externa, resultando também em impasse os algoritmos de controles de concorrências baseados em bloqueio.
Capítulo 14 e 6
cap. 14 (Coulouris et al.) e o cap. 6 (Tanenbaum) exercícios: 14.1, 14.2, 14.4, 14.5, 14.7, 14.8, 14.10-14.14 
14.1 Por que a sincronização do relógio do computador é necessária? Descreva os requisitos de projeto de um sistema para sincronizar os relógios em um sistema distribuído. página 596 
R: É necessária para sincronização de tempo. Cada processador tem uma componente chamada relógio, estes em um S.D. podem: acusar horas diferentes entre si, acusar hora diferente da hora real externa e ter velocidades diferentes. Relógios sincronizados são necessários para uma série de aplicações: identificar atualidade de mensagens, aplicações de tempo real e controle de versões. Enquanto algumas aplicações requerem apenas que relógios estejam sincronizados entre si, outras aplicações requerem também uma sincronização com o relógio real, nestas aplicações não basta identificar uma ordem parcial entre os eventos ou impor uma ordem total arbitrária, mas sim identificar o momento exato de ocorrência dos eventos com relação à hora global.
14.2 Um relógio está mostrando 10:27:54.0 (hr:min:seg), quando se descobre que ele está adiantado 4 segundos. Explique por que não é desejável configurá-lo com a hora certa nesse ponto e mostre (numericamente) como ele deve ser ajustado de modo a estar correto após terem decorrido 8 segundos. página 600
R: Caso o relógio fosse atrasado para acertá-lo e, logo na sequência, o arquivo fosse modificado, poderia parecer que o arquivo fonte foi modificado antes da compilação e erroneamente, não compilaria o arquivo fonte. Deve ser ajustado para 10:27:08 – 00:00:08.
14.4 Um cliente tenta sincronizar com um servidor de tempo. Ele grava os tempos de viagem de ida e volta e os carimbos de tempo retornados pelo servidor na tabela a seguir. Quais desses tempos ele deve usar para configurar seu relógio? Com que tempo ele deve ser configurado? Faça uma estimativa da precisão da configuração com relação ao relógio do servidor. Se for conhecido que o tempo entre o envio e o recebimento de uma mensagem no sistema envolvido é de pelo menos 8 ms, suas respostas mudarão? página 601
R: O cliente deve escolher, entre os registros existentes, aquele que possui o menor RTT, já que este tende a ser o mais preciso. Nesse caso, ele escolhe o último item da tabela (20 ms = 0,02s). A precisão do clock do cliente depende fundamentalmente do tempo gasto com o processamento do pedido, como ele não é conhecido consideramos metade do RTT, desprezando o tempo de deslocamento, sendo assim a precisão é igual a 10 ms. Se o tempo mínimo de transferência de mensagens na rede é de 8ms, podemos considerar que o tempo restante para a metade do RTT consiste na precisão. Sendo assim, o clock continua sendo o mesmo, mas a precisão agora passa a ser de apenas 2 ms.
14.5 No sistema do Exercício 14.4, exige-se que se mantenha a sincronização do relógio de um servidor de arquivos dentro de ±1 milissegundo. Discuta isso em relação ao algoritmo de Cristian. página 601
R: Pode ocorrer o problema de que o único servidor de tempo pode falhar e, assim, tornar a sincronização temporariamente impossível.
14.7 Um servidor NTP B recebe uma mensagem do servidorA às 16:34:23.480, contendo o carimbo de tempo 16:34:13.430, e dá uma resposta. O servidor A recebe a mensagem às 16:34:15.725, contendo o carimbo de tempo de B, 16:34:25.7. Faça uma estimativa da compensação de B e A e a sua precisão. página 605 
R:
A: 16:34:13.430 - 16:34:15.725 = 00:00:02.295
B: 16:34:23.480 - 16:34:25.700 = 00:00:02.220
Precisão de 2.2ms.
14.8 Discuta os fatores a serem levados em conta ao se decidir com qual servidor NTP um cliente deve sincronizar seu relógio. página 606
R: Para cada par de mensagens enviadas entre dois servidores, o NTP calcula uma compensação que é uma estimativa da compensação real entre os dois relógios, e um atraso que é o tempo de transmissão total das duas mensagens. Além da filtragem de dados aplicada nas trocas com cada par, o NTP aplica um algoritmo de seleção de par.
14.10 Considerando um encadeamento de zero ou mais mensagens conectando os eventos e e e', e usando indução, mostre que e → e' ⇒ L(e) < L(e'). página 608 
R: Isso pode ser facilmente mostrado, por indução, em qualquer sequência de eventos relacionando a esses dois eventos.
14.11 Mostre que Vj [i] ≤ Vi [i]. página 609 
R: Podemos identificar quando dois eventos são concorrentes comparando seus carimbos de tempo. Por exemplo, que c || e pode ser visto dos fatos de que nem V(c) ≤ V(e) nem V(e) ≤ V(c).
14.12 De maneira semelhante ao Exercício 14.10, mostre que e → e' ⇒ V(e) < V(e'). página 610
R: É simples mostrar, por indução, no comprimento de qualquer sequência de eventos relacionados a dois eventos e e e', que e → e' ⇒ V(e) < V(e')
 
14.13 Usando o resultado do Exercício 14.11, mostre que, se os eventos e e e' são concorrentes, então nem V(e) ≤ V(e'), nem V(e') ≤ V(e). Assim, mostre que, se V(e) < V(e'), então e → e'. página 610 
R: Podemos identificar quando dois eventos são concorrentes comparando seus carimbos de tempo. Por exemplo, que c || e pode ser visto dos fatos de que nem V(c) ≤ V(e) nem V(e) ≤ V(c).
14.14 Dois processos P e Q estão conectados em anel, usando dois canais, e constantemente fazem o rodízio de uma mensagem m. Em qualquer dado momento, existe apenas uma cópia de m no sistema. O estado de cada processo consiste no número de vezes que ele recebeu m, e P envia m primeiro. Em certo ponto, P tem a mensagem e seu estado é 101. Imediatamente após enviar m, P inicia o algoritmo do instantâneo. Explique o funcionamento do algoritmo neste caso, fornecendo o(s) estado(s) global(is) possível(is) relatado(s) por ele. página 615
R: Veremos que o estado gravado pelo algoritmo do instantâneo tem propriedades convenientes para avaliar predicados globais estáveis. O algoritmo grava o estado de forma local nos processos; ele não fornece um método para agrupar o estado global em um site. Um método óbvio de agrupar é fazer todos os processos enviarem o estado que gravaram para um processo coletor designado, mas não vamos tratar desse problema aqui
Capitulo 6 e 15
Exercícios 8-11 cap. 6 (Tanenbam) p. 164; cap. 15 (Coulouris et al.): 15.5-15.9  
8- Muitos algoritmos distribuídos requerem a utilização de um processo coordenador. Até que ponto esses algoritmos realmente são considerados distribuídos? Comente sua resposta. 
R: Em um algoritmo centralizado sempre existe um processo fixo que age como coordenador. A distribuição vem do fato de que outros processos rodam em máquinas separadas.
9- Na abordagem centralizada da exclusão mútua (Figura 6.14), ao receber uma mensagem de um processo que está liberando seu acesso exclusivo aos recursos que estava usando, o coordenador normalmente concede permissão ao primeiro processo na fila. Cite um outro algoritmo possível para o coordenador. 
R: Os pedidos feitos ao coordenador podem estar associados a prioridades. Os processos com maior prioridade receberão o recurso compartilhado
10- Considere novamente a Figura 6.14. Suponha que o coordenador caia. Isso sempre derruba o sistema? Se não derrubar, sob que circunstâncias isso acontece? Há algum modo de evitar o problema e fazer com que o sistema seja capaz de tolerar quedas de coordenador? 
R: Suponha que o algoritmo seja tal que o coordenador sempre responda a um pedido, ou aceitando ou negando. Se não existem processos acessando recursos, nem na fila, então a queda do coordenador não é fatal. O próximo pedido de permissão ao coordenador irá falhar e o processo requisitante pode iniciar um novo processo de eleição de coordenador.
11- O algoritmo de Ricart e Agrawala apresenta o seguinte problema: se um processo falhou e não responde a uma requisição de um outro processo para acessar um recurso, a falta de resposta será interpretada como uma recusa de permissão. Sugerimos que todas as requisições sejam respondidas imediatamente para facilitar a detecção de processos que falharam. Há algumas circunstâncias em que até esse método é insuficiente? Discuta sua resposta. 
R: Suponha que um processo X negue a permissão e depois caia, o processo requisitante pensa que X está vivo, e ficará esperando uma permissão futura que nunca virá. Uma solução é permitir que o processo requisitante não fique bloqueado esperando uma resposta, o processo requisitante apenas dorme por um período fixo, assim quando acordar verifica se os processos dos quais ele espera uma resposta estão vivos
15.5 Adapte o algoritmo do servidor central para exclusão mútua para tratar da falha por colapso de qualquer cliente (em qualquer estado), supondo que o servidor seja correto e dado um detector de falha confiável. Comente se o sistema resultante é tolerante a falhas. O que aconteceria se um cliente que possuísse a ficha fosse erroneamente suspeito de ter falhado? página 636 
R: O modo mais simples de obter exclusão mútua é empregar um servidor que conceda permissão para entrar na seção crítica. O sistema resultante é tolerante a falhas. Se a fila de processos em espera não estiver vazia, o servidor escolherá a entrada mais antiga, a removerá e responderá para o processo correspondente. Então, o processo escolhido terá a posse da ficha.
15.6 Dê um exemplo de execução do algoritmo baseado em anel para mostrar que os processos não têm necessariamente a entrada garantida na seção crítica na ordem acontece antes. página 637
	 
15.7 Em determinado sistema, cada processo normalmente usa uma seção crítica muitas vezes, antes que outro processo a solicite. Explique por que o algoritmo de exclusão mútua baseado em multicast de Ricart e Agrawala é ineficiente para esse caso e descreva como fazer para melhorar seu desempenho. Sua adaptação satisfaz a condição de subsistência ME2? página 639 
R: Neste algoritmo, os processos não sabem qual processo é que está utilizando o recurso em um determinado momento. Uma vez que um processo perdeu uma ou mais requisições, devido ao fato de ter um tempo lógico superior, então ele responde essas mensagens e não sabe quais processos estão acessando o recurso. Ele só tem a garantia que no futuro ele vai receber os ACKs solicitados e então o recurso estará disponível para ele.
Esse problema pode ser solucionado adicionando respostas, inclusive de negação e de permissão, a cada mensagem de requisição. Uma falha de entrega agora pode ser detectada por timeout.
15.8 No algoritmo valentão, um processo de recuperação inicia uma eleição e se tornará o novo coordenador, caso tenha um identificador mais alto do que o encarregado atual. Essa é uma característica necessária do algoritmo? página 644 
R: Sim, todos nós possuem um identificador e sempre que um nó P percebe que o coordenador não responde, P inicia uma eleição: 
1. P envia uma mensagem ELEIÇÃO a todos os processos de números mais altos;
2. Se nenhum responder, P vence a eleição e se torna o coordenador;
3. Se um dos processos de número mais alto responder, ele toma o poder e o trabalho de P está concluído. 
Dessa forma é eleito o nó com maior identificador.
15.9 Sugira como fazer para adaptar o algoritmo valentão para tratar com particionamentos temporários de rede (comunicação lenta) e processos lentos. página 646
R: O algoritmo funcionaránormalmente, cada um dos processos com maiores números irá receber duas mensagens de ELEIÇÃO, a segunda mensagem é ignorada e o processo de eleição continua.