Динамическое адаптивное резервирование комплексов взаимосвязанных программных модулей на основе сочетания различных вариантов синхронного и асинхронного их резервирования в управляющих параллельных вычислительных системах реального времени

Тип работы:
Реферат
Предмет:
Общие и комплексные проблемы естественных и точных наук


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 272. 26
ДИНАМИЧЕСКОЕ АДАПТИВНОЕ РЕЗЕРВИРОВАНИЕ КОМПЛЕКСОВ ВЗАИМОСВЯЗАННЫХ ПРОГРАММНЫХ МОДУЛЕЙ НА ОСНОВЕ СОЧЕТАНИЯ РАЗЛИЧНЫХ ВАРИАНТОВ СИНХРОННОГО И АСИНХРОННОГО ИХ РЕЗЕРВИРОВАНИЯ В УПРАВЛЯЮЩИХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ
Исаева Н. А., хПанов С.С.
1 Федеральное государственное бюджетное учреждение науки ««Институт проблем управления им. В. А. Трапезникова Российской академии наук», Москва, Россия (117 997, г. Москва, ул. Профсоюзная, 65), e-mail:
nat_i@ipu. ru_
Рассматривается проблема обеспечения надежного выполнения сложных наборов задач (комплексов взаимосвязанных программных моделей) со случайными временами их выполнения в управляющих параллельных вычислительных системах реального времени. Цель работы — разработка и исследование адаптивного метода резервирования вычислительных процессов, базирующегося на сочетании различных вариантов синхронного и асинхронного их резервирования в параллельных вычислительных системах. Разработана математическая модель и правила ее функционирования для исследования свойств и эффектов динамического адаптивного сочетания синхронного и асинхронного резервирования программных модулей на основе прогнозирования надежного их выполнения в управляющих параллельных вычислительных системах — как в штатном режиме функционирования, так и в условиях ошибок (сбоев или отказов).
Ключевые слова: управляющие параллельные вычислительные системы, адаптивное, синхронное, асинхронное резервирование, отказоустойчивость.
DYNAMIC ADAPTIVE REDUNDANCY OF COMPLEXES OF THE INTERCONNECTED PROGRAM MODULES ON THE BASIS OF THE COMBINATION OF VARIOUS OPTIONS OF SYNCHRONOUS AND ASYNCHRONOUS REDUNDANCY IN CONTROL PARALLEL COMPUTING SYSTEMS OF REAL TIME
1Isaeva N., 1Panov S.
1V.A. Trapeznikov Institute ofControl Sciences, Russian Academy of Sciences (Profsoyuznaya, 65, Moscow, 117 997,
Russia), e-mail: nat_i@ipu. ru_
The problem of ensuring reliable execution of difficult sets of tasks (complexes of the interconnected program models) having random times of their execution in parallel control computing systems of real time is considered. The work purpose — development and research of an adaptive method of redundancy of the calculating processes basing on a combination of variants of synchronous and their asynchronous redundancy in parallel computing systems. The mathematical model and rules of its functioning for research of properties and effects of a dynamic adaptive combination of synchronous and asynchronous redundancy of program modules on the basis of forecasting of their reliable execution in parallel computing systems — both in a regular mode of functioning, and in the conditions of mistakes (faults or failures) is developed.
Keywords: parallel control computing systems, adaptive, synchronous, asynchronous redundancy, fault tolerance.
Рассматриваемое исследование является составной частью разработки компьютерной технологии, направленной на обеспечение надежного выполнения сложных комплексов программных модулей (названных комплексами взаимосвязанных работ — КВР) со случайными временами их выполнения в параллельных управляющих вычислительных системах (ВС) [1−3]. Под надежным выполнением конкретного КВР в параллельной ВС понимается выполнение его за время, не превышающее заданное директивное время Tmax, с требуемой (удовлетворяющей пользователя) вероятностью Р [1]. В настоящее время упомянутая технология развивается в направлении разработки и исследований различных методов и средств резервирования КВР, в частности адаптивного метода резервирования
как инструмента для динамического управления вычислительными процессами непосредственно в ходе выполнения КВР в управляющих параллельных ВС [4]. В работе предлагается и исследуется один из вариантов организации адаптивного метода резервирования вычислительных процессов, базирующийся на сочетании различных вариантов синхронного (СР) [5−7] и асинхронного (АР) [8] методов резервирования КВР.
Адаптивное резервирование организуется на основе как синхронного, так и асинхронного резервирования наборов взаимосвязанных процессов (при котором К& gt-1 идентичных копий каждого процесса могут выполняться как синхронно, так и асинхронно — с запаздыванием -по отношению один к другому) с использованием оригинальных математических моделей, а также алгоритмических средств, которые обеспечивают не только диагностику и локализацию неисправностей вычислительных ресурсов параллельных ВС и корректное восстановление процессов, но и включают математические методы оценки влияния случайных неисправностей на время выполнения сложных взаимосвязанных процессов. Цель данного исследования — организация адаптивного метода резервирования вычислительных процессов, базирующегося на сочетании различных вариантов синхронного и асинхронного их резервирования в параллельной ВС- разработка математической модели для исследования свойств и эффектов динамического адаптивного резервирования программных модулей КВР на основе статического прогнозирования надежного их выполнения в параллельных вычислительных системах — как в штатном режиме функционирования, так и в условиях ошибок (сбоев или отказов).
Материал и методы исследования. Теоретической базой разработки являются математический аппарат обрывающихся марковских процессов (ОМП), статистических методов и теории массового обслуживания (ТМО), графовые модели КВР, математические модели синхронного и резервированных КВР в параллельных ВС [5−8], методология динамического управления надежным выполнением КВР на основе адаптивного их резервирования в управляющих параллельных ВС [4].
Результаты такого моделирования могут быть использованы для повышения отказоустойчивости управляющих параллельных ВС. 1. Организация адаптивного резервирования КВР
Базовый КВР (в терминологии и понятиях [1- 2]) включает исходный и резервный КВР и соответствует штатному (без ошибок) выполнению КВР- исходный КВР и резервный КВР образуют две параллельные «ветви» вычислений, независимые по данным одна от другой. Как и в [5−8], — рассматриваются варианты СР и АР работ КВР с кратностью резервирования Z=2, т. е. каждой работе-оригиналу а/ исходного КВР соответствует работа-копия а/ резервного КВР. Сравнение результатов этих работ осуществляется с помощью дополнительного программного модуля — работы сравнения Ь/.
Для организации динамического адаптивного резервирования КВР рассматриваются следующие / версии (где / - номер версии) реализации базовых КВР, состоящих из двух «ветвей» вычислений:
1) синхронное резервирование каждой работы а/ исходного КВР с выполнением одноименной работы сравнения Ь/ на том же процессоре, на котором выполнялась работа-копия а/ (как в [5]) —
2) синхронное резервирование каждой работы а/ исходного КВР с выполнением одноименной работы сравнения Ь/ на дополнительном процессоре, на котором выполнялась работа-копия а/ (как в [6−7]) —
3) асинхронное резервирование каждой работы а/ исходного КВР с использованием одной работы сравнения Ь (как в [8]) —
4) реализация исходного КВР без резервирования его работ.
Ключевыми понятиями для организации динамического адаптивного резервирования КВР являются контрольные события 2/, тестовый фрагмент и Таблица прогнозов, которая содержит набор «критических точек» Т^от, соответствующих контрольным событиям 2/ [1- 4]. Контрольные события 2/ - события завершения некоторых работ а/ КВР, например, отнесенных к «критическим процессам» КВР.
По тестовым фрагментам КВР оценивается время дообслуживания КВР в целом [4]. По контрольным событиям 2/ анализируются состояния процесса реализации КВР в ВС и осуществляется управление этим процессом на основе сравнения прогнозируемого (в статике) времени выполнения тестовых фрагментов КВР с временными параметрами реальных событий, происходящих в системе в динамике.
Смысл «критической точки» заключается в следующем: если дообслуживание КВР (выполнение его тестового фрагмента) начинается не позже момента Т^от — момента наиболее позднего начала выполнения тестового фрагмента КВР для каждой версии / реализации КВР, то обеспечивается «штатное» выполнение КВР в целом за время, не большее директивного времени Ттах, с заданной вероятностью Р. По контрольному событию 2/ возможен переход к динамическому управлению резервированными вычислительными процессами в режиме реального времени выполнения КВР / способами (алгоритмами управления процессами дообслуживания КВР). Таким образом, заранее, в статике (т.е. до выполнения задач в ВС), Таблица прогнозов формируется значениями «критических точек» ТрО по предложенным в [4] процедурам. 2. Математическая модель
Для проведения исследования описанного подхода к организации адаптивного резервирования КВР разработана модифицированная математическая модель. По структуре эта модель аналогична унифицированной математической модели по [9], — при этом
параметры состояний и правила ее функционирования задаются с учетом свойств и характерных особенностей рассматриваемых вариантов СР и АР.
Как и в [9], предлагаемая модель представляется в виде однофазной СМО, состоящей из к & gt- 2 обслуживающих приборов ОП (процессоров — П), буфера Б для готовых к выполнению работ, которые поступают из пула, содержащего в исходном состоянии N работ. Пусть Т — время жизни системы — время выполнения преобразованного КВР из N работ при заданной кратности резервирования I, С работ сравнения, Б работ программного блока диагностирования (БД) и Q работ «отката». Функционирование такой СМО можно описать обрывающимся Марковским процессом (ОМП) Х (/), /е [0,Т) над следующим множеством состояний:
(1) X = {(I- Р- V- т): т= 0- (I + С^ + Б +Q- С = 1, I- Б = 0, 5- Q = 0, N1, где: I = (?1,.. ?м& gt-) — номера работ в буфере Б, w — число работ в Б, причем ^ = 0, (1+ С) (N-1) —
Р = (р1, …, р,.. , рк) — вектор состояний ОП, ?-й элемент этого вектора содержит номер работы, которая выполняется на ОП, к — общее число ОП (процессоров ВС) — V = (и 1,…, и,.., и к) — набор векторов общей (суммарной) размерности (I + С) N + Б + Q, что соответствует общему числу (I+С)N работ базового КВР, БД и Q работ «отката" — вектор и, этого набора соответствует ,-му ОП, — элементами вектора и, являются номера тех работ, которые уже выполнены на ОП, — т — общее количество выполненных работ преобразованного КВР, соответствующее сумме работ базового КВР, БД и работ «отката». Отметим, что при штатном выполнении базового КВР, т. е. при отсутствии ошибок процессоров ВС (Б = 0, Q = 0), мы получаем базовую математическую модель СМО для исследования и прогнозирования времени выполнения базового КВР.
Правила функционирования разработанной математической модели отражают специфические особенности организации сочетания различных вариантов синхронного [5−7] и асинхронного [8] методов резервирования КВР, программных диагностических процедур и формирования работ «отката» [9].
Правило 1. Готовые к выполнению работы-оригиналы а] и их резервные работы а/ базового КВР выбираются из буфера Б обязательно «парами» и синхронно назначаются на обслуживание на два различных процессора П («парный ресурс»), по известному критерию диспетчеризации «ранг г/ соответствующей вершины графа КВР / связность а/ вершины» [1- 2].
Правило 2. Все работы сравнения Ь/ базового КВР назначаются на выполнение на дополнительный (специально выделенный для работ сравнений) процессор при завершении выполнения соответствующих (одноименных) работ-оригиналов а] и резервных работ а/. Правило 3. Если при выполнении работы сравнения обнаружено несовпадение результатов выполнения работы а] и а/, то с абсолютным приоритетом назначаются на выполнение
работы программного блока диагностирования (БД). Результатом функционирования БД является определение «координаты» ошибки (номера процессора Пг, на котором обнаружена неисправность) и установление её типа (сбой или отказ). На процессорах, не использованных для работ БД, продолжают выполняться работы базового КВР в соответствии с правилом 2. Правило 4. Если в результате функционирования БД установлен сбой или отказ процессора Пг при выполнении работы а/ (или а/% принадлежащей «ветви» исходного КВР (или «ветви» резервного КВР), то правильными, неискаженными принимаются результаты выполнения работ только одной из «ветвей», не включающей а/ (или а/'-) — подмножество {а/} работ «отката» (работы, которые необходимо перезапускать на выполнение для корректного восстановления вычислительного процесса) состоит только из работ «корректной» ветви, прерванных работами БД. В случае отказа процессора он признается неисправным и в дальнейшем не используется. После обнаружения неисправности работы сравнения вообще НЕ назначаются на выполнение- исправные процессоры предоставляются работам только «корректного» КВР- результаты выполнения последнего используются в качестве результатов выполнения соответствующего преобразованного КВР.
Вариант асинхронного резервирования работ КВР [8] отличается от приведенного варианта СР только тем, что готовые к выполнению работы-оригиналы а/ и их резервные работы а/ базового КВР асинхронно выбираются из буфера Б и назначаются на обслуживание на два различных процессора П, по известному критерию диспетчеризации «ранг г/ соответствующей вершины графа КВР/связность вершины». 3. Пример реализации
На рис. 1 представлен фрагмент временной диаграммы адаптивного выполнения базового КВР при одиночной ошибке (сбое). Пример иллюстрирует последовательность смены СР на АР, а также правила назначения работ на процессоры и порядок выполнения процедур диагностирования для случая сбоя на процессоре Пз при выполнении работы аб.
Рис. 1. Временная диаграмма реализации адаптивного динамического резервирования КВР для случая ошибки (сбоя) при выполнении работы-оригинала аб.
Работа сравнения bs в момент времени ts не обнаружила несоответствие результатов работ а5 и а5. Момент завершения работы bs соответствует контрольному событию Zi. При этом время наступления контрольного события ts меньше значения соответствующего критического времени 7/(Zi)cr. Следовательно, продолжено выполнение КВР в штатном режиме.
Работа сравнения Ьб в момент времени t (!) обнаружила несоответствие результатов работ аб и аб'-. Программный Б Д (работы БД на рис. 1 заштрихованы) показал, что произошел сбой при выполнении работы аб на процессоре Пз. Момент завершения последней работы БД -работы С6 — соответствует контрольному событию Z2.
В приведенном примере время наступления контрольного события t (!) больше значения соответствующего критического времени Т2)сг. Следовательно, согласно правилу математической модели необходимо переходить к какому-либо другому алгоритму управления дообслуживанием КВР — со значением Т2)сг, для которого выполняется условие t (!) & lt- 7/(Z2)cr. По Таблице прогнозов определяем, что такому условию удовлетворяет способ резервирования f = 3, т. е. переход к реализации асинхронного резервировани работ aj и не назначению контрольных работ bj, что и отражено на рис. 1. Заключение
Предложен подход к организации адаптивного (перенастраиваемое в динамике по реальным событиям в системе) резервирования взаимосвязанных программных модулей на основе сочетании вариантов синхронного и асинхронного их резервирования. Разработана математическая модель и алгоритмические методы для исследования свойств и эффектов адаптивного резервирования программных модулей КВР для обеспечения надежного выполнения комплексов резервированных программных модулей в управляющих параллельных вычислительных системах — как в штатном режиме функционирования ВС, так и в условиях ошибок (сбоев или отказов).
Список литературы
1. Елисеев В. В., Игнатущенко В. В. О проблеме надежного выполнения сложных наборов задач в управляющих параллельных вычислительных системах // Проблемы управления. — 2006. — № 6. — С. 6−18.
2. Игнатущенко В. В., Исаева Н. А. Резервирование взаимосвязанных программных модулей для управляющих параллельных вычислительных систем: организация, оценка
отказоустойчивости, формализованное описание // Автоматика и телемеханика. — 2008. -№ 10. — С. 142−161.
3. Игнатущенко В. В., Исаева Н. А. Интеллектуальное динамическое управление параллельными резервированными взаимосвязанными задачами со случайными временами их выполнения в управляющих параллельных вычислительных системах // Труды Пятой международной конференции «Параллельные вычисления и задачи управления» (РАСО'-2010). — М.: Институт проблем управления им. В. А. Трапезникова, РАН. — 2010. -С. 643−651.
4. Исаева Н. А. Организация динамического адаптивного резервирования взаимосвязанных программных модулей в управляющих параллельных вычислительных системах реального времени // Труды Пятой международной конференции «Управление развитием крупномасштабных систем (МЬ8Б'-2011)» (3−5 октября 2011 г., Москва, Россия). — М.: Институт проблем управления им. В. А. Трапезникова, РАН. — 2011. — Т. II. — С. 230−238.
5. Исаева Н. А., Королев С. С. Синхронное резервирование взаимозависимых параллельных задач для управляющих параллельных вычислительных систем: формализованное описание, оценка отказоустойчивости // Надежность. — 2009. — № 1. — С. 326.
6. Панов С. С. Математические модели синхронного резервирования взаимосвязанных программных модулей для управляющих параллельных вычислительных систем: новые варианты // Труды XXXVIII междунар. конф. «Информационные технологии в науке, социологии, экономике и бизнесе» (ГГ+8Е& quot-11) (Украина, Ялта-Гурзуф, май 2011). — 2011. — С. 56−59.
7. Панов С. С. Организация адаптивного резервирования комплексов взаимосвязанных программных модулей на основе сочетания различных вариантов синхронного их резервирования в управляющих параллельных вычислительных системах // Материалы Х Ы междунар. конф. «Информационные технологии в науке, социологии, экономике и бизнесе» (П+8Е& quot-13) (Украина, Ялта-Гурзуф, октябрь 2013). — 2013. — С. 49−51.
8. Травов А. В. Организация новых вариантов асинхронного резервирования взаимосвязанных программных модулей для управляющих параллельных вычислительных систем // Труды XXXVIII междунар. конф. «Информационные технологии в науке, социологии, экономике и бизнесе» (IT+SE& quot-11) (Украина, Ялта-Гурзуф, май 2011). — 2011. — С. 63−65.
9. Исаева Н. А. Унифицированная математическая модель системы массового обслуживания для прогнозирования надежного выполнения взаимосвязанных программных модулей (задач) при различных методах и сочетаниях их резервирования в управляющих
параллельных вычислительных системах // Открытое образование. — 2011. — № 2 (85). — Ч. 2. — С. 55−59.
Рецензенты:
Вишневский В. М., д.т.н., зав. лаб., Институт проблем управления им. В. А. Трапезникова Российской академии наук, г. Москва-
Бабаян Р. Р., д.т.н., зав. лаб., Институт проблем управления им. В. А. Трапезникова Российской академии наук, г. Москва.

ПоказатьСвернуть
Заполнить форму текущей работой