Problemas de Escalonamento de Tarefas em Computadores
Prof. Flávio Keidi Miyazawa
Os problemas de escalonamento de tarefas que consideramos consistem em determinar uma atribuição das tarefas para processadores de forma a otimizar o tempo de execução total destas tarefas. Alguns problemas de escalonamento de tarefas tem estreita relação com problemas de empacotamento. Isto nos motivou a considerar estes problemas mais particularmente.
A medida que a tecnologia VLSI avança, computadores paralelos com milhares de processadores podem estar disponíveis em breve. Como um processo não necessariamente usa todos estes processadores, poderemos ter vários processos sendo executados ao mesmo tempo, cada um com um subconjunto dedicado de processadores.
Tais problemas são muito importantes para a área de informática e estão ligados diretamente a estratégias usadas por sistemas operacionais e compiladores. São problemas que necessitam de soluções rápidas, muitas vezes de forma on-line. Esta necessidade torna este problema (que é NP-difícil) muito mais complicado pois a busca de soluções ótimas é na maioria dos casos inaceitável (devido ao grande tempo de execução envolvido). Assim, é necessário se obter algoritmos rápidos mas que possuam uma boa garantia de performance, algoritmos de aproximação.
Problema de Escalonamento de Tarefas em Sistemas de
Malha Conexa Particionável (PETSMC)
Um conjunto de tarefas J1,J2,...,Jn deve ser processado em um sistema
de malha conexa particionável que consiste de l x w elementos de
processamento ligados como uma malha retangular (veja Figura
{gridshed}). Cada tarefa Ji é especificada por uma tripla
Ji=(xi,yi,ti) indicando que uma submalha de tamanho (xi,yi) ou (yi,xi)
é requerida pela tarefa Ji, e ti é seu tempo de processamento. O
objetivo é atribuir as tarefas para as submalhas de forma a minimizar
o tempo total de processamento.
A topologia em malha, considerada no problema PETSMC, é uma topologia muito comum em computadores paralelos. Outras topologias comuns em computadores paralelos são: Hiper Malha, Butterfly e Hipercubo.
Problema de Escalonamento de Tarefas em Hipercubo (PEH):
Um sistema de hipercubo é uma rede de computadores (processadores)
onde os processadores estão localizados nos vértices do hipercubo e as
comunicações entre processadores são as arestas do hipercubo (veja
Figura {hipercubos}).
O Problema de Escalonamento no Hipercubo, pode ser definido como: Dado uma
lista de n tarefas J=(J1,...,Jn), cada tarefa Ji com tempo de
execução ti, um sub-hipercubo requerido de dimensão di, e um sistema de
hipercubo H; escalonar as tarefas de J em H de tal forma
que o tempo de execução de todas as tarefas em J é minimizado. Neste
escalonamento, se uma tarefa Ji é escalonada para ser executada em um
subcubo H', então os processadores de H' podem ser escalonados
para outra tarefa somente quando o processamento de Ji estiver encerrado.