Uma infraestrutura para reconfiguração dinâmica de escalonadores tempo real: modelos, algoritmos e aplicações

Abstract

Esta dissertac¸ #ao prop#oe uma infraestrutura para alocac¸ #ao din#amica de tempo de processador em aplicac¸ #oes tempo real multi-modais. A infraestrutura distribui reservas de banda usando modelos de otimizac¸ #ao que podem ser combinados e estendidos para contemplar as necessidades do sistema. Uma vez que a natureza das aplicac¸ #oes varia, diversos modelos s#ao propostos de forma a suportar modos de operac¸ #ao discretos, cont´ýnuos ou h´ýbridos e otimizar um dado crit´erio de desempenho global do sistema ou a justic¸a entre tarefas. Os modelos s#ao generalizac¸ #oes de variada complexidade para o problema da mochila, para os quais algoritmos exatos, heur´ýsticas com garantias de desempenho e esquemas de aproximac¸ #ao em tempo polinomial s#ao propostos. Para fins de avaliac¸ #ao, a infraestrutura foi aplicada no sistema de vis#ao controle e navegac¸ #ao de um rob#o m´ovel, e tamb´em num decodificador multim´ýdia real. Ambas s#ao aplicac¸ #oes que capturam a natureza das tarefas que esta infraestrutura busca suportar.

This dissertation proposes a framework for dynamic, value-based processor time allocation in multi-modal real-time applications. The framework distributes time reservations using optimization models that can be combined and extended to meet the system#s needs. Because the nature of applications varies, several models were proposed to handle discrete, continuous or hybrid modes of operation and optimize task fairness or a given criterion of optimal system performance. The models range from simple to complex generalizations of the knapsack problem for which exac algorithms, heuristics with performance guarantees, and polynomial-time approximation schemes were proposed. As a means of evaluation, the framework was applied to the vision, control and guidance systems on a mobile robot and to a real multimedia decoder, applications that capture the nature of the tasks this framework aims to support.