Escalonamento dinamico de tarefas periodicas e esporadicas

Orientador: Mauricio Ferreira MagalhãesTese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia EletricaResumo: Atualmente, uma abordagem metodológica formal é fundamental para se construir sistemas computacionais de caráter crítico. Estes sistemas, denominados SIstemas de Tempo-Real Crítico(STRC), baseiam-se no fato de que as restrições temporais quantitativas devem ser obedecidas. Tal característica se deve ao fato de que STRCs são, em geral, sistemas dedicados integrados em sistemas maiores que monitoram e controlam um ambiente físico. Este trabalho está inserido dentro do paradigma de flexibilidade e previsibilidade para STRCs que consistem, respectivamente, na capacidade de adaptação do sistema a um ambiente variável e, ao mesmo tempo, na capacidade de prever que determinados comportamentos, que comprometam a operação do sistema, nunca irão ocorrer. Vamos nos concentar na busca de soluções para testes de escalonabilidade que sejam apropriados para STRCs em ambientes dinâmicos. Portanto, estaremos lidando com sistemas onde as tarefas computacionais têm parâmetros que variam no tempo. Serão abordados vários modelos de escalonamento de tarefas, tanto periódicas quanto esporádicas, partindo-se de situações mais simples, onde as tarefas são independentes e, portanto, completamente preemptíveis, até situações onde as tarefas podem apresentar relações de precedência. Inicialmente, investigamos a escalonabilidade de um conjunto de tarefas periódicas com prazo arbitrário, através do fator de utilização. Propomos um teste de escalonabilidade adequado aos propósitos de um escalonamento on-line eficiente, A ,partir daí, verificamos que um servidor esporádico dinâmico pode ser empregado para o teste de escalonabilidade de tarefas em tempo de execução, e apresentamos uma condição suficiente para o escalonamento de tarefas esporádicas em tempo de execução, bem como, reformulamos uma condição necessária e suficiente, de tal forma a atender os requisitos de teste rápido. Através de simulações, analisamos o nível de eficiência das condições suficientes e da condição exata proposta. Para garantir que as tarefas esporádicas essenciais possam cumprir seus prazos, mesmo em situações de sobrecarga, propomos um algoritmo de escalonamento que garanta que tarefas mais importantes possam ser escalonadas com sucesso. Verificamos que o algoritmo proposto, embora seja computacionalmente rápido, tem uma eficiência muito próxima à eficiência de um algoritmo ótimo para o problema referido. Por fim, tratamos o caso em que algumas tarefas periódicas mantêm relações de interdependência, de tal forma a produzir um teste global de escalonabilidade para tarefas periódicas que possuem relações de precedência e tarefas esporádicas com grau de funcionalidade diferente, procurando maximizar a utilização da UCP e garantir a escalonabilidade de tarefas essenciaisAbstract: Nowadays, the design and implementation of Hard Real-Time(HRT) Systems can only be accomplished through a formal methodological approach. These HRT systems are based upon the fact that the quantitative temporal behaviour must be meto Otherwise, severe negative consequences may occur and be spread in the environment. Such behaviour is due to the fact that HRT systems are, generally, embebbed in larger systems that control physical processes. This work is closely tied to the fiexibility and predictability paradigm. This paradigm requires that the HRT system must be fiexible enough to adapt to its environment, and, at the same time, that the desired behaviour will be guaranteed to occur, insuring a safe system. Flexibility relates itself to dynamic reconfiguration( on-line), while predictability will guarantee that the behaviour is according to what is expected. In this way, these aspects may confiict with each other. In this work, we search for schedulability tests that are suitable when dealing with dynamic environment HRT systems. Thus, we allow systems whose comimtational tasks might have varying parameters, for example, variable worst case execution time. The research core contributes to the scheduling theory of periodic and sporadic tasks, particularly when on-line tests are necessary. It will be seen several scheduling models of periodic and sporadic tasks, from the very simple assumptions, where tasks are independent and completely preemptible, up to cases where precedence relations occurs. Initially, we investigate the schedulability of a periodic task set with arbitrary deadlines, through the utilization factor. We propose a schedulability test that is suitable to online scheduling. Then, we drift to a dynamic sporadic server, that can be used as a schedulability test at execution time, and we provide a suflicient condition for sporadic test scheduling as well as redesign an exact condition in order to fullfill the timetable. Through the simulations, we analyse how accurate our condition is working. In order to guarantee that the most important sporadic tasks will met their temporal constraints, even operating at overload, we propose a scheduling algorithm that will try to guarantee important tasks and not to jeopardize urgent tasks. We show that our algorithm is computationally fast and has a great eflicient average. Finally, we deal with periodic tasks that present precedence relations, such that they can be embebbed in a system with sporadic and independent periodic tasks and the overall schedulability may be tested on-line. So, our thesis is very concerned about fiexible environments, as we employ on-line tests, as well as predictable issues, dictated by the applicationsDoutoradoAutomaçãoDoutor em Engenharia Elétric