Contributions to the estimation of the worst-case execution time using measurements in real-time systems

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia de Automação e Sistemas, Florianópolis, 2019Na medida em que o uso de sistemas computacionais prolifera na sociedade, aplicações com requisitos de tempo real tornam-se cada vez mais comuns. Um passo crítico no desenvolvimento desses sistemas é determinar se as tarefas atendem às restrições temporais. Para isso, são necessárias análises de tempo de execução de pior caso (conhecido como WCET). Ao mesmo tempo, a demanda dos sistemas modernos por software cada vez mais complexo requer computadores mais poderosos e complexos. Com isso, torna-se a análise do WCET um desafio cada vez mais difícil. Neste contexto, o objetivo deste trabalho é investigar e propor métodos que podem ser usados para lidar com arquiteturas de computador complexas para estimar o WCET usando medições. A Análise Temporal Probabilística Baseada em Medição (ATPBM) promete produzir WCET probabilísticos para tarefas de tempo real com base na análise de medições de tempo de execução através da Teoria dos Valores Extremos (TVE). A ATPBM exige que os tempos máximos de execução observados sigam uma distribuição de valores extremos e permitam determinar valores de tempo de execução que se espera que sejam excedidos apenas com probabilidades arbitrariamente baixas (pWCETs). Alguns trabalhos sugerem o uso dos modelos Generalized Pareto ou Generalized Extreme Value, enquanto outros consideram os modelos Gumbel ou Exponential mais adequados. Neste trabalho, primeiramente, realizamos uma avaliação da exatidão dos limites do WCET determinados por meio desses modelos. Para isso, consideramos uma plataforma aleatorizada em tempo, na qual a ATPBM deveria produzir resultados confiáveis, a fim de ser considerada utilizável no caso geral. Posteriormente, realizamos uma avaliação da adequação da ATPBM para estimar o pWCET de uma tarefa executada em uma arquitetura complexa com o Linux. Optamos por realizar a análise de uma tarefa que é frequentemente usada em análise temporal com dados de entrada fixos conhecidos para induzir altos tempos de execução e empregamos uma amostra de validação coletada usando a ferramenta Perf. Usamos a ferramenta Perf para deduzir a interferência direta de outras tarefas e tratadores de interrupção. No entanto, tarefas de tempo real executadas em arquiteturas complexas sofrem grande interferência indireta de outras atividades executadas no mesmo sistema, gerando, assim, ruído nos tempos de execução. Neste contexto, é difícil ou impossível determinar o pior cenário para a análise temporal baseada em medições. A variabilidade temporal induzida tanto pelos efeitos de hardware quanto pelos caminhos de execução depende, direta ou indiretamente, dos dados de entrada usados. Nosso experimento mostra que os dados de entrada conhecidos por induzir altos tempos de execução podem produzir tempo de execução menores em tais plataformas. Para fornecer estimativas confiáveis do WCET, é necessário selecionar os dados de entrada que induzem tempos de execução altos. Neste trabalho, realizamos uma análise dos tempos de execução de tarefas de tempo real com respeito aos dados de entrada, isto é, (1) verificamos a sensibilidade dos tempos de execução de tarefas aos dados de entrada, e (2) avaliamos quantitativamente seu impacto nos tempos de execução resultantes. Tarefas sensíveis aos dados de entrada requerem os dados de entrada que maximizam o tempo de execução. Uma abordagem para selecionar dados de entrada é utilizar algoritmos de otimização. No entanto, a variabilidade temporal observada em arquiteturas complexas dificulta a comparação de medidas de tempo de execução obtidas usando dados de entrada diferentes. Nesse contexto, (1) realizamos uma avaliação de diferentes métodos de medição, (2) implementamos um algoritmo genético no qual a função de fitness é baseada em medições de tempo de execução selecionadas usando métodos clássicos e novos, e (3) estimamos limites pWCETs para uma tarefa, usando os piores dados de entrada obtidos através do algoritmo genético desenvolvido. Destacamos que, o trabalho proposto é justificado pela sua relevância científica e pelo potencial impacto econômico positivo decorrente dos métodos para a determinação das estimativas do WCET.Abstract: As the use of computers proliferates in our society, systems with strict timing requirements -- or Real-Time Systems (RTS) -- become ever more common. A critical step in designing such systems is determining whether tasks meet their timing constraints. For that, Worst-Case Execution Time (WCET) analyses are necessary. At the same time, modern systems' demand for increasingly complex software requires more powerful and complex computers being used. These facts make RTS' WCET analysis an increasingly harder challenge. In this context, the objective of this work is to investigate and propose methods that can be used to deal with complex computer architectures for estimating WCET using measurements. The technique known as Measurement-Based Probabilistic Timing Analysis (MBPTA) promises producing WCET bounds for RTS' tasks based on the analysis of execution time measurements through Extreme Value Theory (EVT). For that, MBPTA requires the analysed tasks' maximum observed execution times to adhere to an extreme value distribution and allows determining execution time values expected to be exceeded only with arbitrarily low probabilities (pWCETs). Several works suggest the use of Generalized Pareto or the Generalized Extreme Value models, while others consider the Gumbel or the Exponential models more adequate. In this work, firstly we perform an assessment on the tightness of the WCET bounds determined through these models. For that, we considered a time-randomized platform, in which MBPTA should yield remarkably reliable results in order to be deemed usable in the general case. Posteriorly, we performed an assessment of the adequacy of MBPTA to estimate the pWCET of a task executed on a complex architecture with Linux. For that, we chose to perform the analysis of a task that is frequently used in temporal analysis with fixed input data known to induce high execution times and employed a large execution time validation sample collected using the Perf tool. We use the Perf tool in order to deduct the direct interference from other tasks and interrupt handlers. Real-time tasks executed on complex architectures suffer large indirect interference from other activities executing on the same system, hence generating noise in the observed execution times. In this context, it is difficult to determine the worst scenario for tasks' measurement-based temporal analysis. The timing variability induced both by hardware effects and by the execution paths depend, directly or indirectly, on the input data used. Our experiment shows that the input data generally used in temporal analysis, known to induce high execution times, may in fact produce shorter execution time for a task executed on such platforms. It is hence necessary to select the input data that induce high execution times in this context, to provide reliable WCET estimates. In this work, we performed an assessment of the execution times of real-time tasks with respect to the input data, i.e., (1) verifying the sensitivity of the task execution times to the input data used, and (2) the quantitative assessment of their impact on the resulting execution times. Tasks that are sensitive to input data require input data that maximizes the execution time being searched in order to obtain reliable pWCETs. In order to select input data for performing MBPTA on complex architectures, one possible approach for finding the worst-case input data of a task with respect to its execution time is by employing optimization algorithms, e.g., a genetic algorithm. However, the large timing variability observed on complex architectures hinders the comparison of execution time measurements obtained using different input data. In this context, we (1) performed an assessment of different measurement methods, (2) implemented a genetic algorithm in which the fitness function is based on execution time measurements selected using both traditional and novel methods, and (3) estimated probabilistic WCET bounds for a task, using the worst input data obtained through the developed genetic algorithm. We highlight that the proposed work is justified by its scientific relevance and by the potential positive economic impact arising from methods for the determination of WCET estimates