В работе предлагается и исследуется один из вариантов организации адаптивного метода резервирования вычислительных процессов, базирующийся на сочетании различных вариантов синхронного (СР) [5-7] и асинхронного (АР) [8] методов резервирования КВР.
Адаптивное резервирование организуется на основе как синхронного, так и асинхронного резервирования наборов взаимосвязанных процессов (при котором K>1 идентичных копий каждого процесса могут выполняться как синхронно, так и асинхронно – с запаздыванием – по отношению один к другому) с использованием оригинальных математических моделей, а также алгоритмических средств, которые обеспечивают не только диагностику и локализацию неисправностей вычислительных ресурсов параллельных ВС и корректное восстановление процессов, но и включают математические методы оценки влияния случайных неисправностей на время выполнения сложных взаимосвязанных процессов.
Цель данного исследования – организация адаптивного метода резервирования вычислительных процессов, базирующегося на сочетании различных вариантов синхронного и асинхронного их резервирования в параллельной ВС; разработка математической модели для исследования свойств и эффектов динамического адаптивного резервирования программных модулей КВР на основе статического прогнозирования надежного их выполнения в параллельных вычислительных системах – как в штатном режиме функционирования, так и в условиях ошибок (сбоев или отказов).
Материал и методы исследования. Теоретической базой разработки являются математический аппарат обрывающихся марковских процессов (ОМП), статистических методов и теории массового обслуживания (ТМО), графовые модели КВР, математические модели синхронного и резервированных КВР в параллельных ВС [5-8], методология динамического управления надежным выполнением КВР на основе адаптивного их резервирования в управляющих параллельных ВС [4].
Результаты такого моделирования могут быть использованы для повышения отказоустойчивости управляющих параллельных ВС.
1. Организация адаптивного резервирования КВР
Базовый КВР (в терминологии и понятиях [1; 2]) включает исходный и резервный КВР и соответствует штатному (без ошибок) выполнению КВР; исходный КВР и резервный КВР образуют две параллельные «ветви» вычислений, независимые по данным одна от другой.
Как и в [5-8], – рассматриваются варианты СР и АР работ КВР с кратностью резервирования Z=2, т.е. каждой работе-оригиналу aj исходного КВР соответствует работа-копия aj' резервного КВР. Сравнение результатов этих работ осуществляется с помощью дополнительного программного модуля - работы сравнения bj.
Для организации динамического адаптивного резервирования КВР рассматриваются следующие f версии (где f – номер версии) реализации базовых КВР, состоящих из двух «ветвей» вычислений:
1) синхронное резервирование каждой работы aj исходного КВР с выполнением одноименной работы сравнения bj на том же процессоре, на котором выполнялась работа-копия aj' (как в [5]);
2) синхронное резервирование каждой работы aj исходного КВР с выполнением одноименной работы сравнения bj на дополнительном процессоре, на котором выполнялась работа-копия aj' (как в [6-7]);
3) асинхронное резервирование каждой работы aj исходного КВР с использованием одной работы сравнения bj (как в [8]);
4) реализация исходного КВР без резервирования его работ.
Ключевыми понятиями для организации динамического адаптивного резервирования КВР являются контрольные события Zj, тестовый фрагмент и Таблица прогнозов, которая содержит набор «критических точек» Tf(j)cr, соответствующих контрольным событиям Zj [1; 4]. Контрольные события Zj - события завершения некоторых работ aj КВР, например, отнесенных к «критическим процессам» КВР.
По тестовым фрагментам КВР оценивается время дообслуживания КВР в целом [4]. По контрольным событиям Zj анализируются состояния процесса реализации КВР в ВС и осуществляется управление этим процессом на основе сравнения прогнозируемого (в статике) времени выполнения тестовых фрагментов КВР с временными параметрами реальных событий, происходящих в системе в динамике.
Смысл «критической точки» заключается в следующем: если дообслуживание КВР (выполнение его тестового фрагмента) начинается не позже момента Tf(j)cr – момента наиболее позднего начала выполнения тестового фрагмента КВР для каждой версии f реализации КВР, то обеспечивается «штатное» выполнение КВР в целом за время, не большее директивного времени Тmax, с заданной вероятностью Р. По контрольному событию Zj возможен переход к динамическому управлению резервированными вычислительными процессами в режиме реального времени выполнения КВР f способами (алгоритмами управления процессами дообслуживания КВР). Таким образом, заранее, в статике (т.е. до выполнения задач в ВС), Таблица прогнозов формируется значениями «критических точек» Tf(j)cr по предложенным в [4] процедурам.
2. Математическая модель
Для проведения исследования описанного подхода к организации адаптивного резервирования КВР разработана модифицированная математическая модель. По структуре эта модель аналогична унифицированной математической модели по [9], - при этом параметры состояний и правила ее функционирования задаются с учетом свойств и характерных особенностей рассматриваемых вариантов СР и АР.
Как и в [9], предлагаемая модель представляется в виде однофазной СМО, состоящей из k ³ 2 обслуживающих приборов ОП (процессоров – П), буфера Б для готовых к выполнению работ, которые поступают из пула, содержащего в исходном состоянии N работ.
Пусть T - время жизни системы - время выполнения преобразованного КВР из N работ при заданной кратности резервирования Z, C работ сравнения, D работ программного блока диагностирования (БД) и Q работ «отката». Функционирование такой СМО можно описать обрывающимся Марковским процессом (ОМП) X(t), tÎ [0,T) над следующим множеством состояний:
________________ ____ ____ ____
(1) X = {(I; P; V; m): m= 0; (Z + С)N + D +Q; С = 1, Z; D = 0, 5; Q = 0, N}, где:
I = (i1, . . . ,iw) – номера работ в буфере Б, w – число работ в Б, причем w = 0, (Z+ С) (N-1);
P = (p1, …, pi, . . . , pk) – вектор состояний ОП, i-й элемент этого вектора содержит номер работы, которая выполняется на ОПi, k – общее число ОП (процессоров ВС);
V = (
1, …,i, . . . ,k) – набор векторов общей
(суммарной) размерности (Z + С)N + D + Q, что соответствует общему числу (Z+С)N работ базового КВР, БД и Q работ «отката»; вектор i этого набора соответствует i-му ОПi; элементами вектора i являются номера тех работ, которые уже выполнены на
ОПi; m – общее
количество выполненных работ преобразованного КВР, соответствующее сумме работ базового КВР, БД и
работ «отката».
Отметим, что при штатном выполнении базового КВР, т.е. при отсутствии ошибок процессоров ВС (D = 0, Q = 0), мы получаем базовую математическую модель СМО для исследования и прогнозирования времени выполнения базового КВР.
Правила функционирования разработанной математической модели отражают специфические особенности организации сочетания различных вариантов синхронного [5-7] и асинхронного [8] методов резервирования КВР, программных диагностических процедур и формирования работ «отката» [9].
Правило 1. Готовые к выполнению работы-оригиналы аj и их резервные работы aj' базового КВР выбираются из буфера Б обязательно «парами» и синхронно назначаются на обслуживание на два различных процессора П («парный ресурс»), по известному критерию диспетчеризации «ранг rj соответствующей вершины графа КВР / связность sj вершины» [1; 2].
Правило 2. Все работы сравнения bj базового КВР назначаются на выполнение на дополнительный (специально выделенный для работ сравнений) процессор при завершении выполнения соответствующих (одноименных) работ-оригиналов аj и резервных работ aj'.
Правило 3. Если при выполнении работы сравнения обнаружено несовпадение результатов выполнения работы аj и aj', то с абсолютным приоритетом назначаются на выполнение работы программного блока диагностирования (БД). Результатом функционирования БД является определение «координаты» ошибки (номера процессора Пr, на котором обнаружена неисправность) и установление её типа (сбой или отказ). На процессорах, не использованных для работ БД, продолжают выполняться работы базового КВР в соответствии с правилом 2.
Правило 4. Если в результате функционирования БД установлен сбой или отказ процессора Пr при выполнении работы aj (или aj'), принадлежащей «ветви» исходного КВР (или «ветви» резервного КВР), то правильными, неискаженными принимаются результаты выполнения работ только одной из «ветвей», не включающей aj (или aj'); подмножество {al} работ «отката» (работы, которые необходимо перезапускать на выполнение для корректного восстановления вычислительного процесса) состоит только из работ «корректной» ветви, прерванных работами БД. В случае отказа процессора он признается неисправным и в дальнейшем не используется. После обнаружения неисправности работы сравнения вообще НЕ назначаются на выполнение; исправные процессоры предоставляются работам только «корректного» КВР; результаты выполнения последнего используются в качестве результатов выполнения соответствующего преобразованного КВР.
Вариант асинхронного резервирования работ КВР [8] отличается от приведенного варианта СР только тем, что готовые к выполнению работы-оригиналы аj и их резервные работы aj' базового КВР асинхронно выбираются из буфера Б и назначаются на обслуживание на два различных процессора П, по известному критерию диспетчеризации «ранг rj соответствующей вершины графа КВР/связность sj вершины».
3. Пример реализации
На рис. 1 представлен фрагмент временной диаграммы адаптивного выполнения базового КВР при одиночной ошибке (сбое). Пример иллюстрирует последовательность смены СР на АР, а также правила назначения работ на процессоры и порядок выполнения процедур диагностирования для случая сбоя на процессоре П3 при выполнении работы a6.
Рис. 1. Временная диаграмма реализации адаптивного динамического резервирования КВР для случая ошибки (сбоя) при выполнении работы-оригинала a6.
Работа сравнения b5 в момент времени t5 не обнаружила несоответствие результатов работ а5 и а5'. Момент завершения работы b5 соответствует контрольному событию Z1. При этом время наступления контрольного события t5 меньше значения соответствующего критического времени Тf(Z1)cr. Следовательно, продолжено выполнение КВР в штатном режиме.
Работа сравнения b6 в момент времени t(!) обнаружила несоответствие результатов работ а6 и а6'. Программный БД (работы БД на рис. 1 заштрихованы) показал, что произошел сбой при выполнении работы а6 на процессоре П3. Момент завершения последней работы БД - работы с6 - соответствует контрольному событию Z2.
В приведенном примере время наступления контрольного события t(!) больше значения соответствующего критического времени Тf(Z2)cr. Следовательно, согласно правилу математической модели необходимо переходить к какому-либо другому алгоритму управления дообслуживанием КВР - со значением Тf(Z2)cr, для которого выполняется условие t(!) £ Тf(Z2)cr. По Таблице прогнозов определяем, что такому условию удовлетворяет способ резервирования f = 3, т.е. переход к реализации асинхронного резервировани работ aj и не назначению контрольных работ bj, что и отражено на рис. 1.
Заключение
Предложен подход к организации адаптивного (перенастраиваемое в динамике по реальным событиям в системе) резервирования взаимосвязанных программных модулей на основе сочетании вариантов синхронного и асинхронного их резервирования. Разработана математическая модель и алгоритмические методы для исследования свойств и эффектов адаптивного резервирования программных модулей КВР для обеспечения надежного выполнения комплексов резервированных программных модулей в управляющих параллельных вычислительных системах – как в штатном режиме функционирования ВС, так и в условиях ошибок (сбоев или отказов).
Рецензенты:Вишневский В.М., д.т.н., зав. лаб., Институт проблем управления им. В.А. Трапезникова Российской академии наук, г. Москва;
Бабаян Р.Р., д.т.н., зав. лаб., Институт проблем управления им. В.А. Трапезникова Российской академии наук, г. Москва.