maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2020-2-218-233mais-1326Research ArticleAlgorithmsАлгоритм оценки максимального времени отклика задач в многопроцессорных системах с интервальной неопределенностью длительности выполнения работResearch and Development of an Algorithm for the Response Time Estimation in Multiprocessor Systems Under the Interval Uncertainty of the Tasks Execution Timeshttps://orcid.org/0000-0002-0670-8603ГонопольскийМарк ГеннадьевичGonopolskiyMark G.

студент

Ленинские горы, д. 1, г. Москва, 119991

student

1 Leninskie Gory, Moscow 119991

gmarkmgw@yandex.ruhttps://orcid.org/0000-0001-8716-4128ГлонинаАлевтина БорисовнаGloninaAlevtina B.

программист

Ленинские горы, д. 1, г. Москва, 119991

programmer

1 Leninskie Gory, Moscow 119991

alevtina@lvk.cs.msu.suМосковский государственный университет им. М. В. ЛомоносоваРоссияLomonosov Moscow State UniversityRussian Federation202024062020272218233Copyright © Гонопольский М.Г., Глонина А.Б., 20202020Гонопольский М.Г., Глонина А.Б.Gonopolskiy M.G., Glonina A.B.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1326

В данной статье предложен алгоритм оценки максимального времени отклика задач (Worst Case Response Time — WCRT) в многопроцессорных системах с планировщиками с приоритетом и вытеснением и интервальной неопределенностью длительности выполнения работ. Между задачами имеются зависимости по данным. Для каждой задачи задан приоритет, период и интервал [BCET, WCET], которому принадлежит время выполнения на процессоре работ этой задачи. Если уменьшение времени выполнения задачи A может привести к увеличению времени отклика задачи B, то задача A называется аномальной задачей для задачи B. Согласно выбранному авторами подходу, для получения оценки WCRT некоторой задачи необходимо выполнить два шага. На первом шаге с помощью предложенного в работе алгоритма осуществляется построение множества задач, аномальных для заданной задачи. Приведено доказательство корректности этого алгоритма. На втором шаге с помощью генетического алгоритма выполняется поиск WCRT. Пространство поиска — множество всевозможных наборов длительностей выполнения аномальных задач. Было разработано инструментальное средство на языке Python3, реализующее предложенный подход. Проведено экспериментальное исследование, в ходе которого предложенный метод сравнивался по точности и скорости с двумя известными методами оценки WCRT: методом, не учитывающим интервальную неопределенность, т.е. предполагающим, что время выполнения всех работ равно WCET, а также с переборным методом. Экспериментальное исследование показало, что в отличие от переборного метода, предложенный метод применим для анализа вычислительных систем реальной размерности, а также позволяет достичь большей точности, чем метод, не учитывающий интервальную неопределенность.

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.

генетический алгоритммногопроцессорные системынаихудшее время откликаанализ времени откликааномалии планированияпланирование вычисленийgenetic algorithmmultiprocessor systemsworst-case response timesresponse time analysisscheduling anomaliesschedulingРабота выполнена при финансовой поддержке РФФИ (грант № 19–07–00614).This work was supported by RFBR (grant No 19–07–00614).ReferencesN. Holsti, T. Langbacka, and S. Saarinen, “Using a Worst-Case Execution Time Tool for Real-Time Verification of the DEBIE Software”, EUROPEAN SPACE AGENCY-PUBLICATIONS-ESA SP, vol. 457, pp. 307–312, 2000.N. Holsti, T. Langbacka, and S. Saarinen, “Using a Worst-Case Execution Time Tool for Real-Time Verification of the DEBIE Software”, EUROPEAN SPACE AGENCY-PUBLICATIONS-ESA SP, vol. 457, pp. 307–312, 2000.C. Liu and J. H. Anderson, “Task Scheduling with Self-Suspensions in Soft Real-Time Multiprocessor Systems”, in 2009 30th IEEE Real-Time Systems Symposium, 2009, pp. 425–436.C. Liu and J. H. Anderson, “Task Scheduling with Self-Suspensions in Soft Real-Time Multiprocessor Systems”, in 2009 30th IEEE Real-Time Systems Symposium, 2009, pp. 425–436.J. C. P. Gutierrez, J. J. G. Garcia, and M. G. Harbour, “Best-Case Analysis for Improving the Worst-Case Schedulability Test for Distributed Hard Real-Time Systems”, in Proceedings of 10th EUROMICRO Workshop on Real-Time Systems, 1998, pp. 35–44.J. C. P. Gutierrez, J. J. G. Garcia, and M. G. Harbour, “Best-Case Analysis for Improving the Worst-Case Schedulability Test for Distributed Hard Real-Time Systems”, in Proceedings of 10th EUROMICRO Workshop on Real-Time Systems, 1998, pp. 35–44.C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”, Journal of the ACM (JACM), vol. 20, no. 1, pp. 46–61, 1973.C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”, Journal of the ACM (JACM), vol. 20, no. 1, pp. 46–61, 1973.J. Kim and et al., “An ILP-Based Worst-Case Performance Analysis Technique for Distributed Real-Time Embedded Systems”, in Proceedings of IEEE 33rd Real-Time Systems Symposium, 2012, pp. 363–372.J. Kim and et al., “An ILP-Based Worst-Case Performance Analysis Technique for Distributed Real-Time Embedded Systems”, in Proceedings of IEEE 33rd Real-Time Systems Symposium, 2012, pp. 363–372.R. Wilhelm, “Why AI+ ILP is Good for WCET, but MC is not, nor ILP Alone”, in International Workshop on Verification, Model Checking, and Abstract Interpretation, 2004, pp. 309–322.R. Wilhelm, “Why AI+ ILP is Good for WCET, but MC is not, nor ILP Alone”, in International Workshop on Verification, Model Checking, and Abstract Interpretation, 2004, pp. 309–322.A. Brekling, M. R. Hansen, and J. Madsen, “Models and Formal Verification of Multiprocessor System-on-Chips”, The Journal of Logic and Algebraic Programming, vol. 77, no. 1-2, pp. 1–19, 2008.A. Brekling, M. R. Hansen, and J. Madsen, “Models and Formal Verification of Multiprocessor System-on-Chips”, The Journal of Logic and Algebraic Programming, vol. 77, no. 1-2, pp. 1–19, 2008.J. Kany and S. Madsen, “Design Optimisation of Fault-Tolerant Event-Triggered Embedded Systems”, PhD thesis, Doctoral dissertation, Master’s thesis, Tech. Univ. of Denmark, Lyngby, Denmark, 2007, 176 pp.J. Kany and S. Madsen, “Design Optimisation of Fault-Tolerant Event-Triggered Embedded Systems”, PhD thesis, Doctoral dissertation, Master’s thesis, Tech. Univ. of Denmark, Lyngby, Denmark, 2007, 176 pp.J. Kim and et al., “A Novel Analytical Method for Worst Case Response Time Estimation of Distributed Embedded Systems”, in Proceedings of 50th ACM/EDAC/IEEE Design Automation Conference (DAC), 2013, pp. 1–10.J. Kim and et al., “A Novel Analytical Method for Worst Case Response Time Estimation of Distributed Embedded Systems”, in Proceedings of 50th ACM/EDAC/IEEE Design Automation Conference (DAC), 2013, pp. 1–10.K. Tindell and J. Clark, “Holistic Schedulability Analysis for Distributed Hard Real-Time Systems”, Microprocessing and microprogramming, vol. 40, no. 2-3, pp. 117–134, 1994.K. Tindell and J. Clark, “Holistic Schedulability Analysis for Distributed Hard Real-Time Systems”, Microprocessing and microprogramming, vol. 40, no. 2-3, pp. 117–134, 1994.R. I. Davis and et al., “Controller Area Network (CAN) Schedulability Analysis: Refuted, Revisited and Revised”, Real-Time Systems, vol. 35, no. 3, pp. 239–272, 2007.R. I. Davis and et al., “Controller Area Network (CAN) Schedulability Analysis: Refuted, Revisited and Revised”, Real-Time Systems, vol. 35, no. 3, pp. 239–272, 2007.J. C. Palencia and M. G. Harbour, “Schedulability Analysis for Tasks with Static and Dynamic Offsets”, in Proceedings 19th IEEE Real-Time Systems Symposium, 1998, pp. 26–37.J. C. Palencia and M. G. Harbour, “Schedulability Analysis for Tasks with Static and Dynamic Offsets”, in Proceedings 19th IEEE Real-Time Systems Symposium, 1998, pp. 26–37.O. Redell, “Analysis of Tree-Shaped Transactions in Distributed Real-Time Systems”, in Proceedings of 16th Euromicro Conference on Real-Time Systems, 2004, pp. 239–248.O. Redell, “Analysis of Tree-Shaped Transactions in Distributed Real-Time Systems”, in Proceedings of 16th Euromicro Conference on Real-Time Systems, 2004, pp. 239–248.S. Samii, S. Rafiliu, P. Eles, and Z. Peng, “A Simulation Methodology for Worst-Case Response Time Estimation of Distributed Real-Time Systems”, in Proceedings of the Conference on Design, Automation and Test in Europe, 2008, pp. 556–561.S. Samii, S. Rafiliu, P. Eles, and Z. Peng, “A Simulation Methodology for Worst-Case Response Time Estimation of Distributed Real-Time Systems”, in Proceedings of the Conference on Design, Automation and Test in Europe, 2008, pp. 556–561.R. Racu and R. Ernst, “Scheduling Anomaly Detection and Optimization for Distributed Systems with Preemptive Task-Sets”, in 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’06), 2006, pp. 325–334.R. Racu and R. Ernst, “Scheduling Anomaly Detection and Optimization for Distributed Systems with Preemptive Task-Sets”, in 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’06), 2006, pp. 325–334.V. M. Kureychik, Geneticheskiye algoritmy i ih primeneniye. Taganrog: Izd-vo TRTU, 2002, 244 pp.V. M. Kureychik, Geneticheskiye algoritmy i ih primeneniye. Taganrog: Izd-vo TRTU, 2002, 244 pp.A.B. Glonina,“Programmnoye sredstvo modelirovaniya modulnyh vychislitelnih sistem dlya proverki dopustimosti ih konfguratsiy”, Programmniye produkty i sistemy, vol. 30, no. 4, pp. 574–582, 2017.A.B. Glonina,“Programmnoye sredstvo modelirovaniya modulnyh vychislitelnih sistem dlya proverki dopustimosti ih konfguratsiy”, Programmniye produkty i sistemy, vol. 30, no. 4, pp. 574–582, 2017.

The authors declare that there are no conflicts of interest present.