Development of the equivalent transformation of GERT-networks methods for multiversion software analysis

全文:

Как уже не раз отмечалось, мультиверсионное программное обеспечения (ПО) обладает рядом особенностей, которые и позволяют классифицировать различное ПО по принципу, является ли оно мульти-версионным. Одной из особенностей является то, что область применения мультиверсионного программного обеспечения остается достаточно узкой в связи с тем, что повышение надежности при таком подходе идет за счет программной и ресурсной избыточности [1]. Вследствие этого большая часть таких программ используется для управления объектами, для которых надежность является ключевой характеристикой (например, космическая промышленность). Это обстоятельство, в свою очередь, затрудняет получение реальных технических характеристик таких систем [2]. С другой стороны, анализ мультиверсионного ПО можно проводить, основываясь на распределенных системах обработки информации. Ведутся исследования в этом направлении [3]. В настоящее время практически все большие программные системы являются распределенными. Распределенной называется такая система, в которой обработка информации сосредоточена не на одной вычислительной машине, а распределена между несколькими компьютерами. Зачастую, в таких системах компьютер пользователя управляется одной операционной системой (ОС), компьютер по сбору заявок на обработку запросов - второй, а компьютеры - узлы системы могут управляться третьей ОС, отличной от первых двух. В таком случае эти системы называются распределенными гетерогенными системами обработки информации. Подобные системы могут быть построены при помощи готовых библиотек. Для примера возьмем проект Condor (http://www.cs.wisc.edu/condor). Condor позволяет использовать в составе единого кластера узлы, не только различающиеся в аппаратной части, но и работающие под разными операционными системами, что дает возможность использовать для вычислений существующую компьютерную технику и уже имеющиеся коммуникации, тем самым существенно удешевляя стоимость создания кластера [4]. Condor имеет несколько режимов запуска вычислительных задач: Standard, Vanilla, PVM, MPI, Globus, Java. Режимы PVM, MPI, Globus и Java - это поддержка совместимости для программ, написанных с использованием данных библиотек, поэтому мы не будем их рассматривать. Наиболее интересными с точки зрения мультиверсионного подхода являются режимы Standard (с резервным копированием) и Vanilla (без резервного копирования) [5]. В режиме Standard Condor делает контрольные точки с заданным интервалом. Контрольная точка -это «снимок» текущего состояния задачи. Если необходима миграция задачи (например, пользователь начал использование компьютера), то Condor создает образ контрольной точки, перемещает его на другую машину и возобновляет вычисления с места, где он остановился. Если вычисляющий узел завершил работу аварийно или нарушилась связь с узлом, то Condor размещает на другом узле последний сохраненный образ контрольной точки задачи и возобновляет вычисления. Таким образом, задача может непрерывно вычисляться в течение длительного периода времени. Данный режим соответствует режиму выполнения задачи с периодическим выполнением резервного копирования ее состояния. Режим Vanilla позволяет запускать произвольное консольное приложение, но не позволяет осуществить миграцию и резервное копирование задачи. Ниже представлены функциональные схемы ГЕРТ-сети, моделирующие поведение системы Condor при расчете задачи с фиксированной продолжительностью в режимах без резервного копирования и миграции (рис. 1). ГЕРТ-сеть, изображенная на рис. 2, состоит из узлов, соответствующих началу и завершению каждой отдельной работы, и дуг, представляющих действительное время выполнения каждой работы. Перед тем как перейти к поиску петель данной сети, произведем некоторые преобразования, которые существенно упростят сеть [6]. Соответствующие замены показаны на рис. 3-5. Таким образом, удалось получить эквивалентную сеть, показанную на рис. 6, для которой существенно упростился поиск петель. 12 Вестник СибГАУ. № 1(53). 2014 Рис. 1. Функциональная схема работы системы Condor в режиме Vanilla Рис. 2. ГЕРТ-сеть, описывающая работу системы Condor в режиме Vanilla 13 Математика, механика, информатика \Л/з + W4 ЛЛ/5 6 7Экв. Рис. 3. Применение эквивалентных преобразований для узлов 3 и 5 W-ю -W-, 1 Рис. 4. Применение эквивалентных преобразований для узлов 5 и 6 W-I6 W-|7 1 Рис. 5. Применение эквивалентных преобразований для узлов 9 и 11 12 13 Экв. 19 Экв. 14 Вестник СибГАУ. № 1(53). 2014 W22 W3 + W4 ' W5 6 7Экв. W10 'W11 12 13 Эке W15 W16-W,7 1 Рис. 6. Эквивалентная ГЕРТ-сеть, описывающая работу системы Condor в режиме Vanilla По сети (рис. 6) определим соответствующие эквивалентные коэффициенты пропускания петель первого и второго порядка. Петли первого порядка: ^■ Щ, ■ Ww ■ W , W ■ W2 ■ W8 ■ W9 ■ Wi4-Wi5 (W3 -W ■ W ) 4 5,6,7экв. / : W ■ W ■ W ■ W ■ W ■ W ■ W ■ W ■ W rr1 2 8 9 14 16 17,18,19 экв. 20 22 W1 W ■ W8 ■ W9 ■ W14 ■ W16 ■ W17, 18, 19экв. ■ W20 ■ W21 ■W, ■W, Петли второго порядка: W 8 ■ W10 Используя топологическое уравнение, получаем следующую эквивалентную W-функцию для ГЕРТ-сети, которая описывает работу системы без резервного копирования: WF (t) = WWWWW W W W W n 1 2n 8n 9n 14^ 16^ 17Д8,19экв. 20^ 21 1- W -WW W 24 8 1a 11,12,13экв. - - W1W2W8W9W14W15 (W3 + W4W5,6,7эке.) WWWWW W W W W yy 1ГГ 2rr 8n 9УУ 14" l^c 17,18,19экв. 20'' 21 , WWWWW W W WW yy 2П tfy 9УУ 14ГГ ^уу 17,18,19экв. 20" 22 WWWWW W W W W , l" r' 8" 9" 1/ 16" 17,18,19экв. 20" 21 WW W W ' 8 10 11,12,13экв. 24 Используя полученные функции можно получить математическое ожидание и дисперсию. Методы эквивалентного преобразования ГЕРТ-сетей позволяют упростить поиск петель и расчеты характеристик сети.

作者简介

Dmitry Kovalev

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: saor_sibsau@mail.ru
postgraduate student

Mikhail Saramud

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: saramud@bk.ru
postgraduate student

Margarita Karaseva

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: karaseva-margarita@rambler.ru
Candidate of Engineering Sciences, associate professor, associate professor of the Department of System and operation analysis

Yliya Nurgaleeva

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: saornurgaleeva@sibsau.ru
engineer, postgraduate student

参考

补充文件