trudyniisiТруды НИИСИSRISA Proceedings2225-73493033-6422НИЦ «КУРЧАТОВСКИЙ ИНСТИТУТ» - НИИСИtrudyniisi-77Research ArticleМОДЕЛИРОВАНИЕ МНОГОПРОЦЕССОРНЫХ СИСТЕМMODELING OF MULTIPROCESSOR SYSTEMSОбобщение задачи составления многопроцессорного расписания с прерываниямиGeneralization of the Problem of Creating a Multiprocessor Schedule with InterruptsФуругянМ. Г.FurugyanM.

Москва

rtsccas@yandex.ruФИЦ ИУ РАНРоссия202406122025142МАТЕМАТИЧЕСКОЕ И КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ СЛОЖНЫХ СИСТЕМ: ТЕОРЕТИЧЕСКИЕ И ПРИКЛАДНЫЕ АСПЕКТЫ1014Copyright © Фуругян М.Г., 20252025Фуругян М.Г.Furugyan M.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.t-niisi.ru/jour/article/view/77

Рассматривается задача составления многопроцессорного расписания для комплекса работ, допускающих прерывания и переключения с одного процессора на другой. Предполагается, что обработка прерываний и переключений требует временных издержек. Это условие переводит задачу из класса полиномиально разрешимых в класс NP-трудных. Разработан алгоритм, основанный на методике В.С. Танаева составления многопроцессорного расписания без учета затрат на прерывания и переключения. Методика включает в себя процедуру упаковки для случая, когда работы имеют общий директивный срок, а также процедуру сведения исходной задачи к потоковой для случая произвольных директивных интервалов. При этом используется также известный псевдополиномиальный алгоритм составления допустимого многопроцессорного расписания для непрерываемых работ с общим директивным сроком.

We consider the problem of creating a multiprocessor schedule for a set of jobs that allow interruptions and switching from one processor to another. It is assumed that processing interrupts and switches requires time overhead. This condition transfers the problem from the class of polynomially solvable to the class of NP-hard ones. An algorithm has been developed based on the methodology of V.S. Tanaev for compiling a multiprocessor schedule without taking into account the costs of interruptions and switching. The technique includes a packing procedure for the case when jobs have a common deadline, as well as a procedure for reducing the original problem to a network flow problem for the case of arbitrary deadlines. In this case, the well-known pseudo-polynomial algorithm for creating an admissible multiprocessor schedule for continuous jobs with a common deadline is also used.

многопроцессорная системадирективный интервалдопустимое расписаниепроцедура упаковкипотоковая сетьmultiprocessor systemadmissible scheduledirective intervalpacking procedureflow networkReferencesТанаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984, 383 с.Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984, 383 с.Brucker P. Scheduling Algorithms. Heidelberg: Springer, 2007, 378 с.Brucker P. Scheduling Algorithms. Heidelberg: Springer, 2007, 378 с.Лазарев А.А. Теория расписаний. Методы и алгоритмы. –М.: ИПУ РАН, 2019,407 с.Лазарев А.А. Теория расписаний. Методы и алгоритмы. –М.: ИПУ РАН, 2019,407 с.А.В. Мищенко, П.С. Кошелев. Оптимизация управления работами логистического проекта в условиях неопределенности // Известия РАН. Теория и системы управления. (2021), № 4, 123-134.А.В. Мищенко, П.С. Кошелев. Оптимизация управления работами логистического проекта в условиях неопределенности // Известия РАН. Теория и системы управления. (2021), № 4, 123-134.М.А. Горский, А.В. Мищенко, Л.Г. Нестерович, М.А. Халиков. Некоторые модификации целочисленных оптимизационных задач с учетом неопределенности и риска // Известия РАН. Теория и системы управления. (2022), № 5, 106-117.М.А. Горский, А.В. Мищенко, Л.Г. Нестерович, М.А. Халиков. Некоторые модификации целочисленных оптимизационных задач с учетом неопределенности и риска // Известия РАН. Теория и системы управления. (2022), № 5, 106-117.А.Б. Глонина, В.В. Балашов. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов // Моделирование и анализ информационных систем. (2018), Т. 25, № 2, 174 – 192.А.Б. Глонина, В.В. Балашов. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов // Моделирование и анализ информационных систем. (2018), Т. 25, № 2, 174 – 192.А.Б. Глонина. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем // Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика. (2020), № 3, 16 – 29.А.Б. Глонина. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем // Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика. (2020), № 3, 16 – 29.М.Г. Фуругян. Планирование вычислений в многопроцессорных АСУ реального времени с дополнительным ресурсом //Автоматика и телемеханика. (2015), №3, 144 – 150.М.Г. Фуругян. Планирование вычислений в многопроцессорных АСУ реального времени с дополнительным ресурсом //Автоматика и телемеханика. (2015), №3, 144 – 150.М.Г. Фуругян. Составление расписаний в многопроцессорных системах с несколькими дополнительными ресурсами // Известия РАН. Теория и системы управления. (2017), № 2, 57 – 66.М.Г. Фуругян. Составление расписаний в многопроцессорных системах с несколькими дополнительными ресурсами // Известия РАН. Теория и системы управления. (2017), № 2, 57 – 66.М.Г. Фуругян. Некоторые алгоритмы решения минимаксной задачи составления многопроцессорного расписания // Известия РАН. Теория и системы управления. (2014), №2, 50 - 56.М.Г. Фуругян. Некоторые алгоритмы решения минимаксной задачи составления многопроцессорного расписания // Известия РАН. Теория и системы управления. (2014), №2, 50 - 56.М.Г. Фуругян. Составление расписаний в многопроцессорной системе с учетом затрат на прерывания // В Сб. Математическое и компьютерное моделирование сложных систем: теоретические и прикладные аспекты. Труды НИИСИ РАН. Т. 6, № 2, 57 – 61.М.Г. Фуругян. Составление расписаний в многопроцессорной системе с учетом затрат на прерывания // В Сб. Математическое и компьютерное моделирование сложных систем: теоретические и прикладные аспекты. Труды НИИСИ РАН. Т. 6, № 2, 57 – 61.

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