Arquiteturas de Comunicação

Introdução, Conceitos e Fundamentos

Prof. César Augusto M. Marcon

ARQUITETURA DE COMPUTADORES II

2 / 28

Índice

1. Introdução

2. Classificação

4. Exercícios

3. Estratégias de Comunicação

3 / 28

• Conceito– Estrutura básica para a comunicação entre componentes da arquitetura alvo

• Objetivos– Alta taxa de comunicação– Fidelidade da comunicação– Tolerância a falhas da comunicação– ...

• Classificações– Dinamicidade estática x dinâmica– Conectividade ponto-a-ponto x multiponto– ...

• Estratégias– Estratégias de conexão– Estratégias de roteamento– Estratégias de compartilhamento– ...

• Topologias– Barramentos– Conexões dedicadas– Redes em anel– ...

Introdução

4 / 28

Índice

1. Introdução

4. Exercícios

2. Classificação

3. Estratégias de Comunicação

5 / 28

• Conectividade– Classificação segundo o número de conexões entre componentes da

infra-estrutura de comunicação• Ponto-a-ponto

– Cada canal conecta um par de componentes

• Multiponto– Canais conectam mais de dois componentes

Classificação Segundo Conectividade

1 2 3

4 5 6

1 2 3 4 5 6

6 / 28

• Número de acessos simultâneos– Espacial

• Todas as conexões são independentes. Podem existir tantas transações, quantas forem as conexões

– Temporal• Todas conexões são interdependentes. Ocorre apenas uma transação

por vez

– Espaço-temporal• Combinação das classes acima

• Topologia lógica variável durante a

execução do sistema

Classificação Segundo Número de Acessos Simultâneos

1 2 3

4 5 6

1 2

4 3

1 2

4 3

7 / 28

Dinamicidade refere-se a criação de caminhos variáveis para a informação durante a operação do sistema

• Estáticas– Infra-estrutura de comunicação estática tem topologia lógica fixa, se

mantendo inalterada durante todo ciclo de vida do sistema– Ex.:

– Características• Interligadas através de ligações fixas

– Entre cada componente existe ligação direta dedicada

– Uso• Máquinas paralelas normalmente têm estruturas estáticas regulares com ligações

homogêneas • Sistemas distribuídos possuem estruturas estáticas irregulares com ligações

heterogêneas

Classificação Segundo Dinamicidade

1 2 3

4 5

8 / 28

• Dinâmicas

– Definição• Não existe topologia lógica fixa. Infra-estrutura é dinâmica se é adaptável à

necessidade de comunicação durante a operação

– Classificações de topologias dinâmicas• Bloqueante ou não-bloqueante

– Conexão entre dois pontos impede ou não outra conexão entre componentes quaisquer

• Unilateral ou bilateral– Componente possui uma ligação bidirecional ou uma ligação de envio e outra de

recebimento com a infra-estrutura

– Uso• Interligação de processadores com memórias em multiprocessadores• Multicomputadores

Classificação Segundo Dinamicidade

1 2 4 3

1

2

3

4

9 / 28

Índice

1. Introdução

4. Exercícios

2. Classificação

3. Estratégias de Comunicação

10 / 28

Introdução a Estratégias e Comunicação

• Estratégias de comunicação são técnicas e mecanismos que permitem entender, projetar e verificar qual infra-estrutura tem melhor desempenho para uma dada aplicação

• Estratégias básicas da comunicação– Estratégias de roteamento

• Como as mensagens viajam através da rede

– Estratégias de conexão• Como processos se comunicam com uma seqüência de mensagens

– Estratégias de compartilhamento de recursos• Como gerenciar o acesso à recursos compartilhados da infra-estrutura

de comunicação e eliminar ou pelo menos reduzir a contenção causada pelo compartilhamento

11 / 28

Índice

1. Introdução

4. Exercícios

2. Classificação

3. Estratégias de Comunicação

3.1 Estratégias de Roteamento

3.3 Estratégias de Compartilhamento

3.2 Estratégias de Conexão

12 / 28

Estratégias de Roteamento

• Definição– Roteamento é o procedimento de condução de uma mensagem,

através de nós intermediários, até seu destino

• Problema– Quando um processo no nodo A deseja se comunicar com um

processo no nodo B, como essa mensagem é enviada?

• Soluções– Caminho único Só existem um caminho entre o nodo fonte e o

nodo destino• Exemplos: redes estrela ou hierárquicas

– Múltiplos caminhos existem diversas opções de roteamento• Uso de tabelas de roteamento (na origem ou distribuídas)

– Indicam todos os caminhos alternativos– Podem incluir velocidade e custo dos vários caminhos– Devem ser atualizadas sempre que a infra-estrutura mudar suas

características

13 / 28

Algoritmos de Roteamento

• Momento da realização do roteamento– Dinâmico quando realizado em tempo de execução

– Estático quando realizado em tempo de projeto

• Número de destinos das mensagens– Unicast quando os pacotes têm apenas um destino

– multicast quando os pacotes têm mais de um destino

– broadcast quando um pacote é enviado para todos os nodos

• Local onde a decisão de roteamento é tomada– Centralizado quando único nodo define o caminho de todos os pacotes

– Origem quando o caminho do pacote é definido na origem

– Distribuído quando caminho do pacote é definido durante sua transmissão

• O processo de seleção do caminho– Determinístico quando caminho entre origem e destino é sempre o mesmo

– Adaptativo quando o caminho entre origem e destino é determinado por fatores da rede, tais como condições de tráfego

14 / 28

Políticas de Roteamento

• Store-and-Forward– Armazenar e repassar– Buffer deve ter a capacidade de armazenar toda a mensagem

15 / 28

Políticas de Roteamento

• Cut-Through– Armazena só parte da mensagem (flit) e repassa o restante– Cabeçalho abre caminho (Wormhole)– Restante da mensagem segue caminho do cabeçalho (pipeline)

16 / 28

Índice

1. Introdução

4. Exercícios

2. Classificação

3. Estratégias de Comunicação

3.1 Estratégias de Roteamento

3.3 Estratégias de Compartilhamento

3.2 Estratégias de Conexão

17 / 28

Estratégias de Conexão

• Definição do problema– Uma vez que mensagens chegam aos seus destinos, processos podem

requerer sessões de comunicação afim de trocar informações

• Três esquemas comuns para conectar processos– Chaveamento de circuito (circuit switching)

• Conexão totalmente pré-estabelecida antes de iniciar envio da mensagem

– Chaveamento de mensagem (message switching)• Conexão estabelecida durante o envio da mensagem• Utiliza store-and-forwarding• Requer buffers muito grandes em cada nodo

– Chaveamento de pacotes (packet switching)• Otimização do chaveamento de pacotes• Conexão estabelecida durante o envio da mensagem• Mensagens quebradas em pacotes de tamanho fixo• Utiliza cut-through• Requer buffers menores que o chaveamento de mensagem

18 / 28

Estratégias de Conexão

• Chaveamento de circuito– Alocado para duração da comunicação

– Inicialmente, é estabelecido um caminho fixo da origem ao destino (fig. a), e só depois são enviadas todas as mensagens (fig. b),

– Nenhum outro processo pode utilizar esse caminho durante a comunicação

– Similar a um sistema de telefonia

– O estabelecimento de uma conexão pode ter um custo significativo no tempo total da comunicação

– Não requer buffers temporários nos nós intermediários

– Não tem problemas para aplicações de tempo real

19 / 28

• Chaveamento de pacotes– Uma mensagem lógica pode ser divida em vários pacotes

– Não existe caminho pré-definido

– Custo de roteamento distribuído na rede

– Pacotes são enviados para destino separadamente. Mesma mensagem pode ter pacotes enviados através de caminhos diferentes

– As mensagens devem ser remontadas novamente no seu destino

– Estabelecimento dinâmico do caminho pode permitir que os algoritmos de roteamento reajam mais rapidamente a congestionamentos e falhas na rede de interconexão, optando por caminhos alternativos

Estratégias de Conexão

20 / 28Problemas Associados ao Chaveamento por Mensagem ou

por Pacotes

• Deadlock– É a situação onde dois ou mais processos estão esperando o outro processo terminar,

para então utilizar o recurso. Todos os processos mantém o seu estado indefinidamente• Ex.: gêmeos gentis: tu podes nascer primeiro, não, tu podes nascer primeiro, não, não, eu faço

questão, primeiro tu, ...

• Starvation (postergação infinita)– É a situação onde o acesso à um recurso é postergado infinitamente– Um ou mais processos de maior prioridade acessam continuamente o recurso,

impossibilitando que os processos de menor prioridade acessem o mesmo recurso• Ex.: Uso de rotatória por motorista maluco: preferência é do veículo que está na rotatória e o

motorista que está na rotatória nunca sai, fica dando voltas e mais voltas

• Livelock– É um caso especial de starvation. Nesta situação o recurso nunca é acessado, mas

processos que concorrem por ele mudam de estado continuamente• Ex.: Uso de rotatória por motorista maluco e tentativa de contornar o problema: mesmo

problema acima, mas os veículos, ao invés de ficarem parados sempre procuram por novas vias que sempre conduz a mesma rotatória

21 / 28

Índice

1. Introdução

4. Exercícios

2. Classificação

3. Estratégias de Comunicação

3.1 Estratégias de Roteamento

3.3 Estratégias de Compartilhamento

3.2 Estratégias de Conexão

22 / 28

Estratégias de Compartilhamento do Meio de Comunicação

• Definição do problema– Link pode conectar diversos nodos

• Diversos nodos podem querer transmitir simultaneamente informações sobre este link

• Requer estratégias para compartilhar o link• Enquanto uma mensagem usa o link, as demais devem estar contidas em

estruturas especiais (buffers localizados na rede ou nos próprios nodos)

– Contenção ocorre principalmente em topologias multiponto e/ou temporais– Recursos devem armazenar mensagens ou nodos devem ser notificados

para que as mensagem sejam retransmitidas

• Três técnicas principais para tratar colisão– CSMA (carrier sense with multiple access) / CD (collision detection)

• Nodos devem escutar o link antes de enviar uma mensagem• Link livre começa a transmissão da mensagem• Dispositivo deve esperar (e continuar escutando) até o link ficar livre• Transmissão simultânea de mensagens é registrada como colisão CD (collision

detection) Nodos envolvidos terminam transmissões• Máquinas re-tentam depois de algum intervalo de tempo randômico

23 / 28

– Comunicação com Token• Inicialmente um único tipo de mensagem (token) circula no sistema

• Nodo que deseja transmitir deve esperar pelo token

• Remove token da rede e começa transmissão

• Ao término, reenvia token e outros nodos podem transmitir mensagens

• Se token é perdido, sistema deve detectar e gerar novo token

– Pacotes de mensagens• Número de pacotes com mensagens de tamanho fixo circula na rede

• Pacotes carregam mensagens junto com informações de controle (origem, destino, cheio/vazio)

• Nodo que deseja transmitir deve esperar por pacote vazio– Então insere mensagem no pacote junto com informação de controle– Pacote com mensagem viaja pela rede– Cada nodo que recebe pacote faz a inspeção para ver se mensagem é

para ele

• Mensagens no pacote devem ser de tamanho fixo. Portanto, devem ser quebradas de acordo com tamanho definido pelo pacotes

Estratégias de Compartilhamento do Meio de Comunicação

24 / 28

Índice

1. Introdução

4. Exercícios

2. Classificação

3. Estratégias de Comunicação

25 / 28

Exercícios

1. Como posso medir o desempenho de uma infra-estrutura de comunicação?

2. Porque é importante para sistemas paralelos saber a taxa de comunicação entre as tarefas? Responda a questão analisando o mapeamento de tarefas em processadores se comunicando através de uma infra-estrutura de comunicação

3. Diferencie infra-estruturas de comunicação estáticas e dinâmicas

4. Com relação ao roteamento, como pode ser classificada a Internet?

5. Diferencie infra-estruturas de comunicação ponto-a-ponto e multiponto

6. Descreva como funciona o chaveamento por pacotes e o chaveamento por circuito. De vantagens e desvantagens de cada chaveamento

7. Como pode ser tratado/prevenido o problema de contenção em redes de comunicação? Na sua opinião qual é a melhor solução. Justifique

8. O que significa bloqueante, no contexto de infra-estruturas de comunicação?

9. (ENADE 2008 - 27) Em redes de computadores, o protocolo de controle de acesso ao meio define um conjunto de regras que devem ser adotadas pelos dispositivos que compartilham o meio físico. No caso de uma rede Ethernet IEEE 802.3, conectada a um concentrador (hub), em que abordagem se baseia o protocolo de controle de acesso ao meio?a) na passagem de permissão em anelb) na ordenação com contençãoc) na ordenação sem contençãod) na contenção com detecção de colisãoe) na arbitragem centralizada

26 / 28

Resposta de Exercícios

1. Como posso medir o desempenho de uma infra-estrutura de comunicação?

2. Porque é importante para sistemas paralelos saber a taxa de comunicação entre as tarefas? Responda a questão analisando o mapeamento de tarefas em processadores se comunicando através de uma infra-estrutura de comunicação

3. Diferencie infra-estruturas de comunicação estáticas e dinâmicas

4. Com relação ao roteamento, como pode ser classificada a Internet?

5. Diferencie infra-estruturas de comunicação ponto-a-ponto e multiponto

6. Descreva como funciona o chaveamento por pacotes e o chaveamento por circuito. De vantagens e desvantagens de cada chaveamento

7. Como pode ser tratado/prevenido o problema de contenção em redes de comunicação? Na sua opinião qual é a melhor solução. Justifique

8. O que significa bloqueante, no contexto de infra-estruturas de comunicação?

9. (ENADE 2008 - 27) Em redes de computadores, o protocolo de controle de acesso ao meio define um conjunto de regras que devem ser adotadas pelos dispositivos que compartilham o meio físico. No caso de uma rede Ethernet IEEE 802.3, conectada a um concentrador (hub), em que abordagem se baseia o protocolo de controle de acesso ao meio?a) na passagem de permissão em anelb) na ordenação com contençãoc) na ordenação sem contençãod) na contenção com detecção de colisãoe) na arbitragem centralizada

27 / 28

Exercícios

11. (POSCOMP 2002 - 55) Starvation ocorre quando:a) Pelo menos um processo é continuamente postergado e não executa.

b) A prioridade de um processo é ajustada de acordo com o tempo total de execução do mesmo.

c) Pelo menos um evento espera por um evento que não vai ocorrer.

d) Dois ou mais processos são forçados a acessar dados críticos alternando estritamente entre eles.

e) O processo tenta, mas não consegue acessar uma variável compartilhada.

12. (POSCOMP 2003 - 63) Algoritmos distribuídos podem usar passagem de "token" por um anel lógico para implementar exclusão mútua ou ordenação global de mensagens. Nesses algoritmos, apenas o processo que possui o "token" tem a permissão de usar um recurso compartilhado ou numerar mensagens, por exemplo. Considerando o conceito acima podemos afirmar que:a) A abordagem deve tratar no mínimo dois tipos de defeitos: perda do "token" e colapso de

processos

b) Para usar essa a abordagem os computadores precisam estar conectados em uma rede com topologia em anel

c) Nessa abordagem é impossível evitar a geração espontânea de vários "tokens", mesmo em sistemas livre de falhas

d) A abordagem é adequada apenas para sistemas onde possa ser controlado o tempo que cada computador permanece com o "token"

e) A abordagem é pouco robusta, pois a perda do "token" por um processo provoca o bloqueio do algoritmo distribuído que a usa

28 / 28

Resposta de Exercícios

11. (POSCOMP 2002 - 55) Starvation ocorre quando:a) Pelo menos um processo é continuamente postergado e não executa.

b) A prioridade de um processo é ajustada de acordo com o tempo total de execução do mesmo.

c) Pelo menos um evento espera por um evento que não vai ocorrer.

d) Dois ou mais processos são forçados a acessar dados críticos alternando estritamente entre eles.

e) O processo tenta, mas não consegue acessar uma variável compartilhada.

12. (POSCOMP 2003 - 63) Algoritmos distribuídos podem usar passagem de "token" por um anel lógico para implementar exclusão mútua ou ordenação global de mensagens. Nesses algoritmos, apenas o processo que possui o "token" tem a permissão de usar um recurso compartilhado ou numerar mensagens, por exemplo. Considerando o conceito acima podemos afirmar que:a) A abordagem deve tratar no mínimo dois tipos de defeitos: perda do "token" e colapso de

processos

b) Para usar essa a abordagem os computadores precisam estar conectados em uma rede com topologia em anel

c) Nessa abordagem é impossível evitar a geração espontânea de vários "tokens", mesmo em sistemas livre de falhas

d) A abordagem é adequada apenas para sistemas onde possa ser controlado o tempo que cada computador permanece com o "token"

e) A abordagem é pouco robusta, pois a perda do "token" por um processo provoca o bloqueio do algoritmo distribuído que a usa