Труды Института системного программирования РАН (Oct 2018)

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

  • S. A. Zelenova,
  • S. V. Zelenov

DOI
https://doi.org/10.15514/ispras-2017-29(6)-10
Journal volume & issue
Vol. 29, no. 6
pp. 183 – 202

Abstract

Read online

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

Keywords