Avanços tecnológicos referentes ao hardware e ao software usados em sistemas computacionais têm levado ao aumento do interesse pelo uso em larga escala de sistemas paralelos e distribuídos no que se refere às aplicações em tempo real, banco de dados, defesa, sistemas de manufatura e etc. (PINEDO; CHAO, 1999). Uma das principais questões relativas a esses tipos de sistema é o desenvolvimento de técnicas efetivas para a distribuição dos processos e dos programas paralelos em múltiplos processadores. Segundo Pinto (2004), o problema se refere a como distribuir (escalonar ou escalar) os processos entre os elementos processadores para atingir o
objetivo de performance do sistema, por exemplo: a minimização do tempo de execução, a minimização dos atrasos de comunicação, a maximização da utilização dos recursos, bem como atingir os objetivos de controle de uma planta industrial no que tange os aspectos de indeterminismo quanto ao seqüenciamento das atividades, à designação dos recursos e aos tempos relacionados aos processos. Do ponto de vista de um sistema job shop, a escolha dessa distribuição se torna um problema de administração de recursos e pode ser considerado um fator importante durante a fase de projeto dos sistemas de controle em ambientes com múltiplos processadores.
Métodos de escalonamento de processos são tipicamente classificados dentro de categorias como mostrado na taxonomia proposta por Casavant; Kuhl (1988) como mostrado na Fig.3.1. Esta classificação, apesar de antiga, é ainda bastante usada por pesquisadores que trabalham com escalonamento de sistemas. Outras áreas de conhecimento como: planejamento e controle podem usar classificações diferentes. A classificação do método de escalonamento a ser usado encontra-se sombreada.
Figura 3.1 - Classificação dos Métodos de Escalonamento (CASAVANT; KUHL, 1988).
Nesta taxonomia, o escalonamento local consiste em uma designação de processos para as fatias de tempo de um sistema constituído por um único processador e não faz parte do escopo deste trabalho. O escalonamento global, por outro lado, é o processo de decisão de onde executar um processo em um sistema com múltiplos processadores, podendo ser conduzido por uma autoridade simples e centralizada, ou estar distribuído entre os elementos processadores.
Os métodos de escalonamento global podem ser divididos em duas classes, métodos estáticos ou métodos dinâmicos. Os métodos estáticos são caracterizados principalmente pela obtenção do escalonamento antes do início da execução das tarefas, e conseqüentemente, impossível de adaptar-se às mudanças nas hipóteses em tempo de execução. Por essa razão, os métodos dinâmicos são mais adequados a aplicação em sistemas de manufatura flexíveis, como o tipo de sistema de interesse nesta tese.
3.1.1 Escalonamento Dinâmico
Rabelo; Klen (2000) definem escalonamento dinâmico como sendo "a ação de adaptar o escalonamento corrente, simultaneamente com a sua execução, em função da ocorrência de eventos não planejados, tanto os provenientes do chão-de-fábrica como os do nível de planejamento, de tal forma que o escalonamento se mantenha…
realístico: reflita o real estado do chão-de-fábrica; viável: realizável, de acordo com
as restrições temporais, de capacidade e tecnológicas existentes; e coerente: sem desvios em relação aos objetivos e metas traçadas".
O escalonamento dinâmico baseia-se na distribuição dos processos entre os processadores durante o tempo de execução. Essa distribuição é realizada através da transferência de tarefas de processadores sobrecarregados para processadores menos sobrecarregados ou livres. Este processo é conhecido como balanceamento de carga e tem o objetivo de melhorar a performance da aplicação (SHIVARATRI; KREUGER; SINGHAL, 1992). Um algoritmo de balanceamento de carga típico pode ser definido através de três características particulares:
1. característica de informação: a qual especifica a informação de quantidade de carga que se faz necessário para o trabalho aos responsáveis pela tomada de decisão;
2. característica de transferência: determina as condições sob as quais uma tarefa pode ser transferida, isto é, a carga corrente da estação de trabalho e o tamanho da tarefa que está sendo considerada, e ainda, pode ou não incluir a migração de tarefas, ou seja, suspender uma execução de tarefa e a transferir para outra estação de trabalho para que a execute (preempção);
3. característica de alocação: identifica os elementos processadores para os quais uma tarefa possa ser transferida.
As operações de balanceamento de carga podem ser centralizadas em um único processador ou distribuídas entre todos os elementos processadores que participam do processo de balanceamento de carga. Podem também existir algumas políticas de escalonamento combinadas, como por exemplo, o de uma política de informação que pode ser centralizada, porém as políticas de transferência e alocação das tarefas podem ser distribuídas. Nesse caso, todos os elementos processadores enviam suas respectivas informações de carga para um processador central e recebem informação de carga do sistema através desse processador central. No entanto, as decisões relativas a quando e para onde uma tarefa poderia ser transferida são tomadas localmente por cada processador. Se uma política de informação distribuída for empregada, cada elemento processador mantém sua própria imagem local da carga do sistema. Essa política cooperativa é freqüentemente alcançada através da informação de um gradiente de distribuição de carga entre os elementos processadores. Cada processador repassa sua informação de carga corrente para seus pares em intervalos de tempo, resultando na dispersão da informação de carga entre todos os elementos processadores em um curto período de tempo. Políticas de informação distribuída podem também ser não cooperativas. Técnicas de escalonamento aleatório são um exemplo de escalonamento não cooperativo, em que um processador sobrecarregado escolhe aleatoriamente outro processador para o qual irá transferir uma parte da carga de trabalho. O balanceamento aleatório de carga funciona razoavelmente bem quando as cargas de todos os processadores são
relativamente altas, isto é, quando não faz mais diferença onde a tarefa será executada.
A vantagem do balanceamento dinâmico de cargas sobre os métodos estáticos de escalonamento é que o sistema não necessita estar atento em relação ao comportamento do tempo de execução das aplicações antes da execução. A flexibilidade inerente ao balanceamento dinâmico de carga possibilita a adaptação quanto à característica de imprevisibilidade dos requisitos da aplicação em tempo de execução. O ba1anceamento dinâmico de carga é particularmente proveitoso em sistemas que consistem de uma rede de trabalho, composta de estações de trabalho interligadas, na qual a meta primária de desempenho é maximizar a utilização dos processadores em vez de minimizar os tempos de execução das aplicações. A maior desvantagem dos métodos de balanceamento de carga dinâmicos é o custo relativo ao tempo de execução, devido principalmente aos seguintes fatores:
1. transferência de informação de carga entre os processadores;
2. processos de tomada de decisão quanto à seleção dos processos e dos processadores para a transferência de tarefas;
3. atrasos de comunicação com relação às tarefas de auto-alocação.
Apresentada a classe (escalonamento dinâmico) que caracteriza a nova técnica de escalonamento e, antes de apresentar a solução buscada neste trabalho, explanam-se na próxima seção particularidades do escalonamento em sistemas de manufatura e também a notação a ser usada para a descrição formal do problema de escalonamento.