Em alguns pontos, porém, os Sistemas Distribuídos diferem das máquinas Paralelas verdadeiras. Um dos pontos que nos interessa neste trabalho, é o fato da heterogeneidade do Sistema, ou seja, uma vez que o objetivo é abstrair a rede do usuário, transformando-o mais próximo de uma máquina com vários processadores, temos que estes processadores "virtuais" não são, necessariamente, iguais. Podemos ter máquinas Pentium, misturadas com SUN; podemos ter máquinas com 32 Mb e outras com 64Mb de memória; máquinas rodando a 200Mhz e outras a 300Mhz... Isto nos traz um grande problema: como dividir as tarefas da melhor forma possível neste ambiente distribuído?

O problema também merece atenção nas máquinas paralelas, mas neste caso, uma atenção especial deve ser dada. O fato destas máquinas terem memória compartilhada e suas unidades processadoras iguais (geralmente) e sincronizadas facilita bastante o trabalho de divisão de tarefas. Podemos afirmar que nestas máquinas, simplesmente distribuindo de igual forma as tarefas pelo número de processadores já é um bom começo.

O mesmo não funciona de forma eficiente nos Sistemas Distribuídos. Isso porque, dada as características das CPUs, é muito provável que aquela com maior poder (mais rápida, maior memória, etc) concluirá sua(s) tarefa(s) bem antes que as mais modestas, vindo a ficar ociosa [SIN94]. É fácil perceber que, neste caso, podemos não ter o resultado esperado e pior, podemos até ter um desempenho inferior ao que teríamos se colocássemos todas as tarefas na máquina mais robusta.

Podemos perceber, então, que não basta termos as tarefas a serem executadas, precisamos dividir da melhor maneira possível estas tarefas levando em consideração as características do sistema que estou usando. Para isso, algumas coisas importantes precisam ser estudadas. Primeiro, procurar a melhor maneira de medir o "poder" de processamento das máquinas (chamadas aqui de nodos) e o grau de ociosidade dos mesmos. Depois, tentar medir o "peso" (carga) das tarefas a serem distribuídas e estimar o tempo (ou a ordem) de processamento necessário. Com estas informações, é possível então providenciar uma correta distribuição destas tarefas, ou seja, a busca do Escalonamento ótimo.

Para o correto Escalonamento em Sistemas Distribuídos, um ponto inicial é conhecer detalhadamente cada um dos nodos participantes. Conhecer as características físicas (velocidade, memória, tipo) é fácil e não oferece grandes problemas. A parte mais delicada é saber o grau de ociosidade de um nodo. Saber "quanto" de sua capacidade de processamento está sendo usada.

Uma maneira bem simples e bastante usada é simplesmente usar o tempo médio de espera na fila de execução como medida. Esta média é obtida a partir dos tempos anteriores que as tarefas levaram para serem executadas, desde de a sua entrada na fila até sua saída (execução completada). Esta medida pode ser um tanto injusta se as tarefas não tem a mesma granulosidade.

Uma outra, seria gerar um índice de utilização da CPU. Para isso, é necessário a utilização de processos específicos para testar, de tempos em tempos, estas características..

Outra preocupação deve ser feita quanto a freqüência com que estas informações são atualizadas. Uma atualização excessiva pode onerar muito a CPU, fazendo com que o algoritmo de Escalonamento seja o principal consumidor do Sistema ao qual se propõe escalonar. Por outro lado, uma atualização insuficiente pode resultar na escolha de um nodo que já não mais possui aquelas características, e portanto, resultar em uma escolha errônea. Alguns algoritmos se propõe a fazer apenas uma vez o levantamento das condições dos nodos e usar estes dados durante todo o processo. Esta técnica é chamada de Estática, enquanto que as que se preocupam em atualizar as informações freqüentemente são conhecidas como Dinâmicas.

Escalonamento Dinâmico

Neste tipo de escalonamento há uma constante análise das características dos nodos. No caso de usarmos tempo de espera na fila de CPU como medida de ociosidade não há a necessidade de muito processamento para obter esta informação mas se for usado utilização da CPU, precisaremos de pequenos processos rodando em backgraund para fazer testes contínuos à CPU onde está, coletando informações úteis ao correto escalonamento (chamados de espiões) . Esta prática, no entanto, não é bem vista por alguns autores pois este processo, o espião, acaba sendo também um consumidor de CPU tornando sua atuação onerosa. Para alguns casos pode acontecer que simplesmente dividindo-se as tarefas usando como fator apenas o tempo de espera na fila é ainda mais produtivo que esperar que os espiões analisem cada nodo e forneçam as informações requeridas.

Uma alternativa seria poder regular a intensidade de oneração da CPU, ou seja, que o espião fosse capaz de aumentar um diminuir a freqüência destes testes. Algoritmos que usam esta técnica são um caso especial de Escalonamento Dinâmico e são chamados de Adaptativos. Nestes o algoritmo pode, por exemplo, deixar de realizar alguns testes para não onerar tanto a CPU.

Overhead

Um outro grave problema no Escalonamento em Sistemas Distribuídos é quanto ao Overhead de comunicação. Como estes sistemas são necessariamente com memória distribuída (fisicamente, mesmo que possa ser simulada), o custo na troca de informações entre os nodos é muito grande. Se tivermos, por exemplo, um espião em cada nodo e este constantemente envie mensagens ao Escalonador ou a outros nodos, podemos ter um excesso de comunicação e problemas de desempenho (os nodos ficarão mais tempo se comunicando do que processando).

Podemos classificar um algoritmo de escalonamento de acordo com algumas políticas. A primeira seria determinar qual nodo está apto a receber uma tarefa. Ou seja, qual nodo está trabalhando aquém de suas capacidades de processamento. Também podemos considerar, neste caso, os nodos que estão sobrecarregados, ou seja, estão com um processamento maior que sua capacidade. Nesta etapa (chamada de Política de Transferência) o escalonador define com receiver (ou receptor) os nodos que estão com pouca carga, ou seja, podem receber mais tarefas; e como sender (ou doador) aqueles que estão sobrecarregados. Dependendo do caso, uma troca de tarefas entre receivers e senders (do sender para o receiver) pode ser feita o que denota a segunda política: escolher, dentre tantas, a tarefa mais adequada a ser enviada a determinado nodo. A esta função é dado o nome de Política de seleção. Outra é achar, dentre todos os nodos, aquele mais adequado a receber a carga, a qual recebe o nome de Política de localização. E finalmente definir o local onde as informações sobre os nodos são armazenados e com que freqüência são atualizados (Política de Informação)

De transferência

No caso da política de Transferência, normalmente define-se um número máximo de carga que o nodo suporta. Se a carga atual do nodo ultrapassar este limite, então temos um doador. Caso contrário, o nodo pode ser considerado como receptor. Um cuidado especial deve ser dado quanto a transferência de tarefas de um doador para um receptor. Imagine a seguinte situação: um doador (que tem sua carga maior que o limite) envia uma tarefa para um receptor (cuja carga é menor). Digamos que este receptor, que tinha sua carga menor que o limite, ao receber esta nova tarefa passa a ser um doador (com a carga maior que o limite). Sendo ele um doador, poderá procurar um receptor para esta carga que causou o problema. Esta troca de tarefas pode ser feita várias vezes e até mesmo de forma indefinida. Uma técnica que resolve isto é considerar como doador não apenas se sua carga for menor, mas também se continuará sendo menor ou igual depois de receber a tarefa.

De seleção

Logo que um nodo precisa enviar uma tarefa que o está onerando, ou está apto a receber, a política de seleção decide qual será a tarefa escolhida. Neste ponto vemos também a diferença entre escalonamento Preemptivo e não-preemptivo. No primeiro, uma tarefa que já está em execução pode ser escolhida para ser transferida a outro nodo. Este método pode ser muito oneroso dados os custos necessários à sua transferência. Isso porque tem-se que transferir todo o contexto da tarefa (dados em memória, etc). Geralmente opta-se por tarefas recentemente iniciadas, pois são as que devem possuir menores custos de transferências. Ou então, as tarefas menores.

Já o não-preemptivo transfere somente tarefas que ainda não executaram e, portanto, não necessitam de transferência de contexto.

No caso de nodos sobrecarregados, o mais comum é escolher a tarefa que causou a sobrecarga.

De localização

Como mencionado, consiste no método usado para escolher o nodo que receberá a tarefa. O método mais utilizado é o randômico, ou seja, um nodo escolhe aleatoriamente outro nodo para receber ou enviar tarefa. O problema desta técnica é a chance de se escolher um nodo que esteja na mesma situação que o atual. Uma solução é testar se este nodo possui as características necessárias para fazer-se a troca de tarefas. Alguns selecionam vários nodos e fazem uma votação entre estes para garantir que o melhor nodo foi escolhido, mas isto gera um excesso de comunicação.

De informação

Diz respeito a troca de informações sobre seu estado entre os vários nodos. Podemos ter um armazenamento local, isto é, um nodo específico receber todas as mensagens de estado dos outros. Isso, porém, criará um "gargalo" neste nodo. Uma outra, seria cada nodo enviar um broadcast para todos os outros informando sua capacidade de processamento.

O mais comum, no entanto, é cada nodo ter apenas as informações sobre si próprio e estas informações serem requisitadas por outro nodo quando este desejar fazer uma troca de tarefas. Isto é chamado de demanda, onde cada nodo só se "interessa" pelo estado dos outros quando se torna ou um doador ou um receptor.

Vamos dar uma analisada em dois tipos de algorítmos: os iniciados pelo sender, pelo receiver.

Iniciados pelo sender

Neste tipo de algoritmo, o nodo que ultrapassou seu limite de carga, ou seja, pela definição de sua política de Transferência tornou-se um doador, aciona o algoritmo na tentativa de aliviar sua carga. Assim sendo, é ele quem procura um receptor para sua carga. Alguns algoritmos possuem procura randômica, ou seja, quando precisam "se livrar" de uma carga, selecionam aleatoriamente um nodo para fazê-lo. A aleatoriedade dificulta a coincidência de um mesmo nodo receptor ser escolhido mais de uma vez.

Iniciados pelo Receptor

Aqui o nodo que se encontra da situação de receptor solicita tarefas para processar. Ele então procura um doador para receber tarefas. Esta abordagem é mais interessante pois o nodo que está ocioso tem mais tempo para se preocupar em achar um doador adequado.

Veremos agora o caso de dois sistemas operacionais: o V-System e o Sprite.

V-System

Neste sistema, cada nodo envia um Broadcast com seu estado sempre que este muda consideravelmente. Estes dados são, tipicamente, a utilização da CPU e da memória, além dos dados já conhecidos (que é enviado apenas uma vez) do tipo do processador, e características físicas. Um processo daemon em cada nosso fica responsável em atualiza estas informações.Todos os nodos, então, guardam informações sobre todos os outros. Uma alternativa usada para diminuir o número de informações é cada nodo guardar os estados apenas dos nodos mais livres. Quando uma tarefa precisa ser enviada a outro nodo, este é escolhido randomicamente.

A tarefa escolhida para transferir quando este nodo estiver sobrecarregado é aquela mais recente, ou seja, a que foi designada ao nodo por último, e se o nodo send for um dos de menores cargas (situação no qual todos estão sobrecarregados) a tarefa permanece local.

O problema deste algoritmo é o alto custo de um Broadcast.

Sprite

Este sistema difere drasticamente do anterior. Neste há um Escalonador Central, responsável por todo o escalonamento. Cada nodo envia mensagem para o escalonador informando se está apto a receber tarefas (se é um receiver). Interessante, neste sistema, é que um nodo é considerado ocioso (isto é, um receiver) quando não houver atividade de mouse ou teclado por 30 segundos.

Este custo deve ser ainda mais cuidadosamente avaliado se implementar-se migração de tarefas (preemptivo). Para a execução de um processo em um nodo, salvar seu contexto (dados em memória, pilha, etc), enviar todas estas informações para outro nodo e reiniciar este processo lá, pode levar muito mais tempo do que levaria se o processo permanecesse no nodo sobrecarregado.

[EL-94] EL-REWINI, Heshan; LEWIS, Theodore G.; ALI, Heshan H. Task Scheduling in Parallel and Distributed Systems. Prentice Hall, New Jersey. 1994.290p.

[GAR94] GARCIA, Leonardo de Carvalho. Balanceamento de carga em Sistemas paralelos Fracamente Acoplados. Dissertação de Mestrado. Orientador: Prof. Philippe Olivier Alexandre Navaux. CPGCC, UFRGS. Porto Alegre. 1994. 165p.

[PIN95] PINEDO, Michael. Scheduling: Theory, Algorithms and Systems. Prentice Hall, New Jersey. 1995. 378p.

[SIN94] SINGHAL, Mukesh; SHIVARATRI, Niranjan g.. Advanced Concepts in Operating Systems: Distributed, Database and Multiprocessor operating Systems. McGraw-hill, New York. 1994.522p.