Эта публикация цитируется в 4 статьях

Критерий существования бесконфликтного расписания для системы строго периодических задач

С. А. Зеленова^a, С. В. Зеленов<sup>ab

a</sup> Институт системного программирования им. В.П. Иванникова РАН
^b Национальный исследовательский университет Высшая школа экономики

Аннотация: В критических системах выполнение жестких требований по времени взаимодействия между задачами обеспечивается строгой периодичностью запуска задач, когда каждая задача стартует через равные промежутки времени. При планировании строго периодических задач с прерываниями наиболее трудным этапом является выбор начальных стартовых точек задач. В настоящей работе предлагается новый подход к анализу расписаний, основанный на изучении раскрасок графов периодов задач и на решении систем линейных сравнений. Основным результатом является критерий существования бесконфликтного расписания для произвольного количества строго периодических задач с прерываниями на одном процессоре. Критерий позволяет либо направленно найти стартовые точки, либо быстро установить, что расписание построить невозможно.

Ключевые слова: системы реального времени, строго периодическая задача, планирование, раскраска графа, система линейных сравнений.

DOI: 10.15514/ISPRAS-2017-29(6)-10

Реферативные базы данных:

•