Сборники трудов ИСП РАН


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

Зеленова С.А. (ИСП РАН, Москва, Россия)
Зеленов С.В. (ИСП РАН, Москва, Россия; ВШЭ, Москва, Россия)

Аннотация

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

Ключевые слова

системы реального времени; строго периодическая задача; планирование; раскраска графа; система линейных сравнений

Издание

Труды Института системного программирования РАН, том 29, вып. 6, 2017, стр. 183-202.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

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

Полный текст статьи в формате pdf Вернуться к содержанию тома