Acessos não uniforme à memória em sistemas distribuídos
Orientador: Prof. Dr. Norian Marranghello
Alunos: Hugo Brandão Uchoa Renato Moreno Peixoto de Mello
1. Introdução Existem 3 paradigmas importantes que tratam da troca de informações entre os processos em um sistema distribuído: passagem de mensagens, chamada a procedimentos remotos e compartilhamento de memória. Neste resumo, iremos analisar com maior profundidade o compartilhamento de memórias distribuídas. Nos sistemas multiprocessadores (memória compartilhada), duas ou mais CPU’s compartilham uma memória principal comum. Qualquer processo ou processador pode ler ou escrever qualquer palavra na memória compartilhada simplesmente movendo os dados para o local determinado. Ao contrário, nos sistemas multicomputadores (memória distribuída), cada CPU tem sua própria memória privada, sendo que a comunicação entre as máquinas é realizada por passagem de mensagens via rede. Projetar máquinas, nas quais vários processadores utilizam a mesma memória física não é uma tarefa trivial. Esta característica limita a escalabilidade destes tipos de arquiteturas; já os multicomputadores são mais simples de construir. Com relação à programação ocorre o inverso. Existem várias técnicas para programar multiprocessadores. Para realizar comunicação, um processo apenas escreve dados na memória para ser lido por todos os outros. Para sincronização, seções críticas podem ser usadas, com a utilização de semáforos ou monitores para garantir exclusão mútua. Já nos multicomputadores a situação se complica um pouco. Comunicação geralmente tem que usar passagem de mensagens. Passagem de mensagens apresenta várias complicações, entre elas controle de fluxo, mensagens perdidas, buferização (buffering) e bloqueamento (blocking). Embora várias soluções tenham sido propostas, programação com passagem de mensagens permanece complicada. Em resumo, multicomputadores são simples de construir mas difíceis de programar, sendo os multiprocessadores o oposto, difíceis de construir mas simples de programar. Dessa forma está havendo um aumento muito grande no interesse por memórias compartilhadas distribuídas (MCD). Estes sistemas permite integrar a escalabilidade das memórias distribuídas com a maior facilidade de programação das memórias compartilhadas. O objetivo primordial do compartilhamento de memórias distribuídas é viabilizar o compartilhamento direto de informações entre processos comunicantes por meio da simulação de um espaço de endereçamento lógico compartilhado, sobre um conjunto de memórias locais distribuídas fisicamente. Para sua implementação utiliza-se o mecanismo de passagem de mensagens, o qual fica transparente por ser encapsulado em uma camada com programas para o gerenciamento e o mapeamento entre a MCD e o sistema de passagem de mensagens. Dependendo da localização dos dados, a forma de acesso a eles deve ser diferente. Em um sistema distribuído onde esteja sendo usado o compartilhamento de memória, os dados podem ser armazenados localmente na memória do processador onde o processo estiver sendo executado ou remotamente na memória de outro processador. Dessa forma, o modo de acesso a esses dados ocorre de maneira distinta em cada caso. Em sistemas multiprocessadores de grande porte convém manter a parte do espaço de endereçamento mais freqüentemente acessada por um conjunto de processos mais
próxima do(s) processador(es) em que estiverem sendo executados, deixando o restante do espaço de endereçamento mais afastado. Os multiprocessadores com arquiteturas que permitem este tipo de hierarquia de acessos à memória em vários níveis são conhecidos como sistemas de acesso irregular à memória, ou em inglês, NUMA (Non-Uniform Memory Access). Neste resumo, veremos dois diferentes tipos de sistemas implementados em arquitetura NUMA : MCD (Memória Compartilhada Distribuída) e MCM (Memória Cache de Multiprocessadores). Analisaremos também a transparência no acesso aos dados bem como os modelos de consistência e coerência nessa arquitetura.
2. Arquiteturas NUMA Uma máquina NUMA genérica, apresentada na figura I, pode ser representada por um conjunto de processadores, cada um dos quais com um módulo de memória local. Além do par processador-memória, há uma malha de comunicação interligando todos estes pares e uma interface entra cada par e a malha de comunicação. Essa interface é um controlador, cujo objetivo é manter a coerência do sub-sistema de memória.
Figura I: Diagrama de blocos de uma máquina Numa genérica
Vimos que as arquiteturas de acesso não uniforme à memória (NUMA), permitem dividir a memória em vários níveis de hierarquia. Dois tipos de sistemas que podem ser implementados de acordo com essa arquitetura são o MCM e o MCD. Veremos agora alguns aspectos desses sistemas quando aplicados à arquitetura NUMA.
2.1 Implementação de uma MCM sobre uma máquina NUMA Um tipo de implementação que pode ser feito sobre uma arquitetura NUMA é da MCM, que são sistemas de memória cache de multiprocessadores. Neste caso, os módulos de memória local são “caches” utilizadas principalmente para reduzir o tempo médio de espera nos acessos à memória e minimizar o tráfego de acessos à memória global. A memória global pode ser uma grande memória RAM compartilhada por todos os processadores, mas também pode ser um conjunto de módulos de memória distribuídos pelo sistema. O barramento, por sua vez, pode ser um barramento comum, mas isto tende a gerar grande disputa pelo seu uso. Alternativamente, é possível utilizar vários barramentos, ou uma rede de conexão. Isto é recomendável, principalmente se o sistema for composto por muitos processadores e tiver vários módulos de memória compondo a memória global. Podemos analisar este sistema através da figura II: Memória Global Barramento Comum
CCM P1
CCM M
1
P2
...
CCM M
2
P3
M
Controladores de Coerência
CCM Pn
3
M
n processadores
caches locais
Fig. II: Implementação de uma MCM
2.2 Implementação de uma MCD sobre uma máquina NUMA Além do MCM, temos também o sistema MCD que é um sistema de memórias compartilhadas distribuídas e também pode ser implementado sobre uma máquina NUMA genérica. A implementação deste sistema está representado na figura III. Nesse caso, não há uma memória global física. Os módulos de memória locais são utilizados para formar um espaço de endereçamento global, correspondendo a uma grande memória virtual. Este espaço de endereçamento é compartilhado por todos os processadores do sistema. Os processadores acessam cada porção não local deste espaço de endereçamento através de uma rede de conexão, geralmente formada como uma LAN (local area network) ou WAN (wide area network).
Memória Rede de conexão
CCM P1
CCM M
1
P2
...
CCM M 2
P3
M
Controladores de coerência
CCM Pn
3
M
n processadores
Memórias locais
Fig.III: Implementação de uma MCD
3. Desempenho e Transparência Uma importante medida de desempenho é a latência de memória, que diz respeito ao intervalo de tempo compreendido entre o momento no qual um processador iniciou um acesso a um dado compartilhado até que este acesso seja satisfeito. Dessa forma vemos que em um sistema MCD um bom intervalo de latência dependerá do número de acessos feitos à memórias locais de outros processadores. Se um processo rodando em um processador for buscar muitos dados em memórias locais de outros processadores, então a latência será alta; já se a maioria dos dados que ele necessitar estiver na memória local, então a latência será baixa. Dessa forma, vemos que a uma medida para minimizar a latência em MCD’s seria fazer várias cópias das mesmas informações em módulos de memórias locais. Em um sistema MCM , a latência já é um pouco mais complexa. Como há uma memória global compartilhada por todos os processadores, pode haver uma grande disputa pelo barramento que leva até essa memória. Dessa forma, se aumentar o número de processadores a acessarem a memória global ao mesmo tempo, a latência será alta. A solução de hardware para este problema é o aumento da banda de passagem da memória utilizando-se vários barramentos ou uma rede de ligações escalonável. Além do desempenho, temos também um outro importante objetivo que é visado principalmente pelos sistemas MCD’s que é a transparência. É a transparência que permite diferenciar um sistema distribuído de uma rede de computadores convencional. Através dessa característica, o usuário de um sistema distribuído pode usar recursos de outras máquinas sem que ele perceba, ou seja, é como se o usuário estivesse usando somente os recursos da máquina a qual ele está ‘logado’. As MCDs conseguem prover a transparência na comunicação de dados usando o mecanismo de passagem de mensagens. Com isto os usuários não precisam se preocupar
com o movimento e eventuais conversões de dados, com o tratamento de parâmetros necessários à troca das mensagens ou com a manipulação dos detalhes dos protocolos de comunicação.
4. Replicação e migração de dados Duas estratégias utilizadas para distribuição dos dados compartilhados são replicação e migração. Replicação permite que várias cópias do mesmo item de dado residam em diferentes memórias locais (ou caches). É utilizado principalmente para habilitar acessos simultâneos de diferentes nodos ao mesmo dado, predominantemente quando compartilhamento de leitura prevalece. Migração implica que somente uma cópia de um item de dado existe no sistema, portanto os itens de dados são movidos sob demanda para uso exclusivo. Utiliza-se a replicação e migração de dados no sistema de memória com o intuito de minimizar o tempo médio de acesso aos dados. Para alcançar esse tempo médio satisfatório deve-se colocar a maior quantidade de dados possível na memória local em MCMs ou em MCDs. A taxa de sucesso nas buscas (TSB) locais é diretamente proporcional a quantidade de dados existentes nas memórias locais, ou seja, quanto maior a quantidade de dados disponíveis em uma memória local, maior será a chance do dado procurado estar nesta memória e , consequentemente, menor será a necessidade de buscas em módulos remotos. A TSB sofre influência do tamanho de dois tipos de unidades, além do tamanho da memória local:o da unidade básica para o compartilhamento de dados e o da unidade buscada quando há um insucesso na busca local. Tais unidades utilizam blocos e, embora possam ser diferentes (palavras, linhas, páginas...), o uso de blocos iguais facilita a implementação do sistema. O tamanho do bloco tem influência significativa na TSB. É necessário adotar um tamanho para o bloco que proporcione o melhor desempenho na busca de dados. Quanto maior for o bloco, maior será a cobertura na localização dos dados e, consequentemente, maior será a TSB. Porém, blocos muito grandes armazenam muita informação irrelevante para o processo atual, podendo então remover informações úteis já presentes na memória local, reduzindo a TSB. Além disso, as referências a blocos são armazenadas em uma tabela, para a localização e eventual gerenciamento de cópias. Caso blocos grandes sejam utilizados, menos blocos serão armazenados e o espaço necessário para armazenar esta estrutura será menor, causando menos sobrecarga no sub-sistema de memória. Porém, transferir blocos grandes despende mais recursos, causando maior sobrecarga para o sub-sistema de comunicação. Tendo em vista esta análise, podemos concluir que o uso de blocos pequenos geram pouca sobrecarga no sub-sistema de comunicação e muita sobrecarga no sub-sistema de memória. Quando os dados necessitados não se encontram na memória local (insucesso na busca), devem ser acessados remotamente, utilizando-se migração ou cópia dos dados. A migração consiste na eliminação do bloco de um módulo memória seguido da sua implementação no módulo requisitante. A cópia corresponde a criação de réplicas do bloco em vários módulos de memória. Utilizando o processo de migração o problema de coerência se restringe a coerência entre a única cópia do bloco no sistema e seu original na memória principal. Existem dois
tipos de migração: a migração por iniciativa do processador que detém a cópia e a migração sob demanda. A migração por iniciativa do processador que detém a cópia dá-se quando tal processador detecta que determinado bloco não lhe tem mais serventia no momento, então ele o oferece a outro processador esperando que este utilize tal bloco num futuro próximo. Tal esquema não é muito usado por requerer uma carga de gerenciamento e uma sobrecarga no sub-sistema de comunicação, muitas vezes desnecessárias. Portanto o esquema utilizado é a migração sob demanda, na qual o processador que detém a cópia a mantém até que ela seja solicitada por outro processador ou eliminada para dar lugar a outro bloco. Porém o problema da migração é o chamado efeito pingue-pongue, que ocorre quando um processador A solicita um bloco que está armazenado em outro processador B. O bloco é transferido de B para A, porém em seguida o processador que cedeu o bloco, necessita dele novamente, requisitando a transferência de A para B. Em seguida, o processador A requer o bloco novamente. Então, ocorre uma sequência de transferências do mesmo bloco entre dois processadores, provocando uma sobrecarga no subsistema de comunicação. Isto ainda pode ser agravado quando ocorre uma falso compartilhamento, isto é, quando quando o processador A necessita de uma informação no início do bloco e o processador B necessita de uma informação no final do bloco. Tal problema ocorre principalmente com blocos muito grandes e poderia ser evitando reduzindo o tamanho do bloco. O efeito pingue-pongue pode ser evitado fazendo diversas cópias de certos blocos compartilhados, melhorando a concorrência do sistema, reduzindo também a sobrecarga do subsistema de comunicação. Um processador pode ser obrigado a esperar que o outro termine de usar o bloco, caso o tempo entre dois acesso consecutivos seja menor que o tempo necessário para transferência e o uso do bloco pelo outro processador (problema de latência). O problema principal do uso de cópia de dados é o enorme custo computacional devido ao controle de coerência de dados necessário.
5. Consistência e Coerência Os termos consistência e coerência são geralmente utilizados como sinônimos, entretanto existe algumas distinções entre eles. Dessa forma podemos ter as seguintes definições: consistência: se todas as cópias de uma variável compartilhada contiverem a mesma informação quando todas as operações de escrita forem completadas. coerência: obtida quando uma operação de leitura retorna o valor dado pela última escrita na mesma variável compartilhada. Portanto, vemos que a coerência é uma consequência da consistência.
6. Modelos de Consistência Consistência de memória é a política que determina como e quando mudanças feitas por um processador são vistas pelos outros processadores do sistema. A escolha do modelo de consistência define o comportamento pretendido do mecanismo de MCD com respeito as operações de leitura e escrita. O modelo mais intuitivo de coerência de memória é a consistência rígida, na qual uma operação de leitura retorna o valor de escrita mais recente.
Este tipo de consistência é alcançado somente quando existe uma noção global de tempo que possa fornecer uma ordem determinística para todas as leituras e escritas. Entretanto, "escrita mais recente" é um conceito ambíguo em sistemas distribuídos, onde não existe um relógio global. Por este motivo, e também para aumentar o desempenho, foram desenvolvidos vários modelos para manter a consistência em sistemas distribuídos. Diferentes aplicações paralelas exigem diferentes modelos de consistência. Quanto mais restrito for o modelo de consistência de memória, mais ele influenciará no desempenho do sistema executando estas aplicações. Os modelos de consistência são divididos em duas categorias: os de acesso geral e os de acesso sincronizado. Os modelos de consistência de acesso geral podem não ser tão restritivos se a exigência de ordenamento das operações de escrita for relaxado, com relação aos processadores ou às posições de memória. Tais modelos se dividem em consistência causal, consistência do processador e memória lenta. Já os modelos de consistência de acesso sincronizado limitam a coerência apenas a acessos de sincronização e são representados pela consistência fraca, consistência de liberação e consistência de entrada. Um diagrama em blocos com esta classificação é apresentado na figura IV. Consistência Atômica Relaxamento de Ordem de Tempo-Real Consistência Seqüencial Relaxamento Relativo ao Processador Consistência Fraca
Consistência Causal Relaxamento Relativo ao Processador
Consistência de Liberação
Consistência de Processador Relaxamento Relativo a Posição
Consistência de Entrada
Memória Lenta
Nenhum Suporte de Coerência no Sistema
Fig. IV - Uma Taxonomia de Modelos de Consistência
Consistência Atômica: Este modelo requer que a MCD se comporte como a memória em um sistema centralizado sem cópia de dados. Todos os processadores devem executar os
eventos na mesma ordem, os quais devem parecer executados em sequência (atomicamente). É o modelo mais restritivo e geralmente só é usado como base para a avaliação de outros modelos de consistência. Consistência Sequêncial: Os protocolos de coerência de memória têm que assegurar que todos os nodos vêem a mesma seqüência de leituras e escritas. Sendo que operações de acesso podem sofrer atrasos diferentes e, portanto, ser observadas em ordem diversa por processadores diferentes, o ordenamento real dos eventos não é exigido, porém é necessário que o resultado das operações seja observado na ordem em que forem solicitados. Consistência Causal: Somente escritas com relação de causa precisam ser observadas na mesma ordem por todos os processadores. Consistência de Processador: O modelo de consistência de processador garante que escritas de um dado processador sejam realizadas na ordem em que foram requisitadas. Entretanto, a ordem na qual escritas de dois processadores distintos são observadas por um terceiro processador não precisa ser a mesma. Em outras palavras, consistência em escritas são observadas em cada processador, mas a ordem de leituras de cada processador não é restringida, contanto que elas não envolvam outros processadores. Entretanto, a seqüência de escritas realizadas por qualquer um dos nodos será vista na mesma ordem por todos os outros nodos. A chave do ganho de desempenho alcançado pelo modelo de consistência de processador comparado com a consistência seqüencial é que leituras são diferenciadas das escritas. Consistência de Memória Lenta: Apenas escritas à mesma posição na memória solicitadas pelo mesmo processador precisam ter sua ordem respeitada. Seus efeitos são visíveis localmente, imediatamente, e demoram para ser propagados pelo sistema. Consistência Fraca: O modelo de consistência fraca (weak consistency) distingue acessos normais (leituras e escritas) de operações especiais de sincronização. Nos pontos de sincronização é que o sistema torna-se globalmente consistente. Antes que uma operação de sincronização possa executar, todos os acessos normais anteriores devem ser completados. Além disso, acessos realizados após a operação de sincronização devem esperar para que todas as operações de sincronização sejam finalizadas. Consistência de Liberação: Consistência de liberação (release consistency) é uma extensão do modelo de consistência fraca, que também distingue acessos normais de acessos de sincronização. Acessos de sincronização são divididos em operações de obtenção (acquire) e liberação (release). Este modelo assume que acessos conflitantes de leitura e atualização a memória são sempre protegidos utilizando mecanismos que garantam exclusão mútua, como os semáforos. Pode-se melhorar a concorrência se a operação para obtenção do semáforo não atrasar (bloquear) acessos anteriores e se a operação para liberação não retardar acessos futuros.
Consistência de Entrada: Este modelo bloqueia objetos em vez de seções críticas para a exclusão mútua na sincronização. Tal modelo de consistência recebe este nome devido à consistência da variável compartilhada na entrada da região crítica.
Bibliografia: MARRANGHELLO, N. Apostila de Sistemas Operacionais. Instituto de Biociências Letras e Ciências Exatas- UNESP, 2001 TANENBAUM, A. S. Distributed Operating Systems. Prentice Hall, 1995 CHOW, R. & JOHNSON ,T. Distributed Operating Systens & Algorithms. Addison Wesley, 2000 ARAUJO, E. B. Sistemas de Memória Compartilhada Distribuída Implementados em Hardware. Universidade Federal do Rio Grande do Sul, 1999
