К вопросу формирования мультиверсионного программного обеспечения с учетом ресурсных ограничений

Проблеме формирования программных комплексов (ПК), проектируемых на основе принципов программной избыточности, в настоящее время уделяется значительное внимание. Проблематика проектирования программных комплексов с использованием методологии мультиверсионного программирования рассматривалась в работах А. Авижиениса, Н. Ашрафи, О. Бермана, М. Катлер, Дж. Ву, К. Яо, Р.К. Скотта, Д. Мак Аллистера, К. Е. Гросспитча и мн. др. [1–5]. Разрабатываются новые методы оптимизации версионного состава программного комплекса, новые системы формирования структуры программного комплекса, однако не достаточно внима- ния уделяется разработке методик формирования структуры мультиверсионного программного комплекса с учетом временных и ресурсных ограничений [1]. Основной задачей формирования мультиверсионного программного обеспечения является оптимизация версионного состава программного комплекса. В качестве критерия оптимизации обычно выбирают надежность комплекса.

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

Методология авторов работ [3; 4], исследующих данный вопрос, основывается на следующих положениях:

• –    ПО проектируется методом модульного программирования;

• –    рассматриваются системы, построенные на основании методологии мультиверсионного программирования;

• –    версии модулей разрабатываются независимо друг от друга и их параметры надежности и стоимости могут быть оценены;

• –    реализуется статическое распределение задач с известным временем обслуживания.

В работе рассматривается следующая модель: система конструируется из I задач, для решения каждой из которых назначается определенный программный модуль. Связи между задачами определяются в виде графа задач и также могут быть представлены в виде матрицы инцидентности. Некоторые из задач могут быть структурно идентичны или одинаковы, что позволяет для их решения использовать одинаковые модули (цикличное использование модулей или эксплуатация одного и того же модуля с разными параметрами). Пусть J – число используемых программных модулей. Следовательно, I задач можно разбить на J классов. Через n , = 1, …, J обозначим число задач класса , а через А – множество индексов задач этого класса cardAj = nj, j = 1, ..., J.              (1)

Предполагается, что, учитывая методологию мульти-версионного программирования, имеется K_j версий модуля j , используемого для решения j -го класса задач ( j = 1,…, J ) , т. е. степень избыточности может варьироваться в зависимости от критичности задачи или имеющегося набора версий. Для формального описания использования нескольких версий одного программного модуля вводится следующая булева переменная [5; 6]: X k = 1, если для решения задачи i класса j используется k_j -я ( k_j = 1, …, Kj ) версия модуля j , и 0 – в противном случае.

Множество X = ( X k ) , i = 1, _, I ; j = 1, _, J ; k = 1, ..., ij                                                             j

K_j булевых переменных X_i^k_j^j называется вектором конфигурации системы и представляет возможный способ назначения версий программных модулей задачам в системе.

Вводятся следующие обозначения:

• –    R_kj – оцениваемая надежность версии k_j модуля j: ( R_kj = 1 – P_kj ), где P_kj – соответствующая функция распределения отказов;

• –    R_j – оцениваемая надежность отказоустойчивого модуля j как комбинации K_j независимых версий;

• –    R – оцениваемая надежность всего комплекса ПО.

Условие реализации задачи класса j одной из версий модуля в терминах булевых переменных может быть выражено следующим образом:

Z X k = n j , j = 1, ^, J -          (2)

• i j ⁶ A j

Тогда задача состоит в максимизации надежности max R = ПЛу>              (3)

j = 1 где

^{K j}             X^kj

^Rj = ¹ - n ( 1 - R j ) j

• ^k j = 1

с дополнительными ограничениями

Z X ^ j j= 1, .... J .            (4)

i j ⁶ A j

Здесь выражение (4) определяет то, что в мультивер-сионной системе для некоторой задачи может использоваться более одной версии программного модуля.

С целью описания процессов обслуживания задач в системе вводится так называемый вектор временной развертки (ВВР) набора задач, определяемый как t {t1, ---, ti, ---, ti}, где ti – момент времени, в который начинается обслуживание i-й (i = 1, …, I) задачи. Независимо друг от друга компоненты ВВР должны удовлетворять условиям ti < t,. < ti^i = 1,---, I, где til и tiu – самый ранний и самый поздний моменты времени соответственно, когда может начаться обслуживание задачи i; оба параметра зависят от значений времени выполнения предшествующих задач. Очевидно, что временные критерии улучшаются варьированием параметра ti в рамках величин til и tiu .

Блок-схема алгоритма формирования ВВР ресурсов изображена на рис. 1. Алгоритм заключается в последовательном переборе всех путей следования в порядке убывания времени их выполнения и обработки каждого модуля в цепочке. Каждый модуль, во-первых, проверяется на его включенность в ВВР, далее определяется временной промежуток, в течение которого предполагается выполнение модуля.

Алгоритм поиска начального и конечного момента времени представлен в виде блок-схемы на рис. 2. В качестве начального момента времени используем момент времени, когда заканчивается выгрузка параметров последних из модулей, от которых зависит текущий. Это соответствует моменту времени, когда мы можем загружать параметры, поэтому мы корректируем начальное время, уменьшая его на время загрузки модуля, которое нам известно заранее [7].

Здесь т * i , i = 1--- n m - параметры вектора временной развертки; k – версия программного модуля; N_m – программные звенья; n _х - длина пути; X i - номер выполняемого звена; ( a* ) ¹ _kj и ( a* ) ¹ _ik – элементы матрицы связанности A , структура которой изображена на рис. 3.

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

Программный комплекс имеет Nin входов и Nout выходов, в матрице A в качестве элементов aij будем использовать структуру {inj, outi}, где inj – номер входного пара- метра j-го звена, а out. - номер выходного параметра i-го звена, если существует передача данных, и {0, 0}, если нет. Полученную матрицу обозначим A*, а обращаться к параметрам in. и out. будем при помощи символов (at )j и (at*)2 соответственно. Иначе говоря, мы представляем выходные параметры ПК как задачи, которые могут получить один параметр, но ничего не передают, а входные параметры ПК наоборот передают, но не получают.

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

Программные модули назначаются в соответствии со следующими правилами [7]:

• 1.    Реализуемость (выполнимость) прикладного процесса.

• 2.    Коррекция компонент ВВР в ответ на нарушение условия реализуемости.

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

Рис. 1. Обобщенная блок-схема алгоритма формирования ВВР-ресурсов

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

• 1.    Назначаем k j -й программный модуль для решения задачи i = 1 класса j .

• 2.    Проверка процесса на реализуемость:

• -    если условие выполняется - переход к п. 4;

• -    если условие не выполняется - переход к п. 3.

• 3.    Коррекция вектора временной развертки:

• -    если условия выполняются - продолжаем далее по ходу алгоритма;

• -    если условия не выполняются - переходим к п. 1.

• 4.    Проверка ограничений на число каналов чтения/ записи:

• -    если условия выполняются - переход к п. 5;

• -    если условия не выполняются - переход к п. 1.

• 5.    Увеличиваем i : ( i = i + 1) и назначаем k-й программный модуль для решения задачи i класса j :

• -    если i + 1 <  I - переход к п. 2;

• -    если i + 1 >  I - переход к п. 6.

• 6.    Вычисление длительности вычислительного процесса для измененного способа назначения модулей.

Рассматривая в рамках данной процедуры методы оптимизации версионного состава по критерию надежности ПК [7], следует отметить, что описанный выше алгоритм с точки зрения программиста является нереализуемым. Во-первых, символом k j в работе обозначается номер версии в наборе для модуля j , а не номер модуля, а во-вторых, в алгоритме изменяется только параметр i , а параметр k_j остается неизвестным.

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

Рис. 2. Блок-схемы алгоритма нахождения t и t end

Задачи                Выходные параметры ПК

и S s ч о м

РА

{iHj, OUfj}	{/«2 OU//}		{УШ ou^}	{1,оы^}/{0,0}	{l,c.uf;}/{0,0}		{l,ou/j}/{0,0}
{!>U our?}	{1И2 ouf2}		{УШ out2\	{1,оы^}/{0,0}
.....................
{гиА 84^}	№2 gWi		{УШ Ш	fl,o^}/{□,□}	{l,ou^}/{0,0}		{1,™^}/{0,0}
{2HJ,1 }/{0,0}	{!H2l}/{0,0}		{УшЛ/{0,0}	{0,0}	{0,0}		{0,0}
{зн;Д}/{0,0}				{0,0}	{0,0}		{0,0}
.....................
{=^l}/{0,0}	...	...|(mi}/{0,0}		{0,0}	{0,0}	...	{0,0}

Рис. 3. Структура матрицы связности задач ПК

бора версий напрямую зависит время выполнения задачи.

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

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