Capítulo 8
Sistemas com Múltiplos
Processadores
Motivação: Poder Computacional. Ainda há tarefas
complexas cujo demanda de processamento não está
satisfeita. Estamos no limite da velocidade do relógio para
permitir em certo tamanho que o sinal trafegue de uma
extremidade a outra e volte dentro de um único ciclo. Uma
solução é a adoção de múltiplas CPUs.
Soluções
a) Multiprocessador de memória compartilhada;
acesso de 2 a 50 ns;
b) Multicomputador com troca de mensagens;
acesso de 10 a 50 µs;
c) Sistema distribuído com rede de longa distância;
acesso de 10 a 50 ms.
Multiprocessadores (1)
Sistema computacional no qual duas ou mais CPUs compartilham
acesso total a uma RAM comum.
UMA – Uniform Memory Access: tempo de acesso a memória é
uniforme.
(1) Multiprocessadores baseados em barramento:
a) Sem utilização de cache; contenção no barramento;
b) Com utilização de caches; coerência de cache;
c) Com memória privadas e caches; gerência mem.
Multiprocessadores (2)
Problema de (1): limite do barramento;
(2) Multiprocessadores com chaves de crossbar:
Reduz a contenção.
Multiprocessadores (3)
Problema de (2): excessivo número de cruzamentos –
possível para sistemas de porte médio;
(3) Multiprocessadores com redes de comutação multiestágio:
a) Uma chave 2x2:
2 entradas e 2 saídas;
b) Uma mensagem que chega na entrada e é chaveada
para saída
Endereço dentro do módulo
Multiprocessadores (3)
(3) Multiprocessadores com redes de comutação multiestágio:
Número do módulo
Por exemplo, Endereço do módulo 110.
Em cada estágio, Bit 1 roteia para baixo, Bit 0 roteia para cima.
Reduz número de chaves da solução (2).
Multiprocessadores (4)
Problema de UMA: Hardware caro, limitado a não mais que
100 CPUs;
NUMA – Nonuniform memory access.
Características que diferenciam máquinas NUMA:
1. Espaço de endereçamento único visível a todas as CPUs
2. Acesso à memória remota via comandos
- LOAD
- STORE
3. Acesso à memória remota mais lento que acesso à
memória local
Multiprocessadores (5)
(1) Multiprocessador com base em diretório (cache-coherent):
Mantém um cache localizando dados através de um diretório
Memória dividida em linhas de cache
a)Multiprocess. de 256 nós com base em diretório: base de
dados que informa onde cada linha da cache está. A
coerência é necessária: quem está alterando que bloco de
memória. Hw especial de acesso rápido ao diretório.
Multiprocessadores (5)
(1) Multiprocessador com base em diretório:
CPUs mandam msg
pedindo acesso a
memória. CPU
destino atualiza
diretório.
b)Divisão de end. de
mem. de 32 bits em
campos.
c) O diretório no nó
36. A linha 2 do nó
36 está na cache do
nó 82.
Há mta troca de msg! => Projetos atuais: chips Multicore,
onde as trocas são rápidas no interno do chip.
SOs para Multiprocessadores (1)
Cada CPU tem seu próprio SO.
O código do SO é compartilhado, mas são independentes.
Inconvenientes: não permite compartilhamento de processos –
processos de um usuário só rodam na CPU1 enquanto CPU2 pode
estar ociosa; alocação de memória fixa; caches independentes –
difícil manter coerência.
Modelo dificilmente usado.
SOs para Multiprocessadores (2)
Modelo mestre-escravo.
SO na CPU 1 que atribui tarefas para as demais CPUs.
Inconvenientes: Mestre se torna gargalo se muitas CPUs. (como ele
que executa o SO, chamadas de sistema dos outros tem que
passar por ele).
Ineficiente para multiprocessadores grandes.
SOs para Multiprocessadores (3)
SMP - Symmetric Multiprocessor. (elimina assimetria mestreescravo)
Balanceia dinamicamente processos e memória, havendo um conjunto
único de tabelas, sem mestre. 2 ou + CPUs executando o mesmo código
pode haver conflitos. Mutexes permitem o compartilhamento do código
do SO, que é quebrado em partes independentes. Dificuldade: quebrar
em regiões críticas que possam ser executadas simultaneamente por
CPUs diferentes sem interferência.
Risco de impasse: 2 tabs usadas por 2 CPUs!
Sincronização em Multiprocessadores
Cuidados importantes e difíceis para o funcionamento :
1. Sincronização: desabilitar interrupções funciona para
sincronização com um processador. Com mais de um não
funciona pois só desabilita em uma CPU. Ex: falha de TSL com 2
CPUs que não reservam barramento:
2. Escalonamento: O problema agora é bidimensional: Qual o
próximo processo a executar em qual CPU?
Escalonamento de
Multiprocessadores (1)
(1) Threads independentes: emprega-se uma única estrutura de
dados de escalonamento para os threads prontos no sistema.
Em (a) todas as CPUs estão ocupadas e há threads esperando. Ao
desocupar, atribuir o próximo thread, como se fosse
monoprocessador. (Escalonamento em tempo )
Escalonamento de
Multiprocessadores (2)
(2) Threads em grupo.
Ex: make – o que adianta compilar 9 tarefas simultaneamente se
precisa esperar a décima?
Se os threads se comunicam muito, é melhor fazê-los executar
ao mesmo tempo. Escalonador verifica se há CPUs livres quanto
número de threads. Se não tiver, espere. Não libera
individualmente mas em grupo. (Escalonamento em espaço)
PG 338
Escalonamento de
Multiprocessadores (3)
Threads em grupo – problema:
Problema que pode acontecer se escalonados independentemente,
mas trocam mensagens: A0 mandou msg para A1 que só será
recebida 100ms depois quando A1 executar. A1 responde
imediatamente, mas só será recebida por A0 mais 100ms depois.
Requisições e respostas a cada 200ms.
PG 339
Escalonamento de
Multiprocessadores (4)
Escalonamento em bando
1. Grupos de threads relacionados são escalados como uma unidade (bando)
2. Todos os membros do bando executam simultaneamente em diferentes CPUs com
compartilhamento de tempo
3. Todos os membros de um bando iniciam e finalizam juntos suas fatias de tempo
(se um thread termina antes, sua CPU permanece ociosa até o fim do quantum).
PG 339
Multicomputadores (1)
CPUs fortemente acopladas que não compartilham memória.
Também conhecidos como
– computadores clusters
– clusters de estações de trabalho (COWs – cluster or
workstations)
Os nós podem se conectar com diferentes topologias.
O nó tem CPU, memória e interface de rede. Normalmente sem
teclado, mouse, monitor. Mais fáceis de construir (como hardware)
do que multiprocessadores.
Compartilham sistemas de arquivos, unidos por rede dedicada de
alta velocidade, sistema de gerenciamento comum.
PG 340
Multicomputadores (2)
Posição das placas de interface de rede (NIC) em um multicomputador.
A NIC tem RAM própria, pois se os dados não são armazenados em
tempo real são perdidos. A NIC pode ter DMA ou até CPU completa
(processadores de rede – ops: 2 processadores compartilhando RAM
– já viu este problema?). Note que os números 1 a 5 são cópias
PG 342
RPCs
• Exemplo de uma chamada no cliente:
callrpc (char *host /* Name of server host */,
u_long prognum /* Server program number */,
u_long versnum /* Server version number */, xdrproc_t inproc /* XDR filter to encode arg */, char
*in /* Pointer to argument */, xdr_proc_t outproc /* Filter to decode result */,
char *out /* Address to store result */, char *nettype /* For transport selection */);
--------------------------------------------------------------------------------------------------------------------------------/** * rls.c: remote directory listing client */ #include <stdio.h> #include <strings.h> #include
<rpc/rpc.h> #include "rls.h"
main (argc, argv) int argc; char *argv[];
{ char dir[DIR_SIZE]; /* call the remote procedure if registered */
strcpy(dir, argv[2]);
read_dir(argv[1], dir); /* read_dir(host, directory) - spew-out the results and bail out of here! */
printf("%s\n", dir); exit(0);
}
read_dir(host, dir) char *dir, *host;
{ extern bool_t xdr_dir(); enum clnt_stat clnt_stat;
clnt_stat = callrpc ( host, DIRPROG, DIRVERS, READDIR, xdr_dir, dir, xdr_dir, dir);
if (clnt_stat != 0) clnt_perrno (clnt_stat);
}
RPCs
Os nós do multicomputador se comunicam por msg (muita E/S) ou
pela técnica de Remote Procedure Calls: Um programa é capaz de
chamar um procedimento em outra máquina.
Cliente ligado a stub: representa o procedimento servidor no
espaço do endereçamento do cliente. Parâmetros da chamada do
cliente são colocados na pilha de modo convencional.
PG 346
Multicomputadores (3)
Cuidados importantes:
1. Escalonamento: no multiprocessador todos os processos
residem na mesma memória: uma CPU termina tarefa, pega
um processo e executa. No multicomputador, cada nó tem sua
própria memória e seus próprios processos. Uma vez
associado a um nó é lá que o processo ficará. Tomar boa
decisão na criação. Após criação, pode ser usado algoritmo
de escalonamento local, porém pode também se usar
escalonamento sincronizado entre as CPUs que minimize o
tempo de CPU parada.
2. Balanceamento de Carga: A associação inicial de que processo
deve ir para qual nó é importante de maneira a manter
equilibrado o uso de processador, uso de banda e equidade.
PG 350
Balanceamento de Carga (1)
Algoritmos de Alocação de Processador – decisão importante:
variam de acordo com objetivos e informações conhecidas.
Algoritmo Determinístico teórico de Grafos: Processos estão ligados
com as arestas representando o fluxo médio entre eles (ex:
Mbps). Há k CPUS (nós). Encontrar uma maneira de dividir o
grafo em k subgrafos disjuntos e cada subgrafo rodar em um nó.
Minimizar o tráfego intergrupo. A esq a soma dá menos unidades
que a dir.
PG 351
Balanceamento de Carga (2)
Algoritmo Heurístico distribuído iniciado pelo emissor: Um
processos ao ser criado roda no nó que o criou se este não
estiver sobrecarregado. Se estiver, seleciona outro nó
aleatoriamente para sondar sua ocupação. Se nenhum nó for
encontrado em N tentativas, ele roda na máquina onde foi
gerado. Figura 8.25 (a)
PG 351
Balanceamento de Carga (3)
Algoritmo Heurístico distribuído iniciado pelo receptor: Sempre
que um processo finaliza, o sistema verifica se ele dispões de
trabalho suficiente. Se não escolhe uma máquina aleatoriamente e
pede serviço. Sonda até N máquinas, e se não tem serviço pára de
procurar. Após certo tempo retoma a sondagem. Figura 8.25 (b). É
melhor ter sobrecarga extra quando o sistema não está
sobrecarregado. Abordagem híbrida: livrar-se quando tem muito
trabalho e adquirir trabalho quando está livre.
PG 352
Virtualização (1)
Motivação: Pode acontecer de uma empresa ter múltiplos
servidores (e-mail, web, ftp…) conectados por rede de alta
velocidade (multicomputador), mas não porque a carga é
excessiva, mas por segurança: se um serviço falhar, os outros
continuam a funcionar.
Virtualização: Diferentes servidores funcionam em diferentes
máquinas virtuais, hospedadas em um único computador,
mantendo o modelo de falha parcial a baixo custo e fácil
manutenção. É a base da chamada computação elástica.
PG 353
Justificativa: A maioria das interrupções nos serviços não é por
hardware, mas pelo conjunto de software inchado, não
confiável e com erros (em especial SOs!)
Virtualização (2)
Motivação (ainda):
• O único software que rodaria no modo núcleo seria o
hipervisor que tem menos linhas de código que o SO, e
portanto menos erros.
• Economia em hardware (menos máquinas) implica também
economia de energia;
• Cada aplicação leva consigo seu próprio ambiente; um dos
benefícios é permitir rodar aplicações mais antigas e novas;
outro benefício é não precisar particionar o disco e assim ter
que reiniciar o computador para mudar de SO.
PG 353
Virtualização (3)
Conceito utilizado:
• Emulação: as instruções são executadas via software
permitindo emular um hardware totalmente diferente do
hardware da máquina real. Ex: emuladores de consoles de
video-games emulam o hardware do video-game onde o jogo
“pensa” estar executando no video-game mas na verdade esta
sendo executado por um emulador no computador. Através da
emulação pode-se executar programas para outras
arquiteturas, como por exemplo emular um MACintosh no PC,
ou um hardware totalmente diferente.
• A emulação tem desempenho pior do que a execução no
ambiente nativo.
Hipervisores Tipo 1
Ele é o SO, o único no modo núcleo, gerencia máquinas virtuais e
processos.
O SO hóspede acredita estar no modo núcleo, mas de fato está no
modo usuário (Modo Núcleo virtual). Em CPUs com Virtualization
Technology (VT), quando uma instrução falha (privilegiada
executando em modo usuário), dispara uma armadilha para o
núcleo (hipervisor) que inspeciona a origem da instrução (SO ou
processo do user), permitindo ou não sua execução, emulando ou
não. VT foi introduzido no Intel Core 2.
PG 354
Hipervisores Tipo 2
Hipervisor do tipo 2 é um programa de usuário sobre um SO
hospedeiro.
VMWare: carrega um SO hóspede; na carga varre o binário
procurando blocos de instruções que terminem com instruções que
alterem o fluxo de controle: (jump, call, trap…). Acontece uma
tradução binária: substitui instruções sensíveis (q só podem ser
executadas no modo núcleo) por instruções do VMWare que as
emula.
PG 355
Hipervisores Tipo 2
Após executar um bloco básico o controle retorna ao VMWare
que localiza o próximo bloco. Blocos vão sendo traduzidos,
armazenados e executados. Nenhuma instrução vinda do SO
hóspede é executada pelo hardware real, mas emuladas.
Máquinas que não tem VT podem usar este tipo de
virtualização.
Estudos mostram que máquinas com VT também tem seu custo
como problemas de cache, TLBs… e dependendo da carga de
trabalho pode ter desempenho pior. Com a tradução prévia
antecipa-se o conhecimento de desvios e não se arruinam
caches.
PG 355
Ferramentas Virtuais
Um desenvolvedor de software pode construir uma máquina
virtual, carregá-la com o SO, compiladores, bibliotecas, com
suas dependências, códigos desenvolvidos, congelar e
disponibilizar aos clientes.
Vantagem: pacote pronto com detalhes necessários ocultos dos
clientes.
Exemplo: Mininet
Aplicações Virtuais: nome dado ao pacote completo.
PG 359
VirtualBox
Uma das ferramentas de virtualização disponíveis (Oracle):
https://www.virtualbox.org/
“Presently, VirtualBox runs on Windows, Linux, Macintosh, and
Solaris hosts and supports a large number of guest operating
systems including but not limited to Windows (NT 4.0, 2000,
XP, Server 2003, Vista, Windows 7, Windows 8), DOS/Windows
3.x, Linux (2.4, 2.6 and 3.x), Solaris and OpenSolaris, OS/2, and
OpenBSD.”
Uma máquina virtual (Virtual Machine – VM) pode ser , definida
como “uma duplicata eficiente e isolada de uma máquina real”.
A IBM define uma máquina virtual como uma cópia isolada de
um sistema físico, totalmente protegida.
VirtualBox
Esta cópia pode ser importada , exportada, configurada para
atender a demanda.
A extensão .VDI é o formato nativo do VirtualBox e significa
apenas Imagem de Disco Virtual.
A extensão .VMDK é o formato original da VMWare, aceito pelo
VirtualBox.
Máquinas Virtuais
em CPUs multinúcleos
Ex: Se tivermos uma CPU com 4 núcleos e em cada um podem
executar 8 máquinas virtuais, teremos uma CPU que pode
ser configurada como multicomputador de 32 nós,
dependendo da necessidade do software.
Flexibilização: a aplicação decide o modelo.
Não é comum ainda, mas é concebível que as VMs
compartilhem memória. Neste caso poderia ser um
multiprocessador virtual.
PG 359
Nossos programas não estão preparados para usufruir desta
possibilidade. Como será a licença que normalmente é para
rodar em um CPU?
Paravirtualização
SO Paravirtualizado: instruções sensíveis foram removidas e
substituídas por uma chamada de uma API (do hipervisor)
para realizar operações como E/S, modificação de registros
internos, etc. Não emular melhora o desempenho.
O hipervisor pode ter parte que faz emulação (qdo código do
SO é fechado) e parte que é apenas um micronúcleo.
PG 356
Com milhares
de linhas de
código e não
milhões...
Virtualização de Rede (1)
Infra-estrutura tradicional
de rede
http://www.ibm.com/developerworks/linux/lib
rary/l-virtual-networking/
Infra-estrutura de rede
virtualizada.
OBS: Linux incorpora um
switch de nível 2 simples
dentro do kernel.
37
Virtualização de Rede (2)
Switch virtual distribuído: Liga vNics e vNics a Nics.
“Enables cross-server bridging , making the underlying server
architecture transparent. A virtual switch within one server can
transparently join with a virtual switch in another server making
migration of VMs between servers (and their virtual interfaces) much
simpler, because they can attach to the distributed virtual switch in
another server and transparently join its virtual switched network”.
OpenvSwitch foi comprado pela VMWare . É muito utilizado por cloud
38
Virtualização com FlowVisor (1)
A rede física pode ser separada entre os 3
controladores oferecendo uma parte do controle
para cada um, de acordo com a política.
Nível Aplicação
39
Sistemas Distribuídos (1)
CPUs fracamente acopladas que não compartilham memória.
Cada nó é um computador completo, nós estão espalhados ao redor
do mundo.
O objetivo é transformar um grupo de máquinas fracamente
conectadas em um sistema coerente com base em um conceito.
Fornecer algo que unifique o sistema.
PG 360
Sistemas Distribuídos (2)
Vantagem dos Sistemas Distribuídos: comps podem ser usados por
grande variedade de aplicações;
Desvantagem: programação das aplicações é difícil pois falta modelo
de plataforma comum.
Middleware:
camada de software
para uniformizar
SOs e hardwares
PG 361
Middleware
Oferece certas estruturas de dados e operações que permitem que
processos e usuários em máquinas distintas se relacionem em
grupo de um modo consistente.
• Com base em documento: qualquer coisa é um documento –
base da Web -> http
• Com base em sistema de arquivo: qualquer coisa é um arquivo –
sistema global em q usuários escrevem e leem;
• Com base em objetos compartilhados: qualquer coisa é um
objeto. CORBA – sistema cliente-servidor onde clientes invocam
operações sobre objetos nos servidores.
• Com base em coordenação: processos se comunicam por espaço
de tuplas (estrutura de dados) global. Processos podem inserir
ou remover tuplas no espaço sem considerar como e onde estão
armazenadas (Linda, Jini).
PG 366
a 374
Grade
Coleção grande geograficamente dispersa e normalmente
heterogênea de máquinas conectadas por uma rede privada ou
através da Internet e que oferece um conjunto de serviços a seus
usuários.
Compara-se a um supercomputador virtual, porém em diferentes
domínios administrativos com um middleware comum.
Cuida de aspectos como autenticação, conexão de usuários remotos,
descoberta e anúncio de recursos, escalonamento, etc.
Quando usuário tem trabalho o sw da grade determina onde há
recursos e envio o trabalho para lá.
Exemplo de middleware popular no mundo das grades:
toolkit Globus.
PG 375