Критерий существования бесконфликтного расписания для системы строго периодических задач
https://doi.org/10.15514/ISPRAS-2017-29(6)-10
Аннотация
В критических системах выполнение жестких требований по времени взаимодействия между задачами обеспечивается строгой периодичностью запуска задач, когда каждая задача стартует через равные промежутки времени. При планировании строго периодических задач с прерываниями наиболее трудным этапом является выбор начальных стартовых точек задач. В настоящей работе предлагается новый подход к анализу расписаний, основанный на изучении раскрасок графов периодов задач и на решении систем линейных сравнений. Основным результатом является критерий существования бесконфликтного расписания для произвольного количества строго периодических задач с прерываниями на одном процессоре. Критерий позволяет либо направленно найти стартовые точки, либо быстро установить, что расписание построить невозможно.
Об авторах
С. А. Зеленова
Институт системного программирования им. В.П. Иванникова РАН
Россия
Россия
С. В. Зеленов
Институт системного программирования им. В.П. Иванникова РАН; Национальный исследовательский университет Высшая школа экономики
Россия
Россия
Список литературы
1. Зыков А.А. Основы теории графов. М: Вузовская книга, 2004.
2. Кристофидес Н. Теория графов. Алгоритмический подход. М: Мир, 1978.
3. Оре О. Теория графов. М: Наука, 1980.
4. Виноградов И.М. Основы теории чисел. М.-Л.: Гостехиздат, 1952.
5. Зеленов С.В. Планирование строго периодических задач в системах реального времени. Труды ИСП РАН, том 20, 2011 г., с. 113-122.
6. Третьяков А. Автоматизация построения расписаний для периодических систем реального времени. Труды ИСП РАН, том 22, 2012 г., стр. 375-400. DOI: 10.15514/ISPRAS-2012-22-20.
7. Kermia O., Sorel Y. Schedulability Analysis for Non-Preemptive Tasks under Strict Periodicity Constraints. Proceedings of the 2008 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2008, p. 25-32.
8. Liu C.L., Layland J.W. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. J. ACM, 1973, No 20, p. 46-61.
9. Liu J.W.S.W. Real-Time Systems. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1st edn. 2000.
10. Marouf M., Sorel Y. Schedulability conditions for non-preemptive hard real-time tasks with strict period. Proceedings of 18th International Conference on Real-Time and Network Systems, RTNS'10, 2010, p. 50-58.
11. Yomsi P.M., Sorel Y. Non-Schedulability Conditions for Off-line Scheduling of Real-Time Systems Subject to Precedence and Strict Periodicity Constraints. Proceedings of 11th IEEE International Conference on Emerging technologies and Factory Automation, ETFA'06, WIP, Prague, Czech Republic, September 2006.
12. Yomsi P.M., Sorel Y. Schedulability Analysis for non Necessarily Harmonic Real-Time Systems with Precedence and Strict Periodicity Constraints using the Exact Number of Preemptions and no Idle Time. Proceedings of the 4th Multidisciplinary International Scheduling Conference, MISTA'09, Dublin, Ireland, August, 2009.
Рецензия
Для цитирования:
Зеленова С.А., Зеленов С.В. Критерий существования бесконфликтного расписания для системы строго периодических задач. Труды Института системного программирования РАН. 2017;29(6):183-202. https://doi.org/10.15514/ISPRAS-2017-29(6)-10
Послать статью по эл. почте 