Излагаемое исследование является составной частью разработки компьютерной технологии, направленной на обеспечение надежного выполнения сложных комплексов взаимосвязанных работ (КВР), являющихся комплексами взаимосвязанных программных модулей со случайными временами их выполнения в параллельных управляющих вычислительных системах (ВС), функционирующих в контурах управления реального времени [1–3]. Под надежным выполнением конкретного КВР в параллельной ВС понимается выполнение его за время, не превышающее заданное (пользователем) директивное время Tmax, с требуемой (удовлетворяющей пользователя) вероятностью Р [1]. Надежное выполнение КВР должно обеспечиваться как в штатном режиме функционирования управляющей ВС, так и в условиях внезапных неисправностей (сбоев, отказов) ее вычислительных ресурсов.
В рамках решения этой проблемы в работе предлагается способ организации адаптивного резервирования вычислительных процессов, базирующийся на сочетании различных вариантов многоверсионного резервирования (МР) с асинхронным запуском программных модулей КВР.
Под адаптивным резервированием вычислительных процессов (программных модулей – работ КВР) понимается выбор и настройка различных способов резервирования вычислительных процессов и/или их сочетаний в динамике выполнения КВР. Выбор и настройка способов резервирования КВР осуществляются на основе статического (до выполнения КВР) прогнозирования надежного выполнения заданного пользователем КВР, а также на основе анализа, уточнения и оперативного использования статических прогнозов (рассматриваемых способов резервирования) в процессе реализации задач в параллельной ВС с учетом текущего состояния процессов и системы, в частности – в условиях сбоев или отказов ее вычислительных ресурсов [3, 4]. Перспективными компонентами адаптивного резервирования КВР являются рассматриваемые здесь варианты МР [5–8].
Цель данного исследования – организация адаптивного метода резервирования вычислительных процессов, базирующегося на сочетании различных вариантов многоверсионного их резервирования с асинхронным запуском работ КВР; разработка математической модели для исследования свойств и эффектов динамического адаптивного многоверсионного резервирования программных модулей КВР на основе статического прогнозирования надежного их выполнения в параллельных вычислительных системах – как в штатном режиме функционирования, так и в условиях ошибок (сбоев или отказов).
Теоретической базой разработки является математический аппарат обрывающихся марковских процессов (ОМП), статистических методов и теории массового обслуживания (ТМО), графовые модели КВР, математические модели многоверсионного резервированных КВР в параллельных ВС [5–8], методология динамического управления надежным выполнением взаимосвязанных программных модулей (работ КВР) на основе адаптивного их резервирования в управляющих параллельных ВС [4].
Результаты такого моделирования могут быть использованы для повышения отказоустойчивости управляющих параллельных ВС.
Организация адаптивного многоверсинного резервирования КВР
Базовый КВР (в терминологии и понятиях [1, 2]) включает исходный и резервный КВР и соответствует штатному (без ошибок) выполнению КВР; исходный КВР и резервный КВР образуют две параллельные «ветви» вычислений, независимые по данным одна от другой.
Как и в [5–8] – рассматриваются варианты МР работ КВР с кратностью резервирования Z = 2, т.е. каждой работе-оригиналу aj исходного КВР соответствует работа-версия aj′ резервного КВР. Сравнение результатов этих работ осуществляется с помощью дополнительного программного модуля – работы сравнения bj. Для организации динамического адаптивного резервирования КВР рассмотрим следующие f версии (где f – номер версии) реализации базовых КВР, состоящих из двух «ветвей» вычислений:
1. Исходный КВР и КВР из работ-версий по [7, 8], – обозначим его как КВРБ1.
2. Исходный КВР и резервный КВР из упрощенных вариантов исходных работ по [6, 7], – обозначим его как КВРБ2.
3. Исходный КВР состоит из работ-версий КВРБ1, а резервный КВР из упрощенных вариантов работ-версий (аналогично первому варианту МР по [5, 6]) – КВРБ3.
Ключевыми понятиями для организации динамического адаптивного резервирования КВР являются контрольные события Zj, тестовый фрагмент и Таблица прогнозов, которая содержит набор «критических точек» 
, соответствующих контрольным событиям Zj [1, 4]. Контрольные события Zj, – события завершения некоторых работ aj КВР – например, отнесенных к «критическим процессам» КВР.
По тестовым фрагментам КВР оценивается время дообслуживания КВР в целом [4]. По контрольным событиям Zj анализируются состояния процесса реализации КВР в ВС и осуществляется управление этим процессом на основе сравнения прогнозируемого (в статике) времени выполнения тестовых фрагментов КВР с временными параметрами реальных событий, происходящих в системе в динамике.
Смысл «критической точки» заключается в следующем: если дообслуживание КВР (выполнение его тестового фрагмента) начинается не позже момента 
– момента наиболее позднего начала выполнения тестового фрагмента КВР для каждой версии f реализации КВР, то обеспечивается «штатное» выполнение КВР в целом за время, не большее директивного времени Тmax, с заданной вероятностью Р. По контрольному событию Zj возможен переход к динамическому управлению резервированными вычислительными процессами в режиме реального времени выполнения КВР следующими v (v = 1, ...,4) способами (алгоритмами управления процессами дообслуживания КВР): КВР Б2 (способ v1); КВРБ3 (способ v2); использование только одной «ветви» вычислений – исходного КВР (способ v3); КВР из работ-версий (способ v4); либо вычислительный процесс может быть продолжен в «штатном» режиме – КВРБ1.
Для реализации адаптивного МР резервирования – Таблица прогнозов содержит f (в нашем случае – пять) «критических точек» 
для каждого контрольного события Zj: 
– для продолжения «штатного» выполнения базового КВРБ1; 
(v = 1, ...,4) – для перехода к одному из четырех вышеописанных способов надежного дообслуживания базового КВР. Таким образом, заранее, в статике (т.е. до выполнения задач в ВС), Таблица прогнозов формируется значениями «критических точек» 
по предложенным в [4] процедурам.
Математическая модель
Для проведения исследования описанного подхода к организации адаптивного резервирования КВР на основе сочетания двух вариантов МР с асинхронным запуском работ КВР, разработана модифицированная математическая модель. По структуре эта модель аналогична унифицированной математической модели по [9] – при этом параметры состояний и правила ее функционирования задаются с учетом свойств и характерных особенностей рассматриваемых вариантов МР.
Как и в [9], предлагаемая модель представляется в виде однофазной СМО состоящей из k ≥ 2 обслуживающих приборов ОП (процессоров – П), буфера Б для готовых к выполнению работ, которые поступают из пула, содержащего в исходном состоянии N работ.
Пусть T – время жизни системы – время выполнения преобразованного КВР из N работ при заданной кратности резервирования Z, C работ сравнения, D работ программного блока диагностирования (БД) и Q работ «отката». Функционирование такой СМО можно описать обрывающимся Марковским процессом (ОМП) X(t), t ∈ [0, T) над следующим множеством состояний:
(1)
где I = (i1, ..., iw) – номера работ в буфере Б; w – число работ в Б, причем 
; P = (p1, …, pi, ..., pk) – вектор состояний ОП, i-й элемент этого вектора содержит номер работы, которая выполняется на ОПi; k – общее число ОП (процессоров ВС); 
– набор векторов общей (суммарной) размерности (Z + С)N + D + Q, что соответствует общему числу (Z + С)N работ базового КВР, БД и Q работ «отката»; вектор 
этого набора соответствует i-му ОПi; элементами вектора 
являются номера тех работ, которые уже выполнены на ОПi; m – общее количество выполненных работ преобразованного КВР, соответствующее сумме работ базового КВР, БД и работ «отката».
Отметим, что при штатном выполнении базового КВР, т.е. при отсутствии ошибок процессоров ВС (D = 0, Q = 0), мы получаем базовую математическую модель СМО для исследования и прогнозирования времени выполнения базового КВР.
Правила функционирования математической модели – это правила диспетчеризации работ, отражающие особенности организации различных способов резервирования КВР, программных диагностических процедур и формирования работ «отката» [9]. Опишем правила функционирования математической модели при возникновении контрольного события Zj:
Организация резервирования штатным способом v0
Правило 1. Если при возникновении контрольного события Zj время дообслуживания КВР 
, то в динамике вычислений происходит переход к одному из вышеописанных способов v, – со значением 
, для которого выполняется условие 
– в соответствии с далее приведенными правилами 2–5 или правилом 6.
Организация резервирования способами v1, v2
Правило 2. Готовые к выполнению работы-оригиналы аj и работы-версии 
выбираются на выполнение на свободные процессоры ВС (обязательно различные) по известному критерию диспетчеризации «ранг rj соответствующей вершины графа базового КВРБ2 (или КВРБ3) / связность sj вершины» [1,2]. На процессор П, на котором выполнялась работа-оригинал аj, с абсолютным приоритетом назначается работа сравнения bj.
Правило 3. Если при выполнении работы bj обнаружено несовпадение результатов выполнения работы аj и 
, то с абсолютным приоритетом назначаются на выполнение работы БД по правилам, рассмотренным в [6]. Результатом функционирования БД является определение «координаты» ошибки (номера процессора), установление её типа (сбой или отказ) и идентификации работы КВР с искаженными результатами ее выполнения. На процессорах, не использованных для работ БД, продолжают выполняться работы базового КВРБ2 (или КВРБ3) в соответствии с правилом 2.
Правило 4. В случае обнаружения (с помощью БД) сбоя при выполнении любой работы аj КВРБ2 (или КВРБ3) или работы bj, а также в случае сбоя при выполнении любой работы 
резервной ветви КВР, подмножество {al} работ «отката» является пустым (кроме «работ отката по прерыванию БД»).
В остальных случаях подмножество {al} работ «отката» может оказаться не пустым (помимо «работ отката по прерыванию БД») и включает:
– непосредственных или транзитивных преемников работы 
, которые воспользовались искаженными результатами этой работы (назначены на выполнение или уже выполнены) до момента обнаружения ошибки;
– работы исходного или резервного КВРБ2 (или КВРБ3), не являющиеся преемниками работы 
, но выполнялись на отказавшем процессоре до момента обнаружения ошибки.
Правило 5. По окончании выполнения работ БД и работ «отката» {al} в динамике вычислений происходит переход к способу организации вычислительного процесса (алгоритма управления дообслуживанием КВР) – v3, v4, т.е. к использованию только одной ветви вычислений, в соответствии с правилом 6.
Организация резервирования способами v3, v4
Правило 6. Работы сравнения вообще не назначаются на выполнение; исправные процессоры предоставляются работам только исходного КВР (или КВР из работ-версий); результаты выполнения последнего используются в качестве результатов выполнения соответствующего преобразованного КВР.
Пример реализации
На рисунке представлена временная диаграмма одной из возможных реализаций динамического адаптивного МР резервирования, для КВР с N = 12, k = 4.
Временная диаграмма реализации адаптивного динамического многоверсионного резервирования КВР для случая ошибки (сбоя) при выполнении работы-оригинала а5
Работа сравнения b5 в момент времени t(!) обнаружила несоответствие результатов работ а5 и 
. Программный БД показал, что произошел сбой при выполнении работы а5 на процессоре П1. Момент завершения последней работы БД – работы 
– соответствует контрольному событию Z2 – t2*.
В приведенном примере время наступления контрольного события t2* больше значения соответствующего критического времени Тf(Z2)cr. Следовательно, согласно правилу математической модели необходимо переходить к какому-либо другому алгоритму управления дообслуживанием КВР – со значением 
, для которого выполняется условие 
. По таблице прогнозов определяем, что такому условию удовлетворяет способ резервирования v = 2, т.е. переход к реализации КВРБ3, что и отражено на рисунке.
Заключение
Предложен подход к организации адаптивного динамического резервирования взаимосвязанных программных модулей на основе сочетаний двух вариантов многоверсионного резервирования с асинхронным запуском программных модулей (работ) КВР. Разработана математическая модель и алгоритмические методы для исследования свойств и эффектов адаптивного многоверсионного резервирования программных модулей КВР для обеспечения надежного выполнения комплексов резервированных программных модулей в управляющих параллельных вычислительных системах – как в штатном режиме функционирования ВС, так и в условиях ошибок (сбоев или отказов).
Рецензенты:
Каравай М.Ф., д.т.н., зав. лаб., Институт проблем управления им. В.А. Трапезникова Российской академии наук, г. Москва;
Полетыкин А.Г., д.т.н., зав. лаб., Институт проблем управления им. В.А. Трапезникова Российской академии наук, г. Москва.
Работа поступила в редакцию 15.07.2014.