Fundamentos de sistemas distribuídos

Prévia do material em texto

DESCRIÇÃO
Os conceitos básicos dos sistemas distribuídos, das memórias compartilhadas e distribuídas e
das arquiteturas de sistemas paralelos e distribuídos.
PROPÓSITO
Introduzir os conceitos fundamentais de sistemas distribuídos, bem como conhecer as técnicas
que possibilitaram que esse tipo de arquitetura se desenvolvesse. Saber diferenciar os diversos
conceitos dentro do tema e ter conhecimento de algumas arquiteturas de sistemas distribuídos,
identificando vantagens e desvantagens.
PREPARAÇÃO
Tenha à mão um aplicativo de planilha eletrônica e uma calculadora ou use a calculadora de seu
smartphone/computador.
OBJETIVOS
MÓDULO 1
Descrever os conceitos básicos de sistemas distribuídos
MÓDULO 2
Diferenciar memória compartilhada e memória distribuída
MÓDULO 3
Diferenciar paralelismo de dados e paralelismo de tarefas
MÓDULO 4
Identificar as arquiteturas de sistemas paralelos e distribuídos
INTRODUÇÃO
Vivemos um mundo onde a expressão “estar conectado” diz respeito a uma necessidade primária
das pessoas. Uma das maiores frustrações do ser humano moderno é estar desconectado da
internet. Ao viajarmos para um hotel, uma pousada no campo, as questões que sempre surgem
são: o estabelecimento fornece serviço de Wi-Fi? O sinal de minha operadora funciona no local?
Perguntas desse tipo denunciam a extrema necessidade de participar da internet.
A internet é nada mais que um sistema distribuído muito grande. Por meio dela, podemos
conectar sites, redes sociais, mecanismos de busca, jogos on-line, ou seja, milhões de serviços
que estão disponíveis praticamente em todos os lugares do mundo.
Esses serviços, no entanto, estão funcionando em máquinas dispersas por todo o mundo,
interligadas entre si por algum tipo de rede. Para que esses serviços possam ser providos, as
aplicações conectam usuários através de sites e serviços, como, e-mail, transferência de
arquivos, chat etc. Para isso, as diversas aplicações, sendo executadas nos diversos
computadores, precisam se comunicar entre si e o fazem normalmente por mensagens.
Neste conteúdo, apresentaremos algumas das nomenclaturas, bem como técnicas e
metodologias que deram base aos diversos sistemas distribuídos que estão disponíveis para as
pessoas atualmente.
MÓDULO 1
 Descrever os conceitos básicos de sistemas distribuídos
CONCEITOS DE SISTEMAS DISTRIBUÍDOS
Como explanamos no início deste tema, praticamente tudo com que interagimos em nossos
celulares e em computadores conectados à internet são sistemas distribuídos.
Nesta lista não exaustiva podemos citar:
Mecanismos de busca, como Google, Bing etc.
Sistema de Home Banking
Sistema de Home Broker
Redes sociais
Sistemas de streaming de áudio e de vídeo, como o YouTube
Sistemas de Educação a Distância
Internet das Coisas (em inglês, Internet of Things – IoT)
Sistemas de monitoramento ambiental
Sistemas remotos de monitoramento de saúde
Computação distribuída em grid para aplicação em ciências
Dificilmente, conseguiríamos elencar todos os tipos de aplicação que os sistemas distribuídos
permitem que sejam construídos.
Agora, passemos a uma definição formal.
UM SISTEMA DISTRIBUÍDO É AQUELE NO QUAL OS
COMPONENTES LOCALIZADOS EM COMPUTADORES
INTERLIGADOS EM REDE SE COMUNICAM E
COORDENAM SUAS AÇÕES APENAS PASSANDO
MENSAGENS.
(COULOURIS et al., 2013, p. 1)
Os computadores conectados por uma rede podem estar em continentes diferentes, em um
mesmo prédio ou sala, ou ainda a milhares de quilômetros de distância. A definição de Coulouris
tem as seguintes consequências significativas:
CONCORRÊNCIA
Em uma rede de computadores, a execução simultânea de programas é a regra geral. Enquanto
você executa determinada tarefa no celular, também pode executar uma outra tarefa que
eventualmente acesse a mesma base de dados que outros milhares de usuários estejam
acessando. A capacidade do sistema de lidar com recursos compartilhados pode ser aumentada
adicionando mais recursos, como, por exemplos mais celulares, computadores ou mesmo
dispositivos da IoT. A coordenação de programas de execução simultânea que compartilham
recursos também é um tópico importante e recorrente.
AUSÊNCIA DE UM RELÓGIO GLOBAL
Quando as diversas aplicações precisam cooperar, elas coordenam suas ações trocando
mensagens. Muitas vezes, essa coordenação depende de uma ideia compartilhada do momento
em que as ações dos programas ocorrem. No entanto, existem limites para a precisão com a qual
os computadores em uma rede podem sincronizar seus relógios, não havendo uma noção global
única da hora correta. Isso é consequência direta do fato de a única comunicação ser o envio de
mensagens pela rede.
FALHAS INDEPENDENTES
A prática nos mostra que todos os sistemas de computador podem falhar. Pensando nisso, o
responsável pelo sistema deve planejar as consequências de possíveis falhas e as respostas
apropriadas para cada tipo de falha. Uma falha em determinada rede pode resultar no isolamento
dos dispositivos que estão conectados a ela, mas isso não significa que eles parem de funcionar.
Da mesma forma, a falha de um dispositivo, ou o encerramento inesperado de um programa em
algum lugar do sistema, não é imediatamente detectada ou informada aos outros componentes
com os quais ele se comunica. Cada componente do sistema pode falhar independentemente,
deixando os outros ainda em execução.
A principal motivação para construir e usar sistemas distribuídos é o compartilhamento de
recursos, sejam eles componentes de hardware, como discos de armazenamento, impressoras,
banco de dados, fluxo de informações que vemos em redes sociais, enfim, tudo que pode ser
transformado em informação digital.
TAXONOMIA DE FLYNN
A computação paralela é uma computação em que os trabalhos são divididos em partes
discretas que podem ser executadas simultaneamente. Cada parte é subdividida em uma série
de instruções. As instruções de cada parte são executadas simultaneamente em CPUs
diferentes. Os sistemas paralelos lidam com o uso simultâneo de vários recursos de computador
que podem incluir um único computador com vários processadores, vários computadores
conectados por uma rede para formar um cluster de processamento paralelo ou uma combinação
de ambos.
 COMENTÁRIO
Os sistemas paralelos são mais difíceis de programar do que os computadores com um único
processador, porque a arquitetura dos computadores paralelos varia de acordo com os recursos
disponíveis, sendo assim, os processos de várias CPUs devem ser coordenados e sincronizados.
A primeira descrição formal desse tipo de abordagem foi a taxonomia de Flynn. Essa taxonomia
foi desenvolvida em 1966 e ligeiramente expandida em 1972:
É uma metodologia para classificar formas gerais de operação paralela disponíveis em um
processador.
Propõe uma abordagem para esclarecer os tipos de paralelismo suportados no hardware por um
sistema de processamento ou disponíveis em uma aplicação.
Sua classificação é baseada na visão da máquina ou do aplicativo pelo programador de
linguagem de máquina.
A taxonomia de Flynn é uma categorização de formas de arquiteturas de computador paralelas.
Do ponto de vista do programador de linguagem assembly, os computadores paralelos são
classificados pela simultaneidade em sequências de processamento (ou fluxos), dados e
instruções. Isso resulta em quatro classes: SISD (instrução única, dados únicos), SIMD (instrução
única, dados múltiplos), MISD (instrução múltipla, dados únicos) e MIMD (instrução múltipla,
dados múltiplos).
A taxonomia de Flynn pode ser sumarizada de forma ilustrativa segundo a imagem a seguir.
 Taxonomia de Flynn.
SISTEMAS DE INSTRUÇÃO ÚNICA E DADOS
ÚNICOS (SINGLE-INSTRUCTION, SINGLE-
DATA – SISD)
Um sistema de computação de instrução única e dados únicos (Single-Instruction, Single-Data –
SISD) é uma máquina de um processador que é capaz de executar uma única instrução,
operando em um único fluxo de dados, como se observa na imagem seguinte.
No SISD, as instruções de máquinasão processadas de maneira sequencial, e os computadores
que adotam esse modelo são popularmente chamados de computadores sequenciais. A maioria
dos computadores convencionais derivados da proposição de Von Neumann possui arquitetura
SISD. Todas as instruções e dados a serem processados devem ser armazenados na memória
primária.
A velocidade do elemento de processamento no modelo SISD é limitada (dependente) pela taxa
por meio da qual o computador pode transferir informações internamente. Os sistemas SISD
representativos dominantes são IBM PC e estações de trabalho, entre outros.
 Sistemas de Instrução Única e Dados Únicos (SISD).
SISTEMAS DE INSTRUÇÃO ÚNICA E DADOS
MÚLTIPLOS (SINGLE-INSTRUCTION,
MULTIPLE-DATA –SIMD)
Um sistema SIMD é uma máquina multiprocessada capaz de executar a mesma instrução em
todas as CPUs, mas operando em diferentes fluxos de dados.
As máquinas baseadas em um modelo SIMD são adequadas para computação científica, pois
envolvem muitas operações de vetor e matriz. Para que a informação possa ser passada para
todos os elementos de processamento (Processing Elements – PEs), os elementos de dados
organizados dos vetores podem ser divididos em vários conjuntos (N-conjuntos para sistemas N
PE) e cada PE pode processar um conjunto de dados.
Veja a imagem a seguir.
Os sistemas SIMD representativos são, por exemplo, máquinas de processamento vetorial da
Cray e as Unidade de Processamento Gráfico (Graphical Processing Unit – GPU).
 Sistemas de instrução única e dados múltiplos (SIMD).
SISTEMAS DE INSTRUÇÃO MÚLTIPLA E
DADOS ÚNICOS (MULTIPLE-INSTRUCTION,
SINGLE-DATA – MISD)
Um sistema de computação MISD é uma máquina multiprocessada capaz de executar diferentes
instruções em diferentes PEs, mas todas operando no mesmo conjunto de dados, conforme a
próxima imagem.
O sistema executa diferentes operações no mesmo conjunto de dados. As máquinas construídas
usando o modelo MISD não são úteis na maioria das aplicações, algumas máquinas são
construídas, mas nenhuma delas está disponível comercialmente.
 Sistemas de instrução múltipla e dados únicos (MISD).
SISTEMAS DE MÚLTIPLAS INSTRUÇÕES E
MÚLTIPLOS DADOS (MULTIPLE-
INSTRUCTION, MULTIPLE-DATA – MIMD)
Um sistema de múltiplas instruções e múltiplos dados (MIMD) é uma máquina com
multiprocessador capaz de executar várias instruções em vários conjuntos de dados, conforme a
imagem a seguir.
Cada PE no modelo MIMD tem instruções e fluxos de dados separados; portanto, as máquinas
construídas a partir desse modelo suportam qualquer tipo de aplicação. Ao contrário das
máquinas SIMD e MISD, os PEs em máquinas MIMD funcionam de forma assíncrona.
 ATENÇÃO
As máquinas MIMD são amplamente categorizadas em MIMD de memória compartilhada e MIMD
de memória distribuída com base na maneira como os PEs são acoplados à memória principal.
No modelo MIMD de memória compartilhada (sistemas multiprocessadores fortemente
acoplados), todos os PEs são conectados a uma única memória global e todos têm acesso a ela.
A comunicação entre os PEs nesse modelo ocorre por meio da memória compartilhada, e a
modificação dos dados armazenados na memória global por um PE é visível para todos os outros
PEs. Os sistemas MIMD representativos dominantes de memória compartilhada são as máquinas
Silicon Graphics e SMP (Symmetric Multi-Processing) da Sun / IBM.
Em máquinas MIMD de memória distribuída (sistemas multiprocessadores fracamente
acoplados), todos os PEs têm uma memória local. A comunicação entre PEs nesse modelo
ocorre por meio da rede de interconexão (o canal de comunicação entre processos, ou IPC). A
rede que conecta os PEs pode ser configurada em árvore, malha ou de acordo com o requisito.
ÁRVORE
A topologia de rede em árvore é uma topologia que possibilita a visualização da interligação de
várias redes e sub-redes, caracterizando-se pela presença de um concentrador que interliga
todos os nodos (computadores, servidores, PEs etc.) de uma rede local, enquanto outro
concentrador interliga as demais redes, interligando dessa forma um conjunto de redes locais
(LAN) e fazendo com que estas sejam dispostas no formato de árvore.
MALHA
A topologia de rede em malha consiste em uma topologia de rede de computadores onde cada
nodo da rede (computador, servidor, PE etc.) está conectado aos demais diretamente, o que
possibilita que todos os nodos da rede sejam capazes de trocar informações diretamente com
todos os demais. Nessa topologia, a informação pode ser transmitida da origem ao destino por
diversos meios ou caminhos.
A arquitetura MIMD de memória compartilhada é mais fácil de programar, mas é menos tolerante
a falhas e mais difícil de estender em relação ao modelo MIMD de memória distribuída.
Falhas em um MIMD de memória compartilhada afetam todo o sistema, ao passo que este não é
o caso do modelo distribuído, no qual cada um dos PEs pode ser facilmente isolado.
Além disso, as arquiteturas MIMD de memória compartilhada têm menos probabilidade de serem
escaláveis porque a adição de mais PEs leva à contenção de memória, situação que não ocorre
javascript:void(0)
javascript:void(0)
no caso da memória distribuída, em que cada PE possui sua própria memória. Por causa dos
resultados práticos e requisitos do usuário, a arquitetura de memória distribuída MIMD é superior
aos outros modelos existentes.
 Sistemas de múltiplas instruções e múltiplos dados (MIMD).
LEI DE AMDAHL E SPEEDUP
Quando buscamos o paralelismo da execução de instruções, desejamos que o nosso sistema
realize suas tarefas da forma mais rápida possível. Entretanto, existe um limite teórico para a
execução dessas tarefas, e ele é determinado pela lei de Amdahl.
 ATENÇÃO
A lei de Amdahl afirma que podemos paralelizar e/ou distribuir nossos cálculos tanto quanto
quisermos, ganhando em desempenho à medida que adicionamos recursos de computação. No
entanto, nosso código não pode ser mais rápido do que a velocidade de suas partes sequenciais
combinadas (ou seja, não paralelizáveis) em um único processador.
Colocado de modo mais formal, a lei de Amdahl tem a seguinte formulação.
Dado um algoritmo que é parcialmente paralelo, vamos chamar P sua fração paralela e S sua
fração serial (S + P = 100 % ). Além disso, chamemos T ( n ) o tempo de execução (em
segundos) do algoritmo ao usar n processadores.
Então, a seguinte relação se mantém:
TN≥S . T1+ P . T1N
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
A relação anterior afirma o seguinte:
O tempo de execução do algoritmo descrito aqui em n processadores é igual — e geralmente
maior — do que o tempo de execução de sua parte serial em um processador (isto é, S.T1) mais
o tempo de execução de sua parte paralela em um processador (ou seja, P.T1) dividido por n
(número de processadores).
À medida que aumentamos o número n de processadores usados por nosso código, o segundo
termo da equação fica cada vez menor, tornando-se insignificante em relação ao primeiro termo.
Nesses casos, a relação anterior simplesmente se torna esta:
T∞≈S.T1
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
A tradução dessa relação pode ser interpretada da seguinte forma:
O tempo de execução do algoritmo descrito aqui em um número infinito de processadores (ou
seja, um número realmente grande de processadores) é aproximadamente igual ao tempo de
execução de sua parte serial em um único processador (ou seja, S.T1 ).
Agora, vamos parar por um segundo e pensar sobre as implicações da lei de Amdahl. O que
temos aqui é uma observação bastante simples: muitas vezes, não podemos paralelizar
totalmente nossos algoritmos.
O que significa que, na maioria das vezes, não podemos ter S = 0 nas relações anteriores. As
razões para isso são inúmeras:
Copiar dados e/ou código para onde os vários processadores serão capazes de acessá-los.
Dividir os dados em pedaços e mover esses pedaços pela rede.
Coletar os resultados de todas as tarefas simultânease executar algum processamento adicional
nelas, e assim por diante.
 ATENÇÃO
Seja qual for o motivo, se não pudermos paralelizar totalmente o algoritmo, eventualmente o
tempo de execução do código será dominado pelo desempenho da fração serial. Não apenas
isso, mas mesmo antes que aconteça, começaremos a ver acelerações cada vez menores do
que o esperado.
Como uma observação lateral, algoritmos que são totalmente paralelos são geralmente
chamados de “embaraçosamente paralelos” e oferecem propriedades de escalabilidade
impressionantes (com acelerações geralmente lineares com o número de processadores). É claro
que não há nada de constrangedor nesses softwares. Porém, infelizmente, eles não são tão
comuns quanto gostaríamos.
Como a execução paralela dos algoritmos pode realmente fazer com que a tarefa seja executada
de forma mais rápida, temos de mensurar esse ganho, o que chamamos de speedup.
O speedup é definido como a razão entre o tempo de execução serial do melhor algoritmo
sequencial para resolver um problema e o tempo gasto pelo algoritmo paralelo para resolver o
mesmo problema com p processadores.
É simplesmente a razão entre o tempo gasto com uma execução serial dividido pelo tempo gasto
pela execução paralela, conforme podemos ver na fórmula a seguir.
SPEEDUP= TEMPOSERIALTEMPOPARALELO= TSTP
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Vamos tentar visualizar toda a lei de Amdahl, bem como o speedup associado com alguns
números.
Suponha que o algoritmo leve 100 segundos para ser executado em um único processador.
Vamos supor também que podemos paralelizar 99% disso, o que seria uma façanha
incrível, na maioria das vezes.
Podemos tornar o código mais rápido aumentando o número de processadores que
usamos, conforme esperado.
Veja o cálculo:
T1=100S
T10≈0,01. 100S+0,99*100S10=10,9S ⇒SPEEDUP=10010,9=9,2X
T100≈1S+0,99S=1,99S⟹SPEEDUP= 1001,99=50,2X
T1000≈1S+0,099S=1,099S⇒SPEEDUP=1001,099=91X
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
A partir dos números anteriores, vemos que o aumento da aceleração com valores crescentes de
n é bastante decepcionante.
Começamos com um aumento de velocidade realmente incrível de 9,2x usando 10
processadores, e então caímos para apenas 50x ao usar 100 processadores e um insignificante
91x ao usar 1.000 processadores.
 Exemplo da lei de Amdahl e de speedup.
A imagem anterior mostra a aceleração de melhor caso esperada para o mesmo algoritmo
(calculado até n=5.000). Não importa quantos processadores usamos; não podemos obter um
aumento de velocidade maior que 100x, o que significa que o mais rápido que o código rodará é
um segundo, que é o tempo que sua fração serial leva em um único processador, exatamente
como foi previsto pela lei de Amdahl.
A lei de Amdahl nos diz duas coisas:
A primeira é o quanto de aceleração podemos razoavelmente esperar na melhor das hipóteses e
quando parar de adicionar hardware ao sistema devido aos retornos decrescentes.
A segunda é que a lei de Amdahl se aplica igualmente a sistemas distribuídos e sistemas
híbridos distribuídos paralelamente. Nesses casos, n refere-se ao número total de
processadores em computadores disponíveis no sistema.
SISTEMAS HÍBRIDOS DISTRIBUÍDOS
São aqueles que combinam diferentes tipos de aspectos arquiteturais.
Um aspecto que deve ser mencionado nesse ponto é que à medida que os sistemas que
podemos usar se tornam mais poderosos, nossos algoritmos distribuídos levarão cada vez menos
tempo para rodar, se puderem fazer uso dos ciclos extras.
javascript:void(0)
ENTENDENDO O SPEEDUP
No vídeo a seguir, apresentamos o conceito de speedup, utilizando a Lei de Amdahl
VERIFICANDO O APRENDIZADO
MÓDULO 2
 Diferenciar memória compartilhada e memória distribuída
MEMÓRIA COMPARTILHADA
Para se aproveitar do paralelismo disponível nos sistemas modernos, os programas podem ser
desenvolvidos para utilizar mais de um core (núcleos) simultaneamente. Isso significa que um
programa com essa capacidade, sendo executado em um servidor, por exemplo, com 8 cores,
poderia ser executado até oito vezes mais rápido (já vimos de acordo coma a lei de Amdahl que
isso não é verdade). Para isso, o programa precisa ser explicitamente programado com essa
capacidade, usando bibliotecas ou técnicas específicas.
A memória compartilhada é a memória que pode ser acessada simultaneamente por vários
programas com a intenção de fornecer comunicação entre eles. Além de ser uma forma de
comunicação entre os diversos programas, possibilita a economia de recursos, evitando cópias
redundantes. Dentro desse contexto, os programas podem ser executados em um único
processador ou mesmo em vários processadores separados.
O conceito de memória compartilhada pode ser aplicado tanto em hardware como em software.
Sua aplicação em hardware não é o foco do nosso estudo neste tema, assim, passaremos
apenas a considerar sua aplicação em software.
Em termos de software, a memória compartilhada pode ser um método de comunicação entre
processos (Interprocess Communication – IPC), ou seja, uma maneira de trocar dados entre
programas em execução ao mesmo tempo. Um processo criará uma área na RAM a qual outros
processos podem acessar.
Como dissemos anteriormente, o uso de memória compartilhada permite a conservação de
recursos de memória, evitando cópias de dados de uma mesma instância, usando mapeamentos
de memória virtual ou com suporte explícito do programa em questão.
Uma vez que ambos os processos podem acessar a área de memória compartilhada como
memória de trabalho regular, essa é uma forma muito rápida de comunicação, utilizando-se, via
de regra, a comunicação síncrona nesses sistemas. Por outro lado, é menos escalável, pois os
processos de comunicação devem estar rodando na mesma máquina, ficando limitado aos
recursos desta. Existem ainda outros problemas, pois se os processos que compartilham a
mesma memória compartilhada estiverem sendo executados em CPUs separadas, podem surgir
problemas de coerência de cache.
Passemos a um exemplo onde todos os cores de CPUs utilizados estão sempre no mesmo
servidor, e tem acesso a mesma memória, chamamos essa técnica de paralelização de
memória compartilhada. São termos relacionados a esse mecanismo: SMP, Threads, OpenMP,
os quais não serão objetos de nosso estudo.
 EXEMPLO
Programas em C/C++ podem ser “facilmente” paralelizados para esse modelo usando a biblioteca
OpenMP. Para isso, são necessárias as inclusões de algumas diretivas de compilação (pragmas)
no código e a utilização de um compilador compatível.
A seguir, temos um exemplo de memória compartilhada utilizando a linguagem C. Claro que para
utilizá-lo, a biblioteca OMP já deve estar instalada em seu computador.
Inicialmente, temos que incluir o cabeçalho OpenMP para nosso programa junto com os arquivos
de cabeçalho padrão.
No OpenMP, precisamos mencionar a região que vamos fazer como paralela usando a palavra-
chave pragma omp parallel. O pragma omp parallel é usado para bifurcar threads adicionais para
realizar o trabalho paralelo na região determinada. O encadeamento original será indicado como
o encadeamento mestre com ID de encadeamento 0.
O código para a criação de uma região paralela seria:
Na região entre colchetes, todas as variáveis ali declaradas serão compartilhadas por todos os
threads em execução. Em outras palavras, todas as variáveis criadas nesse espaço de memória
serão compartilhadas por todas as instâncias de thread criadas.
O comando poderia ser, por exemplo:
Defina o número de threads para executar o programa usando a variável externa.
//OpenMP header 
#include <omp.h>
1
2
#pragma omp parallel 
{ 
// As variáveis criadas aqui serão compartilhadas por todas 
// as theads em execução 
//Parallel region code 
}
1
2
3
4
5
6
#pragma omp parallel 
{ 
 printf("Ola Mundo... da thread = %d\n", omp_get_thread_num()); 
}
1
2
3
4
 Ilustração gráfica de uma memóriacompartilhada.
De acordo com a imagem anterior, uma vez que o compilador encontra o código das regiões
paralelas, o thread mestre (thread que tem o id de thread 0) será bifurcado no número
especificado de threads.
Aqui, ele será dividido em 5 threads porque inicializaremos o número de threads a serem
executados como 5, usando o comando export OMP_NUM_THREADS = 5.
Todo o código dentro da região paralela será executado por todos os threads simultaneamente,
bem como todas as variáveis eventualmente declaradas nesse código serão compartilhadas.
Uma vez que a região paralela terminar, todos os threads serão mesclados no thread mestre.
 COMENTÁRIO
Não se preocupe em executar este programa no seu computador. A biblioteca OpenMP não será
o foco do nosso estudo. Mas, caso se interesse no exemplo atual, siga os comandos abaixo
descritos.
Compile o programa no ambiente Linux, utilizando o seguinte comando:
Execute o programa com o seguinte comando:
export OMP_NUM_THREADS=51
gcc -o hello -fopenmp hello.c1
A seguir, está o programa completo descrito anteriormente.
Como especificamos, o número de threads a serem executados como 5, estes 5 threads
executarão a mesma instrução de impressão ao mesmo tempo. Aqui, não podemos garantir a
ordem de execução dos threads, ou seja, a ordem de execução da instrução na região paralela
não será a mesma para todas as execuções.
Na imagem a seguir, durante a primeira execução do programa, o encadeamento 1 é concluído
primeiro, sendo que na segunda execução do programa, o encadeamento 0 é o primeiro a ser
concluído. omp_get_thread_num () retornará o número do thread (tarefa) associado ao segmento.
Veja a saída de uma execução do programa.
./hello1
// Usando o OpenMP para executar o Hello World compartilhado 
// utilizando a linguagem C
 
// OpenMP header 
#include <omp.h> 
 
#include <stdio.h> 
#include <stdlib.h> 
 
int main(int argc, char* argv[]) 
{ 
 
 // Inicio da Regiao Paralela 
 #pragma omp parallel 
 { 
 
 printf("Ola Mundo... da thread = %d\n", omp_get_thread_num()); 
 } 
 // Fim da regiao paralela 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
aluno@ubuntu: ~$ export OMP_NUM_THREADS=5 
aluno@ubuntu: ~$ gcc -o hello -fopenmp hello.c 
aluno@ubuntu: ~$ ./hello 
Ola Mundo... da thread = 1 
Ola Mundo... da thread = 0 
Ola Mundo... da thread = 4 
Ola Mundo... da thread = 3 
Ola Mundo... da thread = 2
1
2
3
4
5
6
7
8
 Primeira execução de um programa de memória compartilhada.
Quando executado por várias vezes: a ordem de execução dos threads muda a cada vez.
 Segunda execução de um programa de memória compartilhada.
MEMÓRIA DISTRIBUÍDA
A memória distribuída refere-se a um sistema de computador multiprocessador no qual cada
processador tem sua própria memória privada. As tarefas computacionais só podem operar em
dados locais e, se forem necessários dados remotos, a tarefa computacional deve se comunicar
com um ou mais processadores remotos.
Em contraste, como vimos anteriormente, um multiprocessador de memória compartilhada
oferece um único espaço de memória usado por todos os processadores. Os processadores não
precisam estar cientes de onde os dados residem, exceto de que pode haver penalidades de
desempenho e que as condições de corrida devem ser evitadas.
CONDIÇÕES DE CORRIDA
Condições de corrida são situações caracterizadas pelo acesso simultâneo de dois ou mais
processos a dados compartilhados, em um processamento ou sistema cujo resultado final
depende da ordem de execução de seus processos.
aluno@ubuntu: ~$ ./hello 
Ola Mundo... da thread = 1 
Ola Mundo... da thread = 0 
Ola Mundo... da thread = 4 
Ola Mundo... da thread = 3 
Ola Mundo... da thread = 2 
aluno@ubuntu: ~$ ./hello 
Ola Mundo... da thread = 0 
Ola Mundo... da thread = 4 
Ola Mundo... da thread = 3 
Ola Mundo... da thread = 2 
Ola Mundo... da thread = 1
1
2
3
4
5
6
7
8
9
10
11
12
javascript:void(0)
Em um sistema de memória distribuída, normalmente, há um processador, uma memória e
alguma forma de interconexão que permite que os programas em cada processador interajam
uns com os outros. A interconexão pode ser organizada com enlaces ponto a ponto ou o
hardware separado pode fornecer uma rede de comutação.
A topologia da rede é um fator chave para determinar como a máquina multiprocessadora é
dimensionada. Os enlaces entre os nós podem ser implementados usando algum protocolo de
rede padrão (onde a comunicação via placas Ethernet é a mais comum) ou algum outro tipo de
comunicação. Como a comunicação, geralmente, é por protocolos de rede, pode existir uma
grande latência nestas operações, que em operações bloqueantes (síncronas) pode não ser
apropriado. Assim, as comunicações assíncronas (em regra as não bloqueantes) são as mais
utilizadas nesse tipo de sistema.
O principal problema na programação de sistemas de memória distribuída é como distribuir os
dados pelas memórias. Dependendo do problema resolvido, os dados podem ser distribuídos
estaticamente ou podem ser movidos através dos nós. Os dados podem ser movidos sob
demanda ou podem ser enviados para os novos nós com antecedência.
A principal vantagem da memória compartilhada é que ela oferece um espaço de endereço
unificado no qual todos os dados podem ser encontrados, além dos dados serem acessados com
maior rapidez.
A vantagem da memória distribuída é que ela exclui condições de corrida, e a principal
preocupação do programador é pensar sobre a distribuição de dados. Da mesma forma, a
memória distribuída é muito mais escalável do que a memória compartilhada, bastando acessar
novos nós a rede. Por outro lado, em que pese a ocultar o mecanismo de comunicação, não é
possível deixar de considerar a latência de comunicação para acessar os dados.
Um programa que usa as funcionalidades de memória distribuída tem de ser explicitamente
desenvolvido com essa capacidade. Geralmente isso é feito usando uma biblioteca MPI (no caso
da memória compartilhada, usamos no nosso exemplo o OpenMP). Não se preocupe em
executar este código no seu computador, alguns conceitos não foram tratados, mas irá permitir
que você tenha uma visão do emprego da memória distribuída, conforme veremos em nosso
vídeo.
// Bibliotecas do MPI necessarias 
#include "mpi.h" 
#include <stdio.h> 
 
int main(int argc, char *argv[]) 
{ 
 int numtasks, rank, len, rc; 
1
2
3
4
5
6
7
MEMÓRIA COMPARTILHADA VERSUS
MEMÓRIA DISTRIBUÍDA
Assista agora a uma comparação entre a memória compartilhada e a memória distribuída.
 char hostname[MPI_MAX_PROCESSOR_NAME]; 
 
 // initializando o MPI 
 MPI_Init(&argc,&argv); 
 // obtendo o numero de tasks 
 MPI_Comm_size(MPI_COMM_WORLD,&numtasks); 
 // obtendo o rank 
 MPI_Comm_rank(MPI_COMM_WORLD,&rank); 
 // obtendo o nome do processador 
 MPI_Get_processor_name(hostname, &len); 
 printf ("Number of tasks= %d My rank= %d Running on %s\n", numtasks,r
 // finalizando o MPI 
 MPI_Finalize(); 
}
8
9
10
11
12
13
14
15
16
17
18
19
20
21
VERIFICANDO O APRENDIZADO
MÓDULO 3
 Diferenciar paralelismo de dados e paralelismo de tarefas
PARALELISMO DE DADOS
O paralelismo de dados é a paralelização dos dados entre vários processadores em ambientes
de computação paralela:
Concentra-se na distribuição dos dados em nós diferentes, que operam nos dados em paralelo.
Pode ser aplicado em estruturas de dados regulares, como arrays e matrizes, trabalhando em
cada elemento em paralelo.
Um trabalho paralelo de dados em uma matriz de n elementos pode ser dividido igualmente entre
todos os processadores.
Vamos supor que queremos somar todos os elementos da matriz fornecida e o tempo para uma
única operação de adição é unidades de tempo Ta.
No caso de execução sequencial, o tempo gasto pelo processo será n × Ta unidades de tempo,
pois soma todos os elementos de uma matriz.
Por outro lado, se executarmos esse trabalho como um trabalho paralelo de dados em 4
processadores, o tempo gasto seria reduzido para n×Ta/4, desconsiderando eventuais atrasos de
execução e operaçõesobrigatoriamente serializáveis já citados na lei Amdahl. Nesse caso, a
execução paralela resulta em uma aceleração de 4 em relação à execução sequencial.
 ATENÇÃO
Uma questão interessante a se notar é que a localidade das referências de dados desempenha
um papel importante na avaliação do desempenho de um modelo de programação paralela de
dados.
A localidade dos dados depende de dois fatores:
Acessos à memória realizados pelo programa.
Tamanho do cache.
Em um sistema multiprocessador que executa um único conjunto de instruções (SIMD),
arquitetura de dados que já explanamos, o paralelismo de dados é obtido quando cada
processador executa a mesma tarefa em diferentes dados distribuídos.
Em algumas situações, um único thread de execução controla as operações em todos os dados.
Em outras, diferentes threads controlam a operação, mas executam o mesmo código.
 EXEMPLO
Considere a multiplicação e adição de matrizes de maneira sequencial. Veja a seguir o
pseudocódigo sequencial para multiplicação e adição de duas matrizes onde o resultado é
armazenado na matriz C. O pseudocódigo para multiplicação calcula o produto escalar de duas
matrizes A e B e armazena o resultado na matriz de saída C.
Se os programas a seguir forem executados sequencialmente, o tempo necessário para calcular
o resultado seria On3, assumindo que os comprimentos de linha e de coluna de ambas as
matrizes são n e On para multiplicação e adição, respectivamente.
// Multiplicacao de matrizes 
for (i = 0; i < row_length_A; i++) 
{ 
 for (k = 0; k < column_length_B; k++) 
1
2
3
4
Podemos explorar o paralelismo de dados no código anterior para executá-lo mais rapidamente,
pois a aritmética é independente em relação ao loop.
A paralelização do código de multiplicação da matriz é obtida usando o OpenMP. Uma diretiva
OpenMP, "omp parallel for" instrui o compilador a executar o código no loop for em paralelo. Para
multiplicação, podemos dividir a matriz A e B em blocos ao longo de linhas e colunas,
respectivamente. Isso nos permite calcular cada elemento na matriz C individualmente, tornando
a tarefa paralela.
 EXEMPLO
Am x n.Bn x k pode ser finalizado em On em vez de Om*n*kquando executado em paralelo
usando m * k processadores.
 Matriz A versus Matriz B.
 { 
 sum = 0; 
 for (j = 0; j < column_length_A; j++) 
 { 
 sum += A[i][j] * B[j][k]; 
 } 
 C[i][k] = sum; 
 } 
} 
// Adicao de arrays 
for (i = 0; i < n; i++) { 
 c[i] = a[i] + b[i]; 
}
5
6
7
8
9
10
11
12
13
14
15
16
17
// Multiplicação de matrizes em paralelo 
#pragma omp parallel for schedule(dynamic,1) collapse(2) 
for (i = 0; i < row_length_A; i++){ 
 for (k = 0; k < column_length_B; k++){ 
 sum = 0; 
1
2
3
4
Pode-se observar a partir do exemplo que, conforme os tamanhos das matrizes continuam
aumentando, serão necessários muitos processadores. Manter o tempo de execução baixo é a
prioridade, mas, na medida em que o tamanho da matriz aumenta, nos deparamos com outras
restrições, como a complexidade de tal sistema e seus custos associados. Portanto, restringindo
o número de processadores no sistema, podemos ainda aplicar o mesmo princípio e dividir os
dados em blocos maiores para calcular o produto de duas matrizes.
Para adição de matrizes em uma implementação paralela de dados, vamos supor um sistema
mais modesto com duas CPUs A e B. A CPU A poderia adicionar todos os elementos da metade
superior das matrizes, enquanto a CPU B poderia adicionar todos os elementos da metade
inferior das matrizes. Como os dois processadores funcionam em paralelo, a tarefa de realizar a
adição do array levaria metade do tempo de realizar a mesma operação em série usando apenas
uma CPU.
 COMENTÁRIO
O paralelismo de dados está muito em voga nos dias atuais, e talvez as placas com tecnologia
GPU sejam o sinônimo desta tecnologia. Esse tipo de abordagem não será o foco do nosso
estudo.
PARALELISMO DE TAREFAS
O paralelismo de tarefas (também conhecido como paralelismo de função e paralelismo de
controle) é uma forma de paralelismo de código de computador em vários processadores em
ambientes de computação paralela. Concentra-se na distribuição de tarefas — executadas
simultaneamente por processos ou threads — em diferentes processadores. Em contraste com o
paralelismo de dados, que envolve a execução da mesma tarefa em diferentes componentes de
 for (j = 0; j < column_length_A; j++){ 
 sum += A[i][j] * B[j][k]; 
 } 
 C[i][k] = sum; 
 } 
}
5
6
7
8
9
10
11
dados, distingue-se pela execução de muitas tarefas diferentes ao mesmo tempo nos mesmos
dados.
 ATENÇÃO
Em um sistema multiprocessador, o paralelismo de tarefas é obtido quando cada processador
executa um thread diferente (ou processo) nos mesmos dados ou em dados diferentes,
diferentemente do que vimos no paralelismo de dados, onde os threads executam a mesma
tarefa.
Os threads podem executar o mesmo código ou código diferente. No caso geral, diferentes
threads de execução se comunicam uns com os outros enquanto funcionam, mas isso não é um
requisito. A comunicação geralmente ocorre passando dados de um thread para o próximo como
parte de um fluxo de trabalho. Essa comunicação entre threads pode ser executada inclusive
utilizando mecanismos de memória distribuída.
 EXEMPLO
Se um sistema está executando o código em um sistema de dois processadores (CPUs "a" e "b")
em um ambiente paralelo e queremos fazer as tarefas "A" e "B", é possível dizer CPU "a" para
fazer a tarefa "A" e CPU "b" para fazer a tarefa "B" simultaneamente, reduzindo assim o tempo de
execução. As tarefas podem ser atribuídas usando instruções condicionais.
O paralelismo de tarefas enfatiza a natureza distribuída (paralelizada) do processamento (ou seja,
threads), em oposição aos dados (paralelismo de dados).
O paralelismo de nível de thread (TLP) é o paralelismo inerente a um aplicativo que executa
vários threads de uma vez. Esse tipo de paralelismo é encontrado principalmente em aplicativos
escritos para servidores comerciais, como bancos de dados. Ao executar muitos threads de uma
vez, esses aplicativos são capazes de tolerar as altas quantidades de input e output e latência do
sistema de memória em que suas cargas de trabalho podem incorrer - enquanto um thread está
atrasado esperando por um acesso à memória ou disco, outros threads podem fazer um trabalho
útil.
A exploração do paralelismo de nível de thread também começou a fazer incursões no mercado
de desktops com o advento dos microprocessadores multicores. Nos computadores de mesa,
isso ficou evidenciado com o advento do Windows NT e do Windows 95, em que pese a essas
tecnologias, já eram possíveis em outros sistemas operacionais, como o SunOS e o Solaris. Isso
ocorreu porque, por várias razões, tornou-se cada vez mais impraticável aumentar a velocidade
do clock ou as instruções por clock de um único núcleo.
 COMENTÁRIO
Se essa tendência continuar, novos aplicativos terão de ser projetados para utilizar vários threads
para se beneficiar do aumento potencial do poder de computação. Isso contrasta com as
inovações anteriores do microprocessador, nas quais o código existente era automaticamente
acelerado ao ser executado em um computador mais novo / mais rápido.
O exemplo que mostramos em memórias compartilhada também serve como exemplo de uma
tarefa distribuída, onde cada thread executava a função de imprimir o seu Id. Uma forma simples
seria colocar uma função dentro do espaço reservado para o paralelismo.
PARALELISMO DE DADOS VERSUS
PARALELISMO DE TAREFAS
No vídeo a seguir, apresentamos uma comparação entre o paralelismo de dados e o paralelismo
de tarefas.
VERIFICANDO O APRENDIZADO
MÓDULO 4
 Identificar as arquiteturas de sistemas paralelos e distribuídos
Há diversas arquiteturas de sistemas paralelos e distribuídos. Neste módulo, veremos cinco tipos
de arquitetura que podem ser aplicados tanto em sistemas paralelos como em sistemas
distribuídos.
São os seguintes:
Cliente-servidor
Mestre-escravoPolling
Peer-to-peer
Clusters.
CLIENTE-SERVIDOR
O modelo cliente -servidor é a arquitetura mais frequentemente citada na literatura de sistemas
distribuídos. Historicamente, é a mais importante e continua sendo a mais amplamente utilizada.
A figura a seguir ilustra a estrutura simples na qual os processos assumem as funções de clientes
ou servidores. Em particular, os processos do cliente interagem com os processos individuais
do servidor em computadores host potencialmente separados para acessar os recursos
compartilhados que eles gerenciam.
O modelo cliente-servidor é uma estrutura de aplicativo distribuída que particiona tarefas ou
cargas de trabalho entre os provedores de recursos e/ou serviços, chamados servidores, e
solicitantes de serviços, chamados clientes.
Frequentemente, clientes e servidores se comunicam em uma rede de computadores em
hardware separado, mas tanto o cliente quanto o servidor podem residir no mesmo sistema.
Um host de servidor executa um ou mais programas de servidor, que compartilham seus recursos
com os clientes.
Um cliente, geralmente, não compartilha nenhum de seus recursos, mas solicita conteúdo ou
serviço de um servidor.
Os clientes, portanto, iniciam sessões de comunicação com os servidores, que aguardam
solicitações de entrada.
São exemplos de aplicativos de computador que usam o modelo cliente-servidor: e-mail,
impressão em rede e a World Wide Web.
 Arquitetura cliente-servidor.
A arquitetura cliente-servidor descreve o relacionamento de programas cooperativos em um
aplicativo. O componente do servidor fornece uma função ou serviço a um ou mais clientes, que
iniciam solicitações para esses serviços. Nesse sentido, os servidores são classificados pelos
serviços que fornecem.
 EXEMPLO
Um servidor web atende páginas web e um servidor de arquivos atende arquivos de computador.
Um recurso compartilhado pode ser qualquer software e componentes eletrônicos do computador
servidor, desde programas e dados até processadores e dispositivos de armazenamento. O
compartilhamento de recursos de um servidor constitui um serviço.
Se um computador é um cliente, um servidor ou ambos, é determinado pela natureza do
aplicativo que requer as funções de serviço.
 EXEMPLO
Um único computador pode executar um servidor web e um software servidor de arquivos ao
mesmo tempo para servir dados diferentes a clientes que fazem diferentes tipos de solicitações.
O software cliente também pode se comunicar com o software servidor no mesmo computador.
Em geral, um serviço é uma abstração de recursos do computador, e um cliente não precisa se
preocupar, em tese, com o desempenho do servidor enquanto atende a solicitação e entrega a
resposta. O cliente só precisa entender a resposta com base no protocolo de aplicativo bem
conhecido, ou seja, o conteúdo e a formatação dos dados para o serviço solicitado.
Clientes e servidores trocam mensagens em um padrão de mensagem de solicitação-resposta. O
cliente envia uma solicitação e o servidor retorna uma resposta. Essa troca de mensagens é um
exemplo de comunicação entre processos. Para se comunicar, os computadores devem ter uma
linguagem comum e devem seguir regras para que o cliente e o servidor saibam o que esperar.
O idioma e as regras de comunicação são definidos em um protocolo de comunicação, sendo que
estes protocolos operam na camada de aplicativo. O protocolo da camada de aplicação define os
padrões básicos do diálogo.
Para formalizar ainda mais a troca de dados, o servidor pode implementar uma interface de
programação de aplicativos (Application Program Interface – API).
A API é uma camada de abstração para acessar um serviço:
Ao restringir a comunicação a um formato de conteúdo específico, facilita a análise.
Ao abstrair o acesso, facilita a troca de dados entre plataformas.
Um servidor pode receber solicitações de muitos clientes distintos em um curto período. Um
computador só pode realizar um número limitado de tarefas a qualquer momento e conta com um
sistema de agendamento para priorizar as solicitações de entrada dos clientes para acomodá-las.
Para evitar sobrecarga e maximizar a disponibilidade, o software do servidor pode limitar a
disponibilidade para os clientes. Aproveitando a eventual possibilidade de sobrecarga, podem ser
feitos ataques de negação de serviço que são projetados para explorar a obrigação de um
servidor de processar solicitações, sobrecarregando-o com taxas de solicitação excessivas.
 ATENÇÃO
Caso a segurança seja um fator importante, técnicas de criptografia podem ser aplicadas se as
informações confidenciais forem comunicadas entre o cliente e o servidor.
Quando um correntista de banco acessa serviços de banco on-line com um navegador da web (o
cliente), este inicia uma solicitação ao servidor de web do banco.
As credenciais de login do correntista podem ser armazenadas em um banco de dados e o
servidor da web acessa o servidor de banco de dados como um cliente.
Um servidor de aplicativos interpreta os dados retornados aplicando a lógica de negócios do
banco e fornece a saída para o servidor da web.
Finalmente, o servidor da web retorna o resultado ao navegador da web do correntista para
exibição.
O resumo a seguir mostra a sequência de ações tanto do lado do cliente como do lado do
servidor.
CARACTERÍSTICAS DO CLIENTE
Inicia solicitações para servidores.
Aguarda por respostas.
Recebe respostas.
Conecta-se a um número reduzido de servidores por vez.
Usualmente, interage diretamente com os servidores por meio de software específico para a
tarefa de estabelecer comunicação entre cliente e servidor.
Utiliza recursos da rede.
CARACTERÍSTICAS DO SERVIDOR
Aguarda por uma solicitação de um cliente.
Atende a essas solicitações e responde aos clientes com os dados requisitados.
Pode estabelecer conexões com outros servidores visando atender uma solicitação
específica do cliente.
Fornece recursos adicionais de rede, além da infraestrutura de rede propriamente dita.
Interage por meio de interfaces diretamente com os usuários finais.
VANTAGENS DO MODELO CLIENTE-SERVIDOR
A arquitetura cliente-servidor permite que as responsabilidades de um sistema de
computação possam ser distribuídas entre vários computadores independentes
interconectados por meio de uma rede, o que resulta em maior facilidade de manutenção.
Os dados principais são armazenados nos servidores, que por regra possuem controles de
segurança mais robustos do que o da maioria dos clientes.
O gerenciamento das atualizações dos dados é mais fácil de ser feita nesse modelo do que
no paradigma peer-to-peer (P2P), onde as atualizações de dados podem necessitar ser
distribuídas e aplicadas a cada nó na rede, o que consome tempo e torna-se passível de
erro.
Muitas tecnologias avançadas de cliente-servidor foram projetadas para garantir a
segurança, facilidade de interface do usuário e facilidade de uso encontram-se disponíveis.
Funciona com vários clientes diferentes, sendo que os clientes podem ter capacidades
diferentes.
Entretanto, o modelo apresenta diversos problemas. Visto que a capacidade de oferecer serviços
ou recursos fica centralizada na figura do servidor, surge um problema:
O que fazer quando o número de requisições dos clientes ultrapassa a capacidade computacional
do servidor?
Essa pergunta não tem uma resposta de alta eficiência para aplicações em redes de
computadores. A sobrecarga de servidores é um problema real apesar de a capacidade
computacional dos servidores crescer consideravelmente ano após ano.
Além do fato de algumas requisições não serem atendidas, pela sobrecarga do servidor, no
modelo cliente-servidor, ainda há o fato de que o modelo não é robusto, ou seja, se um servidor
crítico falha, as requisições já feitas pelos clientes não poderão ser atendidas.
Esses motivos são a base para a concepção das redes peer-to-peer (P2P), que estudaremos
posteriormente ainda neste módulo.
ARQUITETURA MESTRE-ESCRAVO
Embora o nomesugira certa semelhança com o modelo de cliente-servidor, na arquitetura
mestre-escravo, as funções se invertem.
Mestre-escravo é um modelo de comunicação ou controle assimétrico onde um dispositivo ou
processo (o "mestre") controla um ou mais outros dispositivos ou processos (os "escravos") e
serve como seu hub de comunicação.
Em alguns sistemas, um mestre é selecionado a partir de um grupo de dispositivos elegíveis, com
os outros dispositivos atuando na função de escravos.
O processo de comunicação de um mestre com um escravo é denominado transação. Existem
dois tipos:
PERGUNTA-RESPOSTA
O mestre inicia uma transação com um de seus escravos. Todos os escravos o ouvem, mas
apenas aquele a quem a comunicação é dirigida responde. A transação pode envolver a troca de
várias mensagens.
DISSEMINAÇÃO SEM RESPOSTA
O mestre inicia uma transação para todos os escravos. Nenhum escravo responde explicitamente
e o mestre presume que eles terminarão suas execuções em algum ponto. Pode ser que um ou
mais escravos não recebam as informações corretamente e isso deve ser levado em
consideração ao utilizar esse tipo de transação.
Em uma transação mestre-escravo, certos parâmetros são definidos para organizá-los e garanti-
los, entre eles:
PROTOCOLO
Para que dois componentes que estão trocando informações sejam compreendidos, é necessário
que haja acordo sobre o conteúdo das informações trocadas. O conjunto de regras e convenções
que governam a comunicação é chamado de protocolo.
POLLING
O componente mestre interroga sob um esquema programado a sequência de escravos
disponíveis; cada escravo pode receber diferentes tipos de transações correspondentes a uma ou
mais tarefas.
TEMPO ESGOTADO (TIMEOUT)
Quando o mestre inicia a transação com um determinado escravo dentro do esquema de
consulta-resposta, pode acontecer que o escravo seja incapaz de responder ao mestre. Portanto,
o mestre deve lidar com um tempo limite para a resposta do escravo e, se não houver resposta,
abortar a transação para tentar novamente ou para continuar com seu esquema de polling.
NOVAS TENTATIVAS
Quando um escravo não responde e o mestre aborta a transação, ele deve decidir o que fazer:
continuar com o esquema de polling ou tentar novamente a transação abortada. O número de
vezes que uma transação será repetida é chamado de novas tentativas.
Dentro desses modelos, há ainda algumas variações. No projeto de um sistema com arquitetura
mestre-escravo, uma das decisões mais relevantes afeta a distribuição de responsabilidades, o
que se denomina granularidade.
Granularidade é a forma como o trabalho a ser executado é decomposto, ou seja, a carga
computacional ou o tamanho das tarefas atribuídas aos escravos.
Dois tipos são distinguidos:
GRANULARIDADE FINA
Consiste em distribuir o trabalho em muitas pequenas tarefas. Isso tem a vantagem de que, se
um escravo morrer, o mestre atribui a tarefa a outro escravo, com uma penalidade de tempo
muito pequena. Como desvantagem, você precisa de um número maior de escravos para realizar
a tarefa específica.
GRANULARIDADE GROSSA
Consiste em distribuir o trabalho em algumas tarefas grandes. Como vantagem, é apresentado
que não serão necessários muitos escravos para realizar uma tarefa. Por outro lado, se um
escravo morrer, a penalidade de tempo será significativa.
A implantação de um sistema com arquitetura mestre-escravo também permite a aplicação de
diversas variantes dependendo da utilização de um ou mais mestres.
São elas:
MESTRE-ESCRAVO SIMPLES
Estrutura clássica em que existe um único mestre que realiza a distribuição das tarefas entre os
componentes escravos que as executam. Também pode ser responsável pelo gerenciamento dos
próprios escravos (inicialização e parada, criação de mais instâncias em resposta ao aumento de
solicitações ou carga do sistema, prisão de escravos ociosos ou com comportamentos anômalos
etc.).
MESTRE-ESCRAVO MULTINÍVEL
Estrutura profunda na qual, ao invés de ter um único mestre supervisionando todos os escravos,
um ou mais níveis de mestres são introduzidos para esse fim. Esses níveis de mestres então
agrupam a supervisão de escravos ou outros mestres, de forma a conter o número de
componentes supervisionados por cada componente de supervisão. Esta variante é comum em
sistemas com grande número de escravos para evitar problemas de desempenho, ou seja, o
mestre fica saturado com alta frequência de comunicações de escravos e para os escravos.
MASTER SOBRESSALENTE
Estrutura que inclui um ou mais master sobressalentes, com o objetivo de aumentar a
disponibilidade. Esta variante apresenta vários mestres secundários para que o esquema geral da
arquitetura seja mantido. Se, durante a operação usual de monitoramento e controle o mestre
morre, ele é imediatamente substituído por outro (usando pontos de verificação), minimizando o
tempo em que o sistema deixa de estar operacional.
MESTRE COM REDUNDÂNCIA PASSIVA
Estrutura que inclui um ou mais masters sobressalentes, com o objetivo de aumentar a
disponibilidade. Esta variante, como no caso anterior, introduziria um novo mestre, que seria
constantemente atualizado em relação aos dados do mestre principal. Assim, se durante a
operação usual de supervisão e controle o mestre morrer, ele é imediatamente substituído por
outro que já está pronto para funcionar, reduzindo praticamente a zero o tempo em que o sistema
deixa de estar operacional.
Entre as vantagens da arquitetura mestre-escravo está a alta tolerância a erros. Isso significa
que caso um escravo morra, dificilmente o sistema será afetado e poderá continuar operando
sem problemas. A tarefa incompleta pode ser atribuída a outro escravo pelo mestre, e o escravo
com falha pode ser reiniciado ou substituído. Por outro lado, no caso de falecimento do mestre
(que é o caso que mais afeta o sistema, pois envolve uma penalidade maior ou até mesmo faz
com que pare totalmente) pode ser resolvido aplicando algumas das variantes que proporcionam
um substituto para o mestre.
Entre as desvantagens mais problemáticas está a necessidade de independência das tarefas a
serem desempenhadas pelo sistema, de forma a distribuí-las entre os escravos. Além disso, tal
distribuição deve fazer uso inteligente das capacidades dos escravos, para maximizar o
desempenho geral do sistema.
Assim, se uma arquitetura com muitos escravos e um único mestre for implantada, onde há
muitas comunicações entre ela e estes, o mestre pode sofrer problemas de saturação, sendo o
principal componente do sistema, isso resultaria em uma redução direta no desempenho. A
saturação (ou baixo desempenho) do mestre é tanto mais provável quanto mais
responsabilidades lhe forem atribuídas, portanto um sistema em que o mestre, além de distribuir
tarefas entre os escravos, é responsável por processar os dados por eles retornados, fazendo
algum tipo de computação global com esses dados, aumenta o risco de oferecer uma latência
maior do que a esperada.
Em termos gerais, a arquitetura mestre-escravo é adequada para a construção de sistemas de
tempo real, que precisam garantir o tempo de resposta. Também é frequentemente encontrado
em sistemas embarcados, que podem ser construídos combinando arquitetura de repositório ou
arquitetura de pipeline com mestre-escravo.
 COMENTÁRIO
Essa arquitetura, às vezes, é usada para estruturar a parte dos sistemas que lida com a
replicação de informações; portanto, na replicação do banco de dados, o banco de dados mestre
é considerado a fonte autorizada, e os bancos de dados escravos são sincronizados com ele.
Além de organizar a relação entre componentes de software de sistemas computacionais, a
organização mestre-escravo está presente nas camadas mais baixas dos níveis de rede, bem
como nas caraterísticas de arquitetura de computadores.
Os periféricos conectados a um barramento em equipamentos de informática geralmente
funcionam como escravos de um mestre (controlador). Os discos rígidos que usam ATA em
paralelotambém são organizados em um esquema mestre-escravo.
ATA
Acrônimo de Advanced Technology Attachment.
Tecnologia surgida nos anos 80, trazendo o inovador recurso de funcionamento do disco rígido
com o driver (controlador) integrado, tendo o objetivo de homogeneizar os tipos de conectores do
disco rígido à placa mãe e à fonte de energia.
POLLING
Abordamos a arquitetura de polling anteriormente, a agora passaremos a ver mais detalhes
dessa implementação.
O polling é um conceito que pode ser utilizado em diversas situações, tais como controle de
acesso à rede, gerenciamento de impressora, entre outros. Seu mecanismo consiste no processo
de um computador central, ou dispositivo de controle, interrogar cada estação ou recurso
existente que compõe o sistema verificando sua prontidão ou estado.
Em outras palavras, polling, ou operação com polling, na ciência da computação, refere-se à
amostragem ativa do status de um dispositivo externo por um programa cliente como uma
atividade síncrona.
Esse sistema é mais frequentemente usado em termos de entrada/saída (E/S); também é
conhecido como E/S com poll ou E/S orientada por software. A sondagem às vezes é usada
como sinônimo de sondagem em espera ocupada.
Nessa situação, quando uma operação de E/S é necessária, o computador não faz nada além de
verificar o status do dispositivo de E/S até que ele esteja pronto, momento em que o dispositivo é
javascript:void(0)
acessado. Em outras palavras, o computador espera até que o dispositivo esteja pronto.
 COMENTÁRIO
A sondagem também se refere à situação em que um recurso é testado continuamente quanto a
sua prontidão. Caso não esteja, o computador retorna para uma tarefa diferente. Apesar de ser
mais eficiente que a espera ocupada, não desperdiçando tantos ciclos de CPU, isso, geralmente,
não é tão eficiente quanto a alternativa à E/S controlada por interrupção de polling, ou seja, com
um dispositivo de hardware dedicado a esta tarefa.
A grande desvantagem do mecanismo de polling é que se houverem muitos dispositivos no
sistema ou rede, o tempo necessário para percorrer cada um dos dispositivos e voltar ao inicial
será muito alto. A consequência é que pode exceder o tempo disponível para atender ao
dispositivo de E/S.
O mecanismo de polling pode ser descrito nas seguintes etapas:
AÇÕES DA ESTAÇÃO:
1
A estação verifica continuamente o bit de ocupado até que ele se torne livre, por exemplo,
quando o bit assumir o valor 0;
2
Estando o bit marcado como livre, a estação escreve o comando no registro de comando. Caso o
host esteja enviando dados para a saída, ele irá marcar o bit de gravação e enviar um byte de
dados para o registrador de saída de dados.
Caso a estação esteja recebendo dados, ela irá ler o registrado de entrada de dados e define o
bit de leitura para 0 como o próximo comando;
3
A estação irá definir o bit de pronto para comando (command-ready) para 1.
AÇÕES DO CONTROLADOR:
1
Quando o controlador verificar que o bit command-ready está definido, ele configura o bit
ocupado como 1.
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
2
O controlador irá ler o registro de comando. Caso o bit de gravação interno estiver definido, ele lê
os dados do registrador de saída e executa as operações de E/S necessárias no dispositivo.
Caso o bit de leitura esteja definido, os dados do dispositivo serão carregados no registro de
entrada de dados para que a estação possa ler.
3
Quando terminarem as operações, o controlador libera o bit command-ready, limpa o bit de erro
para mostrar que a operação foi bem-sucedida e libera o bit ocupado.
O ciclo de polling pode ser definido como o tempo que leva para, após ter sido consultado em
dado momento, o ciclo receba uma nova consulta. O tempo ideal para cada ciclo depende de
vários aspectos, tais como, retardo esperado para cada componente responder e a sobrecarga,
por exemplo, tempo do processador e largura de banda da pesquisa.
Na votação nominal (roll call polling), o controlador irá consultar cada recurso em uma lista em
uma sequência fixa. Neste tipo de polling, é necessário que seja configurado um mecanismo de
temporização para aguardar a resposta de cada recurso que foi consultado, evitando travamentos
do sistema caso ele não responda. Esse tipo de votação pode ser ineficiente caso haja muitos
elementos a serem consultados, sendo poucos ativos e, também, caso a sobrecarga para as
mensagens de consulta seja alta.
No hub polling, ou token polling, cada recurso pesquisa pelo próximo recurso em uma
determinada sequência fixa, até que o primeiro recurso dessa sequência seja alcançado. E
quando isso ocorre, o ciclo de polling começa novamente.
 ATENÇÃO
O mecanismo de polling é empregado em diversas situações na área de computação,
principalmente para controlar a execução ou a sequência de transmissão dos elementos
envolvidos.
Por exemplo, em sistemas operacionais multitarefa, pode ser utilizado para que vários processos
concorrentes possam disputar o uso do processador ou de dispositivos de E/S.
Outro exemplo seria na área de redes, quando o canal de comunicação é compartilhado entre
diversos dispositivos. Para que não ocorra colisão, é necessário que seja empregado um
javascript:void(0)
javascript:void(0)
mecanismo de controle de acesso ao meio, dentre eles o polling. Uma estação mestre irá
interrogar as estações escravas para que possam transmitir as informações por meio do canal.
REDES PEER-TO-PEER (P2P)
Nas redes P2P, os nós da rede funcionam tanto como cliente quanto servidor. Essa arquitetura
permite que serviços e dados sejam compartilhados sem a necessidade de um servidor central,
conforme imagem a seguir.
 Arquitetura-peer-to-peer.
O fato mais interessante das redes P2P é que todos os peers ou participantes da rede são
igualmente privilegiados na aplicação. Cada computador agindo como um nó fica responsável por
uma parte dos recursos da rede, podendo esses recursos serem armazenamento de dados,
poder de processamento ou até mesmo largura de banda. Diferentemente do modelo cliente-
servidor, onde um servidor central alimenta os clientes da rede, nos sistemas P2P todos os
computadores interligados são fornecedores e consumidores de recurso.
 SAIBA MAIS
As redes P2P entraram em cena a partir de 1999. A primeira aplicação generalizada foi para troca
de músicas protegidas por direitos autorais sem a permissão dos proprietários dos direitos
autorais até que o aplicativo (Napster) foi fechado pelos tribunais em meio a grande controvérsia.
No entanto, a tecnologia ponto a ponto tem muitos usos interessantes e legais. Outros sistemas
continuaram em desenvolvimento, com tanto interesse dos usuários que o tráfego P2P
rapidamente eclipsou o tráfego da web.
Atualmente, o BitTorrent é um dos protocolos P2P mais populares. É tão amplamente usado para
compartilhar vídeos (licenciados e de domínio público), bem como outros conteúdos, que é
responsável por uma grande fração de todo o tráfego da internet. Outra plataforma que utiliza a
arquitetura peer-to-peer são as criptomoedas.
A ideia básica de uma rede de compartilhamento de arquivos P2P é que muitos computadores se
reúnam e reúnam seus recursos para formar um sistema de distribuição de conteúdo. Os
computadores geralmente são simplesmente computadores domésticos. Eles não precisam ser
máquinas em centros de dados da internet.
Os computadores são chamados de pares porque cada um pode atuar alternadamente como
cliente para outro par, obtendo seu conteúdo, e como servidor, fornecendo conteúdo a outros
pares. O que torna os sistemas ponto a ponto interessantes é que não há infraestrutura dedicada.
Todos participam da tarefa de distribuição de conteúdo e, geralmente, não há um ponto central de
controle.
 EXEMPLO
Considere uma rede P2P composta por N usuários médios, cada um com conectividade de banda
larga a 1 Mbps. A capacidade de upload agregada da rede P2P, ou taxa na qual os usuários
podemenviar tráfego para a internet, é N Mbps. A capacidade de download, ou taxa na qual os
usuários podem receber tráfego, também é de N Mbps. Cada usuário pode fazer upload e
download ao mesmo tempo, porque eles têm um link de 1 Mbps em cada direção.
Não é óbvio que isso deva ser verdade, mas acontece que toda a capacidade pode ser usada de
forma produtiva para distribuir conteúdo, mesmo no caso de compartilhar uma única cópia de um
arquivo com todos os outros usuários.
Para ver como isso pode ser verdade, imagine que os usuários estão organizados em uma árvore
binária, com cada usuário não folha enviando para dois outros usuários. A árvore levará a única
cópia do arquivo para todos os outros usuários. Para usar a largura de banda de upload de tantos
usuários quanto possível em todos os momentos (e, portanto, distribuir o arquivo grande com
baixa latência), precisamos canalizar a atividade de rede dos usuários. Imagine que o arquivo
está dividido em 1000 partes. Cada usuário pode receber uma nova peça de algum lugar na
árvore e, ao mesmo tempo, enviar a peça recebida anteriormente.
Dessa forma, uma vez que o pipeline é iniciado, depois que um pequeno número de peças (igual
à profundidade da árvore) são enviadas, todos os usuários não folha estarão ocupados enviando
o arquivo para outros usuários. Visto que existem aproximadamente N/2 usuários não folha, a
largura de banda de upload desta árvore é N/2 Mbps. Podemos repetir esse truque e criar outra
árvore que use os outros N/2 Mbps de largura de banda de upload, trocando as funções de nós
folha e não folha. Juntas, essa construção usa toda a capacidade.
CLUSTER
Um cluster de computador é um conjunto de computadores fracamente ou fortemente conectados
que funcionam juntos para que, em muitos aspectos, possam ser vistos como um único sistema.
Os clusters de computador têm cada nó definido para executar a mesma tarefa, controlado e
programado por software.
Os componentes de um cluster geralmente são conectados uns aos outros por meio de redes
locais rápidas, com cada nó (computador usado como servidor) executando sua própria instância
de sistema operacional. Na maioria das circunstâncias, todos os nós usam o mesmo hardware e
o mesmo sistema operacional, embora em algumas configurações, diferentes sistemas
operacionais podem ser usados em cada computador ou hardware diferente.
Os clusters são, geralmente, implantados para melhorar o desempenho e a disponibilidade em
relação a um único computador, embora sejam, normalmente, muito mais econômicos do que
computadores únicos de velocidade ou disponibilidade comparáveis.
Os clusters de computador surgiram como resultado da convergência de uma série de tendências
de computação, incluindo a disponibilidade de microprocessadores de baixo custo, redes de alta
velocidade e software para computação distribuída de alto desempenho.
Um dos problemas ao projetar um cluster é o quão fortemente acoplados os nós individuais
podem ser. Por exemplo, um único trabalho de computador pode exigir comunicação frequente
entre os nós. Isso implica que o cluster compartilha uma rede dedicada, está densamente
localizado e provavelmente tem nós homogêneos. O outro extremo é quando um trabalho de
computador usa um ou poucos nós e precisa de pouca ou nenhuma comunicação entre nós,
aproximando-se da computação em grade.
COMPUTAÇÃO EM GRADE
javascript:void(0)
“A computação em grade é um grupo de computadores em rede que trabalham em conjunto,
como um super computador virtual, para executar tarefas grandes, como analisar grandes
conjuntos de dados e modelagem do clima.”
Fonte: Microsoft Azure.
Em um cluster, os programas aplicativos nunca veem os nós computacionais (também chamados
de computadores escravos), mas apenas interagem com o mestre, que é um computador
específico que cuida do agendamento e gerenciamento dos escravos. Em uma implementação
típica, o mestre tem duas interfaces de rede, uma que se comunica com a rede privada para os
escravos e a outra para a rede de uso geral da organização.
Os clusters de computador são historicamente executados em computadores físicos separados
com o mesmo sistema operacional. Com o advento da virtualização, os nós do cluster podem ser
executados em computadores físicos separados com diferentes sistemas operacionais, mas é
adicionada uma camada virtual acima deles a fim de parecerem semelhantes.
Existem vários tipos de cluster. Os mais conhecidos são:
CLUSTER DE ALTO DESEMPENHO
Também conhecido como cluster de alta performance, funciona permitindo que ocorra uma
grande carga de processamento com um volume em computadores comuns e utilizando sistema
operacional gratuito, o que diminui seu custo.
CLUSTER DE ALTA DISPONIBILIDADE
É aquele que consegue permanecer ativo por um longo período e em plena condição de uso.
Além disso, consegue detectar erros se protegendo de possíveis falhas.
CLUSTER PARA BALANCEAMENTO DE CARGA
Tem como função controlar a distribuição equilibrada do processamento. Requer um
monitoramento constante na sua comunicação e em seus mecanismos de redundância, pois, se
ocorrer alguma falha, seu funcionamento será interrompido.
ARQUITETURAS DE SISTEMAS
DISTRIBUÍDOS
No vídeo a seguir, apresentamos as arquiteturas de sistemas distribuídos apresentando
exemplos de aplicação, vantagens e desvantagens.
VERIFICANDO O APRENDIZADO
CONCLUSÃO
CONSIDERAÇÕES FINAIS
Vimos inicialmente as características principais dos sistemas distribuídos. Em seguida, vimos a
nomenclatura das principais estruturas de computação paralela que podem ser usadas nesses
sistemas. Com o conhecimento da lei de Amdahl, vimos o ganho teórico máximo de tempo de um
sistema com diversos processadores em paralelo, bem como observamos que a presença de
itens obrigatoriamente serializáveis limitam esse ganho. Além disso, aprendemos o conceito de
speedup.
Depois, vimos a diferença fundamental entre memória compartilhada e distribuída, com enfoque
principal nas vantagens e desvantagens de cada uma.
Também aprendemos o que é paralelismo de dados e de tarefas, suas vantagens e diferenças, e
verificamos que esse tipo de abordagem já está presente em nossos computadores de mesa.
Neste tema, também introduzimos algumas arquiteturas de sistemas distribuídos, desde a mais
utilizada, o cliente-servidor, até os sistemas mestre-escravo e P2P. Por fim, completamos nosso
conhecimento vendo como funciona a estrutura de polling e abordamos o conceito de cluster de
computadores e seus principais tipos.
 PODCAST
No podcast a seguir, apresentamos o conceito de sistema distribuído, sua evolução histórica e
como eles contribuíram para a área de TI e para a vida das pessoas.
AVALIAÇÃO DO TEMA:
REFERÊNCIAS
BUYYA, R.; VECCHIOLA, C.; SELVI, T. Principles of Parallel and Distributed Computing.
Mastering Cloud Computing, Morgan Kaufmann, 2013.
COULOURIS, G. et al. Sistemas distribuídos: conceitos e projetos. 5. ed. Porto Alegre:
Bookmann, 2013.
MICROSOFT. Microsoft Azure, 2021. Plataforma destinada à execução de aplicativos e
serviços, baseada nos conceitos da computação em nuvem. Consultado na internet em: 15 abr.
2021.
TANENBAUM, A. S.; STEEN, M. V. Distributed Systems: Principles and Paradigms. 1. ed. Upper
Saddle River, Pearson Prentice Hall, 2006.
EXPLORE+
Para saber mais sobre os assuntos explorados neste tema, pesquise:
Os livros mais adotados para sistemas distribuídos, que são os de COULOURIS et al., 2013
e TANENBAUM e STEEM, 2006. Neles, podem ser encontrados os principais conceitos
referentes a esses assuntos.
O tutorial de OpenMP do Lawrence Livermore National Laboratory, onde se encontram
orientações bem detalhadas sobre programação paralela e distribuída.
Um exemplo completo e detalhado da multiplicação de matrizes, disponível em Matrix
Multiplication with OpenMP e Mxm Openmp c.
CONTEUDISTA
Sergio Kostin
 CURRÍCULO LATTES
javascript:void(0);