Дослідження граничних часових показників програмних середовищ операційних систем реального часу
Loading...
Files
Date
2018
Journal Title
Journal ISSN
Volume Title
Publisher
Дніпропетровський національний університет залізничного транспорту ім. акад. В. Лазаряна, Дніпро
Abstract
UKR: Мета. Більш ніж двадцятирічний термін дослідження оцінки найгіршого часу виконання програм (Worst Case Execution Time, WCET) призвів до розробки багатьох методів. До цього часу немає остаточних висновків щодо застосування того чи іншого методу. Тому метою нашої роботи є визначення можливості використання гібридного методу для оцінки WCET у системах реального часу. Методика. З’ясування оцінки WCET для гібридного методу полягає в тому, щоб провести синтаксичний аналіз вхідного коду мовою програмування С++ та, побудувавши граф потоку керування, отримати час виконання його базових блоків. Знайшовши найдовший шлях графа, оцінити час виконання цього шляху й отримати оцінку WCET. Для пошуку найдовшого за часом виконання шляху був обраний зворотний алгоритм Дейкстри. Після чого було виконане порівняння граничних часових оцінок, отриманих статичним і гібридним методами, а також аналіз розбіжності цих результатів. Результати. Визначення найгіршого часу виконання програм найбільш важливе для задач «жорсткого реального часу». Недооцінка цього показника може призвести до катастрофічних наслідків. А переоцінка – до суттєвої перевитрати ресурсів. Тому була проведена оцінка WCET за допомогою статичного й динамічного методів, яка дає змогу визначити, що результати, отримані двома методами, непогано корелюються. Для розглянутого класу задач час виконання WCET може бути визначений за допомогою гібридного методу. Додавання додаткового часу в розмірі 15–20 % до результатів, отриманих гібридним методом, дозволяє отримати безпечну оцінку WCET у системах реального часу. Наукова новизна. Гібридний метод існує вже певний час, але надійність його використання ще не була достатньо вивчена. Дане дослідження робить крок у визначенні практичної застосованості гібридного методу для часової оцінки задач реального часу. Практична значимість. Результати дослідження дозволяють дійти висновків, що гібридний метод може бути використаний для отримання оцінки WCET у задачах «жорсткого реального часу». А деякий невідомий на даний момент вплив середовища операційної системи реального часу (ОС РЧ) може бути врахований додаванням додаткового часу.
RUS: Цель. Более чем двадцатилетний срок исследования оценки наихудшего времени выполнения программ (Worst Case Execution Time, WCET) привел к разработке многих методов. До сих пор нет окончательных выводов относительно применения того или иного метода. Поэтому целью нашей работы является определение возможности использования гибридного метода для оценки WCET в системах реального времени. Методика. Выяснение оценки WCET для гибридного метода заключается в том, чтобы провести синтаксический анализ на языке программирования С++ и, построив граф потока управления, получить время выполнения его базовых блоков. Найдя самый длинный путь графа, оценить время выполнения этого пути и получить оценку WCET. Для поиска самого длинного по времени выполнения пути был выбран обратный алгоритм Дейкстры. После чего было выполнено сравнение предельных временных оценок, полученных статическим и гибридным методами, а также анализ расхождения этих результатов. Результаты. Определение худшего времени выполнения программ наиболее важно для задач «жесткого реального времени». Недооценка этого показателя может привести к катастрофическим последствиям. А переоценка – к существенному перерасходу ресурсов. Поэтому была проведена оценка WCET с помощью статического и динамического методов, которая дала возможность определить, что результаты, полученные двумя методами, неплохо коррелируют. Для рассматриваемого класса задач время выполнения WCET может быть определено с помощью гибридного метода. Добавление дополнительного времени в размере 15–20 % к результатам, полученным гибридным методом, позволяет получить безопасную оценку WCET в системах реального времени. Научная новизна. Гибридный метод существует уже некоторое время, но надежность его использования еще не была достаточно изучена. Данное исследование делает шаг в определении практической применимости гибридного метода для временной оценки задач реального времени. Практическая значимость. Результаты исследования позволяют сделать выводы, что гибридный метод может быть использован для получения WCET в задачах «жесткого реального времени». А некоторое неизвестное на данный момент влияние среды операционных систем реального времени (ОС РВ) может быть учтено добавлением дополнительного времени.
ENG: Purpose. More than 20 years of the Worst Case Execution Time (WCET) studies have led to the development of many methods for its evaluation. So far, there are no definitive conclusions about usage of these methods. There-fore, the purpose of this paper is to determine the possibility of using a hybrid method for estimating WCET in real-time systems. Methodology. The approach for evaluating WCET for a hybrid method is to parse the input code in the C++ programming language and, after constructing the control flow graph, get the execution time of its base blocks. After finding the longest way of the graph, to estimate the time of execution of this way and get the WCET evaluation. To find the longest-running way, the reverse Dijkstra algorithm was chosen. After that, there was made a comparison of the limiting time estimations that were obtained by static and hybrid methods, as well as an analysis of the discrepancy between these results. Findings. Determining the worst execution time of programs is most im-portant for «hard real-time» tasks. Underestimation of this indicator can lead to catastrophic consequences. An over-estimation – to a significant overexpenditure of resources. Therefore, WCET was evaluated using static and dynam-ic methods. It was determined that the results obtained by the two methods correlate well. For the class of tasks that are under consideration, WCET execution time can be determined using a hybrid method. Adding an extra time of 15–20 % to the results, obtained by the hybrid method, allows getting a foolproof estimate of WCET in real-time systems. Originality. The hybrid method has been existing for some time, but the reliability of its use has not been sufficiently studied yet. The given study makes a step in determining the practical applicability of the hybrid method for time estimation of real-time tasks. Practical value. The results of this research allow us to conclude that a hybrid method could be used for obtaining WCET in "hard real-time" tasks. Furthermore, some unknown at this moment influence of the OS RT environment can be taken into account by adding extra time.
RUS: Цель. Более чем двадцатилетний срок исследования оценки наихудшего времени выполнения программ (Worst Case Execution Time, WCET) привел к разработке многих методов. До сих пор нет окончательных выводов относительно применения того или иного метода. Поэтому целью нашей работы является определение возможности использования гибридного метода для оценки WCET в системах реального времени. Методика. Выяснение оценки WCET для гибридного метода заключается в том, чтобы провести синтаксический анализ на языке программирования С++ и, построив граф потока управления, получить время выполнения его базовых блоков. Найдя самый длинный путь графа, оценить время выполнения этого пути и получить оценку WCET. Для поиска самого длинного по времени выполнения пути был выбран обратный алгоритм Дейкстры. После чего было выполнено сравнение предельных временных оценок, полученных статическим и гибридным методами, а также анализ расхождения этих результатов. Результаты. Определение худшего времени выполнения программ наиболее важно для задач «жесткого реального времени». Недооценка этого показателя может привести к катастрофическим последствиям. А переоценка – к существенному перерасходу ресурсов. Поэтому была проведена оценка WCET с помощью статического и динамического методов, которая дала возможность определить, что результаты, полученные двумя методами, неплохо коррелируют. Для рассматриваемого класса задач время выполнения WCET может быть определено с помощью гибридного метода. Добавление дополнительного времени в размере 15–20 % к результатам, полученным гибридным методом, позволяет получить безопасную оценку WCET в системах реального времени. Научная новизна. Гибридный метод существует уже некоторое время, но надежность его использования еще не была достаточно изучена. Данное исследование делает шаг в определении практической применимости гибридного метода для временной оценки задач реального времени. Практическая значимость. Результаты исследования позволяют сделать выводы, что гибридный метод может быть использован для получения WCET в задачах «жесткого реального времени». А некоторое неизвестное на данный момент влияние среды операционных систем реального времени (ОС РВ) может быть учтено добавлением дополнительного времени.
ENG: Purpose. More than 20 years of the Worst Case Execution Time (WCET) studies have led to the development of many methods for its evaluation. So far, there are no definitive conclusions about usage of these methods. There-fore, the purpose of this paper is to determine the possibility of using a hybrid method for estimating WCET in real-time systems. Methodology. The approach for evaluating WCET for a hybrid method is to parse the input code in the C++ programming language and, after constructing the control flow graph, get the execution time of its base blocks. After finding the longest way of the graph, to estimate the time of execution of this way and get the WCET evaluation. To find the longest-running way, the reverse Dijkstra algorithm was chosen. After that, there was made a comparison of the limiting time estimations that were obtained by static and hybrid methods, as well as an analysis of the discrepancy between these results. Findings. Determining the worst execution time of programs is most im-portant for «hard real-time» tasks. Underestimation of this indicator can lead to catastrophic consequences. An over-estimation – to a significant overexpenditure of resources. Therefore, WCET was evaluated using static and dynam-ic methods. It was determined that the results obtained by the two methods correlate well. For the class of tasks that are under consideration, WCET execution time can be determined using a hybrid method. Adding an extra time of 15–20 % to the results, obtained by the hybrid method, allows getting a foolproof estimate of WCET in real-time systems. Originality. The hybrid method has been existing for some time, but the reliability of its use has not been sufficiently studied yet. The given study makes a step in determining the practical applicability of the hybrid method for time estimation of real-time tasks. Practical value. The results of this research allow us to conclude that a hybrid method could be used for obtaining WCET in "hard real-time" tasks. Furthermore, some unknown at this moment influence of the OS RT environment can be taken into account by adding extra time.
Description
В. Нечай: ORCID 0000-0001-5358-4335; Д. Волошин: ORCID 0000-0003-1250-3206; О. Нежуміра: ORCID 0000-0002-3905-2591
Keywords
граничний час виконання програм, WCET, операційні системи реального часу, задачі реального часу, гібридний метод, статичний метод, динамічний метод, предельное время выполнения программ, операционные системы реального времени, задачи реального времени, гибридный метод, статический метод, динамический метод, worst case execution time, real-time operating systems, real-time tasks, hybrid method, static method, dynamic method, КІТ
Citation
Нечай, В. Я. Дослідження граничних часових показників програмних середовищ операційних систем реального часу / В. Я. Нечай, Д. О. Волошин, О. І. Нежуміра // Наука та прогрес транспорту. – 2018. – № 3 (75). – С. 105–112. – DOI: 10.15802/stp2018/133384.