81365

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Планирование вычислений в системах реального времени: эффективные алгоритмы построения оптимальных расписаний

Электронная публикация: 

Да

ISBN/ISSN: 

0236-235X

DOI: 

10.15827/0236-235X.149.055-064

Наименование источника: 

  • Программные продукты и системы

Обозначение и номер тома: 

Т. 38, № 1

Город: 

  • Тверь

Издательство: 

  • Центрпрограммсистем

Год издания: 

2025

Страницы: 

55-64
Аннотация
В статье рассматриваются вопросы, связанные с разработкой одного из основных блоков вычислительной системы реального времени – блока планирования вычислений. Предлагаются алгоритмы построения оптимальных расписаний для различных случаев в зависимости от числа процессоров и характеристик работ и ресурсов вычислительной системы. Для однопроцессорного случая с прерываниями и директивными интервалами усовершенствован алгоритм относительной срочности путем использования кучи для хранения данных. Это способствовало понижению вычислительной сложности алгоритма. Разработан алгоритм для задачи с частичным порядком выполнения работ, основанный на предварительной коррекции моментов готовности и директивных сроков и на сведении исходной задачи к задаче без отношений предшествования. Для многопроцессорного случая с прерываниями и директивными интервалами предложен приближенный алгоритм, основанный на обобщении однопроцессорного алгоритма относительной срочности на случай нескольких процессоров. Проведен сравнительный анализ с точным потоковым алгоритмом. Доказано, что в случае учета временных издержек на прерывания и переключения задача является NP-трудной. Для многопроцессорного случая без прерываний и переключений с общим директивным интервалом для всех работ и идентичными процессорами разработан псевдополиномиальный алгоритм, основанный на ограниченном переборе вариантов. Создан приближенный алгоритм для системы с возобновляемыми и невозобновляемыми ресурсами, а также для комплекса со смешанным набором работ (как непрерываемых, так и допускающих прерывания и переключения). Алгоритм основан на сетевом моделировании и сведении исследуемой задачи к поиску потока с определенными свойствами в специальной сети

Библиографическая ссылка: 

Кононов Д.А., Фуругян М.Г. Планирование вычислений в системах реального времени: эффективные алгоритмы построения оптимальных расписаний // Программные продукты и системы. 2025. Т. 38, № 1. С. 55-64.