Известия РАН. Теория и системы управления, 2020, № 4, стр. 83-91

Планирование вычислений в многопроцессорной системе с неопределенными моментами готовности работ

М. Г. Фуругян *

Федеральный исследовательский центр “Информатика и управление” РАН
Москва, Россия

* E-mail: rtsccas@yandex.ru

Поступила в редакцию 10.02.2020
После доработки 26.02.2020
Принята к публикации 30.03.2020

Полный текст (PDF)

Аннотация

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

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

Задачи распределения ресурсов и построения расписаний при наличии неопределенных факторов рассматривались ранее рядом авторов. В [1] описывалась минимаксная задача теории расписаний при нефиксированных длительностях работ, для решения которой был разработан метод построения областей устойчивости оптимальных расписаний. В [2] дополнительно предполагается возможность динамического изменения структуры сети, задающей частичный порядок работ. Задача минимизации времени выполнения сетевого комплекса работ в случае, когда длительности работ являются функциями от вектора распределения ресурсов, а число процессоров не ограничено, исследовалась в [3] и была сведена к задаче нелинейного программирования. В [4] рассматривалась задача минимизации числа процессоров заданной производительности при фиксированных интервалах выполнения работ и известных издержках на переключения процессоров между заданиями. В некоторых случаях задачи распределения ресурсов с нефиксированными параметрами сводятся к сетевым задачам, методы решения которых описаны в [57]. В [8] описывалась задача распределения невозобновляемых ресурсов при наличии неопределенных факторов и для ее решения была использована методика построения многогранников устойчивости, разработанная в [1, 2]. Приведенная в [8] задача является NP-трудной, и предложенный алгоритм ее решения имеет переборный характер. В настоящей статье предполагается, что каждая работа закреплена за определенным процессором, а на множестве работ задано отношение частичного порядка их выполнения. Благодаря этому множество допустимых расписаний описывается с помощью полиномиального алгоритма. С использованием этого множества строится антагонистическая игра, решение которой определяет решение исходной задачи.

1. Постановка задачи. Рассматривается вычислительная система, состоящая из m процессоров, и совокупность работ (заданий) $W = \{ {{w}_{{ij}}}{\text{:}}\;i = \overline {1,{{k}_{j}},} \;j = \overline {1,m} \} $, подлежащих выполнению, kj – заданная величина, равная числу работ, приписанных процессору j, $j = \overline {1,m} $. Работа wij приписана процессору j, т.е. выполняется этим процессором. Таким образом, множество работ W разбито на m групп, каждая из которых исполняется определенным процессором. При этом не допускаются прерывания и переключения с одного процессора на другой. Задан общий директивный интервал [0, T] для всех заданий, т.е. завершить каждую работу необходимо не позднее момента времени T. Длительность работы wij составляет $t({{w}_{{ij}}}) = {{t}_{{ij}}}$, ${{t}_{{ij}}} \leqslant T$. На множестве W задан ориентированный граф без циклов G = (W, A), определяющий частичный порядок выполнения работ, где W – множество узлов, A – множество ориентированных дуг. Если $(w,\bar {w}) \in A,$ то работа $\bar {w}$ может быть начата только после завершения работы w. В этом случае будем использовать обозначение $w \to \bar {w}$. Работа w является непосредственным предшественником работы $\bar {w},$ а $\bar {w}$ – непосредственным последователем работы w. Предполагается, что задания, приписанные одному и тому же процессору j, упорядочены следующим образом:

(1.1)
${{w}_{{1j}}} \to {{w}_{{2j}}} \to \; \ldots \; \to {{w}_{{{{k}_{j}}j}}}.$

Кроме того, каждая работа может иметь непосредственных предшественников, приписанных другим процессорам.

В некоторые неопределенные моменты времени ${{y}_{{hj}}} \in [0,T]$, $h = \overline {1,{{p}_{j}}} $, $j = \overline {1,m} $, pj – заданные величины, $0 \leqslant {{y}_{{1j}}} < {{y}_{{2j}}} < \; \ldots \; < {{y}_{{{{p}_{j}}j}}} \leqslant T$, могут поступать запросы на выполнение дополнительных, более приоритетных, работ $V = \{ {{{v}}_{{hj}}}{\text{:}}\;h = \overline {1,{{p}_{j}},} \;j = \overline {1,m} \} $. Каждая работа ${{{v}}_{{hj}}}$ приписана процессору j, не допускает прерываний и переключений на другие процессоры, а ее длительность составляет shj, ${{s}_{{hj}}} < T$. Таким образом, работа ${{{v}}_{{hj}}}$ выполняется в интервале $[{{y}_{{hj}}},{{y}_{{hj}}} + {{s}_{{hj}}}]$. (Предполагается, что ${{y}_{{hj}}} + {{s}_{{hj}}} \leqslant {{y}_{{h + 1,j}}}$). Если в этом интервале исполняется некоторая работа wij, то она прекращается и переносится на более позднее время. Тем самым нарушается построенное ранее расписание работ W. Процесс выполнения множества заданий W и поступления запросов на дополнительные работы V повторяется многократно. Задача заключается в выработке стратегии построения таких расписаний работ W, которые удовлетворяют следующим условиям.

1. Каждое задание wij выполняется процессором  j.

2. Не нарушаются ограничения частичного порядка выполнения работ W, задаваемые графом G.

3. Если в интервале [0, T] не поступило ни одного запроса на выполнение дополнительных работ V, то все работы W завершаются не позднее момента времени T.

4. Вероятность того, что расписание заданий W будет нарушено вследствие поступления запросов на выполнение дополнительных работ V, минимальна.

Расписание для работ W, при котором не нарушаются условия 1–3, называется допустимым. Таким образом, задача заключается в выработке стратегии построения допустимого расписания для заданий W, при которой выполняется условие 4.

2. Некоторые определения и обозначения. Введем следующие обозначения:

P(w) – множество непосредственных предшественников работы $w \in W$, т.е. P(w) = = $\{ w{\text{'}} \in W:w{\text{'}} \to w\} $;

$\bar {P}(w)$ – множество всех заданий из W, завершение которых должно предшествовать началу выполнения работы w, т.е. $\bar {P}(w)$ – это множество работ $\tilde {w} \in W,$ для которых в графе G существует ориентированный путь, ведущий из $\tilde {w}$ в w;

Q(w) – множество непосредственных последователей работы w, т.е. $Q(w) = \{ w{\text{'}} \in W:w \to w{\text{'}}\} $;

$\bar {Q}(w)$ – множество всех заданий из W, началу выполнения которых должно предшествовать завершение работы w, т.е. $\bar {Q}(w)$ – это множество работ $\tilde {w} \in W$, для которых в графе G существует ориентированный путь, ведущий из w в $\tilde {w}$.

Отметим, что $P(w) \subseteq \bar {P}(w)$ и $Q(w) \subseteq \bar {Q}(w)$. Кроме того, если $w{\text{'}} \in P(w)$, $\tilde {w} \in \bar {P}(w{\text{'}})$ и $\tilde {w} \in P(w)$, то дугу ($\tilde {w}$, $w$) можно удалить из графа G, так как это не приведет к изменению частичного порядка исполнения работ W. Будем предполагать, что такая процедура коррекции графа G уже проведена.

Для работы ${{w}_{{ij}}} \in W$ символами $\tau ({{w}_{{ij}}}) = {{\tau }_{{ij}}}$ и $\theta ({{w}_{{ij}}}) = {{\theta }_{{ij}}}$ будем обозначать соответственно наиболее ранний возможный и наиболее поздний допустимый сроки начала выполнения. Иными словами, работа w не может быть начата раньше момента времени $\tau (w)$ (так как не будут завершены все ее предшественники) и позднее момента времени $\theta (w)$ (так как в этом случае некоторые из ее последователей не успеют завершиться к директивному сроку T).

Далее, поскольку граф G не содержит ориентированных циклов, то вершины W можно разбить на уровни следующим образом. В нулевой уровень W0 включим все вершины $w \in W$, которые не имеют непосредственных предшественников, т.е.

(2.1)
${{W}_{0}} = \{ w \in W:P(w) = \emptyset \} .$

В первый уровень W1 войдут вершины $w \in W$, все непосредственные предшественники которых содержатся в W0, т.е.

(2.2)
${{W}_{1}} = \{ w \in W:P(w) \subseteq {{W}_{0}}\} .$

В общем случае, в уровень Wl, $l = \overline {1,L} $, входят вершины $w \in W{\backslash }\{ {{W}_{0}} \cup {{W}_{1}} \cup \ldots \cup {{W}_{{l - 1}}}\} $, все непосредственные предшественники которых содержатся в ${{W}_{0}} \cup {{W}_{1}} \cup \ldots \cup {{W}_{{l - 1}}}$, т.е.

(2.3)
${{W}_{l}} = \left\{ {w \in W{\backslash }\bigcup\limits_{r = 0}^{l - 1} {{{W}_{r}}} :P(w) \subseteq \bigcup\limits_{r = 0}^{l - 1} {{{W}_{r}}} } \right\},\quad l = \overline {1,L} .$

В дальнейшем будем также использовать другое разбиение множества вершин W графа G на уровни. А именно в нулевой уровень ${{\bar {W}}_{0}}$ включим все вершины $w \in W$, которые не имеют непосредственных последователей, т.е.

(2.4)
${{\bar {W}}_{0}} = \{ w \in W:Q(w) = \emptyset \} .$

В первый уровень ${{\bar {W}}_{1}}$ войдут вершины $w \in W$, все непосредственные последователи которых содержатся в ${{\bar {W}}_{0}}$, т.е.

(2.5)
${{\bar {W}}_{1}} = \{ w \in W:Q(w) \subseteq {{\bar {W}}_{0}}\} .$

В общем случае, в уровень ${{\bar {W}}_{l}}$, $l = \overline {1,L} $, входят вершины $w \in W{\backslash }\{ {{\bar {W}}_{0}} \cup {{\bar {W}}_{1}} \cup \ldots \cup {{\bar {W}}_{{l - 1}}}\} $, все непосредственные последователи которых содержатся в ${{\bar {W}}_{0}} \cup {{\bar {W}}_{1}} \cup \ldots \cup {{\bar {W}}_{{l - 1}}}$, т.е.

(2.6)
${{\bar {W}}_{l}} = \left\{ {w \in W{\backslash }\bigcup\limits_{r = 0}^{l - 1} {{{{\bar {W}}}_{r}}} :Q(w) \subseteq \bigcup\limits_{r = 0}^{l - 1} {{{{\bar {W}}}_{r}}} } \right\},\quad l = \overline {1,L.} $

Отметим, что разбиение множества W на уровни Wl и ${{\bar {W}}_{l}}$, $l = \overline {0,L} $, возможно, поскольку граф G не содержит ориентированных циклов.

Эти разбиения множества W будем использовать для вычисления величин $\tau (w)$ и $\theta (w)$, $w \in W$. Величины $\tau (w)$, $w \in W,$  вычисляются последовательно сначала для W0, затем для W1 и т.д. следующим образом. Если $w \in {{W}_{0}}$, то

(2.7)
$\tau (w) = 0.$

Если $w \in {{W}_{l}}$, $l = \overline {1,L} $, то

(2.8)
$\tau (w) = \mathop {\max }\limits_{{{w}_{{ij}}} \in P(w)} \{ {{\tau }_{{ij}}} + {{t}_{{ij}}}\} .$

Величины $\theta (w)$, $w \in W,$  также вычисляются последовательно сначала для ${{\bar {W}}_{0}}$, затем для ${{\bar {W}}_{1}}$ и т.д. следующим образом. Если $w \in {{\bar {W}}_{0}}$, то

(2.9)
$\theta (w) = T - t(w).$

Если $w \in {{\bar {W}}_{l}}$, $l = \overline {1,L} $, то

(2.10)
$\theta (w) = \mathop {\min }\limits_{{{w}_{{ij}}} \in Q(w)} \{ {{\theta }_{{ij}}} - t(w)\} .$

Лемма 1. Допустимое расписание существует в том и только том случае, когда

(2.11)
${{\tau }_{{{{k}_{j}}j}}} \leqslant {{\theta }_{{{{k}_{j}}j}}}$
при всех $j = \overline {1,m} $.

Доказательство. 1. Пусть верно неравенство (2.11). Покажем сначала, что существует расписание работ W, при котором каждое задание $w \in W$ начинает выполняться в момент $\tau (w)$. Действительно, все работы из W0 не имеют предшественников, и в силу (1.1) назначены на различные процессоры. Следовательно, каждое задание $w \in {{W}_{0}}$ может быть начато в момент $\tau (w) = 0$. Пусть далее это утверждение доказано для всех работ из Wl, $1 \leqslant l < L$. Тогда в силу (2.8) для каждой работы ${{w}_{{ij}}} \in {{W}_{{l + 1}}}$ к моменту времени τij завершены все ее предшественники, а в силу (1.1) в момент времени τij процессором  j может выполняться только работа wij. Таким образом, существует расписание, при котором момент начала каждой работы wij равен τij. А в силу (2.11) это расписание является допустимым.

2. Предположим теперь, что существует допустимое расписание. Как было показано выше, существует расписание, при котором каждое задание wij начинает выполняться в момент ${{\tau }_{{ij}}}$. Следовательно, это расписание также является допустимым, откуда следует (2.11). Лемма доказана.

3. Построение антагонистической игры. Пусть xij – момент начала работы wij, причем справедливы неравенства (2.11) леммы 1 и условия 1–3 из разд. 1. Пусть далее $X = \{ {{x}_{{ij}}}{\text{:}}\;i = \overline {1,{{k}_{j}}} ,j = \overline {1,m} \} $. Множество X описывает все возможные моменты начала выполнения работ W, при которых существует допустимое расписание, и строится следующим образом. Для ${{w}_{{ij}}} \in {{W}_{0}}$

(3.1)
${{x}_{{ij}}} \in [{{\tau }_{{ij}}};{{\theta }_{{ij}}}].$

Для ${{w}_{{ij}}} \in {{W}_{l}}$, $l = \overline {1,L} $,

(3.2)
${{x}_{{ij}}} \in \left[ {\mathop {\max }\limits_{{{w}_{{pq}}} \in P({{w}_{{ij}}})} ({{x}_{{pq}}} + {{t}_{{pq}}});{{\theta }_{{ij}}}} \right].$

Каждый элемент xX определяет допустимое расписание Sx, при котором момент начала работы wij равен xij (здесь $x = \{ {{x}_{{ij}}}\} $). Пусть $Y = \{ {{y}_{{hj}}}{\text{:}}\;h = \overline {1,{{p}_{j}}} ,j = \overline {1,m} $ : $0 \leqslant {{y}_{{1j}}} < {{y}_{{2j}}} < \ldots . < {{y}_{{{{p}_{j}}j}}} \leqslant T\} $. Множество Y описывает все возможные моменты поступления запросов на выполнение дополнительных работ V.

На множестве X × Y будем рассматривать антагонистическую игру с платежной функцией $K(x,y)$, $x \in X$, $y \in Y$, определенной следующим образом:

(3.3)
$K(x,y) = \left\{ \begin{gathered} 1,\quad {\text{если}}\quad {{x}_{{ij}}} + {{t}_{{ij}}} < {{y}_{{hj}}}\quad {\text{или}}\quad {{x}_{{ij}}} \geqslant {{y}_{{hj}}} + {{s}_{{hj\quad }}}{\text{при}}\;{\text{всех}} \hfill \\ j = \overline {1,m} ,\quad i = \overline {1,{{k}_{j}}} ,\quad h = \overline {1,{{p}_{j}}} ; \hfill \\ 0\quad {\text{в}}\;{\text{противном}}\;{\text{случае}}{\text{.}} \hfill \\ \end{gathered} \right.$

Иными словами, если для каждого $j = \overline {1,m} $ выполнение ни одной из дополнительных работ ${{{v}}_{{hj}}}$ не препятствует исполнению ни одного задания wij, т.е. если интервалы $[{{x}_{{ij}}}{\text{;}}{{x}_{{ij}}} + {{t}_{{ij}}}]$ и $[{{y}_{{hj}}};{{y}_{{hj}}} + {{s}_{{hj}}})$ не пересекаются, то $K(x,y) = 1$. Если же для некоторого j, $1 \leqslant j \leqslant m$, выполнение хотя бы одной дополнительной работы ${{{v}}_{{hj}}}$ препятствует исполнению хотя бы одного задания wij, т.е. если хотя бы два интервала $\left[ {{{x}_{{ij}}}{\text{;}}\;{{x}_{{ij}}} + {{t}_{{ij}}}} \right]$ и $\left[ {{{y}_{{hj}}};\;{{y}_{{hj}}} + {{s}_{{hj}}}} \right)$ пересекаются, то $K(x,y) = 0$.

Если $K(x,y) = 1$ то работы V могут быть выполнены так, что при этом расписание Sx для заданий W не будет нарушено. Если же $K(x,y) = 0$, то работы W не могут быть выполнены по расписанию Sx. Пусть $\nu (x)$ – некоторая смешанная стратегия первого игрока в игре с платежной функцией $K(x,y)$, $x \in X$, $y \in Y$. Тогда при фиксированном $y \in Y$ величина

$\int\limits_X {K(x,y)d\nu (x)} $
равна вероятности того, что расписание заданий W не будет нарушено вследствие поступления запросов на выполнение дополнительных работ V. Оптимальная смешанная стратегия $\nu {\text{*}}(x)$ первого игрока максимизирует величину
$\mathop {\inf }\limits_{y \in Y} \int\limits_X {K(x,y)d\nu (x)} $
и определяет искомую стратегию построения расписаний Sx. Метод решения антагонистической игры (3.3), основанный на аппроксимации ее конечными играми, описан в [9].

4. Частный случай рассматриваемой задачи. В [9] описан метод решений антагонистических игр с полунепрерывной платежной функцией, имеющей разрыв на конечном числе поверхностей, разбивающих множество чистых стратегий игроков на области, в которых функция выигрыша является равностепенно непрерывной. Однако игра с платежной функцией (3.3) представляет собой частный случай таких игр, для которого будет описан более эффективный метод решения. Так же, как и в [9], метод основан на дискретной аппроксимации исходной игры конечной игрой.

Будем рассматривать случай, когда имеется один процессор (m = 1), одна основная работа w (k1 = 1) и поступает один запрос на выполнение дополнительной работы ${v}$ (p1 = 1). Далее, пусть t и s – длительности основной и дополнительной работ соответственно, [0; T] – директивный интервал, $t < T$, s < T. Пусть x – момент начала работы w, а y – момент поступления запроса на выполнение работы ${v}$. Тогда, согласно (3.3), платежная функция K(x, y) определяется следующим образом:

(4.1)
$K(x,y) = \left\{ \begin{gathered} 1,\quad {\text{если}}\quad y > x + t\quad {\text{или}}\quad y \leqslant x - s, \hfill \\ 0,\quad {\text{если}}\quad x - s < y \leqslant x + t, \hfill \\ \end{gathered} \right.$
где $x \in X$, $y \in Y$, $X = [0;T]$, $Y = [0;T]$.

Таким образом, платежная функция K(x, y) может принимать только два значения 0 и 1, и имеет разрыв по прямым y = x + t и y = xs.

Аппроксимируем игру (4.1) конечной игрой с конечными множествами чистых стратегий $\bar {X} \subseteq X$, $\bar {Y} \subseteq Y$. Для этого построим числовые последовательности $\{ x_{i}^{l}\} $ и $\{ y_{i}^{l}\} $, $l = \overline {1,4} $, $x_{i}^{l} \in (0;T)$, $y_{i}^{l} \in (0;T)$, элементы которой вычисляются с помощью следующих рекуррентных соотношений:

$x_{1}^{1} = s,\quad x_{{i + 1}}^{1} = x_{i}^{1} + (t + s),\quad i = \overline {1,{{u}_{1}},} $
$y_{1}^{1} = t + s,\quad y_{{j + 1}}^{1} = y_{j}^{1} + (t + s),\quad j = \overline {1,{{{v}}_{1}},} $
$x_{1}^{2} = T - t,\quad x_{{i + 1}}^{2} = x_{i}^{2} - (t + s),\quad i = \overline {1,{{u}_{2}},} $
$y_{1}^{2} = T - (t + s),\quad y_{{j + 1}}^{2} = y_{j}^{2} - (t + s),\quad j = \overline {1,{{{v}}_{2}},} $
$x_{1}^{3} = t + s,\quad x_{{i + 1}}^{3} = x_{i}^{3} + (t + s),\quad i = \overline {1,{{u}_{3}},} $
$y_{1}^{3} = t,\quad y_{{j + 1}}^{3} = y_{j}^{3} + (t + s),\quad j = \overline {1,{{{v}}_{3}},} $
$x_{1}^{4} = T - (t + s),\quad x_{{i + 1}}^{4} = x_{i}^{4} - (t + s),\quad i = \overline {1,{{u}_{4}},} $
$y_{1}^{4} = T - s,\quad y_{{j + 1}}^{4} = y_{j}^{4} - (t + s),\quad j = \overline {1,{{{v}}_{4}}.} $

Здесь ul, ${{{v}}_{l}}$, $l = \overline {1,4} $, – величины, не превосходящие $[T{\text{/}}(t + s)]$. Пары чисел ($x_{i}^{l}$; $y_{i}^{l}$), $l = \overline {1,4} $, являются координатами некоторых точек квадрата $[0,T] \times [0,T]$, лежащих на прямых $y = x + t$ и $y = x - s$ (см. рис. 1). Например, пары ($x_{i}^{1}$, $y_{i}^{1}$) соответствуют точкам с координатами (s, 0), (s, t + s), ($t + 2s$, $t + s$), ($t + 2s$, $2t + 2s$), ($2t + 3s$, $2t + 2s$) и т.д., лежащим на указанных выше прямых.

Рис. 1.

Платежная функция $K(x,y)$ и множества $\bar {X}$ и $\bar {Y}$ при T = 3, $t = 1$, s = 1

Построим следующие конечные подмножества $\bar {X}$ и $\bar {Y}$ множеств X и Y соответственно: $\bar {X} = \{ 0,T,x_{i}^{l},l = \overline {1,4} ,$, i = 1, 2, ...}, $\bar {Y} = \{ 0,T,y_{i}^{l},\;l = \overline {1,4} ,\;i = 1,2,\; \ldots \} $. Перенумеруем элементы множеств $\bar {X}$ и $\bar {Y}$ так, что X = $\{ 0 = {{x}_{1}} < {{x}_{2}} < \ldots < {{x}_{{r - 1}}} < {{x}_{r}} = T\} $, $\bar {Y} = \{ 0 = {{y}_{1}} < {{y}_{2}} < \; \ldots \; < {{y}_{{{v} - 1}}} < {{y}_{{v}}} = T\} $. На рис. 1 указаны множества $\bar {X}$ и $\bar {Y}$ для случая, когда T = 3, t = 1, s = 1. При этом платежная функция K(x, y) имеет разрывы по прямым $y = x + 1$ и $y = x - 1$; $\bar {X} = \{ {{x}_{1}} = 0,\;{{x}_{2}} = 1,\;{{x}_{3}} = 2,\;{{x}_{4}} = 3\} $, $\bar {Y} = \{ {{y}_{1}} = 0$, y2 = 1, y3 = 2, y4 = 3}, $K(x,y) = 1$ при $y > x + 1$ и $y \leqslant x - 1$, $K(x,y) = 0$ при $x - 1 < y \leqslant x + 1$.

Лемма 2. 1. Для любых ${{x}_{i}},\;{{x}_{{i + 1}}} \in \bar {X}$, ${{y}_{j}},\;{{y}_{{j + 1}}} \in \overline Y $ и любого $x \in ({{x}_{i}},{{x}_{{i + 1}}})$ справедливы равенства $K(x,{{y}_{j}}) = K({{x}_{i}},{{y}_{j}})$, $K(x,{{y}_{{j + 1}}}) = K({{x}_{i}},{{y}_{{j + 1}}})$.

2. Для любых ${{x}_{i}},{{x}_{{i + 1}}} \in \bar {X}$, ${{y}_{j}},{{y}_{{j + 1}}} \in \bar {Y}$ и любого $y \in ({{y}_{j}},{{y}_{{j + 1}}})$ верны равенства K(xi, y) = K(xi, ${{y}_{{j + 1}}})$, $K({{x}_{{i + 1}}},y) = K({{x}_{{i + 1}}},{{y}_{{j + 1}}})$.

Доказательство. Из построения множеств $\bar {X}$ и $\bar {Y}$ и определения функции $K(x,y)$ следует, что при всех $x \in \left[ {{{x}_{i}},{{x}_{{i + 1}}}} \right)$ функция $K(x,{{y}_{j}})$ принимает одно и то же значение (0 или 1). То же самое относится к функции $K(x,{{y}_{{j + 1}}})$, а также и к функциям $K({{x}_{i}},y)$ и $K({{x}_{{i + 1}}},y)$ при $y \in \left( {{{y}_{j}},{{y}_{{j + 1}}}} \right]$. Лемма доказана.

Пусть ($K(x,y)$, $\bar {X}$, $\bar {Y}$) – конечная (матричная) игра с платежной функцией K(x, y) на множествах чистых стратегий $\bar {X}$ и $\bar {Y}$ первого и второго игроков соответственно. Пусть $\tilde {V}$ – значение этой игры, а $p = ({{p}_{1}},{{p}_{2}},\; \ldots ,\;{{p}_{r}})$ и $q = ({{q}_{1}},{{q}_{2}},\; \ldots ,\;{{q}_{r}})$ – оптимальные смешанные стратегии первого и второго игроков соответственно, т.е. при всех $j = \overline {1,{v}} $, $i = \overline {1,r} $ выполнены следующие неравенства:

(4.2)
$\sum\limits_{i = 1}^r {K({{x}_{i}},} {{y}_{j}}){{p}_{i}} \geqslant \tilde {V},\quad \sum\limits_{j = 1}^v {K({{x}_{i}},} {{y}_{j}}){{q}_{j}} \leqslant \tilde {V}.$

Определим вероятностную меру ν(x), заданную на X и сосредоточенную в точках xi, в которых она имеет скачки ${{p}_{i}}$, $i = \overline {1,r} $, и вероятностную меру $\mu (y)$, определенную на Y и сосредоточенную в точках yj, в которых она имеет скачки ${{q}_{j}}$, $j = \overline {1,v} $. Тогда из (4.2) следует, что при всех $y \in \bar {Y}$, $x \in \bar {X}$ справедливы неравенства

$\int\limits_X {K(x,y)d\nu (x) \geqslant \tilde {V}} ,\quad \int\limits_Y {K(x,y)d\mu (y) \leqslant \tilde {V}} .$

Пусть $y \in Y$ и $y \in ({{y}_{j}},{{y}_{{j + 1}}}).$ В силу леммы 2 $K({{x}_{i}},y) = K({{x}_{i}},{{y}_{{j + 1}}})$ при всех $i = \overline {1,r} $. Следовательно,

$\int\limits_X {K(x,y)d\nu (x) = \sum\limits_{i = 1}^r {K({{x}_{i}},} y){{p}_{i}} = \sum\limits_{i = 1}^r {K({{x}_{i}},} {{y}_{{j + 1}}}){{p}_{i}} \geqslant \tilde {V}.} $

Аналогично если $x \in X$ и $x \in ({{x}_{i}},{{x}_{{i + 1}}})$, то $K(x,{{y}_{j}}) = K({{x}_{{i + 1}}},{{y}_{j}})$ при всех $j = \overline {1,{v}} $. Поэтому

$\int\limits_Y {K(x,y)d\mu (x) = \sum\limits_{j = 1}^{v} {K({{x}_{i}},} {{y}_{j}}){{q}_{j}} = \sum\limits_{j = 1}^{v} {K({{x}_{i}},} {{y}_{j}}){{q}_{j}} \leqslant \tilde {V}.} $

Следовательно, ($\nu (x)$, $\mu (y)$, $\tilde {V}$) – решение игры ($K(x,y)$, X, Y), Таким образом, решение исходной игры сведено к решению конечной игры ($K(x,y)$, $\bar {X}$, $\bar {Y}$).

5. Модельный пример. Рассмотрим пример, когда число процессоров равно m = 2, множество заданий $W = \{ {{w}_{{11}}},{{w}_{{21}}},{{w}_{{31}}},{{w}_{{12}}}\} $ (работы w11, w21, w31 выполняются первым процессором, а работа w12 – вторым). Длительности работ и директивный срок следующие: ${{t}_{{11}}} = 1$, ${{t}_{{21}}} = 1$, ${{t}_{{31}}} = 2$, ${{t}_{{12}}} = 1$, $T = 6$. Дополнительная работа одна – ${{{v}}_{{12}}}$; выполняется она вторым процессором и ее длительность составляет ${{s}_{{12}}} = 1$. Запрос на выполнение работы ${{{v}}_{{12}}}$ может поступить в неопределенный момент времени ${{y}_{{12}}} \in [0;\;6]$. Граф частичного порядка на множестве W задается следующими отношениями предшествования: ${{w}_{{11}}} \to {{w}_{{21}}} \to {{w}_{{31}}}$ и ${{w}_{{12}}} \to {{w}_{{21}}}$ (рис. 2).

Рис. 2.

Граф частичного порядка G

Разбиения множества W на уровни ${{W}_{l}}$ и ${{\bar {W}}_{l}}$, $l = \overline {0,L} $, построенные по формулам (2.1)(2.6), следующие: ${{W}_{0}} = \{ {{w}_{{11}}},{{w}_{{12}}}\} $, ${{W}_{1}} = \{ {{w}_{{21}}}\} $, ${{W}_{2}} = \{ {{w}_{{31}}}\} $, ${{\bar {W}}_{0}} = \{ {{w}_{{31}}}\} $, ${{\bar {W}}_{1}} = \{ {{w}_{{21}}}\} $, ${{\bar {W}}_{2}} = \{ {{w}_{{11}}},{{w}_{{12}}}\} $. Наиболее ранние возможные и наиболее поздние допустимые сроки начала выполнения заданий W, вычисленные по формулам (2.7)(2.10), соответственно равны ${{\tau }_{{11}}} = {{\tau }_{{12}}} = 0$, ${{\tau }_{{21}}} = 1$, ${{\tau }_{{31}}} = 2$, ${{\theta }_{{31}}} = 4$, ${{\theta }_{{21}}} = 3$, ${{\theta }_{{12}}} = {{\theta }_{{11}}} = 2$. С помощью формул (3.1), (3.2) построим множество X:

$X = \left\{ {{{x}_{{11}}} \in [0,2],\;{{x}_{{12}}} \in [0,2],\;{{x}_{2}}_{1} \in [\max ({{x}_{{11}}} + 1,\;{{x}_{{12}}} + 1);\;3],\;{{x}_{{31}}} \in [{{x}_{{21}}} + 1;\;4]} \right\}.$

Коллизия при запросе на дополнительную работу ${{{v}}_{{12}}}$ может возникнуть только при выполнении задания w12, так как ${{{v}}_{{12}}}$ и w12 должны исполняться на одном и том же процессоре (втором). Платежная функция (4.1) антагонистической игры выглядит следующим образом:

(5.1)
$K({{x}_{{12}}},{{y}_{{12}}}) = \left\{ \begin{gathered} 1,\quad {\text{если}}\quad {{x}_{{12}}} + 1 < {{y}_{{12}}}\quad {\text{или}}\quad {{x}_{{12}}} \geqslant {{y}_{{12}}} + 1; \hfill \\ 0,\quad {\text{если }}{{x}_{{{\text{12}}}}} - 1 < {{y}_{{12}}} \leqslant {{x}_{{12}}} + 1, \hfill \\ \end{gathered} \right.$
${{x}_{{12}}} \in X = [0,2]$, ${{y}_{{12}}} \in Y = [0,6]$. В данном случае множество X × Y является не квадратом, как рассматривалось в разд. 4, а прямоугольником. Однако все рассуждения, проведенные в разд. 4, справедливы и в этом случае. Множества $\bar {X}$ и $\bar {Y}$ выглядят следующим образом: $\bar {X} = \{ 0,1,2\} $, $\bar {Y}$ = = {0, 1, 2, 3, 6}, r = 3, ${v} = 5$.

На рис. 3 приведено схематическое изображение платежной функции $K({{x}_{{12}}},{{y}_{{12}}})$. Пусть ${{\nu }_{a}}({{x}_{{12}}})$, ${{\mu }_{a}}({{y}_{{12}}})$ – вероятностные меры на [0; 2] и [0; 6] соответственно, сосредоточенные в одной точке a, в которой они имеют скачок, равный единице. Пусть далее ν*(x12) = 0.5ν0(x12) + + $0.5{{\nu }_{2}}({{x}_{{12}}})$, $\mu {\text{*}}({{x}_{{12}}}) = 0.5{{\mu }_{0}}({{x}_{{12}}}) + 0.5{{\mu }_{2}}({{x}_{{12}}})$, т.е. вероятностные меры $\nu {\text{*}}({{x}_{{12}}})$ и $\mu {\text{*}}({{y}_{{12}}})$ сосредоточены в двух точках 0 и 2, в которых они имеют скачки, равные 0.5. Тогда справедливы следующие соотношения:

$\int\limits_{[0;2]} {K({{x}_{{12}}},} {{y}_{{12}}})d\nu {\text{*}}({{x}_{{12}}}) \geqslant 0.5$
при всех ${{y}_{{12}}} \in [0;6]$,
$\int\limits_{[0;6]} {K({{x}_{{12}}},} {{y}_{{12}}})d\mu {\text{*}}({{y}_{{12}}}) \leqslant 0.5$
при всех ${{x}_{{12}}} \in [0;2]$.

Рис. 3.

Платежная функция антагонистической игры в модельном примере

Следовательно, значение игры (5.1) равно 0.5, а $\nu {\text{*}}({{x}_{{12}}})$ и $\mu {\text{*}}({{y}_{{12}}})$ – оптимальные смешанные стратегии первого и второго игроков соответственно. Таким образом, с вероятностью 0.5 работу w12 следует начинать в моменты времени 0 и 2, т.е. с вероятностью 0.5 следует применять расписания S0 и S2, где S0 соответствует вектору ${{x}_{0}} \in X$, ${{x}_{0}} = \{ {{x}_{{11}}} \in [0;2],{{x}_{{12}}} = 0$; ${{x}_{{21}}} \in [{{x}_{{11}}} + 1;3]$, ${{x}_{{31}}} \in [{{x}_{{21}}} + 1;4]\} $, а S2 – вектору ${{x}_{2}} \in X$, ${{x}_{2}} = \{ {{x}_{{11}}} \in [0;2],\;{{x}_{{12}}} = 2;\;{{x}_{{21}}} = 3,\;{{x}_{{31}}} = 4\} $.

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

Список литературы

  1. Мищенко А.В., Сушков Б.Г. Минимизация времени выполнения работ, представленных сетевой моделью, при нефиксированных параметрах сети. М.: ВЦ АН СССР, 1980. С. 3–16.

  2. Мищенко А.В. Устойчивость решений задачи оптимального распределения ресурсов при динамическом изменении структуры сети. М.: ВЦ АН СССР, 1980. 12 с.

  3. Давыдов Э.Г. Исследование операций. М.: Высш. шк., 1990. С. 185–189.

  4. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984.

  5. Mironov A.A., Tsurkov V.I. Network Models with Fixed Parameters at the Communication Nodes. 1 // J. Computer and Systems Sciences International. 1994. V. 32. № 6. P. 1–11.

  6. Mironov A.A., Tsurkov V.I. Network Models with Fixed Parameters at the Communication Nodes. 2 // J. Computer and Systems Sciences International. 1995. V. 33. № 3. P. 107–116.

  7. Mironov A.A., Levkina T.A., Tsurkov V.I. Minimax Estimations of Arc Weights in Integer Networks with Fixed Node Degrees // Applied and Computational Mathematics. 2009. V. 8. № 2. P. 216–226.

  8. Фуругян М.Г. Решение одной задачи распределения ресурсов в АСУ реального времени при наличии неопределенных факторов // АиТ. 2002. № 11. С. 167–171.

  9. Фуругян М.Г. Приближенное решение одного класса бесконечных антагонистических игр с полунепрерывной платежной функцией // Вестн. МГУ. Сер. 15. № 2. 1980. С. 66–69.

Дополнительные материалы отсутствуют.