Exercicios - 2 - respostas

Prévia do material em texto

Capítulo 4 
1) Qual a importância de um sistema de nomeação para sistemas distribuídos? 
Para que entidades possam ser referenciadas e acessadas em um sistema distribuído. 
2) O que é um endereço para um sistema de nomeação? 
Uma entidade em um sistema distribuído é acessada por intermédio de seu ponto de acesso. O endereço é o 
nome dado ao ponto de acesso. 
3) Por que não é comum a utilização do endereço do ponto de acesso de uma entidade como nome para 
esta entidade? 
Porque este tipo de nomeação não oferece a flexibilidade desejada e não costuma ser amigável a seres 
humanos. 
4) O que é um nome independente de localização? 
É um nome que pode ser dado a uma entidade e que é independente do endereço de seu ponto de acesso. 
5) O que caracteriza um identificador? 
É um nome utilizado para identificar uma entidade de forma única, sendo que cada entidade possui apenas 
um identificador e este nunca pode ser reutilizado. 
6) O que é um nome amigável a serem humanos? Cite um exemplo. 
São nomes que podem ser utilizados com facilidade por seres humanos e, em geral, são representados por 
cadeias de caracteres. 
Exemplo: www.unesco.org 
7) Qual a característica dos nomes em um esquema de nomeação simples? 
Os identificadores são cadeias de bits aleatórias sem informações sobre como localizar o endereço do ponto 
de acesso de uma entidade. 
8) Explique como o ponto de acesso de uma entidade pode ser localizado quando se utiliza um esquema de 
nomeação simples. 
Explicar o funcionamento de broadcasting, ponteiros repassadores, localização nativa, tabelas hash 
distribuídas ou abordagem hierárquica. 
9) Como funciona a localização do endereço do ponto de acesso de uma entidade por broadcasting? 
Uma mensagem que contém o identificador da entidade é enviada por broadcast a todas as máquinas da rede 
e cada uma delas verifica se tem essa entidade. Somente as máquinas que podem oferecer um ponto de 
acesso para a entidade enviam uma mensagem de resposta, contendo o endereço daquele ponto de acesso. 
10) Por que a localização do endereço do ponto de acesso de uma entidade por broadcasting não é viável em 
uma grande rede? 
Por causa do grande tráfego gerado na rede quando existem muitos hospedeiros fazendo este tipo de 
solicitação, consumindo largura de banda da rede e interrompendo todos oh hospedeiros com constantes 
consultas que não responderão. 
11) Como funciona a localização do endereço do ponto de acesso de uma entidade por ponteiros 
repassadores? 
Quando uma entidade se move de A para B, deixa para trás, em A, uma referência a sua nova localização em 
B. Tão logo uma entidade seja localizada, um cliente pode consultar o endereço corrente da entidade 
percorrendo uma cadeia de ponteiros repassadores. 
12) Como funciona a localização do endereço do ponto de acesso de uma entidade em uma abordagem 
baseada em localização nativa? 
Cada hospedeiro móvel usa um endereço IP fixo. Toda a comunicação para aquele endereço IP é inicialmente 
dirigida ao agente nativo do hóspede móvel. Esse agente nativo está situado na rede local correspondente ao 
endereço de rede contido no endereço IP do hospedeiro móvel. Sempre que um hospedeiro móvel passar 
para uma outra rede, ele requisita um endereço temporário que possa usar para comunicação. Esse endereço 
externo (care-of address – CoA) é registrado no agente nativo. 
Quando o agente nativo recebe um pacote para o hospedeiro móvel, ele consulta a localização corrente do 
hospedeiro. Se este estiver na rede local corrente, o pacote é simplesmente repassado. Caso contrário, o 
pacote é enviado por um túnel até a localização corrente do hospedeiro. Ao mesmo tempo o remetente do 
pacote é informado da localização corrente do hospedeiro. 
13) Em tabelas hash distribuídas (DHT), pode ser utilizada uma tabela e derivação para a localização a 
entidade responsável por determinada chave. Qual a vantagem na utilização da tabela de derivação? 
Na busca tradicional em DHT cada nó monitora sem antecessor e seu sucessor, e a busca pela entidade 
responsável por uma chave deve ser feita seguindo esta cadeia. 
As tabelas de derivação possuem os endereços de entidades que sucedem a entidade atual por uma distância 
de 2n-1, onde n é a entrada da tabela, permitindo saltar vários nós a frente e realizando uma busca mais 
eficiente. 
14) Em um esquema de nomeação simples a busca por uma entidade pode utilizar uma abordagem 
hierárquica. Como é possível a utilização de uma abordagem hierárquica se o nome da entidade não 
fornece informações sobre a localização da entidade? 
Cada domínio D tem um nó de diretório associado, dir(D), que monitora as entidades nesse domínio, incluindo 
as entidades de seus subdomínios. Isso resulta em uma árvore de nós de diretório. 
15) Como uma entidade pode ser localizada em um esquema de nomeação simples utilizando abordagem 
hierárquica? 
Um cliente que deseja localizar uma entidade E emite uma requisição de consulta ao nó de diretório do 
domínio-folha D no qual o cliente reside. Se o nó de diretório não armazenar um registro de localização para 
a entidade, ela não está localizada em D naquele momento. Assim o nó repassa a requisição para seu pai. O 
nó-pai representa um domínio maior do que o de seu filho. Se o pai também não tiver nenhum registro de 
localização para E, a requisição de consulta é repassada para o próximo nível mais alto, e assim por diante, até 
que chegue ao nó de diretório M que armazena um registro de localização para a entidade E. Então a 
requisição de consulta é repassada para o nó de diretório daquele subdomínio que, por sua vez, a repassa 
para baixo pela árvore, até que a requisição finalmente alcance um nó-folha. O registro de localização 
armazenado no nó-folha conterá o endereço de E naquele domínio-folha. Então, esse endereço pode ser 
retornado para o cliente que requisitou inicialmente a consulta. 
16) Qual a diferença entre um esquema de nomeação simples e um esquema de nomeação estruturada? 
Na nomeação estruturada o nome de uma entidade é composto por nomes que podem ser lidos com 
facilidade pelas pessoas. Além disso, o nome da entidade facilita sua localização em um ambiente distribuído. 
17) O que se entende por resolução de nomes em um esquema de nomeação estruturada? 
É o processo de busca pelo endereço do ponto de acesso de uma entidade com base em seu nome. 
18) Na resolução de nomes com nomeação estruturada é possível a fusão de diferentes espaços de nomes 
de forma transparente. Explique a afirmação. 
É possível fazer a montagem de um espaço de nomes dentro de outro. Para tanto, o nó raiz de um espaço de 
nomes (externo) é incorporado (montado) em um identificador no espaço de nomes local, fazendo com que 
o espaço de nomes externo passe a fazer parte do espaço de nomes local. 
19) O que é o NFS (Network File System)? 
É um sistema distribuído de arquivo que vem com um protocolo que descreve como um cliente pode acessar 
um arquivo em um servidor de arquivos remoto. Com o NFS é possível montar um sistema de arquivos de uma 
máquina remota como parte do sistema de arquivos da máquina local. 
20) Espaços de nomes costumam ser organizados em camadas. Qual a função da camada: 
• global 
• administrativa 
• gerencial 
A camada global é formada por nós do nível mais alto, isto é, o nó-raiz e outros nós de diretório logicamente 
próximos ao nó-raiz, ou seja, seus filhos. Os nós na camada global costumam ser caracterizados por sua 
estabilidade, no sentido de que as tabelas de diretório raramente mudam. 
A camada administrativa é formada por nós de diretório que, juntos, são gerenciados por uma única 
organização. Um aspecto característico dos nós de diretório na camada administrativa é que eles representam 
grupos de entidades que pertencem à mesma organização ou unidade administrativa. Os nós na camada 
administrativa são relativamente estáveis. 
A camada gerencial consiste em nós cujo comportamento típicoé a mudança periódica. A camada inclui nós 
que representam arquivos compartilhados. Ao contrário das camadas global e administrativa, os nós na 
camada gerencial são mantidos não somente por administradores de sistemas, mas também por usuários 
individuais de um sistema distribuído. 
21) A resolução de nomes pode ser iterativa ou recursiva. Qual a diferença? 
Na resolução iterativa de nomes, um resolvedor de nomes entrega o nome completo ao servidor-raiz de 
nomes. O servidor-raiz resolverá o nome de caminho até onde puder e retornará o resultado ao cliente, 
contendo o endereço do próximo servidor de nomes. O processo continua recursivamente, servidor a servidor, 
até que o cliente consiga obter o endereço procurado. 
Na resolução recursiva de nomes, em vez de retornar cada resultado intermediário de volta ao resolvedor de 
nomes do cliente, um servidor de nomes passa o resultado para o próximo servidor de nomes, e assim por 
diante, até que obtenha o endereço procurado. Por fim ele passa esse endereço para o resolvedor de nomes 
do cliente. 
Capítulo 5 
1) Por que a sincronização entre processos em sistemas distribuídos é mais complexa do que a sincronização 
entre processos em sistemas centralizados? 
Nos sistemas centralizados a referência de tempo é única, portanto fica claro qual evento ocorreu antes. Como 
em sistemas distribuídos cada hospedeiro tem sua própria noção do tempo, tal ordenação de eventos não é 
trivial. 
2) Como é o funcionamento de um relógio de computador? 
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. 
3) O que se entende por defasagem de relógio? 
Cristais de relógios operam com frequências ligeiramente diferentes, o que faz com que os relógios 
gradativamente saiam de sincronia e informem valores diferentes quando lidos. Essa diferença nos valores 
dos horários é denominada defasagem de relógio. 
4) Para um algoritmo de sincronização de relógios, o que é o deslocamento de um relógio? 
É a diferença entre a hora do relógio e a hora de referência. 
5) Como o NTP faz para sincronizar a hora com um servidor de hora? 
 
Suponha que o hospedeiro A queira sincronizar sua hora com o hospedeiro B. A enviará uma requisição a B, 
com uma marca de tempo cujo valor é T1. B, por sua vez, registrará a hora T2 em que recebeu (obtida de seu 
próprio relógio local) e retornará uma resposta com uma marca de tempo de valor T3, enviando também o 
valor T2. Por fim, A registra a hora da chegada da resposta, T4. Supondo que os atrasos de propagação de A 
até B sejam aproximadamente os mesmos que de B até A, temos que T2-T1 ≈ T4-T3. Nesse caso, A pode 
estimar seu deslocamento em relação a B como 
θ = T2 - (T1 + atraso/2) = T2 - T1 - (T2 - T1 + T4 - T3)/2 = (T2 - T1 + T3 - T4)/2 
6) O que são os estratos do NTP? 
Os servidores NTP formam uma topologia hierárquica dividida em estratos numerados de 0 a 16. O estrato 0 
representa a referência primária de tempo, que é geralmente um receptor do Sistema de Posicionamento 
Global (GPS) ou um relógio atômico. 
O estrato 0 fornece o tempo correto para o estrato 1, que por sua vez fornece o tempo para o estrato 2 e 
assim por diante. Quanto mais perto do estrato 0 maior a exatidão do tempo. 
Quando um hospedeiro A contata um hospedeiro B, só ajustará seu horário se seu próprio nível de estrato for 
mais alto do que o de B. Após a sincronização, o nível de estrato de A se tornará uma unidade mais alto do 
que o de B. 
7) Diz-se que o algoritmo de Berkeley, ao contrário do algoritmo do NTP, não é um algoritmo passivo. O que 
isto significa? 
No NTP hospedeiros perguntam a hora periodicamente a um servidor e ele se limita a responder a essas 
consultas. 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, ele calcula um 
horário médio e diz a todas as outras máquinas como acertarem seus relógios. 
8) Em 1978 Lamport provou que não é necessário que os relógios de hospedeiros estejam em perfeita 
sincronia para determinar a ordem dos acontecimentos em um sistema distribuído. Em que se baseia a 
proposta 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”. 
Para implementar relógios lógicos de Lamport, cada processo Pi mantém um contador local Ci. Esses 
contadores são atualizados conforme as etapas apresentadas a seguir: 
1. Antes de executar um evento, Pi executa Ci ← Ci + 1. 
2. Quando o processo Pi envia uma mensagem m a Pj, ajusta a marca de tempo de m (ts(m)) para o valor de 
Ci após ter executado a etapa anterior. 
3. 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. 
9) Por que é necessária a implementação da exclusão mútua em sistemas distribuídos? 
Existem recursos que podem ser acessados por somente um processo de cada vez. Se não existir um 
mecanismo de exclusão mútua para garantir que somente um processo esteja utilizando o recurso em 
determinado momento, o sistema pode ser corrompido. 
10) Em que consiste a implementação de exclusão mútua baseada em ficha para um sistema distribuído? 
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. 
11) Em que consiste a implementação de exclusão mútua baseada em permissão para um sistema 
distribuído? 
Um processo que quiser acessar o recurso em primeiro lugar solicita a permissão de outros processos. 
Somente poderá acessar o recurso quando receber a permissão. 
12) Como funciona o algoritmo descentralizado de permissão para implementação da exclusão mútua em 
um sistema distribuído? 
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 solicita a permissão de outros processos. Vai precisar 
apenas obter um voto majoritário de m > n/2 coordenadores. 
13) Como funciona o algoritmo distribuído de permissão para implementação da exclusão mútua em um 
sistema distribuído? 
Quando um processo quer acessar um recurso compartilhado, monta uma mensagem que contém o nome do 
recurso, seu número de processo e a hora corrente. Depois, envia a mensagem a todos os outros processos. 
Quando um processo recebe uma mensagem de requisição a ação que ele executa depende de seu próprio 
estado em relação ao recurso nomeado na mensagem. Três casos são distinguidos: 
1. Se o receptor não estiver acessando o recurso e não quiser acessá-lo, devolve uma mensagem OK ao 
remetente. 
2. Se o receptor já tiver acesso ao recurso, simplesmente não responde e coloca a requisição em uma fila. 
3. 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. 
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 remove todos eles da fila 
14) Como funciona o algoritmo do valentão para eleição de um coordenador em um sistema distribuído? 
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: 
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 coordenador. 
3. Se um dos processos de número mais alto responder, ele toma o poder e o trabalho de P está concluído. 
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.