Resumo p1

Prévia do material em texto

Sistemas distribuídos 
● Computadores independentes (diferentes velocidades e SOs) 
● Resolução de problemas que não podem ser resolvidos individualmente 
● Fisicamente distantes 
● troca de mensagens (em vez de mem. Compartilhada) 
● transparência de heterogeneidade → se apresentam como sistema único 
● Fracamente acoplados → processamento > troca de mensagens 
● Não sincronizados 
● Middleware 
○ Software para conexão entre SOs e aplicações 
○ Suporte a redes heterogêneas (diferentes SOs, plataformas e protocolos de comunicação) 
○ Fornecer transparência de heterogeneidade 
○ Mesma interface para várias aplicações 
Arquiteturas de memória 
● Centralizada → mem única acessada por todos → gera gargalo → limita escalabilidade 
● Distribuída → mem junto com os processadores → maior escalabilidade 
○ Compartilhada → espaço de endereçamento global com diferentes tempo de acesso → acesso 
concorrente → comunicação para escrita/leitura 
○ Troca de mensagens → passa pela CPU pra acessar mem. 
Sistemas paralelos 
● Normalmente, fisicamente próximos e com mem. Compartilhada (UMA ou NUMA) 
● Fortemente acoplados 
● Sincronizados em alguns casos 
● Maior vazão → divisão de carga entre processadores 
● Speedup → tempo com 1 CPU / tempo com N CPU 
● Nível de paralelismo → % do tempo em que CPUs executam operações em vez de esperar 
comunicação 
● Sistemas multiprocessados 
○ Memória compartilhada UMA (acesso uniforme) 
○ Sem relógio comum 
○ Redes de interconexão → direciona dados de qualquer entrada para qualquer saída 
○ Redes ômega 
■ N processadores, log n níveis, (n/2)logn switches 
■ No nível s se o s+1 bit for 0, vai pra cima, senão pra baixo 
■ J = 2i, 0<= i <= n/2-1 
■ J = 2i + 1 – n, n/2 <= i <= n-1 
○ Redes butterfly 
■ Conexão entre dois switches se: 
● X = y 
● X xor y possui um único bit 1 no (s+1)-ésimo bit mais significativo 
● Multicomputadores 
○ Pode ou não ter espaço de endereçamento comum 
○ Acesso não uniforme (NUMA) 
○ Fisicamente próximos e fortemente acoplados 
○ Topologias regulares e simétricas 
■ Anel 
■ Mesh → grafo completo 
■ Torus → 2D mesh 
● K² CPUs → dist máx entre 2 nós é 
 
■ Hipercubo → k dimensões → cada nó c/ um rótulo de k bits → ligação entre os q 
diferem em só um bit 
● Dist. Max = k 
● Roteamento salto a salto → mensagem pode ser enviada para qualquer 
dimensão correspondente à posição na qual o endereço do nó corrente difere 
do endereço do destino → múltiplas rotas → tolerância a falhas e controle de 
congestionamento 
● Processadores vetoriais 
○ Fisicamente próximos e fortemente acoplados 
○ Relógio comum 
○ Mem compartilhada ou não 
Taxonomia Flynn 
● SISD → single instruction, single data → 1 CPU e uma unidade de mem. Conectada por barramento 
● SIMD → múltiplos CPUs fortemente acoplados, realizando mesma instrução em dados distintos → 
processamento de vetores e matriz 
● MISD → várias CPUs → operações diferentes, mesmos dados 
● MIMD → op. e dados diferentes → comum em sist. distribuídos e paralelos 
Modelos PRAM e LogP 
● Modelos para projeto e análise de algoritmos paralelos 
● Projeto independente da máquina 
● PRAM → parallel random access machine 
o Mem centralizada e compartilhada; processadores síncronos 
o Modelar acesso exclusivo ou concorrente 
o Não considera custo de comunicação de CPUs 
● LogP 
o Realista → considera custo de comunicação de CPUs 
o L → latência → limite superior para o atraso de troca de mensagens 
o o → overhead → tempo gasto para enviar ou receber mensagem, durante o qual não efetua 
outra operação 
o g → gap → tempo min. Entre transmissão e recepção de mensagens 
o P → número de processadores 
Concorrência 
● Razão: operações locais (s/ comunicação) /total de operações 
● Quando existe duas ou mais threads progredindo (não necessariamente executando ao mesmo 
tempo) 
● Paralelismo → execução simultânea de 2 threads 
Granularidade 
● Razão: qtd de computação / qtd comunicação 
● Baixa granularidade → melhor em sistemas fortemente acoplados 
Troca de mensagens (TM) e mem. Compartilhada (MC) 
● Mem compartilhada é mais fácil de programar 
● Emular TM -> MC 
○ Dividir espaço de endereçamento em conjuntos distintos para os processadores 
○ Implementar send e receive para escrita e leitura 
○ Reservar algum espaço de endereçamento para caixa de correio 
○ Primitivas de sincronização para informar envio e recebimento 
● Emular MC → TM 
○ Usar send/receive para realizar escrita/leitura 
○ Escrita emulada por envio de mensagem de atualização para o dono do espaço de 
endereçamento 
○ Leitura → envio de mensagem de query 
○ Facilita programação, mas é caro → latência devido comunicação por rede 
Primitivas de comunicação 
● Send(destino, dados) 
○ Com buffer → copia do espaço do usuário para o buffer do kernel e depois para a rede 
○ Sem buffer → direto pra rede 
● Receive (origem, dados) 
○ Sempre com buffer 
○ Origem pode ser * (recebe de todos) 
● Síncronas → fazem handshake 
○ Send → controle retoma quando receiver termina recebimento e envia sinal 
○ Receive → controle termina quando acaba de receber os dados 
● Assíncronas 
○ Send → controle retorna ao processo após copiar os dados para fora do buffer do usuário 
○ Receive → não faz sentido ser assíncrono 
● Bloqueante 
○ Fica bloqueado até terminar a primitiva (seja síncrona ou assíncrona) 
● Não bloqueante 
○ Retoma controle logo após invocar primitiva 
○ Send → retoma quando começa a copiar para o buffer do kernel 
○ Receive → retoma mesmo antes de receber os dados 
○ Recebe um handle para verificar se terminou 
○ Wait( handles[] )→ bloqueia até um dos handles ser resolvido 
● Send síncrono bloqueante → fácil de programar, mas menos eficiente (remetente tem q esperar 
receive ser chamado) 
● Send síncrono não bloqueante → evita atrasos quando receive não foi invocado 
● Send assíncrono não bloqueante → útil para dados maiores (não tem q esperar copiar para o buffer) 
● Receive não bloqueante → útil pra receber dados maiores ou quando send não foi invocado 
Sincronismo de processador 
● Relógios sincronizados → impossível em SD 
● Sincronia por passos → barreira para processadores executarem mesmo passo 
Sincronismo de execução 
● Processadores sincronizados 
● Divergência de relógios é limitada 
● Limite de tempo para executar passo 
● Sem sincronismo → tem atraso de mensagens 
● Emular síncrono em assíncrono → usar barreiras, sincronizador 
● Emular assíncrono em síncrono → trivial 
● Síncrono → consegue resolver mais problemas em sistemas suscetíveis a falhas 
Desafios de sistema 
● Comunicação → garantir mecanismo de comunicação 
● Processos → gerenciar processos em clientes e servidores; migração de código e dispositivos móveis 
● Nomenclatura → robusta para localização de recursos e processos transparentemente 
● Sincronização de processos 
● Armazenamento e acesso a dados → acessar de forma rápida e escalável 
● Consistência e replicação → para evitar gargalos e permitir escalabilidade 
● Tolerância a falhas → funcionar eficientemente mesmo se tiver falhas em nós/enlaces 
● Permitir escalabilidade 
Desafios de algoritmos 
● Modelos de execução: fornecer modelos para projeto e análise 
● Desenvolver algoritmos em grafos dinâmicos 
● Comunicação em grupo: algoritmo pra gerência eficiente em caso de falhas; entrega de mensagens 
em ordem 
● Depurar algoritmos: difícil devido a concorrência 
● Garantir confiabilidade e tolerância a falhas 
● Balanceamento de carga: algoritmo pra aumentar vazão e diminuir latência 
● Escalonamento em tempo real: algoritmo pra aplicações sensíveis a tempo 
● Desempenho: garantir certa vazão 
Metas SD 
● Acesso e compartilhamento de recursos remotos de forma eficiente e controlada 
● Transparência de distribuição → ocultarque recursos estão distribuídos → latências e limitações de 
processamento impedem transparência total 
○ De acesso → ocultar arquitetura de máquina e representação dos dados 
○ Localização → ocultar localização física de recursos 
○ Migração → recurso pode mudar de lugar sem afetar como é acessado 
○ Relocação → recurso pode ser movido enquanto em uso (notebooks e celulares) 
○ Replicação → ocultar replicação 
○ Concorrência → ocultar q recurso é compartilhado 
○ Falhas → superar falha sem o usuário perceber 
● Abertura 
○ Oferecer serviços de acordo com regras padronizadas definidas em uma interface 
○ IDL → linguagem de definição de interface 
○ Fácil extensão e configuração 
○ Interoperabilidade → até q ponto 2 componentes podem trabalhar juntos 
○ Portabilidade → até q ponto uma operação para um sistema pode ser executada em outro 
sem modificação 
● Escalabilidade 
○ De tamanho → fácil de adicionar novos usuários e recursos 
■ Evitar gargalos de processamento, comunicação e armazenamento 
■ Serviços centralizados → único servidor para todos → pode ser necessário por 
segurança 
■ Dados centralizados (ex: dns) → gargalo no acesso 
■ Algoritmos centralizados (máquinas com informações completas sobre a rede) → 
transporte de informação a cada alteração sobrecarrega a rede 
○ Geográfica → usuários e recursos podem estar distantes 
○ Administrativa → fácil de gerenciar, mesmo com várias organizações e recursos 
Problemas de transparência 
● Pode reduzir desempenho 
○ Várias tentativas de conexão para mascarar falhas 
○ Propagar alterações em casos de replicação 
● Usuários não entendem o comportamento 
Técnicas de escalabilidade 
● Ocultar latências de comunicação → não esperar resposta (assíncrono) 
● Distribuição → dividir componentes e espalhar pelo sistema (ex: DNS) 
● Replicação → aumentar disponibilidade, diminuir latência e equilibrar carga 
Sistemas de computação distribuídos 
● Derivados da computação paralela 
● Para tarefas de computação de alto desempenho 
● Cluster computing → melhor razão preço/desempenho; computação intensiva paralela 
● Computação em grade →recursos de diferentes organizações reunidos para permitir colaboração 
(heterogeneidade) 
● Em nuvem → computação como serviço; visão cliente-servidor 
Sistemas de informação distribuídos 
● Aplicação (servidor e BD) disponibilizada a cliente remotos 
● Clientes enviam requisição (em forma de transações) e recebem resposta 
Transações 
● Comum em BD 
● Begin_transaction, end_transaction, abort_transaction (mata e restaura valores anteriores), read e 
write 
● Propriedades ACID 
○ Atomicidade → execução de forma indivisível 
○ Consistência → não viola invariantes do Sistema 
○ Isolamento → uma transação não interfere em outra 
○ Durabilidade → mudanças são perpétuas após commit 
● Transações aninhadas → uma transação pode ter subtransações 
Integração de aplicações empresariais 
● Integrar aplicações independentemente do BD 
● Componentes de aplicações se comunicam diretamente → integração por middleware 
● Remote procedure call → componente envia requisição a outro executando chamada de 
procedimento local → ambos componentes ligados e sabendo como se referir ao outro → 
acoplamento q pode ser desvantagem 
● Sistemas publish/subscribe → aplicações indicam interesse por um tipo de mensagem e o 
middleware cuida de entregar 
Sistemas distribuídos pervasivos (espalhados, difusos) 
● Dispositivos móveis e embarcados → pequenos, pouca bateria, móveis 
● Sistemas domésticos, de saúde, redes de sensores 
● Adotar mudanças de contexto → dispositivo sabe q pode mudar de ambiente 
● Comunicação para troca de informações/compartilhamento 
● Administração distribuída