Introdução a Sistemas Distribuídos

Prévia do material em texto

Prof. Luiz Fernando Bittencourt IC - UNICAMP
MC714
Sistemas Distribuídos
2° semestre, 2018
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Introdução	- sistemas	
distribuídos	
• 1. Coleção de entidades independentes que colaboram para 
resolver um problema que não poderia ser resolvido 
individualmente (Kshemkalyani e Singhal).
• 2. Sistema onde componentes de hardware ou software 
localizados em computadores em rede comunicam-se e 
coordenam suas ações através somente de troca de 
mensagens (Couloris, Dollimore e Kindberg).
• 3. Um conjunto de computadores independentes que se 
apresenta a seus usuários como um sistema único e coerente
(Tanenbaum e Van Steen).
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Caracterização	– sistemas	distribuídos
• Usuário só descobre que está usando um sistema distribuído 
quando alguma falha impede de usar alguma aplicação 
(Lamport).
• Coleção de computadores que não compartilham memória 
ou relógio físico comum, que se comunicam por mensagens
sobre uma rede de comunicação, e cada computador possui 
sua própria memória e executa seu próprio sistema 
operacional. Tipicamente são semi-autônomos e fracamente 
acoplados enquanto cooperam para resolver um problema 
coletivamente (Tanenbaum / Van Steen).
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Características
• Sem relógio físico comum
• Introduz a noção de distribuição, dando origem à 
assincronia inerente entre processadores.
• Sem memória compartilhada
• Requer troca de mensagens para comunicação.
• Deve-se notar que pode fornecer abstração de um 
espaço de endereçamento comum através da 
abstração de memória compartilhada distribuída.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Sistemas	paralelos	-
classificação	
• Sistemas multiprocessados
• Multicomputadores
• Processadores vetoriais
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Sistemas paralelos
Computação distribuída Computação paralela
Multicomputadores
Memória compartilhada
NUMA
UMA
Processadores vetoriais
Switch centralizado
Switch decentralizado
Bus
Troca de mensagens Espaço de end. único
• Tarefa: achar inconsistências na figura acima em relação aos slides anteriores.
• Considere dois níveis abaixo. Análise pode ser diferente para cada um deles?
• Programação -> memória compartilhada ou troca de mensagens?
• Arquitetura -> como é a disposição física dos componentes?
Sistemas multiprocessados
Exercício
Relógio físico comum
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Caracterização	de	sistemas	paralelos
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Caracterização	de	sistemas
paralelos
• Distinção/caracterização é importante para projeto de 
algoritmos.
• Considerar latências
• Muito acesso aos mesmos dados, muito acesso a dados locais e 
pouco acesso a dados distribuídos, etc.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Caracterização	de	sistemas
paralelos
• Uso primário de sistemas paralelos: maior vazão através da 
divisão da carga entre os processadores.
• Tarefas que podem ser melhor aceleradas são as que podem 
ser particionadas em subtarefas com pouca comunicação.
• Ex.:Muitas operações sobre vetores e matrizes, comuns em 
aplicações científicas.
• Máquinas paralelas foram objeto de pesquisa teórica e de 
sistemas em 1980, entretanto não se provaram 
economicamente viáveis na época.
• Poucas aplicações populares tiravam vantagem de paralelismo.
• Aumento da capacidade de processamento de PCs.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Taxonomia
• Processamento (Flynn):
• SISD, MISD, SIMD, MIMD
• Programação
• Memória compartilhada
• Troca de mensagens
• PRAM – Parallel Random Access Machine
• LogP vs. PRAM
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Taxonomia	– Flynn
• Quatro “modos” de processamento classificando:
• Como é o processamento de instruções 
• Quais são os dados de entrada de cada processador
• Single Instruction, Single Data – SISD
• Single Instruction, Multiple Data – SIMD
• Multiple Instruction, Single Data – MISD
• Multiple Instruction, Multiple Data – MIMD
Prof. Luiz Fernando Bittencourt IC - UNICAMP
SISD
• Single instruction stream, single data stream
• Modo “convencional” no paradigma de Von Neumann
• Uma CPU
• Uma unidade de memória
• Conectados por bus
• Fig 9
Prof. Luiz Fernando Bittencourt IC - UNICAMP
SIMD
• Single instruction stream, multiple data stream.
• Processamento: múltiplos processadores homogêneos.
• Mesma instrução.
• Itens de dados distintos.
• Processamento de arrays e matrizes.
• Co-processamento (MMX, SSE).
• Fig 10
Prof. Luiz Fernando Bittencourt IC - UNICAMP
MISD
• Multiple instruction stream, single data stream.
• Operações diferentes
• Mesmo dado
• Fig 11
Prof. Luiz Fernando Bittencourt IC - UNICAMP
MIMD
• Multiple instruction stream, multiple data stream.
• Instruções diferentes.
• Dados diferentes.
• Modo de operação de sistemas distribuídos e paralelos em 
geral.
• Sem relógio comum.
• Fig 12
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Troca	de	mensagem,	memória	
compartilhada,	PRAM,	LogP
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Memória	compartilhada
• Paradigmas de programação para sistemas paralelos tem 
uma forte correspondência com políticas de acesso à 
memória em multiprocessadores.
• Diferença fundamental: uso de memória compartilhada 
ou programação usando troca de mensagens.
• Memória compartilhada: cada processador tem acesso 
total à memória compartilhada; comunicação entre 
processos se dá através da memória (acesso 
concorrente necessita sincronização explícita).
• Troca de mensagens: comunicação entre 
processadores feita de forma explícita através de 
comandos send e receive.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Memória	compartilhada
• Tem espaço de endereçamento comum no sistema.
• Comunicação através de variáveis compartilhadas.
• Variáveis de controle para sincronização entre processos (p.ex. 
semáforos e monitores).
• Paradigma de programação (memória compartilhada ou troca de 
mensagem) nem sempre corresponde à organização de memória do 
sistema alvo.
• Troca de mensagem pode ser usada tanto em arquiteturas de memória 
compartilhada quanto de troca de mensagens.
• Em memória compartilhada, uma troca de mensagem pode ser 
implementada como uma simples cópia de memória.
• Memória compartilhada distribuída pode ser emulada através de uma 
camada de software adicional em arquitetura de troca de mensagens.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Modelos	PRAMe	 LogP
• Modelos para projeto e análise de complexidade de 
algoritmos paralelos.
• Descrever/projetar algoritmos independente da máquina 
utilizada
• Modelos que abstraem detalhes
• Foco em aspectos importantes 
• Esconde detalhes “desnecessários”
• Modelos podem ser simulados
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Modelos	PRAMe	 LogP
• PRAM – Parallel Random Access Machine
• Máquina ideal com memória centralizada e 
compartilhada, processadores síncronos.
• Acesso a uma célula: admite modelar acesso exclusivo 
ou concorrente.
• Células diferentes podem ser acessadas 
concorrentemente.
• Simples, porém não considera custos de comunicação 
entre processadores.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Modelos	PRAMe	 LogP
• Modelo PRAM irreal, especialmente em sistemas distribuídos, 
devido à suposição de comunicação sem custo entre 
processadores.
• LogP
• Considera custo de comunicação entre processadores.
• L: limite superior no atraso em uma troca de mensagem.
• o: overhead – tempo que um processador gasta enviando ou 
recebendo uma mensagem, durante o qual não efetua outra 
operação.
• g: Gap – tempo mínimo entre transmissões ou recepções 
consecutivas de mensagens (1/BW).
• Limita número de mensagens simultâneas a
• Modelo assíncrono.
• Fig 13 + exemplo
⇠
L
g
⇡
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Modelos	PRAMe	 LogP
• Sugestão de melhoria no desempenho do exemplo?
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Acoplamento,	paralelismo,	
concorrência	e	granularidadeProf. Luiz Fernando Bittencourt IC - UNICAMP
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Acoplamento
• Grau de acoplamento (hardware ou software): 
interdependência e “amarração” e/ou homogeneidade 
entre módulos.
• Fortemente acoplados (SIMD, MISD / relógio comum) 
ou fracamente acoplados.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Acoplamento
• Ex MIMD:
• Multiprocessadores fortemente acoplados (com memória 
compartilhada Uniform Memory Access). Bus (Sequent, Encore) ou 
switch (NYU)
• Multiprocessadores/computadores fortemente acoplados (com 
memória compartilhada Non-Uniform Memory Access – SGI Origin
2000, Sun Ultra HPC – ou troca de mensagens – hipercubo, torus).
• Multicomputadores (sem memória compartilhada ou relógio comum) 
fracamente acoplados fisicamente próximos. Bus (NOW + LAN ou 
Myrinet), ou usando uma rede genérica, processadores podem ser 
heterogêneos. Sistema distribuído (sem memória compartilhada ou 
relógio comum) com característica de sistema paralelo (processadores 
próximos). Abordagens diferentes de redes de longa distância.
• Multicomputadores fracamente acoplados, fisicamente distantes. Noção 
convencional de sistemas distribuídos.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	/	speedup em	um	
sistema	específico
• Speedup relativo de um programa em uma dada 
máquina específica.
• Depende do número de processadores e 
mapeamento do código nesses processadores.
• Razão entre o tempo de execução T(1) em um 
único processador e tempo T(n) com n
processadores.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	em	um	programa	
paralelo/distribuído
• Medida agregada da porcentagem de tempo que todos os 
processadores estão executando instruções de CPU ao invés 
de aguardar comunicação, seja por memória compartilhada 
ou troca de mensagens.
• Se a medida agregada é somente em função do código, 
paralelismo é independente de arquitetura.
• Caso contrário, definição de paralelismo se assemelha à de 
speedup.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Concorrência	de	um	programa
• Termo mais amplo
• Usado no contexto de sistemas distribuídos
• Razão entre o número de operações locais (sem 
comunicação / memória compartilhada) e o 
número total de operações.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Paralelismo: condição que aparece quando pelo menos duas 
threads estão executando simultaneamente.
• Concorrência: condição existente quando pelo menos duas 
threads estão progredindo. 
• Paralelismo: programação para execução de computação 
simultânea (possivelmente relacionada).
• Concorrência: programação como composição de processos 
(no termo amplo) executando independentemente.
• Paralelismo: quando tarefas executam ao mesmo tempo.
• Concorrência: quando tarefas podem começar, executar, e 
terminar em intervalos de tempo sobrepostos. Não significa 
necessariamente que executarão ao mesmo tempo (e.g., 
multitasking em processadores de núcleo único).
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Problema: mover uma pilha de manuais de linguagens obsoletas 
para uma fornalha.
• Apenas 1 roedor demora muito.
• http://concur.rspace.googlecode.com/hg/talk/concur.html
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Mais roedores.
• Não ajuda, precisamos de mais carrinhos.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Mais roedores e mais carrinhos.
• Mais rápido, mas há gargalos na pilha e na fornalha.
• Necessidade de sincronizar os roedores: uma mensagem 
(comunicação entre roedores) pode resolver.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Dobrar tudo
• Remover gargalo, tornando-os independentes.
• Consome entrada duas vezes mais rápido.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Projeto não é automaticamente paralelo.
• E se somente um roedor move-se em um dado instante de 
tempo?
• Continua sendo concorrente (i.e., o projeto), mas não paralelo.
• Entretanto, é automaticamente paralelizável.
• Essa composição concorrente habilita outros modelos.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Outro projeto.
• Três roedores em ação, mas provavelmente com atrasos.
• Cada roedores é um procedimento independente, mais a 
coordenação (comunicação).
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Adicionar novo roedor para carregar os carrinhos vazios.
• Organizando tudo corretamente (não trivial), é quatro vezes 
mais rápido que o projeto original de 1 roedor.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Quatro procedimentos distintos:
• Carregar manuais no carrinho
• Mover carrinho até a fornalha
• Descarregar carrinho na fornalha
• Retornar o carrinho vazio
• Diferentes projetos concorrentes permitem diferentes 
maneiras de paralelização.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Mais paralelização:
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Ou nenhuma paralelização (se cada um trabalha em determinado 
intervalo de tempo diferente dos outros), mas continua sendo uma 
solução concorrente.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Outro projeto
• Pilha adicional
• 100 pilhas: melhora?
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Paralelizando da maneira usual
• Executar mais procedimentos concorrentes para aumentar vazão
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Ou ainda...
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Usando todas as técnicas: 16 geomídeos trabalhando.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Paralelismo	vs.	Concorrência
• Existem muitas formas de quebrar um processo em pedaços 
menores: projeto concorrente.
• Paralelização pode ser implementada de forma que sua 
corretude é “fácil”.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Granularidade	de	um	programa
• Razão entre quantidade de computação e quantidade de 
comunicação do programa paralelo/concorrente.
• Granularidade alta (baixa): relativamente mais (menos) 
instruções produtivas de CPU comparadas ao número de 
vezes que os processadores comunicam-se.
• Baixa granularidade: se encaixa melhor em sistemas 
fortemente acoplados.
• Latência pode degradar vazão.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Sistemas	de	troca	de	mensagem	
versus	sistemas	de	memória	
compartilhada
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Troca	de	mensagens	e	
memória compartilhada
• Sistemas de memória compartilhada: espaço de endereço 
comum compartilhado no sistema.
• Comunicação se dá através de variáveis compartilhadas
• Variáveis de controle para sincronização entre processadores 
(semáforos, monitores).
• Sistemas de multicomputadores que não têm espaço de 
endereçamento comum fornecido pela arquitetura/hardware 
necessariamente comunicam-se por troca de mensagens.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Troca	de	mensagens	e	
memória compartilhada
• Conceitualmente mais fácil programar/depurar memória 
compartilhada que troca de mensagens.
• A abstração chamada “memória compartilhada” é algumas 
vezes utilizada para simular um espaço de endereçamento 
comum.
• Em sistema distribuído: memória compartilhada distribuída.
• Implementá-la tem certo custo, mas simplifica tarefa de 
programação.
• Comunicação por troca de mensagem pode ser simulada por 
comunicação via memória compartilhada (e vice-versa).
• Os dois paradigmas são equivalentes.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
TM	àMC
• Emular troca de mensagem em sistema de memória 
compartilhada (TM à MC).
• Espaço de endereçamento compartilhado pode ser 
particionado em conjuntos disjuntos, com uma parte para 
cada processador.• Operações send e receive podem ser implementadas pela 
escrita e leitura do espaço de endereçamento do 
destinatário/remetente.
• Especificamente, um espaço separado pode ser reservado 
como “caixa de correio”.
• Uma troca de mensagem Pi-Pj pode ser emulada por uma 
escrita de Pi na caixa de correio, e então uma leitura de Pj.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
TM	àMC
• No caso mais simples, assume-se que essas caixas de 
correio têm tamanho ilimitado.
• As operação de escrita/leitura precisam ser controladas 
utilizando primitivas de sincronização para informar 
destinatário/remetente após o envio/recebimento dos 
dados.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
MC	àTM
• Emular memória compartilhada em sistema de troca de 
mensagem (MC à TM).
• Envolve o uso de operações de send e receive para realizar 
operações de escrita e leitura.
• Cada local compartilhado pode ser modelado como um 
processo separado.
• A escrita em um local compartilhado é emulada pelo envio 
de uma mensagem de atualização para o processo dono 
daquele espaço.
• A leitura de um local compartilhado é emulada pelo envio 
de uma mensagem de query para o dono do processo.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
MC	àTM
• Acessar memória de outro processador é caro (requer 
send/receive).
• Emular memória compartilhada pode ser atraente do 
ponto de vista do programador, mas deve ser considerado 
que é apenas uma abstração em sistemas distribuídos.
• Latências envolvidas nas operações de leitura/escrita 
podem ser altas mesmo usando emulação de memória 
compartilhada, pois, por baixo dos panos, ocorre 
comunicação através de uma rede.
Prof. Luiz Fernando Bittencourt IC - UNICAMP
Troca	de	mensagens	e	
memória	compartilhada
• Aplicações podem combinar memória compartilhada e troca de 
mensagens.
• Em um multicomputador MIMD, cada “processador” pode ser 
por si só um sistema multiprocessado fortemente acoplado com 
memória compartilhada.
• No sistema multiprocessado, processadores comunicam-se via 
memória compartilhada.
• No sistema de multicomputadores, comunicam-se via troca de 
mensagens.
• Sistemas de troca de mensagem são mais comuns e mais 
adequados para sistemas distribuídos amplos, e portanto mais 
extensivamente estudados em sistemas distribuídos.