Planning computations in real-time systems: Efficient algorithms for constructing optimal schedules

Texto integral

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

Известны два основных подхода к разработке вычислительных систем реального времени. Первый подход основан на предварительном расчете расписания выполнения вычислений. Так, авторами [1–3] разработана методика построения допустимых расписаний с директивными сроками в многоядерной вычислительной системе реального времени. Согласно этой методике, сначала строится временная диаграмма работы системы, а затем с ее помощью проверяется выполнение каждого задания в своем директивном интервале. Кроме того, разработана имитационная модель системы, основанная на использовании сетей Петри и обобщенных конечных автоматов с остановкой таймера.

Авторы данной статьи в разное время принимали участие в проектах по созданию вычислительных систем реального времени: для обработки информации при проведении летных испытаний, для функционирования системы противовоздушной и космической обороны, при разработке газовых месторождений и строительных работах. При этом также использовался подход, основанный на предварительном расчете расписания выполнения вычислений, как это было сделано при разработке системы автоматизации программирования вычислительных систем реального времени, предназначенных для обработки циклически поступающей информации. На вход системы поступает программа пользователя, в которой описаны прикладные модули, предназначенные для вычисления, их длительности, входные и выходные параметры, частоты обращения к ним, длительности их выполнения и другие параметры. Блок генерации кодов переводит информацию, содержащуюся в этой программе, в таблицы, удобные для дальнейшей обработки. Далее работает генератор сетевой модели, который строит ориентированную сеть. Узлами сети являются прикладные модули, а дуги указывают отношения частичного порядка их выполнения. Затем подключается генератор расписаний, который, получая на вход эту сетевую модель, определяет, существует ли допустимое расписание выполнения прикладных модулей, и строит его в случае положительного ответа. Управляющая программа запускает в реальном времени прикладные модули согласно построенному расписанию. Одним из основных блоков этой системы является генератор расписаний.

При втором подходе планирование вычислений осуществляется в режиме реального времени. Так, в [4] исследована задача планирования комплекса работ, требования на выполнение которых поступают в известные моменты времени. Однако характеристики работ, такие как длительность и директивные сроки, становятся известными в момент поступления каждого запроса. В этом случае возникает необходимость составлять расписание выполнения вычислений в режиме реального времени. Авторами разработан полиномиальный алгоритм построения допустимого расписания для данного случая.

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

В работах [7–9] рассматривается ряд экономических задач планирования. Предполагается, что некоторые параметры (длительность выполнения работ, объем ресурсов) не являются фиксированными, а могут принимать значения из заданных интервалов либо представляют собой случайные величины. Для решения этих задач авторы используют метод ветвей и границ. В [10] на основе понятия расстояния между задачами разработаны методы решения ряда NP-трудных задач для критерия минимизации максимального запаздывания, а также для задач на быстродействие.

В работе [11] рассмотрены системы реального времени с интегрированной модульной архитектурой. Авторы предлагают алгоритмы составления расписаний, основанные на построении транспортной сети и нахождении в ней максимального потока. Создание алгоритма решения задачи на быстродействие в многопроцессорной системе при ограничении на количество передач данных между процессорами описано в [12]. Алгоритм основан на использовании метода имитации отжига.

В [13] описана процедура построения расписания, состоящая из двух шагов. На первом шаге с помощью эвристического алгоритма, основанного на методе ветвей и границ, определяется последовательность выполнения работ. На втором в построенный график добавляются интервалы простоя с учетом директивных сроков начала и окончания операций. Эта задача сводится к задаче линейного программирования. В [14] рассмотрены проблемы, связанные с установлением директивных сроков выполнения работ и допустимых отклонений от этих сроков. Предложена модель, показывающая связь директивных сроков и стохастической изменчивости объемов ресурсов, необходимых для выполнения работ. В [15] решается задача оптимизации работы и маршрутов двух роботов, которые доставляют продукты в определенные места и должны вернуться в исходное положение. Рассмотрена задача на быстродействие и доказана ее NP-трудность. Для ее решения используются методы целочисленного линейного программирования, а также генетический алгоритм. Для оценки качества решений применяется динамическое программирование.

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

Составление однопроцессорных и многопроцессорных расписаний с прерываниями и директивными сроками

• Построение однопроцессорного расписания

Имеется совокупность работ (заданий) W = {w₁, w₂, …, w_n}, которые должны быть выполнены с помощью m идентичных процессоров. Известны длительности t_i выполнения работ w_i и их директивные интервалы [b_i; f_i], t_i  f_i – b_i (работа w_i не может быть начата раньше момента ее готовности b_i и должна быть завершена не позднее ее директивного срока f_i). При выполнении работ допускаются прерывания и переключения с одного процессора на другой. Предполагается, что они не требуют временных затрат. Не допускаются параллельное выполнение одного задания несколькими процессорами и одновременное выполнение нескольких работ одним процессором. Требуется определить, существует ли допустимое расписание выполнения работ, и найти его, если оно существует. Допустимое расписание – это такое расписание, при котором каждая работа выполняется в своем директивном интервале.

Алгоритм относительной срочности. Для однопроцессорных систем (m = 1) известен алгоритм [16], который выглядит следующим образом.

Алгоритм 1.

Пусть A(t) – множество активных работ в момент времени t, то есть таких работ w_i, которые еще не завершены (или не начаты), и при этом t ∈ [b_i; f_i]. Процессор выделяется активной работе w_i с минимальным директивным сроком $f:f_{i_0}=\underset{i:w_i\in A\left(t\right)}{\min }{f}_i.$ Если таких работ несколько, то выбирается любая из них. Работа w_i выполняется до тех пор, пока либо она не завершится, либо не появится активная работа $w_{j_0}$ с меньшим директивным сроком $f_{j_0}.$ В последнем случае выполнение работы $w_{i_0}$ прерывается и процессор передается заданию $w_{j_0}.$

Поскольку выполнение работ может прерываться только в моменты времени b_i, число прерываний не более n. В отличие от [16] величины f_i для активных работ будем хранить в виде двоичной кучи с минимальным элементом в вершине. В этом случае вычислительная сложность алгоритма 1 составляет O(n log n). Алгоритм, описанный в [16], не использует двоичную кучу и имеет вычислительную сложность O(n²). В работе доказано, что данный алгоритм является корректным: если он не находит решение, то оно не существует.

Построение однопроцессорного расписания с отношением частичного порядка на множестве работ. Сформулированную постановку задачи для однопроцессорной системы дополним еще одним условием. Будем предполагать, что на множестве работ W задано отношение частичного порядка в виде ориентированного графа без циклов G = (W, A), где A – множество ориентированных дуг. Если (w_i, w_j) ∈ A, значит, работа w_j может быть начата только после завершения работы w_i. Здесь w_i – непосредственный предшественник работы w_j, а w_j – непосредственный последователь работы w_i. Предлагаемый алгоритм основан на коррекции директивных интервалов с последующим применением алгоритма 1.

В основе коррекции директивных интервалов лежит следующее простое правило: если (w_i, w_j) ∈ A, то момент готовности b_j работы w_j и директивный срок f_i работы w_i пересчитываются по следующим формулам:

b_j = max (b_j, b_i + t_i), f_i = min (f_i, f_j – t_j).

Действительно, b_i + t_i – это наиболее ранний возможный срок окончания работы w_i, а f_j – t_j – наиболее поздний допустимый срок завершения работы w_i. Перед выполнением процедуры коррекции множество W необходимо разбить на уровни следующим образом. Пусть W₀ – это множество работ, не имеющих непосредственных предшественников. Если построены множества W₀, W₁, …, W_{k - 1}, то W_k – это множество работ, имеющих непосредственных предшественников только в множествах W₀, W₁, …, W_{k - 1}. Предположим, что построено разбиение множества W на уровни W₀, W₁, …, W_p, p ≤ n – 1. Коррекция моментов готовности работ проводится начиная с W₁, затем W₂ и т.д. следующим образом: если w_j ∈ W_k, то принять

b_j = max (b_j ,  (b_i + t_i)), $k=\overline{\mathrm{1,}p}.$ 

Коррекция директивных сроков работ проводится начиная с W_p-1, затем W_p-2 и т.д. следующим образом: если w_i ∈ W_k, то принять

f_i = min (f_i,  (f_j – t_j)), $k=\overline{p-\mathrm{1,}\text{\hspace{0.33em}}0}.$ 

Вычислительная сложность процедуры коррекции директивных интервалов составляет O(n²).

После выполнения процедуры коррекции множество W будет обладать следующим свойством: если (w_i, w_j) ∈ A, то b_i < b_j, f_i < f_j. Следовательно, для поиска допустимого расписания может быть использован алгоритм относительной срочности (алгоритм 1). Таким образом, алгоритм решения поставленной в настоящем разделе задачи следующий.

Алгоритм 2.

Шаг 1. Выполнить процедуру коррекции директивных интервалов.

Шаг 2. Применить алгоритм 1.

Вычислительная сложность алгоритма 2 составляет O(n²).

Построение многопроцессорных расписаний. Для случая m ≥ 2 может быть использован потоковый алгоритм [5] (алгоритм 3), основанный на сведении исходной задачи к нахождению максимального потока в ориентированной сети специального вида. Вычислительная сложность алгоритма 3 составляет O(n³) (если при нахождении максимального потока использовать алгоритм кубической сложности). Алгоритм 3, как и алгоритм 1, является корректным.

Идея алгоритма относительной срочности в том, что процессор всегда занят активной работой с наименьшим директивным сроком и она легко может быть перенесена на многопроцессорный случай (m ≥ 2).

Алгоритм 4.

Процессоры всегда должны занимать m активных работ с наименьшими директивными сроками (если таковые имеются). Если активных работ меньше m, то все они должны выполняться. Если появляется новая активная работа с директивным сроком, меньшим наибольшего директивного срока из выполняемых работ, то она заменяет последнюю. В этом случае следует иметь две двоичные кучи. Первая содержит директивные сроки работ, которые выполняются в данный момент (их не более m). В вершине этой кучи находится максимальный элемент. Вторая куча содержит директивные сроки активных работ, которые в данный момент не выполняются. В вершине этой кучи находится минимальный элемент. Возникшая новая активная работа включается во вторую кучу. Если при этом она оказывается в вершине кучи и ее директивный срок меньше директивного срока, находящегося в вершине второй кучи, то элементы, находящиеся в вершинах обеих куч, меняются местами. После этого каждый из них становится на свое место в соответствующей куче. Вычислительная сложность алгоритма 4 составляет O((n log n) log m). Алгоритм, описанный в [17], является аналогичным обобщением алгоритма 1 на многопроцессорный случай. Однако он не использует двоичные кучи и имеет более высокую вычислительную сложность: O(n (m log m + log n).

Поскольку можно считать, что m << n, вычислительная сложность алгоритма 4 существенно меньше вычислительной сложности потокового алгоритма 3. Рассмотрим простой пример, показывающий работу алгоритма 4.

Пример. Пусть n = 3, m = 2, b_i = 0, f_i = 3, t_i = 2 при всех i = 1, 2, 3. Пусть R_ij – временной интервал, в котором работа w_i выполняется j-м процессором. Тогда алгоритм 4 построит следующее расписание: R₁₁ = [0; 2], R₂₂ = [0; 2], R₁₃ = [2; 4]. Это означает, что работа w₃ не успевает завершиться к своему директивному сроку f₃ = 3, то есть алгоритм 4 не находит допустимого расписания. Однако на самом деле допустимое расписание существует: R₁₁ = [0; 2], R₂₂ = [0; 1], R₂₁ = [2; 3], R₁₃ = [1; 3]. В этом случае все работы успевают завершиться к своему директивному сроку f_i = 3, i = 1, 2, 3.

Следовательно, алгоритм 4 не всегда работает корректно. Как показано в [17], на основании результатов 25 000 численных экспериментов с рандомизированными и плавно варьируемыми переменными можно сделать вывод, что при больших размерностях задачи алгоритм 4 работает в тысячи раз быстрее алгоритма 3. В то же время некорректная работа алгоритма 4 была отмечена не более чем в 3 % случаев. Поэтому можно предложить следующий алгоритм решения задачи: сначала запускается быстрый алгоритм 4; если решение не найдено, запускается алгоритм 3.

Замечание. Если предположить, что прерывания и переключения с одного процессора на другой требуют временных затрат, то задача становится NP-трудной. Покажем, что в этом случае к рассматриваемой задаче полиномиально сводится известная NP-полная задача о разбиении (имеются n натуральных чисел a₁, a₂, …, a_n, и пусть $B={\sum }_{i=1}^n{a}_i$ – четное число; можно ли разбить это множество на два непересекающихся подмножества с одинаковой суммой элементов, то есть существует ли такое подмножество {1, 2, …, n}, что ${\sum }_{i\in \overline{N}}{a}_i={\sum }_{i\in N\backslash \overline{N}}{a}_i=B/2$) [18]. Если в рассматриваемой задаче о построении расписания принять m = 2, b_i = 0, f_i = B/2, i = $\overline{\mathrm{1,}n}$, то допустимое расписание будет существовать в том и только том случае, когда в задаче о разбиении ответ положительный.

Составление многопроцессорных расписаний без прерываний с общим директивным интервалом

Предположим, что работы не допускают прерываний и переключений с одного процессора на другой, длительности t_i принимают натуральные значения, а директивные интервалы всех работ совпадают: b_i = 0, f_i = F, t_i ≤ F. Известно, что такая задача является NP-трудной в сильном смысле [18]. Однако при фиксированном числе процессоров m существует псевдополиномиальный алгоритм.

Пусть X = {x = (x₁, x₂, …, x_m): 0 ≤ x_j ≤ F, j = $\overline{\mathrm{1,}m}$}. Здесь x_j – временная загруженность j-го процессора,  Пусть X_k ⊆ X, k = $\overline{\mathrm{1,}n}$ – непересекающиеся подмножества множества X, которые определяются следующим образом:

X₁ = {x ∈ X: x_i = 0 при i ≠ j, x_j = t_j, j = $\overline{\mathrm{1,}m}$}, то есть X₁ – множество векторов из X, у которых все компоненты, кроме x_j, равны 0, а x_j = t_j, j = $\overline{\mathrm{1,}m}$;

X_k = {x ϵ X: x_j = $\overline{x_j}$ + t_k, x_{j ≤} F, j = $\overline{\mathrm{1,}m}$, $\overline{x}$ ∈ X_k-1}, $k=\overline{\mathrm{2,}n}$, то есть каждый вектор из X_k получается прибавлением величины t_k к j-й компоненте некоторого вектора $\overline{x}$ ∈ X_k-1, j = $\overline{\mathrm{1,}m}$. Каждому вектору x ∈ X_k приписывается метка, указывающая, из какого вектора $\overline{x}$ ∈ X_k-1 он получен.

Важно отметить: если при построении множества X_k для некоторой компоненты x_j вектора x ∈ X_k выполняется неравенство x_j > F, то вектор x не включается в X_k. К тому же число векторов в X_k не превосходит (F + 1)^m. Алгоритм решения задачи (алгоритм 5) заключается в построении множеств X_k, k = $\overline{\mathrm{1,}n}$. Если $X_n\ne \varnothing$, то допустимое расписание существует и может быть построено путем следования по меткам, указанным при построении множеств X_k,
k = $\overline{\mathrm{2,}n}$.

Алгоритм 5.

Шаг 1. Построить множества X_k, k = $\overline{\mathrm{1,}n}$.

Шаг 2. Если X_n $\ne \varnothing$, перейти на шаг 3. В противном случае перейти на шаг 5.

Шаг 3. С помощью меток, указанных при построении множеств X_k, k = $\overline{\mathrm{2,}n}$, построить последовательность векторов x^k ϵ X_k, k = $\overline{n,1}$.

Шаг 4. Если x^k и x^k-1 отличаются j-й компонентой, то работа w_k приписывается процессору j, k = $\overline{n,1}$. Завершение алгоритма.

Шаг 5. Допустимого расписания не существует. Завершение алгоритма.

Далее работы, приписанные процессору j, j = $\overline{\mathrm{1,}m}$, выполняются этим процессором в произвольном порядке. Поскольку число элементов в каждом множестве X_k, k = $\overline{\mathrm{1,}n-1}$, не превосходит число элементов в X, то есть величины (F + 1)^m, и для каждого из них строится не более m элементов в X_k+1, то вычислительная сложность алгоритма 5 составляет O(mn(F + + 1)^m), или O(mnF^m). Следовательно, при фиксированном числе процессоров m алгоритм 5 является псевдополиномиальным.

Составление расписаний в системе с неоднородными ресурсами

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

• Смешанный комплекс работ, общий директивный интервал

Рассмотрим комплекс работ W = W₁$\cup$W₂, где W₁ = {w₁₁, w₁₂, …, } – работы, допускающие прерывания и переключения с одного процессора на другой, W₂ = {w₂₁, w₂₂, …, } – непрерываемые работы. Для работ W₁ и W₂ остаются предположения, сделанные ранее. Для всех работ установлен общий директивный интервал [0; F]. Для выполнения работ имеются m идентичных процессоров и L типов невозобновляемых ресурсов, объемы которых составляют R₁, R₂, …, R_L. Если работе w_ki выделен ресурс l-го типа в количестве r_kil, l = $\overline{\mathrm{1,}L}$, то длительность ее выполнения составляет

$t_{ki}=t_{ki}^0-\sum _{l=1}^L{a}_{kil}{r}_{kil}$, k = 1, 2, i = $\overline{\mathrm{1,}{n}_k}$, (1)

где $t_{ki}^0$ – длительность выполнения работы w_ki в случае, если невозобновляемые ресурсы ей не выделяются; $t_{ki}^0\le F$, k = 1, 2, i = $\overline{\mathrm{1,}{n}_k}$, a_kil > 0 – заданные величины. На величины r_kil накладываются следующие ограничения:

$r_{kil}^1\le r_{kil}\le r_{kil}^2,\text{\hspace{0.33em}}k=\mathrm{1,}\text{\hspace{0.33em}}\mathrm{2,}i=\overline{\mathrm{1,}\text{\hspace{0.33em}}{n}_k},l=\overline{\mathrm{1,}L},$ (2)

$\sum _{k=1}^2\sum _{i=1}^{n_k}{r}_{kil}\le R_l,l=\overline{\mathrm{1,}L},$ (3)

$t_{ki}^0-\sum _{l=1}^L{a}_{kil}{r}_{kil}^2>\mathrm{0,}k=\mathrm{1,}\text{\hspace{0.33em}}\mathrm{2,}i=\overline{\mathrm{1,}\text{\hspace{0.33em}}{n}_k}.$ (4)

Неравенство (2) определяет ограничения на объемы ресурсов, выделяемых каждой работе. Неравенство (3) ограничивает общий объем выделяемых ресурсов каждого типа. Согласно неравенству (4), при выделении работе максимально допустимого объема ресурсов каждого типа ее длительность остается положительной. Распределение ресурсов r_kil, $k=\mathrm{1,}\text{\hspace{0.33em}}\mathrm{2,}i=\overline{\mathrm{1,}\text{\hspace{0.33em}}{n}_k},$ $l=\overline{\mathrm{1,}L},$ удовлетворяющее ограничениям (2)–(4), будем называть допустимым. Задача заключается в поиске допустимого распределения ресурсов и допустимого расписания.

Алгоритм 6 решения задачи состоит из трех этапов. На первом этапе выполняется распределение невозобновляемых ресурсов, после чего будут определены длительности выполнения работ. На втором этапе процессоры делятся на две группы: первая – для выполнения работ W₁, вторая – для выполнения работ W₂. На третьем этапе строится расписание, отдельное для W₁ и W₂.

Для каждого $l=\overline{\mathrm{1,}L}$ ресурс l-го типа распределяется следующим образом. Определяется $\underset{k,i}{\max }{a}_{kil}=a{}_{k_0{i}_{0}l}$, и работе $w_{k_o{i}_o}$ выделяется максимально возможное количество ресурса l-го типа (то есть такое количество, при котором не нарушаются ограничения (2), (3)). Оставшаяся неиспользованной часть ресурса l-го типа распределяется среди оставшихся работ по аналогичному правилу. Такое распределение ресурсов позволяет максимально сократить длительности работ. Если для каждого $l=\overline{\mathrm{1,}L}$ величины a_kil отсортировать по невозрастанию, то вычислительная сложность первого этапа будет составлять O(Ln log n).

После распределения невозобновляемого ресурса между работами вычисляются их длительности по (1) и величины

$m_1=\left[\frac{{\displaystyle \sum _{i=1}^{n_1}{t}_{1i}}}{{\displaystyle \sum _{i=1}^{n_1}{t}_{1i}+\sum _{i=1}^{n_2}{t}_{2i}}}\right]$, m₂ = m – m₁. (5)

Работы W₁ будут выполняться первыми m₁ процессорами, а работы W₂ – оставшимися m₂ процессорами. По формуле (5) распределяются процессоры между работами W₁ и W₂ пропорционально суммарной длительности выполнения работ этих множеств. Вычислительная сложность второго этапа составляет O(n), где n = n₁ + n₂.

Для построения расписания выполнения работ W₁ и W₂ соответственно могут быть использованы алгоритм упаковки [5], вычислительная сложность которого составляет O(n₁), и рассмотренный псевдополиномиальный алгоритм, вычислительная сложность которого составляет

• Прерываемые работы, произвольные директивные интервалы

Предположим, что множество W однородное: каждая работа w_i ∈ W допускает прерывания и переключения с одного процессора на другой и имеет директивный интервал [b_i; f_i]. Для ресурса l-го типа известен коэффициент a_l, показывающий, на какую величину сократится время выполнения работы, если ей будет выделена единица этого ресурса. К тому же выполнены приведенные далее ограничения, аналогичные условиям (1)–(4), а именно: если работе w_i выделено r_il ресурсов l-го типа, то справедливы соотношения:

$t_i=t_i^0-\sum _{l=1}^L{a}_l{r}_{il}$, i = $\overline{\mathrm{1,}n}$, (6)

$r_{il}\le r_{il}^2,\text{\hspace{0.33em}\hspace{0.33em}}i=\overline{\mathrm{1,}\text{\hspace{0.33em}}n},$$l=\overline{\mathrm{1,}L}$, (7)

$\sum _{i=1}^n{r}_{il}\le R_l,l=\overline{\mathrm{1,}L},$ (8)

$t_i^0-\sum _{l=1}^L{a}_l{r}_{il}^2>\mathrm{0,}i=\overline{\mathrm{1,}\text{\hspace{0.33em}}n}.$ (9)

Величины $t_i^0$ и $r_{il}^2$ определяются по аналогии с тем, как это сделано для смешанного комплекса работ.

Для решения задачи по примеру [5] построим потоковую сеть G = (N, A), дополнив ее элементами, соответствующими невозобновляемым ресурсам (см. рисунок). Множество узлов определим как N = {u, I_j, r_l, w_i, v, j = $\overline{\mathrm{1,}p}$, l = $\overline{\mathrm{1,}L}$, i = $\overline{\mathrm{1,}n}$}, где I_j = [y_j-1; y_j], y₀ < y₁ < … < y_p – все различные величины b_i, f_i; i =$\overline{\mathrm{1,}n}$ ; u – источник; v – сток; r_l соответствует ресурсу l-го типа. Множество дуг A определим как A = {(u, I_j), (u, r_l), (I_j, w_i), (r_i, w_i), (w_i, v), j = $\overline{\mathrm{1,}p}$, l = $\overline{\mathrm{1,}L}$, i = $\overline{\mathrm{1,}n}$}. Дуга (l_j, w_i) вводится в сеть G в том случае, если $I_j\subseteq [b_i;f_i]$.

 

Потоковая сеть G (j = $\overline{\text{1},p}$, l = $\overline{\text{1},L}$, i = $\overline{\text{1},n}$)

Stream network G (j = $\overline{\text{1},p}$ , l = $\overline{\text{1},L}$ , i = $\overline{\text{1},n}$ )

 

Пропускные способности U дуг определим следующим образом: U(u, I_j) = m(y_j+1 – y_j), U(u, r_l) = R_l, U(I_j, w_i) = y_j+1 – y_j, U(r_l, w_i) = a_i , U(w_i, v) = t_i, j = $\overline{\mathrm{1,}p}$, l = $\overline{\mathrm{1,}L}$, i = $\overline{\mathrm{1,}n}$. В отличие от [5] будем рассматривать обобщенные сети, в некоторых внутренних узлах которых величина выходящего потока равна величине входящего потока, умноженной на некоторый коэффициент (коэффициент выигрыша), постоянный для данного узла. Так, для рассматриваемой сети G в узлах l_j и w_i выполняется условие сохранения потока, а в узле r_l коэффициент выигрыша равен a_l.

По аналогии с тем, как это сделано в [5], можно показать, что решение задачи существует только в том случае, когда максимальный поток g в сети G насыщает все дуги (w_i, v), то есть

(w_i, v) = t_i  (10)

при всех i = $\overline{\mathrm{1,}n}$. Если это условие выполнено, то потоки по дугам определяют расписание выполнения работ W процессорами [5]. Потоки по дугам (r_i, w_i) определяют распределение ресурса l-го типа:

r_il = g(r_i, w_i)/a_l, l = $\overline{\mathrm{1,}L}$, i = $\overline{\mathrm{1,}n}$ (11)

Таким образом, для решения рассматриваемой задачи разработан следующий алгоритм.

Алгоритм 7.

Шаг 1. Построить сеть G.

Шаг 2. Найти максимальный поток g в сети G.

Шаг 3. Если выполнено условие (10), решение существует; перейти на шаг 4, в противном случае – на шаг 5.

Шаг 4. Расписание выполнения работ W определяется с помощью величин g(I_j, w_i) и алгоритма упаковки [5]. Распределение невозобновляемых ресурсов определяется по формуле (11). Алгоритм завершен.

Шаг 5. Решения не существует. Алгоритм завершен.

Если при нахождении максимального потока в сети G использован алгоритм кубической сложности, то вычислительная сложность алгоритма 7 составляет O((n + L)³), поскольку число узлов в сети G равно O(n + L). Отметим, что в [19] предполагается, что длительность выполнения каждой работы выражается убывающей по каждой переменной функцией от количества предоставленных этой работе невозобновляемых ресурсов. Эта задача сводится к минимизации некоторой функции с O(n(n + L)) переменными при O(n²) линейных ограничений. Предположение о линейности длительностей от выделенных ресурсов позволило свести задачу к потоковой.

Заключение

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

В дальнейшем авторы планируют исследовать обобщения рассмотренных задач на случаи наличия неопределенных факторов и вероятностных характеристик параметров.

Sobre autores

Dmitry Kononov

Trapeznikov Institute of Control Sciences of the Russian Academy of Sciences

Email: dmitrykon52@gmail.com

Dr.Sci. (Engineering), Associate Professor, Leading Researcher

Rússia, Moscow, 117997

Meran Furugyan

Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences

Autor responsável pela correspondência
Email: rtsccas@yandex.ru

Cand. of Sci. (Physics), Associate Professor, Senior Researcher

Rússia, Moscow, 119333

Bibliografia

Arquivos suplementares