Optimal Multiprocessor Real-Time Scheduling via Reduction to Uniprocessor

Abstract

Neste trabalho de doutorado, propõe-se RUN (Redução para Uniprocessor), um novo algoritmo de escalonamento para conjunto de tarefas periódicas com deadlines implícitas em sistemas multiprocessador de tempo real, nos quais as tarefas possuem restrições tanto no domínio do tempo quanto no domínio de valores. RUN apresenta as seguintes propriedades relevantes:

- RUN é ótimo no sentido que ele produz um escalonamento correto, no qual todas as restrições temporais são atendidas, de qualquer sistemas de tarefas utilizando até 100% dos processadores da plataforma de tempo real;

- RUN usa o conceito-chave do escalonamento do tempo ócio, chamado de escalonamento por dualidade, segundo o qual, em algum instante t, o escalonamento de uma tarefa utiliza tanto o conhecimento de seu tempo de execução restante, bem como o seu tempo ócio restante;

- RUN baseia-se na diminuição do número de tarefas a ser escalonadas pela suas agregações em supertasks, os quais chamamos de servidores, com taxa acumulada não superior a 1. Cada servidor é responsável por escalonar o seu conjunto de tarefas clientes, de acordo com alguma política de escalonamento;

- RUN utiliza o princípio original de justiça global (Gfair), de acordo com o qual cada servidor de um conjunto de tarefas T é garantido de executar por um tempo proporcional à taxa acumulada das tarefas de T entre cada duas deadlines das tarefas de T;

- RUN reduz o problema do escalonamento de um conjunto de tarefas em/m/ processadores no problema equivalente do escalonamento de um ou mais conjuntos de tarefas diferentes em sistemas monoprocessador;

- RUN supera significativamente os algoritmos ótimos existentes em termos de preempções com um limite superior de O(log m) preempções média por jobs em/m/ processadores.