Известия РАН. Теория и системы управления, 2019, № 3, стр. 77-86

ПОТОКОВЫЕ АЛГОРИТМЫ ПЛАНИРОВАНИЯ ВЫЧИСЛЕНИЙ В ИНТЕГРИРОВАННОЙ МОДУЛЬНОЙ АВИОНИКЕ

В. А. Костенко a*, А. С. Смирнов a

a МГУ
Москва, Россия

* E-mail: kost@cs.msu.su

Поступила в редакцию 26.12.2018
После доработки 25.01.2019
Принята к публикации 28.01.2019

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

Аннотация

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

DOI: 10.1134/S0002338819030119

Введение. Для поддержки требований реального времени и изолированности программ различных подсистем информационно-управляющих систем реального времени (ИУС РВ) с интегрированной модульной архитектурой [1] был разработан стандарт ARINC 653 [2]. Наиболее широко используемый подход к построению ИУС РВ с интегрированной модульной архитектурой известен как интегрированная модульная авионика (ИМА). Российской операционной системой, соответствующей стандарту ARINC 653, является ОС РВ Багет 3.0 [3, 4]. В операционной системе реального времени (ОС РВ) Багет 3.0 стандарт ARINC 653 выбран в качестве основного. Реализованы все обязательные функции ARINC 653. Стандарт POSIX используется в той мере, в какой это не противоречит ARINC 653.

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

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

В данной работе для построения многопроцессорных статико-динамических расписаний предложены алгоритмы, основанные на нахождении максимального потока в транспортной сети.

1. Близкие задачи и известные алгоритмы. В работах [5, 6] были предложены муравьиные алгоритмы для построения статико-динамических расписаний. Данные алгоритмы применимы только для варианта задачи, когда прерывание программ не допустимо. Это означает, что программа может выполняться только в одном окне своего раздела, что существенно ограничивает практическое применение алгоритмов.

В [7, 8] были рассмотрены алгоритмы, основанные на декомпозиции задачи на две подзадачи: привязка разделов к процессорам и построение набора окон для каждого процессора. Недостатком этих алгоритмов является их ориентация на учет специфических для конкретной ИУС РВ ограничений на корректность статико-динамического расписания, а также зависимость их точности от класса исходных данных.

Наиболее близкими задачами, для которых известны алгоритмы, основанные на нахождении максимального потока в транспортной сети, являются задачи построения расписаний с прерываниями работ. Методика использования алгоритмов нахождения максимального потока в сети для построения расписаний с прерываниями была предложена в работах [9, 10].

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

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

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

2. Задача построения статико-динамического расписания. Для задачи построения статико-динамических расписаний для систем реального времени с архитектурой интегрированной модульной авионики задаются следующие исходные данные: n – число работ; p – число процессоров; q – число разделов; c – время на переключение окна; – набор работ.

Требования к выполнению работ в реальном времени могут задаваться двумя способами:

Способ 1: ${{a}_{k}} = \langle s_{k}^{A},f_{k}^{A},t_{k}^{A},d_{k}^{A}\rangle $, где $s_{k}^{A}$ – директивный срок начала выполнения работы $k$ (выполнение работы должно начаться не раньше этого срока); $f_{k}^{A}$ – директивный срок завершения выполнения работы $k$ (выполнение работы должно завершиться до наступления этого срока), $t_{k}^{A}$ – время выполнения работы; $d_{k}^{A}$ – раздел, к которому относится работа.

Способ 2: ${{a}_{k}} = \langle F_{k}^{A},t_{k}^{A},d_{k}^{A}\rangle $, где $F_{k}^{A}$ – частота ($1{\text{/}}F_{k}^{A}$ – период) выполнения работы; $t_{k}^{A}$ – время выполнения работы; $d_{k}^{A}$ – раздел, к которому относится работа. Частота определяет набор отрезков времени выполнения работы, длина которых равна ее периоду.

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

Требуется построить статико-динамическое расписание, содержащее максимальное число работ из заданного набора. Расписание построено, если определен набор окон для каждого процессора $l$: , где ${{m}_{l}}$ – число окон; $s_{i}^{{{{W}_{l}}}}$ – время открытия окна; $f_{i}^{{{{W}_{l}}}}$ – время закрытия окна; $d_{i}^{{{{W}_{l}}}}$ – номер раздела, которому принадлежит окно; $A_{i}^{{{{W}_{l}}}}$ = =  – набор работ, выполняемых в окне (с указанием времени, отведенном работе на исполнение в данном окне).

Расписание должно удовлетворять условиям корректности для каждого набора окон ${{W}_{l}}$.

1. Окна не перекрываются и учтено минимальное время переключения:

(2.1)

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

(2.2)
$\mathop \sum \limits_{{{a}_{j}} \in {{A}_{i}}^{{{{W}_{l}}}}} {{t}_{{ji}}} \leqslant {\;}f_{i}^{{{{W}_{l}}}} - {\;}s_{i}^{{{{W}_{l}}}}\quad \forall i \in {\;}\overline {1,{{m}_{l}}} .$

3. В окне могут выполняться только части работы или целые работы из того раздела, к которому это окно привязано:

(2.3)
$\forall {\;}{{a}_{j}},{{a}_{k}}{\;} \in {\;}{{A}_{i}}^{{{{W}_{l}}}}{\;} \to {\;}d_{j}^{{{{W}_{l}}}} = {\;}d_{k}^{{{{W}_{{l{\;}}}}}}\quad \forall i \in {\;}\overline {1,{{m}_{l}}} .$

4. Работа размещена, если она выполнена полностью:

(2.4)
${\text{ }}\sum\limits_{{{a}_{k}} \in A_{j}^{{{{W}_{l}}}}}^{} {{{t}_{{kj}}} = t_{k}^{A}\quad \forall {{a}_{{k\quad}}} \in \,} \bigcup\limits_{i = 1}^{{{m}_{l}}} {{{A}_{i}}^{{{{W}_{l}}}}} .$

5. Работы одного раздела выполняются только на одном процессоре.

3. Алгоритм построения статико-динамического расписания на основе алгоритма поиска максимального потока в сети. Алгоритм состоит из трех основных этапов:

1) построение транспортной сети (ориентированного графа),

2) нахождение потока в транспортной сети,

3) восстановление расписания из полученного потока.

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

Поиск потока осуществляется на основе алгоритма “поднять-и-в-начало” как наиболее простого по вычислительной сложности и организации проверки корректности расписания. В нем определены три основные операции:

1) подъем вершины,

2) проталкивание из вершины в вершину,

3) разрядка вершины.

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

Вершины разбиты на группы – вершины-работы каждого раздела и вершины-интервалы-процессоры, всего $q + 1$ группа. Пока есть переполненные вершины, алгоритм производит операцию разрядки вершин. Порядок разрядки следующий: сначала выбирается первый раздел, выполняется разрядка всех его вершин с просмотром возможности проталкивания потока в сток, после этого выполняется разрядка вершин-интервалов. Пока не останется переполненных вершин группы этого раздела и группы вершин-интервалов разрядка осуществляется по следующему правилу: разряжается вершина-работа, если это вызвало появление переполненных вершин-интервалов, то разряжаются они, а потом опять разряжаются вершины-работы раздела.

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

Рассмотрим каждый из этапов алгоритма подробнее.

3.1. Построение транспортной сети. Пусть ${{{\tau }}_{0}} < \; \ldots \quad\; < {{{\tau }}_{s}}$ – все различные значения $s_{k}^{A}\quad$ и $f_{k}^{A}$, k = 1, ..., n, и ${{I}_{i}}\quad = {\;}\left( {{{\tau }_{{i - 1}}};{\;}{{\tau }_{i}}} \right],$ $i\quad = {\;}\overline {1,s} $. Работа $k$ доступна для выполнения (выполнима) в момент времени ${{t}_{0}}$, если $s_{k}^{A} < \quad\;{{t}_{0}} < f_{k}^{A}$.

Сеть представляет собой двудольный граф с дополнительными вершинами: источником $O$ и стоком $O'$ (рисунок). Первый уровень графа состоит из вершин, каждая из которых взаимно однозначно соответствует какой-либо работе (вершины-работы), второй уровень состоит из вершин, соответствующих паре интервал-процессор (вершины-интервалы-процессоры). Источник соединен со всеми вершинами-работами, причем дуга, ведущая к вершине k-й работы, имеет пропускную способность, равную $t_{k}^{A}$ , $k = \overline {1,n} $. Вершина-работа соединяется со всеми вершинами-интервалами-процессорами, на которых эта работа выполнима дугами пропускной способности ${{t}^{A}}$. Все вершины-интервалы-процессоры соединены со стоком $O{\text{'}}$ дугами пропускной способности, равной длине интервала.

3.2. Поиск потока в транспортной сети. Для построения статико-динамического расписания требуются следующие данные: dist – вершина-сток; $s$ – вершина-источник; пропускные способности $c\left( {u,\quad\text{v}} \right)$ всех дуг в сети; функция предпотока $f\left( {u,\quad\text{v}} \right)$ для всех дуг в сети на шаге алгоритма. Каждая вершина имеет целочисленные параметры: избыточный поток ${{e}_{u}}$; высота ${{h}_{u}}$; список вершин-работ по разделам; вершины-работы также имеют номер раздела $p{{t}_{u}}$, к которому эта работа прикреплена. Вершины-интервалы-процессоры знают предшествующий и последующий интервалы $n{{i}_{u}}$, $p{{i}_{u}}$; имеют целочисленный параметр $c{{w}_{u}}$ – количество переключений окон в интервале, параметры $i{{r}_{u}}$ и $i{{l}_{u}}$ показывают, есть ли переключение окна на правой и левой границах соответственно. Вершины-интервалы содержат структуру для запоминания входящих потоков по разделам $PT_{u}^{i}$, где $i\quad = \quad\overline {1,q} ,$ (т.е. можно узнать, сколько времени отведено в данном интервале данному разделу), множество разделов $P{{S}_{u}}$, потоки которых входят в вершину, первый $f{{p}_{u}}$ и последний $l{{p}_{u}}$ разделы окна, длительность интервала $du{{r}_{u}}$. Также для всех вершин-интервалов $v$, $pro{{c}_{v}}$ – номер процессора, с которым ассоциирован данный интервал времени, и максимальное число попыток перераспределений процессоров $K$. Привязка каждого раздела к ядру есть $P{{R}_{{part}}}$.

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

Инициализация сети.

1. Изначально предпоток равен пропускной способности для всех ребер, выходящих из источника, и противоположен для обратных пар вершин:

2. Для остальных пар вершин предпоток равен нулю.

3. Начальная высота равна 10 в сети для источника, 1 – для вершин-работ, 0 – для вершин-интервалов и стока.

Подъем вершины ($u$).

Из всех доступных вершин u (существует дуга и ) выбирается вершина $v$ ($v$ отлична от dist) с минимальной высотой, после чего высота вершины u становится равной ${{h}_{v}}\quad$ + 1.

Добавление переключения окна в $(v).$

В этой операции v является вершиной-интервалом-процессором.

1. Пропускная способность уменьшается на c.

2. Число переключений окон $c{{w}_{v}}$ увеличивается на 1.

3. Если , то изменяется избыточный поток.

4. Переполненный поток , и поток становится равным .

5. Если ${{e}_{v}} > 0$, то вершина v добавляется к списку переполненных вершин.

Удаление переключения окна в $(v)$.

В данной операции $v$ является вершиной-интервалом.

1. Пропускная способность увеличивается на $c$.

2. Если ${{e}_{v}} \geqslant c$, то

${{e}_{v}} = {{e}_{v}}--c,$
${{e}_{{dist}}} = {{e}_{{dist}}} + c.$

3. Если ${{e}_{v}} = 0$, то убрать вершину из списка переполненных вершин.

4. Число переключений окон $c{{w}_{v}}$ уменьшается на 1.

Учет раздела при добавлении потока размера value раздела part из вершины-интервала $v$.

1. Добавляется поток в структуру входящих потоков вершины:

.

2. Если поток этого раздела впервые вошел в вершину-интервал-процессор, то он

добавляется в множество $P{{S}_{v}}$.

2.1. Если это самый первый раздел, то $f{{p}_{v}} = part\quad$и .

2.2. Если это второй раздел, то он сравнивается с первым разделом следующего интервала:

2.2.1. если разделы равны, то $l{{p}_{v}} = part$;

2.2.2. если разделы не равны, то $f{{p}_{v}} = part$.

2.3. Если это третий и более раздел, то он сравнивается с первым разделом следующего интервала:

2.3.1. если разделы равны, то $l{{p}_{v}} = part$;

2.3.2. если нет, то он сравнивается с первым разделом следующего интервала, и если они равны, то $f{{p}_{v}} = part$.

Учет раздела при удалении потока размера value раздела part из вершины-интервала-процессора $v$.

1. Убирается поток из структуры входящих потоков вершины:

$P{{T}_{{part}}} = P{{T}_{{part}}} - value$.

2. Если поток этого раздела равен нулю (равносильно тому, что этот раздел больше не входит в данный интервал), то он убирается из множества $P{{S}_{v}}$.

3. Если не осталось разделов, то $f{{p}_{v}} = 0$ и $l{{p}_{v}} = 0$.

4. Если остался один раздел $pt,$ то $f{{p}_{v}} = pt$ и $l{{p}_{v}} = pt$.

5. Если осталось более одного раздела, то:

5.1. если удаленный раздел равен последнему разделу в интервале, то ($p{{t}_{{nf}}}$ – раздел, не равный первому разделу в интервале) $l{{p}_{v}} = p{{t}_{{nf}}}$;

5.2. если удаленный раздел равен первому разделу в интервале, то ($p{{t}_{{nl}}}$ – раздел, не равный последнему разделу в интервале) $f{{p}_{v}} = p{{t}_{{nl}}}$.

Корректировка окон в вершине-интервале-процессоре $(v)$.

1. Производится корректировка внутренних переключений. Вычисляется число внутренних переключений $c{{w}_{{in}}} = c{{w}_{v}} - i{{r}_{v}} - i{{l}_{v}}$. Выполняются необходимое число раз операции удаление переключения окна в (in) или добавление переключения окна в (in), чтобы число учтенных переключений было равно $c{{w}_{{in}}}$.

2. Производится корректировка правого переключения.

2.1. Если есть справа непустая вершина-интервал-процессор $ni$, то:

2.1.1. если $f{{p}_{{ni}}} \ne l{{p}_{v}}$ и нет переключений справа в $v$ ($i{{r}_{v}} = false$), и нет переключения слева в $ni$ ():

2.1.1.1. если (в следующем интервале есть место для переключения) и (в текущем нет), то выполняется операция добавление переключения окна в ($ni$) и $i{{l}_{{ni}}} = true$;

2.1.1.2. иначе выполняется операция добавление переключения окна в ($v$), .

2.1.2. Если $f{{p}_{{ni}}} = l{{p}_{v}}$ и есть переключение справа в ($v$) и $\left( {i{{r}_{v}} = true} \right)$, то выполнить операцию удаление переключения окна в $(v)$ и $i{{r}_{v}} = false$, если есть переключения слева в $ni$ ($i{{l}_{{ni}}} = true$), то выполнить операцию удаление переключения окна в ($ni$) и $i{{l}_{{ni}}} = false$.

2.2. Если справа все вершины пустые и есть переключение справа в $v$, то выполнить операцию удаление переключения окна в ($v$) и $i{{r}_{v}} = false$.

3. Производится корректировка левого переключения (аналогично с правым).

3.1. Если есть слева непустая вершина-интервал $pi$, то:

3.1.1. если $l{{p}_{{pi}}} \ne f{{p}_{\text{v}}}$ и нет переключений слева в $\text{v}$ ($i{{l}_{\text{v}}} = false$), и нет переключения справа в $pi\left( {i{{r}_{{pi}}} = false} \right)$:

3.1.1.1. если (в предыдущем интервале есть место для переключения) и (в текущем нет), то выполняется операция добавление переключения окна в (pi) $i{{r}_{{pi}}} = true$;

3.1.1.2. иначе выполняется операция добавление переключения окна в $(\text{v})$ и $i{{l}_{\text{v}}} = true$;

3.1.2. если $l{{p}_{{pi}}} = f{{p}_{\text{v}}}$ и есть переключение слева в $\text{v}$ ($i{{l}_{\text{v}}} = true$), то выполнить операцию удаление переключения окна в $(\text{v})$ и $i{{l}_{\text{v}}} = false$, если есть переключения справа в pi ($i{{r}_{{pi}}} = true$), то выполнить операцию удаление переключения окна в (pi) и $i{{r}_{{pi}}} = false$.

3.2. Если справа все вершины пустые и есть переключение cправа в $\text{v}$, то выполнить операцию удаление переключения окна в $(\text{v})$ и .

Удаление работы u из сети.

1. Для всех пар вершина-работа–вершина-интервал-процессор ($u,\text{v}$), где вершина-работа u соответствует не полностью размещенной работе.

2. Убирается поток от вершины-работы к вершине-интервалу-процессору, такой же поток вычесть из потока от вершины-интервала-процессора до стока. Убирается поток от источника до вершины-работы:

$value = f\left( {u,\text{v}} \right),$
${{e}_{{dist}}} = {{e}_{{dist}}} - f\left( {u,\quad\text{v}} \right),$

3. Выполняется операция учет раздела при удалении потока размера value раздела $p{{t}_{u}}$ из вершины-интервала $\text{v}$.

4. Выполняется операция корректировка окон в $\text{v}$.

5. Пропускная способность от источника до вершины-работы становится равной нулю: = 0.

Размещение раздела part на процессор proc.

Для всех вершин-работ u, таких, что $p{{t}_{u}} = part$ и для всех ребер (u, $\text{v}$), таких, что $pro{{c}_{\text{v}}} \ne proc$, пропускная способность $c\left( {u,\quad\text{v}} \right) = 0$ и $P{{R}_{{p{{t}_{u}}}}} = proc$.

Удаление раздела part с процессора proc.

Для всех вершин-работ $u$, таких, что $p{{t}_{u}} = part$.

1. Для всех ребер (u, $\text{v}$), таких, что $pro{{c}_{\text{v}}} \ne proc$: $c\left( {u,\quad\text{v}} \right) = du{{r}_{\text{v}}}$.

2. Для всех ребер (u, $\text{v}$), таких, что $pro{{c}_{\text{v}}} = proc$:

2.2. выполняется операция учет раздела при удалении потока размера $value$ раздела ptu из вершины-интервала-процессора $\text{v}$;

2.3. выполняется операция корректировка окон в $\text{v}$;

2.4. пропускная способность от вершины-работы до вершины-интервала-процессора становится равной нулю: $c\left( {u,\quad\text{v}} \right) = 0$.

Проталкивание (u, $\text{v}$).

1. Поток $f\left( {u,\text{v}} \right)\quad$ увеличивается на величину .

2. На $\delta f\left( {u,\quad\text{v}} \right)$ увеличивается избыточный поток ${{e}_{\text{v}}}$.

3. Обратный поток и избыточный поток eu уменьшаются на $\delta f\left( {u,\quad\text{v}} \right)$.

4. Если u – вершина-работа, $\text{v}$ – вершина-интервал-процессор и раздел еще не размещен ни на один процессор, то выполнить операцию размещение раздела ptu на процессор $pro{{c}_{\text{v}}}$; выполнить операцию учет раздела при добавлении потока размера $\delta f\left( {u,\quad\text{v}} \right)$ раздела ptu в вершину-интервал-процессор $\text{v}$ и выполнить операцию корректировка окон в ($\text{v}$).

5. Если u – вершина-интервал-процессор, $\text{v}$ – вершина-работа, то выполнить операцию учет раздела при удалении потока размера $\delta f\left( {u,\quad\text{v}} \right)$ раздела $p{{t}_{\text{v}}}$ в вершину-интервал-процессор и выполнить операцию корректировка окон в (u).

6. Если ${{e}_{\text{v}}} = 0$, то вершина убирается из списка переполненных вершин соответствующего раздела.

7. Если ${{e}_{\text{v}}} > 0$, то вершина добавляется в список переполненных вершин соответствующего раздела.

Проталкивание $(u,\quad\text{v})$ в вершину-интервал-процессор c учетом остаточного потока ($\text{v},dist$).

В этой операции v является вершиной-интервалом-процессором.

1. Поток $f\left( {u,\quad\text{v}} \right)$ увеличивается на величину:

(3.1)
.

2. Избыточный поток ${{e}_{\text{v}}}$ увеличивается на $\delta f\left( {u,\quad\text{v}} \right).$ Обратный поток $f\left( {\text{v},{\;}u} \right)$ и избыточный поток ${{e}_{u}}$ уменьшаются на $\delta f\left( {u,\quad\text{v}} \right).$

3. Если u – вершина-работа, $\text{v}$ – вершина-интервал и раздел еще не размещен ни на один процессор, то выполнить операцию размещение раздела ptu на процессор $pro{{c}_{\text{v}}}$; выполнить операцию учет раздела при добавлении потока размера $\delta f\left( {u,\quad\text{v}} \right)$ раздела ptu в вершину-интервал $\text{v}$ и выполнить операцию корректировка окон в ($\text{v}$).

4. Если ${{e}_{\text{v}}} = 0$, то вершина убирается из списка переполненных вершин соответствующего раздела.

5. Если ${{e}_{\text{v}}} > 0$, то вершина добавляется в список переполненных вершин соответствующего раздела.

Разрядка вершины u.

Пока ${{e}_{u}}{\;} > {\;}0$.

1. По порядку рассматриваем все доступные вершины для u.

2. При первом рассмотрении:

2.1. если $\text{v}$ – вершина-интервал-процессор, то cw – число переключений окон, которые появятся при проталкивании потока в вершине-интервале-процессоре $\text{v}$;

2.2. вычисляется величина проталкиваемого потока, при условии, что ${{h}_{u}} = {{h}_{\text{v}}} + 1$, по формуле (3.1), и если она не равна нулю, то выполнить операцию проталкивание (u, $\text{v}$) в вершину-интервал c учетом остаточного потока (.

3. При последующих рассмотрениях:

3.1. если ${{h}_{u}} = {{h}_{\text{v}}} + 1$, $\text{v}$ – источник и K > 0, то и выполнить операцию удаление раздела ptu с процессора , иначе выполнить операцию проталкивание (u, $\text{v}$).

4. Выполнить операцию подъем u.

5. Вернуться на первый шаг.

Возможная разрядка вершины u.

В данной операции u является вершиной-работой.

Для всех существующих ребер (u, $\text{v}$).

1. Если $\text{v}$ является источником: если ${{h}_{u}} = {{h}_{\text{v}}} + 1$ и если K = 0, то $K = K - 1$ и выполнить операцию удаление раздела ptu с процессора $P{{R}_{{p{{t}_{u}}}}}$, иначе выполнить операцию проталкивание (u, $\text{v}$).

2. Если $\text{v}$ является вершиной-интервалом-процессором, то: если ${{h}_{u}} = {{h}_{\text{v}}} + 1$, то вычисляется величина проталкиваемого потока по формуле (3.1), и если она не равна нулю, то выполнить операцию проталкивание (u, $\text{v}$) в вершину-интервал c учетом остаточного потока ().

Восстановление расписания.

Последовательно для всех процессоров выполняются следующие операции.

1. Если есть переключение окна слева, то текущее окно закрывается, учитывается время переключения, открывается окно первого раздела в этом интервале, вычитается единица из количества переключений окон в этом интервале.

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

3. Если есть переключение окна справа, то текущее окно закрывается, учитывается время переключения, открывается окно первого раздела следующего интервала.

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

Общая схема алгоритма.

1. Выполняется операция инициализация сети.

2. Строится поток.

2.1. Выбирается раздел, список переполненных вершин которого не пуст (если такого раздела нет, то переход к п. 3, далее для этих вершин u выполняются операции: возможная разрядка вершины u.

2.2. Пока списки переполненных вершин раздела и вершин-интервалов не пусты:

2.2.1. для всех переполненных вершин-интервалов-процессоров $\text{v}$ выполняется операция разрядка вершины $\text{v}$;

2.2.2. для одной переполненной вершины раздела u выполняется операция разрядка вершины u.

2.3. Переход к п. 2.

3. Если есть не полностью размещенные работы, то для первой такой работы выполняется операция удаление работы из сети и переход к п. 2.

4. Выполняется операция восстановление расписания.

4. Свойства алгоритма построения статико-динамического расписания на основе алгоритма поиска максимального потока в сети. Результат работы алгоритма удовлетворяет условиям корректности расписания. В алгоритме основной операцией является операция разрядки вершины, которая в свою очередь состоит из операций проталкивания из вершины в вершину и операций подъема вершины. Операция подъема влияет только на очередность проталкиваний и не влияет на корректность расписания.

Операция проталкивания устроена таким образом, что при отсутствии избыточного потока в сети будут выполнены все условия корректности расписания.

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

Так как размещение происходит сразу после первого проталкивания работы на вершину интервал-процессор данного процессора, то дальнейшее размещение работ этого раздела возможно только на этом процессоре (так как пропускные способности к остальным процессорам равны 0) до того момента, пока работа не захочет сделать проталкивание в исток, что равносильно тому, что не удается разместить весь раздел на этом процессоре. Тогда выполняется вторая операция. Поток отзывается из всех вершин от всех вершин-работ данного раздела (корректность расписания остается, так как учитываются все переключения окон). Пропускные способности до остальных процессоров восстанавливаются. Поэтому не может быть нарушено условие: работы одного раздела выполняются на одном процессоре. Построение сети можно осуществить за O(pn2). Восстановление расписания осуществляется за O(pn).

Для одного процессора верно следующее: если n – число работ, то $V\quad\quad \leqslant 3n + 2$ и $E \leqslant 3n + 2{{n}^{2}}$. Первый шаг алгоритма заключается в возможной разрядке всех вершин одного раздела, который в худшем случае занимает 2n2 операций проталкивания. За этим следует разрядка всех вершин-интервалов, что занимает в худшем случае $2n(n + 1)$ операций проталкивания. Эти действия выполняются для каждого раздела, значит нужно $n(2{{n}^{2}} + 2n\left( {n + 1} \right)$ операций проталкивания. Далее покажем, что для каждой пары вершина-работа – вершина-интервал возможны не более 10 проталкиваний. Рассмотрим функцию высоты для вершин-работ, она всегда больше 0. И если она равна 11, то проталкивание осуществляется в исток и этот поток больше в сети не появляется. Высота истока, равная 10, обеспечивает пять попыток проталкивания из одной и той же вершины-работы в вершину-интервал. Так как высоты вершин-интервалов не уменьшаются (когда проталкивание возвращает поток в вершину-работу), то высота становится больше высоты вершины-работы, из которой было осуществлено проталкивание. Следовательно, для всех пар вершин-работ и вершин-интервалов-процессоров возможно не больше 10 проталкиваний. При удалении работы нужно повторить алгоритм сначала, максимум можно удалить n работ, что соответствует n итерациям алгоритма – $n{\kern 1pt} {\kern 1pt} (2{{n}^{3}} + 2n\left( {n + 1} \right) + 20{{n}^{2}})$. Общая сложность поиска потока для одного процессора алгоритмом равна O(n4), если требуется удаление работ, и O(n3), если получается спланировать все работы. Тогда сложность для всех процессоров составляет O(pn3).

Так как имеется только K попыток перераспределения раз дела, то сложность равна $O(Kp{{n}^{3}})$ при полном планировании расписания и $O(Kp{{n}^{4}})$ – при удалении некоторых работ.

Экспериментальное исследование проводилось в системе с ОС Windows 7 64bit, процессором Intel Core i3-2370M 2.39GHz, ОЗУ 8Гб.

На сгенерированных исходных данных алгоритм построения однопроцессорного статико-динамического расписания разместил все работы. При этом время построения решения не сильно зависит от загрузки процессора и не превышает 1.2 с для 1000 работ. Также число разделов почти не влияет на точность и время решения.

На сгенерированных исходных данных алгоритм продемонстрировал полную планируемость работ при загрузке процессоров до 90% для двух процессоров. Увеличение числа процессоров плохо влияет на число планируемых работ, так для трех процессоров планируемость всех работ возможна при загрузках процессора до 70% при больших значениях – возможно размещение 99% работ. Увеличение числа процессоров до восьми приводит к размещению 99% работ при загрузке до 70% и к размещению 90% работ при загрузке до 90%. Время выполнения алгоритма построения многопроцессорного статико-динамического расписания растет с увеличением загрузки процессоров для восьми процессоров. Это связано с тем, что число размещенных работ меньше 100% и требуется дополнительное время на исключение работ, для которых не нашлось места в статико-динамическом расписании. Время построения такого расписания может занимать 20 мин. Для числа процессоров от двух до четырех время построения статико-динамического расписания не превосходит 4 мин и точность находится на уровне 99–100% при загрузках процессора до 90%.

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

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

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

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

Рисунок.

Транспортная сеть

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

  1. Костенко В.А. Архитектура программно-аппаратных комплексов бортового оборудования // Изв. вузов. Приборостроение. 2017. Т. 60. № 3. С. 229–233.

  2. Arinc Specification 653. Airlines Electronic Engineering Committee. (http://www.arinc.com).

  3. Годунов А.Н. Операционные системы реального времени Багет 3.0 // Программные продукты и системы, 2010. № 4. С. 15–19.

  4. Годунов А.Н., Солдатов В.А. Операционные системы семейства Багет (сходство, отличия и перспективы) // Программирование. 2014. № 5. С. 69–76.

  5. Балаханов В.А., Костенко В.А. Способы сведения задачи построения статико-динамического однопроцессорного расписания для систем реального времени к задаче нахождения на графе маршрута // Программные системы и инструменты. 2007. № 8. С. 148–156.

  6. Балаханов В.А., Кокарев В.А., Костенко В.А. Возможность применения муравьиных алгоритмов для решения задачи построения статико-динамических расписаний // Тр. V Московской междунар. конф. по исследованию операций (ORM2007). М.: МАКС Пресс, 2007. С. 238–240.

  7. Balashov V.V., Balakhanov V.A., Kostenko V.A. Scheduling of Computational Tasks in Switched Network-based IMA Systems // Proc. Intern. Conf. on Engineering and Applied Sciences Optimization. National Technical University of Athens (NTUA), Athens, Greece, 2014. P. 1001–1014.

  8. Балашов В.В. Семейство систем автоматизации проектирования бортовых вычислительных систем реального времени // Программные продукты, системы и алгоритмы. 2017. № 4. С. 1–19.

  9. Federgruen A., Groenevelt H. Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Technique // Management Science. V. 32. № 3. 1986.

  10. Gonzales T., Sanhi S. Preemptive Scheduling of Uniform Processor Systems // J. Association for Computing Machinery. V. 25. № 1. 1978.

  11. Фуругян М.Г. Планирование вычислений в многопроцессорных АСУ реального времени с дополнительным ресурсом // АиТ. 2015. № 3. С. 144–150.

  12. Фуругян М.Г. Планирование вычислений в многопроцессорных системах с несколькими типами дополнительных ресурсов и произвольными процессорами // Вестн. МГУ. Сер. 15. Вычислительная математика и кибернетика. 2017. № 3. С. 38–45.

  13. Фуругян М.Г. Составление расписаний в многопроцессорных системах с дополнительными ограничениями // Изв. РАН. ТиСУ. 2018. № 2. С. 52–59.

  14. Костенко В.А., Смирнов А.С. Алгоритм построения однопроцессорных статико-динамических расписаний // Вестн. МГУ. Сер. 15. Вычислительная математика и кибернетика. 2018. № 1. С. 45–52.

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