Sobre

Resumo

Memória compartilhada distribuída é um sistema que abstrai vários aspectos da memória distribuída convencional evitando a troca de mensagem e assim facilitando a programação.

Existem diversos algoritmos de memória distribuída compartilhada que podem ser implementados por meio de hardware ou software cada um com suas vantagens e desvantagens.

Em tais algoritmos existe uma variedade de problemas que devem ser solucionados, problemas importantes como os de coerência de memória.

Os recursos limitados dos computadores podem ser expandidos utilizando-se computação distribuída. Memória compartilhada distribuída é uma forma de facilitar a programação em tais ambientes computacionais.

Introdução

Os programadores estão acostumados com o conceito de memória compartilhada. Em última análise até uma variável global pode ser visto como memória compartilhada entre procedimentos. Esta abordagem é fácil, familiar e intuitiva para resolver um problema muito simples: compartilhamento de informações.

Problema de compartilhamento de informação é algo que ronda os sistemas distribuídos. Soluções foram dadas anteriormente como, por exemplo, o uso de sockets só que tais mecanismos desviavam o foco do problema a ser programado. O programador era obrigado a tratar erros de sockets criando muitas vezes um protoloco de comunicação.

Memória compartilhada é um modelo atrativo de programação para desenvolvimento de aplicações paralelas e distribuídas. Com as pesquisas desenvolvidas nesta área conseguiu-se chegar a um bom nível de abstração dos aspectos físicos envolvidos. Esta abstração é normalmente chamada de memória compartilhada distribuída (DSM) e possui implementação por software e por hardware.¹

Tais pesquisas para chegar a este modelo produziram um bom material que pode e deve ser analisado para entendimento o mais completo possível desta nova forma de programar suas limitações e também para ser capaz de tomar decisões de projeto adequadas.

Motivação

Em qualquer espaço de tempo que analisarmos vamos perceber que existem limitações de hardware tais como velocidade de processador, por exemplo, no momento em que este trabalho estava sendo escrito o microcomputador mais rápido disponível é o Pentium 4 da Intel².

A exploração do processamento paralelo e distribuído é uma das formas de ampliar os limites de desempenho dos sistemas computacionais. Infelizmente é notório que a programação paralela e distribuída é muito mais complexa do que a programação em sistemas de um só processador ou mesmo em sistemas multiprocessados. Além dos problemas encontrados neste tipo de programação terem que ser solucionados em uma nova abordagem outros, que não existiam anteriormente vem à tona e devem ser resolvidos.³

É importante estudar uma forma para solucionar tais problemas. Compartilhamento de memória surge com este objetivo oferecendo vantagens quando comparados com outras abordagens como a que usa troca de mensagens.

Objetivos

O objetivo deste trabalho é apresentar o conceito memória compartilhada distribuída diferenciando-o de memória distribuída mostrando também suas diversas implementações com seus respectivos problemas, vantagens e desvantagens.

Não espera-se aqui esgotar o assunto, e sim que este trabalho sirva de base para estudantes de nível iniciante ou intermediário.

Memória Compartilhada Distribuída

O modelo de memória compartilhada distribuída foi proposto por Li e Hudak em publicação feita no ano de 1989. Baseava-se em um espaço de endereçamento virtual para estações de trabalho conectadas por uma LAN.⁴

Por simplificação muitas pessoas se referem à memória compartilhada distribuída como simplesmente memória compartilhada. Deve-se atentar no entanto para a diferença: memória compartilhada é o ato de se compartilhar uma determinado espaço de armazenamento de dados, não necessariamente em computação distribuída. No caso mais simples, um programa que possui variável global está compartilhando entre seus diversos procedimentos o espaço de armazenamento acessado via esta variável global.

Esta simplificação tem chegado até às definições mais formais como em um referenciado dicionário de informática do departamento de computação Imperial da Inglaterra.⁵ No verbete referente a memória compartilhada encontramos duas definições, referente ao verbete memória compartilhada:

Se procurarmos sobre no verbete memória distribuída encontramos a seguinte definição:

Memória Distribuída (arquitetura): Um tipo de memória utilizado no processamento paralelo onde cada processador tem acesso mais rápido a sua memória local porém o acesso a memória de outros processadores deve ser feita por envio de mensagens pela rede. O oposto de memória compartilhada.⁷

Em última análise pode-se dizer realmente que memória compartilhada distribuída é o oposto de memória distribuída, no entanto a última foi tomada de base para primeira. Ela foi melhorada tentando-se eliminar boa parte de sua complexidade e problemas tais como controle de fluxo e bloqueamento.⁸

Assim podemos chegar a um conceito mais claro, que reflete aquilo que é encontrado na maior parte da bibliografia, e no qual este trabalho se baseia:

Memória compartilhada distribuída, muitas vezes no ambiente de computação distribuída chamada simplesmente de memória compartilhada, é uma evolução da arquitetura de memória distribuída que se baseia nos conceitos de endereçamento virtual para disponibilizar uma página virtual única para todo o ambiente do sistema distribuído fornecendo assim uma abstração dos detalhes físicos, evitando problemas decorrentes do uso de um sistema baseado em troca de mensagens e provendo um meio eficiente e familiar para o programador compartilhar dados.

Assim sendo memória compartilhada distribuída segue a tendência de simplificação, de criar níveis de abstração entre a máquina e o programador para assim aumentar a produtividade e evitar o desvio do foco do problema.

Diferencial

Basicamente o que diferencia o sistema de memória compartilhada distribuída (DSM) do sistema de memória distribuída (DM) é que ele não utiliza troca de mensagem como base para sua implementação.

A base de um sistema em DSM é a memória virtual. A idéia de memória virtual vem de 1959 e tem como princípio ocultar a hierarquia da memória e simplificar a programação. Pode-se inclusive dizer que memória virtual é um dos grandes triunfos da engenharia da computação.

Tendo a memória virtual como base fica claro o que o foco da DSM é incorporar nos sistemas distribuídos uma camada de abstração, uma camada utilitária que permite tornar a operação de compartilhamento de dados entre computadores tão trivial quanto o acesso à memória primária e secundária já familiares aos programadores.

Quando um processo acessa um espaço de endereço compartilhado um gerenciador de mapeamento mapeia a memória compartilhada para a memória física. Tal mecanismo pode ser implementado tanto pelo sistema operacional quanto em uma rotina a parte, uma runtime library.

No entanto a forma de troca de mensagens utilizada em um sistema em DM não tem tais vantagens de abstração e de trivialidade. Sistemas como os de remote procedure cals (RPC) podem ser classificados como sistemas exemplos de DM.

DM utiliza primitivas como send e receive enquanto sistemas de DSM utilizam read e write⁹. As primitivas de DSM são muito mais intuitivas e por tanto mais fáceis de serem aprendidas.

Algumas tentativas foram feitas para melhorar tais aspectos da DSM como o que foi feito na biblioteca do UNIX para o C que trata portas de comunicação socket como dispositivos do sistema nos quais é possível executar primitivas read e write. No entanto isto não resolve por completo o assunto, ainda assim necessitamos de um protocolo de comunicação e controle de erros o que desvia o foco da programação.

O que diferencia um DSM de um DM é, como tem-se feito questão de frisar e repetir, o DSM por possuir uma abstração da memória permite um melhor aproveitamento dos recursos disponíveis na construção de um sistema. Este é o seu diferencial básico e tem sido o bastante para atrair simpatizantes desta técnica inclusive algumas empresas já tem desenvolvidos produtos baseada neste esquema, a exemplo do JavaSpaces da Sun Microsystems.

Aspectos de Implementação

Existem alguns aspectos de implementação que devem ser entendidos para que seja possível compreender completamente como funciona um sistema de DSM. Para isto vamos pegar uma variação de implementação na qual referências a páginas locais são resolvidas por hardware na velocidade da memória e referências a páginas presentes em outras máquinas causarão falha de página caso esta seja um endereço mapeado para a memória compartilhada distribuída, o sistema de DSM entrará em ação e devolverá a página correspondente caso contrário será enviado um aviso de página faltando para o sistema. Desta forma pode-se identificar um caminho da requisição: página local, memória virtuais e depois memória compartilhadas distribuídas.

É evidente que em algum ponto deste processo ocorrerá troca de mensagens entre máquinas, mas esta camada é abstraída no modelo de DSM. Esta troca pode ser implementada ou no hardware ou no software. Observa-se por este motivo que um sistema de DSM deve ter uma relação intima com a arquitetura do computador, sistemas operacionais, sistemas de tempo de execução e linguagens de programação.

Aspectos de Estrutura

Um sistema de DSM tem basicamente a mesma estrutura de um sistema de DM, ou seja, envolvendo um conjunto de computadores que podem ser agrupados em clusters e que são conectados por uma rede de interconexão escalável.

Atente-se para o fato de que a rede de interconexão tem importância crítica para o sistema, assim sendo deve-se conseguir que elas ofereçam uma pequena latência¹⁰ e uma alta banda a um custo razoável.

Algoritmos

Para se implementar a idéia de memória compartilhada distribuída é necessária não só a compreensão de seus problemas mas também saber como resolve-los por meio de algoritmos computacionais. Dois fatores importantes que devem ser considerados são a eficácia e eficiência com as quais tais algoritmos atuarão. Obviamente eles além de resolver com perfeição os problemas a que se destinam devem executar suas tarefas da maneira mais otimizada possível.

Pode-se dizer que um algoritmo é melhor ou pior do que um outro baseado na sua performance e eficácia na solução de um grupo de problemas. Como na maioria dos algoritmos de informática alguns tipos são bons para determinados problema e péssimos para outros. É de extrema importância saber qual deles aplicar em uma determinada aplicação que vá utilizar DSM.

Quando se fala em algoritmos de implementação de uma dada tecnologia infelizmente sempre se pensa em entidades como sistema operacional, biblioteca de funções sendo o hardware esquecido completamente. Cabe então lembrar que é perfeitamente possível implementar um algoritmo de DSM em hardware.

Em se tratando de memória compartilhada distribuída podemos destacar os seguintes problemas que necessitam de solução (1) consistência dos dados, (2) velocidade de resposta e (3) coerência dos dados. Algumas soluções já foram sugeridas e se baseiam principalmente na replicação e/ou migração dos dados.

Algoritmo do Servidor Central¹¹

Este algoritmo sugere um servidor central que mantém e administra todos os dados. A comunicação entre cliente e servidor é baseada nas primitivas padrão read e write.

Várias condições de erros podem ser identificadas neste algoritmo e são tratadas como se segue:

(1) Tempo máximo de resposta ultrapassado: tal problema é resolvido por meio do envio de uma nova requisição. É evidente que várias sucessivas desta espécie indicam ou problemas com o servidor ou problemas com o meio de transmissão.

(2) Pedido de escrita duplicado: supondo que um cliente envie uma requisição de escrita duplicada por não ter recebido confirmação do servidor seria interessante que o servidor não a processasse pois um tempo de processamento seria perdido desnecessariamente. Para detectar-se este problema utiliza-se de um identificador único em uma requisição de escrita assim o servidor deve simplesmente enviar a confirmação ao invés de re-processar todo o pedido.

(3) Detecção de falha no sistema: o sistema de DSM pode ser identificado como não disponível quando várias requisições de leitura e/ou escrita não tiverem resposta.¹²

(4) Sobre carga do servidor: um servidor sobre carregado pode se tornar facilmente o gargalo do sistema criando assim algo indesejável: uma alta latência nas operações. Para resolver esta deficiência existe a possibilidade de distribuir os dados em mais de um servidor o que obriga os clientes a localizarem o servidor apropriado para encontrar um determinado dado. Para tal fim funções simples de hashing podem ser utilizadas.¹³

A solução proposta por este algoritmo se baseia em proibir a replicação dos dados (centralização da informação) sem requerer a migração (o cliente não necessita levar os dados compartilhados para sua máquina para só então trabalhar com eles).

Percebe-se que este tipo de implementação é fácil de ser desenvolvida porém apresenta um problema crucial que não foi completamente resolvido: o(s) servidor(es) são fatores críticos na performance dos sistema. Principalmente por este fator é aconselhável que este método seja utilizado para uma quantidade e um fluxo de dados proporcional a capacidade do servidor.

Algoritmo da Migração (SRSW¹⁴)

No algoritmo da Migração, os dados compartilhados são enviados para o local onde eles foram requeridos permitindo assim que operações subseqüentes sobre estes mesmos dados sejam executadas localmente diminuindo assim a tempo de latência.

Este algoritmo impõe a seguinte restrição: uma, e somente uma, thread pode executar operações, tanto de leitura quanto de escrita, sobre um determinado dado. Este tipo de regra é também chamado de “single reader/single writer” justificando assim a sigla que geralmente está associada a este método SRSW. O bloqueio acontece no nível de página ou bloco de memória e não em relação a um endereço específico. Tal política tem objetivo claro de reduzir o tamanho da tabela de lock inevitável neste sistema.

Este tipo de solução utilizando páginas possui a vantagem de que é possível integrar a idéia de página compartilhada distribuída com a idéia de memória virtual utilizada pelo sistema operacional. Desta forma um compilador ou biblioteca que suporte DSM pode prover formas mais transparentes de programação.

Existe no entanto a necessidade de um servidor, muito diferente daquele encontrado no Algoritmo do Servidor Central, que é responsável apenas por guardar a localização de uma determinada página.

Algoritmo da Replicação para Leitura (MRSW¹⁵)

A maior intenção deste algoritmo é reduzir o custo das operações de leitura partindo do pressuposto que esta é mais comum do que a operação de escrita.¹⁶ Para conceder tal privilegio nas operações de leitura utiliza-se a replicação.

O primeiro problema encontrado é obvio, se existe replicação dos dados a operação de escrita será penalizada pois exigirá um maior fluxo na rede com mensagens para invalidar as cópias que se tornaram obsoletas (ou no mínimo avisar os portadores das réplicas que tais dados não refletem os dados mais atuais).

O segundo problema, que também deve receber igual atenção, é que o algoritmo é obrigado a saber onde estão as réplicas de uma determinada página para então, no caso de uma escrita as invalidar ou informar que elas não são mais atuais. Este papel pode ser implementado por uma entidade que pode ser chamar de servidor de mapeamento.

Este algoritmo deve ser utilizado se a quantidade de leituras feitas supera em muito a quantidade de gravações.

Algoritmo da Replicação Total (MRMW¹⁷)

Como é obvio pelo nome o este algoritmo permite replicação para leitura e para gravação com a introdução de um novo elemento chamado de seqüenciador responsável por controlar as várias cópias mantendo a consistência dos dados.

O compreender o funcionamento deste novo elemento é crucial para que se possa entender o algoritmo como um todo. O seqüenciador é responsável por atribuir um número a cada alteração feita em um dado replicado e depois enviar todas as alterações para serem executadas seguindo o número serial a ela atribuído para serem executas nas demais réplicas.

Pode-se explicar de outra forma mais resumida: o algoritmo de replicação total adicional à idéia de servidor de mapeamento existe no algoritmo de replicação para leitura a responsabilidade de atualizar todas as cópias na ordem que as alterações foram executadas.

Algumas observação devem ser acrescentadas à interações feitas com o seqüenciador quando um cliente deseja efetuar uma alteração.

(1) Primeiro o cliente informa ao seqüenciador que deseja fazer uma alteração.

(2) Imediatamente o cliente atribui a esta alteração um número seqüencial.

(3) Os clientes executam as alterações necessárias e as enviam para o seqüenciador.

(4) O seqüenciador agrupa estas alterações com outras enviadas pelos demais clientes e as envia para os eles atualizando assim as diversas cópias do dado.

Problemas surgem desta interação entre o cliente e o sequenciador:

(1) O cliente solicitou um número para fazer uma alteração, no entanto sua cópia não esta atualizada: uma solução seria obrigar o cliente a atualizar seus dados primeiro ou simplesmente informá-lo deste fato.

(2) O cliente solicitou o número para fazer uma alteração e não a enviou em um determinado período de tempo: isto é sinal de que ou o cliente caiu ou problemas na rede. O sistema de correção de falhas deve entrar em ação pedindo o reenvio da mensagem ou ignorando a alteração.

Esta pode ser considerada a solução mais flexível, porém podem produzir um alto tráfego na rede com a freqüência atualização.

Decisões de Projeto

Na apresentação dos algoritmos foi dito que é muito importante utilizar os algoritmos adequados para cada projeto. Será apresentada aqui uma série de fatores que podem influenciar o desempenho de um projeto que utilize DSM, cabe ao programador balancear tais fatores com as características de cada algoritmo chegando assim a uma conclusão.

Configuração dos computadores: um computador que inclua um ou vários processadores tem também seus problemas de coerência de cachê e deve ser integrada com a implementação de DSM.¹⁸

Rede de Interconexão: a velocidade, a forma de conexão e a performance em todos os aspectos da rede são de importância fundamental uma vez que a rede é o meio de comunicação por onde a memória compartilhada será escoada. Alguns algoritmos no entanto necessitam mais da rede do que outros.

Estrutura dos dados compartilhados: geralmente implementações via hardware tendem a considerar os dados não estruturados em oposição a implementações via software. Se os dados relacionados podem ser armazenados próximos, por exemplo, na mesma página.

Granulosidade da Unidade de Coerência: a maioria dos algoritmos sugere a utilização da granulasidade o mais próximo possível da implementação das máquinas. Por exemplo, se um sistema operacional trabalha com páginas de 2kb as páginas da memória compartilhada também deve ter 2kb facilitando assim o desenvolvimento e a parte dos algoritmos que garantem coerência. Este fator deve andar lado a lado com o fator responsável a estrutura dos dados. Se os dados estiverem bem estruturados dentro do sistema de DSM e uma granulosidade satisfatória for adotada será evitado falso compartilhamento. Por exemplo, no algoritmo de migração um dado pode estar bloqueado sem que ele esteja sendo realmente operado simplesmente pelo fato de o dado realmente necessário estar na mesma página.

Responsabilidade do gerenciamento de DSM: quanto mais responsabilidade tiver um servidor em um ambiente distribuído mais a sua performance será crítica para o sistema como um todo.

Política de Consistência de Memória¹⁹: como se deve ter sido notado, uma das grandes preocupações de um algoritmo é manter a coerência. Existem diversas políticas para garantir a coerência que podem influenciar boa parte dos fatores acima citados principalmente no que diz respeito às necessidades da rede de interconexão.

Políticas de Consistência de Memória

Por questões de performance os sistemas que utilizam DSM geralmente fazem replicação de dados que podem ser compartilhados [sem que isso comprometa a ordem de execução do sistema] para permitir seu acesso de maneira concorrente. Tal replicação exige que um controle rígido do que está sendo compartilhado seja mantido.

Um modelo de consistência, entre outros itens, deve ter como primitiva principal que uma leitura sempre retorna o valor da última escrita, entretanto a noção global de tempo em um sistema distribuído implica na sincronização dos relógios dos processadores participantes do contexto, e este é um problema ainda não resolvido plenamente.

Portanto um modelo de consistência de memória deve garantir da melhor forma possível a sincronização do acesso aos dados compartilhados.

Um dos fatores mais decisivos na DSM é como um determinado algoritmo implementa a coerência. Como será mostrado existem várias cabe decidir qual a melhor para cada caso tomando como base os recursos disponíveis como rede, estrutura de dados e outros já citados.

Cabe aqui uma importante nota: os algoritmos mostrados neste documento não estavam presos a nenhum das políticas de consistência. A entidade que o implementar é que deve decidir qual (ou quais) utilizar.

Consistência Seqüencial: Tem suas bases na seguinte premissa: “o efeito de cada acesso à memória deve ser executado globalmente antes que o próximo acesso tenha permissão para executar”²⁰.

Consistência de Processador²¹: garante a ordem das operações realizadas por uma determinada máquina (computador no sistema distribuído) sejam realizadas na ordem em que foram requisitadas. Um exemplo ajudará a esclarecer: se duas máquinas escreverem diferentes valores em determinada variável compartilhada cada uma irá ver primeiro o valor da sua escrita.

Consistência Fraca²²: este tipo de implementação transfere a parte do problema de consistência para as mãos do programador sendo este responsável por dizer quando é necessário garanti-la. Um observação: só são permitidas novas operações depois que todo o processo de sincronização é finalizado.

Consistência de Liberação²³: baseia-se em fazer o programador explicitar o acesso a regiões críticas baseando-se em duas diretivas: acquire e release.

Níveis de implementação

O mecanismo de abstração de um DSM pode ser implementado tanto a nível de hardware quanto a nível de software quanto de maneira híbrida. O nível de implementação do DSM afetará tanto o custo de programação quanto o desempenho do sistema.

O mecanismo de DSM pode ser implementado por software através de rotinas de biblioteca em tempo de execução, sistema operacional ou linguagem de programação. Implementações por software tem um custo menor mas geram uma latência de memória maior que implementações por hardware, pois costumam envolver chamadas ao núcleo do sistema operacional, troca de contexto, buferização além da latência do software de comunicação.

Mecanismos de DSM implementados em hardware tem um desempenho mais alto do que os mecanismos implementados por software, mas no entanto exigem hardware especial e um alto custo de implementação. Implementações por hardware são usadas quando a performance esperada do sistema é mais importante que o custo.

Até mesmo em implementações de DSM por hardware, existem características controladas por software, as quais são explicitamente realizadas pelo programador com o objetivo de otimizar as referências a memória. Também várias propostas de DSM por software exigem algum suporte de hardware. Portanto, torna-se mais natural empregar métodos híbridos, com elementos de software e hardware combinados para balancear a relação de custo e benefício.

Gerenciamento de Transações

Significa o tratamento correto de cada uma das transações que ocorrem no ambiente E isto inclui os aspectos de concorrência.

Uma transação é um conjunto de operações executadas sobre dados compartilhados que são agrupadas e tratadas como uma única operação. O gerenciamento de transações deve garantir que o conjunto de todas as operações seja tratado da melhor forma possível assegurando a consistência dos dados envolvidos. Portanto o controle de concorrência e consistência dos dados são os principais aspectos do gerenciamento de transações.

Propriedades ACID

ACID é uma sigla formada por quatro palavras de lingua inglesa: Atomicity, Consistency, Isolation e Durability. Traduzindo: Atomicidade, Consistência, Isolamento e Durabilidade. A seguir cada uma delas é descrita:

Atomicidade: A transação deve ser completamente concluída, caso contrário nada ocorre. Se um erro ocorre no meio da transação toda ela é desfeita.

Consistência: Uma transação deve começar a partir de um estado de consistencia e ao seu término deixar o sistema consistente.

Isolamento: Os dados são manipuilados por uma e apenas uma transação por vez. Desta forma outras transações acessam apenas dados consistentes.

Durabilidade: Uma vez que uma transação seja encerrada, deve-se garantir que ela esteja completa mesmo no caso da ocorrência de uma falha no sistema.

Commit de Duas Fases

Do inglês, Two Phase Commit, é um protocolo que assegura as propriedades ACID de uma transação em ambientes de computação distribuida.

Conclusão

Existem atualmente uma série de implementações disponíveis no mercado mas é evidente que todas elas se baseiam em uma forte teoria. O profissional de informática deve conhece-la para saber por qual das implementações disponíveis deve optar e assim ampliar as disponibilidades de processamento e aumentar a eficiência dos seus sistemas.

Notas de Rodapé