Notas de Aula - MAC 5755 - Sistemas Operacionais Distribuídos

Aula 12 - 21/9/2001

Modelos de Sistemas Distribuídos

• referência: Tanenbaum 4.2

1. antigamente: um computador de grande porte + vários terminais
2. década de 80 e início da década de 90: computadores pessoais desconectados ou fracamente conectados
3. recentemente: estações de trabalho ligadas a redes locais ligadas à Internet:

• Classificação de redes de acordo com tipo das estações de trabalho:
1. Sem disco
• vantagem: baixo custo, HW simples, configuração simples, flexibilidade
• desvantagem: alto uso da rede, servidores de arquivos se tornam gargalo
2. Disco local para paginação e arquivos temporários
• vantagem: redução do tráfego em rede, mais velocidade na execução
• desvantagem: custo adicional dos discos
3. Disco local para paginação, arquivos temporários e executáveis
• vantagem: redução do tráfego em rede
• desvantagem: manutenção mais difícel
4. Disco local para paginação e arquivos temporários, cache de arquivos
• vantagem: redução do tráfego em rede, diminuição de carga nos servidores
• desvantagem: problemas de consistência do cache
5. Disco local para sistema de arquivos completo
• vantagem: tráfego na rede bem baixo, elimina necessidade de servidores
• desvantagem: perda de transparência e flexibilidade, alto custo de configuração

• Grande problema em sistemas baseados em Estações de Trabalho:
• Elas ficam ociosas a maior parte do tempo!
• Precisamos de mecanismos que nos façam poder utilizar esses processadores ociosos:
• comando at e rsh do UNIX
• protetor de tela que resolve problemas computacionalmente pesados
• programa gerenciador de carga didática sendo desenvolvido no curso de XP.
• "venda" de ciclos de processadores ociosos para quem precisa
• Escalonamento Distribuído.

Escalonamento em Sistemas Distribuídos

• referência: Galli, capítulo 7
• Duas questões principais:
1. em qual máquina executar cada processo (escalonamento global ou alocação de processadores)
2. respondida a questão anterior, em qual instante executar cada processo (escalonamento local)

Escalonamento Global

• Apresentamos o tópico de acordo com a taxonomia de Casavant e Kuhl (1988):

1. Tipo da distribuição de carga (objetivos diferentes):
1. Balanceamento de carga (de forma homogênea)
2. Compartilhamento de carga (de forma a evitar máquinas sobrecarregadas)
2. Tipo do algoritmo de escalonamento:
1. algoritmo otimal (busca uma solução ótima)
• otimalidade é medida em termos de
1. tempo total de execução
2. tempo de resposta
3. vazão (número de processos completados por minuto)
• escalonador precisa ter um conhecimento detalhado sobre todos os processos do sistema
• NP-difícil para mais de 2 processadores
• grosso modo, equivalente a testar todas as possibilidades e escolher a melhor
2. algoritmo sub-otimal (busca uma solução boa que não necessariamente é a melhor)
1. Algoritmos de Aproximação
• similar a algoritmos otimais mas não testam todas as possibilidades
• limitam o espaço de busca de forma a achar uma solução boa mais rápido
• Exemplos: Resfriamento Simulado (Simulated Annealing), Algoritmos Genéticos, Busca Tabu
2. Algoritmos com Heurísticas
• usa regras ou intuições sobre escalonamento
• não é possível provar que funcionam, não há justificativa formal para o método
• mas, em geral, funcionam. Exemplos:
1. processos inter-dependentes que "conversam" muito devem ser colocados na mesma máquina ou, pelo menos, próximos
2. processos que compartilham arquivos devem ser colocados na mesma máquina
3. processos sem nenhuma inter-relação aparente devem ser distribuídos homogeneamente pelo sistema
4. se uma máquina está com alta carga, não escalone mais processos para ela
5. ao escalonar um novo processo, escolha a máquina que esteja com carga mais livre.
• heurísticas funcionam bem em sistemas dinâmicos onde não se conhece a priori os processos.
3. Momento da escolha da máquina
1. em qual momento o sistema define em qual nó cada processo será executado
1. tempo de criação do programa executável (estático)
2. tempo de execução (dinâmico)
2. hoje em dia, praticamente só dinâmico é aceitável; estático soa meio ridículo :-)
4. Responsabilidade pelo escalonamento
1. centralizada em um nó coordenador
2. distribuída
5. Tipo de participação das máquinas do sistema distribuído
1. voluntária
2. obrigatória
6. Permanência das decisões de escalonamento
1. decisão imutável, uma vez escolhido o nó, não muda mais
2. adaptável, usa reconfiguração dinâmica / migração para mudar o escalonamento global

• Algoritmos de Escalonamento Global
1. Pontos de Utilização
• Compartilhamento de carga, sub-otimal, heurístico, imutável, escalonador centralizado dinâmico
• pontos de utilização mantidos em um servidor central
• ao usar recursos remotos, os pontos de utilização de uma máquina são acrescidos
• ao oferecer seus recursos para processos remotos, a máquina recebe crédito e seus pontos são decrementados
• máquinas com menos pontos tem prioridade menor para execução pelo escalonador global
• Fig. 7.3 Galli
• pontos de utilização ponderados cobram mais pontos de máquina com carga mais elevada e dão mais crédito a uma máquina quando ela deixa outros usarem seus recursos e a sua carga está elevada.
• Fig. 7.4 Galli
• Ferguson, Yemini e Nikolaou (1988) propuseram a idéia de usar leilões para escalonamento distribuído: cada máquina pode pagar um certo número de pontos para outras máquinas que aceitarem executar os seus processos.
• as máquinas oferecem seus recursos pedindo um certo preço por eles
2. Grafos
• Balanceamento de carga, sub-otimal, aproximação, centralizado estático (ou dinâmico)
• Usa assignment graph (grafo de conferimento) determinando qual processador pode executar qual processo.
• Vértices: P1, P2, ..., Pn processos e L1, L2, ..., Lm localizações (processadores)
• Arestas: ligam dois processos se eles se comunicam entre si e ligam um processo a um processador se aquele processo pode ser executado naquele processador.
• as arestas contém pesos representando o custo da comunicação entre dois processos ou a afinidade de um certo processo a um certo processador
• Corte no grafo: Fig. 7.5 Galli
• o custo do corte é a soma dos pesos das arestas que foram cortadas
• procura-se o corte de custo mínimo
• Outra possibilidade equivalente é usar o Fluxo Máximo
3. Sondas
• enviam-se mensagens (sondas) para os processadores para descobrir qual o melhor lugar para se executar
• pode ser otimal (enviando sondas para todos os processadores) ou sub-otimal (enviando sondas só para um subconjunto ou não utilizando toda a informação coletada pela sonda)
• pode ser distribuído (todo processador pode mandar sondas) ou centralizado (só um pode)
• sondas podem também ser utilizadas para verificar possibilidades de reconfiguração, tornando o método adaptativo
4. Filas de Escalonamento
• são amplamente usadas em escalonamento local
• processadores poderiam manter filas de processos para execução remota incluindo informações sobre as necessidades dos processos
• normalmente essa fila global é mantida em um servidor centralizado mas pode ser cacheada em outros lugares
• pode-se acrescentar ganchos nas filas dos escalonadores locais para puxar um novo processo da fila global de vez em quando
• em sistemas heterogêneos, as entradas na fila global podem conter informações sobre os requisitos para execução do processo
• Essa abordagem foi proposta no Mach da CMU em 1990 por David Black
• Fig. 7.6 Galli
• prioridades aumentam com a idade do thread e diminui com o quanto de CPU ele já usou
• prioridades escalonadas podem ser ligeiramente modificadas por usuários (usando "dicas")
• só tira alguém das filas globais se as filas locais estão vazias
• Mach usa 32 filas
• Mach permite escalonamento em gangues (gang scheduling) para aplicações paralelas onde se define conjuntos de processadores e vários threads são colocados para execução simultânea nesse conjunto
5. Aprendizado Estocástico
• Próxima aula...

Capítulo 7 do Galli, seções 4.2 e 4.3 do Tanenbaum e capítulo 7 e 8 do Sinha.