Известия РАН. Теория и системы управления, 2023, № 1, стр. 72-81

Введение. В настоящее время вычислительные системы реального времени применяются в различных областях деятельности человека: в гражданском и военном строительстве, при испытаниях и эксплуатации самолетов и ракет, при проектировании и функционировании производственных и транспортных систем, в нефте- и газодобывающих отраслях. Одно из основных требований, предъявляемых к таким системам, заключается в том, что все вычисления должны производиться при заданных временных ограничениях. Для решения этой задачи могут быть использованы различные методы построения оптимальных расписаний [1–4].

В [5–7] разработана методика проверки выполнения ограничений реального времени, заключающихся в том, что каждая работа должна выполняться в заданном директивном интервале. Проведенные исследования выполнены для многоядерной вычислительной системы реального времени и основаны на построении имитационной модели с использованием обобщенных конечных автоматов с остановкой таймера. С помощью этой модели строится временная диаграмма работы системы, позволяющая осуществить непосредственную проверку выполнения ограничений реального времени. В [8] предложен псевдополиномиальный алгоритм решения задачи построения оптимального по быстродействию расписания исполнения заданий с логическими условиями предшествования. В этой задаче для каждого задания дан список его непосредственных предшественников, а также число завершенных непосредственных предшественников, необходимое для начала его выполнения. Задача сведена к циклической игре. В [9, 10] некоторые задачи планирования работ сведены к минимаксным задачам.

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

При разработке вычислительных систем реального времени возникает задача оптимизации расположения модулей контроля среди прикладных модулей. Эта задача исследовалась ранее рядом авторов с использованием вероятностных методов. При этом предполагается, что известны вероятности возникновения сбоев и ошибок. В [11, 12] допускалось, что вероятность возникновения ошибки в одном и том же месте системы не является постоянной и может изменяться после рестарта. В [13] для многопроцессорной системы определяется такое расположение модулей контроля, при котором вероятность выполнить все прикладные модули до выхода из строя всех процессоров максимальна. В [14] определяется понятие зоны рестарта – совокупность прикладных модулей, которые следует выполнить заново в случае обнаружения ошибки некоторым модулем контроля. В предположении, что известно расположение модулей контроля, строится минимальная зона рестарта. В [15] решается задача расположения модулей контроля с целью минимизировать математическое ожидание суммарного времени, затраченного на выполнение всех модулей (включая их повторное выполнение при рестарте). Рассмотрены различные виды графа частичного порядка выполнения прикладных модулей.

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

1. Постановка задачи. Задан набор прикладных модулей $W = \{ {{w}_{1}},\;{{w}_{2}},\; \cdots ,\;{{w}_{N}}\} $, $N \geqslant 2$, подлежащих выполнению на вычислительной системе. Число процессоров в системе может быть произвольным. (Как будет показано ниже, на решение рассматриваемой задачи это не влияет.) Каждый модуль w_i выполняется без прерываний и переключений с одного процессора на другой, а длительность его выполнения равна ${{t}_{i}} = t({{w}_{i}})$, $i = \overline {1,\;N} $. На множестве W задано отношение частичного порядка выполнения прикладных модулей в виде ориентированного графа без циклов $G = (W,\;A)$, где W – множество узлов, A – множество ориентированных дуг. Если $({{w}_{i}},\;{{w}_{j}}) \in A$, то начало исполнения модуля w_j  возможно только после завершения модуля w_i. В этом случае будем также использовать обозначение ${{w}_{i}} \to {{w}_{j}}$. В цепочке

модули ${{w}_{{{{i}_{j}}}}}$ при  j < p, $j = \overline {1,\;n - 1} $, являются предшественниками модуля ${{w}_{{{{i}_{p}}}}}$, а при j > p, $j = \overline {2,\;n} $, – его последователями. Кроме того, модуль ${{w}_{{{{i}_{j}}}}}$ выступает непосредственным предшественником ${{w}_{{{{i}_{{j + 1}}}}}}$_, а ${{w}_{{{{i}_{{j + 1}}}}}}$ – непосредственным последователем ${{w}_{{{{i}_{j}}}}}$, $j = \overline {1,\;n - 1} $. Введем обозначения: т.е. $P({{w}_{i}})$ и $Q({{w}_{i}})$ – соответственно все непосредственные предшественники и непосредственные последователи прикладного модуля ${{w}_{i}}$, а ${{P}_{0}}$ и ${{Q}_{0}}$ – прикладные модули, не имеющие соответственно непосредственных предшественников и непосредственных последователей.

Помимо прикладных модулей в системе имеется K модулей контроля, $K \leqslant N$. Каждый модуль контроля присоединяется к некоторому прикладному модулю и выполняется сразу же после завершения этого прикладного модуля. К каждому прикладному модулю присоединяется не более одного модуля контроля. Предполагается, что временем выполнения модуля контроля можно пренебречь, поскольку оно существенно меньше времени выполнения прикладных модулей. Пусть $\overline W = \{ {{w}_{{{{i}_{1}}}}},\;{{w}_{{{{i}_{2}}}}},\;...,{{w}_{{{{i}_{K}}}}}\} $ – множество всех прикладных модулей, к которым присоединены модули контроля. Будем называть его расстановкой модулей контроля или просто расстановкой.

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

Предположим, что модулем контроля, присоединенным к некоторому прикладному модулю ${{w}_{{{{i}_{n}}}}} \in \overline W $, была обнаружена ошибка. В графе G рассматриваются все ориентированные пути (цепочки) $\pi $ вида (1.1), в которых ${{w}_{{{{i}_{j}}}}} \notin \overline W $, $j = \overline {1,\;n - 1} $. Кроме того, либо ${{w}_{{{{i}_{1}}}}} \in {{P}_{0}}$, либо модуль ${{w}_{{{{i}_{1}}}}}$ имеет одного или нескольких предшественников, и если ${{w}_{{{{i}_{1}} - 1}}} \to {{w}_{{{{i}_{1}}}}}$, то ${{w}_{{{{i}_{1}} - 1}}} \in \overline W $. Иными словами, указанный путь начинается с прикладного модуля, который либо не имеет непосредственных предшественников, либо к каждому из его непосредственных предшественников присоединен модуль контроля, а все остальные прикладные модули этого пути, кроме ${{w}_{{{{i}_{n}}}}}$ (${{w}_{{{{i}_{n}}}}} \in \overline W $), не являются таковыми. Будем называть такие пути $\pi $ путями (или цепочками) рестарта. В случае обнаружения ошибки модулем контроля, присоединенным к прикладному модулю ${{w}_{{{{i}_{n}}}}}$, необходимо для каждой цепочки рестарта вида (1.1) повторить выполнение всех ее прикладных модулей. Длиной цепочки рестарта $\pi $ вида (1.1) будем называть величину

Пусть $\Pi ({{w}_{{{{i}_{n}}}}})$ – множество всех путей рестарта $\pi $ вида (1.1) и пусть

т.е. $t(\Pi ({{w}_{{{{i}_{n}}}}}))$ – это длина максимального из указанных путей. Допустимой расстановкой будем называть такую расстановку $\overline W $, при которой к каждому прикладному модулю из ${{Q}_{0}}$ присоединен модуль контроля, т.е.

Отметим, что при $K < \left| {{{Q}_{0}}} \right|$ допустимой расстановки не существует. Если расстановка не является допустимой, то контроль вычислений не может быть выполнен полностью. Поэтому всюду в дальнейшем будем предполагать, что $K \geqslant \left| {{{Q}_{0}}} \right|$ и что к каждому прикладному модулю из Q₀ присоединен модуль контроля.

Пусть $\Omega $ – множество всех допустимых расстановок. Задача заключается в выборе допустимой расстановки $\overline W $, для которой величина

минимальна. Иными словами, требуется определить величину и допустимую расстановку $\overline W $, на которой реализуется указанный минимакс. Такую расстановку будем называть оптимальной. Таким образом, при оптимальной расстановке минимизируется максимальная длина (1.2) цепочки рестарта.

Замечание 1. В данной постановке задачи при любом числе процессоров время выполнения рестарта в случае обнаружения ошибки не может быть меньше длины максимальной цепочки рестарта. Поэтому представленная минимаксная постановка актуальна независимо от числа процессоров в системе.

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

2. Построение оптимальной расстановки. Предлагаются методы построения оптимальной расстановки для случаев, когда граф G представляет собой последовательную цепочку прикладных модулей, несколько независимых последовательных цепочек, дерево, ориентированное от листьев к корню, дерево, ориентированное от корня к листьям, и произвольный граф без циклов.

2.1. Последовательная цепочка. Допустим, что граф G является последовательной цепочкой ${{w}_{1}} \to {{w}_{2}} \to ... \to {{w}_{N}}$. В этом случае ${{Q}_{0}} = \{ {{w}_{N}}\} $ и в силу (1.3) любая допустимая расстановка имеет вид $\overline W = \{ {{w}_{{{{i}_{1}}}}},\;{{w}_{{{{i}_{2}}}}},\;...,\;{{w}_{{{{i}_{{K - 1}}}}}},\;{{w}_{{{{i}_{K}}}}} = {{w}_{N}}\} $. Без ограничения общности можно считать, что $K \geqslant 2$ и тогда $\Omega = \{ \overline W :\;1 \leqslant {{i}_{1}} < {{i}_{2}} < \cdots < {{i}_{{K - 1}}} < {{i}_{K}} = N\} $. Введем обозначения:

где $k = \overline {1,\;K} $, ${{i}_{0}} = 0.$ В соответствие с (1.4) задача заключается в поиске величины и расстановки $\overline W $, реализующей указанный минимакс. Ниже предлагаются два алгоритма решения этой задачи – точный (алгоритм 1) и приближенный (алгоритм 2).

Алгоритм 1 основан на переборе всех допустимых расстановок, число которых составляет $C_{{N - 1}}^{{K - 1}}$. Алгоритм перебора базируется на том, что величины ${{i}_{1}},{{i}_{2}},...,{{i}_{K}}$ могут принимать следующие значения: i_K = N, ${{i}_{{K - 1}}} = \overline {K - 1,\;{{i}_{K}} - 1} $, ${{i}_{{K - 2}}} = \overline {K - 2,\;{{i}_{{K - 1}}} - 1} $, …, ${{i}_{1}} = \overline {1,\;{{i}_{2}} - 1} $. Для каждого набора ${{i}_{1}},{{i}_{2}},...,{{i}_{K}}$ вычисляются величины T_k, $k = \overline {1,\;K} $, согласно (2.1), и величина T_opt, согласно (2.2). Расстановка $\overline W $, реализующая минимакс (2.2), будет оптимальной.

Определим вычислительную сложность алгоритма 1. Для каждой расстановки при вычислении величин T_k, $k = \overline {1,\;K} $, требуется выполнить O(N) операций, а для вычисления максимальной из величин T_k – $O(K)$ операций. Таким образом, вычислительная сложность алгоритма 1 составляет $O(C_{{N - 1}}^{{K - 1}}(N + K))$ или $O((N - K + 1) \cdots (N - 1)(N + K){\text{/}}(K - 1)!)$. Поскольку $K \leqslant N$, то при фиксированном K сложность алгоритма 1 составляет O(N^K), т.е. алгоритм 1 имеет полиномиальную вычислительную сложность.

Далее предлагается приближенный алгоритм (алгоритм 2). Введем обозначения:

Каждая из величин $T_{1}^{*}$, $T_{2}^{*}$ и $T{\kern 1pt} *$ является нижней оценкой величины ${{T}_{{opt}}}$, т.е.

Действительно, если ${{T}_{{opt}}} < T_{1}^{*}$, то существует допустимая расстановка $\overline W \in \Omega $, для которой ${{T}_{k}} < T_{1}^{*}$ при всех $k = \overrightarrow {1,\;K} $ и, следовательно,

Откуда следует, что

что противоречит (2.3). Следовательно,

Кроме того, для любой допустимой расстановки $\overline W $ при некотором k, $1 \leqslant k \leqslant K$, справедливо неравенство $T_{2}^{*} \leqslant {{T}_{k}}$. Следовательно,

Из (2.5), (2.6) следует (2.4).

Алгоритм 2 минимизирует максимальное отклонение величин ${{T}_{k}}$, $k = \overline {1,\;K} $, от T*, т.е. находит

и расстановку $\overline W $, реализующую этот минимакс.

Алгоритм 2.

Шаг 1. Положить k = K, ${{i}_{k}} = N$.

Шаг 2. Если ${{t}_{{{{i}_{k}}}}} \geqslant T{\kern 1pt} *$, то положить ${{I}_{k}} = \{ {{i}_{k}}\} $, $l = {{i}_{k}} - 1$, перейти на шаг 5. В противном случае (т.е. если ${{t}_{{{{i}_{k}}}}} < T{\kern 1pt} *$) перейти на шаг 3.

Шаг 3. Определить номер ${{i}_{0}}$, $1 < {{i}_{0}} \leqslant {{i}_{k}}$, для которого

Если такой номер существует, то перейти на шаг 4, в противном случае – на шаг 6.

Шаг 4. Положить

Если ${{\Delta }_{1}} \leqslant {{\Delta }_{2}}$, то положить $l = {{i}_{0}}$, ${{I}_{k}} = \{ {{i}_{0}},\; \cdots ,\;{{i}_{k}}\} $. Если ${{\Delta }_{1}} > {{\Delta }_{2}}$, то положить $l = {{i}_{0}} - 1$, I_k = = $\{ {{i}_{0}} - 1, \cdots ,{{i}_{k}}\} $.

Шаг 5. Если $l > 1$ и $k > 1$, то положить $k = k - 1$, ${{i}_{k}} = l$, перейти на шаг 2. В противном случае (т.е. если l = 1 или k = 1) перейти на шаг 6.

Шаг 6. Положить

Шаг 7. Если $k \geqslant 2$, то $(K - k)$ неиспользованных модулей контроля включить в максимальные по длине цепочки рестарта с помощью процедуры включения модуля контроля в цепочку рестарта, описание которой содержится в разд. 2.2.

Шаг 8. Решением задачи является допустимая расстановка $\overline W = \{ {{w}_{{{{i}_{1}}}}},\;{{w}_{{{{i}_{2}}}}},\;...,\;{{w}_{{{{i}_{N}}}}}\} $. Алгоритм завершен.

Поскольку для каждого k выполняется $O(N)$ операций, то сложность алгоритма 2 составляет $O(KN)$. Следовательно, алгоритм 2 имеет полиномиальную вычислительную сложность. Для определения отклонения величины

от ${{T}_{{opt}}}$ применима оценка которая может быть вычислена после работы алгоритма 2.

2.2. Несколько последовательных цепочек. Предполагается, что граф G состоит из p независимых (непересекающихся) цепочек:

В этом случае ${{P}_{0}} = \{ {{w}_{{i1}}},i = \overline {1,p\} } $, ${{Q}_{0}} = \{ {{w}_{{i{{N}_{i}}}}},i = \overline {1,p} \} $, а в силу (1.3) $\{ {{w}_{{i{{N}_{i}}}}},i = \overline {1,p} \} \subseteq \overline W $ и $K \geqslant p.$ В приводимом ниже описании приближенного алгоритма построения оптимальной расстановки используется следующая процедура.

Процедура включения модуля контроля в цепочку рестарта. Пусть в цепочку рестарта (1.1) требуется включить дополнительный модуль контроля. Согласно (1.4), этот модуль контроля должен разбивать указанную цепочку на две цепочки так, чтобы длина максимальной из них была бы минимально возможной. Для этого вычисляются величины

Далее определяется номер ${{r}_{0}}$, $1 \leqslant {{r}_{0}} \leqslant n$, при котором величина $\Delta (r)$принимает минимальное значение, т.е.

Дополнительный модуль контроля присоединяется к прикладному модулю ${{w}_{{{{i}_{{{{r}_{0}}}}}}}}$. Процедура завершена.

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

Алгоритм 3.

Шаг 1. Присоединить модули контроля к прикладным модулям ${{w}_{{i{{N}_{i}}}}}$, $i = \overline {1,\;p} $.

Шаг 2. Положить $l = K - p$. Если l = 0, алгоритм завершен. Если $l > 0$, то l раз повторять шаг 3.

Шаг 3. Среди всех цепочек рестарта вида (1.1), содержащих более одного прикладного модуля $(n > 1)$, выбрать цепочку максимальной длины и выполнить для нее процедуру включения модуля контроля.

Алгоритм завершен.

Для определения вычислительной сложности алгоритма 3 отметим, что сложность шага 1 составляет $O(p)$, сложность вычисления длин цепочек рестарта и нахождения максимальной из них составляет

а сложность процедуры включения модуля контроля составляет и повторяется она K – p раз. Следовательно, сложность алгоритма 3 составляет т.е. алгоритм 3 имеет полиномиальную вычислительную сложность.

Для оценки точности алгоритма 3 может быть использовано неравенство (2.7), где T – длина максимальной цепочки рестарта, полученной после работы алгоритма, а

Аналогичный подход применим к П-сетям, т.е. к сетям, в которых помимо цепочек (2.8) есть еще два узла ${{w}_{0}}$ и ${{w}_{N}}$, связанные с узлами ${{w}_{{i1}}}$ и ${{w}_{{i{{N}_{i}}}}}$ отношениями предшествования ${{w}_{0}} \to {{w}_{{i1}}}$ и ${{w}_{{i{{N}_{i}}}}} \to {{w}_{N}}$, $i = \overline {1,\;p} $. В этом случае ${{P}_{0}} = \{ {{w}_{0}}\} ,$ ${{Q}_{0}} = \{ {{w}_{N}}\} $, $K \geqslant 1$.

Приведем еще один приближенный алгоритм, основанный на использовании алгоритма 2.

Алгоритм 4.

Шаг 1. Присоединить модули контроля к прикладным модулям ${{w}_{{i{{N}_{i}}}}}$, $i = \overline {1,\;p} $.

Шаг 2. Вычислить длины ${{T}_{i}}$, $i = \overline {1,\;p} $, всех цепочек вида (2.8).

Шаг 3. Каждой цепочке вида (2.8) дополнительно выделить k_i, $i = \overline {1,\;p} $, модулей контроля, где k_i вычисляется по следующим правилам:

a) ${{k}_{i}} \leqslant {{N}_{i}} - 1$;

б) величины k_i пропорциональны величинам T_i;

в) $\sum\limits_{i = 1}^p {{{k}_{i}}} = K - p$.

Шаг 4. В каждую цепочку вида (2.8) дополнительно включить k_i, $i = \overline {1,\;p} $, модулей контроля, применяя алгоритм 2. Алгоритм завершен.

Сложность алгоритма 4 составляет

или т.е. алгоритм 4 имеет полиномиальную вычислительную сложность.

Оценка точности вычисляется с помощью неравенства (2.7) при

2.3. Дерево, ориентированное от листьев к корню. Граф G имеет структуру дерева, ребра которого ориентированы от листьев к корню w_N. В данном случае ${{Q}_{0}} = \{ {{w}_{N}}\} $, ${{P}_{0}}$ – это множество всех листьев дерева. Каждый узел $w \in W$ дерева имеет два параметра: длительность $t(w)$ выполнения прикладного модуля w (заданная величина) и расстояние $s(w)$ (длина ориентированного пути) от w до ближайшего модуля контроля (вычисляется в ходе работы алгоритма). Приведем общее описание приближенного алгоритма построения оптимальной расстановки, а затем более подробно остановимся на каждом шаге алгоритма.

Алгоритм 5.

Шаг 1. Присоединить модуль контроля к корню дерева ${{w}_{N}}$.

Шаг 2. Для каждого узла $w \in W$ вычислить $s(w)$.

Шаг 3. Выполнять шаги 3.1, 3.2 $(K - 1)$ раз.

Шаг 3.1. Найти максимальную цепочку рестарта, состоящую более чем из одного узла, и выполнить процедуру включения в нее модуля контроля. Пусть модуль контроля был присоединен к прикладному модулю ${{w}_{{{{i}_{0}}}}} \in W$.

Шаг 3.2. Для каждого узла w цепочек рестарта, ведущих к узлу ${{w}_{{{{i}_{0}}}}}$, пересчитать величину $s(w)$.

Алгоритм завершен.

В результате работы алгоритма 5 будет построена расстановка $\overline W $ и вычислена величина

Приведем пояснения к шагам алгоритма 5.

1. Поскольку ${{Q}_{0}} = \{ {{w}_{N}}\} $, то модуль контроля присоединяется к прикладному модулю ${{w}_{N}}$.

2. Величины $s(w)$ для $w \in W$ вычисляются по следующим правилам: $s({{w}_{N}}) = t({{w}_{N}})$; если $\overline w \in P(w)$, то положить $s(\bar {w}) = s(w) + t(\bar {w})$.

3. После выполнения шага 2 величина $s(w)$ равна расстоянию от w до ближайшего модуля контроля.

3.1. Длина максимальной цепочки рестарта – это максимум величин $s(w)$ по всем $w \in W$, для которых либо $w \in {{P}_{0}}$, либо $\bar {w} \in \overline W $ для всех $\bar {w} \in P(w)$. Сама цепочка рестарта однозначно строится, следуя по ребрам дерева от w до ближайшего модуля контроля.

3.2. а) Положить $s(w) = s(w) - s({{w}_{{{{i}_{0}}}}}) + t({{w}_{{{{i}_{0}}}}})$ для каждого узла w, $w \ne {{w}_{{{{i}_{0}}}}}$, цепочек рестарта, ведущих к узлу ${{w}_{{{{i}_{0}}}}}$.

б) Положить $s({{w}_{{{{i}_{0}}}}}) = t({{w}_{{{{i}_{0}}}}})$.

Сложность алгоритма 5 составляет $O(NK)$, т.е. алгоритм имеет полиномиальную вычислительную сложность. Точность алгоритма 5 определяется с помощью оценки (2.7), где

2.4. Дерево, ориентированное от корня к листьям. Граф G имеет структуру дерева, ребра которого ориентированы от корня ${{w}_{N}}$ к листьям V, $V \subseteq W$. В этом случае ${{P}_{0}} = \{ {{w}_{N}}\} $, ${{Q}_{0}} = V$, $K \geqslant \left| V \right|$. Поэтому к каждому листу присоединяется модуль контроля, т.е. $V \subseteq \overline W $. Каждый узел $w \in W$ имеет три параметра: $t(w)$, $\sigma (w)$ и $w'(w)$. Как и прежде, $t(w)$ – длительность выполнения модуля w. Значения параметров $\sigma (w)$ и $w{\kern 1pt} '(w)$ определяются следующим образом. Если $w \notin \overline W $, то $\sigma (w)$ – это длина максимальной цепочки $w \to {{w}_{{{{i}_{1}}}}} \to \cdots \to {{w}_{{{{i}_{n}}}}} \to v$ при $n > 0$, где $v \in \overline W $, а ${{w}_{{{{i}_{j}}}}} \notin \overline W $, $j = \overline {1,\;n} $, т.е. $\sigma (w) = t(w) + t({{w}_{{{{i}_{1}}}}}) + ... + t({{w}_{{{{i}_{n}}}}}) + t(v)$, и $w{\kern 1pt} '(w) = {{w}_{{{{i}_{1}}}}}$. При $n = 0$ указанная цепочка имеет вид $w \to v$, и в этом случае $\sigma (w) = t(w) + t(v)$, $w{\kern 1pt} '(w) = v$. Если $w \in \overline W $, то $\sigma (w) = t(w)$ и $w{\kern 1pt} '(w) = w$. Значения параметров $\sigma (w)$ и $w{\kern 1pt} '(w)$ вычисляются в ходе работы алгоритма.

Перед тем, как дать общее описание приближенного алгоритма построения оптимальной расстановки, остановимся на некоторых его частях. Как отмечено выше, все листья $V$ дерева G включаются в $\overline W $, поскольку они не имеют непосредственных последователей. Вершины W дерева G разбиваются на непересекающиеся подмножества (уровни) ${{W}_{1}},\;{{W}_{2}},\; \cdots ,\;{{W}_{M}}$, ${{W}_{i}} \cap {{W}_{j}} = \emptyset $ при $i \ne j$:

следующим образом: ${{W}_{1}} = \{ {{w}_{N}}\} $, (т.е. каждый узел в ${{W}_{m}}$ является непосредственным последователем некоторого узла из ${{W}_{{m - 1}}}$). Отметим, что ${{W}_{M}} \subseteq V$ (т.е. каждый узел последнего уровня выступает листом).

Значения параметров $\sigma (w)$ и $w{\kern 1pt} '(w)$ узлов $w$ вычисляются следующим образом. Для $w \in \overline W $ полагаем

Отметим, что при этом будут рассчитаны значения параметров $\sigma (w)$ и $w{\kern 1pt} '(w)$ для всех узлов $w \in {{W}_{M}}$. Пусть далее значения параметров $\sigma (w)$ и $w{\kern 1pt} '(w)$ вычислены для всех узлов $w \in {{W}_{m}}$, $1 < m \leqslant M$. Для каждого узла $w \in {{W}_{{m - 1}}}{{\backslash }}V$ рассчитываем

Пусть этот максимум достигается при $\bar {w} = {{\bar {w}}_{0}}.$ Тогда полагаем

Перейдем к описанию приближенного алгоритма построения оптимальной расстановки.

Алгоритм 6.

Шаг 1. Включить в $\overline W $ все листья V дерева G.

Шаг 2. Вершины W разбить на уровни ${{W}_{1}},\;{{W}_{2}},\; \cdots ,\;{{W}_{M}}$.

Шаг 3. Вычислить величины $\sigma (w)$ и $w{\kern 1pt} '(w)$ для всех $w \in W$ по формулам (2.10), (2.11).

Выполнить шаги 4–8 ($K - \left| V \right|$) раз.

Шаг 4. Выбрать узел ${{w}_{{{{i}_{1}}}}} \in W{{\backslash }}\overline W $ с максимальной величиной $\sigma (w)$, что однозначно определяет цепочку рестарта максимальной длины

которая строится с помощью значений $w{\kern 1pt} '({{w}_{{{{i}_{j}}}}})$, $j = \overline {1,\;n - 1} $.

Шаг 5. Выполнить процедуру включения модуля контроля в цепочку (2.12). Пусть модуль контроля был присоединен к прикладному модулю ${{w}_{{i{}_{r}}}}$, $1 \leqslant r < n$.

Шаг 6. Включить ${{w}_{{i{}_{r}}}}$ в $\overline W $.

Шаг 7. Положить $\sigma ({{w}_{{{{i}_{r}}}}}) = t({{w}_{{{{i}_{r}}}}})$, $w{\kern 1pt} '({{w}_{{{{i}_{r}}}}}) = {{w}_{{{{i}_{r}}}}}$.

Шаг 8. Вычислить заново по формулам (2.10), (2.11) величины $\sigma ({{w}_{{{{i}_{j}}}}})$ и $w{\kern 1pt} '({{w}_{{{{i}_{j}}}}})$ для узлов ${{w}_{{{{i}_{{r - 1}}}}}},...,{{w}_{{{{i}_{1}}}}}$ в указанной последовательности.

Шаг 9. Искомой расстановкой является $\overline W $. Положить $T = \mathop {\max }\limits_{w \in W} \sigma (w)$.

Алгоритм завершен.

Вычислительная сложность шагов 1–9 составляет $O(N)$. Следовательно, сложность алгоритма 6 есть $O(N(K - \left| V \right|))$, т.е. алгоритм 6 имеет полиномиальную вычислительную сложность. Точность алгоритма 6 определяется с помощью оценки (2.7), где T* вычисляется по формуле (2.9).

2.5. Произвольный граф. В этом разделе предполагается, что $G$ – произвольный ориентированный граф, не содержащий циклов. Как и раньше, к каждому прикладному модулю $w \in {{Q}_{0}}$ прикрепляется модуль контроля. На каждой итерации предлагаемого ниже алгоритма определяется самая длинная цепочка рестарта, в которую затем включается модуль контроля. Для нахождения такой цепочки будет использована следующая модификация алгоритма дефекта [16, 17], определяющего поток минимальной стоимости в сети.

Пусть в графе G выделены два узла $w \in W{{\backslash }}\overline W $ и $\bar {w} \in \overline W $ и требуется найти самую длинную цепочку рестарта:

где ${{w}_{{{{i}_{j}}}}} \notin \overline W $, $j = \overline {1,\;n} $. Будем рассматривать граф G  как потоковую сеть с источником w и стоком $\bar {w}$. Добавим к сети G возвратную дугу $(\bar {w},\;w)$. Припишем каждой дуге $({{w}_{i}},\;{{w}_{j}}) \in A$ графа G три параметра: нижнюю границу $L({{w}_{i}},\;{{w}_{j}})$ потока по дуге, верхнюю границу $U({{w}_{i}},\;{{w}_{j}})$ потока по дуге и стоимость $C({{w}_{i}},\;{{w}_{j}})$ единицы потока по дуге. Значения параметров дуг сети G  приведены в табл. 1.

Алгоритм дефекта, работая с параметрами, указанными в таблице, построит самый длинный ориентированный путь из w в $\bar {w}$ [16, 17]. Этот путь определяется теми дугами (кроме возвратной дуги), поток по которым равен единице. Однако такой путь, помимо $\bar {w}$, может содержать и другие узлы из $\overline W $, и в этом случае он не будет цепочкой рестарта. Чтобы избежать этого, предлагается использовать следующую простую модификацию алгоритма дефекта. При построении увеличивающего пути из w в $\bar {w}$ нельзя использовать узлы из $\overline W $. А в остальном алгоритм работает так же, как алгоритм дефекта. Перейдем к описанию приближенного алгоритма построения оптимальной расстановки.

Алгоритм 7

Шаг 1. Включить ${{Q}_{0}}$ в $\overline W $.

Выполнять шаги 2–4 $(K - \left| {{{Q}_{0}}} \right|)$ раз.

Шаг 2. Для каждой пары узлов w, $\bar {w}$ ($w \notin \overline W $, $\bar {w} \in \overline W ,$ кроме того, либо $w \in {{P}_{0}}$, либо w имеет одного или нескольких предшественников, если $w{\kern 1pt} ' \to w$, то $w{\kern 1pt} ' \in \overline W $) с помощью модифицированного алгоритма дефекта найти самый длинный путь (2.13). Этот путь является самой длинной цепочкой рестарта.

Шаг 3. Применить процедуру включения модуля контроля в построенную на шаге 3 цепочку рестарта. Пусть в результате этой процедуры модуль контроля был прикреплен к прикладному модулю ${{w}_{{{{i}_{j}}}}}$.

Шаг 4. Добавить ${{w}_{{{{i}_{j}}}}}$ к $\overline W $.

Шаг 5. Расстановка $\overline W $ построена. С помощью процедуры, описанной на шаге 2, вычислить величину

Алгоритм завершен.

В результате работы алгоритма будет построена расстановка $\overline W $, являющаяся приближением к оптимальной. Вычислительная сложность отдельных шагов алгоритма следующая: шаг 1 – $O(N)$; шаг 2 – $O({{\left| A \right|}^{2}}KN)$, где |A| – число дуг в сети G; шаг 3 – $O(N)$; шаг 4 – $O(1)$. Таким образом, сложность алгоритма 7 составляет $O({{\left| A \right|}^{2}}KN(K - \left| {{{Q}_{0}}} \right|))$, т.е. алгоритм 7 имеет полиномиальную вычислительную сложность. Пусть ${{T}_{{\max }}}$– длина самого длинного пути в графе $G$. Пусть далее

если $K > \left| {{{Q}_{0}}} \right|$, и $T{\kern 1pt} * = {{T}_{{\max }}}$, если $K = \left| {{{Q}_{0}}} \right|$. Для определения отклонения величины $T(\overline W )$ от T_opt применима оценка $T(\overline W ) - {{T}_{{opt}}} \leqslant T(\overline W ) - T{\kern 1pt} *$, которая может быть вычислена после работы алгоритма.

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