Genetic Scheduler: Um Algoritmo Genético para Escalonamento de Tarefas com Restrição Temporal em Sistemas Distribuídos

Abstract

Sistemas de Tempo Real (STR) apresentam a necessidade de executar suas tarefas dentro de um limite de tempo conhecido como deadline, caracterizando assim um limite temporal em sua execução. Devido a essa restrição, a ordenação na execução de suas tarefas é um fator crítico para este tipo de sistema. A essa ordenação é dado o nome de escalonamento das tarefas. Encontrar uma lógica capaz de gerar escalonamentos válidos, ou seja, escalonamentos que possam garantir as limitações temporais na execução das tarefas, é uma das principais atividades que devem ser executadas no desenvolvimento de um sistema de tempo real. Como exemplos desse tipo de sistema pode ser citado: sistemas de controle de tráfego aéreo e sistemas de streaming, entre outros. Algoritmos Genéticos (AG) são uma alternativa interessante para a busca de soluções ótimas ou quase-ótimas para problemas de geração de escalonamentos para tarefas de STR em ambientes distribuídos. O objetivo deste trabalho é apresentar uma solução para o problema de geração de escalonamentos de tarefas que possuem limitação no tempo de sua execução, podendo a falha em executar dentro do tempo delimitado gerar problemas de performance ou até levar a sérios erros no sistema. Neste trabalho é apresentado um algoritmo genético capaz de encontrar um escalonamento válido para um conjunto de tarefas que precisam ser executadas em uma determinada configuração de um sistema. É descrito ao longo do trabalho todos os componentes deste algoritmo: modelo do cromossomo, operadores genéticos e critérios de avaliação da qualidade para determinar a validade dos escalonamentos gerados. Por fim, são demonstrados os testes realizados utilizando o algoritmo, detalhando os parâmetros para o algoritmo e métricas obtidas em sua execução.