Creation of a Multiprocessor Schedules in Real-Time System with Communication Restrictions Between Processors
Abstract
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.
References
1. В.С. Танаев, В.С. Гордон,Я.М. Шафранский. Теория расписаний. Одностадийные системы. М.: Наука, 1984, 383 с.
2. P. Brucker. Scheduling Algorithms. Heidelberg: Springer, 2007, 378 с.
3. А.А. Лазарев. Теория расписаний. Оценка абсолютной погрешности и схема приближенного решения задач теории расписаний. М.: МФТИ, 2008, 222 с.
4. А.В. Мищенко, П.С. Кошелев. Оптимизация управления работами логистического проекта в условиях неопределенности. «Изв. РАН. ТиСУ», (2021), № 4, 86 – 101.
5. А.Б. Глонина, В.В. Балашов. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов. «Моделирование и анализ информационных систем», Т. 25 (2018), № 2, 174 – 192.
6. А.Б. Глонина. Обобщенная модель функционирования модульных вычислительных систем реального времени для проверки допустимости конфигураций таких систем. «Вестник ЮУрГУ. Сер. Вычисл. математика и информатика», Т. 6 (2017), № 4, 43 – 59.
7. А.Б. Глонина. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем. «Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика», (2020), № 3, 16 – 29.
8. Д.В. Алифанов, В.Н. Лебедев, В.И. Цурков. Оптимизация расписаний с логическими условиями предшествования. «Изв. РАН. ТиСУ», (2009), № 6, 88 – 93.
9. В.А. Костенко, А.С. Смирнов. Алгоритм построения однопроцессорных статико-динамическихрасписаний. «Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика», (2018), № 1, 45 52
10. В.А. Костенко. Алгоритмы комбинаторной оптимизации, сочетающие жадные стратегии и ограниченный перебор. «Изв. РАН. ТиСУ», (2017), № 2, 48 56.
Review
For citations:
Furugyan M. Creation of a Multiprocessor Schedules in Real-Time System with Communication Restrictions Between Processors. SRISA Proceedings. 2022;12(1-2):28-31. (In Russ.)
Views:
14
Email this article 