• Linda - Programação Paralela com Memória Compartilhada
• Visão Geral
• Baseada no conceito de memória associativa compartilhada
• C - Linda e Fortran - Linda são as implementações compartilhadas
• Utiliza espaço de tuplas que são implementados em memória distribuída
• Primitivas
• Primitivas que são utilizadas para se fazer acesso as tuplas:
• OUT - tupla adicionada ao espaço de tuplas
• IN - tupla satisfazendo template é retirada do espaço de tuplas
• RD - tupla é lida mas permanece no espaço de tuplas
• EVAL - com OUT, mas cria novo processo para avaliar a tupla
• Comunicação - IN e OUT também podem ser utilizados para comunicação
• Sincronização - Semáforos e Barreiras podem ser implementados com IN e OUT
• Concorrência - Utilização do EVAL para criar novos processos
• Network Linda - Linda implementado em memória distribuída
• Arquivo de configuração das máquinas - .tsnet.config
• Sistema escolhe máquina onde novo processo deve ser disparado - uso de informações de configuração e conheciemento de processos já disparados
• Programador não tem como determinar máquina explicitamente
• Exemplo
• Tuplescope - ferramenta gráfica que simula a execução do programa em uma máquina com o objetivo de depuração do programa
• Sistema Piranha
• Suporte ao aproveitamento de recursos ociosos em aplicações Linda
• Permite ao programador especificar quando uma estação deve ser considerada ociosa e ações a realizar quando uma estação deixar de estar ociosa
• Mapeamento de Tarefas a Processadores
• Distribuição de carga
• Importante para aplicações paralelas e para aplicações como sistemas operacionais distribuídos
• Vários estudos apontam uma alta porcentagem de tempo ocioso em redes de estações de trabalho
• Compartilhamento - máquinas sobrecarregadas tentam distribuir parte de sua carga para máquinas ociosas
• Distribuição pode ser estático ou dinâmico
• Balanceamento de Carga e Aproveitamento
• Realizar o melhor aproveitamento global de recursos
• Minimizar recursos de Comunicação
• Modelar as tarefas e as máquinas disponíveis
• Necessidade de migração para alcançar balanceamento
• Compartilhamento de recursos ( Aproveitamento de recursos ociosos ) - Otimizar a alocação de recursos para aquela aplicação
• Modelo de um sistema operacional com Balanceamento e Compartilhamento de Recursos
• Banco de processadores e estações pessoais
• Alocação estática - Decisão sobre a alocação de cada processo é tomada antes do início da execução do programa
• Grafos de Precedência - Muitas vezes utilizados para alocação estática
• Descreve as relações de precedência entre os vários processos
• Grafos de Interação - Quando não há relação de precedência clara entre as tarefas
• Um grafo para descrever os padrões de comunicação
• Simplificações são usadas - precedências são ignoradas, custo de processamento por tarefa é considerado igual em todos os processadores, possibilidade de superposição de comunicação e execução é ignorada
• Soluções :
• Algorítmos exatos - exploração de todas as possíveis soluções
• Algorítmos Heurísticos ( Gulosos e Iterativos )
• Alocação Dinâmica - Decisão sobre a distribuição dos processos é baseada em informações obtidas em tempo real
• Possibilidade de utilizar migração de processos
• Dificuldade maior : Obter informação efetiva sobre o estado do sistema sem interfirir sobre ele
• Uso de indicadores de carga
• Coleta de informação - O objetivo é manter as informações de carga atualizada sem sobrecarregar o sistema com troca de mensagens
• Coleta voluntária - Cada máquina divulga seu estado a intervalos regulares de tempo ou quando ocorre alguma mudança de estado
• Coleta sob demanda - Cada máquina só divulga seu estado quando é requisitado
• Problemas em estudo
• Extensão de critérios de carga
• Heterogeneidade
• Consideração de relações dinâmicas entre processos
• Migração em redes de alta velocidade

Referências:

Home Page de Linda

Nicholas Carriero and David Gelernter. Linda in Context. Communications of the ACM , 32(4). April 1989.