Sistemas Multirprocessadores

Introdução

A industria de computadores sempre buscou e buscara aumentar seu desempenho para um melhor aproveitamento das outras industrias. Todos aproveitam dos novos desempenham que cientistas da
computação descobrem e inventam, sendo eles responsaveis por um importante papel na evolução da ciencia como um todo.
Para um maior poder de processamento, começou-se a usar vários processadores dentro de um mesmo sistema, surgindo assim o “sistemas com múltiplos processadores”, onde cada CPU executa suas atividades de uma velocidade normal, mas trabalhando em conjunto aumentam muito o poder de processamento.
A demanda que requer tais sistemas com poder de processamento elevado variam muito, desde modelagem de corrente de ar ao redor das asas das aeronaves até entendimento das interações na recepção de drogas pelo cerebro.
Com o desenvolvimento da internet, surgiu a possibilidade de interligar varias computadores com um mesmo objetivo, surgindo sistemas com multiplos processadores, mesmo que distante uns dos outros. O obstaculo em tais conexões é o sistema de comunicação, que ainda impede um desempenho superior.
O objetivo de todo sistema com múltiplos processadores, ou qualquer ligação, como de componetes eletrônicos, codificadas por bits, é reduzir o tempo de envio de mensagens, reduzir a distância e aumentar a eficiencia na lógica envolvida.
Existem três tipos de sistemas com multiplos processadores:
Os mais rápidos, que tem o acesso a memória em normalmente de 2 a 50 ns. (m 1 ns, a luz percorre 29,9792458 cm exatos no vácuo pela definição do metro ), são os que tem a memória compartilhada(FIGURA X). Nesse modelo, todo CPU tem acesso igual a qualquer parte da memória fisica.
Em seguida, com uma velocidade de 10 a 50 microsegundos (um microsegundo representa um milionesimo de segundo, ou 10^-6 de segundo) aparece o sistema de pares de CPU-memória(FIGURA Y), onde são conectados por uma interconexão de alta velocidade. Esses sistemas são conhecido como multicomputadores, pois representam várias sistemas de processamento de um CPU interconectadas. Não existe memória compartilhada, como no caso anterior, o que torna mais lento o seu nivel de processamento, formando assim apenas um sistemas de computadores interligados.Pórem, sua construção é mais fácil do que do sistema anterior.
O terceiro sistema, é o modelo constituido pela internet(FIGURA Z). Nele, temos sistemas completos interligados, por uma rede de longa distância, também chamados de sistemas distribuidos. Esse modelo é muito parecido com o anterior, se diferenciando pelo espaço-tempo dos seus membros.

1-Multiprocessadores de memória compartilhada

Um multiprocessador de memória compartilhada, ou simplesmente multiprocessador, é um sistema onde dois ou mais cpu´s compartilham a mesma memória RAM. O problema mais usual, neste tipo de sistema é a diversificação de resultados de um mesmo dado de entrada, por consequencia da alteração dos dados por um outro processador. Pórem, essa é a vantagem, quando bem programada, do uso do sistema de memória compartilhada, um trabalho é feito por mais de um processador.

Os sistemas operacionais que funcionam com os multiprocessadores executam as mesmas tarefas dos sistemas operacionais com sistemas simples, como chamadas de sistemas e gerenciamento de memória. Contudo, usa seu sistema de memória compartilhada para aumentar o desempenho em algumas tarefas, como gerenciamento de recursos e escalonamento.

FIGURA 8.1

1.1 hardware de um sistema com multiprocessadores

O hardware de um sistema multiprocessador pode ser dividido em dois classes: os que acessam qualquer palavra ou bloco de memória no mesmo tempo, chamado de UMA (UNIFORM MEMORY ACESS- Acesso Uniforme a Memória) e os que acessam partes da memória com mais rapidez do que outras partes, chamados de NUMA (NOUNIFORM MEMORY ACESS-Acesso a Memória Não-Uniforme)

-Multiprocessadores NUMA Baseados em Barramento

Os multiprocessadores geralmente se comunicam com apenas um barramento. Quando o processador precisa alocar ou capturar uma palavra que está na memória, e o barramento não se encontra ocupado, ele envia informações junto com com os sinais de controle da respectiva função através do barramento. Mas este barramento geralmente se encontra ocupado, surgindo assim o principal problema dos multiprocessadores NUMA baseados em barramento.

Quando há vários processadores, dificilmente o barramento se encontra disponivel. O fator que limita o desempenho de processamento neste caso é o tamanho do barramento. Em casos, há a possibilidade de colocar uma memória cache para cada CPU, para que algumas leituras usem apenas o cache local, liberando tráfego no barramento, e possibilitando o sistema a incluir novos CPU´s em sua estrutura. Na memória cache, é trabalhada o bloco que encontra a palavra referenciada, levada para dentro do cache local, chamando esse bloco de palavras dentro do cache local de linha de cache.

Os blocos de cache podem ser somente-leitura, caso em que não há limites de cópia desse bloco em outra memória cache ao mesmo tempo, ou leitura-escrita, que acontece quando a CPU vai trabalhar os dados referentes a esse bloco do cache. Se existe uma palavra que está sendo processada por uma CPU dentro do cache de outra CPU, e essa cópia ainda não foi trabalhada, ele é instruido a descartar a sua cópia, e deixar a CPU interessada processar e depois copiarem o mesmo bloco processado.Se outra cache tem a cópia já trabalhada, ela é instruida a copiar para o barramento para ser repassada para o outro CPU interessado ou copiá-lo diretamente na memória. Esse procedimento, com mais uma série de regras são chamados de protocolo de coerência de cache.

Há ainda a possibilidade de cada CPU ter a sua memória local e privada, além do cache. Para esse recurso ser otimizado, cabe ao compilador colocar as informações necessarias, como o código do programa e as constantes dentro dentro da memória local. Com esse recurso, a memória compartilhada só é acessada para as variavéis compartilhadas que podem ser escritas. Com isso, o compilador se torna ainda mais importante, reduzindo assim o tráfego de barramento.

-Multiprocessadores UMA Baseados em Chaves Crossbar

O uso de caches ainda não é suficiente para deixar ilimitado o numero de CPU´s conectados em barramento, geralmente limitando em 16 ou 32 CPU´s. Para a resolução deste problema, os sistemas multiprocessadores fazem o uso de chaves Crossbar, que são usadas há tempos nos sistemas de telefonia, que possibilitam que qualquer memória se conectar diretamente com qualquer CPU.

O sistema de chaves Crossbar é composto por chaves que interligam as partes. Quando essas se encontram fechadas, formam um caminho direto entre a CPU e a memoria, tornando usavel seu sistema de comunicação.

O número de combinações é o numero de memória vezes o numero de CPU´s. Uma grande vantagem desse sistema é que a conexão nunca é negada, pois independe de outras partes do sistema. E ainda, o sistema não precisa ser previamente avisado antes de realizar uma conexão entre

a memoria e a CPU. No caso de duas CPU´s acessar a mesma memoria ao mesmo tempo, essa é dividida para atender as duas CPU´s.

A grande desvantagem desse sistema com o uso de chaves Crossbar é o numero muito elevado das chaves, que cresce exponencialmente ao acrescentar-mos CPU´s e memorias, tornando um projeto com mais de mil CPU´s ou memoria impraticavel. Mas para um projeto de tamanho medio, com media de 30 CPU´s e memoria, essa opção se torna a mais usual.

-Multiprocessadores UMA Baseados em Redes de Comutação MultiEstagio.

As redes de comutação multiestagio é composta por duas opções de entrada e duas opções de saida para cada trecho de rede. Com a mensagem colocada no trecho, ela ganha duas possibilidades até seguir seu caminho desejado.

A mensagem é composta de acordo com o conteudo da mensagem, porem existem quatro campos obrigatorios. O campo Modulo passa a informação para o próximo trecho do programa de qual memoria usar, o campo Endereço informa em que trecho do sistema a mensagem se encontra, e os campos codigoOP e Valor representam a operação a ser feita e o valor da operação, respectivamente.

Um modelo muito usado é a rede Omêga, composta por 8 CPU´s e 8 memórias, usando 12 chaves. Esse modelo, se projetado com o sistema de chaves Crossbar, usaria 64 chaves.

A grande desvantagem desse modelo Omêga é que ela é rede bloqueante. Isso acontece quando duas CPU´s queiram usar a mesma chave, fazendo com que uma tenha que esperar o encaminhamento para poder seguir seu caminho. As esperas podem acontecer na tentativa do uso simultaneo da mesma chave ou do mesmo fio (ou cabo).

-Multiprocessadores NUMA.

Os sistemas apresentados anteriormente não são usaveis em redes de grande porte, com mais de 100 CPU´s e 100 memórias, por necessitarem de um hardware pesado, o que custaria muitos recursos financeiros para a sua implementação.

O sistema NUMA se assemelha ao sistema UMA pois também possui um único espaço de endereçamento para todas as CPU´s para realizar a sua interconexão, mas diferentemente do sistema UMA, o sistema NUMA possui o acesso a memória local mais rapido do que o acesso remoto.

Os sistemas NUMA possui três caracteristicas principais: Existe um espaço de endereçamento único, visivel a todas as CPU´s, o acesso a memoria local é feito via instruções LOAD e STORE, e o acesso a memoria local é mais rapido do que o acesso a memoria remota. Elas ainda se dividem em maquinas que possuem memoria cache local (CC NUMA – NUMA Cache-Coherent ou seja, NUMA com coerencia de Cache) e maquinas que não possuem cache local (NC NUMA – No Cache NUMA, ou seja, NUMA sem memoria cache).

O modelo mais usado em sistemas multiprocessador é o CC NUMA, que toma como base um diretorio que faz a interconexão entre as maquinas, e faz o gerenciamento dos processos. Essa base de dados é pesquisada em cada instrução que referencia a memoria, possuindo um hardware muito veloz para reponder a pesquisa em uma fração de um ciclo de barramento.

Exemplo de um Multiprocessador baseado em diretorio.

Multinucleo

Com os transistores cada vez mais pequenos, aumentou-se o numero de transistores em cada chip. Os processadores da classe Intel Core2 Duo contêm cerca de 300 milhões de transistores. Uma alternativa para o aumento de eficiencia é alocar dois nucleos no mesmo chip.Chips com 3 ou núcleos já estão presentes no mercado, e futuramente trabalharemos com chips com centenas de nucleos.

Pórem, eles semprem dividem a mesma memoria principal, que proporciona cada palavra da memoria com um valor. Há um processo que, com a modificação de uma palavra, todas as suas copias que não foram trabalhadas são apagadas, afim de evitar retrabalho, conhecido como espionagem.

Há diferenças que devem ser consideradas para a formação do software. Primeiramente, os multiprocessadores baseados em barramento, cada CPU tem (seguindo o modelo da Intel) sua cache própria, sendo que a diferença para o processador que ira usar o software (Intel ou não) deve ser considerado na hora de sua codificação. No modelo Intel, quando um CPU necessita de mais memoria cache do que possui, ele “empresta” de outra CPU. Como desvantagem, um problema apresentado por uma CPU pode afetar a CPU do mesmo processador, problema que não ocorre nos processadores tradicionais.

Na classe de processadores multinucleo, exitem tambem os sistemas em um chip, que possuem uma ou mais CPU principal, além do nucleo que se dedica exclusivamente as operações especiais, como os decodificadores.

Mesmo com essa nova ferramenta nas mãos dos programadores, a programação paralela ainda é escassa. Sincronização e eliminações de situações de corrida são problemas presentes hoje. Além da falta de conhecimento de que quais processos realmente necessitam desse recurso.

Tipos de Sistemas Para Multiprocessadores

Nos sitemas multiprocessadores, várias formas do Sistema Operacional são possíveis. As três mais usadas são onde cada CPU tem seu próprio Sistema Operacional, modelo “mestre-escravo” e multiprocessadores simétricos.

No modelo onde cada CPU tem seu próprio Sistema Operacional, a memória é dividida pelo numero de CPU´s do sistema. Para a otimização, geralmente as CPU´s compartilham os codigos do Sistema Operacional e fazem suas copias privadas somente dos dados.

A vantagem que esse esquema leva em relação ao Sistema Multicomputadores é que nesse modelo as CPU´s compartilham o mesmo disco rigido, dispositivos de S/E, além da memoria ser flexivel, mudando de acordo com o processo. Nesse modelo, quatro caracteristicas devem ser frizadas: Cada chamada de sistema é feita e tratada em sua própria CPU, como cada Sistema Operacional tem suas próprias tabelas, cada CPU processa suas tarefas indepedente de outras, não existindo o compartilhamento de processos, podendo surgir uma desigualdade de trabalho, tornando um CPU sobrecarregado enquanto outro fica ocioso. Em terceiro lugar, não existe compartilhamento de paginas, onde cada CPU tem suas paginas individualmente. Ainda, existe a possibilidade de existir em uma cache um bloco de disco das ultimas tarefas feitas, e cada Sistema Operacional tem sua cache própria, podendo haver divergencias entre os blocos existentes. Para evitar esse problema, se faz necessario a eliminação de cache de buffer, o que diminui seu desempenho.

Esse modelo foi muito utilizado no começo das estruturas de multiprocessadores, mas já é dificilmente utilizado.

Multiprocessadores Mestre-Escravo

Nesse modelo, o Sistema Operacional é presente somente na CPU I, e as restantes se encarregam de executar processos do usuario, enquanto a CPU I só executa processos de usuario se houver tempo disponivel.

Uma grade vantagem nesse modelo é que existe uma única lista de processos a serem feitos, sendo assim, se uma única CPU fica ociosa, ela pede ao sistema um processo para executar, além de existir um único cache de buffer, evitando incosistencias.

A sua desvantagem aparece em grandes redes. Se uma CPU Mestre gasta 20% do seu tempo com as chamadas de sistema, 5 CPU´s Escravas já ocupam todo o tempo da CPU Mestre.

Multiprocessadores Simetricos.

Nesse modelo, existe uma copia do Sistema Operacional na memória, e qualquer CPU pode executa-la. Nesse modelo, é eliminado a duplicação de tabelas do Sistema Operacional, como no modelo de vários Sistemas Operacionais.

Mas, em contrapartida, se duas ou mais CPU´s executam o mesmo trecho do Sistema Operacional, pode ocorrer ocorrencias. Para evitar esse problema, usa-se o Mutex, que funciona como um semaforo, fazendo cada CPU executar o Sistema Operacional por vez.

Um problema que pode ocorrer se assemelha ao modelo Mestre-Escravo. Caso dois ou mais CPU´s queiram executar o Sistema Operacional, havera fila. Pórem, como varias partes do Sistema Operacional são indepedentes uma das outras, podem ser executadas simultaneamente. O mutex só se encarrega de liberar ou não o trecho do sistemaop.

Esse é o modelo mais usado nos sistemas multiprocessadores atuais, e saber separar os trechos do sistemaop para uma boa programação do mutex se torna o maior desafio na sua montagem.

Nos processos de evolução do codigo, pode acontecer que uma região precisa de uma tabela nova, que só seria criada em um processo depois de um tempo outro CPU. Por isso, não deve ter rodizio de programadores nessa estrutura de multiprocessadores.

Sincronização em Multiprocessadores

Em sistemas multiprocessadores, a sincronização dos CPU´s é parte de fundamental importância para um desempenho superior ser alcançado.

A sincronização é importante para proteger os processos, para serem finalizados corretamente e não travarem. Se um processo em um processador realiza uma chamada de sistema que requer o acesso a alguma tabelas criticas do nucleo, o codigo do nucleo pode desabilitar a interrupção antes de manipular a tabela. Cada interrupção afeta somente a CPU que esta executando. O mutex tem que ser seguido por todos os CPU´s do sistema.

Para a finalização de um processo ocorrer sem erro e sem a intrometeção de outro processo, é preciso sincronizar as ações, para que, quando um processador realiza uma chamada de sistema e precisar acessar alguma tabela critica do nucleo, o nucleo não a bloqueie. Nesse caso é usado um protocolo, que nada mais é do que a inspeção da palavra na memória. Uma instrução TSL é usada para impedir o acesso de uma parte da memória.

Teste continuo ou chaveamento

Com os novos sistemas de multiprocessadores, surgiu a possibilidade de processadores ficarem esperando a tarefa (thread) a realizar, através da lista de processos, não tendo autonomia para escolher alguma tarefa a executar.

Porém, há casos em que essa autonomia acontece. Se um processador fica ocioso, esperando algum recurso para prosseguir a sua execução, ele em vez de ficar esperando, inicia uma nova execução. Problema que não acontece em sistemas monoprocessadores.

Tanto ficar repetindo (teste continuo) o uso de uma variavel para verificar se o resultado é valido, quando após o primeiro teste é verificado seu travamento, ou realizar o chaveamento (processamento de algo alternativo) desperdiçam ciclos da CPU, visto que é preciso salvar o estado atual, a variavel de tratamento atual, além de ter que abrir um novo thread.

Pode acontecer que a variavel esteja travanto o processamento possa ser liberada mais rapidamente do que o tempo de salvamento e carregamento de uma nova tarefa, o que valeria mais a pena ficar esperando a liberação do que iniciar uma nova execução.

Além do chaveamento e do teste continuo, uma noção alternativa seria registrar cada impedimento, para decidir se seria melhor chaveamento ou o teste continuo para cada parada da CPU. Após alguns estudos (Karlin, 1989 e Outeshout, 1982 ), a maioria dos testes são feitos com um tempo limite para cada tipo de travamento, se esse tempo é atingido, ocorre um chaveamento para outra tarefa, esse tempo pode ser fixo ou variar de acordo com os resultados observados nos testes. Os resultados mais eficientes são aqueles que tomam como base o tempo limite observando os tempos anteriores, e estipulando que esse tempo se repetira.

Escalonamento de Multiprocessadores

È importante para o entendimento de escalonamento observar que há threads do nucleo e de usuario. Se o thread é de usuário e o núcleo não tiver informações sobre ele, não conseguiria escalonar. Mas se o thread é de núcleo, com as informações que ele contém do thread, pode trabalha-lo completamente, indepedente do processo ao qual pertence.

Se o processador é mono, a questão é simples, apenas escolher o próximo processo a executar. Porém, quando se trabalha com multiprocessadores, devem ser escolhidas os próximos processos e em quais CPU´s serão executados. O escalonamento deve sincronizar essas informações.

Há processos que se relacionam com outros, e processos que trabalham sem se relacionar. Os processos que não contém relacionamentos podem trabalhar sem a interferencia de outros, pois seu resultado, indepedente de qual seja, não afetara os demais. Mas os processos que interferem em outros devem ser tratados com cuidado. Por exemplo, um processo que afeta um dado em algum arquivo que sera usado por outro programa na sua compilação, contendo macros, definições de tipo e variaveis. Quando isso ocorre, é invocado um programa make, que analisa a situação e recompila os arquivos que sofreram alterações.

Tempo Compartilhado

Os sistemas mais simples de escalonamento consideram uma única lista de threads para a realização em todas as CPU´s, com cada thread tendo uma prioridade diferente.

Por exemplo, se a CPU 1 fica ociosa, escolhe o próximo processo da fila (no caso a tarefa A). Em seguida, o processador 4 fica ocioso, e a próxima tarefa da fila segundo a ordem de prioridade é a B, que é imediatamente levada a CPU 4, e em seguida a CPU 2 fica livre, é amarrada com a próxima da lista, neste caso a tarefa C. Esse processo é simples, e só pode ser usado caso as tarefas não são relacionaveis.

Essa estrutura é parecida com os do sistema monoprocessadores, pois dificilmente algum processador ficara ocioso por muito tempo, e fornece o balanceamento de energia e processos por CPU. Um ponto fraco neste sistema é a sincronia quando se tem um numero elevado de CPU´s.

Compartilhamento de espaço

Pode acontecer de num processo, as threads se comuniquem frequentemente, neste caso, é util faze-las executar ao mesmo tempo. O escalonamento de multiplos threads ao mesmo tempo sobre multiplos CPU´s é chamado compartilhamento de espaço.

Para esse processo ocorrer, tem que haver um numero minimo de CPU´s livres, para que cada thread fique em uma CPU. Caso isso não seja possível, o sistema espera até isso acontecer. O processador seguira sua thread até que todo o bloco termine, e após o bloco ter terminado, o bloco inteiro é colocado em disposição. Se uma thread é bloqueada esperando alguma ação de E/S, ele continua sendo alocado na CPU até que o desbloqueio possa ser feito.

Acontece ainda dos conjuntos de CPU´s sejam divididos de acordo com a tarefa realizada. Por exemplo, um sistema com 20 CPU´s pode realizar 3 blocos de tarefa com o uso de 6 CPU´s cada, e ainda ter 2 CPU´s não usados.

Escalonamento em bando

O compartilhamento de espaço oferece a opção de não ser mais usado o chaveamento, pois as CPU´s não esperaria uma variavel que necessite para a conclusão da tarefa em execução. Porém, pode acontecer de um bloco de tarefa em execução depender de apenas uma CPU, tornando uma grande do seu poder de processamento parado, até que essa termine e libere a variavel.

Vamos supor que um conjunto de CPU´s esteja trabalhando com dois blocos, A e B, e que cada bloco contenha duas tarefas, A1 e A2, B1 e B2.

CPU 0 A0 B0 A0 B0

CPU 1 B1 A1 B2 A1

LINHA DE TEMPO 1 2 3 4

No espaço de tempo 1, A0 envia uma mensagem para A1 da CPU 1 e espera até obter sua resposta, o que só acontece no tempo 3, sendo que a CPU 1 trabalha durante o tempo 2. Nessa caso, a CPU 1 espera por 2 momentos até que siga sua operação.

Para a resolução deste problema, é usado o escalonamento em bando, que contém três bandos:

1-Os grupos de threads relacionados são escalonados como uma unidade chamada bando.

2-Todos os membros do bando executam suas tarefas simultaneamente, em diferentes CPU´s, com tempo compartilhado.

3-Todos os membros de um bando iniciam e finalizam junto suas fatias de tempo.

Nesse modo, em cada quantum é colocada em uma nova thread nas CPU´s. Se um thread é bloqueado, sua CPU permanece ociosa apenas até o final do quantum.

CPU 0 1 2

TEMPO A1 A2 A3

0

1 B1 B2 C1

2 A1 A2 A3

No exemplo a cima, todas as tarefas do bloco A são executadas ao mesmo tempo. Isso ocorre para que as ligações referentes ao Bloco A sejam feitas com a tarefa em execução, para uqe sejam requisitadas e respondidas quase que imediatamente.