Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,087

DYNAMIC CONTROL OF RELIABLE REALIZATION OF COMPLEXES OF THE INTERCONNECTED PROGRAM MODULES ON THE BASIS OF ADAPTIVE MULTIVERSION OF THEIR REDUNDANTISATION IN PARALLEL COMPUTING SYSTEMS OF REAL TIME

Isaeva N.A. 1 Milkov M.L. 1
1 V.A. Trapeznikov Institute of Control Sciences Russian Academy of Sciences
Рассматривается одно из направлений развития компьютерной технологии, направленной на обеспечение надежного выполнения сложных наборов задач (комплексов взаимосвязанных программных модулей) со случайными временами их выполнения в управляющих параллельных вычислительных системах реального времени. Цель работы – разработка и исследование адаптивного метода резервирования вычислительных процессов, базирующегося на сочетании различных вариантов многоверсионного их резервирования с асинхронным запуском программных модулей. Предложена математическая модель и правила ее функционирования для исследования свойств и эффектов динамического адаптивного многоверсионного резервирования программных модулей на основе прогнозирования надежного их выполнения в управляющих параллельных вычислительных системах – как в штатном режиме функционирования, так и в условиях ошибок (сбоев или отказов).
One of the directions of development of the computer technology aimed at providing of reliable execution of difficult sets of tasks (complexes of interdependent program modules) having random times of execution in parallel control computing systems of real-time is considered. The operation purpose – development and research of the adaptive method of redundancy of the calculating processes basing on a combination of different variants of multiversion their redundancy with asynchronous start of program modules. The mathematical model and rules of its functioning for research of properties and effects of dynamic adaptive multiversion redundancy of program modules on the basis of forecasting of their reliable execution in parallel control computing systems – both in a standard mode of functioning, and in the conditions of errors (faults or failures) is offered.
parallel control computing systems
multiversion redundancy
fault tolerance
1. Eliseev V.V., Ignatushhenko V.V. O probleme nadezhnogo vypolneniya slozhnykh naborov zadach v upravlyayushhikh parallel’nykh vychislitel’nykh sistemakh // Problemy upravleniya. 2006. no. 6. рр. 6–18.
2. Ignatushhenko V.V., Isaeva N.А. Rezervirovanie vzaimosvyazannykh programmnykh modulej dlya upravlyayushhikh parallel’nykh vychislitel’nykh sistem: organizatsiya, otsenka otkazoustojchivosti, formalizovannoe opisanie // Аvtomatika i telemekhanika. 2008. no. 10. рр. 142–161.
3. Ignatushhenko V.V., Isaeva N.А. Intellektual’noe dinamicheskoe upravlenie parallel’nymi rezervirovannymi vzaimosvyazannymi zadachami so sluchajnymi vremenami ikh vypolneniya v upravlyayushhikh parallel’nykh vychislitel’nykh sistemakh // Trudy pyatoj mezhdunarodnoj konferentsii «Parallel’nye vychisleniya i zadachi upravleniya» (PACO’2010). M.: Institut problem upravleniya im. V.А. Trapeznikova, RАN. 2010. рр. 643–651.
4. Isaeva N.А. Organizatsiya dinamicheskogo adaptivnogo rezervirovaniya vzaimosvyazannykh programmnykh modulej v upravlyayushhikh parallel’nykh vychislitel’nykh sistemakh real’nogo vremeni // Trudy pyatoj mezhdunarodnoj konferentsii «Upravlenie razvitiem krupnomasshtabnykh sistem (MLSD’2011)» (3–5 oktyabrya 2011 g., Moskva, Rossiya). Tom II. M.: Institut problem upravleniya im. V.А. Trapeznikova, RАN. 2011. рр. 230–238.
5. Ignatushhenko V.V., Milkov M.L., Sidorov А.V. Mnogoversionnoe rezervirovanie vzaimozavisimykh parallel’nykh zadach dlya upravlyayushhikh parallel’nykh vychislitel’nykh sistem: formalizovannoe opisanie, otsenka otkazoustojchivosti // Nadezhnost’. 2009. no. 4. рр. 44–61.
6. Milkov M.L. Issledovanie sposobov dispetcherizatsii rabot dlya odnogo iz variantov mnogoversionnogo rezervirovaniya vzaimosvyazannykh programmnykh modulej v upravlyayushhikh parallel’nykh vychislitel’nykh sistemakh // Otkrytoe obrazovanie. 2011. no. 2 (85)., CH. 2. рр. 48–52.
7. Isaeva N.А., Milkov M.L. Organizatsiya mnogoversionnogo rezervirovaniya vzaimosvyazannykh zadach so sluchajnymi vremenami ikh vypolneniya v upravlyayushhikh parallel’nykh vychislitel’nykh sistemakh real’nogo vremeni: novyj podkhod // Trudy pyatoj mezhdunarodnoj konferentsii Upravlenie razvitiem krupnomasshtabnykh sistem (MLSD’2011) (3–5 oktyabrya 2011 g., Moskva, Rossiya). T. II. M.: Institut problem upravleniya im. V.А. Trapeznikova, RАN. 2011. S. 152–157.
8. Isaeva N.А., Milkov M.L. Organizatsiya diagnostirovaniya oshibok dlya odnogo iz variantov mnogoversionnogo rezervirovaniya vzaimosvyazannykh programmnykh modulej v upravlyayushhikh parallel’nykh vychislitel’nykh sistemakh // Trudy shestoj Mezhdunarodnoj konferentsii «Parallel’nye vychisleniya i zadachi upravleniya» (PACO’2012) (24-26 oktyabrya 2012 g., Moskva, Rossiya). M.: Institut problem upravleniya im. V.А. Trapeznikova, RАN. 2012. рр. 140–149.
9. Isaeva N.А. Unifitsirovannaya matematicheskaya model’ sistemy massovogo obsluzhivaniya dlya prognozirovaniya nadezhnogo vypolneniya vzaimosvyazannykh programmnykh modulej (zadach) pri razlichnykh metodakh i sochetaniyakh ikh rezervirovaniya v upravlyayushhikh parallel’nykh vychislitel’nykh sistemakh // Otkrytoe obrazovanie. 2011. no. 2 (85)., CH. 2. рр. 55–59.

Излагаемое исследование является составной частью разработки компьютерной технологии, направленной на обеспечение надежного выполнения сложных комплексов взаимосвязанных работ (КВР), являющихся комплексами взаимосвязанных программных модулей со случайными временами их выполнения в параллельных управляющих вычислительных системах (ВС), функционирующих в контурах управления реального времени [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, тестовый фрагмент и Таблица прогнозов, которая содержит набор «критических точек» isaeva01.wmf, соответствующих контрольным событиям Zj [1, 4]. Контрольные события Zj, – события завершения некоторых работ aj КВР – например, отнесенных к «критическим процессам» КВР.

По тестовым фрагментам КВР оценивается время дообслуживания КВР в целом [4]. По контрольным событиям Zj анализируются состояния процесса реализации КВР в ВС и осуществляется управление этим процессом на основе сравнения прогнозируемого (в статике) времени выполнения тестовых фрагментов КВР с временными параметрами реальных событий, происходящих в системе в динамике.

Смысл «критической точки» заключается в следующем: если дообслуживание КВР (выполнение его тестового фрагмента) начинается не позже момента isaeva02.wmf – момента наиболее позднего начала выполнения тестового фрагмента КВР для каждой версии f реализации КВР, то обеспечивается «штатное» выполнение КВР в целом за время, не большее директивного времени Тmax, с заданной вероятностью Р. По контрольному событию Zj возможен переход к динамическому управлению резервированными вычислительными процессами в режиме реального времени выполнения КВР следующими v (v = 1, ...,4) способами (алгоритмами управления процессами дообслуживания КВР): КВР Б2 (способ v1); КВРБ3 (способ v2); использование только одной «ветви» вычислений – исходного КВР (способ v3); КВР из работ-версий (способ v4); либо вычислительный процесс может быть продолжен в «штатном» режиме – КВРБ1.

Для реализации адаптивного МР резервирования – Таблица прогнозов содержит f (в нашем случае – пять) «критических точек» isaeva03.wmf для каждого контрольного события Zj: isaeva04.wmf – для продолжения «штатного» выполнения базового КВРБ1; isaeva05.wmf (v = 1, ...,4) – для перехода к одному из четырех вышеописанных способов надежного дообслуживания базового КВР. Таким образом, заранее, в статике (т.е. до выполнения задач в ВС), Таблица прогнозов формируется значениями «критических точек» isaeva06.wmf по предложенным в [4] процедурам.

Математическая модель

Для проведения исследования описанного подхода к организации адаптивного резервирования КВР на основе сочетания двух вариантов МР с асинхронным запуском работ КВР, разработана модифицированная математическая модель. По структуре эта модель аналогична унифицированной математической модели по [9] – при этом параметры состояний и правила ее функционирования задаются с учетом свойств и характерных особенностей рассматриваемых вариантов МР.

Как и в [9], предлагаемая модель представляется в виде однофазной СМО состоящей из k ≥ 2 обслуживающих приборов ОП (процессоров – П), буфера Б для готовых к выполнению работ, которые поступают из пула, содержащего в исходном состоянии N работ.

Пусть T – время жизни системы – время выполнения преобразованного КВР из N работ при заданной кратности резервирования Z, C работ сравнения, D работ программного блока диагностирования (БД) и Q работ «отката». Функционирование такой СМО можно описать обрывающимся Марковским процессом (ОМП) X(t), t ∈ [0, T) над следующим множеством состояний:

isaeva07.wmf (1)

где I = (i1, ..., iw) – номера работ в буфере Б; w – число работ в Б, причем isaeva08.wmf; P = (p1, …, pi, ..., pk) – вектор состояний ОП, i-й элемент этого вектора содержит номер работы, которая выполняется на ОПi; k – общее число ОП (процессоров ВС); isaeva09.wmf – набор векторов общей (суммарной) размерности (Z + С)N + D + Q, что соответствует общему числу (Z + С)N работ базового КВР, БД и Q работ «отката»; вектор isaeva10.wmf этого набора соответствует i-му ОПi; элементами вектора isaeva11.wmf являются номера тех работ, которые уже выполнены на ОПi; m – общее количество выполненных работ преобразованного КВР, соответствующее сумме работ базового КВР, БД и работ «отката».

Отметим, что при штатном выполнении базового КВР, т.е. при отсутствии ошибок процессоров ВС (D = 0, Q = 0), мы получаем базовую математическую модель СМО для исследования и прогнозирования времени выполнения базового КВР.

Правила функционирования математической модели – это правила диспетчеризации работ, отражающие особенности организации различных способов резервирования КВР, программных диагностических процедур и формирования работ «отката» [9]. Опишем правила функционирования математической модели при возникновении контрольного события Zj:

Организация резервирования штатным способом v0

Правило 1. Если при возникновении контрольного события Zj время дообслуживания КВР isaeva12.wmf, то в динамике вычислений происходит переход к одному из вышеописанных способов v, – со значением isaeva14.wmf, для которого выполняется условие isaeva13.wmf  – в соответствии с далее приведенными правилами 2–5 или правилом 6.

Организация резервирования способами v1, v2

Правило 2. Готовые к выполнению работы-оригиналы аj и работы-версии isaeva15.wmf выбираются на выполнение на свободные процессоры ВС (обязательно различные) по известному критерию диспетчеризации «ранг rj соответствующей вершины графа базового КВРБ2 (или КВРБ3) / связность sj вершины» [1,2]. На процессор П, на котором выполнялась работа-оригинал аj, с абсолютным приоритетом назначается работа сравнения bj.

Правило 3. Если при выполнении работы bj обнаружено несовпадение результатов выполнения работы аj и isaeva16.wmf, то с абсолютным приоритетом назначаются на выполнение работы БД по правилам, рассмотренным в [6]. Результатом функционирования БД является определение «координаты» ошибки (номера процессора), установление её типа (сбой или отказ) и идентификации работы КВР с искаженными результатами ее выполнения. На процессорах, не использованных для работ БД, продолжают выполняться работы базового КВРБ2 (или КВРБ3) в соответствии с правилом 2.

Правило 4. В случае обнаружения (с помощью БД) сбоя при выполнении любой работы аj КВРБ2 (или КВРБ3) или работы bj, а также в случае сбоя при выполнении любой работы isaeva17.wmf резервной ветви КВР, подмножество {al} работ «отката» является пустым (кроме «работ отката по прерыванию БД»).

В остальных случаях подмножество {al} работ «отката» может оказаться не пустым (помимо «работ отката по прерыванию БД») и включает:

– непосредственных или транзитивных преемников работы isaeva18.wmf, которые воспользовались искаженными результатами этой работы (назначены на выполнение или уже выполнены) до момента обнаружения ошибки;

– работы исходного или резервного КВРБ2 (или КВРБ3), не являющиеся преемниками работы isaeva19.wmf, но выполнялись на отказавшем процессоре до момента обнаружения ошибки.

Правило 5. По окончании выполнения работ БД и работ «отката» {al} в динамике вычислений происходит переход к способу организации вычислительного процесса (алгоритма управления дообслуживанием КВР) – v3, v4, т.е. к использованию только одной ветви вычислений, в соответствии с правилом 6.

Организация резервирования способами v3, v4

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

Пример реализации

На рисунке представлена временная диаграмма одной из возможных реализаций динамического адаптивного МР резервирования, для КВР с N = 12, k = 4.

pic_20.tif

Временная диаграмма реализации адаптивного динамического многоверсионного резервирования КВР для случая ошибки (сбоя) при выполнении работы-оригинала а5

Работа сравнения b5 в момент времени t(!) обнаружила несоответствие результатов работ а5 и isaeva20.wmf. Программный БД показал, что произошел сбой при выполнении работы а5 на процессоре П1. Момент завершения последней работы БД – работы isaeva21.wmf – соответствует контрольному событию Z2 – t2*.

В приведенном примере время наступления контрольного события t2* больше значения соответствующего критического времени Тf(Z2)cr. Следовательно, согласно правилу математической модели необходимо переходить к какому-либо другому алгоритму управления дообслуживанием КВР – со значением isaeva24.wmf, для которого выполняется условие isaeva25.wmf. По таблице прогнозов определяем, что такому условию удовлетворяет способ резервирования v = 2, т.е. переход к реализации КВРБ3, что и отражено на рисунке.

Заключение

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

Рецензенты:

Каравай М.Ф., д.т.н., зав. лаб., Институт проблем управления им. В.А. Трапезникова Российской академии наук, г. Москва;

Полетыкин А.Г., д.т.н., зав. лаб., Институт проблем управления им. В.А. Трапезникова Российской академии наук, г. Москва.

Работа поступила в редакцию 15.07.2014.