Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,087

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

Исаева Н.А. 1 Милков М.Л. 1
1 ФГБУН «Институт проблем управления им. В.А. Трапезникова» Российской академии наук
Рассматривается одно из направлений развития компьютерной технологии, направленной на обеспечение надежного выполнения сложных наборов задач (комплексов взаимосвязанных программных модулей) со случайными временами их выполнения в управляющих параллельных вычислительных системах реального времени. Цель работы – разработка и исследование адаптивного метода резервирования вычислительных процессов, базирующегося на сочетании различных вариантов многоверсионного их резервирования с асинхронным запуском программных модулей. Предложена математическая модель и правила ее функционирования для исследования свойств и эффектов динамического адаптивного многоверсионного резервирования программных модулей на основе прогнозирования надежного их выполнения в управляющих параллельных вычислительных системах – как в штатном режиме функционирования, так и в условиях ошибок (сбоев или отказов).
управляющие параллельные вычислительные системы
многоверсионное резервирование
отказоустойчивость
1. Елисеев В.В., Игнатущенко В.В. О проблеме надежного выполнения сложных наборов задач в управляющих параллельных вычислительных системах // Проблемы управления. – 2006. – № 6. – С. 6–18.
2. Игнатущенко В.В., Исаева Н.А. Резервирование взаимосвязанных программных модулей для управляющих параллельных вычислительных систем: организация, оценка отказоустойчивости, формализованное описание // Автоматика и телемеханика. – 2008. – № 10. – С. 142–161.
3. Игнатущенко В.В., Исаева Н.А. Интеллектуальное динамическое управление параллельными резервированными взаимосвязанными задачами со случайными временами их выполнения в управляющих параллельных вычислительных системах // Параллельные вычисления и задачи управления: труды пятой международной конференции (PACO’2010). – М.: Институт проблем управления им. В.А. Трапезникова, РАН, 2010. – С. 643–651.
4. Исаева Н.А. Организация динамического адаптивного резервирования взаимосвязанных программных модулей в управляющих параллельных вычислительных системах реального времени // Управление развитием крупномасштабных систем: Труды пятой международной конференции (MLSD’2011) (3–5 октября 2011 г., Москва, Россия). Т. II. – М.: Институт проблем управления им. В.А. Трапезникова, РАН, 2011. – С. 230–238.
5. Игнатущенко В.В., Милков М.Л., Сидоров А.В. Многоверсионное резервирование взаимозависимых параллельных задач для управляющих параллельных вычислительных систем: формализованное описание, оценка отказоустойчивости // Надежность. – 2009. – № 4. – С. 44–61.
6. Милков М.Л. Исследование способов диспетчеризации работ для одного из вариантов многоверсионного резервирования взаимосвязанных программных модулей в управляющих параллельных вычислительных системах // Открытое образование. – 2011. – № 2 (85)., Ч. 2. – С. 48–52.
7. Исаева Н.А., Милков М.Л. Организация многоверсионного резервирования взаимосвязанных задач со случайными временами их выполнения в управляющих параллельных вычислительных системах реального времени: новый подход // Управление развитием крупномасштабных систем: труды пятой международной конференции (MLSD’2011) (3–5 октября 2011 г., Москва, Россия). Т. II. – М.: Институт проблем управления им. В.А. Трапезникова, РАН, 2011. – С. 152–157.
8. Исаева Н.А., Милков М.Л. Организация диагностирования ошибок для одного из вариантов многоверсионного резервирования взаимосвязанных программных модулей в управляющих параллельных вычислительных системах // Параллельные вычисления и задачи управления: Труды шестой Международной конференции (PACO’2012) (24–26 октября 2012 г., Москва, Россия). – М.: Институт проблем управления им. В.А. Трапезникова, РАН, 2012. – С. 140–149.
9. Исаева Н.А. Унифицированная математическая модель системы массового обслуживания для прогнозирования надежного выполнения взаимосвязанных программных модулей (задач) при различных методах и сочетаниях их резервирования в управляющих параллельных вычислительных системах // Открытое образование. – 2011. – № 2 (85)., Ч. 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.


Библиографическая ссылка

Исаева Н.А., Милков М.Л. ДИНАМИЧЕСКОЕ УПРАВЛЕНИЕ НАДЕЖНЫМ ВЫПОЛНЕНИЕМ КОМПЛЕКСОВ ВЗАИМОСВЯЗАННЫХ ПРОГРАММНЫХ МОДУЛЕЙ НА ОСНОВЕ АДАПТИВНОГО МНОГОВЕРСИОННОГО ИХ РЕЗЕРВИРОВАНИЯ В ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ // Фундаментальные исследования. – 2014. – № 9-5. – С. 983-987;
URL: http://fundamental-research.ru/ru/article/view?id=35001 (дата обращения: 04.07.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074