Research and Development of an Algorithm for the Response Time Estimation in Multiprocessor Systems Under the Interval Uncertainty of the Tasks Execution Times
Open Access
- 24 June 2020
- journal article
- Published by P.G. Demidov Yaroslavl State University in Modeling and Analysis of Information Systems
- Vol. 27 (2), 218-233
- https://doi.org/10.18255/1818-1015-2020-2-218-233
Abstract
The paper presents an algorithm for the worst case response time (WCRT) estimation for multiprocessor systems with fixed-priority preemptive schedulers and the interval uncertainty of tasks execution times. Each task has a unique priority within its processor, a period, an execution time interval [BCET, WCET] and can have data dependency on other tasks. If a decrease in the execution time of the task A can lead to an increase in the response time of the another task B, then task A is called an anomalous task for task B. According to the chosen approach, in order to estimate a task’s WCRT, two steps should be performed. The first one is to construct a set of anomalous tasks using the proposed algorithm for the given task. The paper provides the algorithm and the proof of its correctness. The second one is to find the WCRT estimation using a genetic algorithm. The proposed approach has been implemented software as a program in Python3. A set of experiments have been carried out in order to compare the proposed method in terms of precision and speed with two well-known WCRT estimating methods: the method that does not take into account interval uncertainty (assuming that the execution time of a given task is equal to WCET) and the brute force method. The results of the experiments have shown that, in contrast to the brute force method, the proposed method is applicable to the analysis of the real scale computing systems and also allows to achieve greater precision than the method that does not take into account interval uncertainty.Keywords
This publication has 10 references indexed in Scilit:
- Программное средство моделирования модульных вычислительных систем для проверки допустимости их конфигурацийМеждународный журнал "Программные продукты и системы", 2017
- A novel analytical method for worst case response time estimation of distributed embedded systemsPublished by Association for Computing Machinery (ACM) ,2013
- An ILP-based Worst-case Performance Analysis Technique for Distributed Real-time Embedded SystemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Task Scheduling with Self-Suspensions in Soft Real-Time Multiprocessor SystemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- Models and formal verification of multiprocessor system-on-chipsThe Journal of Logic and Algebraic Programming, 2008
- A simulation methodology for worst-case response time estimation of distributed real-time systemsPublished by Association for Computing Machinery (ACM) ,2008
- Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revisedReal-Time Systems, 2007
- Why AI + ILP Is Good for WCET, but MC Is Not, Nor ILP AloneLecture Notes in Computer Science, 2004
- Holistic schedulability analysis for distributed hard real-time systemsMicroprocessing and Microprogramming, 1994
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973