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

Aula 11 - 24/9/2003

[Eager 86]
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
hoje em dia, as sondas podem ser implementadas não só como mensagens comuns mas também como agentes móveis

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

É uma heurística onde o sistema tenta aprender com a sua história recente; ele tenta determinar qual é a melhor ação a ser tomada baseada no resultado das ações passadas.
Por exemplo

Determinar inicialmente probabilidades iguais de envio de processos para cada nó.
Se o nó escolhido estava relativamente livre, ele envia uma resposta aprovando a escolha e a sua probabilidade aumenta;
o oposto ocorre se o nó estava muito carregado.
Pode-se também usar uma espécie de autômato onde cada estado representa um estado global do sistema (baseado na carga nos nós do sistema).
Em cada estado do autômato, tem-se um vetor de probabilidades para cada nó.
Monitora-se o estado do sistema periodicamente e determina-se em qual estado do autômato se está.

todas máquinas enviam periodicamente informações sobre o seu estado para um nó central
se uma máquina está ociosa, ela nunca manda processos prá fora
se uma máquina está sobrecarregada, o sistema nunca manda processos externos para ela
carga é avaliada baseado em 1) uso da UCP, 2) uso de memória e 3) E/S
ele realizou experimentos com diferentes formas de avaliar a carga; em ordem do melhor para o pior:

a diferença no tempo de resposta médio do pior para o melhor foi só 32%
ele fez experimentos com combinações de critérios mas eles não mostraram nenhum ganho
usa o autômato descrito acima;
nós enviam o seu estado para o nó central a cada 8 segundos
o vetor de probabilidades é usado para se escolher estocasticamente o nó para a execução de cada processo.

Tanenbaum, seção 4.4
Normalmente, escalonamento local é independente do global e usa o escalonador do SO local.
Mas isso pode ser inapropriado se 2 processos em nós diferentes trocam muitas mensagens

exemplo: Fig 4.20a Tanenbaum, pag. 210.
neste caso, os processos passarão uma boa parte do tempo bloqueados pois quando um manda uma mensagem para o outro, o receptor não está escalonado e vice-versa.
se quisermos resolver este problema, precisamos de um mecanismo que permita que processos que se comunicam com freqüência sejam escalonados de forma sincronizada.
Às vezes é difícil saber quais processos irão se comunicar muito mas em muitos casos (p.ex. processos num pipeline UNIX, aplicações paralelas) é possível.

processadores são divididos em fatias de tempo globais
um broadcast avisa quando se passou de uma fatia para a seguinte
algoritmo é baseado em uma matriz onde as colunas são os processadores e as linhas são as fatias de tempo
Fig. 4.20b Tanenbaum, pag. 210. Exemplo: executar grupo de 4 processos que se comunicam.

Exemplos de Pesquisa Recente

gerenciador de recursos distribuídos em redes de grande área (IME/USP)
artigo descrevendo protocolos para escalonamento global (leitura não obrigatória)

extensão do escalonamento global do 2K para levar em conta análise do histórico passado para prever o futuro
artigo descrevendo protocolos e arquitetura geral do sistema (leitura não obrigatória)

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