trudyniisiТруды НИИСИSRISA Proceedings2225-73493033-6422НИЦ «КУРЧАТОВСКИЙ ИНСТИТУТ» - НИИСИtrudyniisi-28Research ArticleСтатьиСоставление многопроцессорного расписания в системе реального времени с ограничениями на связи между процессорамиCreation of a Multiprocessor Schedules in Real-Time System with Communication Restrictions Between ProcessorsФуругянМ. Г.FurugyanM.

Москва

rtsccas@yandex.ruФИЦ ИУ РАНРоссия202215102025121-22831Copyright © Фуругян М.Г., 20252025Фуругян М.Г.Furugyan M.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.t-niisi.ru/jour/article/view/28

Рассматривается задача построения допустимого расписания комплекса программных модулей в многопроцессорной системе реального времени с неполным графом связей между процессорами. Заданы длительности выполнения модулей и их директивные интервалы. При выполнении модулей допускаются прерывания и переключения с одного процессора на другой с учетом ограничений на связи между процессорами и на число переключений в фиксированный момент времени. Параллельное выполнение нескольких модулей одним процессором и одного модуля несколькими процессорами не допускается. Решение задачи основано на ее сведении к многопродуктовой потоковой задаче в сети.

The problem of constructing an admissible schedule for a complex of program modules in a multiprocessor real-time system with an incomplete graph of connections between processors is considered. The duration of the modules execution and their directive intervals are set. When executing modules, interrupts and switching from one processor to another are allowed, taking into account the restrictions on communications between processors and on the number of switches at a fixed point in time. Parallel execution of several modules by one processor and one module by several processors is not allowed. The solution of the problem is based on its reduction to a multicommodity flow problem in the network.

многопроцессорная системадопустимое расписаниедирективный интервалмногопродуктовый поток в сетилинейная система булевых соотношенийmultiprocessor systemadmissible scheduledirective intervalmultiproduct flow in the networklinear system of Boolean relationsReferencesВ.С. Танаев, В.С. Гордон,Я.М. Шафранский. Теория расписаний. Одностадийные системы. М.: Наука, 1984, 383 с.В.С. Танаев, В.С. Гордон,Я.М. Шафранский. Теория расписаний. Одностадийные системы. М.: Наука, 1984, 383 с.P. Brucker. Scheduling Algorithms. Heidelberg: Springer, 2007, 378 с.P. Brucker. Scheduling Algorithms. Heidelberg: Springer, 2007, 378 с.А.А. Лазарев. Теория расписаний. Оценка абсолютной погрешности и схема приближенного решения задач теории расписаний. М.: МФТИ, 2008, 222 с.А.А. Лазарев. Теория расписаний. Оценка абсолютной погрешности и схема приближенного решения задач теории расписаний. М.: МФТИ, 2008, 222 с.А.В. Мищенко, П.С. Кошелев. Оптимизация управления работами логистического проекта в условиях неопределенности. «Изв. РАН. ТиСУ», (2021), № 4, 86 – 101.А.В. Мищенко, П.С. Кошелев. Оптимизация управления работами логистического проекта в условиях неопределенности. «Изв. РАН. ТиСУ», (2021), № 4, 86 – 101.А.Б. Глонина, В.В. Балашов. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов. «Моделирование и анализ информационных систем», Т. 25 (2018), № 2, 174 – 192.А.Б. Глонина, В.В. Балашов. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов. «Моделирование и анализ информационных систем», Т. 25 (2018), № 2, 174 – 192.А.Б. Глонина. Обобщенная модель функционирования модульных вычислительных систем реального времени для проверки допустимости конфигураций таких систем. «Вестник ЮУрГУ. Сер. Вычисл. математика и информатика», Т. 6 (2017), № 4, 43 – 59.А.Б. Глонина. Обобщенная модель функционирования модульных вычислительных систем реального времени для проверки допустимости конфигураций таких систем. «Вестник ЮУрГУ. Сер. Вычисл. математика и информатика», Т. 6 (2017), № 4, 43 – 59.А.Б. Глонина. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем. «Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика», (2020), № 3, 16 – 29.А.Б. Глонина. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем. «Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика», (2020), № 3, 16 – 29.Д.В. Алифанов, В.Н. Лебедев, В.И. Цурков. Оптимизация расписаний с логическими условиями предшествования. «Изв. РАН. ТиСУ», (2009), № 6, 88 – 93.Д.В. Алифанов, В.Н. Лебедев, В.И. Цурков. Оптимизация расписаний с логическими условиями предшествования. «Изв. РАН. ТиСУ», (2009), № 6, 88 – 93.В.А. Костенко, А.С. Смирнов. Алгоритм построения однопроцессорных статико-динамическихрасписаний. «Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика», (2018), № 1, 45 52В.А. Костенко, А.С. Смирнов. Алгоритм построения однопроцессорных статико-динамическихрасписаний. «Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика», (2018), № 1, 45 52В.А. Костенко. Алгоритмы комбинаторной оптимизации, сочетающие жадные стратегии и ограниченный перебор. «Изв. РАН. ТиСУ», (2017), № 2, 48 56.В.А. Костенко. Алгоритмы комбинаторной оптимизации, сочетающие жадные стратегии и ограниченный перебор. «Изв. РАН. ТиСУ», (2017), № 2, 48 56.

The authors declare that there are no conflicts of interest present.