Baixe o app para aproveitar ainda mais
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áquina são processadasde 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 no caso da memória javascript:void(0) javascript:void(0) 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 sua fração paralela e sua fração serial ( ). Além disso, chamemos o tempo de execução (em segundos) do algoritmo ao usar processadores. Então, a seguinte relação se mantém: 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 é, ) mais o tempo de execução de sua parte paralela em um processador (ou seja, ) 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: P S S + P = 100% T (n) n T (n)≥ S . T (1)+ P . T ( 1 ) n S.T (1) P .T (1) 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, ). 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 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âneas eexecutar 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 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. T (∞)≈ S.T (1) S.T (1) S = 0 p 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: 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 é bastante decepcionante. Começamos com um aumento de velocidade realmente incrível de usando 10 processadores, e então caímos para apenas 50x ao usar 100 processadores e um insignificante ao usar 1.000 processadores. Exemplo da lei de Amdahl e de speedup. Speedup = = Temposerial TempoParalelo Ts Tp T (1)= 100s T (10)≈ 0, 01. 100s + = 10, 9s ⇒ Speedup = = 9, 2x 0,99*100s 10 100 10,9 T (100)≈ 1s + 0, 99s = 1, 99s⟹ Speedup = = 50, 2x1001,99 T (1000)≈ 1s + 0, 099s = 1, 099s ⇒ Speedup = = 91x1001,099 n 9, 2x 91x A imagem anterior mostra a aceleração de melhor caso esperada para o mesmo algoritmo (calculado até ). Não importa quantos processadores usamos; não podemos obter um aumento de velocidade maior que , 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. ENTENDENDO O SPEEDUP No vídeo a seguir, apresentamos o conceito de speedup, utilizando a Lei de Amdahl n = 5. 000 100x javascript:void(0) 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: //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 Defina o número de threads para executar o programa usando a variável externa. 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: #pragma omp parallel { printf("Ola Mundo... da thread = %d\n", omp_get_thread_num()); } 1 2 3 4 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. 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. ./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 aluno@ubuntu: ~$ ./hello Ola Mundo... da thread = 1 1 2 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. 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. 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 3 4 5 6 7 8 9 10 11 12 javascript:void(0) 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; 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,rank,hostna // finalizando o MPI MPI_Finalize(); } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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. 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 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 . No caso de execução sequencial, o tempo gasto pelo processo será 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, otempo gasto seria reduzido para , desconsiderando eventuais atrasos de execução e operações obrigatoriamente 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 n Ta n × Ta (n × Ta)/4 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 , assumindo que os comprimentos de linha e de coluna de ambas as matrizes são e para multiplicação e adição, respectivamente. 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 pode ser finalizado em em vez de quando executado em paralelo usando processadores. O(n3) n O(n) // Multiplicacao de matrizes for (i = 0; i < row_length_A; i++) { for (k = 0; k < column_length_B; k++) { 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]; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 A[m x n].B[n x k] O(n) O(m * n * k) m * k Matriz A versus Matriz B. 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 // 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; for (j = 0; j < column_length_A; j++){ sum += A[i][j] * B[j][k]; } C[i][k] = sum; } } 1 2 3 4 5 6 7 8 9 10 11 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 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 arquiteturaque podem ser aplicados tanto em sistemas paralelos como em sistemas distribuídos. São os seguintes: Cliente-servidor Mestre-escravo Polling 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çãodas redes peer-to-peer (P2P), que estudaremos posteriormente ainda neste módulo. ARQUITETURA MESTRE-ESCRAVO Embora o nome sugira 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áticageralmente funcionam como escravos de um mestre (controlador). Os discos rígidos que usam ATA em paralelo també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. javascript:void(0) 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 é 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 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) javascript:void(0) javascript:void(0) 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 largaa 1 Mbps. A capacidade de upload agregada da rede P2P, ou taxa na qual os usuários podem enviar 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 usuários não folha, a largura de banda de upload desta árvore é Mbps. Podemos repetir esse truque e criar outra árvore que use os outros 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. N/2 N/2 N/2 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 “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. javascript:void(0) 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);DESCRIÇÃO Conceitos introdutórios de programação paralela, variáveis compartilhadas, sincronização de processos, semáforos, monitores e ambientes de programação. PROPÓSITO Compreender os conceitos fundamentais de programação paralela e as técnicas inerentes a esse ambiente, para permitir ao aluno o desenvolvimento de aplicações executadas em ambientes distribuídos. OBJETIVOS MÓDULO 1 Identificar problemas e soluções para o uso de variáveis compartilhadas MÓDULO 2 Reconhecer condições de corrida e recursos utilizados para tratamento MÓDULO 3 Distinguir as diferentes abstrações de programação, como semáforos, monitores e suas aplicações MÓDULO 4 Empregar diferentes ambientes de programação, em especial corrotinas, Pthreads, OpenMP e Erlang INTRODUÇÃO O desenvolvimento dos sistemas distribuídos nos permitiu acessar diversos tipos de aplicações, disponibilizadas na internet. Essas aplicações mudaram a forma de estudarmos, de trabalharmos, de nos divertimos e até a maneira como as pessoas se relacionam. Uma aplicação distribuída, porém, tem algumas complexidades. Por ser distribuída, existem vários processos que vão compô-la e, consequentemente, há a necessidade de uma coordenação entre esses processos. Vários processos sendo executados simultaneamente dão origem ao conceito de programação paralela − divisão de uma tarefa computacional em instâncias (processos) independentes e que podem ser executados de forma paralela. Os processos que são executados em paralelo, no entanto, podem trazer algumas situações inconvenientes durante sua execução. Imagine, por exemplo, que existe um recurso − como uma impressora − que deve ser acessado por esses processos que estão executando em paralelo. Se todos quiserem acessar simultaneamente, teremos problemas para definir quem irá imprimir primeiro. É necessário conhecer os fundamentos da computação paralela para entender os problemas que existem nesse paradigma computacional e quais mecanismos podemos utilizar para evitar ou, pelo menos, minimizar os seus efeitos. Por fim, conheceremos diversas plataformas que podem ser utilizadas para o desenvolvimento de programas paralelos. Antes de iniciar o módulo 1, assista ao vídeo a seguir da entrevista com o Professor Jairo Panetta. Ele aborda o que é computação paralela, assim como o seu histórico e sobre onde é possível atuar no mercado. MÓDULO 1 Identificar problemas e soluções para o uso de variáveis compartilhadas VARIÁVEIS COMPARTILHADAS Antes de mais nada, saiba que: Em programas de memória compartilhada, as variáveis podem ser compartilhadas ou privadas. Em um ambiente onde um processo possui vários threads, as variáveis compartilhadas podem ser lidas ou escritas por qualquer um deles, e variáveis privadas normalmente podem ser acessadas apenas por um thread. Quando a comunicação entre os threads é feita por meio de variáveis compartilhadas, ela é implícita, não explícita − como por soquetes ou named pipes. COMENTÁRIO Em muitos ambientes, os programas de memória compartilhada usam threads dinâmicos. Nesse modelo, geralmente há um thread mestre e, em qualquer momento, uma coleção (possivelmente vazia de início) de threads de trabalho. O thread mestre normalmente espera por solicitações de trabalho − por exemplo, em uma rede −, e, quando um novo pedido chega, ele bifurca/inicia um thread de trabalho. Esse thread executa a solicitação e, quando conclui o trabalho, termina e se junta ao thread mestre. Esse tipo de modelo faz uso eficiente dos recursos do sistema, uma vez que os recursos exigidos por um thread só estão sendo usados enquanto este está realmente em execução. PARADIGMA DE THREAD ESTÁTICO Uma alternativa ao paradigma dinâmico é o paradigma de thread estático. Nesse paradigma, todos os threads são bifurcados/iniciados após qualquer configuração necessária pelo thread mestre e os threads são executados até que todo o trabalho seja concluído. Depois que os threads se juntam ao thread mestre, este pode fazer alguma limpeza (por exemplo, liberação de memória) e, então, também finaliza esses threads. ATENÇÃO Em termos de uso de recursos, isso pode ser menos eficiente: se um thread estiver ocioso, seus recursos (por exemplo: pilha, contador de programa etc.) não podem ser liberados. No entanto, bifurcar e unir threads podem ser operações bastante demoradas. Portanto, se os recursos necessários estiverem disponíveis, o paradigma de thread estático tem potencial de melhor desempenho do que o paradigma dinâmico. Ele também tem a virtude de estar mais próximo do paradigma mais amplamente usado para programação de memória distribuída, então, parte da memória que é usada para um tipo de sistema é preservada para o outro. Assim, o paradigma de thread estático é o mais frequente. CÁLCULO NÃO DETERMINÍSTICO Em qualquer sistema MIMD, no qual os processadores são executados de forma assíncrona, é provável que haja não determinismo das tarefas. Um cálculo é não determinístico se uma entrada específica pode resultar em saídas diferentes. Se vários threads estiverem executando de forma independente, a taxa relativa na qual eles concluirão as instruções varia de execução para execução e, portanto, os resultados do programa podem ser diferentes a cada execução. EXEMPLO Suponha que temos dois threads, um com id 0 e o outro com id 1. Suponha também que cada um está armazenando uma variável privada x, o valor de x na thread 0 é 5 e na thread 1 é 8. Além disso, imagine que ambos os threads executem o seguinte código: printf("Thread %d > val = %dnn", x); Então, a saída pode ser: Thread 0 > val = 5 Thread 1 > val = 8 Mas pode ser também: Thread 1 > val = 8 Thread 0 > val = 5 Na verdade, as coisas podem ser ainda piores: a saída de um thread pode ser interrompida pela saída de outro thread. No exemplo anterior, estamos apenas tratando de uma saída. No entanto, como os threads estão executando de forma independente e interagindo com o sistema operacional, o tempo que leva para um thread completar um bloco de instruções varia de execução para execução. Portanto, a ordem em que essas instruções são concluídas não pode ser prevista. COMENTÁRIO Em muitos casos, o não determinismo não é um problema. Em nosso exemplo, uma vez que rotulamos a saída com a classificação do tópico, a ordem em que a saída aparece provavelmente não importa. No entanto, também existem muitos casos em que o não determinismo, especialmente em programas de memória compartilhada, pode ser desastroso, porque pode facilmente resultar em erros de programa. Vejamos um exemplo simples com dois threads: suponha que cada thread calcule um valor inteiro, que ele armazena em uma variável privada val, e que queremos adicionar os valores armazenados em val em um local de memória compartilhada x que foi inicializado em 0. Ambos os threads, portanto, desejam executar um código semelhante a este: val = Compute_val(my_rank); x += val; Agora, lembre-se de que uma adição normalmente requer o carregamento dos dois valores a serem adicionados aos registradores, a adição dos valores e, por fim, o armazenamento do resultado. Para manter o exemplo relativamente simples, vamos presumir que os valores são carregados da memória principal diretamente nos registradores e armazenados na memória principal diretamente dos registradores. Na tabela a seguir, visualizamos uma sequência possível de execução desses threads utilizando os valores 5 e 8 do exemplo anterior: Tempo Núcleo 1 Núcleo 2 0 Carrega o valor de val Chama a função Compute_val 1 Carrega x = 0 para o registrador Carrega o valor de val 2 Carrega val = 5 para o registrador Carrega x = 0 para o registrador 3 Adiciona val a x Carrega val = 8 para o registrador 4 Armazena x = 5 Adiciona val a x 5 Inicia outro trabalho Armazena x = 8 Atenção! Para visualização completa da tabela utilize a rolagem horizontal Tabela: Saída de eventos de dois threads distintos. Elaborada por: Sergio Kostin
Compartilhar