Научный журнал

Фундаментальные исследования

ISSN 1812-7339

"Перечень" ВАК

ИФ РИНЦ = 1,674

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Исаева Н.А. 1 Милков М.Л. 1

---

1 ФГБУН «Институт проблем управления им. В.А. Трапезникова» Российской академии наук

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

Статья в формате PDF

570 KB

управляющие параллельные вычислительные системы

многоверсионное резервирование

отказоустойчивость

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]. Под надежным выполнением конкретного КВР в параллельной ВС понимается выполнение его за время, не превышающее заданное (пользователем) директивное время T_max, с требуемой (удовлетворяющей пользователя) вероятностью Р [1]. Надежное выполнение КВР должно обеспечиваться как в штатном режиме функционирования управляющей ВС, так и в условиях внезапных неисправностей (сбоев, отказов) ее вычислительных ресурсов.

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

Под адаптивным резервированием вычислительных процессов (программных модулей – работ КВР) понимается выбор и настройка различных способов резервирования вычислительных процессов и/или их сочетаний в динамике выполнения КВР. Выбор и настройка способов резервирования КВР осуществляются на основе статического (до выполнения КВР) прогнозирования надежного выполнения заданного пользователем КВР, а также на основе анализа, уточнения и оперативного использования статических прогнозов (рассматриваемых способов резервирования) в процессе реализации задач в параллельной ВС с учетом текущего состояния процессов и системы, в частности – в условиях сбоев или отказов ее вычислительных ресурсов [3, 4]. Перспективными компонентами адаптивного резервирования КВР являются рассматриваемые здесь варианты МР [5–8].

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

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

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

Организация адаптивного многоверсинного резервирования КВР

Базовый КВР (в терминологии и понятиях [1, 2]) включает исходный и резервный КВР и соответствует штатному (без ошибок) выполнению КВР; исходный КВР и резервный КВР образуют две параллельные «ветви» вычислений, независимые по данным одна от другой.

Как и в [5–8] – рассматриваются варианты МР работ КВР с кратностью резервирования Z = 2, т.е. каждой работе-оригиналу a_j исходного КВР соответствует работа-версия a_j′ резервного КВР. Сравнение результатов этих работ осуществляется с помощью дополнительного программного модуля – работы сравнения b_j. Для организации динамического адаптивного резервирования КВР рассмотрим следующие f версии (где f – номер версии) реализации базовых КВР, состоящих из двух «ветвей» вычислений:

1. Исходный КВР и КВР из работ-версий по [7, 8], – обозначим его как КВРБ1.

2. Исходный КВР и резервный КВР из упрощенных вариантов исходных работ по [6, 7], – обозначим его как КВРБ2.

3. Исходный КВР состоит из работ-версий КВР_Б1, а резервный КВР из упрощенных вариантов работ-версий (аналогично первому варианту МР по [5, 6]) – КВР_Б3.

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

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

Смысл «критической точки» заключается в следующем: если дообслуживание КВР (выполнение его тестового фрагмента) начинается не позже момента  – момента наиболее позднего начала выполнения тестового фрагмента КВР для каждой версии f реализации КВР, то обеспечивается «штатное» выполнение КВР в целом за время, не большее директивного времени Т_max, с заданной вероятностью Р. По контрольному событию Z_j возможен переход к динамическому управлению резервированными вычислительными процессами в режиме реального времени выполнения КВР следующими v (v = 1, ...,4) способами (алгоритмами управления процессами дообслуживания КВР): КВР _Б2 (способ v₁); КВР_Б3 (способ v₂); использование только одной «ветви» вычислений – исходного КВР (способ v₃); КВР из работ-версий (способ v₄); либо вычислительный процесс может быть продолжен в «штатном» режиме – КВР_Б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]. Опишем правила функционирования математической модели при возникновении контрольного события Z_j:

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

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

Организация резервирования способами v₁, v₂

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

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

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

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

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

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

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

Организация резервирования способами v₃, v₄

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

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

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

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

Работа сравнения b₅ в момент времени t_(!) обнаружила несоответствие результатов работ а₅ и . Программный БД показал, что произошел сбой при выполнении работы а₅ на процессоре П₁. Момент завершения последней работы БД – работы  – соответствует контрольному событию Z₂ – t₂*.

В приведенном примере время наступления контрольного события t₂* больше значения соответствующего критического времени Т_f(Z₂)_cr. Следовательно, согласно правилу математической модели необходимо переходить к какому-либо другому алгоритму управления дообслуживанием КВР – со значением , для которого выполняется условие . По таблице прогнозов определяем, что такому условию удовлетворяет способ резервирования v = 2, т.е. переход к реализации КВР_Б3, что и отражено на рисунке.

Заключение

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

Рецензенты:

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

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

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

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